PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Variance Reduction without Knowing Oracle Smoothness

Wei Jiang, Yibo Wang, Zechao Li

arXiv:2610.13799v1math.OCcs.LG

TL;DR

Adaptive variance reduction methods attain O(T^-1/3) under average smoothness without knowing problem parameters, but it remains unclear how to retain that guarantee while handling standard smoothness and noiseless settings. The paper proposes a two-phase method for known budgets and a two-path method for unknown budgets. The methods achieve the stated rates across these settings, with logarithmic factors for the anytime method in stochastic settings.

  • Problem

    Adaptive variance reduction attains O(T^-1/3) under average smoothness without knowing problem parameters, but how to retain that guarantee while also handling standard smoothness and noiseless settings remains an open question.

    Source: §1 · p. 1

  • Method

    For known budgets, a two-phase method switches from normalized gradient steps to normalized momentum using a two-gradient comparison, then applies normalized variance reduction; for unknown budgets, two paths combine variance reduction and AdaGrad-Norm.

    Source: §1 · pp. 1–2, §3 · p. 2

  • Results

    The known-budget method achieves O(T^-1/3) under average smoothness, O(T^-1/4) under standard smoothness, and O(T^-1/2) without noise; the anytime method attains corresponding rates up to logarithmic factors in stochastic settings.

    Source: §5 · pp. 6–7

  • Takeaways & Limitations

    Both methods use a constant number of gradient evaluations per round, include output-selection cost, and avoid restarting from the initial point.

    Source: §5 · p. 7

    The stronger rate depends on average smoothness, although the algorithms need not know whether that property holds.

    Source: §2 · p. 2

Abstract

from arXiv · show

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

The paper asks how adaptive variance reduction can retain its average-smoothness rate while also handling standard smoothness and noiseless settings without knowing problem parameters. It proposes a two-phase method for a known budget and a two-path method when the budget is unknown.

1 Introduction

  • STORM uses two evaluations with the same sample to form its gradient estimator and achieves O(T^-1/3) convergence under average smoothness.The setting is smooth non-convex optimization with only stochastic gradients available.Source: §1 · p. 1
  • Adaptive variance reduction retains the O(T^-1/3) rate under average smoothness without knowing L or σ, but adapting to standard smoothness and noiseless settings remains an open question.The paper frames this as preserving the faster average-smoothness guarantee while remaining reliable under general smoothness.Source: §1 · p. 1
  • For a known budget, the method compares two independent gradients, switches to normalized momentum after a threshold failure, then applies normalized variance reduction.The second phase begins from the current point.Source: §1 · pp. 1–2
  • When the budget is unknown, the method maintains a normalized variance-reduction path and an AdaGrad-Norm path.The latter provides standard-smooth and noiseless guarantees.Source: §1 · p. 2

2 Assumptions and notation

The paper assumes a smooth non-convex objective, unbiased stochastic gradients with bounded variance, and a lower-bounded objective. Average smoothness is an additional property for a stronger rate, but the algorithms need not know whether it holds.

2 Assumptions and notation

  • The framework assumes standard smoothness, unbiased gradients with bounded variance, and a lower-bounded objective.The assumptions introduce the smoothness constant L, variance bound, and initial objective gap.Source: §2 · p. 2
  • Average smoothness is an additional property used for the stronger rate, but the algorithms do not need to know whether it holds.Average smoothness is also called mean-squared smoothness.Source: §2 · p. 2
  • Neither algorithm uses L, average-smoothness constant, σ, the initial objective gap, or function values.The paper also does not assume bounded gradients, a bounded domain or objective range, or higher noise moments.Source: §2 · p. 2
  • A weighted reservoir stores one point by replacing its current value with each new point according to that point’s weight relative to the cumulative weight.The implementation stores a single point rather than the entire path.Source: §2 · p. 2

3 The proposed method for a known budget

For a known gradient budget, the method combines normalized gradient steps, normalized momentum, and normalized variance reduction in two phases. It stores candidates and uses validation gradients for output selection, with guarantees stated for standard-smooth, average-smooth, and noiseless settings.

3 The proposed method for a known budget

  • The known-budget method allocates two optimization phases, using normalized stochastic gradient steps and normalized momentum in the first, then normalized variance reduction in the second.The first phase provides the standard-smooth guarantee and accelerates automatically when the oracle is noiseless.Source: §3 · pp. 2–3

3.1 Updates and outputs

  • The first phase compares two independent gradients and takes normalized gradient steps while their difference stays below a threshold, switching permanently to normalized momentum after the first failure.In the noiseless setting, the test always passes and the phase remains normalized gradient descent.Source: §3.1 · p. 3
  • The method stores a weighted-reservoir candidate from the first phase and a uniform-reservoir candidate from the second, then selects between them using validation-gradient norms.Validation gradients are collected for each candidate; the final validation rounds require no optimization updates.Source: §3.1 · p. 3, §3.2 · p. 4

3.2 Guarantees

  • The guarantee statements cover Assumptions 1–3, an additional case when Assumption 4 holds, and a separate noiseless-oracle case.The phase length n is chosen from the budget, with b validation samples per candidate.Source: §3.2 · pp. 3–4, §3 · p. 3

4 The anytime algorithm

The anytime algorithm maintains variance-reduction and AdaGrad-Norm paths, validates frozen candidates at doubling checkpoints, and reports the candidate with the smaller estimated gradient norm. Its guarantees cover mean-square smoothness, standard smoothness, and the noiseless case.

4.1 The proposed schedule

  • The two paths pair variance reduction for mean-square smoothness with AdaGrad-Norm for standard smoothness and noiseless guarantees.Both paths start from x1 and maintain a reservoir candidate.Source: §4.1 · pp. 4–5
  • At checkpoints 1, 2, 4, 8, …, the method freezes both reservoirs, validates them with fresh gradients, and reports the point with the smaller estimated gradient norm.The optimization paths continue during validation rounds.Source: §4.1 · p. 5

4.2 Guarantees

  • Theorem 2 considers the Algorithm’s reported point at every deterministic round τ ≥ 2, with n defined by (16), assuming a lower-bounded L-smooth objective and an unbiased oracle with variance at most σ².Source: §4.2 · p. 5
  • For fixed problem parameters, the three rates include logarithmic factors in stochastic settings, while the theorem states the reported-point guarantee at every deterministic round τ ≥ 2.The bounds are stated for an oracle with standard smoothness and bounded variance, with an additional mean-square smoothness condition for the variance-reduction guarantee.Source: §4.2 · pp. 5–6

5 Conclusion

The paper addresses stochastic non-convex optimization without knowing whether the oracle has average or standard smoothness, or knowing the smoothness and variance parameters. It proposes known- and unknown-budget methods with corresponding convergence guarantees, without restarts or a growing number of oracle calls per round.

5 Conclusion

  • The known-budget method achieves expected gradient norm bounds of O(T^-1/3) under average smoothness, O(T^-1/4) under standard smoothness, and O(T^-1/2) without noise.The method does not require knowing the smoothness constants or variance bound.Source: §5 · pp. 6–7
  • The anytime two-path method attains the corresponding rates up to logarithmic factors in stochastic settings and retains the O(T^-1/2) noiseless rate.Both methods use a constant number of gradient evaluations per round, include output-selection cost, and avoid restarting from the initial point.Source: §5 · p. 7

A Proof of Theorem 1

The proof of Theorem 1 develops lemmas for normalized updates, candidate selection, and gradient-difference testing, then applies them to the direct-gradient phase.

A.1 Useful Lemmas

  • The useful lemmas include a bound for normalized updates and a result for selecting among random candidates using averaged stochastic gradients.The candidate is selected by the smallest norm among the averaged gradients.Source: §A.1 · p. 8
  • A gradient-difference lemma relates the probability that two independent gradients differ beyond a threshold to their variance.The proof applies it with threshold n^-1/2 for a direct step.Source: §A.2 · pp. 9–10

A.2 Direct-gradient step

  • For direct-gradient steps, the proof tracks whether earlier tests passed and partitions outcomes by the first failure event.The possible first-failure events are disjoint.Source: §A.2 · pp. 9–10

A.3 Momentum step

The momentum-step proof bounds the error accumulated by normalized momentum and analyzes the phase after the first failed gradient test, including the noiseless case.

A.3 Momentum step

  • The momentum update exponentially averages stochastic gradients with parameter β before taking a normalized step.The sequence starts with one stochastic gradient and uses the stated recursion for later updates.Source: §A.3 · p. 10
  • The proof bounds the squared norm of the accumulated noise and applies the momentum lemma when a first test failure starts momentum at xs.If no test fails, there are no momentum updates.Source: §A.3 · p. 11
  • When σ = 0, every test passes and the gradients equal the true gradient; the proof then uses normalized descent and equal reservoir weights.The passage states the noiseless case's setup and ensuing descent analysis.Source: §A.3 · p. 12

A.4 The variance reduction step

The variance-reduction phase uses a gradient estimator with a reservoir-sampled output, and its starting point is controlled by the first phase. The validation phase compares candidates and accounts for the oracle-call budget.

A.4 The variance reduction step

  • The estimator error is analyzed from its initialization and update, with the proof bounding the gradient-difference contribution before applying the phase lemmas.The initialization has expected squared error at most σ².Source: §A.4 · p. 13
  • The variance-reduction phase starts at x_(n+1), whose expected function gap is bounded by CG; Lemma 5 is then applied to that phase.The reservoir over the phase assigns probability 1/n to each point, and its estimator uses β = η = n^-2/3.Source: §A.4 · p. 14

A.5 Validation phase

  • During validation, the proof applies Lemma 2 with m = 2 and b samples at each of XG and XV.The noiseless case uses exact validation; the average-smoothness case instead invokes (35).Source: §A.5 · pp. 14–15
  • The stated call count is at most 4n + 2b ≤ T, with at most three oracle calls per round.The accounting includes the first phase, variance-reduction phase, and final validation.Source: §A.5 · p. 15

B Proof of Theorem 2

This proof analyzes the variance-reduction update under mean-square smoothness. It uses a time-varying momentum parameter and a weighted-reservoir candidate.

B.1 Variance reduction bound

  • Lemma 6 analyzes update (9)–(11) under mean-square smoothness, with the estimator error initialized at t = 1.The proof sets K = 6L̄² + 2σ² and uses β_t = t^-2/3 for t ≥ 2.Source: §B.1 · pp. 15–16
  • The estimator-error proof expands the update and removes cross terms with the previous error because the bracketed terms have zero mean.It then bounds the sum of the bracketed terms using the squared-norm inequality.Source: §B.1 · pp. 15–16
  • The proof uses deterministic weights η_t and an index-selection law to analyze the weighted-reservoir candidate.The passage identifies a bound for that candidate but does not provide its value here.Source: §B.1 · pp. 15, 17

B.2 AdaGrad-Norm bound

The AdaGrad-Norm analysis establishes a bound under standard smoothness and bounded variance. Its proof uses a potential argument and a uniformly sampled output.

B.2 AdaGrad-Norm bound

  • The proof follows a potential approach and is presented for bounded variance with a uniformly sampled output.It rewrites the gradient-norm term for summation, then uses smoothness and telescoping terms.Source: §B.2 · pp. 17–20
  • Under standard smoothness and bounded variance, Lemma 7 gives a bound for update (12).The supplied statement does not include the bound's full expression.Source: §B.2 · p. 17
  • The summation proof yields a negative coefficient of -1/4 for the gradient-norm term before moving its sum to the left.This follows after inserting the preceding bounds and averaging over earlier samples.Source: §B.2 · pp. 19–20
  • The proof states a bound for the uniform-reservoir candidate after relating the AdaGrad normalization scale to the true gradients.The candidate's bound is referenced as (41), but its full expression is not included here.Source: §B.2 · pp. 17, 20, 21

B.3 Completion of the theorem

The proof completes the theorem by applying the variance-reduction and AdaGrad-Norm bounds under their respective smoothness conditions. It converts the phase length to the budget parameter and averages over paths.

B.3 Completion of the theorem

  • The proof averages over paths after using weights w_t = η_t and w_t = 1 to establish (13).The supplied passage does not include the resulting averaged bound.Source: §B.3 · p. 21
  • The frozen candidates V_n and A_n each receive n validation samples, and Lemma 2 is used to validate them.Under standard smoothness the proof invokes Lemma 7; under mean-square smoothness it additionally invokes Lemma 6.Source: §B.3 · p. 22
  • For the standard-smoothness bound, M_n is defined from C_A and L, and the proof states that M_n is independent of n.The displayed expression for C_A includes the initial function gap and gradient norm.Source: §B.3 · p. 22
  • The budget substitution gives n^-1/3 < 4^(1/3)τ^-1/3, n^-1/4 < 4^(1/4)τ^-1/4, and n^-1/2 < 2τ^-1/2.It also gives 1 + log n ≤ 1 + log τ.Source: §B.3 · p. 22
Loading 2610.13799v1…