Computational Math Colloquium | Saeed Ghadimi, Stochastic Nested Composition Optimization

Thursday, March 16, 2023 1:30 pm - 1:30 pm EDT (GMT -04:00)

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.