Momentum methods improve nested stochastic optimization efficiency
Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
Machine Learning
Summary
Optimizing problems made up of several layers of functions can be tricky because you only get noisy estimates of the steps needed to improve them. The authors develop smarter ways to combine information from each layer using momentum, which helps speed up finding good solutions. Their methods work well without needing some strong assumptions that others required before. They tested these techniques on financial portfolio choices and risk-sensitive prediction tasks, showing their approach works in practice.
What this means in practice
- •For financial engineers: Improve portfolio optimization under uncertain risk models by efficiently estimating nested risk measures with fewer samples.
- •For machine learning engineers: Enhance training of models involving hierarchical risk or composite objectives by using momentum-based estimators to reduce variance in nested gradients.
Authors
Wei Jiang, Rui Yan, Sifan Yang, Yuanyu Wan, Lijun Zhang, Zechao Li
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}(ε^{-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.