Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
Abstract
This paper investigates stochastic multi-level optimization where the objective is a nested composition of several smooth non-convex functions. We assume that only stochastic estimates of the gradient and function values for each level are accessible. Consequently, obtaining an accurate estimate of the overall gradient is challenging due to the nested structure. To address this, we employ a momentum-based estimator with mini-batches to track the function values of each level, which are subsequently used to construct momentum gradient estimators. We establish an optimal sample complexity of 𝒪(ε−4) for finding an ε-stationary point, avoiding the stronger average smoothness assumption commonly relied upon in prior literature. Furthermore, by employing a normalization technique, we attain the same rate without requiring problem-dependent constants to set hyperparameters. To achieve the optimal rate without mini-batches, we further develop a batch-free method that incorporates a first-order approximation and a clipping technique for function value estimation. Finally, we validate the effectiveness of our proposed methods through experiments on risk-averse portfolio optimization and hierarchical tilted empirical risk minimization.
Related
- Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
- Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
- Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
- A Stochastic Optimization Approach to Control-Affine Optimal Control Problems
- Optimal Stochastic Bilevel Optimization with First-Order Oracles
BibTeX
@misc{jiang2026optimal,
title = {{Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization}},
author = {Wei Jiang and Rui Yan and Sifan Yang and Yuanyu Wan and Lijun Zhang and Zechao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01572},
eprint = {2610.01572},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01572},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
AU - Wei Jiang
AU - Rui Yan
AU - Sifan Yang
AU - Yuanyu Wan
AU - Lijun Zhang
AU - Zechao Li
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01572
UR - https://arxiv.org/abs/2610.01572
AB - This paper investigates stochastic multi-level optimization where the objective is a nested composition of several smooth non-convex functions. We assume that only stochastic estimates of the gradient and function values for each level are accessible. Consequently, obtaining an accurate estimate of the overall gradient is challenging due to the nested structure. To address this, we employ a momentum-based estimator with mini-batches to track the function values of each level, which are subsequently used to construct momentum gradient estimators. We establish an optimal sample complexity of 𝒪(ε^−4) for finding an ε-stationary point, avoiding the stronger average smoothness assumption commonly relied upon in prior literature. Furthermore, by employing a normalization technique, we attain the same rate without requiring problem-dependent constants to set hyperparameters. To achieve the optimal rate without mini-batches, we further develop a batch-free method that incorporates a first-order approximation and a clipping technique for function value estimation. Finally, we validate the effectiveness of our proposed methods through experiments on risk-averse portfolio optimization and hierarchical tilted empirical risk minimization.
ER -