math.OCNov 3, 2026

Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)(L_0,L_1)-Smooth Functions

Authors: Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov, Fedor S. Stonyakin

Organizations: MIRIAI, Moscow Independent Research Institute of Artificial Intelligence, Moscow, Russia. · Yandex, Moscow, Russia. · Innopolis University, Innopolis, Russia, Moscow Institute of Physics and Technology, Moscow, Russia. · Moscow Institute of Physics and Technology, Moscow, Russia, V. I. Vernadsky Crimean Federal University, Simferopol, Russia.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study the minimization of the average of nn convex (L0,L1)(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 RR 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 ε\varepsilon 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)2n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2δ)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.

Figures & tables

Figure 1: Flowchart of the method YETI.
Figure 2: Best relative optimality gap so far on the first instance of each family (log–log scale; YETI in red; κ\kappa is the condition number of the feature covariance).
Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Fraction of the 65 problems on which the number of queries does not exceed the best result by more than a factor of τ\tau ( Dolan and Moré, 2002 ) . At τ=1\tau=1 , all first places are counted, including shared ones; failed runs remain in the denominator.
FamilyYETIL-BFGSCov-LBFGSCov-LBFGSBFGSNesterovGRAALSVRG
  (50)1/41/41/21/2    
Rotated, 10410^{4}6.016333153371969——
Rotated, 10810^{8}6.0261715515725———
High dimension7.044042371123———
Strong nonlinearity8.045242740323108034
Rare features11572719229670161494
Appendix
Table 1: Median number of passes to relative accuracy 10−610^{-6} over five instances. “—” indicates failure on at least one instance; the minimum before rounding is shown in bold. κ\kappa is the condition number of the feature covariance, and n×dn\times d are the number of components and the dimension.
 S, length TTX, length TT
Method81632648163264
YETI224480158213981151
L-BFGS224387181214188175
BFGS39791573132755111217
Katyusha223436868172626551410092005
Nesterov821823777631594168731850
Appendix
Table 2: Number of passes to relative accuracy 10−210^{-2} on the chains. The minimum before rounding is shown in bold; “—” indicates that the tolerance was not reached within the allotted number of passes.
  To 10−2Δ^10^{-2}\widehat{\Delta}To the stopping criterion
FamilyTTYETINoRandomYETINoRandom
   proposalsproposals proposalsproposals
S8228981929027234346145
S1644229943590476329113107
X821121863896333837177593
X16391968106768557418—
Appendix
Table 3: Number of passes for three variants of the heuristic. The method’s own stopping criterion uses ε=10−3Δ^\varepsilon=10^{-3}\widehat{\Delta} . “—” indicates that it was not satisfied within 200000 passes.
 Synthetic problems, nnBikefreMTPL2
Method200020002000020000100000100000Sharingfreq
YETI4.05.05.09.07.0
L-BFGS197168994422
Cov-LBFGS 1/41/42223162112
BFGS35332525326116
Nonlinear CG705707359108102
Appendix
Table 4: Number of passes to relative accuracy 10−410^{-4} on the Poisson models. Notation as in Table 2 .
Figure 4: Optimality gap relative to the reference value and its history-based upper bound at ε=10−9Δ^\varepsilon=10^{-9}\widehat{\Delta} . All quantities are divided by Δ^\widehat{\Delta} ; the dotted line indicates the threshold ε/2\varepsilon/2 . Values below 10−1410^{-14} are shown at the lower boundary of the axis.
More in this topic

Smooth Convex Optimization

See all 16 papers

Explore similar work

CardsList

  1. Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness

    Oct 30, 2026Xinliang Zhang, Lesi Chen, Zonghan Li +1Smooth Convex OptimizationSecond-Order Optimization

    IIIS, Tsinghua University

  2. Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

    Jun 3, 2026Dongruo ZhouOptimization Convergence AnalysisNonconvex Optimization

    Department of Computer Science, Indiana University Bloomington, IN 47408, USA

  3. Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity

    Nov 3, 2026Cedar Site BaiSmooth Convex OptimizationOracle Complexity

    Department of Computer Science, Purdue University