Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-Smooth Functions
Abstract
We study the minimization of the average of n convex (L0,L1)-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 ε in function value in expectation. Up to logarithmic factors, both bounds are of order n(1+(L1R)2/3) +√((n(L0+L12δ)R2)/ε+n(L1R)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.
Related
- Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
- Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
- Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
BibTeX
@misc{rudomanov2026descending,
title = {{Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions}},
author = {Mikhail Rudomanov and Ivan Fomin and Alexander V. Gasnikov and Fedor S. Stonyakin},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04171},
eprint = {2611.04171},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04171},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L_0,L_1)-Smooth Functions
AU - Mikhail Rudomanov
AU - Ivan Fomin
AU - Alexander V. Gasnikov
AU - Fedor S. Stonyakin
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04171
UR - https://arxiv.org/abs/2611.04171
AB - 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 ε in function value in expectation. Up to logarithmic factors, both bounds are of order n(1+(L_1R)^2/3) +√((n(L_0+L_1^2δ)R^2)/ε+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.
ER -