Revisiting Stochastic Multi-Level Compositional Optimization

This paper explores stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth functions. Traditional methods for solving this problem suffer from either sub-optimal sample complexities or require huge batch sizes. To address these limitations, we introduce the Stochastic Multi-level Variance Reduction (SMVR) method. In the expectation case, our SMVR method attains the optimal sample complexity of $\mathcal {O}(1/\epsilon ^{3})$O(1/ε3) to find an $\epsilon$ε-stationary point for non-convex objectives. When the function satisfies convexity or the Polyak-Łojasiewicz (PL) condition, we propose a stage-wise SMVR variant. This variant improves the sample complexity to $\mathcal {O}(1/\epsilon ^{2})$O(1/ε2) for convex functions and $\mathcal {O}(1/(\mu \epsilon ))$O(1/(με)) for functions meeting the $\mu$μ-PL condition or $\mu$μ-strong convexity. These complexities match the lower bounds not only in terms of $\epsilon$ε but also in terms of $\mu$μ (for PL or strongly convex functions), without relying on large batch sizes in each iteration. Furthermore, in the finite-sum case, we develop the SMVR-FS algorithm, which can achieve a complexity of $\mathcal {O}(\sqrt{n}/\epsilon ^{2})$O(n/ε2) for non-convex objectives, $\mathcal {O}(\sqrt{n}/\epsilon \log (1/\epsilon ))$O(n/εlog(1/ε)) for convex functions and $\mathcal {O}(\sqrt{n}/\mu \log (1/\epsilon ))$O(n/μlog(1/ε)) for objectives satisfying the $\mu$μ-PL condition, where $n$n denotes the number of functions in each level. To make use of adaptive learning rates, we propose the Adaptive SMVR method, which maintains the same complexities while demonstrating faster convergence in practice.