Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates

Understand

In this paper, we study smooth stochastic multi-level composition optimization problems, where the objective function is a nested composition of $T$ functions.

• We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle.
• For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze their convergence to an $\epsilon$-stationary point of the problem.
• We show that the first algorithm, which is a generalization of \cite{GhaRuswan20} to the $T$ level case, can achieve a sample complexity of $\mathcal{O}(1/\epsilon^6)$ by using mini-batches of samples in each iteration.