Adaptive Variance Reduction without Knowing Oracle Smoothness

Adaptive Variance Reduction without Knowing Oracle Smoothness Wei Jiang1,2

arXiv:2610.13799v1 [math.OC] 9 Oct 2026

1

Yibo Wang2

Zechao Li1

School of Computer Science and Engineering, Nanjing University of Science and Technology 2 National Key Laboratory for Novel Software Technology, Nanjing University {jiangw, wangyb}@lamda.nju.edu.cn, zechao.li@njust.edu.cn

Abstract Variance reduction improves the convergence rate of stochastic non-convex optimization under the average smoothness condition. Existing adaptive variance reduction methods are especially designed for average smoothness and do not adapt to standard smoothness. In this paper, we study how one algorithm can adapt to these two settings and the noiseless setting without knowing the smoothness constants or the variance bound. Given the gradient budget T , we develop a two-phase method. The first phase compares two independent gradients and switches to normalized momentum when their difference exceeds a threshold. This phase provides both a candidate with standard smooth and noiseless guarantees and also ensures a bounded expected function gap for the second variance reduction phase. The resulting rates are O(T −1/3 ) under average smoothness, O(T −1/4 ) under standard smoothness, and O(T −1/2 ) without noise. When T is unknown, we propose a method with two paths that attain the corresponding rates with logarithmic factors in the stochastic settings. Here, we use a variance reduction path to deal with average smoothness and employ the AdaGrad-Norm for standard smoothness and noiseless setting. Neither method restarts from the initial point or requires a growing number of oracle calls in each round.

1

Introduction

In this paper, we investigate the stochastic optimization problem in the form min f (x),

x∈Rd

(1)

where the objective f is a smooth non-convex function and only stochastic gradients are available. Existing variance reduction techniques, such as STORM (Cutkosky and Orabona, 2019), use two evaluations with the same sample to develop the gradient estimator, achieving the O(T −1/3 ) convergence rate under average smoothness. To avoid requiring the problem constants for setting hyperparameters, adaptive variance reduction methods (Jiang et al., 2024) are proposed. These methods ensure the same O(T −1/3 ) rate with average smoothness, without knowing problem parameters such as the smoothness constant L and the variance upper bound σ. However, an interesting question remains: how can an algorithm retain the faster guarantee when average smoothness is available, while remaining reliable when the objective is only generally smooth? We also hope the same algorithm can accelerate in the noiseless setting. In this paper, we propose novel algorithms for solving this problem. For a known budget, our algorithm has two optimization phases. The first phase starts with normalized stochastic gradient steps. At each point, it compares two independent gradients and continues these steps when their difference is below a threshold. After the first failed comparison, it switches to normalized momentum for the rest of the phase. The second phase applies normalized variance 1

bT )∥, where T is the total gradient evaluation budget. Table 1: Bounds on E ∥∇f (x Oracle setting

Known T

Unknown T

Average smoothness Standard smoothness only Noiseless

O(T −1/3 ) O(T −1/4 ) O(T −1/2 )

O(log(eT )T −1/3 ) p O( log(eT )T −1/4 ) O(T −1/2 )

reduction from the current point. Each phase stores one candidate, and stochastic gradients are used to select the output in the final steps. For the unknown budget, we maintain a normalized variance reduction path and an AdaGrad-Norm path. The latter provides both the standard smooth and noiseless guarantees. Table 1 summarizes the results.

2

Assumptions and notation

The stochastic gradient at x is denoted by ∇f (x; ξ), and we also write g(x; ξ) = ∇f (x; ξ). The following assumptions are imposed throughout the paper. Assumption 1 (Standard smoothness). There exists L ≥ 0 such that, for every x, y ∈ Rd , ∥∇f (x) − ∇f (y)∥ ≤ L ∥x − y∥ . Assumption 2 (Unbiased gradients and bounded variance). For every x ∈ Rd , Eξ ∥∇f (x; ξ) − ∇f (x)∥2 ≤ σ 2 .

Eξ [∇f (x; ξ)] = ∇f (x),

Assumption 3 (Lower bounded objective). The value f∗ := inf x∈Rd f (x) is finite. For the initial point x1 , let ∆f = f (x1 ) − f∗ . The stronger rate uses the following additional property. However, our algorithms do not need to know whether it holds. Assumption 4 (Average smoothness). There exists L̄ ≥ 0 such that, for every x, y ∈ Rd , Eξ ∥∇f (x; ξ) − ∇f (y; ξ)∥2 ≤ L̄2 ∥x − y∥2 .

(2)

Average smoothness is also called mean-squared smoothness. The noiseless setting corresponds to σ = 0 in Assumption 2. Neither algorithm uses L, L̄, σ, ∆f , or function values. We do not assume bounded gradients, a bounded domain, a bounded range of objective values, or higher noise moments. We define the notation (

N (v) =

v/ ∥v∥ , 0,

v ̸= 0, v = 0.

For points with positive weights wt , a weighted reservoir stores one point by replacing its P current value with the t-th point with probability wt / ts=1 ws . For any sequence of points and P weights, the probability of retaining the t-th point after n steps is therefore wt / ns=1 ws . This implementation stores a single point instead of the entire path.

3

The proposed method for a known budget

Our first algorithm uses the budget T to choose the length of two optimization phases. Its first phase combines normalized stochastic gradient steps with normalized momentum. It provides 2

the standard smooth guarantee and accelerates automatically when the oracle is noiseless. The second phase applies normalized variance reduction from the current point. For T ≥ 6, set n = max{k ∈ N : 4k + 2⌈k 2/3 ⌉ ≤ T },

b = ⌈n2/3 ⌉.

(3)

Here n is the length of each optimization phase, and b is the number of validation samples used at each candidate. The parameters are ηD = n−1/2 ,

3.1

ηS = n−3/4 ,

βS = n−1/2 ,

ηV = βV = n−2/3 .

(4)

Updates and outputs

The first phase starts in the direct-gradient mode. At its current point, draw two independent stochastic gradients Gt , G′t . As long as Gt − G′t ≤ n−1/2 ,

(5)

take a normalized step using Gt and step size ηD . At the first failure of (5), switch permanently to normalized momentum with parameters ηS , βS . On that round, draw one independent gradient to initialize the momentum estimator. On all later rounds of the first phase, use one fresh gradient in the momentum update. The above test does not determine whether the oracle is noiseless. A noisy oracle may also pass it. The analysis accounts for these accepted noisy steps directly. In the noiseless setting, the test always passes, so the entire phase becomes normalized gradient descent. P Let ηt be the step size used at round t ≤ n, and write Wt = ts=1 ηs . The first phase maintains a weighted reservoir: after deciding the current mode and step size, replace its stored point by xt with probability ηt /Wt . Freeze the resulting candidate XG at the end of the phase. P For any optimization path, the reservoir selects index t with probability ηt /( ts=1 ηs ). The second phase starts at xn+1 and uses the normalized STORM update. It maintains a uniform reservoir over its n points, giving a candidate XV . During the first b rounds of this phase, accumulate one independent validation gradient at XG per round. After freezing XV , take one validation gradient at XV in each of b additional rounds. No optimization updates are needed in the final validation rounds.

3.2

Guarantees

Since ⌈k 2/3 ⌉ ≤ k, the choice in (3) gives n ≥ ⌊T /6⌋ ≥ T /12 for T ≥ 6. Also, b ≥ n2/3 , so the validation error is at most 2σn−1/3 . For the statement below, define the analysis constant √ 5 CG = ∆f + 2 + L + (4 + 2 2)σ. 2 Theorem 1. Under Assumptions 1–3, the output of Algorithm 1 satisfies 2σ bT )∥ ≤ CG n−1/4 + √ E ∥∇f (x b   1 + L + σ + ∆f =O . T 1/4

(6)

If Assumption 4 also holds, the same output satisfies   q L 2σ 2 2 b E ∥∇f (xT )∥ ≤ CG + + 2σ + 2 2(σ + L̄ ) n−1/3 + √ 2 b !

=O

1 + L + L̄ + σ + ∆f T 1/3 3

.

(7)

Algorithm 1 The proposed method Require: Initial point x1 , budget T ≥ 6. 1: Set n, b and the parameters by (3)–(4). 2: Set the mode to direct-gradient and W0 = 0. 3: for t = 1, . . . , n do 4: if the mode is direct-gradient then 5: Draw independent Gt , G′t at xt . 6: if ∥Gt − G′t ∥ ≤ n−1/2 then 7: Set vt = Gt and ηt = ηD . 8: else 9: Switch to momentum, draw a fresh gradient vt at xt , and set ηt = ηS . 10: end if 11: else 12: Draw a stochastic gradient gt at xt . 13: Set vt = (1 − βS )vt−1 + βS gt and ηt = ηS . 14: end if 15: Set Wt = Wt−1 + ηt and replace the first reservoir by xt with probability ηt /Wt . 16: xt+1 = xt − ηt N (vt ). 17: end for 18: Freeze the first reservoir as XG and set its validation sum to zero. 19: for t = n + 1, . . . , 2n do 20: If t = n + 1, initialize vt = g(xt ; ξt ) with one fresh query. 21: Otherwise, use a sample to set vt = g(xt ; ξt ) + (1 − βV )[vt−1 − g(xt−1 ; ξt )]. 22: If t ≤ n + b, add one independent gradient at XG to its validation sum. 23: Replace the second reservoir by xt with probability 1/(t − n). 24: xt+1 = xt − ηV N (vt ). 25: end for 26: Freeze the second reservoir as XV and average b fresh gradients to obtain g bV . 27: Divide the validation sum at XG by b to obtain g bG . 28: return x bT , which is the candidate in {XG , XV } with smaller estimated gradient norm.

If the oracle is noiseless, then L n−1/2 2   ∆f + L =O . T 1/2 



bT )∥ ≤ ∆f + E ∥∇f (x

(8)

bT )∥ ≤ ϵ are O(ϵ−4 ), O(ϵ−3 ) and O(ϵ−2 ), respectively. Equivalently, complexities for E ∥∇f (x

4

The anytime algorithm

In this section, we assume the budget T is unknown in advance.

4.1

The proposed schedule

When the budget T is unknown, we use two optimization paths: the variance reduction path and the AdaGrad-Norm path. Both paths start at x1 . For the variance reduction path, set βt = ηt = t−2/3 ,

v1 = g(xV1 ; ξ1 ),

xV1 = x1 .

(9)

At round t ≥ 2, draw a fresh sample ξt and form vt = g(xVt ; ξt ) + (1 − βt ) vt−1 − g(xVt−1 ; ξt ) .

4

(10)

At every round, update xVt+1 = xVt − ηt N (vt ).

(11)

The AdaGrad-Norm path uses one sample per round: xA 1 = x1 ,

gt = g(xA t ; ζt ),

b0 = 1,

bt =

q

b2t−1 + ∥gt ∥2 ,

A xA t+1 = xt −

gt . bt

(12)

The samples used by the two paths and by all validations are independent. P The algorithm maintains one reservoir candidate for each path. Define Wt = ts=1 ηs . At round t, replace the variance reduction reservoir by xVt with probability ηt /Wt , and replace the AdaGrad reservoir by xA t with probability 1/t. At a checkpoint n, the two reservoirs have the distributions Pr{Vn = xVt } =

ηt , Wn

Pr{An = xA t }=

1 , n

1 ≤ t ≤ n.

(13)

Checkpoints are n = {1, 2, 4, 8, . . .}. At the end of round n, copy and freeze Vn and An . During rounds {n + 1, . . . , 2n}, take one fresh gradient at each of these two frozen points in every round. Their running averages are gbnV =

n 1X V g(Vn ; ξn,j ), n j=1

gbnA =

n 1X A g(An ; ξn,j ). n j=1

(14)

At the end of round 2n, report the point with the smaller estimated gradient norm:

Zn =

  V ,   n

gbnV

≤ gbnA ,

  A ,

gbnV

gbnA

(15)

n

>

.

The optimization updates and both reservoirs continue throughout these validation rounds. At round 2n, the reservoirs for the longer prefix 2n are copied for the next validation block and the previous report remains available until the next report is completed. Thus, at any deterministic round τ ≥ 2, the reported point is Zn , where n = 2⌊log2 τ ⌋−1 ,

4.2

2n ≤ τ < 4n.

(16)

Guarantees

Define the following constants CA = 4∆f + 2 ∥∇f (x1 )∥2 + 8L2 + 2σ 2 , √ Mn = 4 + 4σ n + 2CA + 16L2 , K = 6L̄2 + 2σ 2 .

(17)

The initial gradient in CA can be eliminated using ∥∇f (x1 )∥2 ≤ 2L∆f . For L > 0, the descent inequality at x1 − L−1 ∇f (x1 ) gives this bound. When L = 0, a lower-bounded function with constant gradient has zero gradient. Theorem 2. Suppose f is lower bounded and L-smooth, and the stochastic gradient oracle is unbiased with variance at most σ 2 . At every deterministic round τ ≥ 2, let n be defined by (16). The reported point of the Algorithm satisfies s

E ∥∇f (Zn )∥ ≤

Mn (CA + 4L log Mn ) 2σ +√ . n n 5

(18)

Algorithm 2 The anytime algorithm Require: Initial point x1 . A 1: Initialize xV 1 = x1 = x1 , b0 = 1, and W0 = 0. 2: Initialize the reservoirs RV = RA = x1 , the report Z = x1 , and the checkpoint n = 1. 3: for t = 1, 2, . . . do 4: Set ηt = βt = t−2/3 and Wt = Wt−1 + ηt . 5: Draw a fresh sample ξt . 6: if t = 1 then 7: Set v1 = g(xV1 ; ξ1 ). 8: else   9: Compute vt = g(xVt ; ξt ) + (1 − βt ) vt−1 − g(xVt−1 ; ξt ) . 10: end if q 2 b2t−1 + ∥gt ∥ . 11: Draw a fresh independent gradient gt = g(xA ; ζ ) and set b = t t t 12: Replace RV by xVt with probability ηt /Wt , and RA by xA t with probability 1/t. A 13: Update xVt+1 = xVt − ηt N (vt ) and xA = x − g /b . t t t t+1 14: if t > n then 15: Draw independent validation samples ξtV , ξtA and update gbnV ← gbnV +

g(Vn ; ξtV ) , n

gbnA ← gbnA +

g(An ; ξtA ) . n

16: end if 17: if t = 2n then 18: Copy Vn to Z if gbnV ≤ gbnA ; otherwise copy An to Z. 19: Set n ← 2n. 20: end if 21: if t = n then 22: Copy and freeze Vn ← RV and An ← RA , replacing the previous frozen pair. 23: Initialize gbnV = gbnA = 0. 24: end if 25: if an external stopping request is received then 26: return Z. 27: end if 28: end for

If the oracle additionally satisfies mean-square smoothness, then   s  ∆ + 2L + 2√K(1 + log n) Mn (CA + 4L log Mn )  2σ f E ∥∇f (Zn )∥ ≤ min , +√ .   n n n1/3

(19)

In particular, for fixed problem parameters, the three rates are respectively 1 + log τ τ 1/3 ! √ 1 + log τ O τ 1/4 

O

O(τ −1/2 )

5



under mean-square smoothness, under standard smoothness,

(20)

when σ = 0 with standard smoothness.

Conclusion

In this paper, we investigate stochastic non-convex optimization without knowing whether the oracle satisfies average smoothness or knowing the smoothness constants and variance bound. For a known total gradient budget T , we proposed a method that achieves expected gradient norm bounds of O(T −1/3 ) under average smoothness, O(T −1/4 ) under standard smoothness, and 6

O(T −1/2 ) in the noiseless setting. We also develop an anytime method with two paths, which attains the corresponding rates up to logarithmic factors in the stochastic settings and retains the O(T −1/2 ) noiseless rate. Both methods use a constant number of gradient evaluations per round, include the cost of output selection, and avoid restarting from the initial point. Further work could investigate whether the logarithmic factors in the anytime bounds can be removed and whether the same guarantees can be achieved along a single path without knowing T .

References A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems 32, pages 15210–15219, 2019. W. Jiang, S. Yang, Y. Wang, and L. Zhang. Adaptive variance reduction for stochastic optimization under weaker assumptions. In Advances in Neural Information Processing Systems 37, pages 22047–22080, 2024. B. Wang, H. Zhang, Z. Ma, and W. Chen. Convergence of AdaGrad for non-convex objectives: Simple proofs and relaxed assumptions. In Proceedings of the 36th Conference on Learning Theory, pages 161–190, 2023.

7

A

Proof of Theorem 1

A.1

Useful Lemmas

Lemma 1. For any point x, vector v, and η > 0, the update x+ = x − ηN (v) satisfies f (x+ ) ≤ f (x) − η ∥∇f (x)∥ + 2η ∥v − ∇f (x)∥ +

L 2 η . 2

(21)

Proof. If v ̸= 0, Cauchy–Schwarz and the triangle inequality give v v + ∇f (x) − v, ⟨∇f (x), N (v)⟩ = v, ∥v∥ ∥v∥ ≥ ∥v∥ − ∥∇f (x) − v∥

≥ ∥∇f (x)∥ − 2 ∥v − ∇f (x)∥ . For v = 0, the inequality still holds. Thus, 2 L + x −x 2 L 2 = f (x) − η ⟨∇f (x), N (v)⟩ + η ∥N (v)∥2 2 L ≤ f (x) − η ∥∇f (x)∥ + 2η ∥v − ∇f (x)∥ + η 2 , 2

D

E

f (x+ ) ≤ f (x) + ∇f (x), x+ − x +

where the last step uses ∥N (v)∥ ≤ 1. Lemma 2. Let X1 , . . . , Xm be random candidate points. At each point, average b independent stochastic gradients to obtain gbi . If J ∈ arg mini ∥gbi ∥, then mσ E ∥∇f (XJ )∥ ≤ E min ∥∇f (Xi )∥ + √ 1≤i≤m b mσ ≤ min E ∥∇f (Xi )∥ + √ . 1≤i≤m b

(22)

Proof. For fixed candidates, the validation average is gbi =

b 1X g(Xi ; ξi,j ). b j=1

Expanding the square and then averaging over the candidates yields b X 1 E ∥gbi − ∇f (Xi )∥ = 2 E [g(Xi ; ξi,j ) − ∇f (Xi )] b j=1

2

2

≤

σ2 . b

Consequently, Cauchy–Schwarz gives E ∥gbi − ∇f (Xi )∥ ≤

q

σ E ∥gbi − ∇f (Xi )∥2 ≤ √ . b

Choose i ∈ arg min1≤k≤m ∥∇f (Xk )∥. If J = i, then ∥∇f (XJ )∥ = mink ∥∇f (Xk )∥. If J = ̸ i, ∥∇f (XJ )∥ ≤ ∥gbJ ∥ + ∥gbJ − ∇f (XJ )∥ ≤ ∥gbi ∥ + ∥gbJ − ∇f (XJ )∥ ≤ ∥∇f (Xi )∥ + ∥gbi − ∇f (Xi )∥ + ∥gbJ − ∇f (XJ )∥ ≤ min ∥∇f (Xk )∥ + k

m X k=1

8

∥gbk − ∇f (Xk )∥ .

Taking expectations gives E ∥∇f (XJ )∥ ≤ E min ∥∇f (Xk )∥ + k

m X

E ∥gbk − ∇f (Xk )∥

k=1

mσ ≤ E min ∥∇f (Xk )∥ + √ . k b Finally, for every fixed index j, min ∥∇f (Xk )∥ ≤ ∥∇f (Xj )∥

E min ∥∇f (Xk )∥ ≤ E ∥∇f (Xj )∥ .

=⇒

k

k

Taking the minimum over j proves the second inequality in (22).

A.2

Direct-gradient step

Lemma 3. Let G, G′ be independent random vectors with mean µ and E ∥G − µ∥2 ≤ σ 2 . For every a ≥ 0, let p = Pr{∥G − G′ ∥ > a}. Then √ √   E ∥G − µ∥ 1{∥G−G′ ∥≤a} ≤ a + 2 σ p. (23) Proof. By independence, EG′ [G − G′ ] = G − µ when G is fixed. Thus Jensen’s inequality gives E ∥G − µ∥ = EG EG′ [G − G′ ] ≤ EG EG′ G − G′ = E G − G′ . Moreover, E G − G′

2

= E (G − µ) − (G′ − µ)

2

= E ∥G − µ∥2 + E G′ − µ

2

− 2E G − µ, G′ − µ

≤ 2σ 2 , where E ⟨G − µ, G′ − µ⟩ = ⟨E[G − µ], E[G′ − µ]⟩ = 0. Splitting the expectation at a, we obtain E G − G′ = E G − G′ 1{∥G−G′ ∥≤a} + E G − G′ 1{∥G−G′ ∥>a} 



q

E ∥G − G′ ∥2 √ √ ≤ a + 2 σ p, ≤a+





q

E1{∥G−G′ ∥>a}

where the second line uses Cauchy–Schwarz. Therefore, E ∥G − µ∥ 1{∥G−G′ ∥≤a} ≤ E ∥G − µ∥ ≤ E G − G′ ≤ a + 



√

√ 2 σ p.

Let St be 1 if every test before round t has passed, and 0 otherwise. Thus St = 1 when round t begins in the direct-gradient mode. At the current point, write pt = Pr ′ { Gt − G′t > n−1/2 }. Gt ,Gt

Fixing the earlier samples and averaging that pair first gives h

E[St pt ] = E St EGt ,G′t 1{∥Gt −G′ ∥>n−1/2 }

i

t

h

i

= E St 1{∥Gt −G′ ∥>n−1/2 } = Pr{first failure at t}. t

9

The possible first-failure events are disjoint, n X

E[St pt ] =

t=1

n X

Pr{first failure at t} ≤ 1.

(24)

t=1

Applying Cauchy–Schwarz first to each expectation and then to the sum, we have n X

n X p p √ E[ St St pt ] E[St pt ] = t=1

t=1

≤

n p X

q

ESt E[St pt ]

t=1

≤

n X

!1/2

n X

ESt

t=1

!1/2

≤

E[St pt ]

√

n.

(25)

t=1

For a direct step, St = 1, vt = Gt , and ηt = ηD . Lemma 3 with a = n−1/2 gives E

X

ηD ∥vt − ∇f (xt )∥ = ηD

n X t=1

1≤t≤n: direct step

≤ ηD

h

i

E St 1{∥Gt −G′ ∥≤n−1/2 } ∥Gt − ∇f (xt )∥ t

n X 

E St (n−1/2 +

√

√  2σ pt )

t=1

= ηD n−1/2

n X

ESt +

t=1 −1/2 −1/2

≤n

n

n+

√

√

n X

√ E[St pt ]

t=1 −1/2 √

√

2σηD

n=1+

2σn

2σ,

(26)

where the last line uses ηD = n−1/2 and (25).

A.3

Momentum step

Lemma 4. Consider m normalized momentum updates with parameters 0 < β ≤ 1 and η > 0: v1 = g(x1 ; ξ1 ),

vt = (1 − β)vt−1 + βg(xt ; ξt )

(t ≥ 2),

xt+1 = xt − ηN (vt ).

Then, we can ensure E ∥vt − ∇f (xt )∥ ≤ σ(1 − β)t−1 + σ β + p

Lη , β

1 ≤ t ≤ m.

(27)

Proof. Write et = vt − ∇f (xt ) and εt = g(xt ; ξt ) − ∇f (xt ). At t = 1, E ∥e1 ∥ ≤ σ. For t ≥ 2, et = (1 − β)vt−1 + βg(xt ; ξt ) − ∇f (xt ) = (1 − β)[vt−1 − ∇f (xt−1 )] + β[g(xt ; ξt ) − ∇f (xt )] + (1 − β)[∇f (xt−1 ) − ∇f (xt )] = (1 − β)et−1 + βεt + (1 − β)[∇f (xt−1 ) − ∇f (xt )]. Since e1 = ε1 , repeated substitution gives et = (1 − β)t−1 ε1 + β

t X

(1 − β)t−k εk +

k=2

t X

(1 − β)t−k+1 [∇f (xk−1 ) − ∇f (xk )].

k=2

For i < j, averaging the sample ξj first yields D

E

E ⟨εi , εj ⟩ = E εi , Eξj [g(xj ; ξj ) − ∇f (xj )] = 0. 10

Thus the squared norm of the noise sum satisfies E (1 − β)t−1 ε1 + β

t X

2

(1 − β)t−k εk

k=2 t X

= (1 − β)2(t−1) E ∥ε1 ∥2 + β 2

(1 − β)2(t−k) E ∥εk ∥2

k=2



≤ σ 2 (1 − β)2(t−1) + β 2

t−2 X



(1 − β)2j 

j=0

"

#

β2 ≤ σ (1 − β) + 1 − (1 − β)2   β 2 2(t−1) = σ (1 − β) + ≤ σ 2 [(1 − β)2(t−1) + β]. 2−β 2

2(t−1)

For the remaining gradient-difference sum, smoothness and ∥xk − xk−1 ∥ ≤ η give t X

(1 − β)t−k+1 [∇f (xk−1 ) − ∇f (xk )] ≤

t X

(1 − β)t−k+1 L ∥xk−1 − xk ∥

k=2

k=2

≤ Lη

t−1 X

(1 − β)j ≤ Lη

∞ X

(1 − β)j =

j=0

j=1

Lη . β

By the triangle inequality and Cauchy–Schwarz, v u 2 u t X u Lη E ∥et ∥ ≤ tE (1 − β)t−1 ε1 + β (1 − β)t−k εk +

β

k=2

Lη β p Lη ≤ σ(1 − β)t−1 + σ β + . β q

≤ σ (1 − β)2(t−1) + β +

Suppose the first failure occurs at round s. Momentum starts at xs and runs for n − s + 1 rounds. Applying Lemma 4 and averaging these samples gives E

n X

ηS ∥vt − ∇f (xt )∥ ≤ ηS σ

t=s

n−s X

(1 − βS )j + (n − s + 1)ηS σ βS + p

j=0

(n − s + 1)LηS2 βS

p ηS σ nLηS2 + nηS σ βS + βS βS −3/4 nLn−3/2 σn = −1/2 + nn−3/4 σn−1/4 + n n−1/2 −1/4 = σn + σ + L.

≤

This bound holds for every s and every preceding sample sequence. If the test never fails, there are no momentum updates. Thus, averaging over the first failure and its preceding samples, E

X

ηS ∥vt − ∇f (xt )∥ ≤ σn−1/4 + σ + L ≤ 2σ + L.

1≤t≤n: momentum step

The direct and momentum rounds partition the first phase. Therefore, E

n X

ηt ∥vt − ∇f (xt )∥ ≤ (1 +

√

2σ) + (2σ + L) = 1 + (2 +

t=1

11

√

2)σ + L.

(28)

Since ηS ≤ ηt ≤ ηD , we have n X

Wn =

ηt ≥ nηS = n1/4 ,

t=1

n X

2 ηt2 ≤ nηD = 1.

(29)

t=1

Rearranging Lemma 1 and summing over t = 1, . . . , n gives E[f (xn+1 ) − f∗ ] + E

n X

ηt ∥∇f (xt )∥

t=1 n X

≤ f (x1 ) − f∗ + 2E

ηt ∥vt − ∇f (xt )∥ +

t=1

n L X E η2 2 t=1 t

√

L 2)σ + L] + 2 √ 5 = ∆f + 2 + L + (4 + 2 2)σ = CG . 2

≤ ∆f + 2[1 + (2 +

(30)

Both terms on the left are nonnegative, and hence E[f (xn+1 ) − f∗ ] ≤ CG .

(31)

For a fixed first-phase optimization path, the probability that the reservoir selects index i is n ηi Y ηt 1− Wi t=i+1 Wt





=

n n Wt − η t Wt−1 ηi Y ηi Y η i Wi ηi = = = . Wi t=i+1 Wt Wi t=i+1 Wt Wi W n Wn

This identity also applies to the random step sizes, after averaging over the path: E ∥∇f (XG )∥ = E

" n X ηt

Wn t=1

#

∥∇f (xt )∥ ≤ n−1/4 E

n X

ηt ∥∇f (xt )∥ ≤ CG n−1/4 ,

(32)

t=1

where the two inequalities use (29) and (30), respectively. When σ = 0, each sampled gradient equals the true gradient. Every test passes, and √ vt = ∇f (xt ), ηt = ηD = n−1/2 , Wn = nηD = n. The normalized descent inequality becomes ηD ∥∇f (xt )∥ ≤ f (xt ) − f (xt+1 ) +

L 2 η . 2 D

Summing gives ηD

n X

∥∇f (xt )∥ ≤ f (x1 ) − f (xn+1 ) +

t=1

L 2 L nηD ≤ ∆f + . 2 2

All reservoir weights are equal, so E ∥∇f (XG )∥ =

n ∆f + L/2 1X ∥∇f (xt )∥ ≤ = (∆f + L/2)n−1/2 . n t=1 nηD

12

(33)

A.4

The variance reduction step

Lemma 5. Consider a phase with t = 1, . . . , n and updates v1 = g(x1 ; ξ1 ), vt = g(xt ; ξt ) + (1 − β)[vt−1 − g(xt−1 ; ξt )]

(t ≥ 2),

xt+1 = xt − ηN (vt ). Under Assumption 4, with β = η = n−2/3 , E ∥vt − ∇f (xt )∥ ≤ σ(1 − β)t−1 +

q

2(σ 2 + L̄2 ) n−1/3 .

(34)

Proof. Let et = vt − ∇f (xt ). At t = 1, the initialization gives E ∥e1 ∥2 ≤ σ 2 , so (34) holds. For t ≥ 2, the estimator update gives et = g(xt ; ξt ) + (1 − β)[vt−1 − g(xt−1 ; ξt )] − ∇f (xt ) = (1 − β)et−1 + β[g(xt ; ξt ) − ∇f (xt )] + (1 − β)[g(xt ; ξt ) − g(xt−1 ; ξt ) − ∇f (xt ) + ∇f (xt−1 )]. By unbiasedness, we have Eξt [g(xt ; ξt ) − ∇f (xt )] = 0,

Eξt [g(xt ; ξt ) − g(xt−1 ; ξt )] = ∇f (xt ) − ∇f (xt−1 ).

The gradient difference satisfies Eξt ∥g(xt ; ξt ) − g(xt−1 ; ξt ) − ∇f (xt ) + ∇f (xt−1 )∥2 = Eξt ∥g(xt ; ξt ) − g(xt−1 ; ξt )∥2 − ∥∇f (xt ) − ∇f (xt−1 )∥2 ≤ Eξt ∥g(xt ; ξt ) − g(xt−1 ; ξt )∥2 ≤ L̄2 ∥xt − xt−1 ∥2 ≤ L̄2 η 2 . Consequently, we can ensure E ∥et ∥2 = (1 − β)2 E ∥et−1 ∥2 + E ∥β[g(xt ; ξt ) − ∇f (xt )] + (1 − β)[g(xt ; ξt ) − g(xt−1 ; ξt ) − ∇f (xt ) + ∇f (xt−1 )]∥2 ≤ (1 − β)2 E ∥et−1 ∥2 + 2β 2 E ∥g(xt ; ξt ) − ∇f (xt )∥2 + 2(1 − β)2 E ∥g(xt ; ξt ) − g(xt−1 ; ξt ) − ∇f (xt ) + ∇f (xt−1 )∥2 ≤ (1 − β)2 E ∥et−1 ∥2 + 2β 2 σ 2 + 2(1 − β)2 L̄2 η 2 ≤ (1 − β)2 E ∥et−1 ∥2 + 2β 2 σ 2 + 2L̄2 η 2 . The initialization gives E ∥e1 ∥2 = E ∥g(x1 ; ξ1 ) − ∇f (x1 )∥2 ≤ σ 2 . Repeated substitution in the last recursion yields E ∥et ∥2 ≤ (1 − β)2(t−1) E ∥e1 ∥2 + (2β 2 σ 2 + 2L̄2 η 2 )

t−2 X

(1 − β)2j

j=0

≤ σ 2 (1 − β)2(t−1) +

2β 2 σ 2 + 2L̄2 η 2

1 − (1 − β)2 2β 2 σ 2 + 2L̄2 η 2 ≤ σ 2 (1 − β)2(t−1) + β = σ 2 (1 − β)2(t−1) + 2(σ 2 + L̄2 )n−2/3 , 13

where 1 − (1 − β)2 = β(2 − β) ≥ β and β = η = n−2/3 . Taking square roots, E ∥et ∥ ≤ ≤

q

E ∥et ∥2

q

σ 2 (1 − β)2(t−1) + 2(σ 2 + L̄2 )n−2/3

≤ σ(1 − β)t−1 +

q

2(σ 2 + L̄2 ) n−1/3 ,

which proves (34). The second phase of Algorithm 1 starts at xn+1 . By (31), E[f (xn+1 ) − f∗ ] ≤ CG . Applying Lemma 5 gives 2n X

ηV E ∥vt − ∇f (xt )∥

t=n+1

≤ ηV

n  X

σ(1 − βV )

j−1

+

q

2(σ 2 + L̄2 ) n−1/3



j=1

ηV σ + nηV 2(σ 2 + L̄2 ) n−1/3 βV q n−2/3 σ = −2/3 + nn−2/3 2(σ 2 + L̄2 ) n−1/3 n q q

≤

2(σ 2 + L̄2 ).

=σ+

Summing Lemma 1 over this phase, we obtain ηV

2n X

2n X

E ∥∇f (xt )∥ ≤ E[f (xn+1 ) − f (x2n+1 )] + 2

ηV E ∥vt − ∇f (xt )∥ +

t=n+1

t=n+1

q

≤ CG + 2σ + 2 2(σ 2 + L̄2 ) +

L 2 nη 2 V

L −1/3 n . 2

The uniform reservoir assigns probability 1/n to each point in this phase. Since nηV = n1/3 , E ∥∇f (XV )∥ =

2n 1 X E ∥∇f (xt )∥ n t=n+1

q

≤

CG + 2σ + 2 2(σ 2 + L̄2 ) + (L/2)n−1/3 n1/3 



q

= CG + 2σ + 2 2(σ 2 + L̄2 ) n−1/3 + 

≤ CG +

A.5

L −2/3 n 2

L + 2σ + 2 2(σ 2 + L̄2 ) n−1/3 . 2 q



Validation phase

Apply Lemma 2 with m = 2 and b samples at each of XG , XV . Then 2σ bT )∥ ≤ min{E ∥∇f (XG )∥ , E ∥∇f (XV )∥} + √ . E ∥∇f (x b Combining this bound with (32) gives 2σ bT )∥ ≤ CG n−1/4 + √ , E ∥∇f (x b 14

(35)

which proves (6). Under average smoothness, (35) instead gives L 2σ bT )∥ ≤ CG + + 2σ + 2 2(σ 2 + L̄2 ) n−1/3 + √ , E ∥∇f (x 2 b 

q



which proves (1). Finally, when σ = 0, exact validation and (33) imply (1): bT )∥ ≤ E ∥∇f (XG )∥ ≤ (∆f + L/2)n−1/2 . E ∥∇f (x

Next, we count the oracle calls and validation calls below Phase First phase Variance reduction phase Final validation Total

Optimization calls ≤ 2n + 1 2n − 1 0 ≤ 4n

Validation calls 0 b b 2b

Maximum per round 3 3 1 3

Thus the total oracle cost satisfies oracle calls ≤ (2n + 1) + (2n − 1) + 2b = 4n + 2b ≤ T.

rounds = 2n + b,

B

Proof of Theorem 2

B.1

Variance reduction bound

Lemma 6. Under mean-square smoothness, the update (9)–(11) satisfies E vt − ∇f (xVt )

2

≤ Kt−2/3 .

(36)

Its weighted reservoir candidate satisfies √ ∆f + 2L + 2 K(1 + log n) E ∥∇f (Vn )∥ ≤ , Wn

Wn ≥ n1/3 .

(37)

Proof. We omit the superscript V and write et = vt − ∇f (xt ). For t ≥ 2, the estimator gives et = (1 − βt )et−1 

+ (1 − βt ) g(xt ; ξt ) − g(xt−1 ; ξt ) − ∇f (xt ) + ∇f (xt−1 ) 





+ βt g(xt ; ξt ) − ∇f (xt ) . By unbiasedness, we have Eξt [g(xt ; ξt ) − g(xt−1 ; ξt )] = ∇f (xt ) − ∇f (xt−1 ). Expanding the square gives Eξt ∥g(xt ; ξt ) − g(xt−1 ; ξt ) − ∇f (xt ) + ∇f (xt−1 )∥2 = Eξt ∥g(xt ; ξt ) − g(xt−1 ; ξt )∥2 − 2 ⟨Eξt [g(xt ; ξt ) − g(xt−1 ; ξt )], ∇f (xt ) − ∇f (xt−1 )⟩ + ∥∇f (xt ) − ∇f (xt−1 )∥2 = Eξt ∥g(xt ; ξt ) − g(xt−1 ; ξt )∥2 − ∥∇f (xt ) − ∇f (xt−1 )∥2 2 ≤ L̄2 ∥xt − xt−1 ∥2 ≤ L̄2 ηt−1 .

Here we used mean-square smoothness and ∥xt − xt−1 ∥ ≤ ηt−1 . 15

(38)

Both bracketed terms in (38) have zero mean. Their cross terms with et−1 therefore vanish. Applying ∥u + v∥2 ≤ 2 ∥u∥2 + 2 ∥v∥2 to their sum gives 2 Eξt ∥et ∥2 ≤ (1 − βt )2 ∥et−1 ∥2 + 2(1 − βt )2 L̄2 ηt−1 + 2βt2 σ 2 2 ≤ (1 − βt )2 ∥et−1 ∥2 + 2L̄2 ηt−1 + 2βt2 σ 2 .

Averaging over the earlier samples proves 2 E ∥vt − ∇f (xt )∥2 ≤ (1 − βt )2 E ∥vt−1 − ∇f (xt−1 )∥2 + 2L̄2 ηt−1 + 2βt2 σ 2 .

(39)

We prove (36) by induction with K = 6L̄2 + 2σ 2 . At t = 1, E ∥e1 ∥2 = E ∥g(x1 ; ξ1 ) − ∇f (x1 )∥2 ≤ σ 2 ≤ K = Kβ1 . For t ≥ 2, βt = t−2/3 ≥ 1/t and u ≤ u2/3 for 0 ≤ u ≤ 1, so 1 1 ≤ 1− t t 

1 − βt ≤ 1 −

2/3

βt . βt−1

=

(40)

Multiplying this inequality by (1 − βt )βt−1 ≥ 0 yields (1 − βt )2 βt−1 ≤ (1 − βt )βt . Also, 2 ηt−1 (t − 1)−4/3 = = βt2 t−4/3



t t−1

4/3

≤ 24/3 < 3.

If E ∥et−1 ∥2 ≤ Kβt−1 , the recursion gives E ∥et ∥2 ≤ K(1 − βt )2 βt−1 + 6L̄2 βt2 + 2σ 2 βt2 ≤ K(1 − βt )βt + (6L̄2 + 2σ 2 )βt2 = Kβt − Kβt2 + Kβt2 = Kβt . Thus, by Cauchy–Schwarz, E ∥et ∥ ≤

q

E ∥et ∥2 ≤

√

K t−1/3 .

By Lemma 1, ηt ∥∇f (xt )∥ ≤ f (xt ) − f (xt+1 ) + 2ηt ∥et ∥ +

L 2 η . 2 t

Taking expectations, summing, and using f (xn+1 ) ≥ f∗ gives n X

ηt E ∥∇f (xt )∥ ≤ f (x1 ) − Ef (xn+1 ) + 2

t=1

n X

ηt E ∥et ∥ +

t=1

n LX η2 2 t=1 t

n n √ X LX −2/3 −1/3 ≤ ∆f + 2 K t t + t−4/3 2 t=1 t=1 n n √ X 1 LX = ∆f + 2 K + t−4/3 . t 2 t=1 t=1

Since both summands decrease with t, n X 1 t=1 n X t=1

t

≤1+

t−4/3 ≤ 1 +

Z n 1

Z n

ds = 1 + log n, s s−4/3 ds = 1 + 3(1 − n−1/3 ) ≤ 4.

1

16

Consequently,

n X

√ ηt E ∥∇f (xt )∥ ≤ ∆f + 2 K(1 + log n) + 2L.

t=1

The weights ηt are deterministic, and the index-selection law in (13) gives E ∥∇f (Vn )∥ = E

" n X ηt t=1

Wn

#

∥∇f (xt )∥ =

n 1 X ηt E ∥∇f (xt )∥ . Wn t=1

This proves the first bound in (37). For the second bound, Wn =

n X

t−2/3 ≥

t=1

B.2

n X

n−2/3 = n1/3 .

t=1

AdaGrad-Norm bound

The proof below follows the potential approach of Wang et al. (2023). We give the details for bounded variance and a uniformly sampled output. Lemma 7. Under standard smoothness and bounded variance alone, the update (12) satisfies Ebn ≤ Mn , E

n ∇f (xA X t ) t=1

2

bt−1

≤ CA + 4L log Mn .

(41)

Consequently, its uniform reservoir candidate satisfies s

E ∥∇f (An )∥ ≤

Mn (CA + 4L log Mn ) . n

(42)

Proof. We omit the superscript A in this proof. Recall that b0 = 1,

b2t = b2t−1 + ∥gt ∥2 ,

bt ≥ bt−1 ≥ 1,

bt ≥ ∥gt ∥ ,

xt+1 = xt −

gt . bt

In particular, ∥xt+1 − xt ∥ =

∥gt ∥ ≤ 1. bt

Thus ∥xt − x1 ∥ ≤ t − 1 and ∥∇f (xt )∥ ≤ ∥∇f (x1 )∥ + L(t − 1),

2

E ∥gt ∥2 ≤ ∥∇f (x1 )∥ + L(t − 1)

+ σ2.

For the proof only, set x0 = x1 and g0 = 0 to make x1 = x0 − g0 /b0 valid. We first bound the effect of using the current gradient in bt . Unbiasedness gives E ∥gt ∥2 = ∥∇f (xt )∥2 + 2 ⟨∇f (xt ), Egt − ∇f (xt )⟩ + E ∥gt − ∇f (xt )∥2 ≤ ∥∇f (xt )∥2 + σ 2 . The difference between the two normalizations is 1 bt−1

−

b2t − b2t−1 1 bt − bt−1 ∥gt ∥2 = = = ≥ 0. bt bt−1 bt bt−1 bt (bt + bt−1 ) bt−1 bt (bt + bt−1 ) 17

Using this identity, the inner-product inequality, and ∥gt ∥ ≤ bt , we obtain 1 E ⟨∇f (xt ), gt ⟩ − bt−1 bt    1 1 ≤ E |⟨∇f (xt ), gt ⟩| − bt−1 bt    1 1 ≤ ∥∇f (xt )∥ E ∥gt ∥ − bt−1 bt 



1



∥∇f (xt )∥ ∥gt ∥3 = E bt−1 bt (bt + bt−1 ) "

#

∥gt ∥2 ∥∇f (xt )∥ E . ≤ bt−1 bt + bt−1 "

#

(43)

Cauchy–Schwarz bounds the last expectation by ∥gt ∥2 E bt + bt−1

!2

∥gt ∥ = E ∥gt ∥ bt + bt−1  

≤ E ∥gt ∥2 E

2

∥gt ∥2 (bt + bt−1 )2

≤ ∥∇f (xt )∥2 + σ 2 E

∥gt ∥2 . (bt + bt−1 )2

Apply uv ≤ (u2 + v 2 )/2 to the resulting product: ∥∇f (xt )∥ ∥gt ∥2 ∥∇f (xt )∥ E ≤ p bt−1 bt + bt−1 bt−1 ≤

∥∇f (xt )∥2 + σ 2 ∥gt ∥2 E bt−1 (bt + bt−1 )2

!1/2

∥∇f (xt )∥2 ∥∇f (xt )∥2 + σ 2 ∥gt ∥2 + E . 2bt−1 2 bt−1 (bt + bt−1 )2

Since bt + bt−1 ≥ bt , ∥gt ∥2 ∥gt ∥2 1 1 − . ≤ = 2 bt−1 (bt + bt−1 ) bt−1 bt (bt + bt−1 ) bt−1 bt Substituting these bounds into (43) gives 1 E ⟨∇f (xt ), gt ⟩ − bt−1 bt 



1



∥∇f (xt )∥2 ∥∇f (xt )∥2 + σ 2 1 1 ≤ + E − . 2bt−1 2 bt−1 bt 



(44)

Next, we rewrite the term containing ∥∇f (xt )∥2 so that it can be summed over t: ∥∇f (xt )∥2 2 =



1

1 − bt−1 bt



∥∇f (xt )∥2 ∥∇f (xt )∥2 − 2bt−1 2bt

1 = 2

∥∇f (xt−1 )∥2 ∥∇f (xt )∥2 − bt−1 bt

18

!

+

∥∇f (xt )∥2 − ∥∇f (xt−1 )∥2 . 2bt−1

(45)

For the last numerator, smoothness gives ∥∇f (xt )∥2 − ∥∇f (xt−1 )∥2 = 2 ⟨∇f (xt ), ∇f (xt ) − ∇f (xt−1 )⟩ − ∥∇f (xt ) − ∇f (xt−1 )∥2 ≤ 2 ∥∇f (xt )∥ ∥∇f (xt ) − ∇f (xt−1 )∥ ≤ 2L ∥∇f (xt )∥ ∥xt − xt−1 ∥ 2L ∥∇f (xt )∥ ∥gt−1 ∥ . = bt−1 Consequently, uv ≤ u2 /4 + v 2 implies ∥∇f (xt )∥ L ∥gt−1 ∥ ∥∇f (xt )∥2 − ∥∇f (xt−1 )∥2 ≤ p 3/2 2bt−1 bt−1 b ≤

∥∇f (xt )∥ 4bt−1

2

t−1 L2 ∥gt−1 ∥2 + . b3t−1

(46)

The smoothness inequality for the AdaGrad update is f (xt+1 ) ≤ f (xt ) −

⟨∇f (xt ), gt ⟩ L ∥gt ∥2 + . bt 2 b2t

Separate 1/bt from 1/bt−1 and use Egt = ∇f (xt ): ⟨∇f (xt ), Egt ⟩ 1 1 + E ⟨∇f (xt ), gt ⟩ − bt−1 bt−1 bt 

Ef (xt+1 ) ≤ f (xt ) −

∥∇f (xt )∥2 1 1 + E ⟨∇f (xt ), gt ⟩ − bt−1 bt−1 bt 

= f (xt ) −







+



+

L ∥gt ∥2 E 2 2 bt

L ∥gt ∥2 E 2 . 2 bt

Insert (44), (45), and (46). The coefficient of ∥∇f (xt )∥2 /bt−1 is −1 + 1/2 + 1/4 = −1/4. Now also average over all earlier samples: 1 ∥∇f (xt )∥2 Ef (xt+1 ) ≤ Ef (xt ) − E 4 bt−1 ∥∇f (xt−1 )∥2 ∥∇f (xt )∥2 1 + E − 2 bt−1 bt "

#

σ2 1 1 ∥gt−1 ∥2 L ∥gt ∥2 + L2 E 3 + E 2 . + E − 2 bt−1 bt 2 bt−1 bt 



(47)

We next bound the last three sums in (47). Since u−3/2 and u−1 are decreasing for u > 0, b2t − b2t−1 ∥gt ∥2 = ≤ b3t (b2t )3/2

Z b2

b2t − b2t−1 ∥gt ∥2 = ≤ b2t b2t

Z b2

t

−3/2

b2t−1

u

1

1 du = 2 − , bt−1 bt 



du = 2 log bt − 2 log bt−1 . b2t−1 u t

Using g0 = 0 and b0 = 1 gives the following bounds, including the index shift in the first sum: n X ∥gt−1 ∥2

b3t−1

t=1

n X ∥gt ∥2 t=1 n  X 1 t=1

bt−1

−

b2t 1 bt

=

n−1 X

∥gt ∥2 1 ≤2 1− 3 bn−1 bt t=1

≤2



n X



≤ 2,

(log bt − log bt−1 ) = 2 log bn ,

t=1



=1−

1 ≤ 1. bn 19

(48)

The function and gradient terms in (47) telescope as follows: n X

f (xt ) − f (xt+1 ) = f (x1 ) − f (xn+1 ),

t=1 n X

∥∇f (xt−1 )∥2 ∥∇f (xt )∥2 − bt−1 bt

t=1

!

= ∥∇f (x1 )∥2 −

∥∇f (xn )∥2 . bn

Summing (47) and moving the gradient sum to the left therefore yields n 1 X 1 ∥∇f (xt )∥2 1 ∥∇f (xn )∥2 ≤ f (x1 ) − Ef (xn+1 ) + ∥∇f (x1 )∥2 − E E 4 t=1 bt−1 2 2 bn

1 σ2 1−E 2 bn 

+

≤ ∆f +



+ L2 E

n X ∥gt−1 ∥2

t=1 2 σ

b3t−1

+

n L X ∥gt ∥2 E 2 t=1 b2t

1 ∥∇f (x1 )∥2 + + 2L2 + LE log bn . 2 2

The last inequality uses f (xn+1 ) ≥ f∗ , (48), and the nonnegativity of ∥∇f (xn )∥2 /bn and 1/bn . Multiplication by four and concavity of the logarithm give E

n X ∥∇f (xt )∥2 t=1

bt−1

≤ 4∆f + 2 ∥∇f (x1 )∥2 + 2σ 2 + 8L2 + 4LE log bn = CA + 4LE log bn ≤ CA + 4L log(Ebn ).

(49)

We now bound Ebn . Since bt−1 ≤ bn for t ≤ n, n X

∥∇f (xt )∥2 =

t=1

n X t=1

bt−1

n X ∥∇f (xt )∥2 ∥∇f (xt )∥2 ≤ bn . bt−1 bt−1 t=1

Take square roots and apply Cauchy–Schwarz to the expectation: v  u n p uX Et ∥∇f (xt )∥2 ≤ E  bn t=1

!1/2  n X p ∥∇f (xt )∥2  ≤ Ebn t=1

bt−1

E

!1/2 n X ∥∇f (xt )∥2 t=1

bt−1

To relate bn to the true gradients, apply the Euclidean triangle inequality: bn = ∥(1, g1 , . . . , gn )∥ ≤ ∥(1, ∇f (x1 ), . . . , ∇f (xn ))∥ + ∥(0, g1 − ∇f (x1 ), . . . , gn − ∇f (xn ))∥ v v u u n n X u uX 2 t = 1+ ∥∇f (xt )∥ + t ∥gt − ∇f (xt )∥2 t=1

t=1

v v u n u n uX uX 2 t ≤1+ ∥∇f (xt )∥ + t ∥gt − ∇f (xt )∥2 . t=1

t=1

Concavity of the square root and the variance bound imply v v u n u n uX uX √ 2 t E ∥gt − ∇f (xt )∥ ≤ t E ∥gt − ∇f (xt )∥2 ≤ σ n. t=1

t=1

20

.

(50)

Combining these inequalities and then using uv ≤ (u2 + v 2 )/2 gives Ebn ≤ 1 +

p

Ebn E

!1/2 n X ∥∇f (xt )∥2

bt−1

t=1

√ +σ n

n √ 1 1 X ∥∇f (xt )∥2 ≤ 1 + Ebn + E + σ n. 2 2 t=1 bt−1

Subtract Ebn /2 and multiply by two. By (49), n X √ ∥∇f (xt )∥2 Ebn ≤ 2 + 2σ n + E bt−1 t=1 √ ≤ 2 + 2σ n + CA + 4L log(Ebn ).

For u ≥ 1, log u ≤

√

u. Since Ebn ≥ 1, another application of Young’s inequality gives p 1 4L log(Ebn ) ≤ 4L Ebn ≤ Ebn + 8L2 . 2

Substituting this inequality and again moving Ebn /2 to the left, we obtain √ 1 Ebn ≤ 2 + 2σ n + CA + Ebn + 8L2 , 2 √ Ebn ≤ 4 + 4σ n + 2CA + 16L2 = Mn . Putting this bound into (49) also gives E

n X ∥∇f (xt )∥2 t=1

bt−1

≤ CA + 4L log(Ebn ) ≤ CA + 4L log Mn ,

which proves both inequalities in (41). Finally, the Cauchy–Schwarz inequality and (50) yield 

v u



n n √ uX 1 1 X ∥∇f (xt )∥ ≤ E  nt ∥∇f (xt )∥2  E ∥∇f (An )∥ = E n t=1 n t=1

v u

n 1 uX = √ Et ∥∇f (xt )∥2 ≤ n t=1

s

≤

B.3

n Ebn X ∥∇f (xt )∥2 E n t=1 bt−1

!1/2

Mn (CA + 4L log Mn ) . n

Completion of the theorem

Fix the optimization path and positive weights w1 , . . . , wn . The probability of selecting index i and retaining it through round n is wi Pi

n Y

s=1 ws t=i+1

1 − Pt

wt

!

s=1 ws

= Pi

wi

n Y

s=1 ws t=i+1

Pt−1

wi ws = Pn . s=1 ws s=1 ws

Ps=1 t

With wt = ηt and wt = 1, respectively, this proves (13). Averaging over the paths gives E ∥∇f (Vn )∥ =

n 1 X ηt E ∇f (xVt ) , Wn t=1

E ∥∇f (An )∥ =

n 1X E ∇f (xA t ) . n t=1

21

The frozen candidates Vn , An each receive n validation samples and Lemma 2 gives  2σ E ∥∇f (Zn )∥ ≤ min E ∥∇f (Vn )∥ , E ∥∇f (An )∥ + √ . n

(51)

Under standard smoothness, Lemma 7 gives s

E ∥∇f (Zn )∥ ≤

Mn (CA + 4L log Mn ) 2σ +√ , n n

which is (18). Under mean-square smoothness, Lemma 6 further gives   s   ∆ + 2L + 2√K(1 + log n) 2σ M (C + 4L log M ) n n A f , +√ . E ∥∇f (Zn )∥ ≤ min   Wn n n

This proves (19). For n ≥ 1, √ √ Mn = 4 + 4σ n + 2CA + 16L2 ≤ (4 + 4σ + 2CA + 16L2 ) n, 1 log Mn ≤ log(4 + 4σ + 2CA + 16L2 ) + log n. 2 Hence

s

p  Mn (CA + 4L log Mn ) 2σ +√ =O 1 + log n n−1/4 . n n

For the variance reduction method, Wn ≥ n1/3 gives √ √ ∆f + 2L + 2 K(1 + log n) ≤ [∆f + 2L + 2 K(1 + log n)]n−1/3 . Wn Therefore,

√   ∆f + 2L + 2 K(1 + log n) 2σ + √ = O (1 + log n)n−1/3 . Wn n

When σ = 0, CA = 4∆f + 2 ∥∇f (x1 )∥2 + 8L2 ,

Mn = 4 + 2CA + 16L2 = 4 + 8∆f + 4 ∥∇f (x1 )∥2 + 32L2 .

Thus Mn is independent of n, and p

E ∥∇f (Zn )∥ ≤

(4 + 2CA + 16L2 )[CA + 4L log(4 + 2CA + 16L2 )] √ . n

This proves the O(n−1/2 ) rate under standard smoothness. At round τ ≥ 2, the latest report is Zn with n = 2⌊log2 τ ⌋−1 ,

2n ≤ τ < 4n,

τ τ <n≤ . 4 2

Consequently, n−1/3 < 41/3 τ −1/3 ,

n−1/4 < 41/4 τ −1/4 ,

n−1/2 < 2τ −1/2 ,

Substitution proves (20).

22

1 + log n ≤ 1 + log τ.

Related documents

• Adaptive Variance Reduction without Knowing Oracle Smoothness#1298295
• Towards Weaker Variance Assumptions for Stochastic Optimization#1116095
• Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad#200482
• A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muon#677577
• A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muon#674378