A Tale of Two-timescale Stochastic Approximation and Random Topology

Speaker : Dr. Gugan Thoppe, Duke University

Title : A Tale of Two-timescale Stochastic Approximation and Random Topology

Date : Tuesday, March 12, 2019

Time : 10:00 AM

Venue : CSA Seminar Hall (Room No. 254, First Floor)

Abstract

The first part of the talk concerns Stochastic Approximation (SA) which refers to any algorithm that resembles a noisy Euler method for solving an ODE. Specifically, we shall discuss two-timescale SA; these mimic methods with nested for-loops and are quite useful in stochastic optimization/control, etc. Using a neat induction trick, our key result is a tight convergence rate estimate for linear two-timescale SA. This answers a long-standing open question on their finite time behaviour.

The second part is about the topology of random Simplicial Complexes (SCs); in particular, it deals with Minimal Spanning Acycles (MSAs), Persistence Diagrams (PDs), and Betti numbers. SCs are generalizations of graphs which, in addition to vertices and edges, also have other higher dimensional faces (e.g., triangles, etc.). Loosely, an MSA is a generalization of a minimal spanning tree in higher dimensions, while a PD records times at which different holes appear and disappear when a given SC is sequentially built (e.g., first by adding the vertices, then edges, etc.). Separately, Betti numbers are the number of holes of different dimensions. We will begin our discussion by looking at the connections between MSAs and PDs; this generalizes the relationship between MSTs and
connectivity thresholds in graphs. As an application, we shall see that both, the set of extremal deaths in the PD and the set of extremal weights in the MSA associated with the so-called randomly weighted d−Linial-Meshulam (LM) complex, converge to a Poisson point process. Using a novel stability result, we shall also see that Frieze’s $zeta(3)$ result and its recent generalization continue to hold even in suitable noisy settings. Following this, we shall discuss a novel streaming algorithm for MSAs in a randomly weighted d-LM complex. Lastly, we shall look at a central limit theorem for Betti numbers of Costa-Farber Complexes.

Biography of the speaker

Gugan Thoppe is a Postdoctoral Associate at Duke University, USA with Prof. Sayan Mukherjee. Earlier, he worked with Prof. Robert Adler as an EC Senior Researcher (postdoc) at Technion, Israel. He did his PhD in Systems Science with Prof. Vivek Borkar at TIFR, India. His work won the TAA-Sasken best thesis award for 2017. He is also a two-time recipient of the IBM PhD fellowship award (2013–14 and 2014-15). His research interests include random topology and stochastic approximation.

Host Faculty : Prof. Matthew Jacob

ALL ARE WELCOME