Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L 0,L 1) -Smooth Functions
math.OC, cs.LG, stat.ML
Submitted: 2026-11-03
Updated: 2026-11-05
Comments: 57 pages, 4 figures, 5 tables, 5 algorithms. Second paper in the Descending Everest series; Part I: arXiv:2610.21461
Code: https://github.com/chitoraphelion/descending-everest-wit
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the minimization of the average of n convex (L 0,L 1) -smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm.
Abstract
We study the minimization of the average of n convex (L 0,L 1) -smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds R on the distance from the starting point to a minimizer and δ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy epsilon in function value in expectation. Up to logarithmic factors, both bounds are of order n(1+(L 1R) 2/3) + sqrt n(L 0+L 1 2δ)R squared over epsilon+n(L 1R) squared. The upper bound is attained by the proposed method YETI. The method combines ideas of accelerated proximal methods and variance reduction methods with a heuristic for choosing additional points. The number of oracle calls made by the heuristic is bounded, which preserves the upper bound on the total number of queries needed to reach the target accuracy. In the experiments, YETI is compared with first-order methods on synthetic problems and Poisson regression problems. We also examine the stopping criterion and the effect of the heuristic separately. The lower bound is obtained by an explicit construction of families of instances that are hard for any first-order method.
Sources
- Lower Bounds for Finding Stationary Points I
- Optimal and Adaptive Monteiro-Svaiter Acceleration
- Robustness to Unbounded Smoothness of Generalized SignSGD
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity
- Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
- A unified variance-reduced accelerated gradient method for convex optimization
- Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
- Variance-reduced Clipping for Non-convex Optimization
- Descending Everest, Part I: Oracle Complexity of Convex Optimization under (L 0,L 1) -Smoothness
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods
- A Proximal Stochastic Gradient Method with Progressive Variance Reduction
- Mirror Descent Under Generalized Smoothness
- Why gradient clipping accelerates training: A theoretical justification for adaptivity
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise