PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Adaptive Methods, Universality and Acceleration

Kfir Y. Levy, Alp Yurtsever, Volkan Cevher

arXiv:1809.02864v1cs.LGmath.OCstat.ML

TL;DR

Earlier approaches addressed noisy feedback and unknown smoothness separately, leaving open whether one accelerated method could address both. AcceleGrad combines an accelerated-gradient-like update with adaptive learning rates, importance weighting, and a linearly coupled-sequence update. AcceleGrad achieves O(1/T^2) in the smooth case and ˜O(1/T) in the general case, without prior information about objective smoothness.

  • Problem

    Earlier approaches addressed noisy feedback and unknown smoothness separately, leaving open whether one accelerated method could address both.

    Source: §1 · p. 2

  • Method

    AcceleGrad combines an accelerated-gradient-like update with adaptive learning rates, importance weighting, and a linearly coupled-sequence update.

    Source: §1 · pp. 2–3

  • Results

    AcceleGrad achieves O(1/T^2) in the smooth case and ˜O(1/T) in the general case, without prior information about objective smoothness.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The method is presented as a universal approach that may exploit smoothness to accelerate while still handling noisy feedback.

    Source: §6 · p. 15

    The current analysis applies only to unconstrained optimization; extending it to constrained problems remains future work.

    Source: §6 · p. 15

Abstract

from arXiv · show

We present a novel method for convex unconstrained optimization that, without any modifications, ensures: (i) accelerated convergence rate for smooth objectives, (ii) standard convergence rate in the general (non-smooth) setting, and (iii) standard convergence rate in the stochastic optimization setting. To the best of our knowledge, this is the first method that simultaneously applies to all of the above settings. At the heart of our method is an adaptive learning rate rule that employs importance weights, in the spirit of adaptive online learning algorithms (Duchi et al., 2011; Levy, 2017), combined with an update that linearly couples two sequences, in the spirit of (Allen-Zhu and Orecchia, 2017). An empirical examination of our method demonstrates its applicability to the above mentioned scenarios and corroborates our theoretical findings.

1 Introduction

The paper addresses whether one accelerated method can handle both noisy feedback and unknown smoothness, which earlier approaches addressed separately. It proposes AcceleGrad and claims rates for smooth, general convex, and stochastic settings without changing the method.

1 Introduction

  • The open gap was whether a method could address noisy feedback and unknown smoothness together: prior methods handled these issues separately.Nesterov’s universal method uses line search and is unsuitable for noisy feedback, while cited noisy-feedback methods require knowledge of smoothness and variance.Source: §1 · p. 2
  • AcceleGrad combines an accelerated-gradient-like update with an AdaGrad-style adaptive learning rate for unconstrained convex optimization.Its technical design uses learning-rate adaptation with importance weighting and an update that linearly couples two sequences.Source: §1 · pp. 2–3
  • AcceleGrad achieves O(1/T^2) in the smooth case and ˜O(1/T) in the general case without prior smoothness information.The general-case rate is stated across the contribution passages as ˜O(1/T).Source: §1 · p. 2
  • Without modification, AcceleGrad also ensures a standard convergence rate in general stochastic convex optimization.The contribution text identifies the setting; the stochastic section says the same algorithm applies with noisy gradient estimates.Source: §1 · p. 2
  • AdaGrad achieves O(1/T + σ/√T) for smooth expected loss under stochastic optimization without knowing smoothness, establishing universality but not acceleration.The paper defines universal as not requiring advance knowledge of whether the objective is smooth.Source: §1 · pp. 2–3

2 Setting and Preliminaries

The setup is unconstrained convex optimization using first-order information, with smooth and non-smooth objectives considered. The analysis assumes a bounded-distance region containing a global minimizer and a Lipschitz objective, but does not assume knowledge of smoothness.

2 Setting and Preliminaries

  • The paper studies approximately minimizing a convex function over Rd using first-order methods that require gradient information.Both smooth and non-smooth objectives are considered.Source: §2 · p. 4
  • The method does not assume the smoothness parameter β is known, but assumes a bound on the distance from the initial point to a global minimizer.A compact convex set K contains a global minimizer; its diameter D bounds that distance, and the objective is G-Lipschitz.Source: §2 · p. 4
  • The stochastic setting replaces exact gradients with noisy, unbiased gradient estimates.The passage identifies this setting as prevalent in machine learning.Source: §2 · p. 4
  • AdaGrad adapts its learning rate using gradient feedback, and its offline error guarantees are presented as a theorem in this setup.The paper notes that AdaGrad is known for online regret guarantees and gives offline error guarantees for concreteness.Source: §2 · p. 4

3 Offline Setting

AcceleGrad combines linearly coupled sequences with an adaptive, importance-weighted learning rate to obtain guarantees in smooth and general convex offline optimization. Its smooth-case analysis establishes an accelerated rate despite the learning rate being independent of the smoothness parameter.

3 Offline Setting

  • AcceleGrad achieves O(1/T^2) convergence for smooth objectives and O(sqrt(log T/T)) for general convex objectives.The section states these rates for the smooth and general convex cases, respectively.Source: §3 · p. 5
  • Linearly coupled sequences use different gradient updates, while an adaptive learning rate incorporates increasing importance weights that emphasize recent queries.The method outputs a weighted average of the y-sequence; its learning rate is independent of β.Source: §3 · pp. 5–6
  • For non-smooth objectives, a projection step extends AcceleGrad to constrained optimization, including when the minimizer over K is not global.The passage states that this modification provides guarantees, but its displayed bound is incomplete.Source: §3 · p. 7

3.1 Analysis of the Smooth Case

  • For smooth objectives, the weighted output has error O(βD^2/T^2).The smooth-case guarantee assumes convexity, β-smoothness, bounded diameter D, and a global minimizer in K.Source: §3 · p. 6, §3.1 · p. 8

4 Stochastic Setting

The stochastic setting uses noisy gradient feedback, and the paper proves that Algorithm 2 converges there without modification. It also shows that AdaGrad is universal and can exploit small variance when the expected loss is smooth.

4 Stochastic Setting

  • Algorithm 2 retains convergence guarantees with noisy gradients in the stochastic setting, without modification.The theorem setup assumes a convex, G-Lipschitz objective, bounded-diameter K, and a global minimizer in K.Source: §4 · p. 11
  • The stochastic setup measures expected excess loss after T rounds of querying points for feedback.The feedback is described as a bounded, unbiased noisy gradient estimate with independent oracle randomizations.Source: §4 · p. 11
  • AdaGrad has the standard O(GD/T) stochastic rate and is shown to be universal, exploiting small variance for fast rates with smooth expected loss.These guarantees do not require prior knowledge of smoothness or a variance bound.Source: §4 · pp. 11–12

5 Experiments

The experiments compare AcceleGrad with AdaGrad and universal gradient methods on smooth and non-smooth regression, including offline and stochastic settings. They report deterministic gains over AdaGrad, stochastic performance similar to AdaGrad where line-search methods fail, and favorable behavior at larger minibatch sizes.

5 Experiments

  • The offline comparison uses exact gradients, initializes all methods at the origin, and constrains iterates to an ℓ2 ball of diameter D.The evaluated regression problems include smooth (p = 2) and non-smooth (p = 1) cases.Source: §5 · p. 13
  • For universal gradient methods, ε controls a trade-off: smaller ε helps smooth problems, while non-smooth problems show late adaptation with small ε and early saturation with large ε.Tuning is difficult because it requires rough knowledge of the optimal value.Source: §5 · p. 14
  • Universal gradient methods require two line-search iterations per outer iteration on average, compared with one data pass per iteration for AdaGrad and AcceleGrad.The fast universal version requires four data passes per iteration.Source: §5 · p. 14
  • AcceleGrad consistently overperforms AdaGrad in the deterministic setting, though overestimating D causes early-iteration overshoot.The reported tuning parameter ρ is the ratio between D/2 and the distance from the initial point to the solution.Source: §5 · p. 14
  • With noisy minibatch feedback, universal line-search methods fail, while AcceleGrad converges and performs similarly to AdaGrad.The study also considers stochastic gradients of F.Source: §5 · p. 14
  • As batch size increases, AcceleGrad's performance versus gradient calculations does not degrade and may improve, whereas AdaGrad degrades.The passage presents this as beneficial for parallelizing stochastic optimization.Source: §5 · p. 15

6 Conclusion and Future Work

The conclusion presents AcceleGrad as a universal method that can exploit smoothness for acceleration while handling noisy feedback. The analysis is limited to unconstrained optimization; extending it to constrained problems and adapting D implicitly are future directions.

6 Conclusion and Future Work

  • AcceleGrad may exploit smoothness to accelerate while still successfully handling noisy feedback.The authors' current analysis applies only to unconstrained optimization.Source: §6 · p. 15
  • The analysis covers unconstrained optimization; extending the method to constrained settings and implicitly adapting D are identified as future directions.The authors suggest scale-free online algorithm ideas for adapting D.Source: §6 · p. 15

A Proofs for the Smooth Case (Thm. 3.1)

The smooth-case proof bounds the weighted suboptimality and uses the algorithm's weights, learning rates, and averaged output to establish the theorem. Its supporting lemmas control the coupled updates and the inequalities needed for the final bound.

A.1 Proof of Lemma 3.1

A.3 Proof of Lemma A.1

A.2 Proof of Lemma A.4

  • The proof of Lemma A.4 uses the first-order optimality condition of the z-update to bound its contribution to the smooth-case argument.The update is written as a minimization involving the squared-distance regularizer.Source: §A.2 · p. 27

A.2.1 Proof of Lemma A.5

  • Lemma A.5 is supported by a direct calculation using the gradient of the squared-distance regularizer.The text notes that the lemma may extend to general Bregman divergences.Source: §A.2 · p. 27, §A.2.1 · p. 28

A.4 Proof of Lemma A.2

A.5 Proof of Lemma A.3

  • Lemma A.3 follows by induction after establishing that log(1 + x) − x/(1 + x) is nonnegative for x ≥ 0.The proof uses this inequality to complete its induction step.Source: §A.5 · pp. 29–30

B Proofs for the General Convex Case (Thm. 3.2)

The general-convex proof bounds the weighted suboptimality for convex G-Lipschitz objectives, then combines the component bounds to obtain the theorem's final rate. A separate lemma controls terms in that bound using a partition of iteration times.

B Proofs for the General Convex Case (Thm. 3.2)

  • For convex G-Lipschitz objectives, Lemma B.1 provides a weighted-suboptimality bound for arbitrary nonnegative weights and learning rates.The theorem proof combines component bounds and uses Jensen's inequality for the weighted-average output.Source: B Proofs for the General Convex Case… · pp. 31, 33, 34

B.1 Proof of Lemma B.1

  • The proof of Lemma B.1 decomposes weighted suboptimality into terms and bounds one using the Lipschitz condition and the update relation.The displayed bound uses ∥f(y_{t+1}) − f(x_{t+1})∥ ≤ G∥y_{t+1} − x_{t+1}∥ ≤ Gη_t∥g_t∥.Source: §B.1 · pp. 34–35

B.2 Proof of Lemma B.2

  • The proof of Lemma B.2 partitions iteration times into intervals and bounds their count using ∥u∥_1 ≤ √n∥u∥_2.The argument applies the definitions of the time variables to establish the needed bounds.Source: §B.2 · pp. 35–37

C Proof of Theorem 4.1

The stochastic proof establishes a bound for AcceleGrad with noisy gradient estimates, then adapts the exact-gradient analysis using their unbiasedness. Taking expectations and applying Jensen’s inequality completes the argument.

C Proof of Theorem 4.1

  • Lemma C.1 establishes a bound for Algorithm 2 with noisy gradient estimates under convexity and G-Lipschitz continuity.The bound applies to any non-negative weights and learning rates.Source: C Proof of Theorem 4.1 · p. 38
  • After ignoring the zero-mean term, the stochastic bound matches the exact-gradient expressions with noisy gradients substituted.The proof therefore reuses the exact-gradient analysis for the learning-rate choice.Source: C Proof of Theorem 4.1 · p. 38
  • The proof concludes by taking expectations and applying Jensen’s inequality to the averaged iterate.This follows the intermediate bound derived from Lemma C.1.Source: C Proof of Theorem 4.1 · p. 38

C.1 Proof of Lemma C.1

  • The proof decomposes the objective gap into contributions from the noisy gradient, the exact gradient, and their difference.The unbiasedness argument applies to the difference term.Source: §C.1 · p. 39
  • Unbiasedness makes the expected error term involving the difference between exact and noisy gradients zero.This removes that term before bounding the remaining contributions.Source: §C.1 · p. 39

D Proof of Lemma 4.1

The appendix begins the proof of Lemma 4.1 by invoking β-smoothness and the fact that the global minimizer has no greater objective value than any other point. It then introduces additional numerical experiments.

D Proof of Lemma 4.1

  • The proof uses β-smoothness to establish an inequality for all x and u in R^d.The supplied passage introduces the condition but does not include the inequality itself.Source: D Proof of Lemma 4.1 · p. 40
  • The final inequality relies on the global minimum x∗ having objective value no greater than at x + u.This is the stated justification for that inequality step.Source: D Proof of Lemma 4.1 · p. 40

E Additional Numerical Experiments

  • The appendix’s additional experiments cover stochastic optimization and a practical variant that omits projection steps.The experiments are presented separately from the proof.Source: E Additional Numerical Experiments · p. 41

E.1 Numerical Experiments on the Stochastic Setting

In stochastic experiments using single-data-point unbiased gradient estimates, AdaGrad and AcceleGrad perform similarly across most parameter choices. Additional experiments report that omitting projections works well in the unconstrained setting.

E.1 Numerical Experiments on the Stochastic Setting

  • The stochastic comparison uses unbiased gradient estimates from a single data point, with each epoch representing 500 iterations.Figure 2 compares smooth (top) and non-smooth (bottom) problems.Source: §E.1 · p. 41, Figure 2 · p. 41
  • AdaGrad and AcceleGrad perform similarly for most stochastic parameter choices, with AdaGrad ahead only on the smooth problem at ρ = 1.The authors attribute this exception to projection and report that slightly increasing D cures it for AcceleGrad.Source: §E.1 · p. 41, Figure 2 · p. 41
  • Universal gradient methods based on line search are not shown because they fail in practice with stochastic feedback.Their line search relies on exact first-order oracle information.Source: §E.1 · p. 42

E.2 Numerical Experiments Neglecting the Projections

  • Ignoring projection works well in the unconstrained setting and may even improve performance in some cases.The method also works when D is underestimated; Figures 3 and 4 show deterministic and stochastic results, respectively.Source: §E.2 · p. 42, Figure 3 · p. 42, Figure 4 · p. 43

E.3 Experiments with Large Minibatch

Large-minibatch experiments compare AcceleGrad with AdaGrad on logistic regression and SVM. For very small target error, AcceleGrad’s performance improves as minibatch size increases, unlike AdaGrad’s predicted degradation with larger minibatches.

E.3 Experiments with Large Minibatch

  • The experiments use RCV14 binary classification with 20,424 samples and 47,366 features, testing logistic loss and hinge loss across minibatch sizes.The paper reports similar behavior for SVM training.Source: §E.3 · pp. 43–44
  • For AdaGrad, performance degrades when minibatch size exceeds b = 1000, consistent with theory.The experiment trains logistic regression on the RCV14 dataset using different minibatch sizes.Source: §E.3 · pp. 43–44
  • At errors below 10^-2, AcceleGrad’s performance improves as minibatch size increases.The authors explain that more accurate gradients let AcceleGrad approach O(1/T^2), while AdaGrad approaches O(1/T).Source: §E.3 · p. 44
  • With S gradient calculations, T = S/b; as minibatch size increases, the stated rates approach O(b^2/S^2) for AcceleGrad and O(b/S) for AdaGrad.These rate comparisons are reported for the large-minibatch regime.Source: §E.3 · p. 44

Related papers

Loading 1809.02864v1…