Optimal Algorithms for Stochastic Multi-Level Compositional Optimization

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

Many modern machine learning problems involve "nested" objective functions, where the goal is to minimize a composition like $F(w) = f_K(f_{K-1}(\dots f_1(w)\dots))$. This structure frequently appears in reinforcement learning (e.g., Bellman equations), meta-learning (e.g., MAML), and risk-averse portfolio optimization.

However, optimizing these nested functions introduces a significant challenge known as the "curse of depth." In standard stochastic gradient descent, we need an unbiased estimate of the gradient. For a composition, the gradient involves the chain rule—specifically, products of Jacobians. Estimating these from noisy samples is notoriously difficult because errors in the inner layers compound and explode as they propagate to the outer layers. Previous "optimal" algorithms attempted to fix this by using massive, impractical batch sizes that grew as the required precision ($\epsilon$) increased.

This paper asks a crucial question: Can we achieve optimal efficiency using only small, constant-sized batches? The answer is yes, through a novel algorithm called SMVR (Stochastic Multi-level Variance Reduction).

The SMVR Algorithm

SMVR is the first algorithm to achieve optimal sample complexity for multi-level compositional optimization without requiring massive batch sizes. It leverages a momentum-based variance reduction technique (inspired by the STORM algorithm) applied to both function values and Jacobians. Key components include:

  • Nested Variance Reduction: SMVR maintains two sequences of estimators for every level $i$: $u_t^i$ to estimate the function value and $v_t^i$ to estimate the Jacobian.
  • The Projection Step: To prevent the "error blow-up" common in deep compositions, the Jacobian estimators are projected onto a ball of radius $L_f$ (the Lipschitz constant). This ensures that even if individual estimates are noisy, the overall gradient estimate remains bounded and stable.
  • Stage-wise SMVR: For convex functions or those satisfying the Polyak-Łojasiewicz (PL) condition, the authors develop a version that runs in stages. Each stage uses a fixed learning rate and a set number of iterations, effectively "halving" the error at each step to reach faster convergence.
  • Adaptive SMVR: The authors also integrate Adam-style adaptive learning rates, allowing the algorithm to automatically adjust to the geometry of the problem while maintaining the same theoretical optimality.

Key Insights and Results

The most significant theoretical insight of this work is that optimality is possible with small batches. You do not need $O(1/\epsilon)$ batch sizes to be optimal. By carefully managing the variance of both function values and Jacobians simultaneously, $O(1)$ batches are sufficient. Surprisingly, SMVR's sample complexity matches the lower bounds of one-level stochastic optimization, suggesting that with the right variance reduction, the multi-level structure doesn't make the problem fundamentally "harder" in terms of sample efficiency.

Theoretically, SMVR achieves a mathematically optimal sample complexity of $O(1/\epsilon^3)$ for non-convex objectives. For convex and PL conditions, it hits $O(1/\epsilon^2)$ and $O(1/\mu\epsilon)$, respectively.

Empirically, the researchers evaluated SMVR across three distinct tasks: Risk-Averse Portfolio Optimization, Hierarchical Tilted Empirical Risk Minimization (TERM), and Multi-step Meta-Learning (using the Omniglot dataset).

Results for Risk-Averse Portfolio Optimization comparing SMVR against baselines.

In all experiments, SMVR converged significantly faster than existing state-of-the-art methods like A-TSCGD, SCSC, and Nested-SPIDER. For instance, on the Omniglot benchmark, SMVR-ADAM (the adaptive version) increased accuracy much more rapidly than competitors, demonstrating its practicality for complex, high-dimensional deep learning tasks.

Limitations and Future Work

While SMVR represents a major step forward, it does have a few limitations:

  • Lipschitz Constants: The projection step requires an estimate of the Lipschitz constant $L_f$. While the algorithm is robust if $L_f$ is set to a large value, it still introduces a hyperparameter that might need tuning in practice.
Sensitivity analysis of SMVR to the Lipschitz constant parameter ($L_f$).
  • Smoothness Assumptions: The current analysis assumes the functions are smooth (Lipschitz continuous gradients). Extending these optimal rates to non-smooth multi-level problems remains an open challenge.
  • Memory Overhead: Maintaining estimators for every level of the composition increases memory usage compared to simple SGD, which could be a factor for extremely deep compositions.

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. E...
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