DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method
Authors: Ahmed Khaled
Konstantin Mishchenko
Chi Jin
Venue: NeurIPS 2023 poster (2023)
Keywords: normalized gradient descent
gradient descent
adagrad
adaptive optimization
parameter-free
smooth optimization
convex optimization
edge of stability

Abstract: This paper proposes a new easy-to-implement parameter-free gradient-based optimizer: DoWG (Distance over Weighted Gradients). We prove that DoWG is efficient---matching the convergence rate of optimally tuned gradient descent in convex optimization up to a logarithmic factor without tuning any parameters, and universal---automatically adapting to both smooth and nonsmooth problems. While popular algorithms following the AdaGrad framework compute a running average of the squared gradients, DoWG maintains a new distance-based weighted version of the running average, which is crucial to achieve the desired properties. To complement our theory, we also show empirically that DoWG trains at the edge of stability, and validate its effectiveness on practical machine learning tasks.

DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method
Ahmed Khaled
Konstantin Mishchenko Samsung AI Center
Chi Jin Princeton University
Princeton University
Abstract
This paper proposes a new easy-to-implement parameter-free pero-mmepeeeeetrrrreeeeeerrree gradient-based op- timizer: DoWG (Distance over Weighted Gradients). We prove that DoWG is efficient-matching the convergence rate of optimally tuned gradient descent in convex optimization up logarithmic factor without tuning any parameters, and umiivessll-auommatical
adapting to both smooth and nonsmooth problems. While popular algorithms following the AdaGrad framework compute a running average of the squared gradients to use for normalization, DoWG maintains a new sestacee-bssd weighted version of the running average, which is crucial achieve the desired properties. To complement our theory, we also show empirically that DoWG trains at the edge of stability, and validate its effectiveness on practical machine learning tasks.
Introduction
We study the fundamental optimization problem
min f(x), #
(OPT)
where is convex function, and X' is convex, closed, and bounded subset of Rdd We assume f has at least one minimizer x. E X. We focus on gradient descent and its variants, as they are widely adopted and scale well when the model dimensionality d large (Bottou et al., 2018). The optimization problem (OPT) finds many applications: in solving linear systems, logistic regression, support vector machines, and other areas of machine learning (Boyd and Vandenberghe, 2004). Equally important, methods designed for (stochastic) convex optimization also influence the intuition for and design of methods for nonconvex optimization- for example, momentum (Polyak, 1964), AdaGrad (Duchi et al., 2010), and Adam (Kingma and Ba, 2015) were all first analyzed in the convex optimization framework.
As models become larger and more complex, the cost and environmental impact of training have rapidly grown well (Sharir al., 2020; Patterson et al., 2021). Therefore, it is vital that we develop more efficient and effective methods of solving machine learning optimization tasks. One of the chief challenges in applying gradient-based methods that they often require tuning one more stepsize parameters (Goodfellow et al., 2016), and the choice of stepsize can significantly influence method's convergence speed well as the quality of the obtained solutions, especially in deep learning (Wilson et al., 2017).
The cost and impact of hyperparameter tuming the optimization process have led to significant research activity in designing parameter-free and adaptive optimization methods in recent years, see e.g. (Orabona and Cutkosky, 2020; Carmon and Hinder, 2022) and the references therein.
We say an algorithm is universal it adapts to many different problem geometries or regularity conditions on the function (Nesterov, 2014; Levy et al., 2018; Grimmer, 2022). In this work. we focus on two regularity conditions: (a) Lipschitz and (b) f smooth. Lipschitz functions
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

have bounded rate of change, that is, there exists some G > 0 such that for all 2, E X' we have If(z) - f(y) I - The Lipschitz property beneficial for the convergence of gradient-based optimization algorithms. They converge even faster on smooth functions, which have continuous derivatives; that is, there exists some T. > such that for all x, y/ X' we have fzz) - Vf(v) & L||a vll- Smoothness leads to faster convergence of gradient- based methods than the Lipschitz property. Universality a highly desirable property because in practice the same optimization algorithms are often used for both smooth and nonsmooth optimization (e.g. optimizing both ReLU and smooth networks).
The main question of our work is as follows:
Can we design a universal, parameter-fir free gradient descent method for (OPT)?
Existing universal variants of gradient descent either rely on line search (Nesterov, 2014; Grimmer, 2022), bisection subroutines (Carmon and Hinder. 2022), or are not parameter-free (Hazan and Kakade, 2019; Levy et al., 2018; Kavis et al., 2019). Line search algorithms are theoretically strong, achieving the optimal convergence rates in both the nonsmooth and smooth settings with only an extra log factor. Through an elegant application of bisection search, Carmon and Hinder (2022) design a parameter- free method whose convergence is only muuble-logartthmicall worse than gradient descent with known problem parameters. However, this method requires resets, i.e. restarting the optimization process many times, which can be very expensive in practice. Therefore, we seek a universal, parameter-free gradient descent method for (OPT) with no search subroutines.
Our contributions. We provide new algorithm that meets the above requirements. Our main contri- bution is a new universal, parameter-free gradient descent method with no search subroutines. Building upon the recently proposed Distance-over-Grees Grad-erd (DoG) algorithm (Ivgi et al., 2023), we develop a new method, DoWG (A (Algorithm 1), that uses different stepsize with adaptively weighted gradients. We show that DoWG automatically matches the performance of gradient descent on (OPT) up to logarithmic factors with no stepsize tuning at all. This holds in both the nonsmooth setting (Theorem 3) and the smooth setting (Theorem 4). Finally, we show that DoWG is competitive on real machine learning tasks (see Section 4).
Algorithm
No search
Parameter-free
Universal
GD framework
Polyak stepsize (Polyak, 1987; Hazan and Kakade, 2019)
X
Coin betting with normalization (Orabona and Pál, 2016; Orabona and Cutkosky, 2020; Orabona, 2023)
50
X
Nesterov line search (Nesterov, 2014)
AdaGrad
X
4
/
(Duchi et al., 2010; Levy et al., 2018; Ene al., 2021)
Adam
X
(Kingma and Ba, 2015; Li et al., 2023)
Bisection search (Carmon and Hinder, 2022)
/
V
D-Adaptation (Defazio and Mishchenko, 2023)
X
DaG (Tvgi et al., 2023)
DoWG (new, this paper!)
(9) Result appeared after the initial release of this paper. Table 1: A comparison of different adaptive algorithms for solving (OPT). "Universal" means that the algorithm can match the rate of gradient descent on both smooth and nonsmooth objectives up to polylogarithmic factors. "No search" means the algorithm does not reset. "GD framework" refers to algorithms that follow the framework of Gradient Descent.
2
Related Work
There is a lot of work on adaptive and parameter-free approaches for optimization. We summarize the main properties of the algorithms we compare against in Table We enumerate some of the major approaches below:

---

Polyak stepsize. When f. = fxx) is known, the Polyak stepsize (Polyak. 1987) is a theoretically- grounded, adaptive. and universal method (Hazan and Kakade, 2019). When f. not known, Hazan and Kakade (2019) show that an adaptive re-estimation procedure can recover the optimal convergence rate up to a log factor when f is Lipschitz. Loizou et al. (2021) study the Polyak stepsize in stochastic non-convex optimization. Orvieto et al. (2022) show that a variant of the Polyak stepsize with decreasing stepsizes can recover the convergence rate of gradient descent, provided the stepsize is initialized properly. Unfortunately, this initialization requirement makes the method not parameter-free.
The doubling trick. The simplest way to make an algorithm parameter- free is the doubling- -eriii.gggrikk..... For example, for gradient descent for L-smooth and convex optimization, the stepsize 17 1/2 results in the convergence rate of
DoLL2 T
- -.=0
(1)
where Do |20 1 x. We may therefore start with small estimate Lo of the smoothness constant L, run gradient descent for T steps, and return the average point. We restart and repeat this for N times, and return the point with the minimum function value. So long N 2 log to we will return a point with loss satisfying eq. (1) at the cost of only an additional logarithmic factor. This trick and similar variants of it appear in the literature on prediction with expert advice and online learning Cessa-Bianchi al., 1997; eesa-Bianchi and Lugosi, 2006; Hazan and Megiddo, 2007). It is not even needed to estimate N in some cases, as the restarting can be done adaptively (Streeter and McMahan, 2012). In practice, however, the performance of doubling trick suffers from restarting the optimization process and throwing away useful that could be used to guide the algorithm.
Parameter-free methods. Throughout this paper, we use the term "parameter-fire free algorithms" to describe optimization algorithms that do not have any tuning parameters. We specifically consider only the deterministic setting with compact domain. As mentioned before, Carmon and Hinder (2022) develop an elegant parameter-free and adaptive method based on bisection search. Bisection search, similar to grid search, throws away the progress of several optimization runs and restarts, which may hinder their practical performance. Ivgi et al. (2023); Defazio and Mishchenko (2023) recently developed variants of gradient descent that are parameter-free free when f is Lipschitz. However, D-Adaptation (Defazio and Mishchenko, 2023) has no known guarantee under smoothness, while DoG (Ivgi et al., 2023) was only recently (after the initial release of this paper) shown to adapt to smoothness. We compare against the convergence guarantees of DoG in Section 3.2. For smooth functions, Malitsky and Mishchenko (2020) develop AdGD, a method that efficiently estimates the smoothness parameter on-the-fly from the training trajectory. AdGD is parameter-free and matches the convergence of gradient descent but has no known guarantees for certain classes of Lipschitz functions. A proximal extension of this method has been proposed by Latafat et al. (2023).
Parameter-free methods in online learning. In the online learning literature, the term "parameter- free algorithms" was originally used to describe another class of algorithms that adapt to the unknown distance to the optimal solution (but can still have other tuning parameters such as Lipschitz constant). When the Lipschitz parameter is known, approaches from online convex optimization such as coin betting (Orabona and Pál, 2016), exponentiated gradient (Streeter and McMahan, 2012; Orabona, 2013), and others (McMahan and Orabona, 2014; Orabona and Cutkosky, 2020; Orabona and Pál, 2021; Orabona and Tommasi, 2017) yield rates that match gradient descent up to logarithmic factors. Knowledge of the Lipschitz constant can be removed either by using careful restarting schemes (Mhammedi et al., 2019; Mhammedi and Koolen, 2020), or adaptive clipping on top of coin betting (Cutkosky, 2019). For optimization in the deterministic setting, it is later clarified that, by leveraging the normalization techniques developed in (Levy, 2017), the aforementioned online learning algorithms can be used without knowing other tuning parameters (i.c., achieve "parameter- free" in the sense of this paper) for optimizing both Lipschitz functions (Orabona and Pál, 2021) and smooth functions (Orabona, 2023). Concretely, as shown in Orabona (2023) (which appears after the initial release of this paper), combining algorithms in Streeter and McMahan (2012): Orabona and Pál (2016) with normalization techniques (Levy, 2017) yields new algorithms that are also search-free parameter-free (in the sense of this paper), and universal. However, these algorithms are rather different from DoWG in algorithmic style: these algorithms only use normalized gradients while DoWG does use the magnitudes of the gradients; DoWG falls in the category of gradient descent algorithms with adaptive learning rate, while these algorithms do not.
3

---

Line search. As mentioned before, sine-search-base algorithms are universal and theoretically grounded (Nesterov, 2014) but are often expensive practice (Malitsky and Mishchenko, 2020).
AdaGrad family of methods. Li and Orabona (2019) study a variant of the AdaGrad stepsizes in the stochastic convex and non-convex optimization and show convergence when the stepsize is tuned to depend on the smoothness constant. Levy et al. (2018) show that when the stepsize is tuned properly the diameter of the domain in the constrained convex case, AdaGrad-Nome adapts to smoothness, Ene et al. (2021) extend this to AdaGrad and other algorithms,, and also to variational inequalities. Ward al. (2019); Traoré and Pauwels (2021) show the convergence of AdaGrad- Norm for any stepsize for non-convex (resp. convex) optimization, but in the worst case the dependence on the smoothness constant worse than gradient descent. Liu al. (2022) show that AdaGrad-Noma converges in the unconstrained setting when f is quasi-convex, but their guarantee is worse than gradient descent. We remark that all AdaGrad-style algorithms mentioned above require tuning stepsizes, and are thus not parameter-free.
Alternative justifications for normalization. There are other justifications for why adaptive methods work outside of universality. Zhang et al. (2020a) study a generalized smoothness condition and show that in this setting tuned clipped gradient descent can outperform gradient descent. Because the effective stepsize used in clipped gradient descent is only a constant factor away from the effective stepsize normalized gradient descent, (Zhang et al., 2020a), also show that this improvement holds for NGD. Zhang et al. (2020b) observe that gradient clipping and normalization methods outperform SGD when the stochastic gradient noise distribution heavy-tailed. However, Kunstner al. (2023) later observe that adaptive methods still do well even when the effect of the noise is limited.
3 Algorithms and theory
In this section we first review the different forms of adaptivity in gradient descent and normalized gradient descent, and then introduce our proposed algorithm DoWG. The roadmap for the rest of the paper is as follows: we first review the convergence of gradient descent in the Lipschitz and smooth settings, and highlight the problem of divergence under stepsize misspecification, and how normalization fixes that. Then, we introduce our main new algorithm, DoWG, and give our main theoretical guarantees for the algorithm. Finally, we evaluate the performance of DoWG on practical machine learning problems.
3.1 Baselines: gradient descent and normalized gradient descent
We start our investigation with the standard Gradient Descent (GD) algorithm:
F++1 [xx fxa)),
(GD)
where 1Ix is the projection on X' (when X = Rd, this is just the identity operator). The iterations (GD) require specifying the stepsize 7) > 0. When f is G-Lipschitz, gradient descent achieves the following standard convergence guarantee:
Theorem 1. Suppose that f is convex with minimizer T.. Let f. = f(x.). ). Let Do def
a
x.I be
the initial distance to the optimum. Denote by ūr + I the average iterate returned by GD. Then:
TT-1
(Bubeck, 2015) If is G-Lipschitz. the average iterate satisfies for any stepsize rj >> 0:
f(īT) - S. D
G/2
(2)
nTT 2
(Nesterov, 2018) I is L-smooth, then for all 17 1/2 the average iterate satisfies
2LD3
f(ør) - ff S 4+ TmL(2 - Ln)
Minimizing eq. (2) over 7) gives f.= -
-
DoG vF
with = GVT We have several remarks
to make about this rate for gradient descent. First. the optimal stepsize depends both the distance

---

1.9 to the optimum Do and the Lipschitz constant G. and in fact, this rate is in general optimal (Nesterov, 2018, Theorem 3.2.1). Moreover, we misspecify Do or G while tuning 7, this does not in general result in divergence but may result in slower rate of convergence. On the other hand, for the smooth setting the optimal stepsize is = E for which f(ær) - f. S
Unfortunately, to obtain this rate we have to estimate the smoothness constant L in order to choose a stepsize 7 < i. and this dependence is hard: if we overshoot the upper bound the iterations of gradient descent can diverge very quickly, as shown by Figure 1. Therefore, GD with a constant stepsize cannot be universal: we have to set the stepsize differently for smooth and nonsmooth objectives.
LD T
100
66
25
60-
2
10+
HIV PaY
vaulreir New
-050
-025
6.00
0.25
0.50
075
-2.6
0.0
3.0
355
Convergence with 17
(b) Divergence with 17 2.1
L
Figure 1: Two trajectories of gradient descent on the one-dimensional quadratic f(x) 2 with 100.
Lx2
2
Normalized Gradient Descent (NGD) (Shor, 2012) consists of iterates of the form
f((())))) 1) [Vf(2))1
T++1 1x
(NGD)
The projection step above is not necessary, and the results for NGD also hold in the unconstrained setting where the projection on X' = Rd is just the identity. NGD has many benefits: it can escape saddle points that GD may take arbitrarily long times to escape (Murray et al., 2019), and can minimize functions that are quasi-conves and only locally Lipschitz (Hazan et al., 2015). One of the main benefits of normalized gradient descent is that normalization makes the method scale-free: multiplying f by constant factor a > 0 and minimizing af does not change the method's 's trajectory adapt to the Lipschitz constant G in nonsmooth optimization as well as the
all. This allows smoothness constant L for smooth objectives, the following theorem states:
Theorem 2. Under the same conditions as Theorem 1, the iterations generated by generated by (NGD) satisfy after T steps satisfy:
(Nesterov, 2018) If is G-Lipschitz, the minimal function function suboptimality satisfies
D
n
min (E(0.L...TTT)
- f-] [f(xx))f+)5
G
(4)
2n
2
where Do ||000 x-
(Levy, 2017; Grimmer, 2019) If L-Lipschitz, the minimal function suboptimality satisfies
min [f(x)) - f.] 2 k=
D
+ 1
(5)
2ny
Tuning eq. (4) in 1 gives " Da and the stepsize is also optimal for eq. (5). This gives VT
convergence rate of D&G when f Lipschitz and D when f smooth. Observe that NGD 7
VT
matches the dependence of gradient descent on G and L without any knowledge of it. Furthermore that, unlike GD where the optimal stepsize is 1 7 in the smooth setting and Da in the nonsmooth GVT
5

---

setting. The optimal stepsize for NGD is the same in both cases. Therefore, NGD is universal: the same method with the same stepsize adapts nonsmooth and smooth objectives. Moreover, misspecification of the stepsize in NGD does not result in divergence, but just slower convergence. Another interesting property that we only get a guarantee on the best iterate: this might be because NGD is non-monotonic, as Figure 2 (a) shows.
10
suboptimality
10
50
100
150
250
Steps
Effective step size
10-3
Effective stepsize
2/L
50
100
150
200
250
Stops
Figure 2: NGD iterations on fz-regularized linear regression on the mushrooms dataset from Lib- SVM (Chang and Lin, 2011) with 7 = 0.1. Top (a) shows the function suboptimality over time. Observe that the number of iterations grow, the method becomes non-monotonic. Bottom (b) shows the effective stepsize Jeff,
0.1 [V][)]] over time.
Edge of Stability Phenomena. We may reinterpret NGD with stepsize 7 simply GD with time- varying "effective stepsize" Joff.t = |. We plot this effective stepsize for an &g regreuulad linear regression problem in Figure 2 (b). Observe that the stepsize sharply increases, then decreases until it starts oscillating around /.- Recall that ス the edge of stability for gradient descent: its iterates diverge when the stepsize crosses this threshold. Arora et al. (2022) observe this phenomenon for NGD, and give detailed analysis under several technical assumptions and when the iterates are close to the manifold of local minimizers.
Theorem 2 offers alternative, global, and less explicit explanation of this phenomenon: NGD matches the optimal gradient descent rate, and in order to do so it must drive the effective stepsize to be large. Specifically, suppose that we use the optimal stepsize nj
Da VT
and call the best iterate
returned by NGD 2,, Then I, satisfies f(z,) fx S
L
and therefore by smoothness T
1.2D8 T
L.D
[V[(x,]| (2L( fa)
Lm-
VT
This implies Netr.r |VM(ai| 2 1. Therefore the effective stepsize at convergence is forced to grow to 22 (7)). But if the effective stepsize increases too much and crosses the threshold a. the gradient norms start diverging, forcing the effective stepsize back down. Thus, NGD is self- stabilizing. We note that Edge of Stability phenomenon is not unique to NGD, and GD itself trains at the edge of stability for more complicated models where the smoothness also varies significantly over training (Cohen et al., 2021; Damian et al., 2023).
3.2 DoWG
We saw in the last section that NGD adapts to both the Lipschitz constant G and the smoothness L, we have to choose v) to vary with the distance to optimum Do = || - x. In this section, we develop novel algorithm that adaptively estimates the distance to the optimum, and attains the optimal convergence rate of gradient descent for constrained convex and smooth optimization up to logarithmic factor. Our algorithm builds upon the recently proposed Distance over Gradients (DoG)

---

algorithm developed by Ivgi et al. (2023). We call the new method DoWG (Distance over Weighted Gradients), and we describe it as Algorithm below.
Algorithm 1: DoWG: Distance over Weighted Gradients
Input: initial point zo E X Initial distance estimate r, > O.
2 Initialize 1-1 = 0, r-- Te- for t = . do
Update distance estimator: T3 f- max (1|ze- - zoll, PI-1)
Update weighted gradient sum: es + vt-1 + V [
Set the stepsize: 1/- V
7
Gradient descent step: I++1 < (x - n. ((()))
8 end
DoWG uses the same idea of estimating the distance from the optimum by using the distance from the initial point surrogate, but instead of using the square root of the running gradient the normalization, DoWG uses the square root of the weighted gradient sum 04 = Ei= F [f Observe that because the estimated distances i are monotonically increasing, later gradients have larger impact on tt than earlier
G. - | fxx)) )1²
compared G.. Therefore, we may expect this to aid the method in adapting to the local properties of the problem once far away from the initialization z0- We note that using a weighted sum of gradients is new: AcceleGrad (Levy et al., 2018) uses time-varying polynomial weights and Adam (Kingma and Ba, 2015) uses exponentially decreasing weights. The difference is that DoWG chooses the weights adaptively based on the running distance from the initial point. This use of distance- weighted averaging is new, and we are not aware any previous methods that estimate the running gradient sum in this manner.
Nonsmooth analysis. The next theorem shows that DoWG adapts to the Lipschitz constant G and the diameter D of the set X' if the function f is nonsmooth but G-Lipschitz. We use the notation log, I log x + following (Ivgi et al., 2023).
Theorem 3. (DoWG, Lipschitz f). Suppose that the function f is convex, G-Lipschitz, and has minimizer I. X. Suppose that the domain is a closed convex set of (unknown) diameter D >> Letre < D. Then the output of Algorithm I satisfies for some t {0, I...TT
GD VT
D log
-
Te
where T. def
Ete a k is weighted average of the iterates returned by the algorithm.
Discussion of convergence rate. DoWG matches the optimal O DG VT
rate of tuned GD and tuned
NGD up to extra logarithmic factor. We note that the recently proposed algorithms DoG (Ivgi al., 2023) and D-Adaptation (Defazio and Mishchenko, 2023) achieve similar rate in this setting.
Comparison with DoG. As we discussed before, DoWG uses an adaptively weighted sum of gradients for normalization compared the simple sum used by DoG. In addition, DoG uses the Ft
stepsize VEi |IV (=x)) whereas the DoWG stepsize is pointwise larger: since r is monotonically increasing in k we have
D.D.
Fry Et=o (+))))
VEL 1 [+)())
Of course, the pointwise comparison may not reflect the practical performance of the algorithms, since after the first iteration the sequence of iterates Z2, Zz. generated by the two algorithms be very different. We observe in practice that DoWG is in general more aggressive, and uses larger stepsizes than both DoG and D-Adaptation (see Section 4).
Smooth analysis. Our next theorem shows that DoWG adapts to the smoothness constant and the diameter D of the set X.
7

---

Theorem 4. (DoWG, Smooth f). Suppose that the function f is L-smooth, convex, and has minimizer v. E X. Suppose that the domain is closed convex set of diameter D > Let r, D.
Then the outpud of Algorithm satisfies for some E
{0, 1,
T
LD D
- 1, 1. --=
log
T
Tel
where T.
Exso kk= T is weighted average of the iterates returned by the algorithm.
The proof of this theorem and all subsequent results is relegated to the supplementary material. We note that the proof of Theorem 4 uses the same trick used show the adaptivity of NGD to smoothness: we use the fact that [x)l s v2I(f(x) f.) for x E X applied carefully-chosen weighted sum of gradients.
Comparison with GD/NGD. Both well-tuned gradient descent and normalized gradient descent achieve the convergence rate O LDA
where Do = -| x. S D for the constrained convex minimization problem. Theorem 4 shows that DoWG essentially attains the same rate up to difference between Do and D and extra logarithmic factor. In the worst case, if we initialize far from the optimum. we have Do
T
and hence the difference is not significant. We note that DoG (Ivgi et al., 2023) suffers from a similar dependence the diameter D of X, and can diverge in the unconstrained setting, where X' is not compact. This can be alleviated by making the stepsize smaller by polylogarithmic factor. A similar reduction of the stepsize also works for DoWG, and we provide the proof in Section in the supplementary.
Comparison with DoG. After the initial version of this paper, Ivgi et al. (2023) reported con- vergence guarantee for the unweighted average ir Ei= Th returned by DoG. In particular, Proposition 3 in their work gives the rate
To Er + FT) [(oT) -. L(Dolog+
LD T
=0
loy
T
Fc
where Do = ||:0 r. and where in the second step we used the bound Do S D and Fr S D. This rate the same as that achieved by the weighted average of the DoWG iterates up to an extra logarithmic factor log,, P. We note that DoG also has guarantee in the stochastic setting, provided the gradients are bounded locally with known constant, while in this work we have focused exclusively on the deterministic setting.
Function suboptimality
-0
[x)
10-2
Steps
Effective step size
10-4
10.4
Effective stepsize
2A.
Steps
Figure DoWG iterations on lz-regularized linear regression on the mushrooms dataset from LibSVM (Chang and Lin, 2011) with r. = 10-6 Top (a) shows the function suboptimality over time. Observe that as the number iterations grow, the method becomes non mon-moooo.iic Bottom (b) shows the DoWG stepsize over time.

---

Edge of Stability. Like NGD. DoWG also tends to increase the stepsize and train at the edge of stability. The intuition from NGD carries over: order to preserve the convergence rate of GD, DoWG tends to drive the stepsize larger. However, once it overshoots, the gradients quickly diverge, foreing the stepsize back down. Figure 3 shows the performance of DoWG and its stepsize on the same regularized linear regression problem as in Figure 2. Comparing the two figures, we observe that DoWG is also non-monotonic and trains close to the edge of stability, but its stepsize oscillates less than NGD's effective stepsize.
Universality. Theorems 4 and 3 together show that DoWG is universal, i.e. it almost recovers the convergence of gradient descent with tuned stepsizes in both the smooth and nonsmooth settings. As the optimal stepsize for gradient descent can differ significantly between the two settings, believe that achieving both rates simultancously without any parameter-tume tentieg or search procedures a significant strength DoWG.
4 Experimental results
10'
Tured Adegmas-nomm
Tran socuracy
Turnd Actegrad-nom
Adam
Adam
Step size
10
Doli
Docs
Teat
DoWS
DoWS
10
Adegoed
DoG mv
DoGS-ave
DoG
DoG
10
DoWS
DoWG ove
Adapt
80
150
Epoch
Epoch
100
10
90
Tedt socurag
Tured AdeCCred-rom
Train accursyy
10"
Adam
80
L-DuG
Step 6ize
10"
DoWS
70
Doli-we
L-Dols-n ove
ave
60
10
DoWiS-ove ove
DoWVG
50
50
100
150
200
0
50
100
150
200
0
20
60
80
100
Epoch
Epoch
Epoch
Figure 4: VGG11 (top) and ResNet-50 (bottom) training CIFAR10. Left: test accuracy, middle: train loss, right: step sizes.
We compare DoWG to DoG, L-DoG from Ivgi et al. (2023), for all of which we also report perfor- mance of the polynomially-averee
iterate with power 8 as recommended by Ivgi et al. (2023). We also add comparison against Adam (Kingma and Ba, 2015) with cosine annealing and the standard step size 10-3 All methods are used with batch size 256 with no weight decay on a single RTX3090 GPU. We plot the results in Figure 4 with the results averaged over 8 random seeds. We train the VGG11 (Simonyan and Zisserman, 2015) and ResNet-50 (He et al., 2016) neural network architec- tures on CIFAR10 (Krizhevsky, 2009) using PyTorrch (Paszke et al., 2019), and implement' DoWG on top of the DoG code?. Unsurprisingly, DoWG's estimates of the step size are larger than that of DoG and D- D-aappt-nomm. which also makes it less stable ResNet-50. While the last iterate of DoWG gives worse test accuracy than Adam, the average iterate DoWG often performs better.
Finally, we note that while both neural networks tested are generally nonsmooth, recent work shows local smoothness can significantly influence and be influenced by a method's trajectory (Cohen et al., 2022; Pan and Li, 2022). We believe this adaptivity to smoothness might explain the empirical difference between DoWG and DoG, but leave rigorous discussion of adaptivity local smoothness to future work.
http:/hhwb..com/kka//////// hnttp::/ggithu wttptthhwbb.omm/mm////gggg

---

References
Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on edge of stability in deep learning. arXiv preprint arXiv:2205.0972 abs/2205.097455, 2022. URL
https://arXiv org/ abs 22005 09745. (Cited on page 6)
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018. doi: 10.1137/16M10000173. URL https://d// org/10. 11000.117111100 1117/16110801777 (Cited on page 1)
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
doi: 10.1017/C80978051110000
(Cited on page 1)
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning 8(3-4):231-355 1-357, 2015. doi: 10.1561/22000000500 URL https: org/ 10. 100116112200000050, (Cited on page
Yair Carmon and Oliver Hinder. Making SGD parameter-free In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 Proceedings of Machine Learning Research, pages 2360-2389. PMLR, 2022. URL https://pppptt atttps:/pproceedingg mlr. wtt.sprrsss/1//// carmon22a. html. (Cited on pages 1, 2, 3, 17, and 18)
Nicolo
and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, USA. 2006. ISBN 0521841089, (Cited on page 3)
Nicolò BisscBBinchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to expert advice. J. ACM, 44(3):427 485, may 1997. ISSN 0004-5411, 1. doi: 10.1145/258128 255888118..58
URL https: :tttps://doi.. org/10. 1145/258128 258179.
(Cited on page
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011. (Cited on pages 6 and 8)
Jeremy M. Cohen, Simran Kaur, Yuanzhi Li, J. Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In JCLR. OpenReview.net, 2021. (Cited on page
Jeremy M. Cohen, Behrooz Ghorbani, Shankar Krishnan, Naman Agarwal, Sourabh Medapati, Michal Badura, Daniel Suo, David Cardoze, Zachary Nado, George E. Dahl, and Justin Gilmer. Adaptive gradient methods the edge of stability. arXiv preprint arXiv:2207. 0e.222277.4444, abs/2207.1144l 14484, 2022.
URL https: pictps://arXaa /arXiviivvv//..////aa///aaaa///a org/ a///abbb222200 11...21.22222 14484. (Cited page 9)
Ashok Cutkosky, Artificial constraints and hints for unbounded online learning. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 874 894. PMLR, 25-28 Jun 2019. URL https: / httpa////oooceeeeeeeeeeee mlr ppess/ /v99/ cutkosky1aa, html, (Cited on page 3)
Alex Damian, Eshaan Nichani, and Jason D. Lee. stabiittaii The implicit bias of gra- dient descent the edge of stability. The Eleventh International Conference on Learning Representations, 2023. URL https: http::::///peeeieee/. www.:eee//foooe www.miiinnnnnnhkh..... (Cited on page 6)
Aaron Defazio and Konstantin Mishchenko. Learning-rate-fiin learning by D-adaptation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 7449-7479. PMLR, 23-29 Jul 2023. (Cited on pages? 2, 3, 7, and 16)
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT 2010- The 23rd Conference on Learning Theory, Huifa, Isruel, June 27-29, 2010, pages 257-269, Omnipress, 2010. URL. ttttp://colt2011 haifa. il. iim. www.co////aaoo wtw.:i/.cco/pppprr////ii.ii.... htt.a//paapss//o.1000rrrrreeeee /CL.T2011procceeiingg pdf## page=265. (Cited pages 1 and 2)
10

---

Alina Ene, Huy L. Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7314-7321, 2021. (Cited on pages 2 and 4)
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Practical Methodology, chapter 11. MIT Press, 2016. URL http://www deepl eareigbonni org. (Cited on page 1)
Benjamin Grimmer. Convergence rates for deterministic and stochastic subgradient methods without lipschitz continuity. SIAM Journal Optimization, (92):1350-1365 2019. doi: 10.1137/ 18M1 1730XX. URL https: /toi. wwg/oogg///.o 100.1117//8811730666 (Cited on page 5)
Benjamin Grimmer. On optimal universal first-order methods for minimizing heterogeneous sums. arXiv preprint arXiv:2208. 08549, 01s/22088085499 2022. URL 08549. (Cited pages and 2)
Vineet Gupta, Tomer Koren, and Yoram Singer. A unified approach to adaptive regularization in online and stochastic optimization. arXiv preprint arXiv: 10111706665563 06569, bittps:/aarxee org/ 1ww./ 06569, (Cited on page 17)
2017. URL
Elad Hazan and Sham Kakade. Revisiting the Polyak step size. arXiv preprint 1r0Sv:1905.00311 abs/ 1905.00315 2019. URL https //trriaaa.i...//aa org/ aass/1955 00313. (Cited on pages 2 and 3)
Elad Hazan and Nimrod Megiddo. Online learning with prior knowledge, In Nader H. Bshouty and Claudio Gentile, editors, Learning Theory, pages 499-513, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540-72927-5 (Cited on page 3)
Elad Hazan, Kfir Y. Levy, and Shai Chalev-Shwarde Beyond convexity: Stochastic quasi-convex optimization. Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Confer- ence on Neural Information Processing Systems 2015, December 7-1 2015, Montreal, Quebec, Canada, pages 1594-1602, 2015. URL https: //t:://prrooc http///peeednn....///////// wwwpodiinnnnnnnnnnnneeeeeee neurips cc/paape/2015// hash /e/9///55aa52244477eeee2e222e211 a04ffaffffffffee Abstract html. (Cited on page 5)
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR). pages 770-778, 2016. doi: 10.1109/CVPR.2016..90 (Cited on page 9)
Maor Ivgi. Oliver Hinder, and Yair Carmon. DoG is SGD's best friend: A parameter-free dynamic step size schedule. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 14465-14499. PMLR, 23-29 Jul 2023. (Cited on pages 2, 3, 7, 8, 9, 15, 16, 17, and 22)
Ali Kavis, Kfir Y. Levy, Francis R. Bach, and Volkan Cevher. UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, ed- itors, Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 6257-6266, 2019. URL https: / http://e//oc/oepe/////oe nwwrips....... ips ctcccccpp/oo cccpppper/2019 hash/ 1aath/8888544477777133fff6ff66
Abstractt html. (Cited page 2)
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.0333 abs/2000..03399, 2020. URL htlttss////aXiv wwe.iivvorr///e httg//abs2000....e 03329. (Cited
on page 1.5)
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL /ttt:///rxivv wwwaaaiwww..aaaaaaaaaaaaaa org/abs//412 6980. (Cited on pages 1, 7, and 9)
Alex Krizhevsky. Learning multiple layers of features from tiny images. pages 32-33, 2009. wwttttsps///wwt cs. toronto. eeaitto..ddu/// wadl///kri/eeeannnggeeae page 9)
2009- TR. pdf. (Cited on
11

---

Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between SGD and Adan on transformers, but sign descent might be. In The Eleventh International Conference Learning Representations, 2023. URL https: //openreview wwt.:eeetffruree ad (Cited on page 4)
Puya Latafat, Andreas Themelis, Lorenzo Stella, and Panagiotis Patrinos. Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient. arXiv preprint arXiv:2301.04431, 2023. (Cited on page 3)
Kfir Y. Levy. Online to offline conversions, universality and adaptive minibatch sizes. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. December 4-9, 2017, Long Beach, CA, USA, pages 1613-1622 2017. URL https: http://ee/////ceeeengeeee newrips cc/ hwwp//aper///// /2017/ 05000000000000066660000880088880 Abstract html. (Cited on pages 3. 5, and 15)
Kfir Yehuda Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages /ttp/////..000000000000000000000
2018. URL https: / /ppoceedingggss neurips. Abstract html. (Cited on
pages 1, 2. 4, 7, 15, and 18)
Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of adam under relaxed assumptions. arXiv preprint arXiv:2304.1397, abs/2304.13972, 2023. URL https://ariii..om org/ abs/ /204.. 13972. (Cited on page 2)
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Confer- ence on Artificial Intelligence and Statisties, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 983-992. PMLR, 2019. URL http: http://pooceeeenneeeeee mlr, greas/v89/1it .ttm.. (Cited on page 4)
Zijian Liu, Ta Duy Nguyen, Alina Ene, and Huy L. Nguyen. On the convergence of AdaGrad(norm) on Rdd Beyond convexity, non-asymptotic rate and acceleration. arXiv preprint arXiv:2209. 14827, abs/2209. 14827, 2022. URL https: // arrivv.vvvvv....///..a/vaaaaa org/ abs/ /209. 14827. (Cited on page 4)
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julices Stochastic polyak step-size for SGD: an adaptive learning rate for fast convergence. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 1306-1314. PMLR, 2021. URL http://proceeding mlr. press/v130/ 1oizou21a. html. (Cited on page 3)
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Pro- ceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6702-6712 12. PMLR, 2020. URL http: ptttp://proceedings mlr. wwt..press/vi99. geress/vi19/maatttty/ mwlaaaayaallaaaammmmmmmmmmm html. (Cited on pages and 4)
H. Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference Learning Theory, COLT 2014, Barcelona, Spain. June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings, pages 1020-1039, JMLR.org, 2014. URL http: /ttaptt::/roooeeinng mlr, press/ v35 /33/m//mmaaa14. html. (Cited on page 3)
Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory, pages 2858-2887. PMLR, 2020. (Cited on page
12

---

Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. Conference on Learning Theory, pages 2490-2511. PMLR, 2019. (Cited page 3)
Ryan Murray, Brian Swenson, and Soummya Kar. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions on Automatic Control, 64(1 1):481844488 2019. doi: 10.1 10.1109/T...2099.20 100.09914999 14998. (Cited on page 5)
Yurii Nesterov. Universal gradient methods for convex optimization problems. Mathematical
Programmingg 152(112):311-404, 2014. doi: 10. 00.1007/11107-011-00753 org/10 10. 111.1100010000011000770770000 o. (Cited on pages 1, 2, and 4)
URL https://doi.
Yurii Nesterov. Lectures Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770. (Cited on pages and 5)
Francesco Orabona. Dimension-free exponentiated gradient. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https:://rp//oocciiingg www.reiiiinnnnnnnnneeeeeeeeeeire neurips ctt.cc/ppppp cc/paper_ files/panse page 3)
pdf. (Cited on
Francesco Orabona. Normalized gradients for all. arXiv preprint arXiv:2308.0555 05622,, abs/2308.05621, 2023. URL httpt::ttt//aaaee http:://///vvvv.e wwwp:/rgg///a./eeeeeeee hwtg/abb/3300.00655 05622.. (Cited on pages 2 and 3)
Francesco Orabona and Ashok Cutkosky. ICML 2020 tutorial on parameter-free online optimiza- tion. ICML Tutorials, 2020. URL pages 2, 3, 15, and 18)
tommicmm-aaa cutooiiatiiaa/. (Cited on
Francesco Orabona and Dávid Pál. Coin betting and parameter-fiee online learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 577-585, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819, (Cited on pages and 3)
Francesco Orabona and Dávid Pál. Parameter-free stochastic optimization of variationally coherent functions. arXiv preprint arXiv:2102.0022 abs/2102.000266, 2021. URL https:// org/ 0bs/2212.00223 (Cited on page 3)
Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. In Isabelle Guyon, Ulrike Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2160-2170, 2017. URL https: httpt::ppp/p/.oeeeeeeeee neurips. page 3)
httppp//0...aa/////ccc6/22222220 Abstract-bbbbbt.. html. (Cited on
Antonio Orvicto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. arXiv preprint arXiv:2205.0458. abs/2205.00458,, 2022. URL https://///aai org/ aba/aaas/.....//////////2 04583. (Cited on page 3)
Yan Pan and Yuanzhi Li. Toward understanding why Adam converges faster than SGD for trans- formers. OPT2023: 14th Annual Workshop on Optimization for Machine Learning, 2022. URL (Cited page 9)
https://openrew// wttpeeiwwwweeeeeeeeeeeee tt
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. URL http: http://papers neurips. cttpppprcccppr///cppppppp 9015-pytorch an- tat-imppratiie-eeeee sttplee-iggg---fffooomneeeeeee wewpeeeeeeeeeeeee--eeeeeeeeeeeee pdf, (Cited on page
learning- library.
13

---

David Patterson, Joseph Gonzalez, Quoe Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. arXiv preprint arXiv: 102.1044.0000 10350, abs/2104. 10350, 2021. https:/ httpttp:://ar/iv.orgraba//////// 10350. (Cited on page 1)
Boris Polyak. Introduction to optimization. Optimization Software, 1987. (Cited on pages 2 and 3)
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964. ISSN 0041-5553. htt////wssiinnceieeeeee/e com/
doi: https://0oooog////oooooo11111111
URL
(ttatc//arriice///////1116666611 (Cited on page
Or Sharir, Barak Peleg, and Yoav Shoham. The cost of training NLP models: a concise overview. arXiv preprint 0rX4v02004008900, abs/2004.08900) 2020. 08900. (Cited on page 1)
Naum Zuselevich Shor. Minimization methods for non-differentiable funccioon volume 3. Springer Science & Business Media, 2012. (Cited page 5)
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //axivv.//iv/////aa org/ abs/
abs//109. 1409. 1556. (Cited on page 9)
Matthew Streeter and H. Brendan McMahan. No-regret algorithms for unconstrained online convex optimization. In Proceedings of the 25th International Conference on Neural Information Process- ing Systems Volume 2, NIPS' 12, page 2402-2410, Red Hook, NY, USA, 2012. Curran Associates Inc. (Cited on page 3)
Cheik Traoré and Edouard Pauwels. Sequential convergence of AdaGrad algorithm for smooth convex optimization. Operations Research Letters, (9(4):452-458 2021. (Cited on page 4)
Rachel Ward, Xiaoxia Wu, and Léon Bottou. AdaGrad stepsizes: sharp convergence over nonconvex landscapes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference California. USA, volume 97 of Proceedings of Machine Learning Research, pages 6677-6686. PMLR, 2019. URL http:// ptttt::p/pprcceedngge mlr. ppwps/v97 /tt/9//wwrrda /ttp//aar19... html. (Cited on page 4)
Machine Learning. ICML 2019. 9-15 June 2019, Long Beach,
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus. S. V. N. Vishwanathan, and Ro- man Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Confer- ence on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4148 4158, 2017. URL httptttts////ceeeeee http://///oc//eeee////ee neurips. cc/ htppppper///// /hah//hhhh//// 81b3833625046477 947 (1w.7747777799b9441447 www.ses--sbstttttteeeeeeeaa html. (Cited on page 1)
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbahaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL /tttpp://openrevies net met//forumidd-BJgnXpa
(Cited on page 4)
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J. Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020b. URL https: httpp:://roceeeeaiiiiieeee /pppoceeiingeeeeeeeeeeeppee..ree neurips wttp:ccppp/p//////////// 0B016676...111100700060004400000 Abstract html. (Cited on page 4)
14

---

Supplementary material
Contents
Introduction
2 Related Work
3 Algorithms and theory
3.1 Baselines: gradient descent and normalized gradient descent
3.2 DoWG
6
Experimental results
5 Algorithm-independenn results
15
Proofs for DoWG
16
6.1 Smooth case
18
6.2 Nonsmooth case
20
7 Unconstrained domain extension
22
Algorihhn-independent results
In this section we collect different results that are algorihmn-independenn the first is consequence of smoothness:
Fact 1. Suppose that f is smooth and lower bounded by f.. Then all x E Idd we have, || < (L)) f.).
Proof. This is common result in the literature, and finds applications in convex and non-convex optimization see e.g. (Levy, 2017; Levy et al., 2018; Orabona and Cutkosky, 2020; Khaled and Richtárik, 2020). We include the proof for completeness. Let E Rdd and define x x -. f(x). Then by smoothness
L |1 x²|
L
( + (Vf(x), x)
2
f(x)
V
(1))
21 [1
1
f(x) 2T. |V [+)())
Because f is lower bounded by fa we thus have
f. f(x) < [(x) 2L |
Rearranging gives [ < (f(x)) - f.).
The next two results are helpful algebraic identities that will be useful for the proof of DoWG.
Lemma 1. (lygi et al., 2023, Lemma 4). Let ag. at be a nondecreasing sequence of nonnegative numbers. Then
t 0h ak-1 2 Voo).
15

---

Proof. This is (lvgi et al., 2023, Lemma 4), We include the proof for completeness:
a
(vkk vak-1)
( aa
+
vak-1
0k
Vax
k=1
s 2
(Vor 0kk vak-1)
k=1
2 ( vuo)
Lemma 2. ((Ivgi al., 2023, Lemma 3), similar to (Defazio and Mishchenko, 2023, Lemma 11)).
Let 8o, , be positive increasing sequence. Then
8i
1
log log, (ST/s0) -1)
T
max
81
where log, x def log x + 1.
Proof. This is (Ivgi et al., 2023, Lemma 3). We include the proof for completeness: Define K = [log sn and n I Then,
ST
(nn(++1)
K min log (n(++1) R-K
log
log
SD
8ykk
8pk
Rearranging and using K flog ST
gives
log en
(n(k+1)
min log
<
< 1.
&CK
K
K
Therefore,
8n(k-1)
min k<K
I c.
Snk
Thus,
8
St-n
Ma8 F
max ET
())
max
K
8
T
K
T
-1
K
T
2 11
1
log
ST
+
Proofs for DoWG
This section collects proofs for DoWG. First, we give the following lemma, which holds under convexity alone (regardless of whether f is smooth or Lipschitz).
16

---

Lemma 3. Suppose that f is convex and has minimizer Txs. For the iterations generated by Algo- rithm 1, we have
F (V - 2F, de + Fz] Uz-1,
(6)
K=
where d, = maxxgt dr-
Proof. This proof follows the proof of DoG (Ivgi al., 2023, Lemma 1), itself modification of the standard proof for adaptive cumulative gradient normalization methods (Gupta et al., 2017) incorporating insights from (Carmon and Hinder, 2022). We specifically modify the proof to handle the weighting scheme we use in DoWG. By the nonexpansivity of the projection we have
d | - x==ll" 1|
11k (z(x) 1=
1ik - x. 112 2nk [V (1x)) 2x - x.) +
df 21p (V f(xx), Ix σ.) + n ff(xx)]
Rearranging and dividing by 2nk we get
dk - + Uk [Vf(2=))
(V)())). x.)5
2T7
2
Multiplying both sides by F we get
FS (V) xx - =x,) - 1
df 1
+
t [f(xa)1
2 7l
2
Summing up as k varies from to - 1 get
(VI())) -2)) 2
(dk
dl++1)
r
[(
(7)
(A)
We shall now bound each of the terms (A) and (B). We have
(A)
K
(d
d
Σ
Uk (sk d
(8)
K=
of
de Vu-i1 Σ
dh (Vuk Uk /un-1
(9)
k=1
S &i - & Vu--1 + d t-1
(vox - v
(10)
= Vvz-1 I d! < 44 U1-
(11)
(12)
where eq. (8) holds by definition of the DoWG stepsize Tis eq. (9) holds by telescoping, eq. (10) holds because Us = Uk-1 + ( 2 uk-1 and hence uh 2 VUk-1, and di < di by definition. Equation (11) just follows by telescoping. Finally observe that de - ddè dZ de for some [t), and d3 de (d, (d, dd). Then by the triangle inequality and that the sequence
17

---

Fi is monotonically nondecreasing we have
dg de
[. I+ ||
| - I. ||
1xg Ft
< 100 roll
+ 100 - 3o
ra + Tτ
- Fs + Fz
< 2
Therefore de - df - (f. + (d + d)) - 4F,d, This explains eq. (12).
For the second term in eq. (7), we have
B
rt Vuk
[Vf((=))]
t-1
10ve0 +
V
f (xx)]² ?
euk
S SP/V00 +
0k
uk-1
Uk
-/ +
U/
Uk-1
Uk
Vi + 2
Ut- Vool
(13)
2F 1
(14)
where eq. (13) is by Lemma 1. Plugging eqs. (12) and (14) in eq. (7) gives
V 2z - x.) < 27,d, / Uz Pi
A=
2 [d + FF] Vo--i.
6.1 Smooth case
We now prove the convergence of DoWG under smoothness. In particular, we shall use Fact and the DoWG design to bound the weighted cumulative error S, = Σx 7 [f(x)) - f-] by its square root multiplied by problem-dependee of AdaGrad-Nor -orr (Levy et al., 2018), in reductions from online convex optimization to stochastic smooth optimization (Orabona and Cutkosky, 2020), and in the method of (Carmon and Hinder, 2022). However, in all the mentioned cases, the unweighted error M, = -i-1 (fxx) f.] is bounded by its square root. Here, DoWG's design allows us to bound the weighted errors S, instead.
constant. We note that similar trick is used in the analysis
Proof of Theorem 4. We start with Lemma Let t E [T]. By eq. (6) we have
(VST))) xx) < 2F, dd + Fel Vi-1-
(15)
18

---

Observe that by convexity we have
(Vi( Ixz z.) 2 f fxxx) f..
Using this to lower bound the left-hand side of eq. (15) gives
Σ -
- fa1
Σ p
(V -
k=0
k=0
2 de + Fz vt-11.
(16)
We have by smoothness that |V - 2l( - f.) for all Rd, therefore
V 21 Σ [f(x)) f.l.
Ut-1
Taking square roots we get
V S V2L,
Σ
(f(((x)) - fol.
(17)
k=n
Using eq. (17) in eq. (16) gives
Σ
(((())))))))))))))))))))(())){)) - f.1 s 2V2TF, (de + Fi)
Σ
[f()())) f.).
k=
fzz) for some k E [t 1] then the statement of the theorem is trivial. Otherwise, we can divide both sides by the latter square root to get
(((((x))) f s 2V2LF (de + Fr).
Squaring both sides gives
Σ (1(( SLF? (de + +r)²
K=
Dividing both sides by E111 F2 we get
8LF? (d, + Fr
Σ ()f((x)) f
Σt PM
k
8T. (de + mt)
k=
By convexity we have
-
Σ
(f)(())))))) - f4l
Σ 12 k=0
8L dh + FT)
(18)
Σ
By Lemma applied to the sequence 8
F2 we have that for some t [T]
T
-1) )
log+ Po
19

---

Because X' has diameter D we have r7
S
D2 and therefore
1
T
-1
1
(19)
log+
k=
We now have two cases:
If 2 2log+
D T
then
1 1
T
and we use this in eqs. (18) and (19) to get
Pb
log
Dz
20g
Dz 0
f(ā)) - f. 16eL (dg + F2)
PT
log
T
0
Observe that because X' has diameter at most D we have de + Fr S 2D, therefore
64eLD2
r2 2
L
D
-
log
0
log
T
0
fo
2log+ Ph
D2 If < 2log, "g
then 1 <
Let E
[T].
Using smoothness and this fact we have
f(tt) - S. s L x.112 s L1|3: 1.11
D
log
T
To
Observe Tz, v. E X and X' has diameter D, hence || - x2.11
-x,
- D2
and we get
LD
D2
LD²
f(ā,) fo S T
log
= 0
log fo
2 0
T
Thus in both cases we have that f(0)) f- = =0
(
LD*
log Fo
this completes our proof.
6.2 Nonsmooth case
We now give the proof of DoWG's convergence when f is Lipschitz.
Proof of Theorem 3. We start with Lemma Let E [T]. By eq. (6) we have
(VS())) - x.) s 2F. [d. + Ft] vn-ii
(20)
Observe that by convexity have
(Vf( 22 x.) 2 f(xx) - fa.
Using this to lower bound the left-hand side of eq. (20) gives
Σ (af((())) - fal Σ F ( f(xx)) 24 - x2))
k=0
< 2F, de + Ft| Ut-II
(21)
We have by the fact that f is G-Lipschitz that [V) < G2 for x E X. Therefore,
1
k=0
< G..
20

---

Taking square roots and plugging into eq. (21) gives
[-1
Σ
(d GVT. - -
k=0
Dividing both sides by k=
t-1 get
we
2 ld Fi] GVT
(f(x)) f.1
(22)
Σ
k=
By Lemma applied to the sequence
px we have that for some t E (T)
T
log+
k=0
Fb
Because Pr D we further have
T
-11 1
(23)
e
log+
k=
fo
We now have two cases:
If 2 2 log
D2 then
2
T
We can use this in eq. (22) alongside eq. (23) and
log
2log
of
the fact that log, x² max 2², 1) max log x, 1) S 2ogg x to get
2 (f(x) - fil [d. + Fr] G
D log
2k=oPh
VT
ño
Because the diameter of X' is bounded by D we have FT S D and de S D, using this and convexity we get
f(x)) -
(f(x)))) - fa]
Ek=0 h=
8 d + Ft
G
log ro
VT
16DG
D
log
VT
ro
If < 2log,
D' then
Fg
2 log
D2
4 log
D Fo
<
(24)
T
T
By convexity and Kauchy-Schwaate we have
f(x:) - S. S (
[++((*)]] x-
(25)
Because f is G-Lipschitz then [V+)(;:) < G and because X' has diameter we have [ || < D. Using this and eq. (24) in eq. (25) gives
f(x)) f. $ DG
D 4DG log Fo
T
Now because T 2 1 we have VT <T and hence
4DG Aoglog.
D
f(ā.) S. S
To
VT
[DG log
In both cases, we have that f(x)) - fo =
and this completes our proof.
vT
21

---

7 Unconstrained domain extension
In this section we consider the case where the domain set is unbounded, and seek dependence only on dg = To I= We use the same technique for handling the unconstrained problem as (lvgi al., 2023) in this section and consider DoWG iterates with the reduced stepsizes
7/
Ut = - +
(26)
Ue log 2
We prove that with this stepsize, the iterates do not venture far from the initialization. The proof follows (lvgi et al., 2023).
Lemma 4. (Stability). For the iterates r++1 22 Tu f (24) following the stepsize scheme given by (26) we have di < 12dg and i2 S 32d provided that ro S do-
Proof. By expanding the square and convexity
d di $ nz 1l
Summing up as varies from
and using (lvgi et al., 2023, Lemma 6)
22x))
F2
72 S
df
Uk
2k
4 log
2 20k
log 2k
4
Therefore we have df < df + the last equation get d? < 3df. Taking square roots gives de v3d,. By the triangle inequality we then get
Now suppose for the sake of induction that F? s 8df, then applying
4
||++11 zoll S || x.11 + ||, zoll S (1 + /3)d
Squaring both sides gives || xo1 < (1+ v < 8df This completes our induction and have of I 8df for all I. Finally, observe that
di
|| x= ||2]
zall + ||10 x. = + do I 2do.
follows that F 8df s 32d for all t. Finally, have df s df s 3d S 12d This completes our proof.
Therefore the iterates stay bounded, The rest of the proof then follows Theorems and 4 and is omitted for simplicity.. In both cases it gives the same results with Do = ||x0 x. instead of D, up extra constants and polylogarithmie factors.
22


Reviews:
[{"review_id": "aAVJMT0M7g", "reviewer": "Reviewer_jvtQ", "summary": "The paper proposes a new optimization algorithm, DOWG, that does not rely on additional hyperparameter tuning or a line search subroutine. Interestingly, the paper also contains a proof and analysis regarding the behavior of NGD and shows that (1) NGD adapts to the smoothness of continuous loss surfaces and (2) NGD operates at the edge of the maximum stable learning rate for continuous loss functions. Finally, the paper presents two empirical studies on CIFAR10 with two different neural networks. ", "questions": "Nil", "limitations": "Nil", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I am not an expert in optimization, but I thoroughly enjoyed reading this paper. The writing is clearly organized and accessible to readers with only some rudimentary knowledge of optimization. \n\nRegarding related work, the paper carefully assigns credit to existing work and precisely describes how the current work stands out at each step along the way, which demonstrates a high level of expertise in the field. \n\nThe theoretical contribution seems solid, and the new algorithm seems to be well motivated and work well, when compared with other parameter-free algorithms. I strongly recommend this paper be accepted. ", "weaknesses": "DOWG does not work as well as Adam with cosine annealing on both neural network problems. However, this is not very surprising because cosine annealing is extremely strong. I do not consider this to be a fatal issue. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your very positive evaluation of our work. We agree that Adam with cosine annealing is an incredibly strong baseline, and we hope that future work can reveal a principled way of improving over that."}, {"review_id": "rTwEHRznE7", "reviewer": "Reviewer_WSp1", "summary": "The paper proposes a new algorithm, DoWG, which modifies DoG (Ivgi et al., 2023) by utilizing the weighted sum instead of the usual sum for the squared gradients.\nConvergence is established for convex and convex & smooth deterministic settings, under the assumption of a (possibly unknown) bounded domain.\nThe method is adaptive to the Lipschitz/smoothness constant and is parameter-free in the sense that the bound of the domain may be unknown.\nExperiments comparing DoWG to several adaptive methods are presented.\nAdditionally, a complementary result for convex & smooth NGD establish that NGD is weakly adaptive to the diameter of the problem.", "questions": "6. Can DoWG achieve similar convergence results to DoG in the stochastic setting? If it is yet established, what is the additional difficulty with respect to DoG?\n7. In the deterministic setting, would DoG achieve similar convergence results to DoGW, or was the modification to DoWG necessary to address specific issues in that setting?\n8. What is the motivation for the problem of deterministic optimization with unknown bounded domain? Corollary 1 of Ivgi et al. (2023) mentions two-stage stochastic programming as an application, but is the deterministic counterpart of interest as well?\n\nOverall, while DoWG shows promise and may yield novel convergence properties, I find the current established guarantees to be partly insufficient compared to previous work on adaptive and parameter-free methods.\n\nEdit: Per the authors response regarding the unbounded case with adaptivity to $D_0$ and the improved log factor with respect to the smooth result of DoG (unknown at the time of submission), i raise my score.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The modification from DoG to DoWG is appealing as it results in larger stepsizes, potentially leading to faster convergence.\n2. A (limited) set of experiments is provided, demonstrating positive empirical evidence for the effectiveness of the DoWG method.", "weaknesses": "3. It is important to highlight that the convergence of DoWG is established exclusively in the deterministic setting, making it weaker than DoG's convergence, which extends to both deterministic and stochastic settings (note that AdaGrad-Norm results also apply to the stochastic setting). The paper should explicitly emphasize this difference and consider exploring DoWG's performance in the stochastic setting.\n4. The theoretical results for DoWG hold significance when dealing with unknown domain bounds. When the domain bound is known, AdaGrad-Norm with stepsizes $\\eta_t=D/\\sqrt{\\sum_t \\lVert \\nabla f(w_t) \\rVert^2}$ has tighter bounds for both convex and convex & smooth settings.\n5. The term \"parameter-free method\" typically used for rates that depends on the distance to the comparator or the minimizer. In this context the convergence of DoWG is not truly parameter-free as it is relevant only for bounded domains and does not improve with a good initialization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive evaluation and constructive criticism of our work. We agree that DoWG's main strength is that it allows for much larger stepsizes than DoG both in theory and practice.\n\nWe now address the weaknesses and questions:\n1. On the stochastic case: We agree that the stochastic case is important and merits exploration on its own, but we note that the results on the convergence of DoG in the stochastic case are *not* parameter-free, as they require knowledge of the Lipschitz constant $G$ on an unknown set. We have tried doing similar (non parameter-free) theory as in DoG, but unfortunately there is some added difficulty over the analysis of DoG. The main difference is that in DoG, the bound on $G$ is used to apply concentration and obtain that the cumulative noise is small. Because in DoWG we may have no such bound, we cannot apply the same concentration inequality, at least in the smooth setting. \n2. Comparison with AdaGrad-Norm: We note that if the domain bound is known, we can simply plug it into the initialization of DoWG, and DoWG will not change it: This is a consequence of Theorems 5 and 6, where if we put $r_{\\epsilon} = D$ (i.e. set the seed initialization to $D$) then $\\log_+ \\frac{D}{r_{\\epsilon}} = \\log \\frac{D}{r_{\\epsilon}} + 1 = \\log 1 + 1 = 1$. Therefore, the rate becomes exactly the same as AdaGrad-Norm, with no additional logarithmic factor.\n3. Convergence of DoWG for unbounded domains: We note that if we slightly reduce the DoWG stepsize, by using $\\eta = \\frac{r_t^2}{v_t} \\frac{1}{\\log_+ \\frac{v_t}{v_0}}$, this allows for convergence rates that depend only on $D_0$ rather than the domain bound $D$. The main reason we did not include this variant is that it did not perform well in practice. We shall include this variant and its theory in the final paper, should it be accepted.\n4. Comparison with DoG in the smooth setting: In the most recent version of the DoG paper, the authors show that a certain iterate averaging strategy can yield smooth rates for DoG. However, the rate they show is $\\mathcal{O} \\left ( \\frac{L D^2}{T} \\left [ \\log_+ \\frac{D}{r_{\\epsilon}} \\right ]^2 \\right )$ compared to DoWG's $\\mathcal{O} \\left ( \\frac{L D^2}{T} \\log_+ \\frac{D}{r_{\\epsilon}} \\right )$, thus DoWG obtains a superior guarantee without changing the averaging strategy. This might be because DoWG takes larger, more aggressive stepsizes than DoG.\n5. Motivation for unknown domain:  Our main motivation in DoWG is to apply this theory in practice. We note that in practice, a combination of reasonable initialization and bounded updates (enforced through e.g. gradient clipping) lead to a domain bound on the iterate that is unknown. For example, [1] show that neural networks with Gaussian initialization and bounded data norms are semi-smooth and generate a sequence of bounded iterates, with the domain bound being a quite complicated function of the neural network's architecture. While the objective of [1] is non-convex, our theory can instead be applied to convex neural networks with similar properties, e.g. Gated Linear Networks common in data compression algorithms [2].\n\n[1] Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song. A Convergence Theory for Deep Learning via Over-Parameterization. arXiv:1811.03962.  \n[2] Joel Veness, Tor Lattimore, David Budden, Avishkar Bhoopchand, Christopher Mattern, Agnieszka Grabska-Barwinska, Eren Sezener, Jianan Wang, Peter Toth, Simon Schmitt, Marcus Hutter. Gated Linear Networks. arXiv:1910.01526"}, {"review_id": "IP2JQnAHTs", "reviewer": "Reviewer_Uwk6", "summary": "This paper introduces a new algorithm for optimization problems. The paper introduces DoWG (Distance over Weighted Gradient) which is a simple extension of a previous work DOG (Distance over gradient). It is a parameter-free gradient optimization method where the step size is automatically adjusted to the function being optimized over the course of the optimization.\n\nThis works also provides justification of why DoWG produces close to the optimal convergence that can be achieved by Normalized Gradient Descent (NGD) for either Lipschitz or smooth functions. As part of this claim the authors also show a new derivation of the optimal convergence for NGD on smooth functions.\n\nFinally the authors show results on training Deep Nets for vision and these demonstrate the while DoWG performs better than other parameter-free methods it doesn't attain the level of accuracy achieved by momentum-based methods such as ADAM.", "questions": "- Does DOG have optimal NGD convergence for smooth functions? Have the authors found a reason why this is not the case or why this would be unlikely and could provide a justification?\n\n- Have the authors considered L-DOWG (layer-wise DOWG similar to L-DOG)?\n\n- The DOG paper (https://arxiv.org/pdf/2302.12022.pdf) in Table 2 page 14 show results for DOG that are superior than ADAM for training a model from scratch. Why could the authors not reproduce those results as a baseline?", "limitations": "Not applicable.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "## Defining Universality\n\nThe authors have very systematically defined their concept of a Universal Gradient Descent-based optimization algorithm. In fact as part of this definition of Universality they have computed the optimal convergence rate of NGD for smooth functions which appears to be a new result although it is not a very surprising result.\n\n## Discussions of NGD\n\nThe paper provides some very strong intuition about how NGD is self-stabilizing. The discussion and example in the paper provides good insight about how parameter-free methods work in general.\n", "weaknesses": "## Comparison to DOG\n\nThe proposed algorithm itself is only slightly different than the existing DOG algorithm and the intuition of why it was proposed is not that clear. The paper mentions that DoWG gives higher weight to later gradients, but why is this important? They do also demonstrate on line 263 that DoWG step sizes could be larger than DOG's and this seems reasonable, but overall the motivation for the improvement is not clear.\n\nNow the paper does show that DoWG has optimal NGD convergence for Lipschitz functions, but it points out that the same holds for DOG. There is no discussion of whether optimal NGD convergence that is proven for smooth functions with DoWG also holds for DOG or not. If the authors could prove that DOG *doesn't* have optimal NGD convergence for smooth functions then their claim that DoWG is the first parameter-free Universal gradient descent algorithm without a search subroutine would be overall stronger.\n\n## Performance Relative to ADAM\n\nThe authors should certainly be lauded for including a superior baseline result. However, the fact that ADAM does so much better than DoWG makes their work more of a theoretical curiosity.\n\nIt appears that the authors hurried through the final evaluation and included very limited results. The previous work that introduced DOG had results showing both fine-tuning as well as training a model from scratch. I would encourage the authors of the current work to do something similar as well as introduce variants such as L-DOWG.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you very much for your review.\n\nPlease find our rebuttal below:\n1. On motivation for DoWG: \"The paper mentions that DoWG gives higher weight to later gradients, but why is this important?\" The practice of assigning higher weights to later gradients is crucial to adaptivity to the loss curvature. For instance, if we start in a highly curved region where the gradients are large, a method that doesn't put a higher weight on the recent gradients would be stuck with small stepsizes for the rest of the training, even if it enters a flat region. This seems to be the reason why Adam works so well: it forgets older gradients at an exponential rate, as the gradient norm estimator in Adam can be written as $\\hat{v}_T = \\sum_{t=0}^{T} \\beta_1^t g_{T-t}$. The same holds for the recently proposed Lion optimizer. The motivation is that as the optimization process continues, we get closer and closer to a minimizer and thus recent gradients give a more accurate direction to the minimizer.\n2. On whether DoG can also converge for smooth objectives: at the time of writing the paper, DoG had no convergence guarantee in the smooth setting. In the most recent version of the DoG paper, the authors show that a certain iterate averaging strategy can yield smooth rates for DoG. However, the rate they show is $\\mathcal{O} \\left ( \\frac{L D^2}{T} \\left [ \\log_+ \\frac{D}{r_{\\epsilon}} \\right ]^2 \\right )$ compared to DoWG's $\\mathcal{O} \\left ( \\frac{L D^2}{T} \\log_+ \\frac{D}{r_{\\epsilon}} \\right )$, thus DoWG obtains a superior guarantee without changing the averaging strategy. This might be because DoWG takes larger, more aggressive stepsizes than DoG. Thus, while DoWG may not be the only algorithm that achieves universality, it is the best such algorithm in the literature.\n3. We have considered L-DoWG, and an additional coordinate-only version of DoWG. We have made these implementations available online, but cannot link them due to anonymity. However, we were already short on space for the submission and thus didn't include them. Should the submission be accepted, we shall use the extra page to add in both algorithms and their motivation.\n4. On superiority to Adam: Table 2 in the DoG paper shows that DoG with a polynomial decay averaging strategy performs better than Adam, but vanilla DoG does not. We reproduced a similar experiment in our paper, without the polynomial decay averaging. The results in our paper match those of Table 2 without polynomial decay averaging."}, {"review_id": "DX1q7i9GcO", "reviewer": "Reviewer_qfrF", "summary": "This paper considers the problem of optimizing a convex function over a convex, closed, and possibly compact set $\\mathcal{X}$. In particular, they are interested in finding a first-order method which is (i) universal (i.e., the same algorithm can be used when the objective is Lipschitz or smooth), (ii) parameter-free (i.e., converges without any hyperparameter tuning w.r.t. problem parameters) (iii) has no search subroutines, and (iv) strongly-adaptive (i.e., preserves the convergence rate of an optimally-tuned GD without tuning). The authors propose an algorithm, Distance-over-Weighted-Gradients, which (essentially) achieves all of these desired properties. The two caveats are (i) the convergence rates have an extra log factor not present in optimally-tuned GD, and (ii) the convergence rates depend on the diameter of the constraint set $\\mathcal{X}$ instead of on $D_0 = || x_0 - x^* ||$. Towards establishing this result, the authors prove that normalized GD universal but not parameter-free.\n", "questions": "The results of Ivgi et al. (2023) hold also in the stochastic setting (assuming stochastic gradients are uniformly-bounded). What are the main barriers to extending your results to the stochastic setting? Is there any similar result that you can obtain when, e.g., the noise of stochastic gradients is uniformly bounded? It might be beneficial to the paper to add a discussion on why extending to this setting is difficult.\n\nIn the introduction of your paper, you mention that the constraint set $\\mathcal{X}$ is “(potentially) compact“, However, your main results (Theorems 5 and 6) assume that the diameter $D$ of $\\mathcal{X}$ is finite (but unknown). Is it possible to extend these results to the unconstrainted case where $\\mathcal{X} = \\mathbb{R}^d$? \n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper provides an algorithm with the remarkable properties of being universal, parameter-free, (nearly) strongly-adaptive, and not requiring a search subroutine. Unless I have misunderstood, this seems to be the first such algorithm satisfying all of these properties simultaneously. Moreover, the analysis is well-written and easy to follow. I also found the discussion of the universal properties of normalized GD to be quite instructive and interesting. Overall, I think this is a very nice paper.\n", "weaknesses": "Much of the analysis appears to rely on or extend arguments from Ivgi et al., (2023). Further, the results in this paper are restricted to the deterministic setting, while the results of Ivgi et al. hold also in the noisy setting (albeit, assuming uniformly bounded stochastic gradients, and thus the results are restricted to the Lipschitz setting). Despite this, I still think the results in this paper are quite nice. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your positive evaluation of our work. \n\n1. On the stochastic setting: We agree that the stochastic case is important and merits exploration on its own, but we note that the results on the convergence of DoG in the stochastic case are not parameter-free, as they require knowledge of the Lipschitz constant on an unknown set. We have tried doing similar (non parameter-free) theory as in DoG, but unfortunately there is some added difficulty over the analysis of DoG. The main difference is that in DoG, the bound on the Lipschitz constant $G$ is used to apply concentration and obtain that the cumulative noise is small. Because in DoWG we may have no such bound, we cannot apply the same concentration inequality, at least in the smooth setting. We will add a more thorough discussion on this in the paper.\n2. Unbounded domains: It is possible to extend DoWG to work for unbounded domains by using the same \"taming\" trick as in DoG: that is, dividing the stepsize by a logarithmic factor. We have carried out the analysis and everything works. The reason we did not include this algorithm is that it does not perform well in practice. We will include it in the appendix should the paper be accepted."}, {"review_id": "MBi0sS7N2e", "reviewer": "Reviewer_oAov", "summary": "The paper presents a modification to the recently proposed DoG algorithm to obtain a adaptive algorithm for the deterministic, convex and [Lipschitz or Smooth] setting that does not need any hyperparameter to achieve a convergence rate competitive with algorithms that know the problem-specific constants.\n\nThe submission discusses the benefits of normalization, linking its behavior to the edge of stability phenomenon and providing an analysis that normalized gradient descent obtains the convergence of GD on smooth function with step-size 1/L without needing to know the smoothness constant.", "questions": "**Prior work**\n\nI found the discussion of the adaptivity to smoothness of normalized GD and the key inequalities (5—7) useful to understand how DoWG achieves a similar result. However, the paragraph prior to Theorem 4 should cite Levy (2017). Their analysis of what they call the AdaNGDk algorithm (an overly general form that recovers normalized gradient descent with a decreasing step-size of the order $1/\\sqrt{t}$\nfor k=1), in Theorem 2.1 is the equivalent of theorem 4 in the current submission, except with a decreasing step-size of $1/\\sqrt{t}$ rather than the constant but horizon-dependent step-size $1/\\sqrt{T}$ used here.\n\nKfir Levy, “Online to Offline Conversions, Universality and Adaptive Minibatch Sizes”, NeurIPS 2017 \n\n---\n\n**Formal definition for some concepts**\n\n**Strong vs. Weak Adaptivity**\n\nThe working definitions of “weak” and “strong” adaptivity are not clear from the current writing, or seems to lead to undesirable conclusions. I find the separation useful, and being able to formalize how sub-optimal the “adaptivity” of AdaGrad-Norm is in the smooth setting would be helpful. \n\nHowever, the definition of weakly adaptive requires that “[weak-adaptivity] just seeks non-divergence given stepsize misspecification. […] the algorithm’s objective is to ensure that the learning process does not result in divergence, even if the chosen stepsize is not optimal” (L145). This definition is problematic because an algorithm that does not move, or gradient descent with a step-size of 0, satisfies the above definition. \n\nSimilarly, for strongly adaptive, the text requires that “an algorithm [is strongly adaptive if] it preserves the convergence rate of optimally tuned gradient descent without any manual tuning.” The proposed DoWG algorithm does not fit this description as the rate worse, if only by a log-factor. \n\nA formalization of the above that could work would be to say that an algorithm is strongly adaptive in a problem setting if it achieves the same convergence rate, up to polylogarithmic terms, as an algorithm that knows problem specific constants. Weakly-adaptive could similarly be defined by allowing for multiplicative polynomial factors. \n\n**Adapting to geometry**\n\nThe term “adapting to geometry” is used in multiple places, but it isn’t clear what is meant by that statement. This term is often used in the literature as a way to convey the intuition of why a method is good, but with limited formalism. For example, Newton adapts to the geometry of the problem by using the Hessian, or AdaGrad adapts to the geometry of the problem by finding a preconditioner that is competitive with the optimal one in hindsight. On each usage of “adapting to geometry”, I do not understand what is meant,. I strongly suggest avoiding it and using a more direct description instead.\n\n- L32: “We say an algorithm is universal if it adapts to many different problem geometries or regularity conditions on the function f”\n(should be removed and only mention regularity condition)\n- L56: “In particular, such adaptive methods empirically show the ability to adapt to the local geometry of the problem (Cohen et al., 2022), especially compared to plain (stochastic) gradient descent (Pan and Li, 2022).”\nL107: “There are other justifications for why adaptive methods work outside of adapting to geometry.”\n- L246 “Therefore, we may may expect this to aid the method in adapting to the geometry of the problem once far away from the initialization x0.”\n\n---\n\n**A mention of the difficulties of obtaining similar results in online learning would be helpful to the reader.** \n\nWhile the online-learning algorithms of Streeter and McMahan (2012), Orabona et Pal (2016) and Orabona and Cutkosky (2020) aim for a similar goal of not having to know the diameter of the set and the Lipschitz constant, the rates presented for the current algorithm or those in the prior works of of Ivgi et al. (2023) and Carmon and Hinder (2022) are not achievable in the adversarial that is common in online learning, see Cutkosky and Boahen (2016, 2017).\n\nAshok Cutkosky, Kwabena Boahen, “Online Convex Optimization with Unconstrained Domains and Losses”, NeurIPS 2016\nAshok Cutkosky, Kwabena Boahen, “Online Learning Without Prior Information”, COLT 2017\n\n---\n\n**Question on Universality and the edge of stability**\n\nThe convergence of normalized GD or DoWG are not discussed under strong-convexity, which I think should be mentioned given the focus on universal algorithms. Especially as some alternative algorithms such as the Polyak step-size do benefit from strong-convexity, whether in the smooth or Lipschitz+bounded set case.\n\nGiven that the empirical results shown in Figure 2 are on a strongly convex problem and the effective step-size oscillates around a constant 2/L, I am interpreting it as the algorithm *not* achieving a linear rate (as the gradient norm should also go down as a linear rate, which does not seem to be the case if $\\eta/\\Vert\\nabla f(x_t)\\Vert$ is constant)?\n\n\n---\n\n**typo?**\n- L80: \"Orvieto et al. (2022) show that a variant of the Polyak stepsize with decreasing stepsizes can recover the convergence rate of gradient descent in the deterministic setting, provided the stepsize is initialized properly\" -- this should be stochastic?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The submission is well presented and I could understand the main objective of the paper at first read. The DoWG algorithm, and especially its proof, is simpler than the one found the prior work of Ivgi et al. (2023) on DoG, and would be an easier starting point for readers trying to understand algorithms that can adapt to the initial distance to the optimum.", "weaknesses": "Beyond the DoWG algorithm, the contributions are also already known in the literature. To the credit of the submission, this is clearly mentioned for the observation that normalized gradient descent on smooth functions leads to a similar behavior to the edge of stability phenomenon (Arora et al., 2022). However, the result that normalized gradient descent obtains the smooth rate can be found in the work of Levy (2017), which seems to have been missed. \n\nThe submission also suffers from a lack of formalism on some of its claims. Some concepts such as weak and strong adaptivity, “adapting to geometry” and what is meant by the edge of stability are left vague, and would benefit from a formal definition and nuanced discussion. \n\nIf those issues, detailed in the question section, are addressed in a revision, I will increase my score to 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and constructive criticism. \n\nWe address your concerns below:\n1. On normalized gradient descent: We thank you so much for pointing out that the algorithm of Levy (2017) reduces to normalized gradient descent. We were not aware of this work and will include it. We'd like to point out that because we do the offline case rather than online learning, our analysis is much simpler, as it is not a reduction from AdaGrad. The main contribution of our work is not the NGD analysis but the DoWG algorithm, and NGD's analysis is used as motivation. We will give the correct citation for the result on NGD's convergence in the revision.\n2. On weak vs strong adaptivity: We agree that the definition as-is is not very rigorous. We shall modify the definition per your suggestion, that an algorithm must also achieve the same rate as some baseline (e.g. Gradient Descent) that knows the convergence parameters. Moreover, we will add that we allow for polylogarithmic factors: this is not an artifact of our analysis, but is tight, as in general without knowledge of problem parameters we have to suffer at least a $\\sqrt{\\log \\log \\frac{D}{d_0}}$ or a $\\sqrt{\\log \\frac{D}{d_0}}$ factor, depending on the class of methods, see [1, Theorems 4 and 6].\n3. On \"adapting to geometry\": We agree that this term is too vague, despite its common usage in the literature on adaptive methods. Instead, we shall change it to adapting to smoothness/non-smoothness and/or regularity. We thank you for pointing this out.\n4. On strong convexity: Indeed, due to the fact that NGD forces the effective stepsize to be 1/L, NGD does *not* adapt to strong convexity out of the box if we use a constant stepsize. Therefore a linear rate is not possible. We note that if problem constants are known, it is possible to extend to use an exponentially decreasing stepsize to get linear convergence out of NGD (see [2]). However, in general, it is easy to adapt to strong convexity (for any parameter-free algorithm with rates under smoothness and convexity) without knowledge of problem constants at all using the restarting scheme of [3]. The application of the restarting scheme of [3] to NGD/DoWG is straightforward, and we will include it in the appendix.\n5. On the difficulty of obtaining the same results in the online learning setting: We agree that this would be instructive to include, the main difference is that in the offline setting, the adversary cannot change the function arbitrarily while just preserving the norm bound, as in the lower bound of [4]. Instead, the iterates have to come from the same function in response to the sequence of iterates picked by the algorithm. This allows for much improved rates. We will mention this in detail.\n\n[1] Konstantin Mishchenko and Aaron Defazio. \"Prodigy: An Expeditiously Adaptive Parameter-Free Learner\"  \n[2] Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee, Courtney Paquette. \"Subgradient methods for sharp weakly convex functions\".  \n[3] Renegar, James, and Benjamin Grimmer. \"A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order Methods\" Foundations of Computational Mathematics, vol. 22, no. 1, Mar. 2021, pp. 211–56. Crossref, https://doi.org/10.1007/s10208-021-09502-2.  \n[4] Ashok Cutkosky, Kwabena Boahen. \"Online Convex Optimization with Unconstrained Domains and Losses\""}, {"review_id": "2MretCRola", "reviewer": "Reviewer_jMMU", "summary": "This paper is concerned with parameter free - adaptive first order optimisation method, that is a method that achieves optimal rates of convergence in the class of function considered without having access to a priori quantities such as smoothness of the function or the minimum value of the function.\nThe authors discuss on normalized gradient descent and they show that this method is adaptive to the smoothness of the function when the step-size is proportional to the distance to the minimizer. \nThe main contribution of the paper is to introduce a new estimation of the distance to the minimizer that achieves optimal rate up to logarithm factor. The method is an improvement over the so-called distance over gradients (DoW) by introducing weights (DoWG) so that it gives more weight to the last gradients. \nNumerical experiments are provided, including comparison to Adam (which is not in the same category...).", "questions": "Could the rate obtained in the analysis of NGD be improved?\n\n- line 131: gives eta so that \n- line 554: Therefore.\n\n", "limitations": "do no apply.", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "I am not a specialist of the field so my contribution in this review was to check the proofs, also in the supplementary material.\n\nAll the proofs are correct. \n\nThe paper is globally nicely written, easy to read and accessible for an outsider of the field as I am. \n\nAlthough from the theoretical point of view, DoWG is incremental (correct me if I am wrong), numerical experiments tend to show that it is clearly more efficient practically.\n\nAlthough the resulting algorithm performs poorly compared to Adam, it seems a fair contribution on the understanding and the technics in the class of methods considered.\n", "weaknesses": "This work appears as an improvement over DoG. It is a bit surprising that the result on Normalized Gradient Descent is new; I was not able to find it in the literature although, again, I am not an expert in the field. \nThe proposed method DoWG of using weights in front of the gradients is a natural idea. \nFrom the theoretical results, DoWG seems a rather incremental advance over DoG.\n\nThe resulting algorithm is probably not going to have any impact on the optimization method in deep learning.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your evaluation of our work.\n\n1. \"The resulting algorithm is probably not going to have any impact on the optimization method in deep learning.\" On the contrary, the method has been independently implemented in at least one GitHub repository with 500+ stars for fine-tuning stable diffusion models, which we became aware of only after the submssion. We cannot link the repository per NeurIPS rules, but we can provide it to the Program Chairs for verification. \n2. On improving the rates for NGD: The rate for NGD in the non-smooth setting matches the optimal rate $\\frac{GD}{\\sqrt{T}}$ for first-order algorithms. In the smooth setting, we do not know if it can be improved. Our theory and experiments suggest the agreement is pretty tight, as we observe the effective stepsize indeed oscillates around $1/L$."}]

Author rebuttal:

Meta-review: After the author responses and discussion phase, all reviewers seem happy with the paper. I would strongly recommend that the authors incorporate the issues brought up in the reviews and discussion phase into the final version.
Decision: Accept (poster)