aiqbench analysis
This research advances stochastic multi-level optimization by introducing momentum-based estimators that achieve optimal sample complexity without relying on strong average smoothness assumptions. The proposed batch-free method further eliminates the need for mini-batches, utilizing first-order approximations and clipping to handle nested non-convex functions efficiently. These theoretical improvements are validated through applications in risk-averse portfolio optimization and hierarchical empirical risk minimization.
Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
arXiv:2610.01572v1 Announce Type: cross 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 $\mathcal{O}(\epsilon^{-4})$ for finding an $\epsilon$-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.
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 $\mathcal{O}(\epsilon^{-4})$ for finding an $\epsilon$-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.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2610.01572 [math.OC]
(or arXiv:2610.01572v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2610.01572 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 266 words
Related coverage
Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization
arXiv · Jul 29, 2026
Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
arXiv · Oct 12, 2026
Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
arXiv · Sep 15, 2026
OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimality
arXiv · Jun 9, 2026