A momentum-based estimator with mini-batches is employed to track the function values of each level, which are subsequently used to construct momentum gradient estimators, and a batch-free method that incorporates a first-order approximation and a clipping technique for function value estimation is developed.
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.
This work proposes a fully Hessian-inverse-free stochastic gradient method for SMOBO which is computationally efficient due to the use of a decoupling approach, and employs a momentum-like gradient estimate to replace the stochastic gradients with their moving average, thereby mitigating the errors induced by dynamic w...
This paper studies projection-free algorithms for stochastic constrained multi-level compositional optimization and proposes variance-reduced projection-free algorithms and establishes complexity guarantees under both the Frank-Wolfe gap and the gradient mapping criteria.
Wei Jiang, Si-Fan Yang, Wen-Hao Yang et al.· 3 citations
Partially Informed Stochastic Optimization (PISO) is introduced, which combines the available gradient component with a running estimate of the residual to establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient compon...
El Mahdi Chayti, Alireza Mirrokni, Martin Jaggi· 0 citations
An alternative to the standard random gradient estimator is introduced, allowing for the projection step of spectral descent to be done at no extra cost and it is shown that by exploiting this low-rank property one obtains much faster convergence to good approximate solutions.
S. Allen, Cash Cherry, Aidan Eck et al.· 0 citations
Traditional variance reduction methods (e.g., SPIDER, SARAH, STORM) have been extensively investigated for improving the convergence rates of stochastic optimization. These techniques typically maintain a sequence of estimators for a single function (or gradient) across iterations. However, what if we need to track mul...
Wei Jiang, Si-Fan Yang, Yi-Bo Wang et al.· 0 citations
A line-search-free and function-value-free adaptive projected-gradient algorithm for the sample-average approximation (SAA) problem that transfers vanishing SAA residuals to Pareto stationarity for the population problem, while an additional concentration argument gives a finite-sample residual bound on compact sets.
Yi-Yang Li, Lei Wang, Xiao-Jun Chen· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026