On Stochastic Approximation, Stochastic Algebraic Topology, and Optimization in High Dimensions

In this talk, we shall discuss three problems respectively from stochastic approximation, stochastic algebraic topology, and optimization in high dimensions.

\textbf{Problem 1:} Stochastic approximation (SA) refers to algorithms that attempt to find optimal points or zeroes of a function when only its noisy estimates are available. Given $\epsilon > 0,$ sample complexity of SA algorithm is the probability that its iterates are eventually within an $\epsilon-$neighbourhood of a desired solution, conditioned on the event that the iterates did enter some bigger neighbourhood of this desired solution. In the first part of this talk, we shall obtain a tight sample complexity estimate by making use of the Alekseev's analogue of variation of constants formula for nonlinear systems and a generalization of a concentration result from Liu and Watbled, 2009.

\textbf{Problem 2:} In stochastic algebraic topology, one is interested in the algebraic topology of random sets. In the second part of this talk, we shall discuss a time varying analogue of the Erdos-Renyi graph, which we call the dynamic Erdos-Renyi graph, and concentrate on the topological aspects of its clique complex. Each edge of the dynamic Erdos-Renyi graph independently evolves as a continuous time on/off Markov chain such that the connection probability is $p$ at all times. Our main result is the weak convergence to stationary Ornstein-Uhlenbeck process of a (normalized) random process determined by $k-$th Betti number of the clique complex associated with the graph when $p=n^\alpha,$ with $\alpha \in (−1/k,−1/(k+1)).$

\textbf{Problem 3:} High dimensional unconstrained quadratic programs (UQPs) involving massive datasets are now common. Without computational resources that match up to these datasets, solving such problems using classical UQP methods is very difficult. In the third part of this talk, we shall first define high dimensional compliant (HDC) methods for UQPs---methods that can solve high dimensional UQPs by adapting to available computational resources. We will then show that the class of block Kaczmarz and block coordinate descent (BCD) are the only existing methods that can be easily made HDC. We shall then discuss a novel deterministic, but adaptive, greedy BCD (GBCD) method for high dimensional UQPs. We shall also see theoretical and experimental tests that demonstrate the effectiveness of GBCD.