Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-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.
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.
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; κ 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 τ ( Dolan and Moré, 2002 ) . At τ=1 , all first places are counted, including shared ones; failed runs remain in the denominator.
Family
YETI
L-BFGS
Cov-LBFGS
Cov-LBFGS
BFGS
Nesterov
GRAAL
SVRG
(50)
1/4
1/2
Rotated, 104
6.0
163
33
15
337
1969
—
—
Rotated, 108
6.0
2617
155
15
725
—
—
—
High dimension
7.0
440
42
37
1123
—
—
—
Strong nonlinearity
8.0
45
24
27
40
323
1080
34
Rare features
11
57
27
19
229
670
1614
94
Appendix
Table 1: Median number of passes to relative accuracy 10−6 over five instances. “—” indicates failure on at least one instance; the minimum before rounding is shown in bold. κ is the condition number of the feature covariance, and n×d are the number of components and the dimension.
S, length T
X, length T
Method
8
16
32
64
8
16
32
64
YETI
22
44
80
158
21
39
81
151
L-BFGS
22
43
87
181
21
41
88
175
BFGS
39
79
157
313
27
55
111
217
Katyusha
223
436
868
1726
265
514
1009
2005
Nesterov
82
182
377
763
159
416
873
1850
Appendix
Table 2: Number of passes to relative accuracy 10−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Δ
To the stopping criterion
Family
T
YETI
No
Random
YETI
No
Random
proposals
proposals
proposals
proposals
S
8
22
898
19290
27
2343
46145
S
16
44
2299
43590
47
6329
113107
X
8
21
1218
63896
33
3837
177593
X
16
39
1968
106768
55
7418
—
Appendix
Table 3: Number of passes for three variants of the heuristic. The method’s own stopping criterion uses ε=10−3Δ . “—” indicates that it was not satisfied within 200000 passes.
Synthetic problems, n
Bike
freMTPL2
Method
2000
20000
100000
Sharing
freq
YETI
4.0
5.0
5.0
9.0
7.0
L-BFGS
197
168
99
44
22
Cov-LBFGS 1/4
22
23
16
21
12
BFGS
353
325
253
26
116
Nonlinear CG
705
707
359
108
102
Appendix
Table 4: Number of passes to relative accuracy 10−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Δ . All quantities are divided by Δ ; the dotted line indicates the threshold ε/2 . Values below 10−14 are shown at the lower boundary of the axis.
We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with n components. Very recently, Tsedenov & Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is Θ~(n+n6/7ε−2/7) by establishing nearly matching upper and lower bounds. In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is Ω(n+n5/7ε−2/7) under this stronger assumption. Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of O~(n+n5/7ε−2/7) by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.
We study the deterministic first-order oracle complexity of finding ε-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical ε−2 rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the ε−7/4 rate under Lipschitz Hessians and the ε−5/3 rate under Lipschitz third derivatives. The matching lower bounds, however, have remained open. We resolve this gap by proving a new dimension-free first-order lower bound for higher-order smooth nonconvex functions, valid for every finite smoothness order. In particular, our construction gives a matching Ω(ε−7/4) lower bound in the Hessian-Lipschitz case and a matching Ω(ε−5/3) lower bound in the third-order-smooth regime. The hard instance is based on a block-chain mechanism that enforces blockwise oracle revelation while preserving the smoothness structure needed for the scalar hard instance. The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors.
Dongruo Zhou
Department of Computer Science, Indiana University Bloomington, IN 47408, USA
In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose pth-order derivatives are Hölder continuous with degree ν and parameter H, and that are uniformly convex with degree q and parameter σ. When these orders match, namely, q=p+ν, we show that any deterministic algorithm with access to derivatives up to order p requires Ω((σH)3(p+ν)−22logεΔ0) oracle calls to reduce an initial optimality gap of Δ0 to ε. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.