PaperlayerView exact revision on arXiv

Source-linked AI summary

Robustness to Unbounded Smoothness of Generalized SignSGD

Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, Zhenxun Zhuang

arXiv:2208.11195v1cs.LGmath.OC

TL;DR

Ordinary gradient-Lipschitz smoothness may not capture some deep-learning losses, motivating analysis under relaxed smoothness. The paper proposes generalized SignSGD updates without explicit clipping and proves a bound close to clipped SGD’s; it also identifies limitations concerning original Adam and the theory’s gradient-bound assumption.

  • Problem

    Gradient-Lipschitz smoothness does not capture some deep-learning losses, motivating optimization analysis under a relaxed condition that permits unbounded smoothness.

    Source: §1 · p. 1

  • Method

    The paper analyzes generalized SignSGD updates under relaxed smoothness, with momentum and a parameterization spanning SignSGD-like to Adam-like behavior.

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

  • Results

    The generalized SignSGD algorithm does not require explicit clipping and can almost guarantee the same bound as SGD with clipping under relaxed smoothness.

    Source: §6 · p. 11

  • Takeaways & Limitations

    Momentum reduces noise effects and exponentially decays the effects of unbounded gradient norms and smoothness in the analysis.

    Source: §1 · p. 3

    The analyzed algorithm is close to, but not equal to, original Adam, whose convergence under relaxed smoothness remains an open question; the theorem also assumes bounded gradients within the initial objective sublevel set.

    Source: §4.1 · p. 6, §6 · p. 11

Abstract

from arXiv · show

Traditional analyses in non-convex optimization typically rely on the smoothness assumption, namely requiring the gradients to be Lipschitz. However, recent evidence shows that this smoothness condition does not capture the properties of some deep learning objective functions, including the ones involving Recurrent Neural Networks and LSTMs. Instead, they satisfy a much more relaxed condition, with potentially unbounded smoothness. Under this relaxed assumption, it has been theoretically and empirically shown that the gradient-clipped SGD has an advantage over the vanilla one. In this paper, we show that clipping is not indispensable for Adam-type algorithms in tackling such scenarios: we theoretically prove that a generalized SignSGD algorithm can obtain similar convergence rates as SGD with clipping but does not need explicit clipping at all. This family of algorithms on one end recovers SignSGD and on the other end closely resembles the popular Adam algorithm. Our analysis underlines the critical role that momentum plays in analyzing SignSGD-type and Adam-type algorithms: it not only reduces the effects of noise, thus removing the need for large mini-batch in previous analyses of SignSGD-type algorithms, but it also substantially reduces the effects of unbounded smoothness and gradient norms. We also compare these algorithms with popular optimizers on a set of deep learning tasks, observing that we can match the performance of Adam while beating the others.

1 Introduction

The introduction motivates relaxed smoothness because gradient-Lipschitz assumptions may not capture deep-learning losses, then reports evidence that Transformers exhibit this behavior. It proposes a generalized SignSGD family spanning SignSGD to Adam-like updates and highlights momentum’s role in controlling noise and unbounded smoothness.

1 Introduction

  • The introduction places the contribution against non-convex optimization analyses that commonly assume Lipschitz gradients and establish convergence rates for methods including SGD, AdaGrad, and STORM.The paper previews formal settings and analysis, followed by deep-learning comparisons and conclusions.Source: §1 · pp. 1, 3
  • Relaxed (L0, L1) smoothness was proposed after evidence that ordinary gradient-Lipschitz smoothness does not capture LSTM training, where the Hessian can grow with gradient size.Prior work showed that gradient clipping can ensure SGD convergence under the relaxed condition, with later improved bounds.Source: §1 · pp. 1–2
  • Transformers appear to satisfy relaxed (L0, L1) smoothness, but coordinate and layer variation motivates a coordinate-wise version to better capture their loss surfaces.The evidence concerns Transformer training; the introduction points to Figure 1 for the global condition and Figure 3 for coordinate differences.Source: §1 · p. 2, Figure 1 · p. 2, Figure 3 · p. 2
  • The generalized SignSGD algorithm is parameterized to recover SignSGD at one end and closely resemble Adam at the other.The paper analyzes the family under relaxed smoothness.Source: §1 · pp. 2–3
  • Momentum reduces noise effects and exponentially decays the effects of unbounded gradient norms and smoothness in the analysis of Adam-type algorithms.The authors say this may partly explain why clipping does not help Adam in their Transformer experiment.Source: §1 · pp. 2–3

2 Related Works

Prior adaptive-method analyses address convex regret or non-convex functions under ordinary smoothness, while existing relaxed-smoothness work centers on clipping or normalization. The paper positions its contribution as guarantees for coordinate-wise optimizer updates, including generalized SignSGD and Adam-type methods, under relaxed smoothness.

Adaptive Gradient Methods

  • The paper claims the first guarantees for coordinate-wise optimizers such as generalized SignSGD and Adam-type updates under relaxed smoothness in the stochastic setting.Earlier adaptive-method analyses cited here address online convex optimization or non-convex smooth functions.Source: §2 · p. 3

Gradient Clipping

  • Prior relaxed-smoothness analyses established convergence for clipped SGD, while related work used gradient normalization and momentum without clipping.The cited normalized method uses one scale across coordinates, unlike Adam; the authors report empirically that normalized SGD with momentum performs worse than Adam.Source: §2 · p. 3

Adaptive Gradient Methods

  • Existing Adam variants using the momentum estimate to form the second moment were analyzed in smooth settings, with one cited result requiring a large epsilon for convergence.The cited later analyses remain restricted to smooth settings.Source: §2 · p. 4

3 Settings and Preliminaries

The paper studies stochastic optimization with differentiable, lower-bounded objectives and coordinate-wise relaxed smoothness. It motivates this finer condition by variation across Transformer layers and coordinates, and assumes bounded coordinate-wise gradient noise.

3 Settings and Preliminaries

  • Assumption 1 requires F to be differentiable and bounded below, while the stochastic setting represents sampled data or noise by ξ from distribution D.The optimization problem is introduced as stochastic optimization.Source: §3 · p. 4
  • Coordinate-wise (L0, L1) smoothness allows potentially unbounded smoothness when L1,j is nonzero and recovers ordinary smoothness when it is zero.The condition refines the global version because Transformer layers and coordinates can have very different (L0, L1) pairs.Source: §3 · p. 4
  • The coordinate-wise smoothness assumption yields a descent lemma for nearby points, with an additional distance condition stated in the lemma.The supplied lemma passage gives the condition in terms of the distance between x and y and coordinate differences.Source: §3 · pp. 4–5
  • The stochastic-gradient noise is assumed bounded almost surely in each coordinate by σ_j.The vector σ collects the coordinate-wise bounds.Source: §3 · p. 5

4 A Generalized SignSGD Algorithm

The generalized SignSGD algorithm spans SignSGD with momentum and an Adam-like update. Its analysis gives convergence guarantees under relaxed smoothness, including a guarantee that closely resembles SGD with gradient clipping.

4 A Generalized SignSGD Algorithm

  • The algorithm uses momentum to form mt and computes vt from m_t^2; changing this to g_t^2 yields Adam except for bias correction.The authors choose momentum in vt because the difference between mt and the true gradient is more controllable than the difference between gt and the true gradient.Source: §4 · p. 5

4.1 Theoretical Convergence Analysis

  • For the general case, the analysis assumes each coordinate’s gradient is bounded on the initial sublevel set, but imposes no gradient restriction outside it.The bound’s dependence on this upper bound decays exponentially with T; the β2 = 0 case does not require the assumption.Source: §4.1 · p. 6
  • For β2 > 0, the algorithm’s dependence on L1M decays exponentially, unlike gradient descent’s linear dependence on L1M.The gradient-descent comparison is stated for any constant step size under the relaxed-smoothness setting.Source: §4.1 · p. 6
  • When β2 = 0, the guarantee no longer requires bounded sublevel-set gradients and its final bound has no ∥L1∥∞ term.In this case the algorithm recovers SignSGD with momentum.Source: §4.1 · pp. 6–7
  • The β2 = 0 guarantee closely resembles SGD with gradient clipping, with the analysis using coordinate-wise smoothness.The paper says the bound is incomparable in general, but matches the cited result’s dependencies when the smoothness parameters are uniform and the noise and gradient vectors are dense.Source: §4.1 · p. 7
  • The proof controls stochastic noise with Freedman’s inequality and uses momentum to control the difference between the momentum and true gradient.The authors say controlling this difference requires choosing β1 wisely, including under unbounded smoothness.Source: §4.1 · p. 8

5 Experiments

Experiments compare the proposed algorithm with popular optimizers on image classification, language modeling, and Transformer training. The reported results include competitive performance and little difference between clipped and unclipped Adam on the tested language-modeling setup.

5 Experiments

  • The experiments use PyTorch on Nvidia V100 GPUs, and Figure 4 and Figure 5 show training curves with confidence-interval shading across five runs.Figure 4 covers CIFAR-10 ResNet training; Figure 5 covers word-level Penn Treebank language modeling with AWD-LSTM.Source: §5 · p. 8, Figure 4 · p. 9, Figure 5 · p. 9

5.1 Comparison with Other Optimizers

  • For CIFAR-10, the 20-layer ResNet is trained for 164 epochs with batch size 128, fixed weight decay 0.0001, and no learning-rate decay schedule.Learning rates and selected optimizer-specific hyperparameters are tuned on a separate validation set; testing is repeated with five random seeds.Source: §5.1 · pp. 9–10
  • On CIFAR-10, Algorithm 1 is among the best; on Penn Treebank, it matches Adam while beating the other compared optimizers.Table 1 reports average final training loss and test accuracy, with 95% confidence intervals over five runs.Source: Table 1 · p. 10, §5.1 · p. 10

5.2 Transformers Observe (L0, L1)-smoothness

  • The experiments verify the norm-based (L0, L1) condition and its coordinate-wise version using a 2-layer Wikitext-2 Transformer Encoder and a 6-layer German-English Transformer.The 6-layer model was trained on WMT’16 for 400 epochs, and the whole training trajectory was reported.Source: §5.2 · p. 10

5.3 Clipping does not Affect Adam’s Performance

  • For Wikitext-103 with GPT-2, clipped and unclipped Adam have similar training loss (2.79 vs 2.76) and perplexity (27.92 vs 27.97), despite clipping every batch.The experiment uses max_norm 0.25 clipping and reports results consistent with the authors’ account of Adam’s implicit clipping behavior.Source: §5.3 · p. 11

6 Conclusion and Limitations

The paper concludes that generalized SignSGD can approach the convergence bound of clipped SGD without explicit clipping, and reports competitive deep-learning performance. Its limitations include unresolved questions about original Adam, the role of β2, relaxed-smoothness lower bounds, model structure, and weight decay.

6 Conclusion and Limitations

  • Generalized SignSGD needs no explicit clipping and can almost guarantee the same bound as clipped SGD, while experiments report matching Adam and exceeding other optimizers.The analysis identifies momentum as reducing noise and the effects of unbounded smoothness and gradient norms.Source: §6 · p. 11
  • The proposed algorithm resembles Adam but is not identical, leaving convergence of Adam in its original form under relaxed smoothness open.The authors also note that their upper bounds do not fully explain why β2 near 1 performs better in practice than the β2 = 0 worst-case implication.Source: §6 · p. 11
  • Further work is needed on lower bounds for all first-order methods, the structures behind Transformer relaxed smoothness, and weight-decay methods that preserve scale-freeness.The authors report that best weight decay varies by optimizer.Source: §6 · p. 11

A.1 Properties of the coordinate-wise (L0, L1) Assumption 2

This appendix examines properties of the coordinate-wise relaxed-smoothness assumption. It relates the condition to the original one in one dimension and to the global form when coordinate parameters are uniform.

A.1 Properties of the coordinate-wise (L0, L1) Assumption 2

  • The appendix proves a descent lemma for functions satisfying coordinate-wise (L0, L1)-smoothness.The stated local condition on x and y is that their distance is at most 1/||L1||∞.Source: §A.1 · p. 16
  • In one dimension, the coordinate-wise (L0, L1) assumption is equivalent to the original condition.The appendix describes this equivalence for twice continuously differentiable functions.Source: §A.1 · p. 16
  • When all coordinates share the same L0 and L1 values, Assumption 2 implies the global condition up to constants.Source: §A.1 · p. 17

A.2 Proof of Lower Bound

The appendix gives a one-dimensional lower-bound construction for gradient descent under relaxed smoothness and corrects issues in an earlier lower-bound result. The construction and bound depend on the learning rate and stated function conditions.

A.2 Proof of Lower Bound

  • For any constant learning rate chosen with knowledge of the stated constants, the appendix constructs a bounded-below one-dimensional function on which gradient descent requires at least the stated number of iterations to reach gradient magnitude below ε.The function is (L0, L1)-smooth and its gradient is bounded by M on the initial sublevel set; the displayed bound is not fully legible in the supplied passage.Source: §A.2 · p. 17
  • The proof constructs different functions depending on the learning rate, using the equivalence between the one-dimensional coordinate-wise and original assumptions.Source: §A.2 · p. 17
  • The authors correct the earlier lower bound’s statement and proof by scaling the constructed functions, yielding coherent units and the appropriate conditions on L0, L1, M, and ε.They identify an undefined logarithm of a dimensional quantity and uncertainty about whether one constructed function satisfies the theorem’s assumptions.Source: §A.2 · p. 19

A.3 Proof of Theorem 1

The proof sets up notation and probabilistic lemmas for analyzing stochastic-gradient noise.

A.3 Proof of Theorem 1

  • The proof identifies two lemmas as its main tools for analyzing noise.One is a martingale concentration lemma; another is stated under Assumption 3 for Algorithm 1.Source: §A.3 · p. 20
  • The martingale lemma assumes a Hilbert-space martingale difference sequence with almost-surely bounded terms and bounded conditional second moments.It gives a high-probability bound over all k ≤ T.Source: §A.3 · p. 20
  • The proof treats each stochastic gradient gτ as an unbiased estimate of ∇F(xτ).Source: §A.3 · p. 20

0. Thus,

The proof bounds gradients by induction and uses a condition to identify approximate stationarity. It also gives a refined special-case guarantee when β2 = 0.

0. Thus,

  • When β2 = 0, the update displacement has norm η, and the generalized algorithm reduces to SignSGD with the same guarantee as (12).Source: §0 · pp. 24, 28
  • The induction bounds past true gradients by Mj by separating small-gradient proximity to stationarity from non-increasing objective values.The argument maintains F(xτ) ≤ F(x1) to obtain the gradient bound.Source: §0 · p. 29
  • Once condition (19) is met, the proof concludes that the algorithm has found an approximate stationary point.Source: §0 · p. 30

A.4 More Experiment Details

The appendix describes experiment tuning and dataset handling, then details a Transformer translation experiment in which the method matches Adam and beats other optimizers.

A.4 More Experiment Details

  • Hyperparameters are selected through coarse-then-fine grid search, extending a search boundary when the best choice lies on it.Source: §A.4 · p. 32
  • For CIFAR-10, 10% of training images are used for validation before testing with the full training set; Penn Treebank uses its original split.The AWD-LSTM experiments fix β1 at 0.9 except for SGDClipGrad, which has no momentum.Source: §A.4 · p. 32

A.5 Training a Transformer Model on WMT’16 German-English Translation Task

  • The Transformer evaluation trains a six-layer model on WMT’16 German-English translation for 400 epochs with batch size 256.The implementation uses the default model structure, 128,000 warm-up steps, and the repository’s learning-rate decay strategy.Source: §A.5 · p. 32
  • The Transformer experiment matches Adam’s performance while beating the other tested optimizers.Table 4 reports average final training loss, test perplexity, and test accuracy over five random-seed runs.Source: Table 4 · p. 33, §A.5 · p. 33
  • Figure 6 plots training curves whose shading represents 95% confidence intervals across five independent random-seed runs.Source: Figure 6 · p. 34
Loading 2208.11195v1…