summaries: The submission presents convergence results for clipped stochastic gradient methods without the sub-Gaussian assumption.  The subject of the submission is of interest to the NeurIPS community. As we find that some of our most difficult problems exhibit heavy-tailed noise, how to handle it in stochastic optimization is becoming more and more relevant.   My understanding of the main contributions of the paper over existing work is that this submission considers $\nu$-Hölder continuity (interpolating between Lipschitz functions and function with Lipschitz gradients) without assuming the stochastic gradients be sub-Gaussian (but still having bounded variance) - For the case $\nu = 0$ (Lipschitz functions), recovers tighter bounds (logarithmic dependence on the confidence level $\beta$ instead of polynomial) than naïve applications of Markov's inequality to results in expectation.  - For the case of $\nu = 1$ (Lipschitz gradient), the claimed contribution over the existing results of Gorbunov et al. [14] is that the problem need only be smooth in a ball around a minimum.

summaries: The authors proposed  clipped-SSTM and its restart version for stochastic nonsmooth optimization with heavy tailed noise. A detailed convergence analysis shows the theoretical advantage of the proposed algorithm. Experiments on real models (Bert) show that clipped-SSTM outperforms standard SGD methods.

summaries: The paper tackles the important problem of high-probability convergence bounds for machine learning optimisation problems. Traditional analyses are done in expectation, which have been shown to not accurately represent all possible training outcomes; hence the need for tighter studies. In this paper, in the specific setting of convex, non-smooth losses with heavy tailed noise, a new high-probability bound is introduced for two algorithms. What sets it apart from previous bounds is that there is no direct negative dependency on the confidence bound (only logarithmic ones); and that in some cases it matches the non-heavy tailed noise bound. Numerical experiments illustrating the theoretical results are presented.

summaries: This paper aims to obtain the high probability convergence for the convex stochastic optimization problem when the stochastic gradient of the objective function is not assumed to be sub-Gaussian. While this goal has been achieved in two recently proposed optimizers by exploiting the gradient clippings technique under the smoothness assumption on the objective, this paper considers the more general setting when corresponding gradient only satisfies a Holder continuity condition. This condition recovers the smooth and non-smooth settings when an extra parameter takes extreme values. In such a more general problem formulation, the authors propose new step-size schemes such that the convergence rate of the aforementioned optimizers (designed for smooth problems) can be smoothly extrapolated to the non-smooth setting.

summaries: This paper analyzes the clipped SGD and clipped SSTM algorithm on generalized smooth objectives with Hölder-continuous gradients. They consider the case where the assumption of sub-Gaussian noise is not needed. They modified the stepsize in the clipped SSTM algorithm to fit the Hölder-continuity assumption. Theoretical analysis is conducted with convergence rates presented.

abstractText: Thanks to their practical efficiency and random nature of the data, stochastic 1 first-order methods are standard for training large-scale machine learning models. 2 Random behavior may cause a particular run of an algorithm to result in a highly 3 suboptimal objective value, whereas theoretical guarantees are usually proved 4 for the expectation of the objective value. Thus, it is essential to theoretically 5 guarantee that algorithms provide small objective residual with high probability. 6 Existing methods for non-smooth stochastic convex optimization have complexity 7 bounds with the dependence on the confidence level that is either negative-power or 8 logarithmic but under an additional assumption of sub-Gaussian (light-tailed) noise 9 distribution that may not hold in practice, e.g., in several NLP tasks. In our paper, 10 we resolve this issue and derive the first high-probability convergence results with 11 logarithmic dependence on the confidence level for non-smooth convex stochastic 12 optimization problems with non-sub-Gaussian (heavy-tailed) noise. To derive our 13 results, we propose novel stepsize rules for two stochastic methods with gradient 14 clipping. Moreover, our analysis works for generalized smooth objectives with 15 Hölder-continuous gradients, and for both methods, we provide an extension for 16 strongly convex problems. Finally, our results imply that the first (accelerated) 17 method we consider also has optimal iteration and oracle complexity in all the 18 regimes, and the second one is optimal in the non-smooth setting. 19

venue: Journal 270 of the American Statistical Association,

authors:
Caroline Chaux
Patrick L Combettes
Jean-Christophe Pesquet
Valérie R Wajs

title: A varia- 272 tional formulation for frame-based inverse problems

venue: Inverse Problems,

authors:
Damek Davis
Dmitriy Drusvyatskiy
Lin Xiao
Junyu Zhang

title: From low probability to 275 high confidence in stochastic convex optimization

venue: Journal of Machine Learning Research,

title: Exactness, inexactness and stochasticity in first-order methods for large-scale 278 convex optimization

venue: PhD thesis, PhD thesis,

authors:
Olivier Devolder
François Glineur
Yurii Nesterov

title: First-order methods of smooth convex 280 optimization with inexact oracle

venue: Mathematical Programming,

authors:
Pavel Dvurechensky
Alexander Gasnikov

title: Stochastic intermediate gradient method for con- 282 vex problems with stochastic inexact oracle

authors:
Kacha Dzhaparidze
JH Van Zanten

title: On bernstein-type inequalities for martingales

venue: Stochas- 285 tic processes and their applications,

title: On tail probabilities for martingales

authors:
Alexander Vladimirovich Gasnikov
Yu E Nesterov
Vladimir Grigor’evich Spokoiny

authors:
Jonas Gehring
Michael Auli
David Grangier
Denis Yarats
Yann N Dauphin

title: Convolutional 292 sequence to sequence learning

venue: In Proceedings of the 34th International Conference on Machine 293 Learning-Volume

authors:
Saeed Ghadimi
Guanghui Lan

title: Optimal stochastic approximation algorithms for strongly 295 convex stochastic composite optimization i: A generic algorithmic framework

venue: SIAM Journal 296 on Optimization,

title: Stochastic first-and zeroth-order methods for nonconvex 298 stochastic programming

venue: SIAM Journal on Optimization,

authors:
Ian Goodfellow
Yoshua Bengio
Aaron Courville

title: Deep Learning. MIT Press, 2016

authors:
Robert Mansel Gower
Nicolas Loizou
Xun Qian
Alibek Sailanbayev
Egor Shulgin
Peter 306 Richtárik

title: Sgd: General analysis and improved rates

venue: In International Conference on Machine 307 Learning,

authors:
Vincent Guigues
Anatoli Juditsky
Arkadi Nemirovski

title: Non-asymptotic confidence bounds 309 for the optimal value of a stochastic program

venue: Optimization Methods and Software,

authors:
Cristóbal Guzmán
Arkadi Nemirovski

title: On lower complexity bounds for large-scale smooth 312 convex optimization

venue: Journal of Complexity,

authors:
Elad Hazan
Kfir Levy
Shai Shalev-Shwartz

title: Beyond convexity: Stochastic quasi-convex 314 optimization

authors:
Anatoli Juditsky
Arkadi Nemirovski

title: First order methods for nonsmooth convex large- 316 scale optimization, i: general purpose methods. Optimization for Machine Learning, pages

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint 319

venue: Mathematical 321 Programming,

authors:
Vien V Mai
Mikael Johansson

title: Stability and convergence of stochastic gradient clipping: 323 Beyond lipschitz continuity and smoothness

venue: arXiv preprint arXiv:2102.06489,

authors:
Aditya Krishna Menon
Ankit Singh Rawat
Sashank J Reddi
Sanjiv Kumar

title: Can gradient 325 clipping mitigate label noise

authors:
Eric Moulines
Francis R Bach

title: Non-asymptotic analysis of stochastic approximation 327 algorithms for machine learning

authors:
Aleksandr Viktorovich Nazin
AS Nemirovsky
Aleksandr Borisovich Tsybakov
AB Judit

venue: Automation 331 and Remote Control,

authors:
Arkadi Nemirovski
Anatoli Juditsky
Guanghui Lan
Alexander Shapiro

title: Robust stochastic 333 approximation approach to stochastic programming

venue: SIAM Journal on optimization,

authors:
Arkadi Semenovich Nemirovsky
David Borisovich Yudin

title: Problem complexity and method 336 efficiency in optimization

venue: Mathematical 338 Programming,

title: A method for solving the convex programming problem with convergence 340 rate o (1/kˆ 2)

venue: In Dokl. akad. nauk Sssr,

authors:
Razvan Pascanu
Tomas Mikolov
Yoshua Bengio

title: On the difficulty of training recurrent 342 neural networks

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
344 Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga
Alban Desmaison
Andreas 345 Kopf
Edward Yang
Zachary DeVito
Martin Raison
Alykhan Tejani
Sasank Chilamkurthy
346 Benoit Steiner
Lu Fang
Junjie Bai
Soumith Chintala

title: Pytorch: An imperative style, high- 347 performance deep learning library

authors:
Herbert Robbins
Sutton Monro

title: A stochastic approximation method. The annals of 351 mathematical statistics, pages

authors:
Umut Şimşekli
Mert Gürbüzbalaban
Thanh Huy Nguyen
Gaël Richard
Levent Sagun

title: On 357 the heavy-tailed theory of stochastic gradient descent for deep neural networks

venue: arXiv preprint

authors:
Umut Simsekli
Levent Sagun
Mert Gurbuzbalaban

title: A tail-index analysis of stochastic 360 gradient noise in deep neural networks

venue: arXiv preprint arXiv:1901.06053,

title: Parametric estimation. finite sample theory

venue: The Annals of Statistics,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
364 Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in neural information 365 processing systems,

authors:
Alex Warstadt
Amanpreet Singh
Samuel R Bowman

title: Neural network acceptability 367 judgments

venue: arXiv preprint arXiv:1805.12471,

authors:
Thomas Wolf
Lysandre Debut
Victor Sanh
Julien Chaumond
Clement Delangue
Anthony 369 Moi
Pierric Cistac
Tim Rault
Rémi Louf
Morgan Funtowicz
Joe Davison
Sam Shleifer
370 Patrick von Platen
Clara Ma
Yacine Jernite
Julien Plu
Canwen Xu
Teven Le Scao
Sylvain 371 Gugger
Mariama Drame
Quentin Lhoest
Alexander M. Rush

title: Transformers: State-of-the- 372 art natural language processing

venue: In Proceedings of the 2020 Conference on Empirical Methods 373 in Natural Language Processing: System Demonstrations,

authors:
Jingzhao Zhang
Tianxing He
Suvrit Sra
Ali Jadbabaie

title: Why gradient clipping accelerates 376 training: A theoretical justification for adaptivity

venue: In International Conference on Learning

text:
Thanks to their practical efficiency and random nature of the data, stochastic1 first-order methods are standard for training large-scale machine learning models.2 Random behavior may cause a particular run of an algorithm to result in a highly3 suboptimal objective value, whereas theoretical guarantees are usually proved4 for the expectation of the objective value. Thus, it is essential to theoretically5 guarantee that algorithms provide small objective residual with high probability.6 Existing methods for non-smooth stochastic convex optimization have complexity7 bounds with the dependence on the confidence level that is either negative-power or8 logarithmic but under an additional assumption of sub-Gaussian (light-tailed) noise9 distribution that may not hold in practice, e.g., in several NLP tasks. In our paper,10 we resolve this issue and derive the first high-probability convergence results with11 logarithmic dependence on the confidence level for non-smooth convex stochastic12 optimization problems with non-sub-Gaussian (heavy-tailed) noise. To derive our13 results, we propose novel stepsize rules for two stochastic methods with gradient14 clipping. Moreover, our analysis works for generalized smooth objectives with15 Hölder-continuous gradients, and for both methods, we provide an extension for16 strongly convex problems. Finally, our results imply that the first (accelerated)17 method we consider also has optimal iteration and oracle complexity in all the18 regimes, and the second one is optimal in the non-smooth setting.19
1 Introduction20
Stochastic first-order optimization methods like SGD [32], Adam [20], and their various modifi-21 cations are extremely popular in solving a number of different optimization problems, especially22 those appearing in statistics [36], machine learning, and deep learning [13]. The success of these23 methods in real-world applications motivates the researchers to investigate theoretical properties24 for the methods and to develop new ones with better convergence guarantees. Typically, stochastic25 methods are analyzed in terms of the convergence in expectation (see [12, 24, 15] and references26 therein), whereas high-probability complexity results are established much rarely. However, as27 illustrated in [14], guarantees in terms of the convergence in expectation have much worse correlation28 with the real behavior of the methods than high-probability convergence guarantees when the noise29 in the stochastic gradients has heavy-tailed distribution.30
Recent studies [35, 34, 41] show that in several popular problems such as training BERT [37] on31 Wikipedia dataset the noise in the stochastic gradients is heavy-tailed. Moreover, in [41], the authors32 justify empirically that in such cases SGD works significantly worse than clipped-SGD [30] and33 Adam. Therefore, it is important to theoretically study the methods’ convergence when the noise is34 heavy-tailed.35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
For convex and strongly convex problems with Lipschitz continuous gradient, i.e., smooth convex and36 strongly convex problems, this question was properly addressed in [25, 3, 14] where the first high-37 probability complexity bounds with logarithmic dependence on the confidence level were derived38 for the stochastic problems with heavy-tailed noise. However, a number of practically important39 problems are non-smooth on the whole space [40, 22]. For example, in deep neural network training,40 the loss function often grows polynomially fast when the norm of the network’s weights goes to41 infinity. Moreover, non-smoothness of the activation functions such as ReLU or loss functions such42 as hinge loss implies the non-smoothness of the whole problem. While being well-motivated by43 practical applications, the existing high-probability convergence guarantees for stochastic first-order44 methods applied to solve non-smooth convex optimization problems with heavy-tailed noise depend45 on the negative power of the confidence level that dramatically increases the number of iterations46 required to obtain high accuracy of the solution with probability close to one. Such a discrepancy in47 the theory between algorithms for stochastic smooth and non-smooth problems leads us to the natural48 question: is it possible to obtain high-probability complexity bounds with logarithmic dependence49 on the confidence level for non-smooth convex stochastic problems with heavy-tailed noise? In this50 paper, we give a positive answer to this question. To achieve this we focus on gradient clipping51 methods [30, 10, 23, 22, 40, 41].52
1.1 Preliminaries53
Before we describe our contributions in detail, we formally state the considered setup.54
Stochastic optimization. We focus on the following problem55
min x∈Rn
f(x), f(x) = Eξ [f(x, ξ)] , (1)
where f(x) is a convex but possibly non-smooth function. Next, we assume that at each point x ∈ Rn56 we have an access to the unbiased estimator∇f(x, ξ) of ∇f(x) with uniformly bounded variance57
Eξ[∇f(x, ξ)] = ∇f(x), Eξ [ ‖∇f(x, ξ)−∇f(x)‖22 ] ≤ σ2, σ > 0. (2)
This assumption on the stochastic oracle is widely used in stochastic optimization literature [11,58 12, 19, 21, 26]. We emphasize that we do not assume that the stochastic gradients have so-called59 “light tails” [21], i.e., sub-Gaussian noise distribution meaning that P{‖∇f(x, ξ)−∇f(x)‖2 > b} ≤60 2 exp(−b2/(2σ2)) for all b > 0.61
Level of smoothness. Finally, we assume that function f has (ν,Mν)-Hölder continuous gradients62 on a compact set Q ⊆ Rn for some ν ∈ [0, 1], Mν > 0 meaning that63
‖∇f(x)−∇f(y)‖2 ≤Mν‖x− y‖ν2 ∀x, y ∈ Q. (3)
When ν = 1 inequality (3) implies M1-smoothness of f , and when ν = 0 we have that ∇f(x)64 has bounded variation which is equivalent to being uniformly bounded. Moreover, when ν = 065 differentiability of f is not needed, and one can assume uniform boundedness of the subgradients of66 f . Linear regression in the case when the noise has generalized Gaussian distribution (Example 4.467 from [2]) serves as a natural example of the situation with ν ∈ (0, 1). Moreover, when (3) holds for68 ν = 0 and ν = 1 simultaneously then it holds for all ν ∈ [0, 1] with Mν ≤M1−ν0 Mν1 [28]. As we69 show in our results, the set Q should contain the ball centered at the solution x∗ of (1) with radius70 2R0 = 2‖x0 − x∗‖2, where x0 is a starting point of the method, i.e., our analysis does not require (3)71 to hold on Rn.72
High-probability convergence. For a given accuracy ε > 0 and confidence level β ∈ (0, 1) we73 are interested in finding ε-solutions of problem (1) with probability at least 1− β, i.e., such x̂ that74 P{f(x̂) − f(x∗) ≤ ε} ≥ 1 − β. For brevity, we will call such (in general, random) points x̂ as75 (ε, β)-solution of (1). Moreover, by high-probability complexity of a stochastic methodM we mean76 the sufficient number of oracle calls, i.e., number of∇f(x, ξ) computations, needed to guarantee that77 the output ofM is an (ε, β)-solution of (1).78
high-probability complexity. Unlike all previous high-probability complexity results in this setup84 with ν < 1 (see Tbl. 1), our result depends only logarithmically on the confidence level β that85 is highly important when β is small. Moreover, up to the difference in logarithmic factors the86 derived complexity guarantees meet the known lower bounds [21, 17] obtained for the problems87 with light-tailed noise. In particular, when ν = 1 we recover accelerated convergence rate [29, 21].88 That is, neglecting the logarithmic factors our results are unimprovable and, surprisingly coincide89 with the best-known results in the “light-tailed case”.90
• We derive the first high-probability complexity bounds for clipped-SGD when the objective91 functions is convex with (ν,Mν)-Hölder continuous gradient and the noise is heavy tailed., i.e., we92 derive93
O ( max { D2,max { D1+ν ,
σ2R20 ε2
} ln D2 +D1+ν
β
}) , D = M 1 1+ν ν R0
ε 1 1+ν
high-probability complexity bound. Interestingly, when ν = 0 the derived bound for clipped-SGD94 has better dependence on the logarithms than the corresponding one for clipped-SSTM. Moreover,95 neglecting the dependence on ε under the logarithm, our bound for clipped-SGD has the same96
• Using restarts technique we extend the obtained results for clipped-SSTM and clipped-SGD to99 the strongly convex case (see Tbl. 2). As in the convex case, the obtained results are superior to all100 previous known results in the general setup we consider.101
• As one of the key contributions of this work, we emphasize that in our theoretical results it is102 sufficient to assume Hölder continuity of the gradients of f only on the ball with radius 2R0 =103 2‖x0 − x∗‖2 and centered at a solution of the problem. This makes our results applicable to much104 larger class of problems than functions with Hölder continuous gradients on Rn, e.g., our analysis105 works even for polynomially growing objectives.106
• To test the performance of the considered methods we conduct several numerical experiments107 on image classification and NLP tasks, and observe that 1) clipped-SSTM and clipped-SGD108 show a comparable performance with SGD on the image classification task, when the noise109 distribution is almost sub-Gaussian, 2) converge much faster than SGD on the NLP task, when the110 noise distribution is heavy-tailed, and 3) clipped-SSTM achieves a comparable performance with111 Adam on the NLP task enjoying both the best known theoretical guarantees and good practical112 performance.113
1.3 Related work114
Light-tailed noise. The theory of high-probability complexity bounds for convex stochastic op-115 timization with light-tailed noise is well-developed. Lower bounds and optimal methods for the116 problems with (ν,Mν)-Hölder continuous gradients are obtained in [26] for ν = 0, and in [11] for117 ν = 1. Up to the logarithmic dependencies these high-probability convergence bounds coincide with118
the corresponding results for the convergence in expectation (see first two rows of Tbl. 1) While not119 being directly derived in the literature, the lower bound for the case when ν ∈ (0, 1) can be obtained120 as a combination of lower bounds in the deterministic [27, 17] and smooth stochastic settings [11].121 The corresponding optimal methods are analyzed in [4, 6] through the lens of inexact oracle.122
Heavy-tailed noise. Unlike in the “light-tailed” case, the first theoretical guarantees with reasonable123 dependence on both the accuracy ε and the confidence level β appeared just recently. In [25], the124 first such results without acceleration [29] were derived for Mirror Descent with special truncation125 technique for smooth (ν = 1) convex problems on a bounded domain, and then were accelerated and126 extended in [14]. For the strongly convex problems the first accelerated high-probability convergence127 guarantees were obtained in [3] for the special method called proxBoost requiring solving auxiliary128 nontrivial problems at each iteration. These bounds were tightened in [14].129
In contrast, for the case when ν < 1 and, in particular, when ν = 0 the best-known high-probability130 complexity bounds suffer from the negative-power dependence on the confidence level β, i.e., have131 a factor 1/βα for some α > 0, that affects the convergence rate dramatically for small enough132 β. Without additional assumptions on the tails these results are obtained via Markov’s inequality133 P{f(x)− f(x∗) > ε} < E[f(x)−f(x∗)]/ε from the guarantees for the convergence in expectation to134 the accuracy εβ, see the results labeled by ♣ in Tbl. 1. Under an additional assumption on noise135 tails that P{‖∇f(x, ξ)−∇f(x)‖22 > sσ2} = O(s−α) for α > 2 these results can be tightened [9]136 when ν = 0 as O ( M20R 2 0 max { ln(β−1)/ε2, (1/βεα) 2/(3α−2) })
without removing the negative-power137 dependence on the confidence level β. Different stepsize policies allow to change the last term in138 max to β− 1 2α−1 ε− 2α 2α−1 without removing the negative-power dependence on β.139
Gradient clipping. The methods based on gradient clipping [30] and normalization [18] are popular140 in different machine learning and deep learning tasks due to their robustness in practice to the noise141 in the stochastic gradients and rapid changes of the objective function [13]. In [40, 22], clipped-GD142 and clipped-SGD are theoretically studied in applications to non-smooth problems that can grow143 polynomially fast when ‖x − x∗‖2 → ∞ showing the superiority of gradient clipping methods144 to the methods without clipping. The results from [40] are obtained for non-convex problems145 with almost surely bounded noise, and in [22], the authors derive the stability and expectation146 convergence guarantees for strongly convex under assumption that the central p-th moment of the147 stochastic gradient is bounded for p ≥ 2. Since the authors of [22] do not provide convergence148 guarantees with explicit dependencies on all important parameters of the problem it complicates direct149 comparison with our results. Nevertheless, convergence guarantees from [22] are sub-linear and are150 given for the convergence in expectation, and, as a consequence, the corresponding high-probability151 convergence results obtained via Markov’s inequality also suffer from negative-power dependence on152 the confidence level. Next, in [41], the authors establish several expectation convergence guarantees153 for clipped-SGD and prove their optimality in the non-convex case under assumption that the central154 α-moment of the stochastic gradient is uniformly bounded, where α ∈ (1, 2]. It turns out that155 clipped-SGD is able to converge even when α < 2, whereas vanilla SGD can diverge in this setting.156
2 Clipped Stochastic Similar Triangles Method157
In this section, we propose a novel variation of Clipped Stochastic Similar Triangles Method [14]158 adjusted to the class of objectives with Hölder continuous gradients (clipped-SSTM, see Alg. 1).159
The method is based on the clipping of the stochastic gradients:160 clip(∇f(x, ξ), λ) = min { 1, λ
‖∇f(x, ξ)‖2
} ∇f(x, ξ) (4)
where ∇f(x, ξ) = 1m ∑m i=1∇f(x, ξi) is a mini-batched stochastic gradient. Gradient clipping161 ensures that the resulting vector has a norm bounded by the clipping level λ. Since the clipped162 stochastic gradient cannot have arbitrary large norm, the clipping helps to avoid unstable behavior of163 the method when the noise is heavy-tailed and the clipping level λ is properly adjusted.164
However, unlike the stochastic gradient, clipped stochastic gradient is a biased estimate of ∇f(x):165 the smaller the clipping level the larger the bias. The biasedness of the clipped stochastic gradient166
Algorithm 1 Clipped Stochastic Similar Triangles Method (clipped-SSTM): case ν ∈ [0, 1] Input: starting point x0, number of iterationsN , batchsizes {mk}Nk=1, stepsize parameter α, clipping
parameter B, Hölder exponent ν ∈ [0, 1]. 1: Set A0 = α0 = 0, y0 = z0 = x0 2: for k = 0, . . . , N − 1 do 3: Set αk+1 = α(k + 1)
2ν 1+ν , Ak+1 = Ak + αk+1, λk+1 = Bαk+1
4: xk+1 = (Akyk+αk+1zk)/Ak+1 5: Draw mini-batch mk of fresh i.i.d. samples ξk1 , . . . , ξ k mk
and compute ∇f(xk+1, ξk) = 1 mk ∑mk i=1∇f(xk+1, ξki )
6: Compute ∇̃f(xk+1, ξk) = clip(∇f(xk+1, ξk), λk+1) using (4) 7: zk+1 = zk − αk+1∇̃f(xk+1, ξk) 8: yk+1 = (Akyk+αk+1zk+1)/Ak+1 9: end for
Output: yN
complicates the analysis of the method. On the other hand, to circumvent the negative effect of167 the heavy-tailed noise on the high-probability convergence one should choose λ to be not too large.168 Therefore, the question on the appropriate choice of the clipping level is highly non-trivial.169
Fortunately, there exists a simple but insightful observation that helps us to obtain the right formula170 for the clipping level λk in clipped-SSTM: if λk is chosen in such a way that ‖∇f(xk)‖2 ≤ λk/2171 with high probability, then for the realizations ∇f(xk+1, ξk) of the mini-batched stochastic gradient172 such that ‖∇f(xk+1, ξk) − ∇f(xk+1)‖2 ≤ λk/2 the clipping is an identity operator. Next, if the173 probability mass of such realizations is big enough then the bias of the clipped stochastic gradient is174 properly bounded that helps to derive needed convergence guarantees. It turns out that the choice175 λk ∼ 1/αk ensures the method convergence with needed rate and high enough probability.176 Guided by this observation we derive the precise expressions for all the parameters of clipped-SSTM177 and derive high-probability complexity bounds for the method. Below we provide a simplified version178 of the main result for clipped-SSTM in the convex case. The complete formulation and the full proof179 of the theorem are deferred to Appendix B.1 (see Thm. B.1).180 Theorem 2.1. Assume that function f is convex and its gradient satisfy (3) with ν ∈ [0, 1], Mν > 0181 on Q = B2R0 = {x ∈ Rn | ‖x − x∗‖2 ≤ 2R0}, where R0 ≥ ‖x0 − x∗‖2. Then there exist such182 a choice of parameters that clipped-SSTM achieves f(yN )− f(x∗) ≤ ε with probability at least183
1− β after O ( D ln 2(1+ν) 1+3ν D
β
) iterations with D = M 2 1+3ν ν R 2(1+ν) 1+3ν 0
ε 2 1+3ν and requires184
O ( max { D ln 2(1+ν) 1+3ν D
β , σ2R20 ε2 ln D β
}) oracle calls. (5)
The obtained result has only logarithmic dependence on the confidence level β and optimal depen-185 dence on the accuracy ε up to logarithmic factors [21, 17] for all ν ∈ [0, 1]. Moreover, we emphasize186 that our result does not require f to have (ν,Mν)-Hölder continuous gradient on the whole space.187 This is because we prove that for the proposed choice of parameters the iterates of clipped-SSTM188 stay inside the ball B2R0 = {x ∈ Rn | ‖x − x∗‖2 ≤ 2R0} with probability at least 1 − β, and,189 as a consequence, Hölder continuity of the gradient is required only inside this ball. In particular,190 this means that the better starting point leads not only to the reduction of R0, but also it can reduce191 Mν . Moreover, our result is applicable to much wider class of functions than the standard class of192 functions with Hölder continuous gradients in Rn, e.g., to the problems with polynomial growth.193 For the strongly convex problems, we consider restarted version of Alg. 1 (R-clipped-SSTM, see194 Alg. 2) and derive high-probability complexity result for this version. Below we provide a simplified195 version of the result. The complete formulation and the full proof of the theorem are deferred to196 Appendix B.2 (see Thm. B.2).197 Theorem 2.2. Assume that function f is µ-strongly convex and its gradient satisfy (3) with ν ∈ [0, 1],198 Mν > 0 on Q = B2R0 = {x ∈ Rn | ‖x− x∗‖2 ≤ 2R0}, where R0 ≥ ‖x0 − x∗‖2. Then there exist199
Algorithm 2 Restarted clipped-SSTM (R-clipped-SSTM): case ν ∈ [0, 1] Input: starting point x0, number of restarts τ , number of steps of clipped-SSTM in restarts {Nt}τt=1,
batchsizes {m1k} N1−1 k=1 , {m2k} N2−1 k=1 , . . . , {mτk} Nτ−1 k=1 , stepsize parameters {αt}τt=1, clipping pa-
rameters {Bt}τt=1, Hölder exponent ν ∈ [0, 1]. 1: x̂0 = x0 2: for t = 1, . . . , τ do 3: Run clipped-SSTM (Alg. 1) for Nt iterations with batchsizes {mtk} Nt−1 k=1 , stepsize parameter
αt, clipping parameter Bt, and starting point x̂t−1. Define the output of clipped-SSTM by x̂t. 4: end for
Output: x̂τ
such a choice of parameters that R-clipped-SSTM achieves f(x̂τ )− f(x∗) ≤ ε with probability at200 least 1− β after201
N̂ = O ( D ln 2(1+ν) 1+3ν D
β
) , D = max {( Mν
µR1−ν0
) 2 1+3ν
ln µR20 ε ,
( M2ν
µ1+νε1−ν
) 1 1+3ν } (6)
iterations of Alg. 1 in total and requires202
O ( max { D ln 2(1+ν) 1+3ν D
β , σ2 µε ln D β
}) oracle calls. (7)
Again, the obtained result has only logarithmic dependence on the confidence level β and, as our203 result in the convex case, it has optimal dependence on the accuracy ε up to logarithmic factors204 depending on β [21, 17] for all ν ∈ [0, 1].205
3 SGD with clipping206
In this section, we present a new variant of clipped-SGD [30] properly adjusted to the class of207 objectives with (ν,Mν)-Hölder continuous gradients (see Alg. 3).208
Algorithm 3 Clipped Stochastic Gradient Descent (clipped-SGD): case ν ∈ [0, 1] Input: starting point x0, number of iterations N , batchsize m, stepsize γ, clipping parameter B > 0.
1: for k = 0, . . . , N − 1 do 2: Draw mini-batch of m fresh i.i.d. samples ξk1 , . . . , ξ k m and compute ∇f(xk+1, ξ
k) = 1 m ∑m i=1∇f(xk+1, ξki )
3: Compute ∇̃f(xk, ξk) = clip(∇f(xk, ξk), λ) using (4) with λ = B/γ 4: xk+1 = xk − γ∇̃f(xk, ξk) 5: end for
Output: x̄N = 1N ∑N−1 k=0 x k
We emphasize that as for clipped-SSTM we use clipping level λ inversely proportional to the stepsize209 γ. Below we provide a simplified version of the main result for clipped-SGD in the convex case. The210 complete formulation and the full proof of the theorem are deferred to Appendix C.1 (see Thm. C.1).211 Theorem 3.1. Assume that function f is convex and its gradient satisfy (3) with ν ∈ [0, 1], Mν > 0212 on Q = B2R0 = {x ∈ Rn | ‖x− x∗‖2 ≤ 2R0}, where R0 ≥ ‖x0 − x∗‖2. Then there exist such a213 choice of parameters that clipped-SGD achieves f(x̄N )− f(x∗) ≤ ε with probability at least 1− β214 after215
O ( max { D2, D1+ν ln D2 +D1+ν
β
}) , D = M 1 1+ν ν R0
ε 1 1+ν
(8)
iterations and requires216 O ( max { D2,max { D1+ν ,
σ2R20 ε2
} ln D2 +D1+ν
β
}) oracle calls. (9)
As all our results in the paper, this result for clipped-SGD has two important features: 1) the217 dependence on the confidence level β is logarithmic and 2) Hölder continuity is required only on218 the ball B2R0 centered at the solution. Moreover, up to the difference in the expressions under219 the logarithm the dependence on ε in the result for clipped-SGD is the same as in the tightest220 known results for non-accelerated SGD-type methods [4, 16]. Finally, we emphasize that for ν < 1221 the logarithmic factors appearing in the complexity bound for clipped-SSTM are worse than the222 corresponding factor in the complexity bound for clipped-SGD. Therefore, clipped-SGD has the223 best known high-probability complexity results in the case when ν = 0 and f is convex.224
For the strongly convex problems, we consider restarted version of Alg. 3 (R-clipped-SGD, see225 Alg. 4) and derive high-probability complexity result for this version. Below we provide a simplified
Algorithm 4 Restarted clipped-SGD (R-clipped-SGD): case ν ∈ [0, 1] Input: starting point x0, number of restarts τ , number of steps of clipped-SGD in restarts {Nt}τt=1,
batchsizes {mt}τk=1, stepsizes {γt}τt=1, clipping parameters {Bt}τt=1 1: x̂0 = x0 2: for t = 1, . . . , τ do 3: Run clipped-SGD (Alg. 3) for Nt iterations with batchsize mt, stepsize γt, clipping parame-
ter Bt, and starting point x̂t−1. Define the output of clipped-SGD by x̂t. 4: end for
Output: x̂τ
226 version of the result. The complete formulation and the full proof of the theorem are deferred to227 Appendix C.2 (see Thm. C.2).228 Theorem 3.2. Assume that function f is µ-strongly convex and its gradient satisfy (3) with ν ∈ [0, 1],229 Mν > 0 on Q = B2R0 = {x ∈ Rn | ‖x− x∗‖2 ≤ 2R0}, where R0 ≥ ‖x0 − x∗‖2. Then there exist230 such a choice of parameters that R-clipped-SGD achieves f(x̄N )− f(x∗) ≤ ε with probability at231 least 1− β after232
O ( max { D 2 1+ν
1 ln µR20 ε ,D 2 1+ν 2 ,max
{ D1 ln
µR20 ε ,D2
} ln D
β }) iterations of Alg. 3 in total and requires233
O ( max { D 2 1+ν
1 ln µR20 ε ,D 2 1+ν 2 ,max
{ D1 ln
µR20 ε ,D2, σ2 µε
} ln D
β
}) oracle calls, where
234
D1 = Mν
µR1−ν0 , D2 =
Mν µ 1+ν 2 ε 1−ν 2 , D = (D 2 1+ν 1 +D1) ln µR20 ε +D2 +D 2 1+ν 2 .
As in the convex case, for ν < 1 the log factors appearing in the complexity bound for R-clipped-235 SSTM are worse than the corresponding factor in the bound for R-clipped-SGD. Thus, R-clipped-236 SGD has the best known high-probability complexity results for strongly convex f and ν = 0.237
4 Numerical experiments238
We tested the performance of the methods on the following problems:239
• BERT fine-tuning on CoLA dataset [38]. We use pretrained BERT from Transformers library [39]240 (bert-base-uncased) and freeze all layers except the last two linear ones.241
• ResNet-18 training on ImageNet-100 (first 100 classes of ImageNet [33]).242
First, we study the noise distribution for both problem as follows: at the starting point we sample243 large enough number of batched stochastic gradients ∇f(x0, ξ1), . . . ,∇f(x0, ξK) with batchsize244 32 and plot the histograms for ‖∇f(x0, ξ1)−∇f(x0)‖2, . . . , ‖∇f(x0, ξK)−∇f(x0)‖2, see Fig. 1.245 As one can see, the noise distribution for BERT + CoLA is substantially non-sub-Gaussian, whereas246 the distribution for ResNet-18 + Imagenet-100 is almost Gaussian.247
Next, we compared 4 different optimizers on these problems: Adam, SGD (with Momentum),248 clipped-SGD (with Momentum and coordinate-wise clipping) and clipped-SSTM (with norm-249 clipping and ν = 1). The results are presented in Fig. 2. We observed that the noise distributions do250
not change significantly along the trajectories of the considered methods, see Appendix D. During251 the hyper-parameters search we compared different batchsizes, emulated via gradient accumulation252 (thus we compare methods with different batchsizes by the number of base batches used). The base253 batchsize was 32 for both problems, stepsizes and clipping levels were tuned. One can find additional254 details regarding our experiments in Appendix D.255
Image classification. On ResNet-18 + ImageNet-100 task, SGD performs relatively well, and256 even ties with Adam (with batchsize of 4× 32) in validation loss. clipped-SSTM (with batchsize of257 2× 32) also ties with Adam and clipped-SGD is not far from them. The results were averaged from258 5 different launches (with different starting points/weight initializations). Since the noise distribution259 is almost Gaussian even vanilla SGD performs well, i.e., gradient clipping is not required. At the260 same time, the clipping does not slow down the convergence significantly.261
Text classification. On BERT + CoLA task, when the noise distribution is heavy-tailed, the methods262 with clipping outperform SGD by a large margin. This result is in good correspondence with the263 derived high-probability complexity bounds for clipped-SGD, clipped-SSTM and the best-known264 ones for SGD. Moreover, clipped-SSTM (with batchsize of 8 × 32) achieves the same loss on265 validation as Adam, and has better accuracy. These results were averaged from 5 different train-val266 splits and 20 launches (with different starting points/weight initializations) for each of the splits, 100267 launches in total.268
References269
[1] George Bennett. Probability inequalities for the sum of independent random variables. Journal270 of the American Statistical Association, 57(297):33–45, 1962.271
[2] Caroline Chaux, Patrick L Combettes, Jean-Christophe Pesquet, and Valérie R Wajs. A varia-272 tional formulation for frame-based inverse problems. Inverse Problems, 23(4):1495–1518, jun273 2007.274
[3] Damek Davis, Dmitriy Drusvyatskiy, Lin Xiao, and Junyu Zhang. From low probability to275 high confidence in stochastic convex optimization. Journal of Machine Learning Research,276 22(49):1–38, 2021.277
[4] Olivier Devolder. Exactness, inexactness and stochasticity in first-order methods for large-scale278 convex optimization. PhD thesis, PhD thesis, 2013.279
[5] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex280 optimization with inexact oracle. Mathematical Programming, 146(1):37–75, 2014.281
[6] Pavel Dvurechensky and Alexander Gasnikov. Stochastic intermediate gradient method for con-282 vex problems with stochastic inexact oracle. Journal of Optimization Theory and Applications,283 171(1):121–145, 2016.284
[7] Kacha Dzhaparidze and JH Van Zanten. On bernstein-type inequalities for martingales. Stochas-285 tic processes and their applications, 93(1):109–117, 2001.286
[8] David A Freedman et al. On tail probabilities for martingales. the Annals of Probability,287 3(1):100–118, 1975.288
[9] Alexander Vladimirovich Gasnikov, Yu E Nesterov, and Vladimir Grigor’evich Spokoiny.289 On the efficiency of a randomized mirror descent algorithm in online optimization problems.290 Computational Mathematics and Mathematical Physics, 55(4):580–596, 2015.291
[10] Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional292 sequence to sequence learning. In Proceedings of the 34th International Conference on Machine293 Learning-Volume 70, pages 1243–1252. JMLR. org, 2017.294
[11] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly295 convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal296 on Optimization, 22(4):1469–1492, 2012.297
[12] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex298 stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.299
[13] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.300 http://www.deeplearningbook.org.301
[14] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with302 heavy-tailed noise via accelerated gradient clipping. In H. Larochelle, M. Ranzato, R. Had-303 sell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems,304 volume 33, pages 15042–15053. Curran Associates, Inc., 2020.305
[15] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter306 Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine307 Learning, pages 5200–5209, 2019.308
[16] Vincent Guigues, Anatoli Juditsky, and Arkadi Nemirovski. Non-asymptotic confidence bounds309 for the optimal value of a stochastic program. Optimization Methods and Software, 32(5):1033–310 1058, 2017.311
[17] Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth312 convex optimization. Journal of Complexity, 31(1):1–14, 2015.313
[18] Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex314 optimization. In Advances in Neural Information Processing Systems, pages 1594–1602, 2015.315
[19] Anatoli Juditsky, Arkadi Nemirovski, et al. First order methods for nonsmooth convex large-316 scale optimization, i: general purpose methods. Optimization for Machine Learning, pages317 121–148, 2011.318
[20] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint319 arXiv:1412.6980, 2014.320
[21] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical321 Programming, 133(1-2):365–397, 2012.322
[22] Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping:323 Beyond lipschitz continuity and smoothness. arXiv preprint arXiv:2102.06489, 2021.324
[23] Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Can gradient325 clipping mitigate label noise? In International Conference on Learning Representations, 2020.326
[24] Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation327 algorithms for machine learning. In Advances in Neural Information Processing Systems, pages328 451–459, 2011.329
[25] Aleksandr Viktorovich Nazin, AS Nemirovsky, Aleksandr Borisovich Tsybakov, and AB Judit-330 sky. Algorithms of robust stochastic optimization based on mirror descent method. Automation331 and Remote Control, 80(9):1607–1627, 2019.332
[26] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic333 approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574–334 1609, 2009.335
[27] Arkadi Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method336 efficiency in optimization. 1983.337
[28] Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematical338 Programming, 152(1-2):381–404, 2015.339
[29] Yurii E Nesterov. A method for solving the convex programming problem with convergence340 rate o (1/kˆ 2). In Dokl. akad. nauk Sssr, volume 269, pages 543–547, 1983.341
[30] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent342 neural networks. In International conference on machine learning, pages 1310–1318, 2013.343
[31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan,344 Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas345 Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy,346 Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-347 performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-348 Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32,349 pages 8024–8035. Curran Associates, Inc., 2019.350
[32] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of351 mathematical statistics, pages 400–407, 1951.352
[33] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng353 Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.354 ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision355 (IJCV), 115(3):211–252, 2015.356
[34] Umut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On357 the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint358 arXiv:1912.00018, 2019.359
[35] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic360 gradient noise in deep neural networks. arXiv preprint arXiv:1901.06053, 2019.361
[36] Vladimir Spokoiny et al. Parametric estimation. finite sample theory. The Annals of Statistics,362 40(6):2877–2909, 2012.363
[37] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez,364 Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information365 processing systems, pages 5998–6008, 2017.366
[38] Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. Neural network acceptability367 judgments. arXiv preprint arXiv:1805.12471, 2018.368
[39] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony369 Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer,370 Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain371 Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-372 art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods373 in Natural Language Processing: System Demonstrations, pages 38–45, Online, October 2020.374 Association for Computational Linguistics.375
[40] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates376 training: A theoretical justification for adaptivity. In International Conference on Learning377 Representations, 2020.378
[41] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi,379 Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In380 H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural381 Information Processing Systems, volume 33, pages 15383–15393. Curran Associates, Inc.,382 2020.383
Checklist384
1. For all authors...385 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s386 contributions and scope? [Yes]387 (b) Did you describe the limitations of your work? [Yes] Section 1.1 describes all assump-388 tions that we use389 (c) Did you discuss any potential negative societal impacts of your work? [No] Our results390 are primarily theoretical, therefore, such a discussion is not applicable.391 (d) Have you read the ethics review guidelines and ensured that your paper conforms to392 them? [Yes]393 2. If you are including theoretical results...394
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section 1.1395 describes all assumptions that we use.396
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix B and C397 include the complete proofs of all the results we derive.398
3. If you ran experiments...399 (a) Did you include the code, data, and instructions needed to reproduce the main experi-400 mental results (either in the supplemental material or as a URL)? [Yes] See our code in401 the supplementary material.402
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they403 were chosen)? [Yes] See Appendix D.404
(c) Did you report error bars (e.g., with respect to the random seed after running exper-405 iments multiple times)? [No] Instead of it, we show the averaged trajectories of the406 methods’ convergence.407
(d) Did you include the total amount of compute and the type of resources used (e.g., type408 of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix D.409
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...410 (a) If your work uses existing assets, did you cite the creators? [Yes]411 (b) Did you mention the license of the assets? [No] We use only publicly available412 resources.413
(c) Did you include any new assets either in the supplemental material or as a URL? [No]414 (d) Did you discuss whether and how consent was obtained from people whose data you’re415 using/curating? [No] We use only publicly available resources.416 (e) Did you discuss whether the data you are using/curating contains personally identifiable417 information or offensive content? [N/A]418 5. If you used crowdsourcing or conducted research with human subjects...419
(a) Did you include the full text of instructions given to participants and screenshots, if420 applicable? [N/A]421
(b) Did you describe any potential participant risks, with links to Institutional Review422 Board (IRB) approvals, if applicable? [N/A]423
(c) Did you include the estimated hourly wage paid to participants and the total amount424 spent on participant compensation? [N/A]425

title: Gradient Clipping Helps in Non-Smooth Stochastic Optimization with Heavy-Tailed Noise


summaries: This paper studies long-horizon time series forecasting where the historical input length is shorter than the forecast horizon, i.e, output length. This approach extends the transformer by replacing the self-attention unit by autocorrelation and decomposition units.  The autocorrelation unit chooses the top $k$ highly correlated time lags from $L$ time lags between the query and key embeddings of a time series of length $L$. The normalized correlation of lag j between the query and key embeddings multiplied by the j-item rotated value embedding.  The decomposition block decomposes a time series to seasonal and trend components. The trend component is defined by using an average pooling, which is an average value of the neighbouring values. And the seasonal is then defined as the difference between the (observed) time series and the trend component. The proposed approach autocorrelation unit is compared with standard attention, logsparse attention, LSH and probsparse attention.

summaries: This paper studies the problem of long-term forecasting for time series. There are two challenges: (1) it is difficult to directly study the entangled temporal dependencies for long time series; (2) the traditional self-attention mechanism in Transformer is computationally expensive. To address these two problems, the paper proposes a novel Autoformer with a novel auto-correlation mechanism and a series decomposition module.

summaries: This paper presents Autoformer to perform long-term time series forecasting. The key idea is to leverage an auto-correlation mechanism to discover the sub-series similarity based on the series periodicity and aggregate similar sub-series from underlying periods. The experiment results on several datasets showed the effectiveness of the proposed method.

summaries: This paper focuses on the long-term forecasting problem of time series. This work introduces the traditional idea of decomposing time series into seasonality and trend-cycle components into deep Transformer architecture. This work also proposes an auto-correlation mechanism that replaces the original self-attention in Transformers.  Further, they improve the computation efficiency by computing power spectral density. Experiments on several datasets show that the proposed method achieves better performance compared to SOTA methods.

summaries: This paper introduces a new approach for long-term time-series forecasting that is based on decomposition and auto-correlation. Essentially, the authors define a series decomoposition block which extracts the mean (trend-cyclical) and subtracts it from the series, obtaining the seasonal part. In addition, the authors design an auto-correlation component that identifies local structures across periods. The method is evaluated on six benchmark datasets and in comparison to several baseline approaches. The presented results show improvements over existing work.

abstractText: Extending the forecasting time is a critical demand for real applications, such as extreme weather early warning and long-term energy consumption planning. This paper studies the long-term forecasting problem of time series. Prior Transformerbased models adopt various self-attention mechanisms to discover the long-range dependencies. However, intricate temporal patterns of the long-term future prohibit the model from finding reliable dependencies. Also, Transformers have to adopt the sparse versions of point-wise self-attentions for long series efficiency, resulting in the information utilization bottleneck. Going beyond Transformers, we design Autoformer as a novel decomposition architecture with an Auto-Correlation mechanism. We break with the pre-processing convention of series decomposition and renovate it as a basic inner block of deep models. This design empowers Autoformer with progressive decomposition capacities for complex time series. Further, inspired by the stochastic process theory, we design the Auto-Correlation mechanism based on the series periodicity, which conducts the dependencies discovery and representation aggregation at the sub-series level. Auto-Correlation outperforms self-attention in both efficiency and accuracy. In long-term forecasting, Autoformer yields stateof-the-art accuracy, with a 38% relative improvement on six benchmarks, covering five practical applications: energy, traffic, economics, weather and disease. Code is available at this repository: https://github.com/thuml/Autoformer.

authors:
O. Anderson
M. Kendall

title: Time-series. 2nd edn

venue: J. R. Stat. Soc. (Series D),

authors:
Reza Asadi
Amelia C Regan

title: A spatio-temporal decomposition based deep neural network for time series forecasting

venue: Appl. Soft Comput.,

authors:
Shaojie Bai
J Zico Kolter
Vladlen Koltun

title: An empirical evaluation of generic convolutional and recurrent networks for sequence modeling

venue: arXiv preprint arXiv:1803.01271,

authors:
Anastasia Borovykh
Sander Bohte
Cornelis W Oosterlee

title: Conditional time series forecasting with convolutional neural networks

venue: arXiv preprint arXiv:1703.04691,

authors:
G.E.P. Box
Gwilym M. Jenkins

title: Time series analysis, forecasting and control

authors:
George EP Box
Gwilym M Jenkins

title: Some recent advances in forecasting and control

venue: J. R. Stat. Soc. (Series-C),

authors:
Tom Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared D Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell
Sandhini Agarwal
Ariel Herbert-Voss
Gretchen Krueger
Tom Henighan
Rewon Child
Aditya Ramesh
Daniel Ziegler
Jeffrey Wu
Clemens Winter
Chris Hesse
Mark Chen
Eric Sigler
Mateusz Litwin
Scott Gray
Benjamin Chess
Jack Clark
Christopher Berner
Sam McCandlish
Alec Radford
Ilya Sutskever
Dario Amodei

title: Language models are few-shot learners

venue: NeurIPS,

title: The analysis of time series: an introduction

authors:
Renyi Chen
Molei Tao

title: Data-driven prediction of general hamiltonian dynamics via learning exactlysymplectic maps

authors:
Emmanuel de Bézenac
Syama Sundar Rangapuram
Konstantinos Benidis
Michael Bohlke-Schneider
Richard Kurle
Lorenzo Stella
Hilaf Hasson
Patrick Gallinari
Tim Januschowski

title: Normalizing kalman filters for multivariate time series analysis

authors:
J. Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: In NAACL-HLT,

authors:
Alexey Dosovitskiy
Lucas Beyer
Alexander Kolesnikov
Dirk Weissenborn
Xiaohua Zhai
Thomas Unterthiner
Mostafa Dehghani
Matthias Minderer
Georg Heigold
Sylvain Gelly
Jakob Uszkoreit
Neil Houlsby

title: An image is worth 16x16 words: Transformers for image recognition at scale

venue: In ICLR,

authors:
S. Hochreiter
J. Schmidhuber

title: Long short-term memory

venue: Neural Comput.,

authors:
Rob J Hyndman
George Athanasopoulos

title: Forecasting: principles and practice

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Nikita Kitaev
Lukasz Kaiser
Anselm Levskaya

title: Reformer: The efficient transformer

authors:
Richard Kurle
Syama Sundar Rangapuram
Emmanuel de Bézenac
Stephan Günnemann
Jan Gasthaus

title: Deep rao-blackwellised particle filters for time series forecasting

authors:
Guokun Lai
Wei-Cheng Chang
Yiming Yang
Hanxiao Liu

title: Modeling long-and short-term temporal patterns with deep neural networks

venue: In SIGIR,

authors:
Shiyang Li
Xiaoyong Jin
Yao Xuan
Xiyou Zhou
Wenhu Chen
Yu-Xiang Wang
Xifeng Yan

title: Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting

authors:
Ze Liu
Yutong Lin
Yue Cao
Han Hu
Yixuan Wei
Zheng Zhang
Stephen Lin
Baining Guo

title: Swin transformer: Hierarchical vision transformer using shifted windows

venue: In ICCV,

authors:
Danielle C Maddix
Yuyang Wang
Alex Smola

title: Deep factors with gaussian processes for forecasting

venue: arXiv preprint arXiv:1812.00098,

authors:
Boris N Oreshkin
Dmitri Carpov
Nicolas Chapados
Yoshua Bengio

title: N-BEATS: Neural basis expansion analysis for interpretable time series forecasting

authors:
Athanasios Papoulis
H Saunders

title: Probability, random variables and stochastic processes

authors:
Adam Paszke
S. Gross
Francisco Massa
A. Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Z. Lin
N. Gimelshein
L. Antiga
Alban Desmaison
Andreas Köpf
Edward Yang
Zach DeVito
Martin Raison
Alykhan Tejani
Sasank Chilamkurthy
Benoit Steiner
Lu Fang
Junjie Bai
Soumith Chintala

title: Pytorch: An imperative style, high-performance deep learning library

authors:
Syama Sundar Rangapuram
Matthias W Seeger
Jan Gasthaus
Lorenzo Stella
Yuyang Wang
Tim Januschowski

title: Deep state space models for time series forecasting

authors:
Cleveland Robert
C William
Terpenning Irma

title: STL: A seasonal-trend decomposition procedure based on loess

venue: J. Off. Stat,

authors:
David Salinas
Valentin Flunkert
Jan Gasthaus
Tim Januschowski

title: DeepAR: Probabilistic forecasting with autoregressive recurrent networks

venue: Int. J. Forecast.,

authors:
Rajat Sen
Hsiang-Fu Yu
Inderjit S. Dhillon

title: Think globally, act locally: A deep neural network approach to high-dimensional time series forecasting

authors:
Shun-Yao Shih
Fan-Keng Sun
Hung-yi Lee

title: Temporal pattern attention for multivariate time series forecasting

authors:
Huan Song
Deepta Rajan
Jayaraman Thiagarajan
Andreas Spanias

title: Attend and diagnose: Clinical time series analysis using attention models

venue: In AAAI,

authors:
Antti Sorjamaa
Jin Hao
Nima Reyhani
Yongnan Ji
Amaury Lendasse

title: Methodology for long-term prediction of time series

authors:
Sean J Taylor
Benjamin Letham

title: Forecasting at scale

venue: Am. Stat.,

authors:
Aäron van den Oord
S. Dieleman
H. Zen
K. Simonyan
Oriol Vinyals
A. Graves
Nal Kalchbrenner
A. Senior
K. Kavukcuoglu

title: Wavenet: A generative model for raw audio

venue: SSW,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Ł ukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Ruofeng Wen
Kari Torkkola
Balakrishnan Narayanaswamy
Dhruv Madeka

title: A multi-horizon quantile recurrent forecaster

title: Generalized harmonic analysis

venue: Acta Math,

authors:
Sifan Wu
Xi Xiao
Qianggang Ding
Peilin Zhao
Ying Wei
Junzhou Huang

title: Adversarial sparse transformer for time series forecasting

authors:
Q. Yao
D. Song
H. Chen
C. Wei
G.W. Cottrell

title: A dual-stage attention-based recurrent neural network for time series prediction

authors:
Rose Yu
Stephan Zheng
Anima Anandkumar
Yisong Yue

title: Long-term forecasting using tensor-train rnns

venue: arXiv preprint arXiv:1711.00073,

authors:
Haoyi Zhou
Shanghang Zhang
Jieqi Peng
Shuai Zhang
Jianxin Li
Hui Xiong
Wancai Zhang

title: Informer: Beyond efficient transformer for long sequence time-series forecasting

heading: 1 Introduction

text:
Time series forecasting has been widely used in energy consumption, traffic and economics planning, weather and disease propagation forecasting. In these real-world applications, one pressing demand is to extend the forecast time into the far future, which is quite meaningful for the long-term planning and early warning. Thus, in this paper, we study the long-term forecasting problem of time series, characterizing itself by the large length of predicted time series. Recent deep forecasting models [41, 17, 20, 28, 23, 29, 19, 35] have achieved great progress, especially the Transformer-based models. Benefiting from the self-attention mechanism, Transformers obtain great advantage in modeling long-term dependencies for sequential data, which enables more powerful big models [7, 11].
However, the forecasting task is extremely challenging under the long-term setting. First, it is unreliable to discover the temporal dependencies directly from the long-term time series because the dependencies can be obscured by entangled temporal patterns. Second, canonical Transformers with self-attention mechanisms are computationally prohibitive for long-term forecasting because of the quadratic complexity of sequence length. Previous Transformer-based forecasting models [41, 17, 20] mainly focus on improving self-attention to a sparse version. While performance is significantly improved, these models still utilize the point-wise representation aggregation. Thus, in the process of efficiency improvement, they will sacrifice the information utilization because of the sparse point-wise connections, resulting in a bottleneck for long-term forecasting of time series.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
To reason about the intricate temporal patterns, we try to take the idea of decomposition, which is a standard method in time series analysis [1, 27]. It can be used to process the complex time series and extract more predictable components. However, under the forecasting context, it can only be used as the pre-processing of past series because the future is unknown [15]. This common usage limits the capabilities of decomposition and overlooks the potential future interactions among decomposed components. Thus, we attempt to go beyond pre-processing usage of decomposition and propose a generic architecture to empower the deep forecasting models with immanent capacity of progressive decomposition. Further, decomposition can ravel out the entangled temporal patterns and highlight the inherent properties of time series [15]. Benefiting from this, we try to take advantage of the series periodicity to renovate the point-wise connection in self-attention. We observe that the sub-series at the same phase position among periods often present similar temporal processes. Thus, we try to construct a series-level connection based on the process similarity derived by series periodicity.
Based on the above motivations, we propose an original Autoformer in place of the Transformers for long-term time series forecasting. Autoformer still follows residual and encoder-decoder structure but renovates Transformer into a decomposition forecasting architecture. By embedding our proposed decomposition blocks as the inner operators, Autoformer can progressively separate the long-term trend information from predicted hidden variables. This design allows our model to alternately decompose and refine the intermediate results during the forecasting procedure. Inspired by the stochastic process theory [8, 24], Autoformer introduces an Auto-Correlation mechanism in place of self-attention, which discovers the sub-series similarity based on the series periodicity and aggregates similar sub-series from underlying periods. This series-wise mechanism achieves O(L logL) complexity for length-L series and breaks the information utilization bottleneck by expanding the point-wise representation aggregation to sub-series level. Autoformer achieves the state-of-the-art accuracy on six benchmarks. The contributions are summarized as follows:
• To tackle the intricate temporal patterns of the long-term future, we present Autoformer as a decomposition architecture and design the inner decomposition block to empower the deep forecasting model with immanent progressive decomposition capacity.
• We propose an Auto-Correlation mechanism with dependencies discovery and information aggregation at the series level. Our mechanism is beyond previous self-attention family and can simultaneously benefit the computation efficiency and information utilization.
• Autoformer achieves a 38% relative improvement under the long-term setting on six benchmarks, covering five real-world applications: energy, traffic, economics, weather and disease.

heading: 2 Related Work

heading: 2.1 Models for Time Series Forecasting

text:
Due to the immense importance of time series forecasting, various models have been well developed. Many time series forecasting methods start from the classic tools [32, 9]. ARIMA [6, 5] tackles the forecasting problem by transforming the non-stationary process to stationary through differencing. The filtering method is also introduced for series forecasting [18, 10]. Besides, recurrent neural networks (RNNs) models are used to model the temporal dependencies for time series [36, 26, 40, 22]. DeepAR [28] combines autoregressive methods and RNNs to model the probabilistic distribution of future series. LSTNet [19] introduces convolutional neural networks (CNNs) with recurrent-skip connections to capture the short-term and long-term temporal patterns. Attention-based RNNs [39, 30, 31] introduce the temporal attention to explore the long-range dependencies for prediction. Also, many works based on temporal convolution networks (TCN) [34, 4, 3, 29] attempt to model the temporal causality with the causal convolution. These deep forecasting models mainly focus on the temporal relation modeling by recurrent connections, temporal attention or causal convolution.
Recently, Transformers [35, 38] based on the self-attention mechanism shows great power in sequential data, such as natural language processing [11, 7], audio processing [14] and even computer vision [12, 21]. However, applying self-attention to long-term time series forecasting is computationally prohibitive because of the quadratic complexity of sequence length L in both memory and time. LogTrans [20] introduces the local convolution to Transformer and proposes the LogSparse attention to select time steps following the exponentially increasing intervals, which reduces the complexity to O(L(logL)2). Reformer [17] presents the local-sensitive hashing (LSH) attention and reduces the complexity to O(L logL). Informer [41] extends Transformer with KL-divergence based ProbSparse
attention and also achieves O(L logL) complexity. Note that these methods are based on the vanilla Transformer and try to improve the self-attention mechanism to a sparse version, which still follows the point-wise dependency and aggregation. In this paper, our proposed Auto-Correlation mechanism is based on the inherent periodicity of time series and can provide series-wise connections.

heading: 2.2 Decomposition of Time Series

text: As a standard method in time series analysis, time series decomposition [1, 27] deconstructs a time series into several components, each representing one of the underlying categories of patterns that are more predictable. It is primarily useful for exploring historical changes over time. For the forecasting tasks, decomposition is always used as the pre-processing of historical series before predicting future series [15, 2], such as Prophet [33] with trend-seasonality decomposition and N-BEATS [23] with basis expansion and DeepGLO [29] with matrix decomposition. However, such pre-processing is limited by the plain decomposition effect of historical series and overlooks the hierarchical interaction between the underlying patterns of series in the long-term future. This paper takes the decomposition idea from a new progressive dimension. Our Autoformer harnesses the decomposition as an inner block of deep models, which can progressively decompose the hidden series throughout the whole forecasting process, including both the past series and the predicted intermediate results.

heading: 3 Autoformer

text: The time series forecasting problem is to predict the most probable length-O series in the future given the past length-I series, denoting as input-I-predict-O. The long-term forecasting setting is to predict the long-term future, i.e. larger O. As aforementioned, we have highlighted the difficulties of long-term series forecasting: handling intricate temporal patterns and breaking the bottleneck of computation efficiency and information utilization. To tackle these two challenges, we introduce the decomposition as a builtin block to the deep forecasting model and propose Autoformer as a decomposition architecture. Besides, we design the Auto-Correlation mechanism to discover the period-based dependencies and aggregate similar sub-series from underlying periods.

heading: 3.1 Decomposition Architecture

text:
We renovate Transformer [35] to a deep decomposition architecture (Figure 1), including the inner series decomposition block, Auto-Correlation mechanism, and corresponding Encoder and Decoder.
Series decomposition block To learn with the complex temporal patterns in long-term forecasting context, we take the idea of decomposition [1, 27], which can separate the series into trend-cyclical and seasonal parts. These two parts reflect the long-term progression and the seasonality of the series respectively. However, directly decomposing is unrealizable for future series because the future is just unknown. To tackle this dilemma, we present a series decomposition block as an inner operation of Autoformer (Figure 1), which can extract the long-term stationary trend from predicted intermediate hidden variables progressively. Concretely, we adapt the moving average to smooth out periodic fluctuations and highlight the long-term trends. For length-L input series X ∈ RL×d, the process is:
Xt = AvgPool(Padding(X )) Xs = X − Xt,
(1)
where Xs,Xt ∈ RL×d denote the seasonal and the extracted trend-cyclical part respectively. We adopt the AvgPool(·) for moving average with the padding operation to keep the series length unchanged. We use Xs,Xt = SeriesDecomp(X ) to summarize above equations, which is a model inner block. Model inputs The inputs of encoder part are the past I time stepsXen ∈ RI×d. As a decomposition architecture (Figure 1), the input of Autoformer decoder contains both the seasonal part Xdes ∈ R( I2+O)×d and trend-cyclical part Xdet ∈ R( I 2+O)×d to be refined. Each initialization consists of two parts: the component decomposed from the latter half of encoder’s input Xen with length I2 to provide recent information, placeholders with length O filled by scalars. It’s formulized as follows:
Xens,Xent = SeriesDecomp(Xen I 2 :I )
Xdes = Concat(Xens,X0) Xdet = Concat(Xent,XMean),
(2)
where Xens,Xent ∈ R I 2×d denote the seasonal and trend-cyclical parts of Xen respectively, and X0,XMean ∈ RO×d denote the placeholders filled with zero and the mean of Xen respectively.
Encoder As shown in Figure 1, the encoder focuses on the seasonal part modeling. The output of the encoder contains the past seasonal information and will be used as the cross information to help the decoder refine prediction results. Suppose we have N encoder layers. The overall equations for l-th encoder layer are summarized as X len = Encoder(X l−1en ). Details are shown as follows:
Sl,1en , = SeriesDecomp ( Auto-Correlation(X l−1en ) + X l−1en ) Sl,2en , = SeriesDecomp ( FeedForward(Sl,1en ) + Sl,1en ) ,
(3)
where “ ” is the eliminated trend part. X len = Sl,2en , l ∈ {1, · · · , N} denotes the output of l-th encoder layer and X 0en is the embedded Xen. Sl,ien , i ∈ {1, 2} represents the seasonal component after the i-th series decomposition block in the l-th layer respectively. We will give detailed description of Auto-Correlation(·) in the next section, which can seamlessly replace the self-attention.
Decoder The decoder contains two parts: the accumulation structure for trend-cyclical components and the stacked Auto-Correlation mechanism for seasonal components (Figure 1). Each decoder layer contains the inner Auto-Correlation and encoder-decoder Auto-Correlation, which can refine the prediction and utilize the past seasonal information respectively. Note that the model extracts the potential trend from the intermediate hidden variables during the decoder, allowing Autoformer to progressively refine the trend prediction and eliminate interference information for period-based dependencies discovery in Auto-Correlation. Suppose there are M decoder layers. With the latent variable XNen from the encoder, the equations of l-th decoder layer can be summarized as X lde = Decoder(X l−1de ,XNen). The decoder can be formalized as follows:
Sl,1de , T l,1 de = SeriesDecomp ( Auto-Correlation(X l−1de ) + X l−1de ) Sl,2de , T l,2 de = SeriesDecomp ( Auto-Correlation(Sl,1de ,XNen) + S l,1 de
) Sl,3de , T l,3 de = SeriesDecomp ( FeedForward(Sl,2de ) + S l,2 de
) T lde = T l−1de +Wl,1 ∗ T l,1 de +Wl,2 ∗ T l,2 de +Wl,3 ∗ T l,3 de ,
(4)
where X lde = Sl,3de , l ∈ {1, · · · ,M} denotes the output of l-th decoder layer. X 0de is embedded from Xdes for deep transform and T 0de = Xdet is for accumulation. Sl,ide , T l,i de , i ∈ {1, 2, 3} represent the seasonal component and trend-cyclical component after the i-th series decomposition block in the l-th layer respectively. Wl,i, i ∈ {1, 2, 3} represents the projector for the i-th extracted trend T l,ide .
… L
Q K V
FFT
x
FFT
Inverse FFT
Time Delay Agg
Linear Linear Linear
Linear
Concat
LxC SxC SxC
LxCx2
LxC
LxC
LxCx2 ConjugateLxCx2
LxC
Resize Resize
LxC
Roll( )
Roll( )
Roll( )
x
x
x
…
Fu sio n Time Delay Top k kxC SoftMax
test
haixu wu
April 2021
1 Introduction
⌧1 ⌧2 ⌧k R(⌧1) R(⌧2) R(⌧k)
1
test
haixu wu
April 2021
1 Introduction
⌧1 ⌧2 ⌧k R(⌧1) R(⌧2) R(⌧k)
1
test
haixu wu
April 2021
1 Introduction
⌧1 2
⌧k ⌧1) ⌧2) R(⌧k)
1
test
haixu wu
April 2021
1 Introduction
⌧1 ⌧2 ⌧k R(⌧1) R(⌧2) R(⌧k)
1
test
haixu wu
April 2021
1 Introduction
⌧1 ⌧2 ⌧k
(⌧1) R(⌧2) R(⌧k)
1
test
haixu wu
April 2021
1 Introduction
⌧1 ⌧2 ⌧k R(⌧1) R(⌧2) R(⌧k)
1
Figure 2: Auto-Correlation (left) and Time Delay Aggregation (right). We utilize the Fast Fourier Transform to calculate the autocorrelationR(τ), which reflects the time-delay similarities. Then the similar sub-processes are rolled to the same index based on selected delay τ and aggregated byR(τ).
The final prediction is the sum of the two refined decomposed components, asWS ∗ XMde + T Mde , whereWS is to project the deep transformed seasonal component XMde to the target dimension.

heading: 3.2 Auto-Correlation Mechanism

text:
As shown in Figure 2, we propose the Auto-Correlation mechanism with series-wise connections to expand the information utilization. Auto-Correlation discovers the period-based dependencies by calculating the series autocorrelation and aggregates similar sub-series by time delay aggregation.
Period-based dependencies It is observed that the same phase position among periods naturally provides similar sub-processes. Inspired by the stochastic process theory [8, 24], for a real discretetime process {Xt}, we can obtain the autocorrelationRXX (τ) by the following equations:
RXX (τ) = lim L→∞
1
L L∑ t=1 XtXt−τ . (5)
RXX (τ) reflects the time-delay similarity between {Xt} and its τ lag series {Xt−τ}. As shown in Figure 2, we use the autocorrelationR(τ) as the unnormalized confidence of estimated period length τ . Then, we choose the most possible k period lengths τ1, · · · , τk. The period-based dependencies are derived by the above estimated periods and can be weighted by the corresponding autocorrelation.
Time delay aggregation The period-based dependencies connect the sub-series among estimated periods. Thus, we present the time delay aggregation block (Figure 2), which can roll the series based on selected time delay τ1, · · · , τk. This operation can align similar sub-series that are at the same phase position of estimated periods, which is different from the point-wise dot-product aggregation in self-attention family. Finally, we aggregate the sub-series by softmax normalized confidences.
For the single head situation and time series X with length-L, after the projector, we get queryQ, key K and value V . Thus, it can replace self-attention seamlessly. The Auto-Correlation mechanism is:
τ1, · · · , τk = argTopk τ∈{1,··· ,L} (RQ,K(τ))
R̂Q,K(τ1), · · · , R̂Q,K(τk) = SoftMax (RQ,K(τ1), · · · ,RQ,K(τk))
Auto-Correlation(Q,K,V) = k∑ i=1 Roll(V, τi)R̂Q,K(τi),
(6)
where arg Topk(·) is to get the arguments of the Topk autocorrelations and let k = bc× logLc, c is a hyper-parameter. RQ,K is autocorrelation between series Q and K. Roll(X , τ) represents the operation to X with time delay τ , during which elements that are shifted beyond the first position are re-introduced at the last position. For the encoder-decoder Auto-Correlation (Figure 1), K,V are from the encoder XNen and will be resized to length-O, Q is from the previous block of the decoder.
For the multi-head version used in Autoformer, with hidden variables of dmodel channels, h heads, the query, key and value for i-th head are Qi,Ki,Vi ∈ RL× dmodel h , i ∈ {1, · · · , h}. The process is:
MultiHead(Q,K,V) =Woutput ∗ Concat(head1, · · · ,headh) where headi = Auto-Correlation(Qi,Ki,Vi).
(7)
Efficient computation For period-based dependencies, these dependencies point to sub-processes at the same phase position of underlying periods and are inherently sparse. Here, we select the most possible delays to avoid picking the opposite phases. Because we aggregate O(logL) series whose length is L, the complexity of Equations 6 and 7 is O(L logL). For the autocorrelation computation (Equation 5), given time series {Xt},RXX (τ) can be calculated by Fast Fourier Transforms (FFT) based on the Wiener–Khinchin theorem [37]:
SXX (f) = F (Xt)F∗ (Xt) = ∫ ∞ −∞ Xte−i2πtfdt ∫ ∞ −∞ Xte−i2πtfdt
RXX (τ) = F−1 (SXX (f)) = ∫ ∞ −∞ SXX (f)ei2πfτdf,
(8)
where τ ∈ {1, · · · , L}, F denotes the FFT and F−1 is its inverse. ∗ denotes the conjugate operation and SXX (f) is in the frequency domain. Note that the series autocorrelation of all lags in {1, · · · , L} can be calculated at once by FFT. Thus, Auto-Correlation achieves the O(L logL) complexity.
Auto-Correlation vs. self-attention family Different from the point-wise self-attention family, Auto-Correlation presents the series-wise connections (Figure 3). Concretely, for the temporal dependencies, we find the dependencies among sub-series based on the periodicity. In contrast, the self-attention family only calculates the relation between scattered points. Though some selfattentions [20, 41] consider the local information, they only utilize this to help point-wise dependencies discovery. For the information aggregation, we adopt the time delay block to aggregate the similar sub-series from underlying periods. In contrast, self-attentions aggregate the selected points by dot-product. Benefiting from the inherent sparsity and sub-series-level representation aggregation, Auto-Correlation can simultaneously benefit the computation efficiency and information utilization.

heading: 4 Experiments

text:
We extensively evaluate the proposed Autoformer on six real-world benchmarks, covering five mainstream time series forecasting applications: energy, traffic, economics, weather and disease.
Datasets Here is a description of the six experiment datasets: (1) ETT [41] dataset contains the data collected from electricity transformers, including load and oil temperature that are recorded every
15 minutes between July 2016 and July 2018. (2) Electricity1 dataset contains the hourly electricity consumption of 321 customers from 2012 to 2014. (3) Exchange [19] records the daily exchange rates of eight different countries ranging from 1990 to 2016. (4) Traffic2 is a collection of hourly data from California Department of Transportation, which describes the road occupancy rates measured by different sensors on San Francisco Bay area freeways. (5) Weather3 is recorded every 10 minutes for 2020 whole year, which contains 21 meteorological indicators, such as air temperature, humidity, etc. (6) ILI4 includes the weekly recorded influenza-like illness (ILI) patients data from Centers for Disease Control and Prevention of the United States between 2002 and 2021, which describes the ratio of patients seen with ILI and the total number of the patients. We follow standard protocol and split all datasets into training, validation and test set in chronological order by the ratio of 6:2:2 for the ETT dataset and 7:1:2 for the other datasets.
Implementation details Our method is trained with L2 loss, using the ADAM [16] optimizer with an initial learning rate of 10−4. Batch size is set to 32. The training process is early stopped within 10 epochs. All experiments are repeated three times, implemented in PyTorch [25] and conducted on a single NVIDIA TITAN RTX 24GB GPUs. The hyper-parameter c of Auto-Correlation is in the range of 1 to 3 to trade off performance and efficiency. See supplementary materials for standard deviations and sensitivity analysis. Autoformer contains 2 encoder layers and 1 decoder layer.
Baselines We include 10 baseline methods. For the multivariate setting, we select three latest stateof-the-art transformer-based models: Informer [41], Reformer [17], LogTrans [20], two RNN-based models: LSTNet [19], LSTM [13] and CNN-based TCN [3] as baselines. For the univariate setting, we include more competitive baselines: N-BEATS[23], DeepAR [28], Prophet [33] and ARMIA [1].
1https://archive.ics.uci.edu/ml/datasets/ElectricityLoadDiagrams20112014 2http://pems.dot.ca.gov 3https://www.bgc-jena.mpg.de/wetter/ 4https://gis.cdc.gov/grasp/fluview/fluportaldashboard.html

heading: 4.1 Main Results

text:
To compare performances under different future horizons, we fix the input length and evaluate models with a wide range of prediction lengths: 96, 192, 336, 720. This setting precisely meets the definition of long-term forecasting. Here are results on both the multivariate and univariate settings.
Multivariate results As for the multivariate setting, Autoformer achieves the consistent state-ofthe-art performance in all benchmarks and all prediction length settings (Table 1). Especially, under the input-96-predict-336 setting, compared to previous state-of-the-art results, Autoformer gives 74% (1.334→0.339) MSE reduction in ETT, 18% (0.280→0.231) in Electricity, 61% (1.357→0.509) in Exchange, 15% (0.733→0.622) in Traffic and 21% (0.455→0.359) in Weather. For the input36-predict-60 setting of ILI, Autoformer makes 43% (4.882→2.770) MSE reduction. Overall, Autoformer yields a 38% averaged MSE reduction among above settings. Note that Autoformer still provides remarkable improvements in the Exchange dataset that is without obvious periodicity. See supplementary materials for detailed showcases. Besides, we can also find that the performance of Autoformer changes quite steadily as the prediction length O increases. It means that Autoformer retains better long-term robustness, which is meaningful for real-world practical applications, such as weather early warning and long-term energy consumption planning.
Univariate results We list the univariate results of two typical datasets in Table 2. Under the comparison with extensive baselines, our Autoformer still achieves state-of-the-art performance for the long-term forecasting tasks. In particular, for the input-96-predict-336 setting, our model achieves 14% (0.180→0.145) MSE reduction on the ETT dataset with obvious periodicity. For the Exchange dataset without obvious periodicity, Autoformer surpasses other baselines by 17% (0.611→0.508) and shows greater long-term forecasting capacity. Also, we find that ARIMA [1] performs best in the input-96-predict-96 setting of the Exchange dataset but fails in the long-term setting. This situation of ARIMA can be benefited from its inherent capacity for non-stationary economic data but is limited by the intricate temporal patterns of real-world series.

heading: 4.2 Ablation studies

text:
Decomposition architecture With our proposed progressive decomposition architecture, other models can gain consistent promotion, especially as the prediction length O increases (Table 3). This
verifies that our method can generalize to other models and release the capacity of other dependencies learning mechanisms, alleviate the distraction caused by intricate patterns. Besides, our architecture outperforms the pre-processing, although the latter employs a bigger model and more parameters. Especially, pre-decomposing may even bring negative effect because it neglects the interaction of components during long-term future, such as Transformer [35] predict-720, Informer [41] predict-336.
Auto-Correlation vs. self-attention family As shown in Table 4, our proposed Auto-Correlation achieves the best performance under various input-I-predict-O settings, which verifies the effectiveness of series-wise connections comparing to point-wise self-attentions (Figure 3). Furthermore, we can also observe that Auto-Correlation is memory efficiency from the last column of Table 4, which can be used in long sequence forecasting, such as input-336-predict-1440.

heading: 4.3 Model Analysis

text:
Time series decomposition As shown in Figure 4, without our series decomposition block, the forecasting model cannot capture the increasing trend and peaks of the seasonal part. By adding the series decomposition blocks, Autoformer can aggregate and refine the trend-cyclical part from series progressively. This design also facilitates the learning of the seasonal part, especially the peaks and troughs. This verifies the necessity of our proposed progressive decomposition architecture.
Dependencies learning The marked time delay sizes in Figure 5(a) indicate the most likely periods. Our learned periodicity can guide the model to aggregate the sub-series from the same or neighbor phase of periods by Roll(X , τi), i ∈ {1, · · · , 6}. For the last time step (declining stage), AutoCorrelation fully utilizes all similar sub-series without omissions or errors compared to self-attentions. This verifies that Autoformer can discover the relevant information more sufficiently and precisely.
Complex seasonality modeling As shown in Figure 6, the lags that Autoformer learns from deep representations can indicate the real seasonality of raw series. For example, the learned lags of the
daily recorded Exchange dataset present the monthly, quarterly and yearly periods (Figure 6 (b)). For the hourly recorded Traffic dataset (Figure 6 (c)), the learned lags show the intervals as 24-hours and 168-hours, which match the daily and weekly periods of real-world scenarios. These results show that Autoformer can capture the complex seasonalities of real-world series from deep representations and further provide a human-interpretable prediction.
Efficiency analysis We compare the running memory and time among Auto-Correlation-based and self-attention-based models (Figure 7) during the training phase. The proposed Autoformer shows O(L logL) complexity in both memory and time and achieves better long-term sequences efficiency.

heading: 5 Conclusions

text:
This paper studies the long-term forecasting problem of time series, which is a pressing demand for real-world applications. However, the intricate temporal patterns prevent the model from learning reliable dependencies. We propose the Autoformer as a decomposition architecture by embedding the series decomposition block as an inner operator, which can progressively aggregate the longterm trend part from intermediate prediction. Besides, we design an efficient Auto-Correlation mechanism to conduct dependencies discovery and information aggregation at the series level, which contrasts clearly from the previous self-attention family. Autoformer can naturally achieveO(L logL) complexity and yield consistent state-of-the-art performance in extensive real-world datasets.
Acknowledgments and Disclosure of Funding
This work was supported by the National Natural Science Foundation of China under Grants 62022050 and 62021002, Beijing Nova Program under Grant Z201100006820041, China’s Ministry of Industry and Information Technology, the MOE Innovation Plan and the BNRist Innovation Fund.

title: Autoformer: Decomposition Transformers with Auto-Correlation for Long-Term Series Forecasting