Optimal Algorithms for Stochastic Multi-Level Compositional Optimization

Wei Jiang, Bokun Wang, Yibo Wang, Lijun Zhang, Tianbao Yang

Abstract

In this paper, we investigate the problem of stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth but possibly non-convex functions. Existing methods for solving this problem either suffer from sub-optimal sample complexities or need a huge batch size. To address these limitations, we propose a Stochastic Multi-level Variance Reduction method (SMVR), which achieves the optimal sample complexity of $\mathcal{O}\left(1 / \epsilon^{3}\right)$ to find an $\epsilon$-stationary point for non-convex objectives. Furthermore, when the objective function satisfies the convexity or Polyak-{\L}ojasiewicz (PL) condition, we propose a stage-wise variant of SMVR and improve the sample complexity to $\mathcal{O}\left(1 / \epsilon^{2}\right)$ for convex functions or $\mathcal{O}\left(1 /\left(\mu\epsilon\right)\right)$ for non-convex functions satisfying the $\mu$-PL condition. The latter result implies the same complexity for $\mu$-strongly convex functions. To make use of adaptive learning rates, we also develop Adaptive SMVR, which achieves the same complexities but converges faster in practice. All our complexities match the lower bounds not only in terms of $\epsilon$ but also in terms of $\mu$ (for PL or strongly convex functions), without using a large batch size in each iteration.

Introduction

Stochastic multi-level compositional optimization is a fundamental challenge in modern machine learning, appearing in applications such as multi-step meta-learning (MAML), risk-averse optimization, and reinforcement learning. These problems involve objective functions of the form $F(w) = f_K(f_{K-1}(\dots f_1(w)\dots))$. The primary difficulty, often termed the "curse of depth," arises from the accumulation and amplification of stochastic noise across nested layers. Previous approaches typically required either sub-optimal sample complexities or prohibitively large batch sizes to maintain stability, limiting their practical utility.

The SMVR Algorithm

To overcome these challenges, we introduce Stochastic Multi-level Variance Reduction (SMVR). SMVR is a single-loop algorithm that achieves theoretical optimality through several key innovations:

  1. Dual Variance Reduction: Unlike traditional methods, SMVR maintains separate estimators for both function values ($u^i_t$) and Jacobians ($v^i_t$) at every layer $i$.
  2. Nested STORM Estimators: The algorithm adapts the Stochastic Recursive Momentum (STORM) technique to a multi-level setting, allowing it to smooth noise by incorporating information from previous iterations.
  3. Jacobian Projection: To ensure stability in deep compositions, SMVR projects Jacobian estimators onto a ball of radius $L_f$ (the Lipschitz constant). This prevents error explosion without requiring the massive batch sizes used by previous state-of-the-art methods like Nested-SPIDER.
Sensitivity analysis of the projection radius $L_f$ on risk-averse portfolio optimization tasks. The results show that the algorithm is robust to the choice of $L_f$ as long as it is sufficiently large.

Empirical Evaluation

We evaluated SMVR against state-of-the-art baselines, including SCSC, A-TSCGD, Nested-SPIDER, and NLASG, across several distinct tasks.

Risk-Averse Portfolio Optimization

Using industrial asset payoff data from the Kenneth R. French Data Library (Industry-10, 12, 17, 30), we observed that SMVR consistently outperforms existing methods in both convergence speed and final objective value. Notably, SMVR maintains a constant batch size of $O(1)$, making it significantly more memory-efficient than methods requiring batch sizes that scale with $1/\epsilon$.

Comparison of SMVR against baseline algorithms on risk-averse portfolio optimization tasks. SMVR (solid red line) demonstrates superior convergence in both function value $F(w)$ and gradient norm $||\nabla F(w)||_2$.

Meta-Learning and TERM

In 5-step MAML experiments on the Omniglot dataset, SMVR and its adaptive variant (SMVR-ADAM) reached higher test accuracy faster than all baselines. Similar performance gains were observed in Hierarchical Tilted Empirical Risk Minimization (TERM) tasks on datasets like HIV-1 and Breast-cancer, where SMVR demonstrated better robustness to ill-conditioned problems.

Conclusion

SMVR provides the first optimal sample complexity for multi-level compositional problems—$O(1/\epsilon^3)$ for non-convex and $O(1/\epsilon^2)$ for convex objectives—effectively matching single-level lower bounds. By utilizing constant batch sizes and robust Jacobian projection, SMVR offers a practical and theoretically sound framework for deep compositional optimization. Future research may extend these optimal rates to non-smooth multi-level problems common in robust reinforcement learning.

Summary updated

Abstract

In this paper, we investigate the problem of stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth but possibly non-convex functions. Existing methods for solving this problem either suffer from sub-optimal sample complexities or need a huge batch size. To address these limitations, we propose a Stochastic Multi-level Variance Reduction method (SMVR), which achieves the optimal sample complexity of $\mathcal{O}\left(1 / \epsilon^{3}\right)$ to find an $\epsilon$-stationary point for non-convex objectives. Furthermore, when the objective function satisfies the convexity or Polyak-{\L}ojasiewicz (PL) condition, we propose a stage-wise variant of SMVR and improve the sample complexity to $\mathcal{O}\left(1 / \epsilon^{2}\right)$ for convex functions or $\mathcal{O}\left(1 /\left(\mu\epsilon\right)\right)$ for non-convex functions satisfying the $\mu$-PL condition. The latter result implies the same complexity for $\mu$-strongly convex functions. To make use of adaptive learning rates, we also develop Adaptive SMVR, which achieves the same complexities but converges faster in practice. All our complexities match the lower bounds not only in terms of $\epsilon$ but also in terms of $\mu$ (for PL or strongly convex functions), without using a large batch size in each iteration.
BibTeX
@inproceedings{jiang2022optimal,
  author = {Wei Jiang and Bokun Wang and Yibo Wang and Lijun Zhang and Tianbao Yang},
  title = {{Optimal Algorithms for Stochastic Multi-Level Compositional Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=m2q35QGk-3J},
}
Figure