aiqbench analysis
This paper is theoretical optimization research: it proves upper and lower bounds on how many gradient or oracle calls are needed to minimize a finite sum of convex functions under a relaxed smoothness condition. The proposed YETI method combines accelerated proximal and variance-reduction techniques, and the authors test it on synthetic problems and Poisson regression. For ML readers, the main value is a sharper complexity benchmark for finite-sum training objectives, not a practical system or product. Its results apply to convex problems, so the implications for training non-convex deep networks are indirect.
Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions
arXiv:2611.04171v1 Announce Type: cross 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 $\delta$ 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 $\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2\delta)R^2}{\varepsilon}+n(L_1R)^2}$. 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.
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 $\delta$ 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 $\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2\delta)R^2}{\varepsilon}+n(L_1R)^2}$. 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.
57 pages, 4 figures, 5 tables, 5 algorithms. Second paper in the Descending Everest series; Part I: arXiv:2610.21461
Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2611.04171 [math.OC]
(or arXiv:2611.04171v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2611.04171 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 · 319 words
Related coverage
Training and Simulation of Quadrupedal Robot in Adaptive Stair Climbing and Descending for Indoor Firefighting: An End-to-End Reinforcement Learning Approach
arXiv · Jul 23, 2026
Scattered thoughts on how doing math feels these days
LessWrong · Oct 27, 2026
FlyCNS: Connectome-Grounded Information Organization for Communication-Constrained Embodied Control
arXiv · Sep 25, 2026
Researchers Link Circuit Complexity to Learning Ability
Quantum Zeitgeist · Sep 3, 2026