Implicit Regularization of AdaDelta
Authors: Matthias Englert
Ranko Lazic
Avi Semler
Venue: Accepted by TMLR ()

Abstract: We consider the AdaDelta adaptive optimization algorithm on locally Lipschitz, positively homogeneous, and o-minimally definable neural networks, with either the exponential or the logistic loss.  We prove that, after achieving perfect training accuracy, the resulting adaptive gradient flows converge in direction to a Karush-Kuhn-Tucker point of the margin maximization problem, i.e. perform the same implicit regularization as the plain gradient flows.  We also prove that the loss decreases to zero and the Euclidean norm of the parameters increases to infinity at the same rates as for the plain gradient flows.  Moreover, we consider generalizations of AdaDelta where the exponential decay coefficients may vary with time and the numerical stability terms may be different across the parameters, and we obtain the same results provided the former do not approach 1 too quickly and the latter have isotropic quotients.  Finally, we corroborate our theoretical results by numerical experiments on convolutional networks with MNIST and CIFAR-10 datasets.

Published in Transactions on Machine Learning Research (12/2024)
Implicit Regularization of AdaDelta
Matthias Englert"
m.cegglert@wwrrwicc.c.... uk
University of Warwick
Ranko Lazić* University of Warwick
r.s.laaio@warwicc.ccc uk
Avi Semler
avi. wet.smeeer@uuurrree wwwrwickwwccooommmmmmmmm ac. uk
University of Warwick
Reviewed on OpenReview: https: // openreview. net/ forun? id= .d=nm400. Obb bwoR
Abstract
We consider the AdaDelta adaptive optimization algorithm on locally Lipschitz, positively homogeneous, and o-minimally definable non-smooth neural networks, with either the exponential the logistic loss. We prove that, after achieving perfect training accuracy, the resulting adaptive gradient flows converge in direction to Karush-Kuhn-Tuuch point of the margin maximization problem, i.e. perform the same implicit. regularization as the plain gradient flows. We also prove that the loss decreases to zero and the Euclidean norm of the parameters increases to infinity at the same rates as for the plain gradient flows. Moreover, we consider generalizations of AdaDelta where the exponential decay coefficients may vary with time and the numerical stability terms may be different across the parameters, and we obtain the same results provided the former do not approach 1 too quickly and the theoretical results by numerical
latter have isotropic quotients. Finally, corroborate experiments convolutional networks with MNIST and CIFAR-10 datasets.
1 Introduction
Understanding when, why, and how training overparameterized neural networks by gradient-based algorithms achieves good generalization (Zhang, Bengio, Hardt, Recht, and Vinyals, 2021; Belkin, Hsu, Ma, and Mandal, 2019) remains one of the central questions in machine learning, despite several years of vibrant research. Much progress on the question has been made by investigating implicit regularization (or implicit bias) (Neyshabur, Bhojanapalli, McAllester, and Srebro, 2017): the mysterious preference of the training algorithms for interpolators that perform well at test time.
Buiding on the seminal work of Soudry, Hoffer, Nacson, Gunasekar, and Srebro (2018), one of the most celebrated results in the field was obtained by Lyu and Li (2020); Ji and Telgarsky (2020): that after achieving perfect training accuracy, gradient flow implicitly regularizes locally Lipschitz, positively homogenous, and o-minimally definable non-smooth networks so that their paramcters converge in direction to a margin maximization KKT point. This precise bias towards margin maximization for this wide class of networks has been the basis of numerous theoretical works (cf. Vardi (2023)), as well remarkable practical methods such the reconstruction of training data by Haim, Vardi, Ychudai, Shamir, and Irani (2022); Buzaglo, Haim, Yehudai, Vardi, Oz, Nikankin, and Irani (2023).
Nevertheless, already Soudry et al. (2018) observed that algorithms such as Adam (Kingma and Ba, 2015) may not perform the same implicit regularization, and posed the research question:
Can we characterize the bias of adaptive optimization algorithms for classification problems?
'Equal contribution.

---

Published in Transactions on Machine Learning Research (12/2024)
The pertinence of this question was further attested by Wilson, Roclofs, Stern, Srebro, and Recht (2017); who demonstrated that, for several realistic deep learning models, the solutions found by adaptive methods often generalize significantly worse than those found by stochastic gradient descent, even when the former solutions have better training performance.
Extending the pioneering work of Gunasekar, Lee, Soudry, and Srebro (2018); Qian and Qian (2019); Zhou, Feng, Ma, Xiong, Hoi, and E (2020), major advance was made by Wang, Meng, Chen, and Liu (2021) who proved that, for the same wide class of networks as admitted by Lyu & Li (2020); Ji & Telgarsky (2020) and in the continuous setting corresponding to an infinitesimal learning rate, if the adapter' of an algorithm without momentum can be shown to converge to an isotropic vector without large fluctuations, then the implicit regularization is the same as for plain gradient flow. They also established that this holds for RMSProp (Hinton, Srivastava, and Swersky, 2012) and Adam without momentum," 2 but fails for AdaGrad (Duchi, Hazan, and Singer, 2011).
Our contributions. In this work, we tackle the posed research question for AdaDelta (Zeiler, 2012), which has remained open. AdaDelta is one of the main adaptive optimization algorithms, implemented in PyTorch? and known to perform well in many circumstances compared to other algorithms including RMSProp and Adam (cf. egg. Ruder (2016)). Specifically:
we overcome the technical challenge of AdaDelta having exponentially decaying averages in both the numerator and the denominator of the adapter (which makes it not readily amenable to the techniques of Wang ct al. (2021)), and prove that the adapter has the required convergence propertics, which enables us to conclude the same implicit regularization as for plain gradient flow;
we show that the implicit regularization critically depends on the numerical stability terms in the numerator and the denominator of the adapter, and that it changes if they are permitted to have different components so that their quotient is not isotropic;
we also investigate permitting the exponential decay coefficients to vary with time, and show that under a mild assumption on their integrals, the implicit regularization is not affected;
we corroborate these theoretical results in three empirical settings, ranging from a simple visualization to a 14-layer convolutional network on CIFAR-10.
Further related work. The implicit regularization of adaptive optimization algorithms was the focus of several other recent. works. Wang, Meng, Zhang, Sun, Chen, Ma, and Liu (2022) proved that momentum does not affect the implicit bias towards margin maximization for linear classification. Tarzanagh, Li, Zhang, and Oymak (2023) showed margin maximization when optimizing attention by gradient descent. Cattanco, Klusowski, and Shigida (2024) studied the implicit bias of Adam and RMSProp by backward error analysis. Zhang, Zou, and Cao (2024) established that Adam without a numerical stability term maximizes the oc-nomm margin for linear logistic regression. Some of the prior empirical works on generalization of adaptive methods are Keskar and Socher (2017); Zaheer, Reddi, Sachan, Kale, and Kumar (2018); Luo, Xiong, Liu, and Sun (2019); Chen, Zhou, Tang, Yang, Cao, and Gu (2020).
Convergence properties of the popular Adam algorithm have been considered further in works that include the following. Wang, Fu, Zhang, Zheng, and Chen (2023) proved a tight upper bound on Adam's iteration complexity. Wang, Zhang, Zhang, Meng, Sun, Ma, Liu, Luo, and Chen (2024) studied convergence of randomly reshuffled Adam with diminishing learning rate and without assuming bounded smoothness, and showed that it can be faster than stochastic gradient descent with diminishing learning rate. Thilak, Littwin, Zhai, Saremi, Paiss, and Susskind (2024) identified and investigated a slingshot phenomenon in late-stage Adam and related it to grokking (Power, Burda, Edwards, Babuschkin, and Misra, 2022). Xie and Li (2024) showed that Adam with decoupled weight decay implicitly performs constrained optimization.
II adaptive algorithm, for each model parameter, the learning rate is adapted by separate coefficient. The "adapter" consists of those coefficients, and is updated at every step of the algorithu. "Here the difference between RMSProp and Adam without momentum is that the latter involves bias-correction coefficient in the computation of the exponentially decaying average.
/tttpp://pytorch http:////pporrtoooott///sesseeee wrt/docs/staaallaaaeeeeeoe/ wtwp///ccs/taaabe//eeeeeeed/edde gegereteeettorraeo optin. Adadelta ta. html
2

---

Published in Transactions on Machine Learning Research (12/2024)
A number of works have investigated convergence of classes of adaptive optimization algorithms with momentum, often by means of continuuus-time limits. Da Silva and Gazeau (2020) derived a system of non-auronomous differential equations that is the limit for a class of algorithms that includes Adam, AdaFom, Heavy Ball, and Nesterov's Accelerated Gradient (NAG); and they studied convergence of its trajectories. In a concurrent work, Barakal and Bianchi (2021) focused on a similar system of equations, handling an irregular vector field that arises from the original version of Adam, and establishing further connections with the discrete-time iterates. The latter were extended by Barakat, Bianchi, Hachem, and Schechtman (2021) to allow noise in the Euler discretization of the non-autonomous differential equation system, thus being able to express algorithms such as stochastic Heavy Ball and stochastic NAG, and in particular to prove convergence of stochastic NAG in & non-convex setting. In a concurrent work, Gadat and Gavra (2022) were also able to prove almost. sure escape of local maxima with low mini-batch noise level. More recently, Xiao, Hu, Liu, and Toh (2024) provided a framework for establishing convergence properties of Adam faaail algorithms without assuming smoothness, which is thus applicable to neural networks with non-smooth activations.
Understanding generalization in deep learning by means of obtaining bounds in terms of the normalized margin and related quantities has attracted extensive attention, ef. e.g. Bartlett, Foster, and Telgarsky (2017); Neyshabur, Bhojanapalli, and Srebro (2018); Golowich, Rakhlin, and Shamir (2018); Wei, Lee, Liu, and Ma (2019); Wei and Ma (2020); Glasgow, Wei, Wootters, and Ma (2023). Although a variety of questions remain open, there is significant evidence behind the general understanding that larger normalized margins lead to better generalization, cf. e.g. (Jiang, Krishnan, Mobahi, and Bengio, 2019; Jiang, Neyshabur, Mobahi, Krishnan, and Bengio, 2020).
2 Preliminaries
Basic notation. We write: [n] for the set {1,..., (u, v) for the inner product of vectors u and w; ||a|| /(0,e) v) for the Euclidean length of a vector v; v, for the ith component of a vector v; 0, 1, oo, etc. for the vectors whose dimension inferred from the context and whose all components are equal to the specified value, that for all i we have 0, = 0, 1, 1, 20, = oc, etc.
Provided u and v are vectors of equal dimensions, we write uv, u/v, v², Vē, etc. for the component wise product, quotient, square, square root, etc. operations, so that for all i we have (uv); = u,v, (u/v); = u./u; (v²); (v.)², (Vo); = Vu,, etc. Similarly, we write u < v, u S v. etc. for the component-wise less, less than or equal, etc. relations, so that we have u C U + Vi: u, < Us u < + Vi: u, S v;, ctc.
Local Lipschitz continuity and the Clarke subdifferential Suppose a function f: + Lipschitz, iee. every point v E I2* has a neighborhood U such that f is Lipschitz continuous on U. By Rademacher's theorem (cf. e.g. Borwein and Lewis (2010, Theorem 9.1.2)), then f is differentiable almost everywhere. The Clarke subdifferential of f at a point v is the convex hull
is locally
af(v): = conv lim (
VS((())
lim ( v and ()((()) exists for all i) i=
It nonempty and compact for all v, and equals the singleton [Vf(v)} if f is continuously differentiable at v (Clarke, 1975). It consists of subgradients, which we may refer to simply as gradients.
O-minimal structures and definable functions. An o-minimal structure S a family (5+) such that: each S₁ is a set of subscts of R S₁ the set of all finite unions of open intervals and points; cach Se contains the zero sets of all polynomials on R*; each S& is closed under finite union, finite intersection, and complement; each Sk*R contains the Cartesian products of all sets in S₁ and Syy; each Sy contains the projections of all sets in S onto the first & components. A function f: R - TR is definable in S if and only if its graph is a set in SK+K
For every o- o-minimal structure, the collection of all definable functions is closed under algebraic operations, composition, inverse, maximum, minimum, etc. (cf. e.g. Ji & Telgarsky (2020, Appendix B)). Morcover, by Wilkie's theorem (Wilkie, 1996), there exists an o-minimal structure in which the exponential function is definable.
3

---

Published in Transactions on Machine Learning Research (12/2024)
Procedure 1 Discrete generalized AdaDelta. In step k + 1, using a current gradient Ö[(w)) E (t(w(()), it computes the next exponentially decaying average 9x+1 of squared gradients, and computes the next adapted gradient A++1. It then computes the next exponentially decaying average h of squared adapted gradients, and computes the next parameter vector Ws+1 by subtracting A scaled by the learning rate. The hyperparameters are: learning rate 7) > 0, exponential decay coefficients Ps E [0, 1]"; and numerical stability terms case where Pk e for all k, and ò = E e1. By specializing further to = 1, we obtain the original AdaDelta (Zeiler, 2012).
and 0. The implementation of AdaDelta in PyTorch" corresponds to the special
Ik+1 Ph.Pa + (1 - (1-pp))C(uu) )x)
E E+ hv TL(w))
h hh + (1 4 1
A Ak+1
8
9k+1
Wk+1 wK - - k+1
Predictor and loss functions. We assumee the following properties of the predictor function ((w, æ) with parameters u E R2, inputs z E IRd, and scalar outputs. The L-positive homogencity mcans that scaling the parameters w by any a > 0 scales the output by at, i.e. D(ow,, x)) = <b (1,,,)))) a))
Assumption 1. For some L > O and some o-minimal structure S in which the exponential function is definable, for each æ we have that D(w, x:) as a function of w is: (i) locally Lipschitz; (ii) L-pposifively homogeneous; (ttt) definable in S.
This assumption admits neural networks that are constructed from a wide variety layer types, including fully connected, convolutional, ReLU, Leaky ReLU, Square ReLU, cube activation, and max-pooling, which may be composed arbitrarily. Points of hondifferentiability, such at in the case of the ReLU nonlinearity, are permitted because assume only local Lipschitzness instead of continuous differentiability and work with the Clarke subdifferential instead of the gradient. However, due to the L-positive homogeneity (ii), skip connections are excluded, biases are excluded except at the first layer, and activations based on the exponential function (c.g. sigmoid activation) are excluded. The homogencity exponent L is the degree to which the parameters are multiplied when computing the network output. this may be determined by starting with exponent 0, then going forwards through the layers and e.g.: adding 1 the exponent the layer fully connected, not changing the exponent if the layer is ReLU, doubling the exponent if the layer is Square ReLU, etc.
We consider minimizing the total loss L(w) = Σm= () ())), which is with respect to finite dataset {(x(() Rd (0) {+1])]² and where the individual loss function is one of:
for the exponential loss; ((2) = [og(1+e77) for the logistic loss.
c==
Now make use of the definability of the exponential function in the o-minimal structure (The exponential function was effectively excluded by the homogeneity clause (ii) from the building of the predictor function (ww, x))) Since the individual loss function é (in both cases, exponential and logistic) is locally Lipschitz and definable in S, the same is true of the total loss function L. Note however that the loss functions we consider are not homogeneous.
struncurrsrruuuuure S from Assumption 1.
Generalized AdaDelta flow trajectories. The starting point of our analysis is the adaptive gradient descent of Procedure 1, which is generalization of AdaDelta (Zeiler, 2012) by allowing: the learning rate to be specified (this is already the case in the PyTorc implementation"), the exponential decay coefficients to vary with time (e.g. by following a specified schedule), and both those coefficients and the numerical stability terms to be specified differently across the vector components.
The focus of our thcoretical study the adaptive gradient flow that corresponds to the adaptive gradient descent with an infinitesimal learning rate. To arrive at its definition, we first restate the equations of Procedure 1 as follows. We eliminate the auxiliary variable A 1,, we suppose the hyperparameters Ps obey
4

---

Published in Transactions on Machine Learning Research (12/2024)
Process 2 Continuous generalized AdaDelta. This adaptive gradient flow, where @L(w(t)) E aL(w(()) is a gradient of the loss at the current parameters w(t), corresponds to the adaptive gradient descent of Procedure with an infinitesimal learning rate. The hyperparameters are: exponential decay coefficienss schedule p: [0, oo) + [0, 1J,, and mumerical stability terms 0 and & > 0.
g'(l) = (1 - (()))((()(())² -g(() h'()) (1 p(())(w h(t))
(2)
h(t) h(t) dl(w(I))
w w'(1) = V 5 + g()
(3)
that (1-PP- PpP)// is constant with respect to the hyperparameter 77, and we replace steps & by times kn:
g(t + n) -(()) (1 p(1) ())( -1())
"1
htt 1)) h((t) = (1)) ((w(t +1) ( n((t)
wt + n) - -w(() 6 g g((+ dl(w(t))
+ h(t)
1
Now, regarding these equations determining the endpoints g(l + 1)), h(t + n), w0l + n) of the next line segments in some continuous polygonal curves g. h, w: [0, o0) - RR' born from the adaptive gradient descent of Procedure with learning rate (cf. e.g. Elkabetz and Cohen (2021)), letting tend to 0 we obtain that the limits of their directions are given by the sight-hand sides of eqs. (1) to (3), which we take to be the derivatives that determine the adaptive gradient flow we are seeking.
We therefore analyze trujectories g, h, w: [0, 00) + R' of the two exponentially decaying averages and of the parameters, which are ares (i.e. absolutely continuous every compact subinterval) and which obey the adaptive gradient flow of Process 2 for almost all 2 O.
Assumption 2. (i) Su (1 p(1))dt= co. (ū) ( 2 0 and (0)) 2 0. (il)) There exists a time to such that ((w(to)) < <()).
This is a mild regularity assumption. Part (i) ensures that the exponential docay coefficients are not scheduled to approach so fast that they stop the learning, and for example it is satisfied by any constant coefficients smaller than 1. Part (ii) just requires that the exponentially decaying averages of squared gradients and squared adapted gradients are initialized as nonnegative (in original AdaDelta they are initialized to zero). Part (iii) assumes that the dataset is separable by the network, moreover that for every paramcters trajectory that we consider arising from the generalized AdaDelta flow, there exists time lo at which separation (Lee the perfect training accuracy) is achieved; this commonly occurs when training overparameterized neural networks by gradient based algorithms (cf. c.g. Zhang et al. (2021)). We also remark that, for both the exponential and the logistic individual loss function f(z), f(z) is defined by f(z) = e f(z), then f(z) is monotonically increasing, and so the condition L(ur(to) < ((0) is equivalent. to f (logl (/(((u(()))))) 0.
Admittance of chain rule. Since the total loss function is locally Lipschitz and definable in S (for both the exponential and the logistic individual loss functions), and the trajectory of the parameters is an arc, we are able to use the following fact applicd to them.
Proposition (Davis, Drusvyatskiy, Kakade, and Lee (2020, Theorem 5.8)). If f: 12t + R is locally Lipschita and definable in an o-minimal structure, then il admils a chain rule: for all ares v: [0, 0o) + RR almost all t 2 0, and all u e @f(v(t)), we have df(v(t))/dt (u, du(t)/)))
Directional convergence, KKT conditions, and margin maximization. That trajectory converges in direction to vector means lim v(())||(((]I u/ ||]]]
5

---

Published in Transactions on Machine Learning Research (12/2024)
Following Dutta, Deb, Tulshyan, and Arora (2013, Section 2.2), supposing f. 9......... RR - R are locally Lipschitz, we have that I& is Karrss-Kuuhrg Kuhn-Tucker point of the problem
minimize: f()) subject to: gi(b) for all [n]
if and only if there exist Lagrange multipliers A An 2 0 such that:
(feasibility) g:(v) S 0 for all i E [n];
(equilibrium inclusion) 0 E 0f(v) + E (,0g( (complementary slackness) ( (w) 0 for all i [n].
For local optimality, these first-order conditions are necessary, however in general not sufficient.
The margin of parameters vector w is the smallest label-adjusted prediction for an input, i.e. formally minge[n] (d (())(vvv) (w, ())). By the L-positive homogeneity of the predictor function (cf. Assumption I.(i)), the normalized margin
min ( (w x ( will min ( ( (ur//|/rll rEin]
[E(m)
depends only the direction of w, and it is straightforward to show that the directions that maximize it are also the optimal directions of the problem
minimize:
subject to: (w, (0) 2 for all i e [n]
(4)
3
Main result
We prove that continuous generalized AdaDelta obeys the same tight rates for convergence of the loss and growth of the parameters as were established for plain gradient flow by Lyu & Li (2020, Corollary A.11), and also implicitly regularizes the parameters to converge in direction to a KKT point of variant of the margin
maximization problem in eq. (4), in which the objective function ||/ is replaced by the skewed 2 V wil?. If the quotient 6/c of the numerical stability hyperparameters is isotropic (i.c. 6,/E, are equal for all j E [p]), then this modification does not alter the directions of the KKT points, so the implicit regularization is the same as was established for plain gradient flow by Lyu & Li (2020, Theorem A.8) and Ji & Telgarsky (2020, Theorem 3.1). Otherwise, the sets of points that have the same objective value 1 v/e w/l2 are ellipsoids which are not spheres, and the directions of the KKT points may be different from those for the margin maximization problem in eq. (4). Moreover, these conclusions are robust with respect to changing the exponential docay coefficients schedule p hyperparameter.
Theorem 2. Under Assumptions and 2, for the continuous generalized AdaDelta defined in Process 2, with either the eaponential loss or the logistic loss, we have that L(w(t)) = [((ng))) [|w((t]] O(log 1)1/4,, and w(t) converges in direction to KKT point of the problem
minimize: LI 12
subject to: y (w, x()) 2 1 for all i [n]
The growth of the Euclidean length [|w(())] of the parameters to infinity during the training process is an artifact the L-positively homogencous predictor function and the strictly deercasing individual loss function (both exponential and logistic) indeed, once perfect training accuracy achieved, scaling the parameters w(t) by any a > 1 decreases the total loss. Theorem 2 however establishes that this growth is slow, bounded above and below by the th root of log Note also that the convergence shown in Theorem 2 to KKT point of the skewed normalized margin maximization problem is directional, and so independent of the growth of [t]]-
Remark 3.
Our proof of Theorem 2 builds on the following result, stated here in terms of the notations in this paper.

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 4 (Wang et al. (2021, Theorems 2, 3, and 10)). Under Assumption if X E Rp has zero component. and v, B: oo) + Rp are ares that obey the adaptive gradient flow
v'(t) = -=())(()((((()) for almost all 2 0,
where =[v)==((p ((x Ei= (y U, x.)) is with either exponential logistic if L(v(ta)) < E(0) at some time to, lime (t) 1, and if d log /(t)/dt is Lebesgue integrable, then we have that L(v(t)) θ (on))==27)) ||((t]]]= = (((logt))/1) and v(t) converges in direction to a KKT point of the problem
minimize:
||11
subject to: ,xx,, ( 2 for all ie [n].
To apply Theorem to the continuous generalized AdaDolta Process 2, we define for all 2 0:
x o
v(1) (l)//x
3(1) = V
1+/e I+g(1788
oā(v(()) =x xā((((1))
In terms of the skewing vector x and the skewed adapter B(t), eq. (3) that governs the parameters trajectory can then be restated as
w'(t) = -x2 B(t) (c(w(t)) for almost all t 20. Hence v1( = (1)/xx = 3x) xx(())((((()) (()) (Z))(() for almost all t 2 0, as required. From Assumption (iii, we have L(w((t)) < E(0), also as required.
xx²
(5)
=
Therefore, to establish Theorem 2, it remains to prove that lim, B(t) = 1 and that d log B(t) dt is Lebesgue integrable. The remainder of this section consists of a sequence of lemmas, which culminates in Lemma that shows the former fact and Lemma that shows the latter fact. The lemmas in particular make use of Assumption 2.(fi) the initialization of the ares of the exponentially decaying averages g(t) and h(t), and of Assumption (1) on the unboundenness of the integrals of the complements of the exponential decay coefficients, to show that each component of the skewed adapter Btt) monotonically (either from below or from above, depending on g0) and h(0), and on the numerical stability terms and e) tends to as the time t tends to infinity.
Our first lemma shows useful expression for the derivative of 1 minus the squared skewed adapter. 1-p(t) Lemma 5. For almost all t 2 0 we have d (1-B(())) = 1+910/0 (1 - -(133).
Proof. Observe that
di (1 - -1(1)) = W((t)EE (t))) (()1666-())666(0))(0)
by the def. of (())
(1+
p(t)
h(t)/ )l(ur(1)) g
by eqs. (1) and (2)
(1 (t)
+w'(1)g(()/e8 (c(w((t))h(t)/bb
p(()
(00)8-h(t)/s++
(w'(t)/=)
rearranging
(1 + 9())88)2
-(BC(u()))/0)) h(t//E)
1-p(t)
(1 + 9(1)/8)2 (g(t)/8 8 h(t)/E)
by eq. (5)
1 1-p(1)
(1 -(())
calculation
1 + g8
for almost all t 2 0.
The second lemma verifies that the exponentially decaying averages of squared gradients and squared adapted gradients are nonnogative at all times.
*Wang et al. (2021, Theorem 10) contains a typo: the bound e (1ng should be @((ogg 12))

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma 6. For all t have g(t) 2 and h(t) 0.
Proof. Suppose g()) 0 for some i and j E [p]. By Assumption 2.(ii) and since 9,; [0, 00) R is an arc,
there exists to t such that g(tu), 0 and for all (to, t] we have g(T) < 0. Recalling that P3 [0, 00)
[0, 1I, from eq. (1) we obtain that g ( 2 0 for almost all 7 E (lo, 4]. Hence g(!); - g(lo), + S. g (T) dr 2 0,
which is a contradiction.
Supposing h(t), for some t 2 and [p], we obtain a contradiction analogously, using eq. (2).
Consider an arbitrary 5th component of the skewed adapter. By Assumption 2.iii,, its initial value ((0,
is positive. The proof of the third lemuna shows that there are three cases: if ((0), < then ( is
monotonically nondecreasing and bounded above by 1, if 3(0), 1 then B(t) constant, and if ((0)) then B(t) is monotonically nonincreasing and bounded below by 1.
Lemma 7. The following hold for each j [p]]
(i) For almost all 0 we have: if 0 {(t) then ('(t), 2 0, if B(t) then B'(t), 0, and if ((1) > 1 then 3 (t), S 0.
(ii) For all 2 0 we have (()) min (00) 1}.
Proof. Consider an arbitrary j E [p].
For part (i), suppose t 2 0 is such that Lemma 5 applies. If < B(t) then 1 B(t) > 0, from
Lemmas and 6, and by recalling that 0 S p(t) S 1, we have d(1 - B() dtt s 0, i.e. dB(())/ddt 2 0. But d = ( (t),, and so (t), 2 0. In the remaining two cases, namely if ((t), = or B(t); > 1, the reasoning is analogous.
Now part (ii) follows by part (i) and the fact that, since 9j hy: [0, 00) - I are ares, is B
Lemma provides a lower bound for the skewed adapter, but it leaves open its asymptotic behavior. The next lemma fills that gap, establishing that all its components converge 1. This equivalently means that c++((()
the continuous generalized AdaDelta adapter v 6+9(1) converges to the squared skewing vector x² V
Lemma 8. We have that lim ((t) 1.
Proof. We first use Lemma prove that the squared gradients have bounded integrals. To that end, for all t we have
((w(O)) > L(w(()) ((w(())
since L(w(l))
/ (dL(w(())/dr)d
calculus
/ (OC(w)())) w (T)))r
by Proposition 1
[ (o((w(T)) B()) ((r))ttt))
by eq. (5)
/ (V min (100
by Lemma 7.
Σ V min 1} 5L(w(T))3
rearranging,
jE(2)
for each [p] we have
[ 5c(w)(T))3dr < <Vo; /0 L(w(O) =: C min (B()) 1}

---

Published in Transactions on Machine Learning Research (12/2024)
Now suppose j [p]. Equation (1) and Lemma 6 imply that
g(t), = g + ! g'(r), dr S g0(0) + L. (C(w(T))3 dr < g(()) + +C -===
for all t 2 0,
so recalling Lemma 5 and Lemma 7.(), and setting Cj 140 we have
d log 1 - 3(t)3//ddt & -CJ(1 p(t),) for almost all t 2 such that {(t) + 1.
Hence
11 - 3()) 1 1 - exp (-- (1-)(t)))dr) for all t t 200
which by positivity of C and unboundodness of the integrals of the complements of the exponential decay coefficients (cf. Assumption (1) establishes the lemma.
Our final lemma shows that the components of the skewed adapter converge without large fluctuations of their logarithms.
Lemma 9. The function log B(t)/dt is Lebesgue integrable.
Proof. For each [p], from the proof of Lemma 7 we have that doog B(t) B (tt))/B(t) is cither nonnegalive for almost all / 2 0, or nonpositive for almost all / 2 0. Thus by Lemma 8 we have
1 (d
log ((1)/d//dt
log log B()/d()dl
log log ((0) log 3(0) < 80.
4
Experiments
To test our theoretical result for generalized AdaDelta, we evaluated comparatively five algorithms:
SGD:
Stochastic gradient descent as implemented in PyTorch
AdaDelta: Its standard PyTorch implementation', with the exponential decay coefficient o 0.9, and the 10-5.
nunerical stability term
AdaDeltaS: This is AdaDelta amended to have the exponential decay coefficients follow the schedule @ = 1-1//11 + [100k/K]), where K is the total number of steps. Thus 1 - 2 follows a harmonic sequence, increasing the coefficient from &o = 0.9 at the first step to ek-1 = 0.999 at the last step, which lessens aggressiveness of the decay in computing the averages of the squared gradients and the squared adapted gradients along the training.
This is AdaDelta amended to have the numerical stability terms different in the numerator and the denominator of the adaptor, and different across the network parameters. At the start of the training, sampled independently from 10 -0x where X a centered Gaussian with
AdaDeltaN:
each component of 8 and standard deviation for the smaller two networks we consider, and with standard deviation 0.25 for the largest network.
This combines the extensions in AdaDeltaS and AdaDeltaN, ie. has exponential decay coefficients that follow the specified schedule well as numerical stability terms whose components are initialized randomly above.
AdaDeltaNS:
We performed experiments in the following three gradually more complex settings. The total compute for the perceptron setting was around 10min on mid-range CPU; whereas one run of all five algorithms for the smaller convolutional sctting took roughly 2h, and for the larger convolutional sctting took roughly 12h, in both cases on a mid-range GPU.

---

Published in Transactions on Machine Learning Research (12/2024)
Two-layer Leaky ReLU perceptron two-dimensional dataset. Following Wang al. (2021), we first. considered a perceptron with parameters E IR and w E R2, whose prediction for an input a E IR? equals (ww, 2)), where a is the Leaky ReLU nonlinearity with inactive gradient 0.5.
The dataset { (xx1), )) (2(00)))))))) consists of 50 points sampled from (cos 0.5, sin 0.5) + u inde- pendently and labelled 1, and 50 points sampled from -ccos 0.5, sin 0.5) u independently and labelled -1, where u is distributed uniformly on the square [-0.6, 0.6]².
This toy setting is convenient for We trained the network for K = 5000 full-batch epochs using the exponential loss, with learning rate 0.1 for SGD and learning rate for the four variants of AdaDelta. The learning rate for SGD was chosen so that it achieves perfect training accuracy after a similar number of epochs as the four versions of AdaDelta. We repeated the training 100 times, where in each round the five algorithms used the same randomly initialized parameters and numerical stability terms (if applicable). The results are shown in fig. 1.
visualizations of the adapter's reciprocal square roots.
We observe that:
all rounds achieve 100% training accuracy by around 256 epochs, in line with the separation Assump- tion (iii;;;
the final normalized margin, which here equals min ( ek o x ())(((>> + | is within a higher and much narrower range for SGD and with isotropic numerical stability hyperparameters (i.e. for AdaDelta and AdaDeltaS), confirming the prediction of Theorem 2 that, without the isotropy, the implicit regularization may not be towards margin maximization;
the final adapter's reciprocal square root, which in the notations of Procedure 1 equals V 1 has ethx-1
large variance of its direction when the numerical stability hyperparameters have random components (i.e. for AdaDeltaN and AdaDeltaNS), and it is the limit of this direction that according to the proof of Theorem 2 determines the nature of the implicit regularization.
Four-layer convolutional network on MNIST. Also following Wang et al. (2021), we then considered the network from Mędry, Makelov, Schmidt, Tsipras, and Vladu (2018) with biases removed, and in order consisting of: 32-channel 5 x 5-filter convolutional, ReLU, 2-kernel 2-stride max-pooling, 64-channel 3 x 3-filter convolutional, ReLU, 2-kernel 2-stride max-pooling, 1024-width fully connected, ReLU, and 10-width fully connected.
We trained the network on MNIST (LeCun, Bottou, Bengio, and Haffner, 1998) from the default PyTrh random initialization for 500 epochs using the cross-entropy loss: in a finer regime with batch size 100, learning rate 0.01 for SGD, and learning rate 0.1 for the four variants of AdaDelta; and in a coarser regime with batch size 1000, learning rate 0.1 for SGD, and learning rate 1 for the four variants of AdaDelta. The learning rates for SGD were chosen so that it achieves perfect training accuracy after a similar number of epochs as the four versions of AdaDelta. The results are shown in fig. 2.
For both regimes, we observe that:
all algorithms achieve perfect training accuracy by around 250 epochs, line with the separation Assumption (iii;;
the normalized margin, whose values here relatively small partly due to the division by the fourth power of the norm of the network parameters, grows significantly higher for SGD and with isotropic numerical stability hyperparameters (ie for AdaDelta and AdaDeltaS), confirming the prediction of Theorem 2 that, without the isotropy, the implicit regularization may not. be towards margin maximization;
after all algorithms achieve perfoct training accuracy, their test accuracies remain roughly constant, in the finer regime without significant differences among the four versions of AdaDelta, and in the coarser regime with AdaDelta and AdaDeltaS generalizing slightly but consistently better;
10

---

Published in Transactions on Machine Learning Research (12/2024)
the training loss shrinks faster when the numerical stability hyperparameters have random components (i.e. for AdaDeltaN and Ad) however remains within constant multiplicative band of the training loss when those hyperparameters are isotropic;
the results are not substantially affected by whether the exponential decay coefficients follow the increasing schedule, L.e. they are similar for AdaDelta and AdaDeltaS, and also for AdaDeltaN and AdaDeltaNS.
VGG on CIFAR-10.
Following Lyu & Li (2020), we finally considered the 14-layer VGG-16 (Simonyan and Zisserman, 2015) with biases only at the first level, and in order consisting of: 64-channel convolutional then ReLU, repeated 2 times; max-pooling; 128-channel convolutional then ReLU, repeated 2 times; max-pooling; 256-channel convolutional then ReLU, repeated 3 times; max-pooling; 512-channel convolutional then ReLU, repeated 3 times; max-pooling; 256-channel convolutional then ReL.U, repeated 3 times; max-pooling; 10-width fully connected. Each convolutional layer is 3 x 3-filter, and each max-pooling is 2-kernel 2-stride.
We trained the network on CIFAR-10 (Krizhevsky, 2009) from the default PyTorch random initialization for 1000 epochs using the cross-entropy loss: in finer regime with batch size 100, and learning rate 0.1 for all five algorithms; and in a coarser regime with batch size 250, and learning rate 0.25 for all five algorithms. The results are shown in fig. 3.
For both regimes, we observe that:
all algorithms achieve perfect training accuracy by around 250 epochs, line with the separation Assumption 2.(ii))
the normalizod margin, whose values here relatively small partly due to the division by the 14th power of the network norm, grows significantly higher for SGD and with isotropic numerical stability hyperparameters, with the exception in the coarser regime of AdaDelta whose training loss shrinks considerably slower compared with AdaDeltaS - this is in line with Theorem 2, whose prediction of implicit regularization towards margin maximization depends both on the isotropy and on convergence to zero training loss;
after all algorithms achieve perfect training accuracy, their test accuracies remain roughly constant and without substantial differences among them (approximately within 81 + 1% in the finer regime, or 79 + 1% in the coarser regime), with the exception in the coarser regime of AdaDelta and AdaDeltaN whose training losses shrink considerably slower compared with AdaDeltaS and AdaDeltaNS;
whether the exponential decay coefficients follow the increasing schedule does not substantially affect the results in the finer regime, however in the courser regime AdaDeltaS and AdaDeltaNS shrink the training loss considerably faster than AdaDelta and AdaDeltaN, leading to higher normalized margins as well as better gencralization.
5
Conclusion
Our main result, Theorem 2 which holds under Assumptions 1 and 2, indicates that AdaDelta may be used in practical methods that rely on the optimization algorithm implicitly regularizing the network parameters to converge in direction to margin maximization KKT point, which places AdaDelta in the same category e.g. RMSProp and Adam without momentum (Wang et al., 2021, Theorem 7). This relies on the isotropy of the quotient of the numerical stability hyperparameters, without which according to Theorem 2 the implicit regularization of AdaDelta may not be towards margin maximization, as is the case for e.g. AdaGrad (Wang et al., 2021, Thcorem 6).
Relaxing Assumption 1 on the predictor function is challenging even without considering adaptive algorithms, e.g. the definability excludes pathological examples such as based on the "Mexican hat" function (cf. Lyu & Li (2020, Appendix J)).
We focused on binary classification for simplicity of presentation; it is straightforward to extend Theorem 2 for logistic loss to an arbitrary number of classes (cf. Wang et al. (2021, Appendix E)).
An important future goal is obtain a counterpart of Theorem directly for adaptive gradient descent as in Procedure 1. This is also challenge already without adaptivity: the directional convergence result. (Ji
11

---

Published in Transactions on Machine Learning Research (12/2024)
SGD
AdaDelta
AdaDeltaS
AdaDeltaN
AdaDeltaNS
Normalized Margin
0.1
Average Accuracy
0.8
0.05
0.6
20
22
21
26
28
20
22
20
40
60
80
100
Epoch
Round
1
0.5
0.5
1
0
0
0.5
0.5
0.5
0.5
1
0
0
Adapter Reciprocal Square Root
Adapter Reciprocal Square Root
1
1
0.5
0.5
1
0
0
0.5
0.5
0.5
0.3
1
0
1
Adapter Reciprocal Square Root
Adapter Reciprocal Square Root
We trained two-layer Leaky ReLU perceptron a synthetic binary classification dataset which consists of 100 points in two-dimensional space. Each of 100 rounds the experiment consisted of randomly initializing the network parameters and the numerical stability terms (if applicable), and then rumning separately each of the five algorithms for 5000 epochs. The plots the top row show: on the left, the training accuracy averaged over the rounds, depending on the epoch; and on the right, the normalized margin at the end of the training, across each of the rounds. The plots in the next two visualize the direction of the adapler's 's reciprocal square root at the end of the training, where the isotropic direction is indicated by the longer dashed orange arrow.
Figure 1:
12

---

Published in Transactions on Machine Learning Research (12/2024)
SGD
AdaDelta
AdaDeltaS
AdaDeltaN
AdaDeltaNS
2a
22
Training Loss
2-6
2-5
2-12
2 2-12
2-19
2-19
20
21
2
23
24
25
26
27
2
2
2
2
23
24
25
26
2
2
Training Accuracy
0.99
0.99
0.98
0.98
0.97
0.97
20
21
22
23
24
25
26
27
2
20
2
22
23
24
25
26
27
2
0.994
0.994
Test Accuracy
0.992
0.992
0.99
0.99
100
200
300
400
500
100
200
300
400
500
-10-5
-10
2
Normalized Margin
1
0
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Figure 2: The results of training 4-layer convolutional network on MNIST, with batch sizes and learning rates for the right-hand column that are 10 times larger than for the left-hand column. The solid lines show the median values, and the shaded areas are between the 25th and 75th percentiles, over 19 runs.
13

---

Published in Transactions on Machine Learning Research (12/2024)
SGD
AdaDelta
S
AdaDeltaN
AdaDeltaNS
2a
2
Training Loss
2-7
2-7
2 2-16
2
2 2-26
2-25
26
27
2
29
26
27
2
29
1
Training Accuracy
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
26
27
2
29
26
27
28
29
0.82
0.8
Test Accuracy
0.81
0.7
0.8
0.6
200
400
600
800
1,000
200
400
600
800
1,000
-10-2 25
-10-5
Normalized Margin
3
2
0
200
400
600
800
1,000
200
400
600
800
1,000
Epoch
Epoch
Figure 3: The results of training a 14-layer convolutional network CIFAR-10, with batch sizes and learning rates for the right-hand column that 2.5 times larger than for the left-hand column. The solid lines show the median values, and the shaded areas are between the 25th and 75th percentiles, over 19 runs.
14

---

Published in Transactions on Machine Learning Research (12/2024)
& Telgarsky, 2020, Theorem 3.1) is only for gradient flow, and the characterization of directional limits for gradient descent (Tyu & Li, 2020, Theorem E.3) assumes C"-smoothness of the predictor function which excludes nonlinearities such as ReLU and Leaky ReLU.
Broader Impact Statement
This is foundational research general-purpose algorithm for optimizing neural networks. Greater understanding of its implicit regularization properties may lead to machine learning models that have cheaper training, greater efficiency, and increased performance.
Acknowledgments
We acknowledge the Centre for Discrete Mathematics and Its Applications at the University of Warwick for partial support.
References
Anas Barakat and Pascal Bianchi. Convergence and Dynamical Behavior of the ADAM Algorithm for Nonconvex Stochastic Optimization. SIAM J. Oplim., 31(1):244225 2244, 2021. 3
Anas Barakat, Pascal Bianchi, Walid Hachem, and Sholom Schechtman. Stochastic optimization with momentum: Convergence, fluctuations, and traps avoidance. Flectron. J. Statist., 15(2):3892 3947, 2021.
3
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normmalieed margin bounds for neural networks. In NewrIPS, pp. 6240-6249, 2017.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- machine-learning practice and the classical variana trade-off. Proc. Natl. Acad. Sci., 116(32):15844-15554 2019.
Jonathan Borwein and Adrian Lewis. Conver Analysis and Nonlinear Optimization: Theory and Examples. Springer, 2nd edition, 2010. 3
Gon Buzaglo, Niv Haim, Gilad Yehudai, Gal Vardi, Yakir Oz, Yaniv Nikankin, and Michal Irani. De- constructing Data Reconstruction: Multiclass, Weight Decay and General Losses. In NewrIPS, 2023.
Matias D. Cattaneo, Jason M. Klusowski, and Boris Shigida. On the Implicit Bias of Adam. In ICML, 2024.
2
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang. Yuan Cao, and Quanquan Gu. Closing the Generalization Gap Adaptive Gradient Methods in Training Deep Neural Networks. IJCAL, pp. 3267 3275, 2020. 2
Frank H. Clarke. Generalized gradients and applications. Trans. Amer. Math. Soc., 205:247-200 1975. 3
André Belotto da Silva and Maxime Gazeau. A General System of Differential Equations Model First-Order
Adaptive Algorithms. J. Mach. Learn. Res., 21:129:1-129:42, 2020. 3
Damek Davis, Dmitriy Drusvyatskiy, Sham M. Kakade, and Jason D. Lee. Stochastic Subgradient Method Converges on Tame Functions. Found. Comput. Math., 20(1):119-1544 2020.
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. J. Mach. Learn. Res., 12:2121-2159, 2011. 2
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate KKT points and a proximity measure for termination. J. Glob. Optim., 56(4):1463 1499,, 2013. 6
Omer Elkabetz and Nadav Cohen. Continuous vs. Discrete Optimization of Deep Neural Networks. In NewrIPS, pp. 4947-4960, 2021.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Sébastien Gadat and Ioana Gavra. Asymptotic Study of Stochastic Adaptive Algorithms in Non-convex Landscape. J. Mach. Learn. Res., 1-2228:1-28::58 2022. 3
Margalit Glasgow, Colin Wei, Mary Wootters, and Tengyu Ma. Max Margin Works while Large Margin Fails: Generalization without Uniform Convergence. In ICLR, 2023.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- SizeIIndeeendent Sample Complexity of Neural Networks. In COLT, pp. 297-299, 2018. Extended version in CoRR abs/ abs/1712.06541. 3
Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing Implicit Bias in Terms of Optimization Geometry. In ICML, pp. 1827-1836, 2018.
Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing Training Data From Trained Neural Networks. In NewrIPS, 2022.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Overview of mini-batch gradient descent, 2012. Neural Networks for Machine Learning: Lecture 6a. 2
Ziwei Ji and Matus Telgarsky, Directional convergence and alignment in deep learning. In NewrIPS, 2020. 1, 2, 3, 6, 11
Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the Generalization Gap in Deep Networks with Margin Distributions. In TCLR, 2019.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic Generalization Measures and Where to Find Them. In ICLR, 2020. 3
Nitish Shirish Keskar and Richard Socher. Improving Generalization Performance by Switching from Adam SGD. CoRR, (bss/171.0072/ 2017. 2
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In JCLR, 2015. 1
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Master's thesis, University of Toronto, 2009. 11
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recoguition. Proc. IEEE, 86(11):2278 2324, 1998. 10
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive Gradient Methods with Dynamic Bound of Learning Rate. In ICLR, 2019. 2
Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin of Homogencous Neural Networks. In ICLR, 2020. 1, 2, 6, 11, 15
Aleksander Mądry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In ICLR, 2018. 10
Behnam Neyshabur, Srinadh Bhojanapalli, David McA Alester, and Nati Srebro. Exploring Generalization in Deep Learning. In NewrIPS, pp. 5947-5956 2017. 1
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian Approach to Spectrally- Normalized Margin Bounds for Neural Networks. In ICLR, 2018. 3
Alethca. Power, Yuri Burda, Harrison Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gencralization Beyond Overfitting Small Algorithmic Datasets. CoRR, ab2/2201.021177 2022.
Qian Qian and Xiaoyuan Qian. The Implicit Bias of AdaGrad on Separable Data. In NeurIPS, pp. 7759 7767, 2019.
Sebastian Ruder. An overview of gradient descent optimization algorithms. CoRR, abs/1000000 04649.4744777 2016. 2
16

---

Published in Transactions on Machine Learning Research (12/2024)
Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. In ICL.R 2015. 11
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The Implicit Bias of Gradient Descent Separable Data. J. Mach. Learn. Res,, 19(70):1-56 57, 2018.
Davoud Atace Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-Margin Token Selection in Attention Mechanism. In NewrIPS, 2023.
Vimal Thilak, Etai Littwin, Shuangfei Zhai, Omid Saremi, Roni Paiss, and Joshua M. Susskind. The Slingshot Effect: A Late-Stage Optimization Anomaly in Adaptive Gradient Methods. Trans. Mach. Learn. Res., 2024. 2
Gal Vardi. On the Implicit Bias in Deep-Learning Algorithms. Commun. ACM, 66(6):86 2023.
Bohan Wang, Qi Meng, Wei Chen, and Tie-Yan Liu. The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks. In ICML, pp. 10849 10858, 2021. 2, 7, 10, 11
Bohan Wang, Qi Meng, Huishuai Zhang, Ruoyu Sun, Wei Chen, Zhi-Ming Ma, and Tic-Yar Liu. Does Momentum Change the Implicit Regularization on Separable Data? In NewrIPS, 2022. 2
Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap between the upper bound and lower bound of Adam's 's iteration complexity. In NewrIPS, 2023. 2
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, Tie-Yan Liu, Zhi-Quan Luo, and Wei Chen. Provable Adaptivity of Adam under Non-uniform Smoothness. In KDD, pp. 2960 2969, 2024. 2
Colin Wei and Tengyu Ma. Improved Sample Complexitics for Deep Noural Networks and Robust Classification via an All-Layer Margin. In ICLR, 2020.
Colin Wei, Jason D. Lee, Qiang Liu, and Tengyu Ma. Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel. In NewrIPS, pp. 9709-9721, 2019. 3
Alex Wilkie. Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. J. Am. Math. Soc., 9(4):1051- 1996. 3
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The Marginal Value of Adaptive Gradient Methods in Machine Learning. In NewrIPS, pp. 4148-448 44484415,, 2017.
Nachuan Xiao, Xiaoyin Hu, Xin Liu, and Kim-Chuar Toh. Adam Adam-family Methods for Nonsmooth Optimization with Convergence Guarantecs. J. Mach. Learn. Res., 25:48:1-48:53, 2024. 3
Shuo Xie and Zhiyuan Li. Implicit Bias of AdamW: toc Norm Constrained Optimization. In ICML, pp- 54488 54510, 2024. 2
Manzil Zahcer, Sashank Reddi, Devendra Singh Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive Methods for Nonconvex Optimization. In NewrIPS, pp. 9815 9825, 2018. 2
Matthew D. Zeiler. ADADELTA: An Adaptive Learning Rate Method. CoRR, Abs/1212.5701, 2012. 2, 4
Chenyang Zhang, Difan Zou, and Yuan Cao. The Implicit Bias of Adam Separable Data. CoRR, his/2400.106500 2024. Accepted to NeurIPS 2024. 2
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107-115 2021. 1,
Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu-Hong Hoi, and Weinan E. Towards Theoretically Understanding Why Sgd Generalizes Better Than Adam in Deep Learning. In NewrIPS, 2020.
17


Reviews:
[{"review_id": "oNxtwhcAdT", "reviewer": "Reviewer_uzSm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. This is probably the first time implicit regularization analysis is carried out when both numerator and denominator of $\\Delta x$ in an adaptive gradient algorithm have exponentially moving averages. \n2. The amount of implicit regularization has been characterized directly in terms of the algorithm parameters. The key theoretical tool that the authors used is Lemma 3, which does the heavy lifting in presence of exponentially moving average of both numerator and denominator of $\\Delta x$. \n3. The proofs in Section 3 are technically correct and well-presented.  \n4. The numerical results supports the main theoretical result.\n\nWeakness/Limitation:\n1. In $\\Delta x$ of AdaDelta, the current gradient $\\partial L (w_t)$ and the adaptive term $\\beta(t)$ are separable. In Adam, the numerator of $\\Delta x$ has exponentially moving sum of gradients, and hence, no separable gradient term $\\partial L (w_t)$.  Thus, extending the presented analysis technique to such adaptive algorithms might be challenging.\n2. Why is the numerical stability ($\\epsilon$) required in the numerator? While the generalization in terms of $\\eta$ and $\\delta$ are meaningful, the purpose of  introducing $\\epsilon$ is not clear.\n3. Does not the statements of Lemma 4 and 5 follow directly from Lemma 3? Let us denote $y(t) = 1 - \\beta(t)^2$. Then, Lemma 3 states that $\\frac{dy(t)}{y(t)} = - dt * z(t)$, where $z(t)$ is a positive valued function of t. From this and by integration, we can easily get Lemma 4 and 5?\n4. Figure 2: The qualitative behavior between AdaDeltaN and AdaDeltaNS are not consistent across training and testing. Also, test accuracy of AdaDeltaNS is the best, but normalized margin AdaDelta/AdaDeltaS is best. Is not normalized margin a characterization of generalization ability?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the implicit regularization of the AdaDelta optimizer for training a class of neural networks for solving classification problems. The concept of implicit regularization is one of the tools that helps in explaining the generalization behavior of gradient-based optimizers. The contribution lies in a generalization (in terms of non-uniform numerical stability parameters and learning rate scheduling) of the existing AdaDelta algorithm: whereas implicit regularization has been theoretically studied before for few other adaptive gradient optimizers (AdaGrad, RMSProp, Adam without momentum), this is probably the first time such analysis is carried out when both numerator and denominator of $\\Delta x$ have exponentially moving averages. The theoretical guarantees are numerically verified with a set of experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Not Critical for Acceptance Recommdenation:\n1. Explain the reason for introducing $\\epsilon$ for better numerical stability. Possibly with instances where with $\\epsilon=0$, AdaDelta can go unstable. This is not critical for acceptance, as the analysis still has value without $\\epsilon$.\n2. Is the result in Theorem 2 valid for both exponential loss and logistic loss. Nowhere in the theorem statement and in the proof, the loss function class is mentioned. Please mention it explicitly in or right before the theorem statement.\n\nCritical:\n1. Please check if the proofs of Lemma 4 and 5 can be simplified from my earlier comment. This is critical, as the paper is mostly theoretical.\n2. Why does AdaDeltaNS have better test accuracy in Figure 2, despite not having the best margin maximzation?\n3. The effect of numerical stablitity on AdaDelta and AdaDeltaN are also not consistent: AdaDeltaN is worse than AdaDelta, while AdaDeltaNS is better than AdaDeltaS.", "broader_impact_concerns": "The broader impact that is evident - first time implicit regularization analysis when both numerator and denominator in an adaptive gradient algorithm have exponentially moving averages. \n\nBut I do not agree with the statement that this is a foundational research on a `general algorithm' for optimizing neural networks. While the research is foundational, it is limited in its current form only to a generalization (in terms of numerical stability and learning-rate schedule) of AdaDelta algorithm. It is not clear how the results extend to other algorithms for training neural networks, such as Adam and its variants. It is also not clear how the results will help in cheaper training and better efficiency, since the experimental results lack comparison with other optimizers on benchmark models.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EdvijQe55Y", "reviewer": "Reviewer_ECdm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The general topic of generalization is important in deep learning. This work builds on (and contributes to) a well-established line of research investigating the relationships between optimization and generalization, specifically for the popular class of adaptive methods which is very successful in practice.  \n- The exposition and writing are clear overall. The introduction for the topic of implicit regularization, the goal and the contributions of the paper are quite clear. \n- I checked the proofs and they are correct to the best of my knowledge, up to some specific concerns/questions described in details below.  \n\n**Weaknesses:** The following comments include a discussion about weaknesses as well as comments and questions for clarifications. \n \n- The main result regarding implicit regularization is only shown for the continuous-time AdaDelta and no result is established for the (discrete-time) algorithm of interest: \n\n— I understand that prior work seems to be mostly restricted to continuous time as briefly mentioned in the conclusion. Nevertheless, AdaDelta corresponds to $\\eta = 1$ which makes it a particular case of Procedure 1. However, if you take $\\eta \\to 0$ to obtain the continuous-time system, why would the obtained flow be a relevant description of AdaDelta? \n\n— Is there any reason why the authors do not derive a result similar to Theorem 8 in Wang et al. 2021 to have at least a result for the actual algorithm (in discrete time) even if it is at the price of stronger smoothness assumptions? Since the main result of the present work builds on results of Wang et al. 2021, I am wondering why not also including such a result in discrete time. Is there any major technical issue? If you assume $C^2$ smoothness of the predictor function, can you still state a result characterizing the directional limits for your adaptive AdaDelta flow? (similarly to e.g. Theorem E.3 of Lyu and Li ’20 that you mention in the conclusion).  \n\n\n- Theorem 2: \n\n— Could you comment more on the relevance of this implicit regularization result compared to vanilla gradient flow? What does the result suggest in practice: Should we always use $\\delta = \\epsilon$ to asymptotically match gradient flow? Are there any specific differences with vanilla gradient flow that provide some kind of advantage to AdaDelta (or adaptive gradient flow more generally)? Any theoretical or actionable practical implementation insight regarding hyperparameters? It seems that only numerical stability hyperparameters might play a role asymptotically and affect implicit regularization. \n\n— As a follow-up to the previous comment, one would expect some difference with respect to gradient flow depending on the specific choice of the exponential decay coefficient rate for instance that should effect the provided rates. Indeed, the rate of convergence of $\\beta(t)$ to 1 seems to be driven by two ingredients: a) how fast $\\rho(t)$ goes to 1 as captured by the integrability condition Assumption 2 (i) and b) how fast $\\tilde{\\partial} \\mathcal{L}(\\omega(t))$ goes to zero as captured by the constant $C_j$ appearing in the square integrability condition that you show in Lemma 5, i.e. convergence to `stationarity’. \nThe current analysis does not exhibit such a difference as it shows overall that both adaptive and vanilla gradient flows have the same implicit regularization properties including for rates. It would be interesting to further comment (if possible) on how these convergence rates might be beneficial for the convergence of the weights compared to standard gradient flow, i.e.  if a different analysis taking this into account could be possible. \n\n— The norm of the the weights diverges to infinity at a log rate for $t \\to \\infty$, what’s the meaning of this blow-up result? Can you provide any intuition for clarification (perhaps based on prior work also showing the same result)? \n\n-- Any additional comment about the comparison to other adaptive algorithms previously studied in the literature (e.g. RMSProp) in theory and in practice? \n\n- About assumption 1: \n\n— I guess the exponential function is excluded due to positive homogeneity, activation functions such as the sigmoid are also excluded as a consequence. Does it mean that only (almost) `linear’ networks (composition of linear layers with potentially Relu, … zeroing out inputs in some ranges) are allowed? As the O-minimal class of functions considered is  chosen to contain the exponential function (as if it was indeed an advantage), this is rather confusing. \n\n— Comment about $L$ for positive homogeneity: I guess it is related here to the number of layers. A remark would be useful to clarify. \n\n- The so-called separability assumption (Assumption 2 (iii)) is formulated a bit differently in Wang et al. 2021 (see their assumption 1. III). Do both formulations coincide exactly? Can you comment on your formulation here? \n\n- last sentence of the conclusion: `the benefits of anisotropic numerical stability terms and of exponential decay coefficients that we observed in some experiments’. Can you be more specific here? Numerical stability hyperparameters are usually introduced to avoid blowing up or vanishing numerical issues. It seems odd to use them for a different purpose and I am not expecting this to provide any uniform advantage over SGD for all problems. The analysis provided shows that using $\\delta \\neq \\epsilon$ only leads asymptotically to a rescaling of the (vanilla) gradient flow by the constant square root of $\\delta$ over $\\epsilon$ (given that $\\beta$ goes to 1). This can be simply seen as a rescaling of the objective (loss) function by a constant. \n\n- While the discussion is relatively clear regarding the very specific topic of implicit regularization, the related work discussion is quite minimal regarding continuous-time analysis of adaptive gradient methods. While the main focus of this work is rather on implicit regularization, the analysis of the continuous-time system is the crucial technical contribution of this work enabling to establish implicit regularization. There are a number of works on the topic in the literature that might even include AdaDelta as a particular case (Barakat and Bianchi (SIOPT 2021) for Adam, Da Silva and Gazeau (JMLR 2021) for a class of adaptive methods in continuous time, Barakat et al. (EJS 2022) for a class of adaptive methods in both continuous and discrete time, Gadat and Gavra (JMLR 2022) for RMSProp and AdaGrad in both continuous and discrete time, more recently Xiao et al. (JMLR 2024) for adaptive methods for nonsmooth optimization). Notice for instance that several similar technical steps (e.g. Lemma 4, 5 and their proofs, exponential decaying coefficient integrability conditions such as Assumption 2 (i) …) were also shown and used in this related literature for a larger class of adaptive methods including also momentum algorithms (although for different final purposes). Note also that some of these works also deal with time varying exponential decay coefficients and use similar assumptions. It might even be that a general unified analysis including momentum (which seems to be missing in the literature) might be conducted based on these works and ideas from the present work and prior work (Wang et al. 2021) to show implicit regularization for a large class of adaptive gradient methods in a unified manner.   \n\nA. B. Da Silva, M. Gazeau. A general system of differential equations to model first-order adaptive algorithms, JMLR 2020. \n\nA. Barakat, P. Bianchi. Convergence and dynamical behavior of the Adam algorithm for non-convex stochastic optimization, SIOPT 2021. \n\nA. Barakat, P. Bianchi, W. Hachem, Sh. Schechtman. Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance, EJS 2021. \n\nS. Gadat, I. Gavra. Asymptotic study of stochastic adaptive algorithms in non-convex landscape, JMLR 2022.\n\nN. Xiao, X. Hu, X. Liu, K-C. Toh. Adam-family methods for nonsmooth optimization with convergence guarantees, JMLR 2024. \n- Technical analysis:\n\n— Please justify the first inequality in the proof of Lemma 5 precisely. It seems that you should require or show that at least $\\mathcal{L}(\\omega(t))$ should admit a limit when $t \\to \\infty$ for the integral from 0 to infinity of the derivative to exist. This would mean that the training loss needs to stabilize asymptotically, is this an assumption or do you rather prove it somewhere? It seems that this limit is proven to be equal to zero for RMSProp in Wang et al. 2021 in the second step of their proof strategy (see discussion sec. 5 p. 6 and Lemma 4 p. 8). Maybe using a similar argument to Lemma 12 in Wang et al. ’21 should fix this. Please clarify. \n\n— In the proof of Lemma 4, the non negativity of $g$ can be shown more clearly. While the main arguments are there, the proof deserves a clearer presentation: e.g. suppose there exists $t_0 > 0$ s.t. $g(t_0) < 0$ then there should exist $t_1 <  t_0$ s.t. $g(t_1) = 0$ (supposing $g$ is positive at $0$) by continuity of $g$ but then $g’(t_1)$ is nonnegative by (1) and this would contradict the sign of $g(t_0) < 0$. Please clarify your reasoning. In particular, is $g$ necessarily continuous in your nonsmooth setting, given that there might be some jumps in the (Clarke) sub gradients of the loss function? \n\n— Proof of Lemma 5, p. 7: Please add more details about how you derive the inequality. Writing $g(t) = g(0) + \\int_0^t g’(s) ds$ and injecting $g’(s)$ in eq. (1) does not immediately lead to the result. It seems that you are also using the nonnegativity of $g$ here (as seems to be proved in the proof of Lemma 4, see previous item discussion) and the non negativity of $\\rho$.  \n\n- Experiments: \n\n— Why considering two different standard deviations depending on the size of the networks in the end of p. 7?\n\n— Is the learning rate tuned for SGD? How? \n\n— p. 9: `the test accuracy is consistently high for AdaDelta and AdaDeltaS, corroborating the link between the normalized margin and generalization’. Does this mean that AdaDelta does generalize better than SGD given Fig. 2 (c) (at least in this example)? This seems to be contradicting some of the empirical results reported in the introduction regarding generalization of adaptive methods (Wilson et al. 2017). \n\n— Fig. 1 p. 10: It seems that the S variants of the algorithm do not make any difference. I guess this is related to the way the exponential decay coefficients are set. Are the results sensitive to this choice. In particular, what do we observe for faster or slower increasing exponential decay coefficients towards 1? \n\n— What do all the different vectors represent in Fig. (f), (g)? Are these final adapter’s reciprocal square roots across different rounds with different random numerical stability hyperparameters? \n\n— Fig. 2 (c)-(d): Large margin does not seem to always translate to better generalization. Any comment? \n\n— The normalized margins in Fig. 2. (d) (same in Fig. 3 (d)) do not seem to converge to the same value for SGD, AdaDelta and AdaDeltaS unlike what is predicted by the theory. Is this expected, consistent? Any explanation? \n\n\nMore minor:\n- p. 1: `if the adapter of an algorithm without momentum …’: on a first reading (without going through the whole paper), it is not very clear what is meant by an adapter here. Although you provide a reference, a clearer formulation (exempting the reader from checking the reference) would be appreciated. \n- p. 2: `RMSProp and Adam without momentum’: to the best of my knowledge Adam without momentum and RMSProp as defined in their respective original papers/lectures are the same, are you maybe referring to some other variants of them? Please clarify. \n- Typos: a few occurrences of AdaDeta instead of AdaDelta. \n- p. 6: please avoid overloading the numerator in the second equation, I understand that this is more compact but this can be confusing at first reading, maybe put in factor the denominator instead to gain some space. \n- It seems that you are also showing in the proof of Lemma 4 that $\\beta$ is actually monotone, that is a result that might be highlighted in the lemma. \n- p. 7: `the skewed adapter converge without large fluctuations’: fluctuations of $\\log \\beta(t)$ here I guess, it might be that $\\beta(t)$ actually fluctuates quite a lot when translating back from the log scale.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focuses on a specific adaptive gradient method called AdaDelta. The paper shows that the continuous-time version of AdaDelta (in the limit of small step sizes) is an adaptive gradient flow in the sense of the work of Wang et al. 2021, i.e. a preconditioned gradient flow with a preconditioner whose coordinates converge to 1 with a Lebesgue integrable derivative of its logarithm. Using this result, they apply a theorem established in Wang et al. 2021 to deduce their main result: In continuous time, AdaDelta enjoys the same implicit regularization as the vanilla gradient flow which was shown in prior work. More precisely, for positively homogeneous  locally Lipschitz and definable neural networks with suitable regularity and technical assumptions, they show that the weights of the neural network updated with AdaDelta converge in direction to a KKT point of a maximum margin problem where the objective (squared weight norm) is slightly distorted by the numerical stability hyper parameters of AdaDelta. In particular, this work considers exponential decay functions varying with time at a controlled speed by an integrability assumption. Numerical experiments on the popular MNIST and CIFAR-10 datasets with convolutional networks support and illustrate part of the main theoretical result.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above section for questions and comments which I believe deserve to be addressed. The main points that are essential are the technical aspects as well as some of the questions regarding experiments and the alignment of the results with the main theoretical findings. The rest of the comments are also important for strengthening the paper and efforts from the authors to address them to the best of their ability will be appreciated, especially concerning the benefit of AdaDelta over vanilla gradient flow and possible results in discrete time. \n\nSome additional comments and suggestions for improvement below: \n\n- To better highlight the motivation, I suggest to further recall and insist on the existing correlation results between max-margin maximization and generalization error. \n\n- As the work mainly relies on prior work for deriving the main result (Theorem 2), giving slightly more expanded discussion about their result (including some intuitions and key arguments to establish it) would be appreciated to make the paper more self-contained.   \n\n- Right after Theorem 2, you start deriving some Lemmas for analyzing $\\beta(t)$. It would be better to guide the reader from the beginning about your proof strategy. I had to check the reference in more details to understand why you are proving the lemmas. I would rather start by stating the general proof strategy (rather than finishing the proof with it), saying that you rewrite the flow as an adaptive gradient flow in the sense of Wang et al. 21 and that you would like to prove that $\\beta(t)$ goes to 1 and that the derivative of the adapter’s log function is Lebesgue integrable, you can even state their result for completeness.", "broader_impact_concerns": "Does not apply.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "op4Qlf4N3g", "reviewer": "Reviewer_wbBq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proof is rigorous and provides a solid theoretical grounding for implicit regularization with AdaDelta, which was never explored before\n- Results are solid and well corroborated by experiments\n- Theoretical and empirical analyses are extensive and provide interesting insights not only on AdaDelta, but also on what can happen when some conditions are not present, e.g. when quotient of the numerical stability parameters is not isotropic\n\nWeaknesses:\n- Clarity: structure of the proof is confusing, the paper does not always outline very well the link between different lemmas - the reasoning behind the different parts of the proof is not always easy to follow\n- Conclusion of the proof is unclear: the paper does not explain well how what was just shown connects with Theorems 2, 3 and 10 of the Wang et al. paper\n- Empirical results could be discussed in more details: the discussions per dataset are fairly short, and having 3 pages of graphs with practically no comment is hard to follow", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes the implicit regularization phenomenon, i.e. the tendency of some optimization algorithm to converge towards solutions with good generalization properties, for the AdaDelta algorithm and some of its variants. The broader setting is fitting a variety of neural networks for a classification problem, with either exponential or logistic loss. \nIt builds on several previous results for different algorithms (and namely The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks, Wang et al., 2021) to provide a rigorous theoretical analysis and proof of the conditions where the AdaDelta method converges towards a KKT point of a specific margin maximization problem. It then illustrates the implicit regularization properties of the different variants of AdaDelta on various network types and datasets, ranging from generated data to CIFAR-10.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section above. In short:\n- Add more structure to the proof, e.g. with a proof sketch section where the link between each step of the proof is clearly explained\n- Add more details in the conclusion, restate the Wang et al. results and show how they connect to what was just shown\n- Discuss experiments in more details and give more insights\n- Add an an appendix with code and illustration for reproducibility", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The papers claims now clearly match their content, there is an audience who would be interested, and revised version of the paper is already satisfactory.
Decision: Accept (poster)