Theoretical Investigation of Adafactor for Non-Convex Smooth Optimization
Authors: Yusu Hong
Junhong Lin
Venue: NeurIPS 2025 poster ()
Keywords: Adafactor
stochastic optimization
non-convex smooth optimization
convergence rate
Primary area: optimization

Abstract: Adafactor is an early memory-efficient optimization algorithm proposed as an alternative to Adam. By eliminating first-order momentum and employing a
rank-$1$ matrix factorization to approximate the second-moment matrix, Adafactor achieves near-zero memory overhead compared to traditional gradient descent methods.
Despite its practical suitability for large-scale training tasks where memory efficiency is critical, its theoretical convergence analysis remains unexplored, largely due to the challenges posed by its matrix factorization and update clipping mechanisms. In this work, we provide a convergence analysis of Adafactor for non-convex smooth optimization.
We establish optimal convergence rates (up to logarithmic factors) for finding stationary points in both deterministic and stochastic settings, the latter under sub-Gaussian noise.
Central to our analysis is viewing Adafactor as an approximation of Adam, and the use of a new proxy step-size to approximate the unique
adaptive step-size induced by Adafactor's matrix factorization and update clipping, along with an induction argument to control the gradient magnitude. 
Our findings may theoretically suggest that involving rank-$1$ matrix approximation of the second-moment matrix in Adam does not fundamentally hinder the convergence.

Theoretical Investigation of Adafactor for Non-Convex Smooth Optimization
Yusu Hong Center for Data Science
Junhong Lin" Center for Data Science Zhejiang University junhongāzju. edu. edu. cn
and School of Mathematical Sciences
Zhejiang University yusuhongōzju. edu,
Abstract
Adafactor is early memory-efficient optimization algorithm proposed alternative to Adam. By eliminating first-order momentum and employing a rank-1 matrix factorization to approximate the second momeen matrix, Adafactor achieves near-zero memory overhead compared to traditional gradient descent methods. De- spite its practical suitability for large-scale training tasks where memory efficiency is critical, its theoretical convergence analysis remains unexplored, largely due to the challenges posed by its matrix factorization and update clipping mechanisms. In this work, we provide convergence analysis of Adafactor for non-convex smooth optimization. We establish optimal convergence rates (up logarithmic factors) for finding stationary points in both deterministic and stochastic settings, the latter under sub-Gaussian noise. Central to our analysis is viewing Adafactor an approximation of Adam, and the use of new proxy step-size to approxi- mate the unique adaptive step-size induced by Adafactor's matrix factorization and update clipping, along with induction argument to control the gradient magnitude. Our findings may theoretically suggest that involving rank-1 matrix approximation of the second-moment matrix in Adam does not fundamentally hinder the convergence.
Introduction
Adaptive gradient-based methods, such as AdaGrad 11]. RMSProp Adadelta Adam 22 and AMSGrad [37]. among others, are efficient approaches in solving the following unconstrained stochastic optimization problem in deep learning fields:
min X X
f(X) = Ezep (1 ((x;
where f is a smooth potentially non-convex function, P denotes a probability distribution and X denotes all the trainable weights of the mode During the training process, these adaptive methods store the historical gradients' information to automatically tune their step-sizes. For example, both RMSProp and Adam maintain the exponential moving average of squared gradients, and AdaGrad stores the accumulation of squared gradients. Despite their effectiveness, adaptive gradient algorithms incur memory overhead compared standard gradient descent, they must store additional gradient statistics (e.g.. first and second moments in Adam). This may become problematic when training large-scale models, such as GPT-3 4. which contains over 175 billion parameters. The extra memory requirements may limit batch sizes or model complexity, posing challenges for resource-constrained training environments.
'The corresponding author is Junhong Lin. We consider the matrix parameter following the same setup in
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Adafactor [88] was proposed as memory -efnoorrefffiiintt alternative to Adam, and subsequently many other memory-efficient optimization algorithms have been developed recently, see e.g.. [38 31 23 32]
and the references therein. Unlike Adam, which maintains per-par per-parameter first and second moments of gradients, Adafactor employs a rank-1 matrix factorization to approximate the second-moment matrix. This reduces memory usage for the second-moment from (mm) to Om + +n) with tracking only the exponential moving averages of the row and column sums of the squared gradient matrix. Additionally, Adafactor removes Adam's first-moment buffer and incorporates update clipping to improve training stability. In real applications, several LLMs including PaLM and TS [36] have adopted Adafactor as of their main optimizers [53], and recent numerous studies memory- efficient optimization algorithms have adopted Adafactor as the benchmark algorithm for comparative experiments.
The given empirical results reveal that Adafactor achieves comparable performance to RM- SProp/Adam on training Transformer models [38), despite discarding part of the gradient infor- mation to save memory. Unlike Adam, whose convergence theory has been recently studied, e-g.. 46 (55 50
24 42 [9]. theoretical analysis for Adafactor remains absent to the best of our knowledge, though the algorithm was proposed several years ago. Specifically, is unknown whether Adafactor can guarantee to find a stationary point Adam for non-convex smooth optimization, and so, what its specific convergence rate is and what conditions on hyper-parameter parameters are required. We believe that the analysis is challenging, largely due to matrix factorization and update clipping mechanisms.
In this paper, we take the first step to analyze Adafactor's convergence theory for non-convex smooth optimization problems with unbounded gradients. Our main theoretical results are summarized as follows.
With an appropriately chosen step-size and any decay rate 32, [0, 1), full-batch Adafactor can find a stationary point with a rate of O1/TT), matching that of Gradient Descent (GD) and the lower bound for first-order methods (5] up constant factors.
The stochastic Adafactor without update clipping can attain the convergence rate of ((1/VT)
under a common step-size parameter Pk ((1/v)) and decay rate $2, = -1- 1-12 1/k. The convergence rate is optimal up to logarithmic factors, matching the lower bound in (2]
Adafactor with update clipping attains the nearly optimal convergence rate ((1/VT), pro- pro- vided that the clipping threshold and hyper-parameters are chosen appropriately.
We finally provide some simple numerical experiments natural language processing to complement our theoretical results.
The analysis is non-trivial compared to semorryunconstranne adaptive methods such as AdaGrad and Adam due to the unique matrix factorization and update clipping. The core of our analysis viewing Adafactor the complicated adaptive step-size, while simultancously breaking the correlation with stochastic gradients. In addition, we rely an induction argument prove that the objective function value is non-increasing in full-batch cases and that the gradient magnitude remains uniformly bounded during the training process in stochastic cases.
approximation of Adam, and designing new proxy step-size to approximate
The rest of the paper is organized as follows. The next section briefly mentions some of the most relevant works. Section 3 presents some necessary notations and problem setups. Section reviiww Adafactor and major differences to RMSProp/AAdm. Sections/ provide convergence bounds for full-batch Adafactor and stochastic Adafactor (without update clipping), respectively. Section 7 investigates Adafactor with the update clipping. Section & summarizes the main proof challenges and Dactiongbrietly (biitly presents experimental results to complement our theory. All the detailed proofs and some experiments can be found in the appendix.
the proof novelty. Section
2 Additional related work
We briefly list some typical works, due to page limitations.
PPLLM applies Adafactor without matrix factorization.

---

Convergence of unnoossrinnen adaptive methods. In the early stages, most works focus on the regret bound of adaptive methods on (online) convex optimization, e.g., [2 40 for AdaGrad, for Adam and AMSGrad. Several works study the convergence of adaptive methods for non-
22 37
convex smooth optimization, including 226 44
21
13
43
[9] for AdaGrad-Nomm
43 29
20
for AdaGrad, 25 for RMSProp. [54] for AMSGrad, and [46 TO, 55 11
6
17
50
24
42
for Adam. This body of work for non-convex smooth optimization consistently derives a convergence
rate of (I/vVT), with differences mainly on the noise and smooth assumptions, hyper-parameter dependencies and logarithmic factors in convergence bounds.
Memory efficient algorithms. The aforementioned as AdaGrad and Adam require additional memory usage to store gradient-related statistics compared traditional gradient descent methods. Consequently, a line of works focus on reducing the memory usage of such adaptive methods. For instance, []] presents variant of AdaGrad, called SM3, by maintaining & sets of gradient accumulators, Both Adafactor and CAME [31 use matrix factorization to approximate the second moment of gradients in Adam. GaLore [5I] factorizes the gradients through Singular Value Decomposition (SVD) before they enter the optimizer state. [32 proposes a variant of Adam called MicroAdam by compressing both gradients and error feedbacks. Adapprox leverages randomized low-rank matrix approximation for Adam's 's second moment estimator. 23 develops 4-bit Adam using quantization techniques to compress the first and second moment 49 reduces the memory by cutting down the learning rate resources in Adam.
adaptive methods such
122
estimators in Adam.
However, most of these works provide empirical convergence results, with scarce exceptions on theoretical analysis. [ establishes regret bound in convex and
setting for SM3. [32 provides convergence guarantees in expectation for MicroAdam with the assumptions of bounded gradients and well-behaved compression operators in non-convex smooth settings. Notably, these algorithms differ structurally from Adafactor, resulting in key differences in the proof. Morcover, our results hold with high probability without requiring bounded gradients or convexity assumptions.
Another line of works also use the idea of memory-efficiency over full-matris preconditioned gradient methods. For example, works such as [ Hessian matrices in a memory- proposed algorithms in convex settings, assuming certain bounded gradien//Hessian-rehee
45 28 employ various techniques to approximate 14.
way.
and (28 provide convergence bounds for their
terms.
Notations. For any positive integer T, let [T] {1,2 .T). || || and || lloo denote the Frobenius norm and lx -norm, respectively. a ~ O(b) and a < O(b) denote a = Cob and a S Cob for some positive constant Co. For any two matrices X (zt)), )o
(yiy)s E _ we define (X = E Σ/= Kzylly. X O Y. ES or X/Y, and vX denote the element-wise product, quotient, and square root, respectively. O, and 1, denote the n-dimensional zero and one vectors respectively. and nx denotes the n x m-dimensional matrix of ones. For any sequence {ax (21), we define Σi ag = 0 and I
04 1 XA denotes the indicator function with the set A.
We define RMS(X) mm Σ 1== Em=13
3 Problem setup
We consider unconstrained stochastic optimization in over Rexm under the Frohenius norm. The objective function f Rm - R is differentiable. Given an x matrix X, we assume gradient oracle that returns a random matrix g(X, Z) E 1@ dependent on the random sample Z. The gradient of f at X is denoted by f(() _=xm
Assumptions. We make the following assumptions throughout the paper.
(A1) L-smoothness: for any X, Y E R"xm, (Y - vx(x) S Y -X
(A2) Bounded below: there exists f* oc such that f(x) 2 fx,vx Raxm,
(A3) Unbiased estimator: the gradient oracle returns unbiased estimator of (X()), i.c. E [g(X, Z) X = ff()), VX E p
(A4) Sub-Gaussian noise: for > 0, E exp [1x(x1))V/1(X11
X se, Raxm
3

---

Algorithm Adafactor
Input: Horizon T, initialization X, Raxm, R Om: Co 0 step-size parameters
(Pk h211 decay rates {$2,)R21 E [0, 1), regularization constant 6 > 0, clipping threshold
for = -,,.... do
Draw random sample Z and G. g(x, Zx);
R = R2 + (1 82,x) GR O G mmi
C = 82,4CR + $2,x) (G& @ Gy + t,l,1m
WR = (RI, R:):
UE GE/VWE:
FR Pa/ [1, RMS(UR)/d)
X = Xx T)-- Gt/ GE/
end for
Assumptions (A1)-(A4) are standard in the convergence analysis for smooth non-convex optimization. In particular, the sub-Gaussian noise assumption is widely used in the convergence analysis of gradient-based methods, including SGD [15], AdaGrad [27 21 29 and Adam [24).
review of Adafactor
In this section, we briefly introduce Adafactor and highlight its major differences from Adam. The pseudocode for Adafactor is presented in Algorithm
Matrix factorization. Throughout the training process, Adam maintains two n x m matrices, Mg and Vs, using the exponential moving average update: for $I,k, 82,6 [0, 1).
M = 1 + (1
BI,,) V = - V-- + (1 - 32,) @ Gb),
(2)
which results in tripled memory usage. The key innovation of Adafactor in improving memory usage is approximate V& as the outer product of two rank-1 matrices R2 and Cz/(1, Rx), as shown in Algorithm | Moreover, R2 and C are exactly the row sums and column sums of Vk, and they also follow the exponential moving average update. Therefore, Adafactor only maintains two rank-1 1 matrices R2 and Cs, significantly reducing the memory usage of storing Va from O (mm) to Omm + n).
Increasing decay rate. In Adam, corrective terms are introduced into M2 and VR, leading two decay rates that increase toward one. Theoretically, it has been demonstrated that value close to one for f2.4 would ensure the convergence, e.g.. [1] 55] 50) whereas a constant one may lead to decay 1/k5, e > replace corrective terms. As pointed out by (38), this setting allows for enjoying the stability of low 32 at the early stages of training and the insurance of convergence from high 82 as the run progresses. Moreover, it leverages the bias correction.
divergence (37. Inspired by this observation, Adafactor uses increasing second-
rate 32.4
Update clipping. Adafactor modifies the update process by discarding the first-order moment M; and instead applies an update clipping technique inside the step-size Tą-- It is worth highlighting Us when it exceeds a threshold d, which differs from the standard gradient-clipping with the form 7) Pk/ max (1, (T.ll/ This mechanism helps to calibrate the second-moment moment estimator W. when it's seaecr-tha-ddesiir Ga @ Gr. Empirical findings in (38) indicate that implementing update clipping leads to significant performance improvements when the learning-rate warm-up is not used.
that the update clipping involves dividing the root-mean-square
5 Convergence bound for full-batch Adafactor
We first provide the convergence bound for the full-batch Adafactor. At each iteration, full-batch Adafactor obtains the gradient v)((2)) and then updates RR, C2 using ()()s) instead of Gg in Algorithm | The proof can be found in Appendix A

---

Theorem 5.1. Let (K2 be generated by Algorithm and Assumptions (Al) and (A2) hold. For
any constants co. d > 0 and 32,1 [0. 1), we define
G = ( f + co.
A = m-xmax [1x
60
(3)
d(1 82,1)
If0 S 2 < L, = po, vk 2 1 and
Co E dmn(1 - --2,1)
Po 5
(4)
LoemnGA2
then, for any T 2 1,
|G 2GA (f(X)) RE(T]
min
PoT
The result indicates that full- bull-batch Adafactor can find a stationary point at a rate (1/TT) matching that of Gradient Descent and the lower bound for deterministic non-convex smooth optimization [5] up to constant factors. We require E1
O me and Pa I O mn The setting for 32, k is mild,
including the default setup in (38 where 32,x = 1/K0.8, In addition, we can set Pu ~ O mrm to derive a convergence bound ((m)) with respect to the dimension.
6 Stochastic Adafactor without update clipping
In the stochastic case, we start from the simple scenario where Tik- = Pk. dropping the update clipping 1/ max RMS(U&))d)) The main reasons follows.
As a first step toward theoretically investigating the convergence of Adafactor, we retain its most essential component the matrix factorization-wiine temporarily omitting the relatively secondary update clipping. This simplification makes the proof more tractable.
As pointed out in the experiments from [8 Adafactor's performance shows little difference with and without update clipping when implementing learning rate warm-up which a popular method in deep learning 533
We now present the probabilistic convergence bound for Adafactor without update clipping as follows. The detailed proof can be found in Appendix B
Theorem 6.1. Let {X hx21 be generated by Algorithm 7 with me Pk. Vk and Assumptions (A (AA4) hold. For any T 2 1, E (0, 1/2), Ao co O, we define
12o Au
T
42o + A0) + log
H² : 2((((((
- -f)
log
co
8
o
cT
E H log
H
coymn.
(5)
If Po satisfies that
do min
1
1
0 0
(6)
VH
29 H3/2
En VH
and other parameters satisfy that E1
82,1 1/2 P1
Po, for some constant E [0, 1].
Vmn't
Po
B2, =
Wk 2 2,
(7)
ke
k1-o/2
then, with probability at least 1 28,
2
cT
min
H
+ o
log
+ vou
(8)
k
8
5

---

Convergence rate. Since H² (log T). we can set po L 1677
O
satisfying
log ((g)/2(T)
(6) which leads to O log's (2) 7
order of convergence rate. With logarithmic factors ignored, Adafac-
tor can achieve the nearly optimal (11/VT) convergence rate when = 1, matching the ones for RMSProp/Adam in literature and the lower bound [2] for stochastic non-convex smooth optimization.
Hyper-parameter setups. Our result indicates that the optimal rate is attained with 32,
1/k, Pl: Po/vk, pattern commonly appeared in theoretical analyses of RMSProp [55] 25 and Adam [55]. When c increases from to 1, the convergence rate also improves. We also test our hyperparameter setup empirically, indicating similar improvement increases, see Figure and Table in the appendix.
We apply polynomial decay step-size parameters, which have been widely used in existing literature such as
33
We also require Pu I (poly(ing)) and 61 ~ O
Vmn
Dimension dependency. We can set Po ((H-3/2) ~ (((m))=8/4 given that H²2 ~ O(1) and (Vmm) in terms of dimension dependency. With the setup, the convergence bound is (mmn))34 with respect the dimension. Under the assumptions of smoothness, (29 20 derive
bounds of at least (mm) with respect to the dimension for AdaGrad. For Adam and RMSProp, many existing works M 30 25 derive ((poly(mn)) dependency while 24 derive dimension-free convergence bound. Our convergence bounds show comparable dimension dependency to most results for AdaGrad and Adam, though a gap remains toward achieving fully dimension free guarantees, and improving the dimension dependency could be further investigated in the future.
1- 1- Ak The result indicates that Adafactor can still achieve Ö(1/VT) convergence rate. The detailed proof is in Appendix B.5
Time-invariant 82 The following convergence bound sets time-invariant
[T'], a setting commonly used in Adam's 's convergence results [T] 42 19].
Corollary 1. Let { [x be generated by Algorithm 7 with 7ソK = Pk: Vk 2 1 and Assumptions
(AI)-A4) hold. Let T 2 1, E (0, 1/2), H and H. be defined in (5) If 32,1 = 1 B2.x = 1 7, Vk e
(T) (1), Ph = 5 Vk E [T), = ca and po S Au min
VH 22,, 2372 5w B }. then it holds
Vmn
LL
that with probability at least 28,
1 T
H² PLLVT
TeT log (3)
H H
+ voo
7 Stochastic Adafactor with update clipping
In this section, we consider the update clipping and slightly change the threshold Algorithm to time-varying threshold dg. The update clipping in Adafactor differs from the standard clipping mechanism, bringing some more essential challenges for analysis. what follows, we demonstrate that incorporating such clipping can still ensure convergence for Adafactor under sub-Gaussian noise. The detailed proof is in Appendix C
Theorem 7.1. Let { X&ha21 be generated by Algorithm I with d replaced by for any k-th iteration. Let Assumptions (Al)-(A4) hold. For any T 2 1,8 E (0, 1/2), do. Co > and a >> 1, let
1 = (=(2L(((xx)) -f) + 42o + Ao) + log T) + 4v5(1 + log
+ 192No
T
2a+1 Ao + log T)
log
(9)
co
(mn) (a- (a-1)/2gg
Also, lei Ex = + σ
log
TT (at
and I == E + cov coymm. po satisfies that
Ao
1
1
0< pa 5
min
(10)
T
EVVI' E/ E,VI T(EIVI)

---

61 12.k and follow the setups in 7 for any E [0, 1], and d2 2 - Ak (T), then. with probability least 28,
min || kE|T
T2
1 1 log
eT vco
PoLTO/2
Convergence rate. of Po is O (1/ lo/log 2 ) (T) satisfying 10 which leads to O log 20 (T) order for
With 1 Olog T), both Σj and I are Olog T) order and the typical setup max
76/2
the convergence bound. When c Adafactor still achieves the nearly optimal ((1/VT) rate. In addition, we can set Po with respect to the dimension. Under this setup, the convergence bound is ((mm))/4 with respect
3/2) ~ (((m))-334 given that 1 ((1) and I (vmm)
to the dimension.
Impact of update clipping. When incorporating update clipping, influences the selection of po and dg, and the log I" order in the convergence bound. The results suggest that the update clipping does significantly impact the convergence rate under sub-Gaussian noise. We hypothesize that under sub-Gaussian (light-tailed) noise, update clipping is not necessary for ensuring convergence. However, for other cases such as the heavy-tailed noise, update clipping may play crucial role, similar to the role of standard gradient clipping, as demonstrated in e.g., 9 48 7).
We require de increase with steps k. At the early stages of training where the updates usually unstable 38 Figure 1]. dg is small to ensure the clipping works effectively. As training progresses, the stable. Consequently, there is less need for update clipping, corresponding to a relatively large dę. We test this setup through some experiments, showing its comparable performance with the standard setting da
sequences become
Figure 4 and Table 2
in the appendix.
Time-invariant $2.k- We also provide the convergence bound with $2, = 1 1/T, which shares similar form the one in Corollary [ The detailed proof is in Appendix C.4
Corollary 2. Let T 2 1,8 E (0, 1/2), I and I be defined in Theorem P00 Ah E [T).
7.1
If B2,1 2 82, =
1 1. Vk E [T] (1),Pk VT.
Co
dy 2 1)(a-1), Vk E [T] and Po S
"mme
Àe min- EiVI 2371377: EIVI' TEEVIIJ }. then it holds that with probubility at least 25,
V S I2
(T log
cT
+
c
PoLTe
5
Summary of proof challenges and techniques
In this section, we will summarize the main proof challenges brought by Adafactor, which are essentially different from other memory-unconstrained adaptive methods such as Adam due to the unique matrix factorization and update clipping.
We let G3 v)(x,) and begin by the descent lemma of the smoothness
34 Theorem 2.1.5),
f(X+11) f(x)) 7 (Gr.
Ge
L
G
vk 1.
(11)
VWR
2
W
(I)
(II)
Then, the following challenges arise from estimating (I) and (II).
Challenge I. Correlation between G& and W.. The classical method for estimating (I) is to decompose it as the "descent term" " plus the "noise variance term":
GE W
mh (Ge,
Ge G
(1)
Tk
WWR
descent term
noise variance
7

---

For non adna-tdetive methods such SGD, "noise variance" is martingale difference sequence. However, its conditional expectation is not necessarily zero, and the property of martingale can no longer be used due to the correlation of GR and W. in Adafactor. Other adaptive methods such as AdaGrad and Adam, also face similar problem.
overcome this, existing works for AdaGrad and Adam such as 44 11 42 19 typically introduce a proxy step-size matrix Ag that is conditionally independent of G. and decompose (1) as
G
2
Gk Gk VAR
11) -1
I Gki
+
Gk. Gx 2
(12)
A
VA
VWB
martingale difference
For these works, proxy step-sizes are designed based on the linear update of Wk. the adaptive part in step-sizes, such as @ However, Adafactor uses more complicated adaptive step-size with non-linear update rule between Wt and WK-1. as shown in Algorithm making existing proxy step-sizes not applicable.
Solution.
We first define some temporary bounds for (stochastic) gradients: for fixed horizon T || [F, Σn Di + a log
and any k E [T], Dx max
oT and
Gk.1 == 2 mE1, Gk. = 2 + nE1. Gp := 2x + mnE1.
(13)
Relying on the property of Lub--aussian noise, we can verify the following inequalities with proba- bility least 8 (an equivalent form of (42).
elf' 5
max <
G. - Golle S v log
max E
|Gal| F S Ex, vk E [T].
(14)
We design a new proxy step-size matrix A as follows:
A (32 (1 Gx.1) 1n) (32, 82, 9k.2 1m)
32 + 32,x)9x
A& satisfies two important properties: (a). It's conditionally independent with G. Gg. Thereby, "martingale difference" term in (12) can be bounded through the concentration inequality. (b). The following "distance" between Wi and A₃ be estimated by D₁ multiplying small term
/ B2. as 32.2 is set to close enough to one: let W = (w )ig. As = (a )a, then
w
(k)
(K)
0o
(D(VIII-
B2xx
VA E [T, E [m].j E [m]]
(k)
Relying on this bound and the setups of 7/ and B2,5 in 7.. and probability event in (14). we get that
error
Gx
+ +0
2/ log!). E [7].
(15)
Ax
1=1
We also refer the proof of Proposition B.I in the appendix for more details.
Challenge II. Additional update clipping. The first solution only considers the case where the update clipping is omitted. The update clipping introduces an even more complex adaptive step-size.
We incorporate the new proxy step-size method in Solution 1 and some techniques from the analysis
of algorithms with standard clipping [9] 30 35).
Solution. We first rewrite the update rule as
G
G
X
X
Pk
WE
G
max RMS(U.)/

---

Then, we follow the design of A in the first solution and provide decomposition for (T) in
G V A
II) Pk
+
Pk
Gk:
Gk
VA
VW
deseent term
error
G+.
Gk VAR
GR
G
Pk
Gk
Zz
+ Pk
Gk.
13
V
VAk
VAR
martingale difference
ettor 2
where Zg is the k-th random sample. Note that "error 1" shares similar form as "error" in (12). which can be estimated similarly in (15). The critical point is to handle the additional "error 2".
With Aş conditionally independent with Zg and G₁ = Ez, [G&] from Assumption 3,
G₂ VA
S2 = Gx (1 max ||Ux|l (d wnm]) (16)
error 2 S Pk
Ezz |12
Under the probability event of (4). will estimate Ez, |[R which is solely dependent Zz, -k Then, we can further derive that
2V
E ||22
2%
(17)
dymmnne
Combining the above, and applying setups for dk. Pk and 61, we get the following bound under 14
error 2 SOO Σ Do Exv
s so (PoD, (Ziv (ΣrV (i)) logt).
AA E [T].
k
1=
For more details, we refer the proof of Proposition C.I in the appendix.
Challenge III. Potential unbounded gradient magnitude. Throughout the paper, we do not assume the gradient magnitude is bounded. Therefore, we can only estimate (I) and (II) through the temporary bounds Dx. Σ and 9% in 13).
Solution (stochastic case). First, based on the estimations for (I) and (II), one can derive that for some increasing positive function Φ(x), with probability at least - 8,
Gx
2
(MoO(D)))
(7)
1)))
f(X++))
+0
Vt Vt
(18)
2
A
Then, we use an induction argument to restrict the gradient magnitude. The induction will start by verifying D1 S H and then assume that D, < for some E [I] where H a value defined with Olv (Tg(8)) order in prior. Using the induction assumption and |.++lli S 22( - f*) into (18).
G A
(OL log (5))
G S -
m
+0
5
co log
(19)
where the last inequality applies the setup Po S Lo(H) Then, we derive that ||G++1ll S H² from
(19) as H² is (1og(T/6)) order and can be set equal to the RHS of (19). The induction is thereby complete, and the gradient magnitude bounded by H. We refer to the proof of Proposition for more details.
Solution (full-batch case). In the noiseless case, (I) and (II) can be cancelled with each other through a proper selection of mn- Relying on this, we can use an induction to derive stronger result where fXx) is non-increasing with t. See the proof of Proposition A. for more details.

---

c=10
c=0.7
0.8
00
C=0.9
0-
Traning LOGS
0,7
Training
0.6
3.5
Step
Step1
(a) BERT-Large GLUEMNII
(h) GPT-2 on BookCorpus dataset
Figure 1: Training loss vs steps for different decay rates using Adafactor (no update clipping)
Experiment
Many existing works, such as [38 51 32 53
have empirically demonstrated the convergence of Adafactor, showing that it achieves comparable performance to Adam in training NLP models.
While main contribution lies in theoretical parts, also test full fine-tuning (FFT) scenario. We train BERT-Base and BERT-Large on GLUE/MNLI and GPT-2 on BookCorpus dataset. We follow the setup in Theorem 6. and require range from 0.6 to 1.0. Training loss curves are presented in Figure [ and Figure 3 and test accuracy is reported in Table D in the appendix. The results show that increases, both the training loss and the test accuracy improve, complementing our theoretical findings. The detailed training settings can be found in Appendix D.I
Syper-paramene setups in the
We also compare our configuration at = (the optimal selection in thcoretical) with the default setting proposed in (38) and with Adam, finding that their performances remain comparable. When incorporating update clipping, we test the increasing clipping threshold de k क proposed in Theorem 7.1 and find its performance to be comparable to the default setting where da = and to Adam. Detailed experimental results provided in Appendix D.2
10
Conclusion
In this paper, we take the first step toward understanding the convergence of Adafactor in the non- convex smooth landscape under aub-Gaussian noise. Our theoretical results indicate that with the proper hyper-parameter setups, Adafactor can achieve the nearly optimal convergence rate, matching the lower bound for first-order methods in full-batch cases up to constant factors, and stochastic cases up to logarithmic factors.
Linitations. First, the convergence behavior of Adafactor with constant clipping threshold, which may be more common in practical applications, remains theoretically unexplored. Second, it remains unknown whether Adafactor can still converge under other noise assumptions, such as heavy-tail noise and affine variance noise. Third, the convergence results for Adafactor are established under the standard smoothness assumption. would be interesting to further investigate the convergence under more general smoothness conditions that better reflect practical applications, such as (Lo, L1)- smoothness. Finally, it's beneficial to further support our theoretical results through experiments on large language models.
Acknowledgement
This work was supported in part by the NSFC under grant number 12471096, and the National Key Research and Development Program of China under grant number
References
[1] Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory efficient adaptive optimization. In Advances in Neural Information Processing Systems, 2019.
10

---

[2] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming. 199(1-2):165-22) 2023.
[3] Amit Attia and Tomer Koren. SGD with AdaGrad stepsizes: full adaptivity with high probability unknown parameters, unbounded gradients and affine variance. In International Conference on Machine Learning, 2023.
[4] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages
1877-1901, 2020.
[5] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points Mathematical Programming, 184(1):71-10, 2020.
[6] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
[7] Savelii Chezhegov, Yaroslav Klyukin, Andrei Semenov, Aleksandr Beznosikov, Alexander Gasnikov, Samuel Horváth, Martin Takáč, and Eduard Gorbunov. Gradient clipping improves AdaGrad when the noise is heavy-tailed. arXiv preprint arXiv:2406.0444 2024.
[8] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1- 113, 2023.
[9] Ashok Cutkosky and Harsh Mehta. High- high-probabiilty bounds for non-convex stochastic opti- mization with heavy tails. In Advances in Neural Information Processing Systems, volume 34, pages 4883 4883,4895,20 2021.
[10] Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for R.SPrrp and Adam in non-convex optimization and an empirical comparison to Nesterov acceleration. arXiv preprint arXiv: 1807.0676, 2018
[11] Alexandre Défossez, Leon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of Adam and AdaGrad. Transactions on Machine Learning Research, 2022.
[12] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learming Research, 12(7):2121-213 2011.
[13] Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in SGD: self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, 2022.
[14] Elias Frantar, Eldar Kurtic, and Dan Alistarh, M-FAC: Efficient matrix-free approximations of second-order information. Advances in Neural Information Processing Systems, volume 34, pages 14873-14886, 2021.
[15] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
[16] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems, volume 33, pages 15042-15053, 2020.
[17] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the Adam family. In Annual Workshop on Optimization for Machine Learning, 2021.
[18] Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. International Conference on Machine Learning, pages 1842-1850. PMIR, 2018.
11

---

[19] Yusu Hong and Junhong Lin. On convergence of Adam for stochastic optimization under relaxed assumptions. In Advances Neural Information Processing Systems, volume 37, pages 10827-10877, 2024.
[20] Yusu Hong and Junhong Lin. Revisiting convergence of AdaGrad with relaxed assumptions. In Uncertainty in Artificial Intelligence, pages 1727-1750. PMLR, 2024.
[21] Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for class of nonconvex algorithms with AdaGrad stepsize. In International Conference on Learning Repre- sentations, 2022.
[22] Diederik P Kingma and Jimmy Ba. Adam: a method for stochastic optimization. In International Conference on Learning Representations, 2015.
[23] Bingrui Li, Jianfei Chen, and Jun Zhu. Memory efficient optimizers with 4-bit states. In Advances in Neural Information Processing Systems, volume 36, 2024.
[24] Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of Adam under relaxed assumptions. In Advances in Neural Information Processing Systems, 2023.
[25] Huan Li, Yiming Dong, and Zhouchen Lin. On the O Vd
( convergence rate of RMSProp
and its momentum extension measured by n-nom.. Journal of Machine Learning Research, 26(131):1 25, 2025.
[26] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In International Conference on Artificial Intelligence and Statistics, 2019.
[27] Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive SGD with momentum. In Workshop on International Conference on Machine Learning, 2020.
[28] Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprint arXiv:2305.14342. 2023.
[29] Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, 2023.
[30] Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou, Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In Conference Learning Theory, pages 66602290. PMLR, 2023.
[31] Yang Luo, Xiaozhe Ren, Zangwei Zheng, Zhuo Jiang, Xin Jiang, and Yang You. CAME: Confidence-guided adaptive memory efficient optimization. In Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics, 2023.
[32] Ionut-Vlad Modoranu, Mher Safaryan, Grigory Malinovsky. Eldar Kurtić. Thomas Robert, Peter Richtarik, and Dan Alistarh. Microadam: Accurate adaptive optmiizttion with low space overhead and provable convergence. In Advances in Neural Information Processing Systems, volume 37, pages 1-43, 2024.
[33] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. In Advances in neural information processing systems, volume 24, 2011.
[34] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[35] Ta Duy Nguyen, Thien H Nguyen, Alina Ene, and Huy Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In Advances in Neural Information Processing Systems, volume 36, pages 24191-24222, 2023.
[36] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020.
12

---

[37] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
[38] Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, 2018.
[39] Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. RMSProp converges with proper haper-parameter. In International Conference on Learning Representations, 2020.
[40] Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv:1002.4802 2010.
[41] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
[42] Bohan Wang. Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap between the upper bound and lower bound of Adam's 's iteration complexity. In Advances in Neural Information Processing Systems, 2023.
[43] Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of AdaGrad for non-convex objectives: simple proofs and relaxed assumptions. In Conference on Learning Theory, 2023.
[44] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(1):9047-9076 2020.
[45] Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney. Adahessian: An adaptive second order optimizer for machine learning. In proceedings of the AAAI conference artificial intelligence, volume 35, pages 10665-10673, 2021.
[46] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, 2018.
[47] Matthew Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212.5711. 2012.
[48] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, 2020.
[49] Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Diederik P Kingma, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. Adam-mini: Use fewer learning rates to gain more. In International Conference on Learning Representations, 2025.
[50] Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can con- verge without any modification on update rules. In Advances in Neural Information Processing Systems, 2022.
[51] Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficiint I1m training by gradient low-rank projection. In International Conference on Machine Learning, pages 61 621--11143. PMLR, 2024.
[52] Pengxiang Zhao, Ping Li, Yingjie Gu, Yi Zheng, Stephan Ludger Kölker, Zhefeng Wang, and Xiaoming Yuan. Adapprox: Adaptive approximation in Adam optimization via randomized low-rank matrices. arXiv preprint ar arXiv:2403. 140.5 2024.
[53] Wayne Xin Zhao. Kun Zhou, Junyi Li. Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang. Junjie Zhang, Zican Dong, al. A survey of large language models. arXiv preprint arXiv:2303. 18223, 2023.
[54] Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. In Annual Workshop on Optimization for Machine Learning, 2020.
13

---

[55] Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSProp. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
14

---

A Proof detail for Theorem 5.1
the replacement of the stochastic gradient by the gradient (X(x at each iteration. We first provide the form of full-batch Adafactor as follows. The only difference Algorithm Lis
Algorithm 2 Full-batch Adafactor
Input: Initialization point X, R= Ro O,, C. 0 step-size parameters {p*)221.
decay rate (k2, E [0, 1), regularization constant 6 > 0, clipping threshold d.
for k =I.... .T do
Ge =V](Xa);
Rg R2 (1- @ 1
C₁ = 82,4Cr-1 + (1- 1 (Gs o Ga + +elll)
W. - =(R,Cz)/1, Ru:
U² = Gv/VWW:
fR = pa/ max (M)
X = X îi. GE/ Ve/V WE:
end for
A.1 Preliminary
We first denote the auxiliary matrix Gh. Gy o GR + 111,1 In addition, we define V
as follows,
Vo Onxm:
V = f2, V (1 (2,0-2,6)000 B2 1
(20)
To simplify the notation, we let G2 =
R clU) and Sv, be the i-th row sum, j-th column sum and the coordinate sum of V. respectively. The same definition principal is applied to the
(k)
9ij
ij
notation 12(0) and CG) We also use ( Di Uif denote the coordinates of WA. Vi, Uk GR
(k) (k)
in Algorithm respectively. In addition, we define the temporary upper bound for the gradient
magnitude
D. max ||Gllle ke[t]
A = DJ + mnc1.
(21)
A.2 Technical lemmas
Before proving the main result, we introduce some technical lemmas.
Lemma A.1. For any 2 1, Ei. s + logt.
Proof. With simple calculation, have
/ dx < 11
p /" dr = 1 +ogg l.
Σ 2=
h
The following result standard in the analysis of smooth-based optimization.
Lemma A.2. Let f satisfy Assumptions (Al) and (A2). Then, || f (X) || s 2L( f*) and
((Y) < (XX) + (V)(X),X - x) Y - X
VX E mxm
(22)
Lemma A.3. Let 82 [0, 1], vk 2 1 and Tx be defined by
To = 0,
T₁ = 32 (1 B2,x),
Vk >
Then, (1 (1-39,1 32.1) T4 < 1, vk 1.
15

---

Proof. We could prove the result by induction. Since Fo 0, it's easy to derive that (1 B2,1) =
I1 S Suppose that for any c 11. 82,1) $ ; S Then
F& 2 f2 - $2,1) + (1 - 32,k) 2 $2,1, T& S 32, + (1 82,x) = 1.
The induction is then complete.
Lemma A.4. Let Vi be defined in (0), Rg and C₁ be defind Algorithm 2
For any 2 0, it holds
that
R Vilmm C₁ 1,
Sv. 1 V
As a consequence, for any E [n],] E [m].
R()
B2 (1) Vx-1 + (1 82
(1) GR.a
c Be,c c(d Ve-, Ve-1 +
B2, Gh.a (1- +11
Proof. Note that Ro Volm On and Co V. Vo O Suppose that for any j I k
R3- 1, C2 1 V, Then, using the updated rule in Algorithm 2 and 20
R 82 R + (1 32,x kin 1m (32, ( + (1 32,x) G k.r 1m = V kmm
(23)
C₁ 32 Ck-1+ (1 82,x) GR K.e, 1 (82,r V--1 (1 G k.e.)) 1 Vj.
Since Sv, represents the coordinate sum of VR. could derive that
SV.
R = 1g
R(() Since RV.. denotes the i-th row sum of Vg, it's the i-th coordinate of R Hence, for each coordinate of R2, using 23). we get that
R
32, R())
+
82,x)
Similarly, we can derive the result related to clu) Vi
Lemma A.5. Let Dù and Dạ be defined in
21
Then, for any i E [n], E [m], k 2 1, it holds that
(6( [mei (1 (2,1), D mei), cbil E [nei 12,1), D nei),
Sv, E [mnez (2,1), Axl.
Proof. Recalling the definition of V in 20 and T& Lemma A.3
we derive that k
B2,0) (0!57) 2 +G)
Sv. =
II B2d 1=p+1
1=1 j=l
$
B2,z)
$2,1 1=pt1
GGpll + +Tgmme
1=1
< [D + mmc))
S A
(24)
where the last inequality applies Lemma
A.3 Following 24 and Lemma A.3 we also derive that
Sv. Im 2 mmnc 12.1)
and c(i) as follows, Vi.
We also derive the upper bounds for Vi
)2
II (=p+1
32
I1 + Tame, & D + mc,,
(1 32,p)
II 1=p+1
32,1
GG + +'nne S DE + mei.
1=1 p=1
Similarly, the lower bound could be derived by
R
(1)
> me,TR mc B2,1),
c(il
2 neT 2 nc -221). Vi
16

---

A.3
Non-increasing function value.
Before proving Theorem 5.1 we need to establish key proposition as follows, indicating that the
objective function value is non -on-increasing under the proper selection of 61 and Pk: in (4). The proof will rely on an induction argument.
Proposition A.I. Following the same conditions in Theorem 5.7 for any lo 2 1,
((X++)) Pk:
G
(25)
2GA
where G and A are as
Proof. Using Lemma A.2 and the updated rule in Algorithm
2 we get that
[(X++1) S f(Xx) (Gx, Xx+1
Xx)
X
k-1
Gk
Liik
G2
s(xss 7
Gk:
+
WR
2
W
Gk
G2
$ ((())
+
1k
(26)
V Wx
2
WR k
(n)
(b)
Step I: Estimating (a) and (b).
To lower bound (a), we first discuss the maximum operator inside
thk Let two index sets be defined as
E kk)
{
[k]
|1.|| 2 dvmm)
EY = fsE [k] |..1I dv m
R cli v2
Using Lemma A.5 and w (B)
and noting that RLO V.2 Vi
S Sv. we derive that
Sv,
mnc?( (1 B2,1)²
(K)
(N) wij
S Sv. S Ao.
(27)
D
Then, we have
(k)
12
m
Pij
1
DEAx mne - (2,1)²
|
(28)
(k)
mnee(1
12
1=
Hence,when &s E E
the clipping effective and we get that
G
dymmpk
||
deimn(11 - (8.1) -b21) Gall
(29)
Wn
U
Db
max;,j
When & E the clipping does not work and we obtain that
Ge
Pk ||
Pk |k| 1
(30)
Wr
(R)
A
maxij
W
Combining with (29 and 30 and using 6 dmn(1- B2.1)*
Go
we derive that
(a) > min
Co
Pk | Gull..
(31)
V DRAr
Using we have
(b) 5 Lp G
Lp |o GkllDAt
(32)
2 ming,j w/
2(1 - Prnnee
17

---

Step 2: Verifying k 1. To prove the desired result in 25 we use an induction argument. First, we need to prove the case of l Note that when k from Lemma A.2 Ej and D1, A defined in (21). we get that
Dj = G 1p 2)(
f*)
A Dj mme1 S G² + mne1 S A.
(33)
Then, setting k in 31 and using 33
Copı CopilI || 1 P1 G
Co
(a) 2 min
(34)
A
GA
GA
where the equality applies that A >
and I 1 from
Similarly, applying 333 into
with
k I, and combining with (34) and 26
with 1,
A
cop1 |G
f(X2) S s((i) Gill2
S f((i))
2(1
82,1 mmme?
GA
2GA
where the last inequality applies the setups of e1, P1 in
Step Verifying
Suppose that for any S 1, 22 holds. Consequently, for any k S t.
|| < ( fr) S ... S 2T - f*) GP D A.
(35)
Then, setting k = in (31 and 32). and using (35). we have
1
copr. G. l GA
G.
(a) 2 min
G
(b) S 2(1 B2,1 Jemner
(36)
V GA
Plugging (36 into 26 with and using Pt Pn in
we get that
f(X+11) f(,) + + P ||
T,, 2(1 ?
Co
s((()) - cope CoPellGoll?
GA
2GA
Then, the induction is complete, and we prove the desired result.
A.4 Proof of Theorem
Now, based Proposition A.1
easily prove the main convergence result. Consequently,
subtracting f* on both sides of (55 and summing up both sides over E [T),
Pk: 1
S s(Xi) ((X..1) S s(x)) S*,
2GA
where the last inequality applies Assumption (A2). Then, with Pk = Po. we can derive that
G < 2GA (f(Xi) f()
min
G
kE
PoT
B Proof detail for Theorem 6.1
B.1 Preliminary
We first follow the notations of G3 =
Dij ij
(k)
= vf(X)). Let G₁ =
(1))
and Ex :=
G GR. We define Gh.,, = G ① G + 61 1 and V3 (14)) ) such that
Vo = Onxm: === B2 V + (1 82,x) GR, Kee
121.
(37)
We also define R(6) ctil and Sv. as the i-th row sum, j-th column and coordinate of Vx represent the same definitions with respect G2 G Then, using
respectively. R2(i) and (úU G
similar deduction in Lemma A.4 we obtain that for any k 2 1, [m], E [m].
R!() = R2 + (1 32,x) GR.
Chi = B2, C(
+ (1 - B2, C0) Gi. Ve
(38)
18

---

As consequence of 38
each coordinate of W satisfies that
(2 (1- 32,x) 32,x) Ch.,, (B2nOV Va-1 +
82,
C(ú) BV
G
(k)
Vi
Wij
SVv
S2 + (1 82, 82,x)SSr2...
(39)
well-constructed proxy step-size.
For any to 2 define
e7
D3 max *E
[.,lr,
Ex Dj + o
log
GR,1 = Σ + me,
GR.2 Ex + nel,
GR : Σx + mMe1.
(40)
Then, we introduce a proxy step-size matrix A₁ = (15
(k)
such that
B2 -1-11111801 (2.)) C2 1
+ (1 92.2)
(2) 1
Ve-1
(41)
B2 + (1 32,
The proxy step-size technique is standard way in the convergence analysis of udaptive methods, e.g., 44 [I]. We provide new proxy step-size in (4T) handle the matrix factorization in Adafactor. This construction satisfies two properties. First, it's independent from the k-th random sample Z and thereby conditionally independent with the k-th stochastic gradient GG. Second, needs to remain sufficiently close to the original adaptive step-size W; to avoid generating divergent terms, as indicated in Lemma
B.2 Technical lemmas
In the following, we first provide some necessary technical lemmas. We introduce a concentration inequality for the martingale difference sequence. See [27] for proof.
Lemma B.1. Suppose that [Zabwe|r] is a martingale difference sequence with respect to Gi.... Cr- Assume that for each [T', o. is a random variable only dependent on S1,-1- ,5-1 and satisfies that
Z2
E
exp
G (.....
So-2 Sc.
o?
Then, for any > and for any 8 E (0, 1), holds that
1
3
P
Σ Z. X
log
o
8
We also introduce standard result showing that the maximum magnitude of sequence of vectors with sub- Gob-Guussian norm is restricted. See [27] Lemma 5) for a proof.
Lemma B.2. Let T 2 and E = Ge Gk. Vk E (T] satisfy Assumption (A4). Then, with probability least 8,
eT
|E o² log kE[T]
max
(42)
Then, the following lemmas will be established based on the probabilistic event in Lemma B.2
Lemma B.3. Let T 2 1, 32,1 = 1/2, 82 E [0, 1), Vk 2 2 and GR.1. Gu.2. Gy be defined in 40 If
42 happens, then, for any k E [T], i [n] and E [m].
(1) R
RV,. E [mcm/22 20c1/2,9u.11 Gr.l,
c
c [nc//2, Gk.2,, Scg,, Sv, E [mmee]/2 Gx)-
G
G
19

---

Proof. First, using 42 we have for any &s E [T),
cT'
|| = ||Galll + |1Ex11F
D2 + + log
Mi.
(43)
0
Using
40
derive that
mme1/2 S Sch...
m ΣΣ
9ig
(R)
2
t61
= =|Gxll +mne1 S GK.
1= i= j=1
me1/2 - (2(1)
C2
Σ
Pij
(1)) 2
+
<
men S GK.1,
j=1
nc1/ < ((5
Gh.01
0ij
(k)
+a
< S|G++| + S 9k.2-
Using Lemma A.3 and 44). we can show that
mE1(1 1 S RV
Σ (1 B2,p)
II 1=p+1
B2n1 ||Gpll + TTmee S T2(22 + mei).
p=1
With $2,1 = 1/2, we then obtain the desired result. The bounds for CVi. Sv, can be also derived by the similar deduction.
We have the following lemma to control each coordinate of the proxy step-size matrix A
Lemma B.4. Let T 2 1, 32.1 1/2, 32 [0, 1), Vk: 2. If 42 happens, then it holds that for any l E [T) i E [n].] E [m].
mnei 2
S w
(k)
mne?
S ai S min.
(R)
4Gk
4Gk
G. 2
12 mnc!
Consequently,
VWz
R(9 o6 Sv,
(k)
Proof. With w
we can easily derive from Lemma B.3 that
(k)
mne
Gx
4 Gk
why
4G
WW
ming,j w
(R)
mne?
where the last inequality applies
43
Since R(()
RV Ve-. S SSv_., and Gr. Gv.2 Gk. have
(
12 Vo (1
9
B2 v + (1 92.2 1.
$1,
3 +
32, 19k 19k
S2. (1 32, 19k
Then, using Lemma
B.3 we derive that
< min
B2 R(0) Ve_, + (1 - G2. B2, Ve-1 + 82,x) I min Gr.2
(44)
To lower bound aiz we can derive from Lemma
(k)
B.3 that
B2 (e) + (1 Ge, 2
32, + (2,t)(me1/2) mme1/2.
Similarly, we get that 32, cl) + +(1 (1-32,x))x. ne//2 and further deriv that a
(k)
4Vr.
Next, we have the following probabilistic result relying on the property of the martingale difference sequence and sub- Gaob-aa noise.
20

---

Lemma B.5. Let Pk be defined in 77) and 32, E (0.1). Let Assumptions (A3), (A4) hold and H. be as in S). For any T 2 1, and 8 E (0, 1), it holds that with probability least 6,
3 2
G
Pk
Gki
V
Ph
Ak
+
log
8
Vt E [T]
Proof. Let <4 -p (appn/GG vA. and the filtration Fs (Z), ZR) where a()) denotes the o-algebra. Note that Pk. G₁ and Ag measurable with FR-1 and & is measurable with F&. Then, [G4h221 is a martingale difference sequence with Fx since from Assumption (A3),
E Ex
Fk-1
E [Sk Fx-1]
- Ppk
Gk,
0.
V
Let W/ = pp
Gr vAn
We derive from
inequality and Assumption (A4) that
Gx VA.
2
E
exp
?
Fk-1
S EE
exp
Fi-1
S.
(45)
o²
Gx
vd
F
Then, using Lemma B.I
it leads to that for any À > O, with probability at least 1 8,
Gki
EK
3
Gx
Pk
Pk
+
log
(46)
A
4
VA
k=1
The following key lemma provides upper bound for the "relative distance" between We and A
Lemma B.6. Let T 1, 12, = 1/2, B2, [0, 1), wk 2 2. If (42) happens, then for any
k 2 1, [n],j j E [m]] and Gr in (40). it holds that
(k)
(k)
w 3j
aij
<3 -B2,A)Kk.
(47)
V 0ij
Proof. To simplify the notation, we let
X; = 32, R + - 32,x) Gi,
X = (1 - (22x) [5.11 - R
Y₂ 32,1 O(1 Ve_, + (1 - (2,x)
YE (1 B2,4)) 9k.2 c(U)
G
7 S2 + (1 B2,1))
7: = (1 - -22,5) (gx- - (Sk-Sozn)
(48)
Then, we have
X&Yr (Xx
8x) Vik)
w d
(K) (k)
Zk
2x + 2x
X&Y Zx V2:
V Zx Zx
Z (Zx + Z+}
Recalling djj in 41).
(8)
we get that (k)
(x Vi))
Hence, derive that
Zat2e
(k) Wij
aij
2 - NaZaPa YrZuN, - Za.
(K)
Z Z (X+ + XX) - (2) + 2k)
X&VA + V. + +(8rPa)
X&Y&
(Xx + Xx)(Yr + (2) + Zx)
Z ZXV + XY) + +Y) + Zt)
(c)
(d)
(49)
21

---

Since 42 happens, we can apply Lemma B.3 to verify that
5 Xx <1 12,
0 S Y S (1 92,2)9
0 2x S (1 - B2,
(50)
Since v 2 0 and 2 + Zx > 0, (c) can be bounded as
X&Yx X + X
X&Yx + Yx,, +X
(c) VXX.% && + XxVA + 7k)
(51)
Zx + Zx
Recalling the definition, we have Xs, Xx 1 Zx + Zx and Y3 S Zk + Zz. Further, applying (50). we derive that
XAYR
Yu.x
S
S (1 9k.2
S X S (1 - (2,x)
Z + Zz
Zz + Zx
X
S Yx < (1- - -2,x)
Zk + Z&
We then derive from
51
9 S gh and gk.2 S 9b that
(c) - / 3(1 - 9k
(52)
Then, we move to bound (d). Recalling the definitions in 48 we have 0 0 Xx < ZR 0 S Yn S Za.
Combining (50p where XR, Yk, Zx 2 O, have
ZR
VAYAZZR
(d)
SV (1- 32,
(53)
Zu Z Zu
Zk
Applying (52 and
53
into 449
we then derive the desired result.
B.3
Bounding gradient magnitude
In this part, we will control the gradient magnitude along the optimization trajectory. The result is summarized in the following proposition.
Proposition B.1. Following the same conditions and notations Theorem 6.1 for any 2 1 and 5 E (0, 1/2), it holds that with probability at least
26,
D2 max
|Gxl|e & H, E,
< Σn,
G1 S H. Vt [T).
(54)
kE
Proof. Using the inequality in Lemma A.2 and Algorithm I
we have
[(X++1) < ((x)) + (Gx, X - -Xa) +
Xx-1
Xxl1
2
Gx
L
G₁
{ UK GE:
VWa
VWa
Introducing the proxy step-size matrix A in 41) and then summing up both sides over k E [t], derive that
Gk Th Gk,
v A
A
1 VA
L 2
2 v W.
G2
Gk, Ga
(55)
VWa
First, we will assume that the probability event in 442 happens and estimate B, C relying on the temporary upper bounds Dr. Σg, Gbe in (40). The estimation for A is given during the induction
argument. Note that when the same conditions in Theorem 6. hold and (42) holds, Lemmas B.3
B.4 B.6 To start with, using (42 we have
|G |G
||El|F S Σg-
(56)
22

---

Estimating B. B is essentially the enror brought by the proxy step-size Ag. We will first calculate the gap of 1/ w
(R)
and 1/ 4g
(k)
follows,
Wuij
Vij
(k)
V
w a5
(k)
(57)
V
(k)
(K)
(R)
V i
(k)
v
Voij
(k)
We then apply (57) and Young's 's inequality,
(R) (k) Jig
(k)
(2) 0.3
B
The
9ij
(k:
Wi
(k)
aij
(k)
Dis
(R)
2
7
(58)
4 k=1
(k)
(k)
k=1
Thus, plugging (47) from Lemma B.6
into (58). then using Lemma B.4 and T/ = Pk.
Po/k e02 82,1 1/2, $2,
1/k- we derive that
G
Gk
B
1
+ 12
The (1
B2
A
VW
k=
Gk
48pu
Σ 1K
mine
2
G
48po
S// (1 logt)
$ 4 k=1
Σ Pk
(59)
VAR
m
F
where we apply En < Ex, Gk S Gr,k k S and Lemma A.I in the last inequality.
Estimating C.
Using the setups of тą and B2,ks Lemma B.4 and Lemma A.I we have
Pú k
G
2Lp mnej
k 2L + log 1)
C
(60)
W
k
mne?
k=1
An induction argument bound D₁- The induction is established based on the events in 422
and Lemma B.5 Hence, the target result will hold with probability at least - 25. First, it's easy to
verify that Gf S (X), f*) S H² from Lemma A.2 Let suppose that for some E [T].
Dr S H, consequently with = co/ ////mn.
Ex S En,
GR S H.
Ak [4]
(61)
where the specific defitions of H, Σh and H are in (5). Then, we move the case of + 1. We first
subtract f on both sides of (55) and use Lemma A.2 2
to derive that
|G++1ll2 112 S 5(( - f(1)
-
(62)
2L
Next, we provide the esimtation for A based on 42 and Lemma B.5
Estimating A.
We first introduce & G
G3 into and get that
2
Ex
A
M G
(63)
A
A
1=1
Under 42 and 17/ Pk, combinine with Lemma B.4 and Pk: in to derive that when e E [0, 2).
Pk
Po
2
2pov Vmnce
(64)
(K)
h.
/ /mne
23

---

Therefore, setting À = (66nee Pu) in 446
using 64
and re-scaling ó, we derive that
Ek
Pkv Gk
G
60 6
PoV H
T
Pb
Gia
VAK
VH
A
+
/mee
log
8
Vt E [T],
k=1
F
which leads to that
1=1 4 -1)
Vgk
G
6o
GoppoVH
T
A <
log
VA E [T]
(65)
A
Vmne1
8
Putting together.
Note that the estimations in 59
60 and (65) are established based on the
probability events in (42) and Lemma B.5 these estimations, we have
Then, using (61
Po defined in (6) and 61 vmn
oo_ into
3
GE
20 log Lco
(
A S
Pk
AA
8
k=
Gk
48A0 (1 + log T))
B
4
Pk
A
Leğ
2T
2 H(1
log
2xg(1 lloog T)
C
(66)
mnei
Leg
Then, plugging (66) into 62). it leads to that
|
l1
Gk
60 log
T
2L
S f(Xi) -
Pk
VA
+
Lco
8
F
224 + A0) + +og
(67)
Leg
With both sides multiplying 2L, we derive that
G
12o
Ao
T
|G++1lli < 2L(f(X1) - f4)
Pk
Ax
F
+
CO
log
8
47o(24 + 1o) + log T)
G
< 3
Pk
< H2
(68)
A
where H is defined in 5 The induction is complete, and we prove the desired result.
B.4 Proof of Theorem 6.1
The final convergence bound is established based on the probabilistic events in which thereby holds with probability at least 25. As a consequence of 68)
42 and Lemma B.5
G
L
2
1 < H
(69)
Moreover, using Lemma
B
Proposition B.I and E co/ sl//mmn, we have
(k)
Vmnei S EH voo,
wk [T].
(70)
Thereby, with Po/
1-
c/2
we have
T
G
T
Pk G 22
G
Pa
Pk
A
F
1= maxi,j / aij
(k)
EH + /co
k1-of2
(71)
Combining with (71) and (69) and using ΣT 1/k- o/2
1/22 > 1/2 we derive that
H [E va)
min | < KE
po L/
24

---

B.5 Proof of Corollary 1
Here, we let constant. We still suppose that the probability events in (42) and Lemma Le hold. Then, all the lemmas in Section still hold as they only require 32.1 = 1/2, $2, E [0, 1). Also, the estimation for A in (65) remains unchanged. Following the similar deduction in (58) and applying 32,1 = 1/2.
Po/VT,k [T], 82,1 = 1/2 and f2,6 = 32 = 1 1 = 2.... . be
B2,k = 32 = = 1/T, k 2 2 and ps: Po/ ee/V2 VT, we have
G
48po D.G mndi
(222
Σ
B <
4
A R
2T
T
k=
F
k=
G
E6po
Pk
(72)
A
mne
k=
Following the similar deduction in (60 and using Pk: -Po/ Po/VTT
2T. mnei
D T
2T 2T.p
C
(73)
mine
Thereby, with the similar induction argument based and Lemma B.5 proabability at least 26, (69) and the following results hold
derive that with
D. max |Galle S H, E, S En, 9. H. At E kE
(74)
when H, H and En are as in (5) and
1
0
min VH 2 H3/2
(75)
ΣH H
Hence, we will derive the convergence rate based on the probabilistic events in 42 which thereby holds with probability at least 1 - 25. Since 82,1 = 1/2, $2 E 0. 1), and holds, we can get that
and Lemma B.5
co/ mn
(k) a
S
EH + vou,
Vk [7].
Following the same result in 711.. and using Pk: po/ we have for any h: E [T].
T
G
2
T
Pk ||Gille
G
Pe
Pk
2
(76)
V
A
k
F
k=
maxi.j V
dij
(k)
En +
Then, combining 69
we get the desired result that
G H² (E + voo)
Σ
PoLVT
C Proof detail for stochastic Adafactor with update clipping
C.1 Proof preliminary
We follow the notation definitions of DR. Σ5 and G5 in (40). Next, define
G
G max /u/lF// (da mmn))
(77)
Since R.S((u)) ||Ux|FF/ / the update rule for Adafactor becomes
G
X = X Pk WE
(78)
25

---

C.2
Bounding gradient magnitude
Before proving the main convergence result, we still need control the gradient magnitude through an induction argument in the following proposition. The proof detail, however, is different from the one for Proposition We will rely on some techniques the analysis of algorithms with standrad clipping.
Proposition C.1. Following the conditions and notations of Theorem 7.1 al least 26,
it holds that with probability
DR S. Eg S Et,
9k SI,
vk E (T).
Proof. Using the inequality in Lemma
A.2 and 78)) we have
T
f(X++1) $ f(x)) (G Xx11 X&)
+
Xx-1 Xx11
Gk VW
Lp
G
f(xs)) Pk
G
2
VW
Subtracting f" on both sides and summing up both sides over E
[t]. we have for any & 2 1,
G
G L
f(X(+1) - S f(x))
f +
Ps
Gk:
(79)
W
2
W
F
Introducing A₁ defined in (41
we further have the following decomposition,
Gk
(Ge,.
D
Pk
Gk.
AR
+
Pk
VAR
VW
G
l= 1
k=
D.1
Gk
Pk
+.1
1/ A
k=1
F
G
G VAg
GR
G VÆ
Pk
G1:
Ez
Pk:
Gi,
E Z
(80)
VA
A
k=1
D.2
D.3
In the following estimations, D.1. E and D.3 are established based on the probability event in (2)) whereas D.2 does not rely on (42). First, based on 42) 777 and D2, Σn defined in (40), we have
||Gx||e DR.
|| IF | + |. Galle Ex.
||Ga|l < |Gulle Ex. (81)
Hence, under (42). get that
||Ez, [G&llr & Ez, | I Ez, G
cT Ez, | Galle Do + o
< Ezz G
log
Eg.
(82)
Estimating E. Under
42
we can use G3 defined in (7p. Lemma B.4 and
8T
to verify that
Gx
|G (K)
&
4 mne?
(83)
VW
min.,i wig
min,,; w
(k)
Using Ak Pa/k: 10/2 & Pa/ VT. Ex S E,, Ix I Gr, Vk < f and we derive that
Lp
4
2L
2L 2
+ logt)
E
<
(84)
2
mne
mne
mne
where the last inequality applies Lemma A.I
26

---

Estimating D.1
We can follow the similar deduction in 57
and
58
to derive that
(k) (k)
D.1 <
96j 9is
(K)
Wis
(k) (k)
Oig 96
(k)
(2)
Pk
10
Oij
(K)
k=1
W
m
P6
(k)
8
m
03j
sj
(R)
2
Pk
Pk
(85)
(K)
(k)
(k)
k=
Under 42
we can apply Lemma
B.6
Gk I
Gr.
1k: S L, and
83 into
85
to derive that
Gk
GR
D.1
Pk
12
PVV
82,
A
WW
k=1
$
Σ
1
Gk 2
48E2
9/22
Σ Pk PkV
32,
(86)
4 km
V
mnej
Using Pk Po/k 1/22
c/2
82,8
1 1/k and Lemma
A.1
we further have
G
48p Egg
3/2 (1 +1+10 log t)
D.1
Pk
(87)
A
mne?
k=1
Estimating D.2.
Since Ag is independent from Zs. it leads to
D.2 = Σ Pk VAR
Gt
Gx Eze (Gu))
Let 9p -pk
G. ( VA. G and A measurable with FR-1- Since & is measurable with Fk. could prove that {pp))21 a martingale difference sequence by showing that
G Ez,
Gx and the filtration Fu = (Zz, ..,,,..,2 Zx). Note that Pk.
E 1pk
Fx-1l = -ph
Gx
Ez, Gx
Ez, [Gal 0.
AAx
Using that || < ||Gxll and ||G&|l S DR. we derive that
G Ez, G+ (I|Gxlle Ez, }
< (I[ - G+ Ir | |r + Ez, IG: GKllF + Ez, /
$ (IG₂ - GxIFF - Ez, Gk - GxllF
+ (ell=+27 2Dx)²²
(88)
Letwo = 4E inequality,
G₂
which is measurable with Fx-1- We thus derive from the Seuucy-Schwarz
A
888) and
Σt. D/ < Σx.
Gx VAr
||G
Ez, [Ga]13
22t (2
E exp
F
$ E
cxp
Frc-1
GL 1 1692
VAa
2( G
Gx + Ez, G Gxlle)2 + &D&
< E
exp
FA-1
1622
GG - Gx 11 + (Ez, G - Gr(ll)))
<
E
exp
[
exp(1122
402
G GA 1 + Ez, G G [5(-1
< E
exp
2
eexp(1/2)
27

---

Using Jensen's ss inequality, we get that
Ez, Gk
Gxll
G
Ge112.
B
exp
- E
Ez
exp
FR-11
4
402
|
Gkll2
=
E
exp
[x-1
40
Using Jensen's inequality and the definition of Lub-Gaussian noise, further have
exp
G G+
Fe-1
E
cxp
Gk - Gall2
[Fo-.)
1/4
I c2/4
2
σ²
Combining the above, we get that E leads to that for any > O, with probability at least
exp
(wL
F S c. Then, using Lemma B.1 and (42).
8, for all & [7].
G2
T
D.2
Σ Ph S 12A
Σ
+ log
VAR
8
(k)
Pk
Dij
T
12x
(k)
Pk
(k)
log
8
(89)
aij
Estimating D.3.
First, since A is independent from Z& and Ez, [Gk]
Gk. we have
Ez,
[
Ez,
D.3
Pk
Gk
VAx
VAk
k=1
G
Ge max (1, Uxlle (dx mn)
Pk
Ez,
Gk
(90)
A
k=1
Then, we will estimate Ez, Qt under the event in 42 and consequently
14
that we restate here:
|Gillr
Ex, vk [T).
(91)
[E(k]
We note that Ez, Qr is a random variable depending only on { , and Zk can be replaced by any Z that is i.i.d. with Z..... Zk-1 and we shall use the similar notations such as E- 52' and U for the corresponding variables with Z₁ replaced by Z Then, we define the indicator functions Sg.1 1 and St,2 follows,
Z
S SI
Sk.2 X(lee 13.00 log( (}))
Using Hölder's inequality and 82 we derive that,
Ezj
| alll Sp.2 S v Ezz 1 v EEz [$2
S EEz G
15 & En T
where the last inequality uses the following result since Zi,... Z and Z is independent from Z,,..., Zk-1.
42 holds, SE.2 is dependent from
ef' (ef)
Ez,15t. [5. = P [| 0² 2blog log
Zi,
Zz-1 5 7
We next define the indicator functions Sk.1, Sk.2 and St, as follows,
Sk.1 = Sk.1. Sk.2 = X| /mn Sa.1. Sk.1
Sk.1- dymner (1ccolle2
2
28

---

Under 91 and the event of Sk.1, we can use the similar deduction in Lemma B.4 to derive that
G S Ghil
2
Ukll = VWA F
& ||
|G S Ex-
(92)
minej V (wly
y
Vmnci
Consequently, we have Sx,1 I Sx,1 from 92 Note that when Sn,2 1, implies that S2 Oxxm- Then, we derive that
Ezz [1 Sk.1 Swal
= ||E Ezi [St + Ezz (k.2k
< Ezy [ 12/1 f1 - Ezj
5x.1 ||
S Ezy
Sk,1 |G
where the last inequality applies || < ||/Gle S Σx. Using that O3 and Σg are indepedent from
||G frr from 90 Note that when St = 1, demnei S
2
Z and noting that 1, we have
2V
Bz SE.1 G s Ezz
S |
G
1-a
2x
demney
From the above analysis, we derive that under 91).
2/9
Ez. [xlll
B [2
S
E
Ed
(93)
T
dEmne1
Under 911. we can use Lemma B.4 to get that,
Gx
GGxlIF
2D
(94)
VA F
ming.j
Vaig
(k)
Vmnii
Combining with 90
93 and 94 and using Pk Po/k 10/2 c (0, 2 ke/2 and Lemma
A.1 we derive that under 91
DaVER Vmnci
2V
D.3
EKV T
De
dymne
k=1
Doo
Σ.Vo +2 Eg
(1 + log T',
(95)
VITiE
miEE1
where the last inequality further uses D₃ < Dr, En S D, Gx S G. when &s S t.
An induction argument. The induction argument is based the probability events in 42 and
189 thereby the desired result holds with probability at least 1 - 26. First, we can easily verify that (*) < 12 from Lemma A.2 Let suppose that for some [T].
DJ
((((
D2 T consequently,
Σg S E,,
Gk < I,
Vk E [1].
(96)
Since 42) holds, we can first use Pk Po/k 2/2 cCE E [0, 11. 42 and Lemma B.4 to derive that
2
2po /gk
Pk
Po.
(97)
IT
o/2
/mnce
/mncc
Plugging 197) into (89 and re-scaning 8, it leads to that for any X > O, with probability at least - 25,
D.2
24Xpo
PE
9k
G VA
log
{
T
V7 E [T].
V Vmne1
Setting À (/mner)/ (9653 VIpo) where E, I are as in Theorem 7.1 we then derive that
G
96EVVIpo log
D.2 <
AI E [7].
(98)
EJVI
A
Vmnc1
km
29

---

Then, we can plug the estimations (84
87
(98
and
95
into
80)
and
79). and use
96 to get that
G
48po I3 (1 log T)
f(X(11) - S
f(x)
2
Σ
Pk
V Ax
mnc
1=
T
2pol V Vmnci
2VI
log Vmnce1
EIVo + En
(1 + log T)
mn66]
2 + +og log
(99)
mi
Recalling the condition for pa in 10 and 6j = co/ mmn then using |G4+1lB S ( -f* from Lemma A.2
G
2v8(1
+ log T) Ao
S f((1)
Pk
+
2L
2 R=1
VA
Co
L
(4820 + (1 + log T)
962u log
T
2 do + llog 7)
+
+
Lej
Lco
8
L [mm) 12
With both sides multiplying 2L, we obtain that
G
Pk
<
(100)
k=1
F
where 7 defined in (9) Then, the induction complete, and we prove the desired result.
L
C.3 Proof of Theorem
The final convergence bound is established based on 44 and probability least 1 28. As a consequence of (1O)..
89
which thereby holds with
T
Pk
k
S 12
-| / S S.
(101)
A
1=1
Under 42 we can use Lemma B.4
and Proposition C.1 to get that azj
S E + min S
Σ3 + mmee for all [T]. With co/ /// and pk Po/ kk2-k/
have
T
G
2
T Pk G 11
G
Σ
1=1
Pk
V A
1= maxi,j /o15
(K)
Pa
C0
k1-c/2
(102)
Using Ete 1/k² c/2 > T we derive that
min kE[T
T PVE
LLLT S
12
(To log
(eT' (
+ /co
PoLTe12
C.4 Proof of Corollary 2
Here, we let Ph: P [T], 82, 1/2 and 32.4 B2 1--/TT, 2,3. T
Setting 82 = 1 1/T and Pk po/ VT. the estimations in 84 (98) and (95) remain unchanged Indeed, these estimations can be further tighten by replacing
under the probability event in
42
Ei=1 F 1 + logt with Et=
< 1. The minor difference comes from the estimation of D.1.
Following the similar deduction
85
and (6). and using the new setups for Pk and $2 we have
48po E/9
D.1 <
Pk
V2T
4
VA
MIRE
2 T
G2
96po E2g
Pk
(103)
4 k=1
A
mine
30

---

Thereby, with the induction argument and the probability events in 422 and (89) we can still verify that with probability least 1 26, (T00) and the following inequalities hold
D& S 1. Ex S.nn Er,
9x SI,
e [T],
(104)
when
0< 0< Po S À
min
(105)
EJVI 2X E,VI I(EIVI)
Hence, we establish the convergence rate based on the (2) and 89), which thereby holds with probability at least 1 - 26. Since 82,1 = -1/2, B E 1), 2 2 and é1 = co/ so/vin mn, we can use Lemma B.4 and Proposition C.I to get that
(
> min(m, S 23 MInei vk [2].
Then, using Pk = Po/ T, we have
T
Pk Gi
G
2
Gx || VT
Σ
Pk
Po
(106)
A
maxij Val)
+
Then, combining (101).
we get the desired result that
T
Σ
T
G
1 1VVE+
c
12
(100
log
cT o
+ vco)
POINT
POTNT
D
Some complementary experiments
All the experiments are conducted using the fairseq implementation of Adafactor and the Hugging Face implementation of Adam two NVIDIA GeForce RTX 4090 GPUs. The pretrained models of BERT-Base/Large and GPT-2 are also downloaded from Hugging Face.
D.1 Experiments on Adafactor without update clipping
We conduct experiments on BERT-Base and BERT-Large using the GLUE/MNLI benchmark, and on GPT-2 using the BookCorpus dataset. All models are trained with the Adafactor optimizer without update clipping, under the parameter setting 32.x = 1 1/k and pk = po/ks, where the decay rate ranges over {0.6, 0.7, 0.8, 0.9, 1.03. Additionally, we compare the optimal performance under our setup (with e = 1) against both the default Adafactor configuration proposed by (38), that is, 32 1 1/10.8 and py = pa/ V VE, and the Adam optimizer with 3, = 0.9, 32 = 0.999.
Each experiment is conducted over three epochs with batch size of 128 for BERT-Base/ Base/Large and batch size of 8 for GPT-2. The base learning rate Pa is selected via a two-stage grid search. First, we search over the coarse grid {1, 0.1, 0.01, 0.001, 0.0001}. Then, based on the best candidate (e.g.. 0.001), we refine the search by evaluating its surrounding values with step-size equal to one-tenth of the candidate value (e.g.. x 10-1), 1), and choose the pert-perforning learning rate. All training loss curves and test accuracy results are presented in Figures Figure 3 and Table
Our results show that both convergence rates and test accuracy consistently improve as the decay rate e increases from 0.6 to 1.0, with the best performance achieved = which aligns well with Theorem 6.1 The training loss at = 1 is slightly better or comparable to that under the default Adafactor setting. However, test accuracy is marginally worse, which may be attributed to overfitting under this configuration.
Furthermore, the best performances of Adafactor (at 1) for training BERT-Base and BERT-Large are comparable to that of Adam, suggesting that the reduced memory overhead in Adafactor does not necessarily compromise convergence speed generalization performance.
31

---

1.0
Default
Default
Adam
c=1.0
Teining Loss
0.9
c-1.0
0.8
Training
0.7
0.5
Step
Step:
(a) BERT-L Large GLUEMNII
(h) GPT-2 on BookCorpus dataset
Figure 2: Training loss of Adafactor (no update clipping) with c c= or default setup, and Adam
1.0
C-0.9
c=10
c-0.6
co0.7
1.0
Default
Adam
Traiing Lo3s
0.9
0.9
c- 1.0
0.7
0.6
0.5
0.5
Step
Step
(a) BERT-BaaE GLUE/MNLI
(b) BERT-BaREE GLUE/MNII
Figure 3: Training loss vs steps of Adafactor (no update clipping) with different c
Table The test accuracy after epochs. We use Adafactor (no update clipping) and Adam train BERT-Base and BERT-Large on GLUE/MNLI.
c == 0.6
c 0.7
c
c 0.9
c 1.0
Default
Adam
BERT-Large
74.78%
77.32%
78.90%
80.65%
82.28% 80.24%
82.35% 80.64%
83.28% 82.56%
BERT-Base
70.08%
72.91%
75.56%
79.68%
D.2 Experiments on Adafactor with update clipping
We further test our newly proposed increasing clipping threshold in Theorem 7.1 and compare it with the standard setting where dy = 1. We fix = 1 which is the optimal selection in our theory and use
dj = h -1) with {2.0, 4.0, 5.0, 7.0, 9.0, 12.0}. The other settings keep the same as the ones in Section D.I We report the training loss curves in Figure and test accuracy in Table
Table 2: The test accuracy after 3 epochs. We use Adafactor with different clipping thresholds to train BERT-Base/lLarg GLUE/MNLI.
2.0
a 4.0
5.0
7.0
a 9.0
12.0
d =
BERT-Large 82.84%
82.88%
82.79%
82.21
82.78%
82.43% %
81.94% 81.28%
BERT-Base
81 81.65%
81.61 %
81.18%
81.08%
82.01 %
81.71 %
The results indicate that the increasing clipping thresholds lead to comparable performance the constant one as well as Adam. In addition, compared Table with the test accuracy of c = in Table I. it's clear see that adding update clipping can enhance the performance, particularly when there no learning rate warm up. This finding is also aligned with the experimental results in [8
32

---

1.1
a 2.0
9.0
1.0
a
4.0
12.0
a 5.0
d=1
Training Loss
0.9
a
7.0
0.8
0.7
0.6
0.5
0.4
0
2000
4000
6000
8000
Step
BERT- BERT-Large on GLUE/NNI
1.1
2.0
9.0
a= 4.0
a a= 12.0
1.0
a= 5.0
d=1
Training Loss
0.9
a 7.0
0.8
0.7
0.6
0.5
0.4
0
10000
20000
30000
40000
Step
(b) BERT- Base on GLUE/MNI
Figure 4: Training loss vs steps of Adafactor with different update clipping thresholds
33

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the Abstract and Introduction parts.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section 10
34

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Theorem 5.1 Theorem 6.1 and Theorem 7.1 and their corresponding proofs.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Section
g
Guidelines:
The answer NA means that the paper does not include experiments.
35

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibilityy which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our code based on Pytorch package which standard. addition, we have clarified the detailed experimental setup in our paper and the experiments are easy to reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https:/nnips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g.. for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 7/nips. wwwpcccccccc//....c....c...eetle hwublic/guuids//// CooeeSumisssii sssssoooiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
36

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We do not provide error bars, but instead explain how we report the results in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We use NVIDIA 4090 GPU.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
37

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://berrppp...ppbbbbb//ccccc
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
38

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
39

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy hbtp:://eeerrppscccc///feeeeeeee for what should or should not be described.
40


Reviews:
[{"review_id": "TgHPmtrID7", "reviewer": "Reviewer_qPLs", "summary": "The paper analyzes the convergence rate to a stationary point of Adafactor.", "questions": "# Suggestions\n1. Some symbols look too close to each other, I suggest changing some of them.\n    1. $c$ and $c_0$ have different purposes, but almost identical symbols.\n    2. $G_k$ and $\\mathbf{G}_k$ looks almost identical. I think that bold text is not enough to differentiate between symbols.\n2. The corollaries are not a direct result of the theorem as they use different $\\beta_{2,k}$. I think the paper should clarify that the proofs of the corollaries are in the appendix.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n1. For the deterministic case, the paper proves an optimal convergence rate $\\mathcal{O}(1/T)$ for Adafactor.\n2. For the stochastic case, the paper proves a near-optimal convergence rate $\\mathcal{O}(1/\\sqrt{T})$ for Adafactor.\n\n# Weaknesses\n1. Some things are not written in the most clear way. More details are written in the suggestions.", "was_revised": true, "final_justification": "The authors have addressed all the points I mentioned.\nHowever, the paper only analyzes the convergence rate to a stationary point of Adafactor. This was already analyzed for other algorithms, thus limiting the theoretical significance of this paper.", "rebuttal": "We appreciate the reviewer’s comments. We address the reviewer’s concerns point by point below:\n\n> *Some symbols look too close to each other, I suggest changing some of them.*\n\n**Re.** We will revise some symbols that may be confused by readers. Particularly, for what the reviewer suggests on $c,c_0$ and $G_k,{\\bf G}_k$:\n\n- We will change the decay rate parameter notation from $c$ to $\\gamma$, e.g., in Formula (7), Line 179, and Line 206;\n- We will use ${\\bf G}_k$ to denote the stochastic gradient at $k$-th iteration and change the notation $G_k$ to $D_k:=\\max\\_{j \\in [k]}\\\\|\\nabla F(X\\_k)\\\\|\\_F$, e.g., in Line 224 and Line 467. \n\n---\n\n> *I think the paper should clarify that the proofs of the corollaries are in the appendix.*\n\n**Re.** We will add the following statement in the revised version:\n\n- ‘**The detailed proof can be found in Appendix B.2.**’ in Line 194;\n- ‘**The detailed proof can be found in Appendix C.4.**’ in Line 223.\n\n---\n\nWe would be glad to elaborate further if there are any remaining concerns."}, {"review_id": "kzxXGy90im", "reviewer": "Reviewer_NfZt", "summary": "The paper studies the convergence of the Adafactor algorithm for smooth non-convex functions. It provides convergence rates under sub-Gaussian noise that match the optimal rate up to log factors for this class of functions.", "questions": "-  Can your approach work with smoothness with operator norms instead of Frobenius?\n\n- What about other smoothness assumptions like $(L_0,L_1)$?", "limitations": "Maybe more general smoothness assumptions and operator norms.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is clearly written and does a good job introducing the algorithm for readers who might not be super familiar, and it also does a good job explaining the challenges that were faced in obtaining such theoretical results.  \n- The theoretical analysis is interesting for the community: ideas used here for dealing with the one rank approximation and the clipping of Adafactor can be potentially used for other methods.\n\nWeaknesses (minor):\n- The theory assumes smoothness and bounds the noise in terms of the Frobenius norm, this norm hides (in the worst case) a factor that is proportional to the dimension compared to operator norms (associated to $\\ell_2$ for example). \n- I can also go on about smoothness that is known not to hold for NNs, but we have to start somewhere. It would be nice if this could be extended to more general smoothness assumptions.", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s comments. We address the reviewer’s concerns point by point below:\n\n> (a). *The theory assumes smoothness and bounds the noise in terms of the Frobenius norm; this norm hides (in the worst case) a factor that is proportional to the dimension compared to operator norms (associated to $\\ell_2$-norm for example).* (b). *Can your approach work with smoothness with operator norms instead of Frobenius?*\n\n**Re.** We thank the reviewer for this insightful question. Note that the smoothness assumption with respect to a general norm is:\n\n$$\n\\\\|\\nabla f(Y) - \\nabla f(X)\\\\| \\le L\\\\|Y-X\\\\|_{*},\n$$\n\nwhere $\\\\|\\cdot \\\\|$ and $\\\\|\\cdot \\\\|_{*}$ are dual norms. In this paper, we consider the smoothness with standard Frobenius norm $\\\\|\\cdot\\\\|_F$, which is self-dual, and it is aligned with the standard smoothness definition in terms of $\\ell_2$-norm in the stochastic optimization.\n\nWe agree that using the operator norm could be meaningful in some aspects. For instance, by adopting the induced $\\ell_2$-norm $\\\\|\\cdot \\\\|_{2 \\rightarrow 2}$, the dual norm is the nuclear norm.  In this case, one could establish a descent lemma based on the operator norm and potentially follow similar proof techniques in our paper to derive a convergence guarantee. However, for this moment, the answer is not very clear, which deserves further study.\n\nWe also kindly remind that, although the operator norm could avoid the dimension, the dimension factor may emerge in its dual norm. For example, the nuclear norm may also introduce implicit dependencies on the dimensions without making additional assumptions.\n\n---\n\n> (a). *I can also go on about smoothness that is known not to hold for NNs, but we have to start somewhere. It would be nice if this could be extended to more general smoothness assumptions.* (b). *What about other smoothness assumptions like $(L_0,L_1)$?*\n\n**Re.** We agree with that the standard $L$-smoothness assumption may not always hold for neural networks in some practical cases. Developing theory to more general smoothness conditions—such as the $(L_0,L_1)$-smoothness [1] is indeed valuable. However, such generalizations could be nontrivial, especially because the gradient norm can be unbounded and thus may complicate convergence analysis. We think that the point can be a promising direction for future work, which will be added in **Limitation** part as follows:\n\n**The convergence results for Adafactor are established under the standard smoothness assumption. It would be interesting to further investigate convergence under more general smoothness conditions that better reflect practical applications, such as $(L_0, L_1)$-smoothness.**\n\n---\n\nWe would be glad to elaborate further if there are any remaining concerns.\n\n**References.**\n\n[1] Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity, Zhang et al., ICLR 2020.\\\n[2] The Geometry of Sign Gradient Descent, Balles et al., arXiv 2020.\\\n[3] Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization, Zou et al.,arXiv 2021."}, {"review_id": "TWtmPtqYIH", "reviewer": "Reviewer_8wZR", "summary": "The paper provides the theoretical analysis of Adafactor for nonconvex objectives under standard smoothness and stochastic gradient assumptions. The proof techniques are extended from those used to analyze the convergence of earlier adaptive stepsize algorithms such as Adam. The convergence rates are comparable to those of Adam.", "questions": "- The introduction before formulation (1) is slightly too narrow. Adafactor and other adaptive stepsize algorithms are proposed to optimize neural networks with multiple matrices instead of only one matrix. Could authors revise the introduction?\n\n- In Figure 1, could authors also compare Adam's training curve with Adafactor's? This would convince the reader about the effectiveness of the implementation of Adafactor.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- Adafactor is an important memory-saving adaptive stepsize algorithm, and its theoretical analysis would be important for practitioners and theoreticians as well. \n\n- The writing is clear. Assumptions and theoretical results are clearly stated. The new techniques are properly highlighted in Section 8.\n\nWeakness\n\n- The value of $c_0$, which is related to $\\epsilon_1$ according to Theorem 6.1, should be the order of $10^{-30}$ based on [37]. This may result in super large constants $H$ and $I$. Authors may also discuss the theoretical implications of small $\\epsilon_1$.\n\n-  One motivation of Adafactor is reducing memory cost from $O(mn)$ to $O(m+n). Therefore, it is better to also make the dependence on $m$ and $n$ explicit in Theorem 5.1, Theorem 6.1, and Theorem 7.1.", "was_revised": true, "final_justification": "Authors have addressed my concerns regarding $\\epsilon$ in the rebuttal. Authors also acknowledge that the problem formulation could be more general. I thus keep my support for the paper.", "rebuttal": "We appreciate the reviewer’s comments. We address the reviewer’s concerns point by point below:\n\n> *The value of $c_0$ , which is related to $\\epsilon_1$ according to Theorem 6.1, should be the order of $10^{-30}$ based on [37]. This may result in super large constants $H$ and $I$ .*\n\n**Re.** We appreciate the reviewer’s careful observation. Note that the relationship between $\\epsilon_1$ and $c_0$ is:\n\n- In Theorem 5.1, we require $\\epsilon_1 = \\frac{c_0}{mn}$;\n- In Theorems 6.1 and 7.1, we require $\\epsilon_1 = \\frac{c_0}{\\sqrt{mn}}$.\n\nSince the dimension $mn$ could be large in some practical examples, $\\epsilon_1$ will naturally be small even when $c_0$ is a moderate constant. This allows us to set $c_0$ as a small, fixed constant without needing to choose it on the order of $10^{-30}$. Our theoretical setup for $\\epsilon_1$ suggests the use of a small value that could be roughly in line with the typical setting, though there may be a gap between the theoretical and practical setups. We will make this clearer in the revision.\n\n---\n\n> *Therefore, it's better to also make the dependence on $m$ and $n$ explicit in Theorems 5.1, 6.1 and 7.1.*\n\n**Re.** We appreciate this valuable suggestion. We will add the following discussion on the dimension dependency:\n\n- After Theorem 5.1: **We can set  $\\rho_0 \\sim \\mathcal{O}((mn)^{-1})$ to derive a convergence bound of $\\mathcal{O}(mn)$ with respect to the dimension for full-batch Adafactor.** \n- After Theorem 6.1: **We can set $\\rho_0 \\sim \\mathcal{O}(\\mathcal{H}^{-3/2}) \\sim \\mathcal{O}((mn)^{-3/4})$ given that $H^2 \\sim \\mathcal{O}(1) $ and $\\mathcal{H} \\sim \\mathcal{O}(\\sqrt{mn})$. With the setup, the convergence bound is $\\mathcal{O}((mn)^{ 3/4})$ with respect to the dimension for stochastic Adafactor without update clipping.**\n- After Theorem 7.1: **We can set $\\rho_0 \\sim \\mathcal{O}(\\mathcal{I}^{-3/2}) \\sim \\mathcal{O}((mn)^{-3/4})$ given that $I^2 \\sim \\mathcal{O}(1)$ and $\\mathcal{I} \\sim \\mathcal{O}(\\sqrt{mn})$. With the setup, the convergence bound is $\\mathcal{O}((mn)^{ 3/4})$ with respect to the dimension for stochastic Adafactor with an increasing clipping threshold.** \n\nWe will also add the following comparison to some existing results for memory-unconstrained adaptive methods right after Theorem 6.1:\n\n**Under the non-convex smoothness optimization setting, [1] and [2] derive convergence bounds of at least $\\mathcal{O}(mn)$ with respect to the dimension for AdaGrad. [3] derives a convergence bound of $\\mathcal{O}(mn)$ with respect to the dimension for RMSProp (where they considered $\\ell_1$-norm as the measurement). For Adam, many existing works [4, 5, 6] derive convergence bounds with a $\\mathcal{O}(\\text{poly}(mn))$ dependency, while [7] derives a dimension-free convergence bound. Our convergence bounds show comparable dimension dependency to most results for AdaGrad and Adam, though a gap remains toward achieving fully dimension-free guarantees, and improving the dimension dependency could be further investigated in the future.**\n\n---\n\n> *The introduction before formulation (1) is slightly too narrow. Adafactor and other adaptive stepsize algorithms are proposed to optimize neural networks with multiple matrices instead of only one matrix. Could the authors revise the introduction?*\n\n**Re.** We really appreciate the reviewer for pointing this out. In Formula (1), we follow the standard setup in stochastic optimization where $X$ represents **all** the trainable weights in a model, e.g., the combination of weight matrices in each layer of a deep neural model. We will add the following statement after Formula (1) to clarify this:\n\n**where $X$ denotes all the trainable weights of the model**. \n\nWe also recognize that Adafactor applies its matrix factorization separately to each weight matrix (e.g., per-layer weight matrices) when training multi-layer models. Therefore, a more precise interpretation is that $X$ consists of a set of matrices $\\\\{X^{(i)}\\\\}_{i=1}^L$, where each $X^{(i)} \\in \\mathbb{R}^{m_i \\times n_i}$ corresponds to a layer-wise weight matrix. \n\nOur theoretical analysis treats $X$ as a unified matrix in $\\mathbb{R}^{m \\times n}$ to simplify the convergence analysis while still capturing the essential behavior of Adafactor. We believe that it would be an interesting direction for future work to analyze convergence under a per-matrix (i.e., layer-wise) factorization setting, which more closely reflects the practical implementation in training multi-layer models.\n\n---\n\n> *In Figure 1, could authors also compare Adam's training curve with Adafactor's? This would convince the reader about the effectiveness of the implementation of Adafactor.*\n\n**Re.** Thanks a lot for this helpful suggestion. We have included the comparison of Adafactor (with decay rate $c=1.0$) with Adam in Figure 2(a), Figure 3(b) and Table 1 from Appendix D.1. We will add Adam's training loss curve in Figure 1 in the revised version to make the comparison more direct and accessible.\n\n---\n\nWe would be glad to elaborate further if there are any remaining concerns.\n\n**References.**\n\n[1] High Probability Convergence of Stochastic Gradient Methods, Liu et al., ICML 2023.\\\n[2] Revisiting Convergence of AdaGrad with Relaxed Assumptions, Hong and Lin, UAI 2024.\\\n[3] On the $O({d\\over T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\\ell_1$-Norm, Li et al., 2024.\\\n[4] A Simple Convergence Proof of Adam and Adagrad,  Défossez et al., TMLR 2022.\\\n[5] Adam Can Converge Without Any Modification On Update Rules, Zhang et al., NeurIPS 2022.\\\n[6] Closing the Gap Between the Upper Bound and the Lower Bound of Adam’s Iteration Complexity, Wang et al., NeurIPS 2023.\\\n[7] Convergence of Adam Under Relaxed Assumptions, Li et al., NeurIPS 2023."}, {"review_id": "xKEhuG77CQ", "reviewer": "Reviewer_zkWc", "summary": "This work establishes convergence guarantees for the Adafactor algorithm in non-convex smooth optimization. Adafactor is analyzed in the deterministic case, the stochastic case without clipping, and in the stochastic case with clipping under a slight modification from a fixed clipping threshold to a time-dependent tuned threshold. Experiments on language tasks are provided to demonstrate the relationship between a theory-related parameter ($c$) and the training loss.", "questions": "1. While this work is mainly focused on the dependence on $T$, can the authors compare the established result to other adaptive methods (Such as AdaGrad, Adam, and Shampoo. Not necessarily all of them) in terms of the dependence on the dimension? From what I gather, the dependence is linear in the deterministic case and super-linear in the stochastic case.\n2. Can the authors conjecture of other methods whose theoretical analysis might benefit from the tools developed in this work?\n\nOverall, this work contributes to our understanding of adaptive methods by providing convergence guarantees for the Adafactor method, while the established guarantees are yet to indicate why such methods perform so well in practice.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. It is of value to have proper convergence guarantees for practical methods, in order to better understand the proposed methods and to support future improvements.\n2. An analysis of a method such as Adafactor requires handling several technical challenges, which the authors detailed in their work. It is often the case that techniques introduced in one method can help in the analysis of other closely related methods.\n\n**Weaknesses**\n\n3. Beyond establishing the convergence of Adafactor (which is of value of its own), I do not see how the analysis leads to new and meaningful conclusions. This is in addition to the fact that Adafactor, or variants of it, is not a widely used method.\n4. A weakness of this work, which often appears in the analysis of such methods, is the sub-optimal bounds (in terms of problem parameters) compared to vanilla SGD. It would be beneficial to demonstrate a somewhat general setting (under additional but reasonable assumptions) where Adafactor has improved convergence compared to SGD. This is minor as this weakness is shared across several works on the topic of adaptive methods, but solving it can contribute to the significance of this work.", "was_revised": true, "final_justification": "As I mentioned in my review, AdaFactor is somewhat an outdated algorithm, limiting the significance of the result. That said, I still think it may be beneficial for future work, leading me to my limited yet positive support of this work.", "rebuttal": "We appreciate the reviewer’s comments. We address the reviewer’s concerns point by point below:\n\n**Weaknesses.**\n\n> *Beyond establishing the convergence of Adafactor (which is of value of its own), I do not see how the analysis leads to new and meaningful conclusions.*\n\n**Re.** We really appreciate the reviewer’s recognition of the value of our work. Beyond providing the first convergence guarantee for Adafactor, we believe our convergence analysis may yield some interesting conclusions:\n\n- **Comparable convergence rate to Adam:** Although Adafactor is derived as a memory-efficient variant of Adam, our theoretical results could show that its convergence bound matches that of Adam up to logarithmic factors (in terms of $T$) in non-convex smooth optimization setting. Our simple NLP experiments also complement the comparable training performance; see Figure 2(a), Figure 3(b), and Table 1 in Appendix D.1.\n- **Potentially transferable proof techniques:** As Reviewer NfZt points out, *“ideas used here for dealing with the rank-one approximation and clipping of Adafactor can be potentially used for other methods.”*  Our techniques may inspire convergence proofs for other memory-efficient algorithms using matrix approximations, such as GaLore and CAME.\n\n---\n\n> *This is in addition to the fact that Adafactor, or variants of it, is not a widely used method.*\n\n**Re.** We acknowledge that Adafactor is not as widely used as Adam. Nevertheless, we think that analyzing Adafactor could be an interesting topic for the optimization community. As an early memory-efficient optimizer based on matrix approximation, it has served as a standard baseline in numerous works proposing new memory-efficient algorithms, such as GaLore, CAME, and MicroAdam. Also, several LLMs, including PaLM, T5, UL2, and GShard, have adopted Adafactor as one of their main training optimizers.\n\n---\n\n> *A weakness of this work, which often appears in the analysis of such methods, is the sub-optimal bounds (in terms of problem parameters) compared to vanilla SGD. It would be beneficial to demonstrate a somewhat general setting (under additional but reasonable assumptions) where Adafactor has improved convergence compared to SGD. This is minor as this weakness is shared across several works on the topic of adaptive methods, but solving it can contribute to the significance of this work.*\n\n**Re.** \n- We acknowledge this point but note that achieving the same (or better) parameter dependencies as SGD may be inherently difficult for Adafactor: \n  - **Theoretical limitation.** It has been shown that SGD is minimax optimal among stochastic first-order methods for non-convex smooth optimization [1]. The convergence improvement is therefore impossible, provided that only smoothness is assumed.\n  - **Trade-off due to memory efficiency.** Adafactor is designed as a memory-efficient variant of Adam. Given the information it discards, it remains unclear whether it's possible to achieve the same or even better parameter dependency as Adam or SGD.\n \n- We agree that it is possible to demonstrate improved convergence performance of Adafactor over SGD under additional but reasonable assumptions. In fact, prior studies have shown that adaptive methods such as AdaGrad and Adam can outperform SGD in certain settings—for example, when the gradient noise is heavy-tailed [2], when the Hessian is highly imbalanced [3, 4], or when the Hessian is nearly block-diagonal [5]. Extending these lines of analysis to Adafactor would be a promising direction for future work.\n\n---\n\n**Questions.** \n\n> *can the authors compare the established result to other adaptive methods (Such as AdaGrad, Adam, and Shampoo. Not necessarily all of them) in terms of the dependence on the dimension?*\n\n**Re.** Thanks a lot for this valuable suggestion. We will add the following discussion on the dimension dependency:\n\n- After Theorem 5.1: **We can set  $\\rho_0 \\sim \\mathcal{O}((mn)^{-1})$ to derive a convergence bound of $\\mathcal{O}(mn)$ with respect to the dimension for full-batch Adafactor.** \n- After Theorem 6.1: **We can set $\\rho_0 \\sim \\mathcal{O}(\\mathcal{H}^{-3/2}) \\sim \\mathcal{O}((mn)^{-3/4})$ given that $H^2 \\sim \\mathcal{O}(1) $ and $\\mathcal{H} \\sim \\mathcal{O}(\\sqrt{mn})$. With the setup, the convergence bound is $\\mathcal{O}((mn)^{ 3/4})$ with respect to the dimension for stochastic Adafactor without update clipping.**\n- After Theorem 7.1: **We can set $\\rho_0 \\sim \\mathcal{O}(\\mathcal{I}^{-3/2}) \\sim \\mathcal{O}((mn)^{-3/4})$ given that $I^2 \\le \\mathcal{O}(1)$ and $\\mathcal{I} \\sim \\mathcal{O}(\\sqrt{mn})$. With the setup, the convergence bound is $\\mathcal{O}((mn)^{ 3/4})$ with respect to the dimension for stochastic Adafactor with an increasing clipping threshold.** \n\nWe will also add the following comparison to some existing results for memory-unconstrained adaptive methods right after Theorem 6.1: \n\n**Under the same conditions of non-convex smoothness, [6] and [7] derive bounds of at least $\\mathcal{O}(mn)$ with respect to the dimension for AdaGrad. [8] derives a convergence bound of $\\mathcal{O}(mn)$ with respect to the dimension for RMSProp (where they considered a better $\\ell_1$-norm). For Adam, many existing works [9, 10, 11] derive $\\text{poly}(mn)$ dependency while [12] derive a dimension-free convergence bound. Our convergence bounds show comparable dimension dependency to most results for AdaGrad and Adam, though a gap remains toward achieving fully dimension-free guarantees, and improving the dimension dependency could be further investigated in the future.**\n\n---\n\n> *Can the authors conjecture of other methods whose theoretical analysis might benefit from the tools developed in this work?*\n\nWe suspect that other methods may benefit from our approach in the following points:\n\n- We design a proxy step-size based on the matrix factorization structure of Adafactor to decouple the correlation of adaptive step-size parameters and stochastic gradients. The construction may be beneficial for other memory-efficient optimizers that also apply the matrix factorization, such as GaLore and CAME;\n- We reveal that with a proper setup of clipping threshold, convergence is also guaranteed under the unique update clipping of Adafactor. This update clipping, which uses the root-mean-square to calibrate the second-moment estimator, is different from the standard clipping mechanism. Our techniques may be useful when incorporating this update clipping to other adaptive methods. \n- We use an induction argument to control the unbounded gradient. We believe that it could be used for the analysis of other adaptive methods.\n\n---\n\nWe would be glad to elaborate further if there are any remaining concerns.\n\n**References.**\n\n[1] Lower bounds for Non-Convex Stochastic Optimization, Arjevani, et al., Mathematical Programming, 2023.\\\n[2] Why are Adaptive Methods Good for Attention Models? Zhang et al., NeurIPS 2020.\\\n[3] Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models, Kunstner et al., NeurIPS 2024.\\\n[4] AdaGrad under Anisotropic Smoothness, Liu et al., ICLR 2025.\\\n[5] Why Transformers Need Adam: A Hessian Perspective, Zhang et al., NeurIPS 2024.\\\n[6] High Probability Convergence of Stochastic Gradient Methods, Liu et al., ICML 2023.\\\n[7] Revisiting Convergence of AdaGrad with Relaxed Assumptions, Hong and Lin, UAI 2024.\\\n[8] On the $O({d\\over T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\\ell_1$-Norm, Li et al., 2025.\\\n[9] A Simple Convergence Proof of Adam and Adagrad,  Défossez et al., TMLR 2022.\\\n[10] Adam Can Converge Without Any Modification On Update Rules, Zhang et al., NeurIPS 2022.\\\n[11] Closing the Gap Between the Upper Bound and the Lower Bound of Adam’s Iteration Complexity, Wang et al., NeurIPS 2023.\\\n[12] Convergence of Adam Under Relaxed Assumptions, Li et al., NeurIPS 2023.\\\n[13] Noise is not the Main Factor behind the Gap between SGD and Adam on Transformers, but Sign Descent might be, Kunstner et al., ICLR 2023.\\\n[14] Implicit Bias of Adamw: Norm Constrained Optimization, Xie and Li, ICML 2024.\\\n[15] The Implicit Bias of Adam on Separable Data, Zhang et al., arXiv: 2406.10650."}]

Author rebuttal:

Meta-review: This paper presents the first convergence analysis of Adafactor in the setting of nonconvex smooth optimization. To the best of my knowledge, such a result is novel and a timely contribution. The analysis is clearly written and technically sound, with the authors providing satisfactory responses to several technical concerns raised during the review process. There are two key limitations: (1) the theoretical results do not explicitly demonstrate the advantage of Adafactor in terms of convergence rate compared to existing optimizers; (2) the assumption of smoothness may not hold for neural networks. Nonetheless, given the originality of the contribution, the clarity of exposition, and the addressed reviewer feedback, I recommend acceptance. The authors are expected to discuss the limitations explicitly in the final version of this paper.
Decision: Accept (poster)