MC 5501 and Zoom (email compmath@uwaterloo.ca for Zoom link)
Speaker
Saeed Ghadimi | University of Waterloo
Title
Stochastic Nested Composition Optimization
Abstract
Recently, stochastic nested composition optimization (SNCO) problems whose objective function is a composition of two or more exceptions, have gained much interest due to their emerging applications including risk-averse optimization and training large-scale graph neural networks. The main challenge in solving SNCO problems is that an unbiased estimator for the gradient of the objective function with a bounded second moment is not readily available and hence the classical stochastic optimization methods are not directly applicable.
In this talk, we will present a few settings under which we can provide efficient first-order stochastic approximation algorithms to find an approximate stationary point of the SNCO problems. We will further show that by properly defining a Lyapunov function, we can establish the finite-time convergence analysis of these algorithms such that their sample complexities match that of the single level stochastic optimization problems and hence are optimal in terms of dependence on the target accuracy while only polynomially depend on the number of compositions in the objective function.
