Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad
Authors: Sayantan Choudhury
Nazarii Tupitsa
Nicolas Loizou
Samuel Horváth
Martin Takáč
Eduard Gorbunov
Venue: NeurIPS 2024 poster (2024)
Keywords: Scale-invariant methods
AdaGrad
non-convex optimization
adaptive methods
Primary area: optimization

Abstract: Adaptive methods are extremely popular in machine learning as they make learning rate tuning less expensive. This paper introduces a novel optimization algorithm named KATE, which presents a scale-invariant adaptation of the well-known AdaGrad algorithm. We prove the scale-invariance of KATE for the case of Generalized Linear Models. Moreover, for general smooth non-convex problems, we establish a convergence rate of  $O((\log T)/\sqrt{T})$ for KATE, matching the best-known ones for AdaGrad and Adam. We also compare KATE to other state-of-the-art adaptive algorithms Adam and AdaGrad in numerical experiments with different problems, including complex machine learning tasks like image classification and text classification on real data. The results indicate that KATE consistently outperforms AdaGrad and matches/surpasses the performance of Adam in all considered scenarios.

Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad
Sayantan Choudhury"
Nazarii Tupitsa MBZUAI & Innopolis University
MBZUAI & Johns Hopkins University
Nicolas Loizou Johns Hopkins University
Samuel Horváth MBZUAI
Martin Takáč MBZUAI
Eduard Gorbunov MBZUAI
Abstract
Adaptive methods extremely popular in machine learning they make learning rate tuning less expensive. This paper introduces a novel optimization algorithm named KATE, which presents scale-invariant adaptation of the well-known Ada- Grad algorithm. We prove the scale- invarianeee of KATE for the case of Generalized Linear Models. Moreover, for general smooth non-convex problems, a convergence rate of ((loTT/VT) for KATE, matching the best-known ones for AdaGrad and Adam. We also compare KATE to other state-of-the-art adaptive algorithms Adam and AdaGrad in numerical experiments with different prob- lems, including complex machine learning tasks like image classification and text classification on real data. The results indicate that KATE consistently outper- forms AdaGrad and matches/surpasses the performance of Adam in all considered scenarios.
establish
Introduction
In this work, consider the following unconstrained optimization problem:
minwer=s(w).
(1)
where ʃ Rd a L-smooth and generally non-convex function. In particular, we are interested
in the situations when the objective has either expectation f(w) = Eş Ee<DDJe [[(w)) finite-sum f(w) = = [i(w) form. Such minimization problems are crucial in machine learning, where w corresponds to the model parameters. Solving these problems with stochastic gradient-based optimizers has gained much interest owing to their wider applicability and low computational cost. Stochastic Gradient Descent (SGD) (Robbins and Monro, 1951) and similar algorithms require the knowledge of parameters like L for convergence and are very sensitive the choice of the stepsize in general. Therefore, SGD requires hyperparameter tuning, which can be computationally expensive. To address these issues, it is common practice to adaptive variants of stochastic gradient- based methods that can converge without knowing the function's 's structure.
There exist many adaptive algorithms such AdaGrad (Duchi et al., 2011), Adam (Kingma and Ba, 2014), AMSGrad (Reddi et al., 2019), D-Adaptation (Defazio and Mishchenko, 2023), Prodigy (Mishchenko and Defazio, 2023), AI-SARAH (Shi et al., 2023) and their variants. These adaptive techniques are capable updating their step sizes on the fly. For instance, the AdaGrad method determines its step sizes using cumulative sum of the coordinate-wise squared (stochastic) gradient
Part this work was done when Choudhury was an intern at MBZUAL, UAE.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

of all the previous iterates:
Agu
AdaGrad: W++1 Wa
diag
+ Σ 5-1
g-
where Sr represents an unbiased estimator of (w,)), i.e., E [gt we] (w,)), diag(M) Rd is vector of diagonal elements of matrix M E Rd A > O, and the division by vector is done component-wiss Ward et al. (2020) has shown that this method achieves a convergence rate of O (/v)) for smooth functions, similar to SGD, without prior knowledge of the functions' param- eters. However, the performance of AdaGrad deteriorates when applied to data that may exhibit poor scaling ill-conditioning. In this work, we propose novel algorithm, KATE, address the issues of poor data scaling. KATE is also a stochastic adaptive algorithm that can achieve a convergence rate of O (logT/VI) for smooth non non-convex functions in terms of ( E [ (wx)lll)
1.1 Related Work
A significant amount of research has been done adaptive methods over the years, including AdaGrad (Duchi et al., 2011; McMahan and Streeter, 2010), AMSGrad (Reddi et al., 2019), RMSProp (Tieleman and Hinton, 2012), AI-SARAH (Shi et al., 2023), and Adam (Kingma and Ba, 2014). However, all these works assume that the optimization problem is contained a bounded set. To address this issue, Li and Orabona (2019) proposes variant of the AdaGrad algorithm, which does not use the gradient of the last iterate (this makes the step sizes of (-th iteration conditionally independent of g+) for computing the step sizes and proves convergence for the unbounded domain.
Each of these works considers a vector of step sizes for each coefficient. Duchi et al. (2011) and McMahan and Streeter (2010) simultancously proposed the original AdaGrad algorithm. However, McMahan and Streeter (2010) was the first to consider the vanilla scalar form of AdaGrad, known as
3g.
AdaGradNorm: W1+1 = W/
+ Et ||==11
Later, Ward et al. (2020) analyzed AdaGradNorm for minimizing smooth non-convex functions. In a follow-up study, Xie et al. (2020) proves linear convergence of AdaGradNorm for strongly convex functions. Recently, Liu et al. (2022) analyzed AdaGradNorm for solving smooth convex functions without the bounded domain assumption. Moreover. Liu et al. (2022) extends the convergence guarantees of AdaGradNorm to quasar-convex functions 2 using the function value gap. Orabona et al. (2015) introduce the notion of scale-invariance, which is special case of affine invariance (Nesterov and Nemirovskii, 1994; Nesterov, 2018; d' Aspremont et al., 2018), propose a scale- invariant version of AdaGrad for online convex optimization for generalized linear models, and prove O ((T) regret bounds in this setup.
Recently, Defazio and Mishchenko (2023) introduced the D-Adaptation method, which has gathered considerable attention due to its promising empirical performances. In order to choose the adaptive step size optimally, one requires knowledge of the initial distance from the solution, i.c., = |lwo w.| where w. E argmin fw). The D-Adaptation method works by maintaining an estimate of D and the stepsize choice in this case is dt/VEt- I|g=1| 2I for the t-th iteration (here de is an estimate of D). Mishchenko and Defazio (2023) further modifies the algorithm in follow-up work and introduces Prodigy (with stepsize choice dt //V/E. d 1[ to improve the convergence speed.
Another exciting line of work on adaptive methods is Polyak stepsizes. Polyak (1969) first pro- posed Polyak stepsizes for subgradient methods, and recently, the stochastic version (also known as SPS) was introduced by Oberman and Prazeres (2019); Loizou et al. (2021); Abdukhaki- mov et al. (2024, 2023); Li et al. (2023) and Gower et al. (2021). For finite sum problem f:(w))-f? min f(w) == 1 Ei fi(w), Loizou et al. (2021) uses e (.,.) as their stepsize choices (here J == minger= Se(w)), while Oberman and Prazeres (2019) uses E [ tion. However, these methods are impractical when f* or f is unknown. Following its introduction,
2(f(w))- for k-th itera-
2 satisfy f f(w)= (f(w), w- - w) for some < (0, 1] where w frg)

---

a[k] Table 1: Summary of convergence guarantees for closely-related adaptive algorithms to solve smooth non-convex stochastic optimization problems. Convergence rates are given in terms of minkelr E [[;)](
We highlight KATE's scale-invariance property for problems of type (4),
Algorithm
Convergence rate
Scale invariance
AdaGradNorm (Ward et al., 2020)
O (log T/VT)
x
AdaGrad (Défossez et al., 2020)
O (lox T/vT)
X
Adam (Défossez et al., 2020)
(loR T/VT)
KATE (this work)
O (loRT/vT)
several variants of the SPS algorithm emerged (I.i et al., 2023; D'Orazio et al., 2021). Lately, Orvieto et al. (2022) tackled the issues with unknown J and developed truly adaptive variant. In practice, the SPS method shows excellent empirical performance on overparameterized deep learning models (which satisfy the interpolation condition i.c. f; 0, Vi [n]) (Loizou et al., 2021).
1.2 Main Contribution
Our main contributions are summarized below.
new scale-invariant version of AdaGrad. We propose new method called KATE that can seen as a version of AdaGrad, which does not use a square root in the denominator of the stepsize. To compensate for this change, we introduce a new sequence defining the numerator of the stepsize. We prove that KATE scale-invariant for generalized linear models: the starting point zero, then the loss values (and training and test accuracies in the case of classification) points generated by KATE are independent of the data scaling (Proposition 2.1). mcaning that the speed of convergence of KATE is the same as for the best scaling of the data.
KATE:
Convergence for smooth non-convex problems. We prove that for smooth non-convex prob- lems with noise having bounded variance KATE has Ollg(())/ convergence rate (Theorem 3.4), matching the best-known rates for AdaGrad and Adam (Défossez et al., 2020).
Numerical experiments. We empirically illustrate the scale-invariance of KATE on the logistic regression task and test its performance on logistic regression (see Section 4.1), image classification, and text classification problems (see Section 4.2). all the considered scenarios, KATE outperforms AdaGrad and works either better or comparable to Adam.
1.3 Notation
,n. as [n]]. For vector a Rdd, a[k] is the k-th coordinate of a and a² We denote the (1,2....,
represents the element-wise suqare of a, i.e., a²[k] = (a(k))) For two vectors and b, 5 stands for element-wist wise division and i.e., k-th coordinate & is
bja Given function Rd + IR we V/ E Id to denote its gradient and V hh to indicate the k-th component of Vh. Throughout the paper represents the æg-norm and f. = inf fww). Moreover, we use ||l]|a for a positive- definite matrix A to define ||||| == V Aw. Furthermore, E [-] denotes the total expectation while E, []] denotes the conditional expectation conditioned on all iterates up to step /. i.e. wo, W1,-. Wt-
2 Motivation and Algorithm Design
We focus on solving the minimization problem (1) using variant of AdaGrad. We aim to design an algorithm that performs well, irrespective of how poorly the data is scaled.

---

Generalized linear models. Here, we consider the parameter estimation problem in generalized linear models (GLMs) (Nelder and Wedderburn, 1972; Agresti, 2015) using maximum likelihood estimation. GL.Ms are an extension of linear models and encompass several other valuable models, such as logistic (Hosmer Jr et al., 2013) and Poisson regression (Frome, 1983), as special cases. The parameter estimation to fit GLM on dataset (.,, U4 ) (where Jy R are feature vectors and y; are response variables) can reformulated as
min f(w) wERd
Pi (z, w)
(4)
n
for differentiable functions 9; R R Schalev-Shwarde and Ben- 2014; Nguyen al., 2017b; Takáč et al., 2013; He et al., 2018; Chezhegov et al., 2024). For example, the linear regression on data (zi, Me 12 is equivalent solving (4) with (p((2) (z yz)². Next, the choice of yo for logistic regression is spr(2) = log (1 + exp (-):
Scale-invariance- Now consider the instances of fitting GLMs two datasets {I,, 14 ) and (Vz,, P: where V E Rddd is a diagonal matrix with positive entries. Note that the second dataset is a scaled version of the first one where the k-th component of feature vectors i; are multiplied by scalar V&L. Then, the minimization problems corresponding to datasets { Us ) and Vr, 3i are (4) and
min (V WERd
9x Vw).
(x.
respectively, for functions Pt: In this work, we want to design an algorithm with equivalent perfor- mance for the problems (4) and (5). If we can do that, the new algorithm's 's performance will not deteriorate for poorly scaled data, i.c., the method will be scale-invariant (Orabona et al., 2015), which is a special case of affie-invariance, see (Nesterov and Nemirovskii, 1994; Nesterov, 2018; d' Aspremont et al., 2018). To develop such an algorithm, we replace the denominator of AdaGrad step size with its square (remove the square root from the denominator), i.e., Ak E [d]
3m, [k]
Wh+ [k]
Σ 9² k [c]
66)
for some m, E IRd 3 The following proposition shows that this method (6) satisfies a scale-invariance property with respect to functional value.
Proposition 2.1 (Scale invariance). Suppose we solve problems (4) and (5) using algorithm (6). Then, the iterates úú and to!" corresponding to (4) and (5) follow: Vk [d]
Bm [k]
(
ib [k]
9e [e),
Σ 00 2
[R]]
Bm [k]
2 91 [k]
(8)
Σt= (of [k]]
with g- = (I,) )x,, and of = (x,, V (r for i chosen uniformly from [m].
0, s......,.f
t, t 2 0. Moreover, updates (7) and (8) satisfy
w. = Vw Vg: = sh, I (w))= = V (vol)
(9)
for all f 2 0 when dhp = w. 0 Rd Furthermore we have
|1 11-
(10)
The Proposition 2.1 highlights that the update rule of the form (6) satisfies scale-invariance property for GLMs. contrast, AdaGrad does not satisfy (9) and (10). In Appendix C, we illustrate numerically the scale-invariance of KATE and the lack of the scale-invariance of AdaGrad. We also emphasize that AdaGrad with A is known to be a scale-free method'.
Sequence (mehgga can depend on the problem but assumed to be scale-invariant. 'The algorithm is called scale-free if for any e > 0, it generates the same sequence of points for functions and ef given the same initialization and hyperparameters. To the best of our knowledge, this definition is

---

Algorithm 1 KATE
Require: Initial point wo 1R step size 3 > 0, E R4 and 6-1, m_ 0.
I: for t= 0, 1, ..... I" do
2: Compute 9t R² such that [ v(w)).
3: by = =,,-. o
4: mi m + 192 +
5:
Wx+1
Wir
BEres by
St
Design of KATE. In order to construct an algorithm following the update rule (6), one may choose me[k] = Ak E [d]. However, the step size from (6) in this case may decrease very fast, and the resulting method does not necessarily converge. Therefore, we need more aggressive choice of me, which grows with f. It motivates the construction of our algorithm KATE (Algorithm 1),² where
we choose [,[k] 6n[]]p[[||
+ Σr=
g2 kg
Note that the term Σ
k
is scale-invariant
84 [
for GLMs (follows from Proposition 2. To make scale-invariant, we choose 1) E R in the following way:
- 0: When is very small, m, is also approximately scale-invariant for GLMs.
7 \/(Vf(wo)) In this case n6ū ((mo)) is scale-invariant for GLMs (follows from Proposition 2.1) as well as
KATE be rewritten in the following coordinate form Wh+1 [k] w, [k] vs [k]]
Vk E [d].
(11)
where Or is an unbiased estimator of V fw;,) and the per-coefficient step size v/ [k] is defined
3 n [[k]] + Σt
1/4 [
(12)
[
Note that the numerator of the steps [k] is increasing with iterations t. However, of the crucial properties of this step size choice is that the steps always decrease with I, which we rely on in our convergence analysis.
Lemma 2.2 (Decreasing step size). For [k[kk] defined in (11) we have
| < v: [k], vk E [d].
(13)
Comparison with the scale-invariant version AdaGrad by Orabona et al. (2015). In the special case of GLMs, Orabona al. (2015) propose different version of AdaGrad. The method is proposed for the case online convex optimization, and the case of standard optimization with GLMs (4), it has the following form
El V fi, (w,
We = O, Wr+1 ==
a, == max
(14)
a3 ad 72 Et (V.1,
r=0,..,f
where f are arbitrary indices from [n] (e.g., selected uniformly at random), functions f; Rd ++ are defined as fi(w) == (x w) for i [m]] and 7 such that f((w) 7-Lipschitz for i [n]. In this setup, the update rule of KATE with Wo 0 can be written as follows:
W4+1 == 3
mr V.r(w:))
m, =
n Σ [w, + 7=0
62
T=0
introduced Cesa-Biande Bianchi et al. (2005. 2007) in the context of learning with expert advice and extended context of generic online convex optimization by Orabona and Pal (2015, 2018). We emphasize that fealeefreeness scale-invariance are completely different concepts.
Note that, for Vt we get the AdaGrad algorithm.

---

where by = Virzo (1,,()) {i-)==o are sampled from [n] uniformly at random. Although
both methods can be seen as variations of AdaGrad due to the terms Σi (V/1 )² and Ex= fi- (w, (w)))² respectively, the scale-invariance is achieved quite differently in these methods. The method from (14) uses the feature vectors explicitly in the update rule to ensure scale-ine inveriinariance:: indeed, the square root the definition of w(+1 is independent of scaling, and af in the denominator ensures that w = Vie4 if we define them similarly to KATE (see equations (7)-(8).. In contrast, KATE achieves the seale-ivvrrianee by removing the square root from the denominator (as explained earlier). Moreover, unlike the method from (14), KATE does not use the feature vectors explicitly in its update rule (only the gradients of Ji,) and, thus, can be used for general stochastic optimization (not necessarily for the case of GLMs).
3 Convergence Analysis
In this section, we present and discuss the convergence guarantees KATE. the first subsection, list the assumptions made about the problem.
3.1
Assumptions
In our theoretical results, we assume that f is smooth as defined below.
Assumption 3.1 (L-smooth). Function f is L-smooth, i.e. for all w, w' E Rd
L f(w') S f(w) + (Vf(w), w/ wo + ||w w²ll?
(15)
This assumption is standard in the literature adaptive methods (Li and Orabona, 2019; Ward et al., 2020; Liu et al., 2022; Nguyen et al., 2018. 2021, 201 7a; Beznosikov and Takáč, 2021). Moreover, we assume that any iteration of KATE, we can access 9t a noisy and unbiased estimate of (((x).. We also make the following assumption the noise of the gradient estimate Gr-
Assumption 3.2 (Bounded Variance). For fixed constant a >> 0, the variance of the stochastic gradient St. (unbiased estimate of V (wx) )) at any time satisfies
Eg [llg. V f(ww)]]]] S 02.
(BV)
Bounded variance is a common assumption to study the convergence of stochastic gradient-based methods. Several assumptions on stochastic gradients are used in the literature to explore the adaptive methods. Ward et al. (2020) used the BV, while Liu al. (2022) assumed the sub- Weibull noise, i.e.
E exp - (/ww))
I exp (1) for some 0 > 0, to prove the convergence of AdaGradNorm. Li and Orabona (2019) assumes sub-Gaussian (0 1/2 in sub- sub-Weibull condition) noise to study a variant of AdaGrad. However, sub-Gaussian noise is strictly stronger than BV. Recently, Faw et al. (2022) analyzed AdaGradNorm under more relaxed condition known affine variance (i.e E, |lg. - ((())] < of + oo [V,((,)))
3.2 Main Results
In this section, cover the main convergence guarantees of KATE for both deterministic and stochastic setups.
Deterministic setting. We first present results for the deterministic setting. In this setting, consider the gradient estimate to have no noise (i.e. σ² = 0) and gr = v.(ww). The main result in this setting is summarized below.

---

Theorem 3.3. Suppose f satisfy Assumption 3.1 and = Vf(we). Moreover, 3 > 0 and n[k] > 0 are chosen such that 2/1 k] S t for all ls E [d]. Then the iterates of KATE satisfies
2(flwo)-(a) +Ek bolkk)
2
min [V[(W)
vial
T+1
where 7/u = min n.].
Discussion on Theorem 3.3. Theorem 3.3 establishes an O (?/r) convergence rate for KATE, which is optimal for finding first-order stationary point of non-convex problem (Carmon et al., 2020). However, this result is not parameter-free, To prove the convergence, we assume that volk] S
L vk E [d] in Theorem 3.3, which is equivalent to 3 8 + no (VrJ(wo)))² S (vo)( (wo))), /L, Vk E [d]. Note that the later condition holds for sufficiently small (dependent on L) values of 3, >
However, is possible to derive a parameter-fre version of Theorem 3.3. Indeed, Lemma 2.2 implies that the step sizes are decreasing. Therefore, we break down the analysis of KATE into two phases: Phase I when vn [k) > 1/1 and Phase II when vo [k] < 1/z, when the current analysis works, and then follow the proof techniques of Ward et al. (2020) and Xie et al. (2020). We leave this extension as a possible future direction of our work.
Stochastic setting. Next, present the convergence guarantees for KATE in the stochastic case, when we can access an unbiased gradient estimate Ir with non-zero noise.
Theorem 3.4. Suppose f satisfy Assumption 3.1 and ge is an unbiased estimator of f such that BV holds. Moreover, we assume fVf(w: (w:) 1|2 I 7² for all t. Then the iterates of KATE satisfy
|l96|| T
2(7 +o) VT
1/2
2C,
< min E V ST
3/100
where Y/o min kkk] and
C₁ = f(wo) - ff + 280
k= V /n/[] log
(c(02
gā(k)
+ +
L L
log
celor +1²
2
25
96 [4]
Comparison with prior work. Theorem 3.4 shows an O (TT1'// convergence rate for KATE with respect to the metric min E [|] V fw:)))l for the stochastic setting. Note that, in the stochastic setting, KATE achieves a slower rate than Theorem 3.3 due to noise accumulation. Up to the logarithmic factor, this rate optimal (Arjevani al., 2023). Similar rates for the same metric follow from the results of (Défossez et al., 2020) for AdaGrad and Adam.
Finally, Li and Orabona (2019) considers a variant of AdaGrad closely related to KATE:
Bg.
Wi+1 = Wi
(16)
2 tc
diag AI + Et
for some E [0, 1/2) and A > O. It differs from AdaGrad in two key aspects: the denominator of the stepsize does not contain the last stochastic gradient, and also, instead of the square root of the sum of squared gradients, this sum is taken in the power of 1/2 + E. However, the results from Li and Orabona (2019) do not imply convergence for the case of & 1/2. which expected since, this case, the stepsize converges to zero too quickly in general. To compensate for such a rapid decrease, in KATE, we introduce an increasing sequence m, the numerator of the stepsize.
Dééfossez et al. (2020) derive (/VTT) convergence rates for AdaGrad and Adam terms of mingrr E [I [wx](( which is smaller than minegr (E [[:))(()))))))
7

---

Proof technique. Compared to the AdaGrad, KATE uses more aggressive steps (the larger nu- merator of KATE due to the extra term E+= 12)1) Therefore, we expect KATE to have better empirical performance. However, introducing Σ [ in the numerator raises additional technical difficulties in the proof technique. Fortunately, as we rigorously show, the KATE steps v [k] retain some of the critical properties of AdaGrad steps. For instance, they (i) are lower bounded by
AdaGrad steps up to constant, (ii) decrease with iteration (Lemma 2.2), and (ii) have closed-form
upper bounds for -i 2 9 [e]. These are indeed the primary building blocks of our proof technique.
Numerical Experiments
In this section, we implement KATE in several machine learning tasks to evaluate its performance. To ensure transparency and facilitate reproducibility, provide access to the source code for all of our experiments at https: hete:://gittin //gg/ttttt///////////// com www.//oo///accaeeeeeae nazya//ATz.
4.1 Logistic Regression
In this section, we consider the logistic regression model
min f(w) WERd
log (1 + exp (-yer, w)),
(17)
2=1
to elaborate the scale-invariance and robustness of KATE for various initializations. For the experiments of this Section 4.1, we used Mac mini (M1, 2020), RAM GB and storage 256 GB. Each of these plots took about 20 minutes run.
4.1.1 Robustness of KATE
To conduct this experiment, we set the total number of samples to 1000 (i.c. n = 1000). Here, we simulate the independent vectors
18 such that each entry is from (000, 1). Moreover, generate diagonal matrix V E 220x20 such that log V& we generate w² 2220 with each component from A 1) and set the labels
iid Unif(- 10, 10), wk: E [20]. Similarly,
{1, L, -1,
x Vu" 2 0, 2, V."
y/ -
E
< 0,
We compare KATE's performance with four other algorithms: AdaGrad, AdaGradNorm, SGD- decay and SGD-constant, similar to the section 5.1 of Ward et al. (2020). For each algo- rithm, we initialize with We size 10 to update the weight vector We compare the algorithms AdaGrad with stepsize SGD-decay with stepsize
E R220 and independently draw a sample of mini-batch
3
AdaGradNorm with step size
VA+2 9/AVEI, and SGD-constant with step size 3/3. Similarly, for KATE use stepsize Bms b
VA+2%
where m n7, + b - 0²/02 and b3 -f g². Here, we choose f(wu) f(w") and vary A in {10 10 10 10 1, 102 10 10 10%).
In Figures/ la. 1b, and Ic. we plot the functional value f(w:) (on the y-axis) after 10 5 10 and 105 iterations, respectively. In theory, the convergence of SGD requires the knowledge of smoothness constant I.. Therefore, when the small (hence the stepsize large), SGD-decay and SGD-constant diverge. However, the adaptive algorithms KATE, AdaGrad, and AdaGradNorm can auto-tune themselves and converge for a wide range of As (even when the A is too small), As we observe in Figure 1, when the A is small, KATE outperforms all other algorithms. For instance, when = 10 KATE achieves a functional value of 10-3 after only 1 iterations (see Figure la), while other algorithms fail to achieve this even after 10y iterations (see Figure Ic). Furthermore, KATE performs as well as AdaGrad and better than other algorithms when the A is large. In particular, this experiment highlights that KATE is robust to initialization A.
4.1.2 Peformance of KATE on Real Data
In this section, we examine KATE's performance on real data. We test KATE on three datasets: heart, australian, and splice from the LIBSVM library (Chang and Lin, 2011). The response variables y, of
8

---

101
Km)
100
(a) Plot of (wx)
(b) Plot of Accuracy
(c) Plot of Gradient Norm
Figure 1: Comparison of KATE with AdaGrad, AdaGradNorm, SGD-decay and SGD-constant for different values of A (on r-axis for logistic regression model. Figure la, lb and Ic plots the functional value (w+) (on y-axis) after 10", x 10 and 10 iterations respectively.
012
OFT1 Acpurattion
523 recoer
(a) Dataset: heart
(b) Dataset: australian
(c) Dataset: splice
Accurdy
ACCUrsCy
00
2008
2000
3000
2088
280
2000
(d) Dataset: heart
(c) Datasct: australian
(f) Dataset: splice
Figure 2: Comparison of KATE with AdaGrad, AdaGradNorm, SGD-decar and SGD-constant on datasets heart, australian, and splice from LIBSVM. Figures 2a, 2b and 2c plot the functional value f (we), while 2d, 2e and 2f plot the accuracy y-axis for 000 iterations.
each of these datasets contain two classes, and we use them for binary classification tasks using a (wo))) for KATE and tune 3 in all the experiments. For tuning 3, we do a grid search on the list (10-10, 10-8 10-6 10-4, 10-2, 1]. Similarly, we tune stepsizes for other algorithms. We take 5 trials for each of these algorithms and plot the mean of their trajectories.
logistic regression model (17). We take
We plot the functional value (w,) (i.e. loss function) in Figures 2a, 2b and 2c, whereas Figures 2d, 2e and 2f plot the corresponding accuracy of the weight vector w; on the y-axis for 5, 000 iterations. We observe that KATE performs superior to all other algorithms, even on real datasets.
4.2 Training of Neural Networks
In this section, we compare the performance of KATE, AdaGrad and Adam on two tasks, i.e. training ResNet18 (He et al., 2016) on the CIFARI0 dataset (Krizhevsky and Hinton, 2009) and BERT (Devlin et al., 2018) fine-tuning on the emotions dataset (Saravia et al., 2018) from the Hugging Face Hub. We use internal cluster with the following hardware: AMD EPYC 7552 48-Core Processor, 512GiB RAM, NVIDIA A100 40GB GPU, 200gb user storage space.
General comparison. We choose standard parameters for Adam (3, 0.9 and B2 0.999) that are default values in PyTorch and select the learning rate of 10- for all considered methods. We run KATE with different values of 77 {0, 10 10 10-22. For the image classification task, we normalize the images (similar to Horváth and Richtárik (2020)) and use a mini-ban bini-batch size of 500. For the BERT fine-tuning, we use mini-batch size 160 for all methods.
Figures 3-8 report the evolution of top-1 accuracy and cross-entropy loss (on the y-axis) calculated on the test data. For the image classification task, observe that KATE with different choices of

---

Accuracy
Accoracy
Sterutiots
Am
310
37t Iterations
3738
Iteratiars
CrusErtrapptass
Constrrappt
Dila Iteratians
640
150
260
2013
100
Iterations
Iterations
Figure 4: CIFARIO: 7
Figure 5: CIFAR1O:
Figure CIFARIO: 7j 0
0.001
0.1
Accorscy
1891
Iterations
Aterratiars
CrossEttrop repptttopooo
CrossEst rosssitroojoos roppios
5
crondtet
200 2i
201
251
1234 138 2000
Figure 7: Emotion: 0.001
Figure 6: Emotion: 17 =
Figure 8: Emotion: 7 = 0.1
y outperforms Adam and AdaGrad. Finally, we also observe that KATE performs comparably to Adam the BERT fine-tuning task and is better than AdaGrad. These preliminary results highlight the potential of KATE to be applied for training neural networks for different tasks. For BERT each run takes about 35 minutes, and 25 minutes for ResNet.
Elyper-parameters tuning. Next, compare baselines presented in Saravia et al. (2018) for emotions classification and Zhang et al. (2019) for image classification. These papers provide efficient setups for learning rates and learning rate schedulers that are reasonable to compare with. Saravia al. (2018) performs search of efficient learning rate and uses a linear learning rate scheduler with warmup for Adam optimizer. A different learning rate (le-5), A=le-5 and the same scheduler applied for KATE lead to the same performance, see Figure 9. We would like to point out that it is challenging find a reference for hyper-parameters for a certain setup. Thus, to fairly compare with Saravia al. (2018) we use distilroberta- base model. Zhang et al. (2019) did a grid search for an efficient learning rate and used a multi-step scheduler for Adam optimizer, decaying the learning rate by factor of 5 at the 60th, 120th, and 160th epochs. Zhang et al. (2019) refers Drieies and Taylor (2017) for the code implementing special techniques, namely data augmentation and cutout to achieve higher accuracy. different learning rate (Ie-3), the same scheduler and A=le-3 applied for KATE demonstrates comparable performance, see Figure 10. For Figure 10: Emotion: 7) 0.001 BERT each run takes about 20 minutes, while 100 minutes for ResNet.
fart farr
Just atcureec
471
Iterations
Figure 9: Cifar 0.001
Epochs
10

---

Acknowledgments and Disclosure of Funding
We thank Francesco Orabona and Dmitry Kamzolov for the pointers to the related works that we missed while preparing the first version of this paper. We also thank anonymous reviewers for their useful feedback and suggestions.
References
Ahdukhakimov, F., Xiang, C., Kamzolov, D., Gower, R., and Takáč, M. (2023). Sania: Polyak-type optimization framework leads to scale invariant stochastic algorithms. arXiv preprint arXiv:2312.1336
Ahdukhakimov, F., Xiang, C., Kamzolov, D., and Takáč, M. (2024). Stochastic gradient descent with precondi- tioned polyak step-size. Computational Mathematics and Mathematical Physics, 64(4):621-634.
Agresti, A. (2015). Foundations of linear and generalized linear models. John Wiley & Sons.
Arjevani, Y., Carmon, Y., Duchi, C., Foster, D. J., Srebro, N., and Woodworth, B. (2023). Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2):15-214,
Beznosikov, A. and Takáč, M. (2021). Random-reshuftld sarah does not need full gradient computations. In Optimization for Machine Learning Workshop @ NeurIPS 2021.
Carmon, Y., Duchi, C., Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points i. Mathematical Progrumming, 184(1-2):71-120,
Cesa-Bianchi, N., Mansour. Y., and Stoltz, G. (2005). Improved second-order bounds for prediction with expert advice. In International Conference on Computational Learning Theory, pages 217-232. Springer.
Cesa-Bianchi, N., Mansour, Y., and Stoltz, G. (2007). Improved second-order bounds for prediction with expert advice. Machine Learning, 66:321-352.
Chang, C.-C. and Lin, C.-. (2011). Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27.
Chezhegov, S., Skorik, S., Khachaturov, N., Shalagin, D., Avetisyan, A., Beznosikov, A., Takáč, M., Kholodov, Y., and Gasnikov, A. (2024). Local methods with adaptivity via scaling, arXiv preprint axXiv224660088
d' Aspremont, A., Guzman, C., and Jaggi, M. (2018). Optimal affine-invariant smooth minimization algorithms. SIAM Journal on Optimization, 28(3):238422405
Defazio, A. and Mishchenko, K. (2023). Learning rathingg--rt-tteee rate-free learning by D-adaptation. arXiv preprint arX11:2301.07731.
Défossez, A., Bottou, L., Bach, F. and Usunier, N. (2020). A simple convergence proof of adam and adagrad. arXiv preprint arX1v:2003.02305
Devlin, J.. Chang, M.W.,, Lee, K., and Toutanova. K. (2018). BERT: Pre- Pre-training of deep bidirectional transformers for language understanding, arXiv preprint 1xX.::1810.04005
DeVries, T. and Taylor, G. W. (2017). Improved regularization convolutional neural networks with cutout. arXiv preprint arXiv: 1000:0458.222
D'Orazio, R., Loizou, N., Laradji. I., and Mitliagkas, I. (2021). Stochastic mirror descent: Convergence analysis
and adaptive variants via the mirror stochastic polyak stepsize. arXiv preprint arXiv:2110. 15412.
Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online lcarning and stochastic optimization. Journal of machine learning research, 12(7).
Faw, M., Tziotis, I., Caramanis, C., Mokhtari, A., Shakkottai, S., and Ward, (2022). The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pages 313-355. PMLR.
Frome, L. (1983). The analysis of rates using poisson regression models. Biometrics, pages 665 674.
Gower. R. M.. Defazio, A., and Rabbat, M. (2021). Stochastic polyak stepsize with moving target. arXiv preprint 1r0iv:2106.1188
He, K., Zhang, X., Ren. S. and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778.
11

---

He, X., Tappenden, R., and Takac, M. (2018). Dual free adaptive minibatch sdea for empirical risk minimization. Frontiers in Applied Mathematics and Statistics, 4:33.
Horváth, S. and Richtárik. P. (2020). A better alternative to enorr feedback for communication distributed learning. arXiv preprint 20..xx:000..1177.
Hosmer Jr. D. W., Lemeshow, S., and Sturdivant, R. X. (2013). Applied logistic regression, volume 398. John
Wiley & Sons.
Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:
Krizhevsky, A. and Hinton, G. (2009). Learning multiple layers of features from tiny images.
Li, S., Swartworth, W. J., Takáč, M., Needell, D., and Gower, M. (2023). Sp2: A second order stochastic polyak method. ICLR.
Li, X. and Orabona, F. (2019). On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd international conference on artificial intelligence and statistics, pages 983-992. PMI.R
Liu, Z., Nguyen, T. D., Ene, A., and Nguyen, H. L. (2022). On the convergence of adagrad Rd: Beyond convexity, non-asymplotic rate and acceleration. arXiv preprint arXiv:2209.1482.
Loizou, N., Vaswani, S., Laradji. I. Н., and Lacoste-Julien, S. (2021). Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. International Conference on Artificial Intelligence and Statistics, pages 1306-1314. PMLR.
McMahan, H. B. and Streeter, M. (2010). Adaptive bound optimization for online convex optimization. arXiv preprint arXi:: 1902.490.
Mishchenko, K. Defazio, A. (2023). Prodigy: An expeditiously adaptive parameter- free learner. arXiv preprint arXiv:2306.0000 06100.
Nelder, A. and Wedderbum, R. W. (1972). Generalized linear models, Journal of the Royal Statistical Society
Series A: Statistics in Society, 135(3)3370-2
Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer.
Nesterov, Y. and Nemirovskii, A. (1994), Interior-point polynomial algorithmss in convex programming. SIAM.
Nguyen, I.,, Liu, J., Scheinberg, K., and Takáč, M. (2017a). Sarah: A novel method for machine learning problems using stochastic recursive gradient. In In 34th International Conference on Machine Learning, ICML 2017.
Nguyen, L. M., Liu, J., Scheinberg, K., and Takáë, M. (2017b). Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprint arXiv:1705.07266
Nguyen, L. M., Nguyen, P. H. van Dijk, M., Richtárik, P., Scheinberg, K., and Takáč, M. (2018). Sgd and hogwild! convergence without the bounded gradients assumption. In In 34th International Conference Machine Learning, ICML 2018
Nguyen, I.. M., Scheinberg, K., and Takáč, M. (2021). Inexact sarah algorithm for stochastic optimization. Optimization Methods and Software, 36(1):237-258.
Oberman, A. M. and Prazeres, M. (2019). Stochastic gradient descent with polyak's learning rate. arXiv preprint 1eXiv:/903.0800
Orabona, F. Crammer, K., and Cesa-Bianchi, N. (2015), A generalized online mirror descent with applications classification and regression. Machine Learning. 99:411-435.
Orabona, F. and Pál, D. (2015). Scale-free algorithms for online linear optimization. In International Conference on Algorithmic Learning Theory, pages 287-301. Springer.
Orabona, F. and Pál, D. (2018). Scale-free online learning. Theoretical Computer Science, 716:50-69.
Orvieto, A., Lacoste-Julien S., and Loizou, N. (2022). Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. Advances in Neural Information Processing Systems. 35:26943-2660 26954.
Polyak, B. T. (1969). Minimization of unsmooth functionals. USSR Computational Mathematics and Mathemat- ical Physics, 9(3):14-29
12

---

Reddi, S. J. Kale. S., and Kumar, S. (2019). On the convergence of adam and beyond. arXiv preprint arXiv:190.009237.
Robbins, H. and Monro, S. (1951). A stochastic approximation method. The annals of mathematical statistics, pages 400 407.
Saravia, E., Liu, H.-C. T., Huang, Y.HH., Wu, J., and Chen, Y.-. (2018). CARER: Contextualized affect representations for emotion recognition. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pages 3687-3697, Brussels, Belgium. Association for Computational Linguistics.
Shalev-Shwarz. and Ben-David. S. (2014). Understanding machine learning: From theory algorithms. Cambridge university press.
Shi, Z.. Sadiev, A.. Loizou, Richtárik, P., and Takáč, (2023). AI-SARAH: Adaptive and implicit stochastic recursive gradient methods. Transactions on Machine Learning Research.
Takáč, M., Bijral, A., Richtárik, P., and Srebro, N. (2013). Mini-batch primal and dual methods for syms. In
30th International Conference on Machine Learning, ICML 2013.
Tieleman, Hinton, G. (2012), Rmsprop: Divide the gradient by running average of recent magnitude.
coursera: Neural networks for machine learning. COURSERA Neural Networks Mach. Learn, 17.
Ward, R., Wu, X., Bottou, L. (2020). Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21 (1)999977-
Xie, Wu, X., and Ward, R. (2020). Linear convergence of adaptive stochastic gradient descent. International conference on artificial intelligence and statistics, pages 1475-1485. PMLR.
Zhang, M., Lucas, Ba, J., and Hinton, E. (2019). Lookahead optimizer: steps forward, step back. Advances in neural information processing systems, 32.
13

---

Supplementary Material
Contents
Introduction
Related Work
1.2 Main Contribution
1.3 Notation
2 Motivation and Algorithm Design
3 Convergence Analysis
3.1 Assumptions
3.2 Main Results
4
Numerical Experiments
8
4.1
Logistic Regression
4.1.1 Robustness of KATE
4.1.2 Peformance of KATE on Real Data
8
4.2 Training of Neural Networks
A Technical Lemmas
15
Proof of Main Results
19
B.1 Proof of Proposition 2.1
19
B.2 Proof of Lemma 2.2
20
B.3 Proof of Theorem 3.3
21
B.4 Proof of Theorem 3.4
23
Additional Experiments: Scale-Invariance Verification
26
14

---

A
Technical Lemmas
Lemma A.I (AM-GM), For À > we have
ab
b².
(18)
2x
Lemma A.2 (Cauchy-Schine Schwarz Inequality). For d1,". ... Chn, bı ... bn E IR we have
Σ
bj
Σ
a
(19)
Lemma A.3 (Holder's Incquality). Suppose X, are two random variables and p, > 1 satisty
1
Then
E ([XY)) < (I(I))) (B (
(20)
Lemma A.4 (Jensen's Inequality). For convex function g + R and random variable such that (X)( and V (E(()) are finite, we have
V (E(X)) S (X)())).
(21)
Lemma A.5. For d1, "2."." an 0 and b1, b2, dn > 0 we have
Σ aj 2 2i=1 a:
(22)
vb
2i=1 bi
Proof. Expanding the LHS of (22)
a
0:aj
v /bbb
o
(23)
b
The last inequality follows from
ai
2
0 for all E [m]. Now, using Cauchy-Schwarz Inequality (19), we have
bb.
n
n
Σ
bi
Σ
(24)
by
i=1
Then combining (23) and (24), we get
Σ
a:
Σ
0
vb
Finally dividing both sides by En and taking square root we get the desired result.
15

---

Lemma A.6. For & [d] and 2 1 we have
Byn[k] 12-1114] (V+f(we))²
B (Vas(w)))
R2
mi[k]]
Va (anla))
2 6/ [k] + (Vi(w:)) +
[
+2, +23 /
(25)
69[k]
8V /v [c]
Proof. Note that, using 1/(k) 2
we have
B / [K]
[K[
b22 [4]
[vx)) 0
1
< [/][k]]
66-,, [K] + (V+f(w))) 0
bi(k]]
b][k]]
b2 [A] (V+f(we))² o²
be [/] V 63 [6] (V=[(we)) + o²
be[k) / (Va[(ee))) +
9 (Vas(w,))² o²
= n/
be [4] b2- [k] + (V=f(w,)) o² [b[Ak] 1 + (V=f(we)) o
(g) - V+ (ge[k] V*f(wx)) o2
be [6c] 03 [A] + (Ve)(we)) 0² be(kk) / [k) + (Vaf(we))² 002
8 /n/ki [or[k) Vaf(w)) (oc(A) - vaf(we))
by [R[ V 67 [6] + (v=)(w)) + 0²
belkl + v 67 [4] + (V+f(wx)) +
8 //ko0
by [k|
b7 [k] (v.f( +
bo(k]] + DL (b) (Vaf(w.))² +
8 7 1 Ig [k]
[af(m)))
Bynkee
(26)
b/ 82 (V=f(w)))
o2
be [a / + (Vaf(w:))) t
Note that the second last inequality follows from the use of triangle inequality in the following way
(ge + Vxf(w=))) (x)()))) 0² o² s [se[k] + Val( [m - vaf(we)) - -02
<
+ VaJ [
while the last inequality follows from
be(k] + [k] (Vaf(w:))² t0²
lg 21 Vaf(w)))
be[k] [ (V+f(w)))² 20
16

---

Then from (26) we have
8 B//
E,
68 [k]] + (Vxf(wx))) + m1]ki] V (u )s.
[oe(A>] Vaf(we)) [+f((u)) [0
8 [
b.lkk/ 62- [4]] + (Vx((w))) o2
scrm
ff [k]
+ 3 T/|
(27)
bi 02 [K] (w.)))
term 1I
term in (27), we use Lemma A.I with
20²
V ML [M] + (Vxf(u)))² + tz
Lec [K]
[K]
19x [k] [al(ea))
b
V 6 [b] + (vx)( 0z
get
[o.[A] (w |b-1
BV ME].
be 68 [+]++ (V. + 0²
8 1|6 V 12- [A] + (w.) 0²
Vuf (w), 1)² B. [9. [uf(w,))
2
bp [k] + (Vef(w))) + 0²
B M
gi
E.
67
B [b] (Vef(w))) +
3 k) (Vaf(w)))
B.B nk
gi
(28)
62[k]
4 88 [M] + (Vrf())))
The inequality follows from BV. Similarly, we again use Lemma A.1 with
2
b [K] + (Vrf(w)))
0²
19 [All
be[k]
[el(wx)
VoN (V+((w))) o2
and b2[k]] + (V=f(wx))
+ 0² 2 to get
Vef 19 [k
[2 B/KKkoB.
B//lkkEE
S
b2
62 [ + (Vel (1x))) + 02 by [e[bb]
3 3 n (w:))
(29)
4 22 [k] (V)(w))) +
17

---

Therefore using (28) and (29) in (28) we get
The ( Bynk
gf I
velk))
Vas(w))orlA)
s 2 v n
[+] (V= +
[
/v 1/nki (V (v=f(w=))
2 2 6/_ [M] (VS(w,)) ) + o
This completes the proof of this Lemma.
Lemma A.7.
by [k] [
log
(30)
k
Proof. Using bi(A]]
Σt=o of have
oe [c]
9
1+
[
62
62
07
[A]]
1+
6714]]
(6714)
1+
de
[K]
62_ [8]]
[91
1+
[4]
de
68(N)
b7[k]
1 log
bg(A]
The inequality follows from the fact Lemma.
72 < when 16-1 S & S 62].). This completes the proof of the
18

---

B Proof of Main Results
B.1 Proof of Proposition 2.1
Proposition B.1 (Scale invariance). Suppose solve problems (4) and (5) using algorithm (6). Then, the
iterates the and wy corresponding to (4) and (5) follow: vk
[d]
We+ [k]
[b] [k]
Sone W
g+
[k],
(31)
0 l
0 [k]
wi [k]
Sm, (b]
2 9:
[k]
(32)
E. (of [ki)
with g. (/,((,,, [xr] di )a,, and 9.¹² pl,, (xr__ V (w V Ii. for i, chosen uniformly from [n]. t 0, .,..,,
2 0. Moreover, updates (31) and (32) satisfy
Vg= = gh' I ((.)) = (ux))
for all t 2 0 when wo dy 0 E ue Furthermore we have
| 1l
119:11
(33)
Proof. First, we will show 10 = V Viž and Vge = of using induction. Note that for r = 1 and & [d]. we get
i1 [k: =
-Bmg -Mee, (0)=
-mmlk) Fi (0) R]
(+h, (0)) Mi)
wi [k] = -Amal (0) Varri
8ma
(Hi, Vo) (N))
1% (0) Vo
as 10g V O. Therefore, we have wk E [d], de [k] = VaN [k). This can be equivalently written as 11 V Y as diagonal matrix. Then is easy check
V9i = v/. (1 10 Vxn, = so,, (x), (o Vx,, = 9)
(34)
where the second equality follows from de Vwy Now, assume the proposition holds for 1,... Then, we need to prove this proposition for T + Note that, from (7) we have
,
U.
[k]
de [k]
Er=o of 9e [k] = Vu [k]
Smu Ex (o Vas
"YM
= ViLN04+1kk)
Here, the second last equality follows from w, V and Vg- ge VT [t]. while the last equality holds due to (32). Therefore, we have dh++1 = Vw Then similar to (34) we get Vge+1 = gi+1 using 1h+1 Vay Again, using the Vwa we can rewrite (1ix) as follow
f(w:) = Ei s (x. wh) 1 En s0 (x. VΦ!) fv (wY).
The last equality follows from (5). This proves f(w:: l (wx)) ). Finally using V g: gē we get
| (ol) (ov)v-- V-2 oo" of VV VV 11g.11
This completes proof Proposition 2.1.
19

---

B.2
Proof of Lemma 2.2
Lemma B.2 (Decreasing step size). For v defined in (11) we have
[k] ve [A] vk [d].
Proof. We want to show that Me+1 [A] proving
S ve [A]. Taking square and rearranging the terms (13) is equivalent to
by [ [k] S bet1 [M] [k].
(35)
Using the expansion of m²²+ [k]. (241 [6]. LHS of (35) can be expanded as follow
b [4]mmi+all [k]
[[]]k] (m + n(kgge+a + b[[k] + oe [4:
g [A:]
(36)
Similarly, the RHS (35) can be expanded to
by [4]m[[]] = m
m [ (b + (A1)
? b [A] + m [k]g2 [k]] + ( (A]0((A)))
(37)
Therefore using (36) and (37), inequality (35) is equivalent to
g. [K]
[b]] m [A: n[M]99++1A1
m [i]b + v [1]gé+11b]]
+2m |k |k: D [4:]6 [c).
(38)
Now subtracting m3 [k]]6]] [i] from both sides of (38) and then multiplying both sides by & + 1 (38) equivalent to
se2, [M
m 2m 14 [
-m [k] [ + 2m (x]0 (39)
Therefore, proving (13) equivalent proving (39). Note that, from the expansion m b[A]b?[k]] + sa14 1 and m [b] 2 n]]4]6 [A]] Then using m [k] 2 we get
Et [ we have m² [b] 2
ge 1 [1]
S ml [ [4]g2 [M]]
(40)
Again, using m [A] 2 n|<bb2 [+]. we have
n(4|g2+1 by [ + 7 7 (A]01(
1 + m (A] [A])
(41)
Then adding (40) and (41) we get
71 + n [k [b]]
[A] + [A]]6 s 1+ [R]] 2m 14) (42)
Therefore, (39) is true due to (42) and mi [K]g] [A]] the Lemma.
2 2 O. This completes the proof of
20

---

B.3 Proof of Theorem 3.3
Theorem B.3. Suppose is L-smooth, 9: Vf(we) and 1), 8 are chosen such that vn [k] - 1 for all le [d].
Then for (11) we have
2(f(wo) - f.)
min [VS(w)I] $ T+1
Σ bolk] +
VTS
Proof. Suppose g+ (w(e). Then using the smoothness of f we get
f(WT++1 2 f(wr) + (gr, Wr+1 wr) + ||TTI1 - ur
f(wr) +
grlk] (wT+1 [k:] wr [k]) + (wr+1[k] [k]]
v [4]97 T. Σ
-[(W))
Σ vr [K]
k=1
[k] (1- ur (1
= f(wr)
[A].
Then using this bound recursively we get
Σ Σ [M[ ( 1 1= k=1
T
a
(1 f(wx)
un
gē [x].
Note that, initialized KATE such that vo(k] tVk [d]. Therefore using Lemma 2.2 have e4 [K[k] $ 1. which is equivalent 1 vn [M]] 2 2 for all k E [d]. Hence from (43) we have
f(WT++1
S f(wu)) ΣΣ
ve A of [k).
2
Then rearranging the terms and using (WT++1 f. we get
ΣΣ [k] [k] S f(wo) - fa.
(43)
Then from (43) and m. [8] Vnobe [k] we get
gf k
2( f-)
(44)
be Ak)
VnoiB
1 1
Now from the definition of by [4], we have (k] = b [k] + gf [k]. This can be rearranged to get
o [k]
bT[k]
=
br- [k]
br [k]]
+ by
97 [
<
by [k] +
(45)
br [A]
T
be [A]
9F
(46)
by [+]
t=0
Here the last inequality (46) follows from recursive use of (45). Then, taking squares both sides and summing
over l: E [d] we get
T
[k]
[b:]
bn[k]
+
Σ
[x[k]
1=0
T Σ
d
97 [k]
bulk]
be(k)
1=
2 2(f(wo) f-)
bo[k]] +
(47)
v 9
21

---

The second inequality follows from bu + Σi gi
for all [d] and the last inequality from (44).
Now note that Ei=o llg.ll -i gf Σe= b[[]]. Therefore dividing both sides of (47) by T + 1, we get
min [V/(w
Σ
[K] + 2(f(wp) f-)
T+1
This completes the proof of the theorem.
22

---

B.4 Proof of Theorem 3,4
Theorem B.4. Suppose f is L-smooth function and gi is unbiased estimator of V (wv) such that BV holds. Moreover, we assume [V=(ll I "² for all t. Then KATE satisfies
2(7 +
2C
min [ S
VT
3,7700
where
CJ = f(wo) fa +
Σ k=1
4
23v 1/K|o
2
+
29h [K]
B
)
log
[0² + -2)"
2 [k]
+1)
Proof. Using smoothness, we have
L
[wi+11 1 f(we) + (V[(wr), we+1 -we)
|
well 2
L
d
=[(w))
w. [k]]
(w [6]] we [4])
2
A=
= f(m))
L
Σ
2
Then, taking the expectation conditioned on wt, have
E. [f(w]+1)] $ f(wr)
Ex (0x))]
+
Ee [ 1 [+]]
[wx)
E. [m)
Ez [M] 14 [+]]
k=1
B /
[V (V+s(u)) 9r [A:]]
[M] + (Vxf(we)) 0
= f(m))
Σ The
1/ (v (w:)) + 2e(ki]
( [k]
B ni (Vaf(w=))²
[1] [k]]
b3 [k] + (Vef(ux)) +
The second
last
equality
follows
from
E. (Va((w:) (Vaf(we) 9. [b]]
(uf(w)) (Vaf(m,) Eg lsc (A]) = Now we use (25) to get
9ft [K]
E, [f(+)))) < f(w)) +
Σ 23 /nkkoo bi[k]]
+ Σ B. [
k=l
B //ik (V=f(we))
2 b7
+ (Vef(w))) 2
Then rearranging the terms we have
B w k (Vaf(w.))*
d + Σ
9 [k]
f(w)) - E. [f(w
2, / 17
k
62
R= 2 07 [ + (wi( 0
k=
L
E. [+]1
23

---

Now take the total expectations to derive
8 B (Vaf(we))
of [b] [2[A]
E
E [f((w))] E [f(w)+)) )] + Σ 2/ nkKo
2 8 M (wx)(
+
L
d
Σ
[k]
k=1
The ahove inequality holds for any t. Therefore summing up from t = to = T and using f (Wr++1 2 fa we
get
B [k] (Ve(()))) 22 (Vzf(w;)) o
of [k]
1 f(wo) - f. +
23
nl
67[1k]
ΣΣ R [u 1
(48)
k=
Note that, using the expansion of v2 [k] we have
0714
2 [k]]
==0
1714
[K]
B
Σ
k
19 1k:
K
B M
Σ
93 [m]
(49)
6 KK]
(50)
by
[A]
Here (49) follows from 6]]{]] 2 [8[]] and (50) from b²({]]
Σラー [k)] Then using (50) in (48) derive
[ux()))))
BnllL
B L
k
E
S ((ww) f.
23 n[KKo +
4=0 k=
2/ 03 [k] + (we)) + 0²
t= k=
2
2
[4]
f(wo) -
3
3
b3 1k
28v 23//T/kl0 n/ko +
log
+
1
2g [h:]
63 A
Here the last inequality follows from (30). Now using Jensen's Inequality (21) with (=z) = log(2) we have
B n (wee)
E
< f(w))= f-
2 62 [K] + (Vi((w)))
02
8 3
32L
F 1o [R]]
23 /Tlkoo +
log
+ +1)
2 [R:]
Now that EZ [b] Therefore, we have the bound
D [x]]
Σ [gr
[as(w))] (V+s():)))
(0² + T
3 / (V (w=)(
d $ f(wo) S. 2,3r
ee(o2 + + 6g [k]
E
n log
2 b2 [k] + (Vef(w))) +
k=1
LL
'elo" + x2yT
log
2
6g [k]
(51)
24

---

Here the RHS is exactly Cy. Using (22) we have
d
(Vaf(w)))*
Σ (V+S(wr))
1= Bi [b] (Vxf(w))) + 0
Σi 12 b/-1(k] + (V (V (w)e) t
| f(w))ll 2l
(52)
v 1lbb-111* + [[/e))) + do²
Therefore using (52) in (51) arrive at
V (wx))
2C₁ /
E
(53)
|1b 11? + V [(w))ll + do?
- ( $
Now we use Holder's Incquality (20)
B(XY)
with
$
(wx))
and Y (VIbb= ( + do?
X
| + | (wx))l + do?
get lower bound on LHS of (53):
| fv+) ||
E
2
|b 212 + | [V](w)))l' )1² do²
E. (1b:-11 2 [Vf(w 3 doz)
[V+))))
(54)
lbbll + 22 + do
Therefore from (53) and (54) we get
T
min [[+()=)) tsT
2C,
5
b1 l + 2T( do
B
Then multiplying both sides by [boll I v27 vdla
we have
T
|bbull T
2(7
+0)
2C,
anin
E
|
[
AST
vT
B
Here we use the above equation to get
S
E
v [(x)))
(follows from Jensen's Inequality (21) with V(() = =/ in
|bbul T
2(7 + 0)
2C,
min E ((
T
'T
This completes the proof of the Theorem.
25

---

C Additional Experiments: Scale-Invariance Verification
In this experiment, we implement KATE on problems (4) (for unscaled data) and (3) (for scaled data) with
(0((2) log (1 + exp (-)+=))
We generate the data similar Section 4.1.1. We KATE for 10, 000 iterations with mini-batch size 10, y = 1/V (wo)) and plot functional value ((w) and accuracy in Figures 1la 11b. We use the proportion of correctly classified samples to compute accuracy, i... 7 2i-1 (ucaT 2x20)'
In plots laa and Ilb, the functional value and accuracy of KATE coincide, which aligns with our theoretical findings (Proposition 2.1). Figure 1lc plots [VV[( and ||V [V for unscaled and scaled data respectively. Here, (10) explains the identical values taken by corresponding gradient norms KATE iterates for the scaled and unscaled data. Similarly, Figure 12, we compare the performance of AdaGrad on scaled and un-scaled data. This figure illustrates the lack of the scale- invarriiie for AdaGrad.
Dataset: (6,g0
10-1
[fitaa Dataset: (sy0) (ofW)) Wery!
Datasat: [Vh,
Accuraice
Grdd
Jin
Dotaset: D6 Dstaset:
Iterations
Iterotins
Itoractind
(a) Plot of f(w)
(b) Plot of Accuracy
(c) Plot of Gradient Norm
Figure 11: Comparison of KATE on scaled and un-scaled data. Figures 1la, and 1lb plot the functional value (w)) and accuracy scaled and unscaled data, respectively, Figure 1lc plots f and [[V for unscaled and scaled data respectively.
Ado md
Accurscy
Dataset: (5
[oAll]] Datasst (6.R) 1ontel
Dataset:
Grad
0.2
Dataset: (o.p5)
10a
Reration
Serations
Iterations
(a) Plot of (w:)
(b) Plot of Accuracy
(c) Plot of Gradient Norm
Figure 12: Comparison of AdaGrad on scaled and un-scaled data. Figures 12a, and 12b plot the functional value fw:) and accuracy on scaled and unscaled data, respectively. Figure 12c plots || (wx) and ||V fw:)))l for unscaled and scaled data respectively.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the new method and its scale invariance property are introduced Section 2, main convergence results are provided in Section 3, and the numerical results are provided in Section 4.
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 be pereeived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation long it is clear that these goals attained by the paper.
2. Limitations
Question: Does paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: see Section
Guidelines:
The answer NA means that paper has no limitation while answer means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust results are violations 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 the scope of the claims made, e.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers 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 important role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
grounds for rejection,
Theory Assumptions and Proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Section and the Appendix.
Guidelincs:
The answer NA means that the paper does not 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.
27

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors 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 or supplemental material.
Theorems and Lemmas the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental 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)?
Question:
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to 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 a new model (e.g.. a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct
dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the of cosed-source models, it may be that access to the model is limited some way (e.g.. to 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 faithfully reproduce the main experimental results, described supplemental material?
the data and code, with sufficient instructions
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
muides/CodeSubenn ssionPolccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g.. for a 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: :/ //np///p...//////// cc/public/ mu.ides//ooeeSubbiisssoo/oo/u for more details.
28

---

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 proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommenedd, but including URLs to data and code is permitted.
6. Experimental Setting/Detann Details
Question: Does the paper specify all the training and test details (c.g,, data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [NA]
Justification: the results are consistent for different runs.
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, confidence intervals, or statistical significance tests, at 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should given (e-g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error than state that they not verified.
CL, if the hypothesis of Normality of errors
asymmetric distributions, authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). crror bars are reported tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, docs the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We have added all the details in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
29

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question:
Does the research conducted the paper conform. every respect, with NeurIPS Code Ethics
cc/ cc/public/Ethi ceGuidelineedeeeeeeeee
Answer:
[Yes]
Justification: the paper follows NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: the paper is mostly thcoretical and docs not have direct socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations. (e.g.. deploy- of technologies that could make decisions that unfairly impact specific groups), privacy considcrations, and security considerations.
The conference expects that many papers will be foundational research and not tied 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 not needed point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 (c.g., gated relcase of models, providing defenses in addition to attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible relcase of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: we do not release data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk 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 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 is challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
30

---

12. Licenses for existing assets
Question: Are creators or original owners assets (e.g., code, data, models), used the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected"'
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not use existing assets.
authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the
is used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets 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 a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged reach out asset'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: not applicable.
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 sub- missions via structured templates. This includes details about training. license, limitations.
The paper should discuss whether and how consent was 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 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, applicable, as as details about compensation (if any)?
Answer: [NA]
Justification: not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of 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
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?
Question:
Answer: [NA]
Justification: not applicable.
Guidelines:
31

---

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 the paper.
recognize that the procedures for this may vary significantly between institutions and Iocations, and we expect authors adhere to the NeurIPS Code of Ethics the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review,
32


Reviews:
[{"review_id": "rui0juG1GF", "reviewer": "Reviewer_ZFDF", "summary": "This paper proposes a scale-invariant variant of AdaGrad, called KATE, particularly for generalized linear models. Theoretically, the authors proved a convergence rate of $\\mathcal{O}(\\log T/\\sqrt{T})$ for KATE, matching the best known rates for AdaGrad and Adam. Numerical experiments are used to illustrate KATE on several machine learning tasks, which outperforms AdaGrad consistently and matches/outperforms Adam.", "questions": "While it could be harder to demonstrate the scale-invariant property of KATE with real data experiments, is it possible to demonstrate the scale invariant property of KATE compared to AdaGrad and Adam with the logistic regression using simulated data? This could better help readers understand why the scale-invariant property of KATE is plausible compared to other adaptive optimizers.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work studies a crucial problem of developing a scale-invariant variant of AdaGrad which is particularly useful whenever data exhibit poor scaling or ill-conditioning. Convergence rates of KATE similar to those of AdaGrad and Adam under both deterministic and stochastic settings are established, with comprehensive numerical experiments to justify the efficacy of KATE compared to AdaGrad and Adam.", "weaknesses": "As the motivation of KATE is to develop a scale-invariant optimizer, the experiments (even the one with simulated data) do not seem to have demonstrated this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review and positive evaluation. Below, we address the reviewer's questions and concerns.\n\n> **While it could be harder to demonstrate the scale-invariant property of KATE with real data experiments, is it possible to demonstrate the scale-invariant property of KATE compared to AdaGrad and Adam with the logistic regression using simulated data? \nThis could better help readers understand why the scale-invariant property of KATE is plausible compared to other adaptive optimizers.**\n\nThank you for your insightful feedback. We appreciate the reviewer's concern regarding the demonstration of KATE's scale-invariance property. To address this, we have included plots that illustrate the scale-invariance of KATE using simulated data. These plots can be found in Appendix C, Figure 11.\n\nThese plots provide a visual demonstration of the scale-invariance property that we have theoretically proved in Proposition 2.1. Unfortunately, due to space constraints, we were unable to include these plots in the main body of the paper. However, we have referenced them in the main paper on line 121 to ensure that readers are aware of their existence and can easily locate them.\n\nWe hope these additional visual proofs address your concern. If this clarification meets your expectations, please consider raising your score to further support our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GWyGYxuo25", "reviewer": "Reviewer_eTbr", "summary": "The paper introduces a novel optimization algorithm which demonstrate scale-invariance property for generlized linear models unlike Adagrad. The authors analyzed KATE for smooth and non-convex functions and on generalized linear models to obtain the same convergence upper bounds (asymptotically) as Adagrad and Adam. However the scale invariant algorithm implies, the speed of the algorithm would be the same as for the best scaling of data. The authors also empirically verify this via numerical experiments on logistic regression and deep learning tasks.", "questions": "In line 80-81  “meaning that the speed of convergence of KATE is the same as for the best scaling of the data.”, is this reflected in the convergence bound? i.e., whether scale dependence of Adagrad bound vs scale independence of KATE bound is emphasized. The Table 1 only mention asymptotic bounds for Adagrad. It would help the paper if the convergence bounds are analyzed for the generalized linear models for Adagrad and KATE to understand the affect of scale on the final upperbounds.", "limitations": "Authors have adequately addressed limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) The authors come up with KATE which is scale invariant, and yet admit a convergence upper bound of $\\mathcal{O}(\\log(T)/\\sqrt{T})$, which is an interesting algorithmic finding.\n2) The paper is easy to read and understand. \n3) Comprehensive appendix.", "weaknesses": "I think authors need to emphasize the first point in Strengths by comparing with the diagonal online-newton method (diag-SONew) [1] which is also scale-invariant algorithm and what part of the analysis can fail for diag-SONew. I wrote the algorithm without the EMA here, which is essentially adagrad without the square root but with varying $\\eta_t$:\n\n$$\nw_t := w_{t-1} -\\eta_t g_t /({\\sum_{s=1}^t g_s* g_s})\n$$\n\n schedules one can try is $\\eta_t=1$ or $\\eta_t=\\sqrt{t}$. I think comparing with the latter schedule will give a good understanding of the novelty behind KATE, as the schedule simulates the square root in Adagrad while being scale-invariant. Similarly empirical comparisons (if possible) with this simple algorithm in logistic-regression can help understand which algorithm is better.\n\n2) Comparison with Adam doesn’t make sense in neural networks as KATE lacks momentum and EMA in second-moments (which are key features of Adam). Devising KATE with these features similar to [2] would help the empirical performance in neural networks.\n\n[1] Devvrit, Fnu, Sai Surya Duvvuri, Rohan Anil, Vineet Gupta, Cho-Jui Hsieh, and Inderjit Dhillon. \"A computationally efficient sparsified online newton method.\" Advances in Neural Information Processing Systems 36 (2024).\n[2] Defazio, A., & Mishchenko, K. (2023, July). Learning-rate-free learning by d-adaptation. In International Conference on Machine Learning (pp. 7449-7479). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review and positive evaluation. Below, we address the reviewer's questions and concerns.\n\n> **I think authors need to emphasize the first point in Strengths by comparing with the diagonal online-newton method (diag-SONew) [1], which is also a scale-invariant algorithm, and what part of the analysis can fail for diag-SONew….. schedules one can try is $\\eta_t = 1$ or $\\eta_t = \\sqrt{t}$. I think comparing with the latter schedule will give a good understanding of the novelty behind KATE, as the schedule simulates the square root in Adagrad while being scale-invariant. Similarly, empirical comparisons (if possible) with this simple algorithm in logistic regression can help understand which algorithm is better.**\n\nThank you for your excellent question. Indeed, the design of our KATE optimizer was motivated by a similar exploration of different step-size strategies. Our approach involved experimenting with different step sizes to determine their effectiveness before proving the corresponding theorems. Initially, we tried setting $\\eta_t=1$, but it did not converge to the optimal solution (as noted on lines 123-124 of our paper). \n\nWe then experimented with $\\eta_t = \\sqrt{t}$​, which showed mixed results—performing well in some experiments but poorly in others. From these experiments, we observed that $\\eta_t = \\eta \\sqrt{t}$​, where $\\eta$ needs to be tuned, performed better. However, this algorithm was still not robust to the choice of $\\eta$, unlike KATE. In particular, when full gradients are used instead of stochastic ones, the denominator is provably bounded. This means that with $\\eta_t = \\eta \\sqrt{t}$, the overall stepsize is growing, and one has to choose $\\eta$ small enough (and dependent on the time horizon) to avoid the divergence. For KATE, the numerator of the step size is adaptive and depends on the function $f$ and stochastic gradients, allowing it to adjust to the problem more effectively.\n\nWe will incorporate this discussion and include experiments comparing KATE with the step sizes you mentioned in the updated version of our paper. We hope this explanation clarifies our design process and KATE's robustness in handling different step sizes.\n\n>**Comparison with Adam doesn’t make sense in neural networks as KATE lacks momentum and EMA in the second moments (which are key features of Adam). Devising KATE with features similar to [2] would help with empirical performance in neural networks.**\n\nThank you for this insightful comment. We are aware of the D-adaptation work and recognise its importance. We plan to incorporate momentum and Exponential Moving Average (EMA) into KATE as part of our future research. This enhancement is on our to-do list, and we are excited about the potential improvements it can bring to KATE's performance and robustness. Thank you for highlighting this area, and we look forward to sharing our progress in future publications.\n\n>**In lines 80-81, “meaning that the speed of convergence of KATE is the same as for the best scaling of the data.” is this reflected in the convergence bound? i.e., the scale dependence of the Adagrad bound vs. the scale independence of the KATE bound is emphasised. Table 1 only mentions asymptotic bounds for Adagrad. It would help the paper if the convergence bounds were analysed for the generalised linear models for Adagrad and KATE to understand the effect of scale on the final upper bounds.**\n\nWe thank the reviewer for the great question. Since our convergence bounds are derived for the general smooth non-convex problems, which are not necessarily generalised linear models (GLMs), the scale-invariance is not reflected in the convergence bounds. Adapting our analysis to the case of GLMs is an interesting direction for future research.\n\n**Thanks for the valuable suggestions and the positive evaluation. If you agree that we addressed all issues, please consider raising your score to support our work. If you believe this is not the case, please let us know so we can respond.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NgEIveROgY", "reviewer": "Reviewer_bngL", "summary": "This work proposes an optimizer that achieves the optimal convergence guarantee for smooth nonconvex settings and more importantly the scale-invariance property.", "questions": "- I think since a lot of baselines this paper considers is originally designed for online convex optimization, it is important to also do an extensive analysis of KATE for the corresponding OCO settings and compare. In particular, some regret analysis as well as the convergence analysis for nonsmooth convex setting might be helpful.\n\n\n- The main motivation this paper argues for the need of scale-invariance under the data scaling is that previous approaches could be brittle when data has poor-scaling or ill-conditioning. In order to make a case that this is an important question to solve, I'd like to see some practically relevant scenarios where the lack of good scaling of data leads to failure of non-scale-invariance approaches like Adam and Adagrad. I think for this paper to be have a bigger impact, a compelling set of experiments along this line seems to be necessary.\n\n- Do you expect poor data scaling to be the major issue in the training large AI models such as LLMs? If that's the case, I think this paper might have a bigger impact.", "limitations": "As I said, the reason for the current score is mainly due to the main scope of this paper.\nIn my opinion, unless the authors have compelling experimental results or arguments, tacking the scale-invarance seems to have limited practical impact in the community.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very cleanly written. It was very easy to follow.\nThe main results look sound, and the experimental results are well presented as well.", "weaknesses": "Overall, the paper presents the main scope and the results very well.\nIn other words, I do not have much concern for this paper by itself. \n\nMy only concern is the importance of the problem it tackles. Scale-invariance is definitely a desirable property, but I'm not sure what advances it brings about for the ML optimization. What I mean is, in general, the important question in the community is whether one can design an optimizer that has a noticeable advantage over the previous popular ones. I'm not sure whether resolving scale-invariance will drastically improve our current technology for optimizing ML models. The experiments presented in this paper doesn't seem to justify this in a compelling way. (I think results are convex models have limited practical impact.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review. Below, we address the reviewer's questions and concerns.\n\n> **My only concern is the importance of the problem it tackles. Scale-invariance is definitely a desirable property, but I'm not sure what advances it brings about for ML optimization. What I mean is, in general, the important question in the community is whether one can design an optimizer that has a noticeable advantage over the previous popular ones. I'm not sure whether resolving scale invariance will drastically improve our current technology for optimizing ML models. The experiments presented in this paper don't seem to justify this in a compelling way. (I think results are convex models that have limited practical impact.)**\n\nThank you for your insightful comment. We believe that good adaptive methods should work well for all problems, particularly relatively simple problems that we can analyze. Therefore, we see scale-invariance as an intermediate step toward designing practical methods for large classes of ML problems, going beyond generalized linear models. We fully acknowledge the reviewer's concern and would like to emphasize the significant performance improvements that KATE offers compared to the AdaGrad algorithm. Specifically, KATE has consistently outperformed AdaGrad across various tasks on real-world datasets, such as CIFAR-10 and the emotions dataset from Hugging Face Hub. We attribute KATE's superior performance to its scale-invariance property. Moreover, it is noteworthy that KATE performs comparably to Adam on these tasks, even though it does not incorporate advanced techniques like momentum and Exponential Moving Average (EMA). This observation suggests that if we were to develop a scale-invariant version of Adam, it could potentially outperform the standard Adam algorithm across all tasks.\n\nIn summary, our paper lays the groundwork for the future development of improved scale-invariant algorithms. We strongly believe this work represents an important stride towards developing more robust and effective optimization methods. \n\n>**I think since a lot of baselines this paper considers are originally designed for online convex optimization, it is important to also do an extensive analysis of KATE for the corresponding OCO settings and compare. In particular, some regret analysis and convergence analysis for non-smooth convex settings might be helpful.**\n\nWe thank the reviewer for the suggestion. We believe that our analysis can be generalized to the case of online convex optimization and non-smooth convex setting, and up to the logarithmic factor, we can derive the standard $1/\\sqrt{T}$ rate for these settings. Therefore, in terms of the theoretical convergence bounds, KATE has comparable convergence rates with the best-known algorithms in these settings (up to the logarithmic factor). However, it would be interesting to compare KATE with other methods designed for online convex optimization in the experiments (and, perhaps, take the best of two worlds to develop even better methods). We leave this direction for future work.\n\n> **The main motivation this paper argues for the need for scale-invariance under the data scaling is that previous approaches could be brittle when data has poor scaling or ill-conditioning. In order to make a case that this is an important question to solve, I'd like to see some practically relevant scenarios where the lack of good scaling of data leads to the failure of non-scale-invariance approaches like Adam and Adagrad. I think for this paper to have a bigger impact, a compelling set of experiments along this line seems to be necessary.**\n\nIt is common practice to normalize/scale the input data to get better results in Neural Network training (e.g., see Horváth and Richtárik (2020)). We are currently working on extending our numerical experiments for image classification to illustrate how the methods behave with and without data normalization and with and without scaling.\n\n>**Do you expect poor data scaling to be the major issue in training large AI models such as LLMs? If that's the case, I think this paper might have a bigger impact.**\n\nThat is an interesting question. We have not yet considered this aspect in our current work. Additionally, our research is primarily theoretical, and conducting experiments on large language models (LLMs) falls outside the scope of this paper. However, we recognize the importance of the reviewer's concern and commit to exploring the existing literature on LLMs to investigate if data scaling can impact the training of large AI models. We agree that if such an impact is found, it could represent a significant contribution to the community.\n\n> **As I said, the reason for the current score is mainly due to the main scope of this paper. In my opinion, unless the authors have compelling experimental results or arguments, tacking the scale-invariance seems to have limited practical impact in the community.**\n\nPlease see our response to the weaknesses.\n\n**Thanks for the valuable suggestions and the positive evaluation. If you agree that we addressed all issues, please consider raising your score to support our work. If you believe this is not the case, please let us know so we can respond.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fXYaHvdxZd", "reviewer": "Reviewer_uk2H", "summary": "This paper presents a novel algorithm, KATE, which demonstrates impressive scale-invariance properties for Generalized Linear Models.", "questions": "1 How does the scale-invariance property of KATE impact its performance in real-world applications compared to traditional adaptive algorithms?\n\n2 Can the authors elaborate on the computational complexity of KATE and how it scales with the size of the dataset?\n\n3 Are there any specific scenarios or types of machine learning tasks where KATE may not perform as effectively, and if so, how does the algorithm address these limitations?", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper presents a novel algorithm, KATE, which demonstrates impressive scale-invariance properties for Generalized Linear Models. The thorough theoretical analysis provided in the paper, along with the experimental results, showcases the effectiveness of KATE in various machine learning tasks. The comparison with existing algorithms like AdaGrad and Adam highlights the superior performance of KATE in terms of convergence rate and efficiency.", "weaknesses": "While the paper excels in presenting the theoretical foundations and empirical results of the KATE algorithm, there are a few areas that could be further strengthened. Firstly, the paper could benefit from a more detailed discussion on the limitations of the proposed algorithm, especially in scenarios where certain assumptions may not hold. Additionally, providing insights into the computational efficiency and scalability of KATE with larger datasets could enhance the practical applicability of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review. Below, we address the reviewer's questions and concerns.\n\n> **Firstly, the paper could benefit from a more detailed discussion of the limitations of the proposed algorithm, especially in scenarios where certain assumptions may not hold.**\n\nThank you for your suggestion. We acknowledge that one of the assumptions in our work is the bounded gradient assumption, which states that $|| \\nabla f(w_t) ||^2 \\leq \\gamma^2$. This assumption is strong and critical for our convergence analysis of the KATE algorithm in the stochastic setting, as presented in Theorem 3.4. This assumption may not hold in several scenarios when the optimization problem's domain is unbounded, and the gradient might grow without limit. To address this limitation, we plan to investigate using gradient clipping techniques with KATE in future work.\n\nHowever, we emphasize that this assumption is not a limitation of our work. The bounded gradient assumption is a standard regularity condition employed in analyzing numerous stochastic optimization algorithms, including well-established methods like Adam and AdaGrad. The bounded gradient assumption helps manage the stochastic noise and ensure the stability of the updates, which is crucial for deriving theoretical guarantees. By adopting this assumption, we align our analysis with the existing body of work, making our results comparable and sticking to established theoretical frameworks. We will add the above discussion in the updated version. \n\n> **Additionally, providing insights into the computational efficiency and scalability of KATE with larger datasets could enhance the practical applicability of the algorithm.**\n> **Can the authors elaborate on the computational complexity of KATE and how it scales with the size of the dataset?**\n\nWe thank the reviewer for their insightful question regarding the computational efficiency and scalability of KATE. To address computational efficiency, KATE is designed to be computationally efficient by requiring only one gradient computation per iteration. This is achieved by storing and reusing intermediate computations, specifically $m^2_{t-1}$​ and $b^2_{t-1}$​, from the previous iteration. This approach avoids redundant calculations and contributes to the algorithm's overall efficiency. In terms of convergence rate, KATE exhibits a favorable theoretical convergence rate of $O(\\log T/ \\sqrt{T})$ in the stochastic setting and $O(1/T)$ in the deterministic setting. A detailed comparison of convergence rates with other algorithms is provided in Table 1 of our paper.\n\nTo demonstrate KATE's scalability, we have conducted experiments on large-scale datasets, including CIFAR-10 for image classification and the emotions dataset from Hugging Face Hub for BERT fine-tuning. Our results indicate that KATE outperforms both Adam and AdaGrad on the CIFAR-10 dataset while exhibiting comparable performance to Adam on the emotions dataset. These findings suggest that KATE is capable of handling large-scale datasets efficiently and effectively. **We believe that the combination of computational efficiency, favorable convergence rate, and strong empirical performance on large-scale datasets highlights KATE's potential for practical applications.**\n\n\n>**How does the scale-invariance property of KATE impact its performance in real-world applications compared to traditional adaptive algorithms?**\n\nThank you for the question. We believe that good adaptive methods should work well for all problems, particularly relatively simple problems that we can analyze. Therefore, we see scale-invariance as an intermediate step toward designing practical methods for large classes of ML problems, going beyond generalized linear models. As discussed in Section 2: Motivation and Algorithm Design, KATE was specifically designed to make AdaGrad scale-invariant. This design choice is pivotal, as it allows KATE to outperform AdaGrad across all tasks on real-world datasets, such as CIFAR-10 and the emotions dataset from Hugging Face Hub. We attribute KATE's superior performance to its scale-invariance property, which ensures consistent and reliable results regardless of the scale of the gradients.\n\nAdditionally, we compared KATE with Adam in our experiments. While KATE does not incorporate momentum and the Exponential Moving Average (EMA) of second moments (also mentioned by reviewer eTbr), as Adam does, it still performs comparably to or better than Adam in real-world applications. This observation underscores the potential for further enhancements. If a version of Adam could be designed to be scale-invariant, similar to KATE, it might achieve even better performance.\n\nIn summary, our work with KATE not only demonstrates its effectiveness but also lays the groundwork for future research in adaptive methods. By leveraging the scale-invariance property, there is significant potential for further advancements in this field.\n\n\n> **Are there any specific scenarios or types of machine learning tasks where KATE may not perform as effectively, and if so, how does the algorithm address these limitations?**\n\nThank you for the question. Currently, we are not aware of any situations where KATE performs worse than AdaGrad or Adam. As we have highlighted earlier, we believe that KATE's scale-invariance property plays a crucial role in ensuring its superior performance.\n\n**If you agree that we addressed all issues, please consider raising your score. If you believe this is not the case, please let us know so that we can respond.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their feedback and time. We appreciate that the reviewers acknowledged the following strengths of our work:

- Reviewer ZFDF recognises the importance of developing a scale-invariant version of AdaGrad.
- Reviewer uk2H finds the scale-invariance property of KATE very impressive.
- Reviewer eTbr highlights the significance of KATE achieving the $O(\log T/ \sqrt{T})$ rate even with the scale-invariance property.
- Reviewers eTbr and bngL find our work easy to read and understand. They appreciate the paper's presentation. 
- Reviewers eTbr, ZFDF, and uk2H value the thorough theoretical analysis of KATE provided in the paper.
- All the reviewers acknowledge the numerical experiments provided in our paper. 

In our responses, we have addressed the reviewers' questions and concerns in detail. If the reviewers have further questions/concerns/comments, we will be happy to participate in the discussion.

Meta-review: The paper introduces KATE, a new optimization algorithm that adapts the AdaGrad method, for Generalized Linear Models. KATE is proven to have a convergence rate comparable to AdaGrad and Adam for smooth non-convex problems. Experimental results show that KATE consistently outperforms AdaGrad and matches or exceeds Adam's performance in various machine learning tasks, including image and text classification. Most of the reviewers recognized that this is an important work in providing a new adaptive stepsize rule that are scale invariant. However, some reviewers also pointed out, and I agree, that larger scale and more practical numerical experiments are needed to truly demonstrate the proposed approach. I would suggest that the authors include such numerical tests, if at all possible.
Decision: Accept (poster)