AI & Applications

Nonconvex Stochastic Nested Optimization - Saeed Ghadimi, Assistant Professor, University of Waterloo.

Please register for this event here.

Abstract:

In this talk, I present a class of stochastic optimization problems in which the objective function is a composition of two or more expectations. This class of problems arises in several applications such as low-rank matrix estimation, policy evaluation for Markov decision processes, and compressed sensing. I will first present a Nested Averaging Stochastic Approximation (NASA) algorithm for solving this non-classical optimization problem when the objective function is a composition of two functions and show that it achieves the well-known sample complexity of $O(1/\epsilon^4)$ for finding an $\epsilon$-stationary point of the problem which seems to be unimprovable even for single-level general smooth stochastic optimization. The convergence analysis of the NASA method is the same for both constrained and unconstrained problems and it does not require a batch of samples per iteration. This property makes NASA attractive for the online setting.

I will then present two generalizations of the NASA algorithm when we have a composition of more than two functions. While the first algorithm achieves a sample complexity of $O(1/\epsilon^6)$ by taking a mini-batch of samples per iterations, its modified variant relaxes such a requirement and possesses the unimprovable complexity of $O(1/\epsilon^4)$ regardless of the number of composition functions.

Bio:

Saeed Ghadimi is an assistant professor in the Department of Management Sciences at the University of Waterloo. Before joining UWaterloo, he was an associate research scholar at Princeton University. He also received his PhD with a major in Industrial and Systems Engineering and a minor in Mathematics from University of Florida.
His research is mainly focused on decision making under uncertainty. In particular, he works on a) reinforcement learning and stochastic optimization, b) developing first- and second-order algorithms for data analytics and large scale optimization problems, c) simulation-based optimization, and d) developing computational lower bounds.

Please register for this event here.