Training Neural Networks for and by Interpolation
Authors: Leonard Berrada
Andrew Zisserman
Pawan M. Kumar
Venue:  (2020)
Keywords: optimization
adaptive learning-rate
Polyak step-size
Newton-Raphson

Abstract: In modern supervised learning, many deep neural networks are able to interpolate the data: the empirical loss can be driven to near zero on all samples simultaneously. In this work, we explicitly exploit this interpolation property for the design of a new optimization algorithm for deep learning. Specifically, we use it to compute an adaptive learning-rate in closed form at each iteration. This results in the Adaptive Learning-rates for Interpolation with Gradients (ALI-G) algorithm. ALI-G retains the main advantage of SGD which is a low computational cost per iteration. But unlike SGD, the learning-rate of ALI-G uses a single constant hyper-parameter and does not require a decay schedule, which makes it considerably easier to tune. We provide convergence guarantees of ALI-G in the stochastic convex setting. Notably, all our convergence results tackle the realistic case where the interpolation property is satisfied up to some tolerance. We provide experiments on a variety of architectures and tasks: (i) learning a differentiable neural computer; (ii) training a wide residual network on the SVHN data set; (iii) training a Bi-LSTM on the SNLI data set; and (iv) training wide residual networks and densely connected networks on the CIFAR data sets. ALI-G produces state-of-the-art results among adaptive methods, and even yields comparable performance with SGD, which requires manually tuned learning-rate schedules. Furthermore, ALI-G is simple to implement in any standard deep learning framework and can be used as a drop-in replacement in existing code.

Under review as a conference paper at ICLR 2020
TRAINING NEURAL NETWORKS FOR AND BY INTERPOLATION
Anonymous authors Paper under double-blind review
ABSTRACT
In modern supervised learning, many deep neural networks are able to interpolate the data: the empirical loss be driven to near zero on all samples simultaneously. In this work, we explicitly exploit this interpolation property for the design of a new optimization algorithm for deep learning. Specifically, we use to compute an adaptive learning-rate in closed form at each iteration. This results in the Adaptive Learning-rater for Interpolation with Gradients (ALI-G) algorithm. ALI-G retains the main advantage of SGD which is low computational cost per iteration. But unlike SGD, the learning-rate of ALI-G uses a single constant hyper-parameter and does not require decay schedule, which makes it considerably easier to tune. We provide convergence guarantees of ALI-G in the stochastic convex setting. Notably, all our convergence results tackle the realistic case where the interpolation property is satisfied up to some tolerance. We provide experiments on a variety of architectures and tasks: (i) learning differentiable neural computer; (ii) training a wide residual network on the SVHN data set; (iii) training a Bi-LSTM on the SNLI data set; and (iv) training wide residual networks and densely connected networks on the CIFAR data sets, ALI-G produces adaptive methods, and even yields comparable performance with SGD, which requires manually tuned learning-rate schedules. Furthermore, ALI-G is simple to implement in any standard deep learning framework and can used as a drop-in replacement in existing code.
results among
INTRODUCTION
Training a deep neural network is a challenging optimization problem: it involves minimizing the average of many nigh-dimensional non-convex functions. In practice, the main algorithms of choice are Stochastic Gradient Descent (SGD) (Robbins & Monro 1951) and adaptive gradient methods such AdaGrad (Duchi et al. 2011) Adam (Kingma & Ba (015). In recent work, the ability to interpolate - i.e. to achieve near zero loss on all training samples simultancously - has been used to show convergence of SGD (Ma et al. 2018 Vaswani al. 2019a| Zhou et al. 2019). This property is usually satisfied in supervised deep learning because of the empirical success of over- paraametttee architectures. However, while the convergence analyses provide a better theoretical understanding of SGD, they do not help improve its practical behavior.
In this work, we open a different line of enquiry, namely: can the interpolation property be used to design a robust and efficient optimization algorithm for deep learning? In order to answer this question, we begin by giving the following two desiderata of an optimization algorithm for deep learning: (i) an inexpensive computational cost per iteration (typically call to a stochastic first-order oracle); and (ii) adaptive learning-rand rates that do not require a manually designed schedule.
We present ALI-G (Adaptive Learning-rates for Interpolation with Gradients), an algorithm that takes advantage of interpolation by design and satisfies both properties mentioned above. Key to the ALI-G algorithm are the following two ideas. First, an adaptive learning-rate can be computed for the non-stochastic gradient direction when the minimum value of the objective function is known (Polyak] 1969 Shor 1985 Brännlund] 1995| Nedić & Bertsekas) 2001 b). And second, one such minimum value is usually approximately known for interpolating models: for instance, it is close
to zero for a model trained with the cross-entropy loss. By carefully combining these two ideas,

---

Under review as a conference paper at ICLR 2020
create stochastic algorithm that provably converges fast in the convex setting and that obtains state-of-the-an results with neural networks.
Procedurally, ALI-G is close to many existing algorithms, such as Deep Frank-Wolff (Berrada et al. 2019), APROX (Asi Duchi 2019) and La (Rolinck & Martius 2013). And yet uniquely, thanks to its careful design and analysis, ALI- enables accurate optimization of a wide class of deep neural networks using only a single pyper--prammter that does not need to be decayed. This makes ALI-G well-suited to the deep learning setting, where hyper-parameter tuning is widely regarded as an onerous and time consuming task. Since ALI-G is easy to implement in any deep learning framework, we believe that can prove be practical and reliable optimization tool for deep learning.
Contributions. We summarize the contributions of this work as follows:
We design an optimization algorithm that uses single hyper-parameter for its learning-rate and does need any decaying schedule. In contrast, the closely related APROX (Asi & Duchi 2019) and La (Rolinek & Martius 2018) use respectively two and four parrmepprameters for their learning-rate.
We provide convergence rates of ALI-G in various stochastic convex settings. Importantly, our theoretical results take into account the error in the estimate of the minimum objective value. To the best of our knowledge, our work is the first to establish convergence rates for interpolation with approximate estimates.
We demonstrate state-of ofte-of-the-are art results for ALI-G on learning differentiable neural computer; training variants of residual networks on the SVHN and CIFAR data sets; and training a Bi-LSTM on the Stanford Natural Language Inference data set.
2
THE ALGORITHM
2.1 PROBLEM SETTING
Loss Function. We consider supervised learning task where the model is parameterized by w E IRP Usually, the objective function can be expressed as an expectation over 2 E 2, a random variable indexing the samples of the training set:
f(w) A [e)))(s(w)]],
where each &g is the loss function associated with the sample z. We assume that each lg is non- negative, which is the case for the large majority of loss functions used in machine learning. For instance, suppose that the model is a deep neural network with weights w performing classification. Then for each sample (=(w) can represent the cross-entropy loss, which is always non-negative. Other non-negative loss functions include the structured or multi-class hinge loss, and the Li or L2 loss functions for regression.
Regularization. It is often desirable to employ a regularization function in order to promote generalization. In this work, we incorporate such regularization as constraint on the feasible domain: (w E TRP: <(w) S r for some value of to assume that the objective function can be driven close to zero without unrealistic assumptions about the regularization. Our framework can handle any constraint set Ω on which Euclidean projections are computationally efficient. This includes the feasible set induced by La regularization: Ω = ( w E R': || < . for which the projection is given by a simple rescaling of w. Finally, note that if we do wish to use any regularization, define Ω R and the corresponding projection is the identity.
the deep learning setting, this will allow us
Problem Formulation. The learning task can be expressed as the problem (P) of finding feasible vector of parameters w, E Ω that minimizes f:
W. E argmin f(w).
(P)
wEn
Also note that f. refers the minimum value of f over Ω: f. A minwen f(w).
2.2 THE POLYAK STEP-SIZE
Before outlining the ALI-G algorithm, we begin with a brief description of the Polyak step-size, from which ALI- draws some fundamental ideas.
2

---

Under review as a conference paper at ICLR 2020
Setting. We assume that f. is known and non-stochastic updates: each iteration, the full objective ff and its derivative are evaluated. We denote by Vf(ww the first-order derivative of f at w (e.g. (w) can be sub sub-gradient or the gradient). In addition, || I| is the standard Euclidean norm in IRP, and (w) is the Euclidean projection of the vector w E RR on the set
Polyak Step-Size. At time--ste step using the Polyak step-size (Polyak] 1969
Shor 1985
Brannlund
1995 Nedić & Bertsekas 2001a b) yields the following update:
f(w) - f. [W,()
We+1
1l (w; (ww))) where
(2)
where we loosely define for simplicity purposes.
Interpretation. It can be shown that Wx+1 lies on the intersection between the linearization of w, and the horizontal plane 2 = f. (see Figure [ more the supplementary material). Note that since f. is the minimum of f, the Polyak step-size Yt is necessarily non-negative.
Loss function
Lineusization at Ws
Minimum f-
details in Proposition
Limitations. Equation 2 has two major short- comings that prevent its applicability in a machine learning setting. First, each update requires full eval- uation of f and its derivative. Stochastic extensions have been proposed in Nedić Bertsekas (2001a b). but they still require frequent evaluations of /. This is expensive in the large data setting, and even computa- tionally infeasible when using massive data augmen- tation. Second, when applying this method the non-convex setting of deep neural networks, the method sometimes fails to converge.
Figure 1: Illustration of the Polyak step-size in ID. this case, and further assuming that O. the algorithm coincides with the Newton Newton-Raphson method for finding roots of function.
Therefore we would like design an extension of the Polyak step-size that (i) is inexpensive to compute in a stochastic setting (e.g. with computational cost that is independent of the total number of training samples), and (ii) converges in practice when used with deep neural networks. The next section introduces the ALI-G algorithm, which achieves these two goals in the interpolation setting.
2.3 THE ALI-G ALGORITHM
We now present the ALI-G algorithm. For this, we suppose that we are in an interpolation setting: the model is assumed to be able to drive the loss function near all samples simultaneously.
Algorithm. The main steps of the ALI-G algorithm are provided in Algorithm| 1 ALI-G iterates over three operations until convergence. First, computes a stochastic approximation of the learning objective and its derivative (line 3). Second, it computes step-size decay parameter " based on the stochastic information (line 4). Third, updates parameters by moving the negative derivative direction by an amount specified by the step-size and projecting the resulting vector on to the feasible region (line 5).
Algorithm The ALI-G algorithm
Require: maximal learning-rate 7), initial feasible wo E Ω, small constant à
1: t= t= 0
2: while not converged do
3: Get fz, (Wz),
(Wez), Vlz, (we) with 2; drawn i.i.d. E (w.)
4: 71 min
[V (we) (+
5: Wi+1 = II
(we Vl W)))
6:
t=t+1
7: end while
3

---

Under review as a conference paper at ICLR 2020
Comparison with the Polyak Step-Size. There three main differences to the update in equation 2 First, each update only uses the loss l,. and its derivative rather than the full objective ff and its derivative. Second, the learning-rate 7/2 is clipped to 7), the maximal learning- rate emphasize that v remains constant throughout the iterations, therefore it is a single nyper-parametee and does not need schedule like SGD learning-rate. Third, the minimum f. has been replaced by the lower-bound of O. All these modifications will be justified in the next section.
We
The A Variant. When ALI-G uses no maximal learning-rate, we refer the algorithm as A since it is equívalent to use an infinite maximal learning-rate. Note that ALI-G requires no hyper-parameter for its step-size.
JUSTIFICATION AND ANALYSIS
3.1 INTERPOLATION ENABLES INEXPENSIVE STOCHASTIC UPDATES
By definition, the interpolation setting gives f. 0, which used in ALI-G simplify the formula of the learning-rate "/-- More subtly, the interpolation property also allows the updates to rely on the stochastic estimate L,, (w₂) rather than the exact but expensive f(w,). Intuitively, this is possible because in the interpolation setting, each training sample can use its own learning-rai without harming progress the other ones. Recall that ALI- the variant of ALI-G that uses no maximal learning-rate. The following result formalizes the convergence guarantee of ALI-G in the stochastic convex setting:
Theorem (Convex and Lipschitz). We assume that Qi is a convex set, and that for every 2, & is convex and C-Lipschitz, Let w. be solution of (P). and assume that the interpolation property approximately satisfied: vzz Z, (=(w,) &, for some interpolation tolerance 2 0. Then ALI-G applied to I satisfies:
C ( +1)
Wo W. II.I +0
Σ 1=0
Wt
Se
(3)
In other words, by assuming interpolation, ALI-G provably converges while requiring only Ez, (w.) and VL,, (We) (stochastic estimation per sample) to compute its learning-rate. In contrast, the Polyak step-size, which does not exploit interpolation, would require f(w,) and Vf(w:) compute the learning-rate (deterministic computation over all training samples). This constitutes a major computational advantage of ALI-G over the usual Polyak step-size.
We emphasize that in Theorem ! our careful analysis explicitly shows the dependency of the convergence result the interpolation tolerance e. It is reassuring to note that convergence is exact when the interpolation property is exactly satisfied (e 0).
In the supplementary material, also establish convergence rates of O(1/T) for smooth convex functions, and Oc(xp( (aT/888))) for a-strongly convex and 3-smooth functions. Similar results can be proved when using a maximal learning-rate yy: the convergence speed then remains unchanged provided that is large enough, and it lowered when is small. We refer the interested reader to the supplementary for the formal results and their proofs.
3.2 MAXIMAL LEARNING- RATE HELPS WITH NON- CONVEXITY
The Polyak step-size may fail to converge when the objective is non-convex, as figure 2 illustrates: in this (non-convex) setting, gradient descent with Polyak step-size oscillates between two symmetrical points because its step-size is too large (details in the supplementary).
Indeed, we empirically find that non-convexity usually leads to overestimation of the Polyak step-size. Intuitively, using maximal learning-rate allows ALI-G to behave like constant step-size SGD in non-convex regions where the Polyak step-size would be evtr-estimated, and to automatically use the Polyak step-size once reaching convex basin of convergence.
Importantly, using a maximal bearning-rate can be seen as a very natural extension of SGD when using a non-negative loss function:
4

---

Under review as a conference paper at ICLR 2020
Proposition 1. [Proximal Interpretation] Suppose that 92 = Rp and let ó O. We consider the update performed by SGD: wSGD = W: N Vlza (we): and the update performed by ALI-G: (w,)
= W. - 7th 222 (We), where Tt2 = min (we))l [+1
Then we have:
SGD W r+1 = argmin
||w
w.ll? + le, (we) + Vlz, (we) T we)}.
(4)
wER
2T
ALJG W++1
argmin
|w- well max (W,, + Vlz, (we) (w -w))
(5)
WER
27
In other words, at each iteration, ALI-G solves proxi- mal problem in closed form in a similar way to SGD. In both cases, the loss function &, is locally approximated by a first-order Taylor expansion at w,. The difference that ALI-G also exploits the fact that l, non- negative. This allows ALI-G to use constant value for y in the interpolation setting, while the searning-rate T) of SGD needs to be manually decayed.
f + w² - 1
I Linearizations of f
is currently an open question whether ALI-G can be proved to converge in the stochastic non-convex setting given a sufficiently small yet constant maximal learning-rate rate 77.
Figure 2: simple example where the Polyak step-size oscillates due to non- convexity. On this problem, ALI-G con- verges whenever its maximal learning-rate r is lower than 10.
RELATED WORK
Interpolation in Deep Learning. As mentioned in the introduction, recent works have successfully exploited the interpolation assumption to prove convergence of SGD the context of deep learning (Ma et al., 2018, Vaswani et al., (2019a] Zhou al. 2019). Such works are complementary the sense that they provide a convergence analysis of an existing algorithm for deep learning.
in
Adaptive Gradient Methods. Similarly to ALI-G, adaptive gradient methods also rely on tuning single hyper-parameter, thereby providing more pragmatic alternative to SGD that needs specification of the full learning-rate schedule. While the most popular ones are Adagrad (Duchi
ct al. 2011), RMSPROP (Tieleman & Hinton 2012), Adam (Kingma & Ba 2015) and AMSGrad
(Reddi et al. aal,[220 2018), there have been many other variants (Zeiler 2012 & Pal 2013 Détossez
& Bach 2017 Levy 2017] Mukkamala & Hein 2017 Zheng & Kwok 2017 Bernstein et al.) [0088
Chen & [018 [Saazerr & Stern [tem|22018] Zaheer et al.
2018 CChn
2018|Chen et al. 2019 Loshchilov & Hutter
2019 Luo al., 2019). However, as pointed out in Wilson al. (2017), adaptive gradient methods
tend to give poor generalization in supervised learning. In our experiments, the results provided by
AL.- are significantly better than those obtained by the most popular adaptive gradient methods.
Adaptive Srarning-Rate Algorithms. Vaswani et al. 2019b) show that one can use line search in a stochastic setting for interpolating models while guaranteeing convergence. However, in contrast to our work, the resulting algorithm requires more than one hyper-parameter (up to four), and the line-search is not computed in closed form. Less closely related methods have proposed adaptive learning-rae -aates without using the minimum for the computation of the learning rate (Schaul et al. 2013 Tan et al., 2016 Zhang et al. 2017 Baydin et al. 20088) /Wu et al., 2018 Li & Orabonal (019)). )) but they have not demonstrated competitiveness against SGD with well-tuned hand-designed schedule.
LA Algorithm. The L1 algorithm (Rolinek & Martius 2018 also uses modified version of the Polyak step-size. However. the L, algorithm computes an online estimate of f. rather than relying on a fixed value. This requires three syperrparammters, which are in practice sensitive to noise and crucial for empirical convergence of the method. addition, Ia does not come with convergence guarantees. In contrast, by utilizing the interpolation property and a maximal learning-rate, our method is able to (i) provide reliable and accurate minimization with only a single hyper-parameter and (ii) offer guarantees of convergence in the stochastic convex setting.
5

---

Under review as a conference paper at ICLR 2020
Frank-Wolft Methods. The proximal interpretation in Proposition Ialoows allows us to draw additional
parallels to existing methods. In particular, the formula of the learning -rateng--rrrtggaeee rate "t may remind the reader
of the Frank- Wolfe algorithm (Frank & Wolfe 1956) in some of its variants (Locatello et al. (017).
or other dual methods (I (Lacoste-Julien et al. [013] Shalev-Shwartz & Zhang 2016). This is because
such methods solve in closed form the dual of problem (5), and problems the form of (5) naturally
appear in dual coordinate ascent methods Shalev-Shwarte & Zhang 2016).
When no regularization is used, ALI-G and Deep Frank-Woll (DFW) (Berrada al. 2019) are procedurally identical algorithms. This is because in such setting, one iteration of DFW also amounts to solving 5 in closed-form more generally. DFW is designed to train deep neural networks by solving proximal linear support vector machine problems approximately. However, we point out the two fundamental advantages of ALI-G over DFW: (i) ALI-G can handle arbitrary (ower-boundel. loss functions, while DFW can only use convex piece-wise linear loss functions; and (ii) as seen previously, ALI-G provides convergence guarantees the convex setting.
SGD with Polyak's Learning-Rate Oberman & Prazeres 2019) extend the Polyak step-size to rely on a stochastic estimation of the gradient Vłz, (w₂) only, instead of the expensive deterministic gradient V f(wz). However, they still require evaluate /(we), the objective function over the entire training data set, in order to compute its learning-rate, which makes the method impractical. In addition, since they do not do exploit the interpolation setting nor the fact that regularization can be expressed as a constraint, they also require the optimal objective function value f. in advance.
PROX Algorithm. Asi & Duchi 2019) have recently introduced the APRO algorithm, family of proximal stochastic optimization algorithms for convex problems. Notably, the APROX "truncated model" version is similar to ALI-G. However, there are four clear advantages of our work over (Asi) & Duchi 2019) in the interpolation setting, in particular for training neural networks. First, our work is the first to empirically demonstrate the applicability and usefulness of the algorithm on varied modern deep learning tasks most of our experiments use several orders of magnitude more data and model parameters than the small-scale convex problems of (Asi & Duchi 2019). Second, our analysis and insights allow to make more aggressive choices of learning rate than (Asi & Duchi 2019). Indeed, Asi & Duchi (2019) assume that the maximal learning-rate is exponentially decaying, even in the interpolating convex setting. In contrast, by avoiding the need for an exponential decay, the learning-rate of ALI-G requires only one hyper-parameters instead of two for APROX. Third, our analysis takes into account the interpolation tolerance 2 rather than unrealistically assuming the perfect case ε = O (that would require infinite weights when using the cross- cross-enrrppy loss for instance). Fourth, our analysis proves fast convergence in function space rather than iterate space.
EXPERIMENTS
We empirically compare ALI-G to the optimization algorithms most commonly used in deep learning. Our experiments span a variety of architectures and tasks: (i) learning differentiable neural computer; (ii) training wide residual networks on SVHN; (iii) training a Bi-LSTM on the Stanford Natural Language Inference data set; and (iv) training wide residual networks and densely connected networks on the CIFAR data sets. Note that the tasks of training wide residual networks on SVHN and CIFAR- 100 part of the DeepOBS benchmark [Schneider et al. (2019), which aims standardizing baselines for deep learning optimizers. In particular, these tasks are among the most difficult ones of the benchmark because the SGD baseline benefits from a manual schedule for the learning rate. Despite this, ALI-G obtains competitive performance with SGD. In addition, ALI-G is the best performing method with a single hyper- aperrpprreeter on the difficult tasks of Bi-LSTM on SNLI and ResNet variants on CIFAR.
The code to reproduce our results will be made publicly available. In the Tensorflow (Abadi et al. 2015) experiment, we use the official and publicly available implementation of I. In the Py Porch (Paszke et al. (017)) experiments, we use our implementation of I4,, which we unit-test against the official Tensorflow implementation. In addition, we employ the official implementation of DrWF) and
httt::://gttubb..om/vvaaaaa

---

Under review as a conference paper at ICLR 2020
re-use their code for the experiments SNLI and CIFAR. All experiments are performed either on a 12-core CPU (differentiable neural computer) or on a single GPU (SVHN, SNLL, CIFAR).
5.1 DIFFERENTIABLE NEURAL COMPUTERS
Setting. The Differentiable Neural Computer (DNC) GGrvess et al. 2016 is recurrent neural network that aims at performing computing tasks by learning from examples rather than by executing an explicit program. In this case, the DNC learns repeatedly copy a fixed size string given input. Although this learning task is relatively simple, the complex architecture of the DNC makes it an interesting benchmark problem for optimization algorithms.
Methods. We use the official and publicly available implementation of DN We vary the initial learning rate as powers of ten between 10 10- -4 and 10t for each method except for LęAdam and La Mom. For Adam and LoMom, since the main hyper-parameter is designed to lie in (0. 1), we vary it between 0.05 and 0.095 with a step of 0.1. The gradient norm is clipped for all methods except for ALI-G, LjAdam and L Mom (as recommended by Rolinek & Martius (011
Step-Siae Hsper-Parateeted (e3)
sas
LAAda
2--
4--4
5--5
Sm Te-i
Tea0
2e-1
Laurning Tlate (q):
163
16.3
1ve8
Adams
G--2
1--4
2--4
5-15
2e-1
2e-5
lef2
1++2
RMssPrup
2i-1
2--7
2--7
3x-7
Te+0
1++2
SGD
Se-0
9v
Maxtimal Learning- Date (1))
1o44
A1L44
Se-a
2i-3
6--1
2u-4
G--5
3e-5
4
1e.7
In-7
2-22
Final objective function when training Differentiable Neural Computer for 10k steps (lower is better). The intensity of each cell is pog-proportional to the value of the objective function (darker is better). ALI-G obtains good performance for very large range of n (10-1 S 10%).
Figure 3:
Results. We present the results in Figure ALI-G provides accurate optimization for any 7) within 10-1,100; and is among the best performing methods by reaching an objective function of 4.10 On this task, RMSProp, L4Adam and M4Mom also provide accurate and robust optimization. In contrast to ALI-G and the L4 methods, the most commonly used algorithms such as SGD, SGD with momentum and Adam are very sensitive to their main learning-rate syper-parameter Note that the difference between perl-performing methods is not significant here because these reach the numerical precision limit of single-precision float numbers.
5.2
WIDE RESIDUAL NETWORKS ON SVHN
Setting. The SVHN data set contains 73k training samples, 26k testing samples and 531k additional easier samples. From the 73k difficult training examples, we select 6k samples for validation; we use all remaining (both difficult and easy) examples for training, for total of 598k samples. We train wide residual network 16-4 following Zagoruyko & Komodakis (016)).
Method. For SGD, we use the manual schedule for the learning rate of Zagoruyko Komodakis (2016). For La Adam and LoMo we cross-validate the main learning-rate hyper-parameter a to be in (0.0015, 0.015, 0.15) (0. 15 is the value recommended by Rolinek & Martius (2018)). For other methods, the learning rate hyper-parameter is tuned as power of 10. The Ls regularization cross- vrlss-aal in (0.0001, 0.0005) ) for all methods but ALI-G. For ALI-G, the regularization is expressed as constraint the L2-norm of the parameters, and its maximal value is set 50. SGD,
httpp:: /tt::://gtttii com deepm/deemmiiii
7

---

Under review as a conference paper at ICLR 2020
ALI-G and BPGrad use Nesterov momentum of 0.9, All methods use dropout rate of 0.4 and fixed budget 160 epochs, following (Zagoruyko & Komodakis (016))
Results. The results are presented in Table On this relatively easy task, most methods achieve about 98% test accuracy. Despite the cross-validation, LęMom does not converge on this task. Even though SGD benefits from designed schedule, ALI-G and other adaptive methods obtain close performance to it.
Adagrad
Adam
AMSGrad
BPGrad
DFW
LaAdam
LyMom
ALLG
SGD
SGD
98.0
97.9
97.9
98.1
98.1
98.2
19.6
98.1
98.3
98.4
Table 1: Test Accuracy (%) on SVHN. In red, SGD benefits from hand-designed schedule for its learning-rate, In black, adaptive methods, including ALJ-G, have single soper-parameter for their learning-rate SGDI refers the performance reported by Zagoruyko & Komodakis (2016).
5.3 BI-LSTM ON SNLI
Setting. We train a Bi-LSTM of 47M parameters on the Stanford Natural Language Inference (SNLI) data set (Bowman et al. 2015). The SNLI data set consists in 570k pairs of sentences, with each pair labeled as entailment, neutral or contradiction. This large scale data set is commonly used as pre-training corpus for transfer learning many other natural language tasks where labeled data scarcer (Conneau et al. 2017) much like ImageNet is used for pre- pre-training in computer vision. We follow the protocol of Berrada al. 22019;; we also re-use use their code and results for the baselines.
is cross-validated in {0.015, 0.15) compared to the recommended value of 0.15, this helped convergence and considerably improved performance. The SGD algorithm benefits from hand hand-designed schedule, where the learning- -aate is decreased by when the validation accuracy does rates and do not require such schedule. The value of the main syper-parameted a power of ten for the AL.- algorithm and for previously reported adaptive methods. Following the evaluated
Method. For Adam and Mom, the main hyper-parameter
improve. Other methods use adaptive learning-
is cross-validated as
implementation by Conneau et al. (017)). no C2 regularization is used. The algorithms with the Cross- cesss-Entropy (CE) loss and the multi-class hinge loss (SVM), except for DFW which is designed for SVMs only. For all optimization algorithms, the model is trained for 20 epochs, following (Conneau et al.) 2017).
AMSGrad
Adagrad*
Adam*
BPGrad
DFW
L4Adam
LyMom
ALI-G
ALI-G
SGD*
SGD
Loss
CE
83.8
84.5
84.2
83.6
83.3
83.7
84.6
84.8
84.7
84.5
SVM
84.6
85.0
85.1
84.2
85.2
82.5
83.2
84.7
85.2
85.2
Table 2: Test Accuracy (%) on SNLI. In red, SGD benefits from a hand-designed schedule for its learning-rate, In black, adaptive methods have single hyper-parameter for their learning-rate. In blue, R does not have any syper-parameter for its learning-ratt ratte. With an SVM loss, DFW and ALI-G are procedurally identical algorithms - but in contrast to DFW. ALI-G can also employ the CE loss. Methods in the format X re-use results from Berrada et al. 2019). SGD is the result from Conneau et al. (2017).
Results. We present the results in Table 2 ALI-G is the only method that requires hyper- parameter for its learning-ran rate. Despite this, and the fact that SGD employs learning-rate schedule that has been hand designed for good validation performance, ALI-G* is still able to obtain results that are competitive with SGD. Moreover, ALI-G, which requires a single hyper-parameter for the learning-rate, outperforms all other methods for both the SVM and the CE loss functions.
8

---

Under review as a conference paper at ICLR 2020
5.4 WIDE RESIDUAL NETWORKS AND DENSELY CONNECTED NETWORKS ON CIFAR
Setting. We follow the methodology of Berrada et al. (0019) ; we also re-use their code and we reproduce their results. We test two architectures: Wide Residual Network (WRN) 40-4 (Zagoruyko & Komodakis] 2016) and a bottleneck DenseNet (DN) 40-40 (Huang et al. 2017). We use 45k samples for training and 5k for validation. The images are centered and normalized per channel. We apply standard data augmentation with random horizontal flipping and random crops. AMSGrad was selected in Berrada et al. (2019) because it was the best adaptive method on similar tasks, outperforming in particular Adam and Adagrad. In addition to the baselines from |errada et al. (2019), we also provide the performance of L4 Adam, LyMom, AdamW (Loshchilov Hutter 2019) and Yogi (Zaheer et al. 2018).
Method. All optimization methods employ the cross-entropy loss, except for the DFW algorithm, SVM loss. For DN and WRN respectively. SGD uses the manual learning rate schedules from Huang et al. (0017) and Zagoruyko & Komodakis (2016). Following Berrada et al. (2019), the batch-size cross-validated (64, 128, 256} for the DN architecture, and {128, 256, 5 for the WRN architecture, For LdAdam and L,Mom, the learning rate hyper- parameter
which is designed to
validated in {0.015, 0.153. For AMSGrad, AdamW, Yogi, DFW and ALI-G, the Searning-rate hyper-panne parameter is cross-validane validated as power of 10 (in practice 17 {0.1. 1 for ALI--). SGD, DFW and ALI-G use a Nesterov momentum of 0.9. Following [errada al. (2019). for all methods but ALI-G and Adam W. the L2 regularization is cross-validated in {0.0001, 0.0005) on the WRN architecture, and is set to 0.0001 for the DN architecture. For Adam W, the weight-decay constraint on the
cross- vols--vllddted as power of 10. For ALI-G, L2 regularization is expressed norm on the vector of parameters; its maximal value is set to 100 for the WRN models, 80 for DN on CIFAR-10 and 75 for DN on CIFAR-100 For all optimization algorithms, the WRN model is trained for 200 epochs and the DN model for 300 epochs, following respectively (Zagoruyko & Komodakis 2016) and (Huang et al. 2017).
Results. We present the results in Table 3 In this setting again, ALI-G obtains competitive
performance with manually decayed SGD. AL-G largely outperforms AMSGrad, AdamW and Yogi. In addition, it significantly bridges the gap between DFW and SGD on CIFAR- 10 with the WRN model, and on CIFAR-100 with the DN one.
AMSGrad
AdamW
Yogi
DFW
L4Adam
L&Mom
ALL-G
SGD
SGD
Data Set
Architecture
WRN
90.8
92.1
91.2
94.2
90.5
91.6
95.2
95.3
95,4
CIFAR-10
DN
91.7
92.6
92.1
94.6
90.8
91.9
95.0
95.1
WRN
68.7
69.6
68.7
76.0
61.7
61.4
75.8
77.8
78.8
CIFAR-100
DN
69.4
69.5
69.6
73.2
60.5
62.6
76.3
76.3
Table 3: Test Accuracy (%) the CIFAR data sets. In red, SGD benefits from hand-designed
schedule for its learning-rate. In black, adaptive methods, including ALI-G, have a single hyper- parameter for their learning-rate. SGDI refers the result from Zagoruyko & Komodakis (2016). Each reported result is an average over three independent runs; the standard deviations are reported in Appendix (they are at most 0.3 0.3 ALI-G and SGD).
5.5 TRAINING PERFORMANCE
The experiments have so far focused on testing accuracy (except for the DNC task), because that the main metric driving practitioners' choice of optimization algorithm. In this section, we empirically assess the performance of ALI-G and its competitors in terms of training objective. comparable objective functions, the L2 regularization is deactivated. We do not use dropout. The learning-rate selected as a power of ten for best final objective value, and the batch-size is set to its default value. All methods use fix budget of 160 epochs for WRN-SVHN, 200 epochs for WRN- CIFAR and 300 epochs for DN-CIFAL following (Zagoruyko & Komodakis, 2016) and (Huang al. 2017), The L4 methods diverge CIFAR- -00 in this setting. For clarity, only display the
order to have

---

Under review as a conference paper at ICLR 2020
performance of SGD, Adam, Adagrad and ALI-G (DFW does not support the cross-entropy loss). Here SGD uses a constant learning-rate to emphasize the need for adaptivity. Therefore all methods use one nyper-parameter for their learning- rate. As can be seen, ALI-G provides better training performance than the baseline algorithms on all tasks.
WRN-CIFARIO
WRN-CIFARIO0
DN-CIFARIO
10a
10a
10a
10
1
10
10 2
10
2
10 3
10
10
3
100
200
200
DN-CIFARI00
WRN-SVHN
16
10
Adagrad
10-2
Adam
10
SGD
ALI-G
10-4
10"3
100 200 300
80
160
Figure 4: Objective function functionn over the epochs on CIFAR-1O, CIFAR-100 and SVHN (smoothed with a moving average over 5 epochs). On SVHN, ALI-G obtuins similar performunce to its competitors and converges faster. On CIFAR-10 and CIFAR-100, which are more difficult tasks, ALI-G yields an objective function that is order of magnitude better than the baselines.
6 DISCUSSION
We hope that the ALI-G algorithm is helpful step towards efficient and reliable training of deep neural networks. ALI-G is readily applicable to a broad range of applications in deep learning where the model can interpolate the data. When that is not the case however, it would be interesting to design new algorithms that adapt the minimum f. online while requiring few hyper-parameters. This could be achieved for instance by building upon the works Nedié & Bertsekas (2001b) and Rolinek & Martius 2018).
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo. Zhifeng Chen, Craig Citro, GregS. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelioné Man, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernandaégas Vi, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems, 2015. Software available from tensorflow.org.
Hilal Asi and John C Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity. SIAM Journal on Optimization, 2019.
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. International Conference on Learning Representations, 2018
10

---

Under review as a conference paper at ICLR 2020
Jeremy Bernstein, Yu- Xiang Wang. Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd: Compressed optimisation for non-convex problems. International Conference on Machine Learn- ing, 2018.
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Deep Frank-Wor Wolfe for neural network optimization. International Conference on Learning Representations, 2019.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. Conference on Empirical Methods in Natural Language Processing, 2015.
Ulf Brännlund. A generalized subgradient method with relaxation step. Mathematical Programming, 1995.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 2015.
Jinghui Chen and Quanquan Gu. Padam: Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint, 2018.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. International Conference on Learning Representations, 2019.
Alexis Conneau, Douwe Kiela, Holger Schwenk, Loic Barrault, and Antoine Bordes. Supervised learning of universal sentence representations from natural language inference data. Conference on Empirical Methods in Natural Language Processing, 2017.
Alexandre Défossez and Francis Bach. Adabatch: Efficient gradient aggregation rules for sequential and parallel stochastic gradient methods. arXiv preprint, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research
Logistics Quarterly, 1956.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwiñska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using neural network with dynamic external memory. Nature, 2016.
Gao Huang, Zhuang Liu, Kilian Q Weinberger, and Laurens van der Maaten. Densely connected convolutional networks. Conference on Computer Vision and Pattern Recognition, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International
Conference on Learning Representations, 2015.
Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate Frank-
Wolfe optimization for structural SVMs. International Conference on Machine Learning, 2013.
Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. Neural Information Processing Systems, 2017.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. International Conference on Artificial Intelligence and Statistics, 2019.
Francesco Locatello, Rajiv Khanna, Michael Tschannen, and Martin Jaggi. A unified optimization view on generalized matching pursuit and frank-wolfe. International Conference on Artificial Intelligence and Statistics, 2017.
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. International Conference on Learning Representations, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. International Conference on Learning Representations, 2019.
11

---

Under review as a conference paper at ICLR 2020
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern wwrrpparametrized learning. International Conference on Machine Learning, 2018.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. International Conference on Machine Learning, 2017.
Angelia Nedić and Dimitri Bertsekas. Convergence rate of incremental subgradient algorithms. Stochastic optimization: algorithms and applications, 2001a.
Angelia Nedié and Dimitri Bertsekas. Incremental subgradient methods for nondifferentiable opti- mization. SIAM Journal Optimization, 2001b.
Adam M Oberman and Mariana Prazeres. Stochastic gradient descent with polyak's learning rate. arXiv preprint, 2019.
Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. International Conference on Algorithmic Learning Theory, 2015.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. NIPS Autodiff Workshop, 2017.
Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 1969.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. International Conference on Learning Representations, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, 1951.
Michal Rolinek and Georg Martius. L4: Practical loss-based stepsize adaptation for deep learning. Neural Information Processing Systems, 2018.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. International Conference on Machine Learning, 2013.
Frank Schneider, Lukas Balles, and Philipp Hennig. DeepOBS: A deep learning optimizer benchmark suite. International Conference on Learning Representations, 2019.
Shai Shalev-Shwartz and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Mathematical Programming, 2016.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. International Conference on Machine Learning. 2018.
Naum Zuselevich Shor. Minimization methods for non-differentiable funniiiir Springer Series in Computational Mathematics, 1985.
Conghui Tan, Shigian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic
gradient descent. Neural Information Processing Systems, 2016.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 2012.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. International Conference on Artificial Intelligence and Statistics, 2019a.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. arXiv preprint, 2019b.
12

---

Under review as a conference paper at ICLR 2020
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Neural Information Processing Systems, 2017.
Xiaoxia Wu, Rachel Ward, and Léon Bottou. WNGrad: Learn the learning in gradient descent. arXiv preprint, 2018.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. British Machine Vision Confer- ence, 2016.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Neural Information Processing Systems, 2018.
Matthew Zeiler. ADADELTA: an adaptive learning rate method. arXiv preprint, 2012.
Ziming Zhang, Yuanwei Wu, and Guanghui Wang. Bpgrad: Towards global optimality in deep learning via branch and pruning. Conference on Computer Vision and Pattern Recognition, 2017.
Shuai Zheng and James T Kwok. Follow the moving leader in deep learning, International Conference on Machine Learning, 2017.
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges to global minimum in deep learning via star-convex path. International Conference Learning Representations, 2019.
13

---

Under review as a conference paper at ICLR 2020
A LOCAL INTERPRETATION OF THE POLYAK STEP-SIZE
Proposition 2. Suppose that the problem is unconstrained: Ω I.P Let Wi+1
We
f(wa)-f f Vf(w.). Then We+1 verifies: [wwll
We+1
T argmin ||www[ll subject to: f(w.) V.(ww)) (w -ww) Sar
(6)
WER*
where we remind that f. the minimum of f. and w + f(w)) + f((w)) (w w.) is the linearization of f at wt. In other words, Wi-1 is the closest point we that lies on the hyper- ppaer-plane
f(we) + V((w)) (w we) f..
Proof: See Appendix D.I
B CONVERGENCE RESULTS
Before we detail our convergence results, we introduce the notions of uniform lower bound and e-interpolation.
B.1 NOTATION
Intuitively, a uniform lower bound on the problem (P) is a lower bound on all loss functions & on their unconstrained domain RP. We formalize this below:
Definition (Uniform Lower Bound). say that B is a uniform lower bound on P ift
inf inf (w).. ZE wERr
Note that in the main paper, we have used the special case B = 0 as the uniform lower bound. The definition above makes useful statistic analyze the behavior of each loss function f, around w., in a uniform way (that is, independently of 2). The quality of a uniform lower bound B can be quantified by the notion of e-interpolation:
Definition (E-Interpolation). Let B be a uniform lower bound on P W. be a solution of P and
2 0 be non-negafive number. Then say that w. is e-interpolation for (PP) if:
Vz Z, (w(w)) S.
(8)
By taking the expectation over equation we can see that if w. is an e-interpolation for (P)) B).
then we immediately have: f-- E S B S f.. other words, B is also an approximation of f. by below, and its quality is quantified by e. We further note that f- does not satisfy the definition of uniform lower bound in the general case. However when f. actually is a uniform lower bound, for any solution w, of w, is a O-interpolation for (P), f.).
In the general case where B may different from O, the ALI-G step-size can be defined as:
Ez, (w:)
7t min
Vi (. 1 5
We now turn convergence results, which give convergence rates in three settings: convex and Lipschitz functions, convex and smooth function, and strongly convex and smooth functions. each setting, analyze three regimes which complement each other: no (infinite) maximal learning-rate. large maximal learning-rate and small maximal learning-rate.
B.2 LIPSCHITZ CONVEX FUNCTIONS
Theorem 2. [Convex and Lipschitz] We assume that X convex set, and that for every Z,
lg is convex and C- C-Lipschirz. Let be a uniform lower bound on (P) and w, be a solution of (P) Further suppose that w. is an e-interpolatton for (.P). B). Then ALI- applied satisfies:
T
C ( +
+1)
Wo w. 1. +
We - - -e
(10)
T+
VT
14

---

Under review as a conference paper at ICLR 2020
Proof: See Appendix D33
Theorem 3. We assume that X is a convex set, and that for every 2, Eg is convex and C-Lipschitz.
Let w. be an e-interpolation for ((P), B). We further assume that v) > 5. Then if we apply ALI-G with maximal learning-rac -rate of rj to f. we have:
T
Wo w.ll
8²
102 8)1 Wo w.ll
C
Σ We
J.
8(1 - )) +V
+81
+1.
1 (T +1)
T T+1
(11)
Proof: See Appendix D.4
We note that for very large values of o0). Theorem 3 gives the exact same result Theorem 2. However when is small, the convergence error of Theorem i large. This is corrected in the following result which is informative in the regime where rj is small:
Theorem 4. We assume that is a convex set, and that for every E 2, lg is convex and C-Lipschitz. Let w. be e- e-interpolation for (P). B). Then we apply ALI-G with maximal learning -ate of
to J, we have:
(wo w.ll n(T + 11
(C2 + :5)l(wo w.ll? + NEEC2 + (12)
f
Σ
We
f.
+
T+1 1=0
T+1
Proof: See Appendix D.5
B.3 SMOOTH CONVEX FUNCTIONS
We now tackle the convex and 6-smooth case. Our proof techniques naturally produce the separation 7 2 23 and 17 S J. Whenever 77 2 28 the convergence result is exactly the same when r co.
When S 23 the speed of convergence is limited by the value of r7.
Theorem 5. [Convex and Smooth] We assume that X is convex set, and that for every 2 2, le is
convex and 3-smooth. Let be uniform lower bound on (P) and w. be solution of P). Further suppose that w. is an E-interpolation for satisfies:
B), and that > 23c. Then ALI-G applied to f
6
23
[Wo w.1l2
We
Sa
+
(13)
T
3(1
29c
1
20 8
T + 1
1==
8
Proof: See Appendix D.6
Theorem 6. We assume that X is convex set, and that for every 2, Eg is convex and B-smooth.
Let w. be an e-interpolation for ( (P)). B), and suppose that 8 >> 23c. Further assume that nj 2 23"
Then if we apply ALI-G with maximal learning-rate of 1 to f. we have:
T
8
23
Wo W. 112
Σ
We
- f.
+
(14)
T+I
3(1
29g
1
3
T+1 1
1=0
Proof: See Appendix D.7
Theorem 7. We assume that X is a convex set, and that for every 2 E Z, lg is convex and B-smooth.
Let w. be E-interpolation for ( ((P). B), and suppose that 8 > 23c. Further assume that n m Then if we apply ALI-G with maximal learning-rai rate of 17 to f. have:
1
T
-f < | w. w.ll2
T+12 1=0
+ E.
(15)
(T 1)
23
Proof: See Appendix
D.8
15

---

Under review as a conference paper at ICLR 2020
B.4 SMOOTH AND STRONGLY CONVEX FUNCTIONS
Finally, we consider the a-strongly convex and 8-smooth case. Again, our proof yields a natural separation between 1) 2 and // S 23* In similar way to the 3-smooth case, when 1/ 2 28' Theorem gives the exact same result as + oo. And when S 2 by Theorem is limited by the value of
the rate of convergence given
Theorem 8. [Strongly Convex and Smooth] We assume that X' is a convex set, and that for every E 2, lz is a-strongly convex and 3-smooth. Let be a uniform lower bound ( and w. be solution of (P). Further suppose that w, is an e-interpolation for (P). B), and that ò > 2Bc. Then
ALI-G applied to f satisfies:
aT
28 w.ll
82
f(WT+1) s Bexp
10
+
(16)
83
a
a
a²
In other words. f approximately converges f. at rate of (eepp(paa///00
Proof: Appendix
Theorem 9. We assume that X is convex set, and that for every Z, Eg is a-strongly convex and B-smooth. Let w, be an e-interpolation for (P)) B), and suppose that ō > 2ßc. Further assume that 1) 2 23' Then if we apply ALI- with a maximal learning-raad -aae of to J, we have:
aT
28
3
32
f(wT+1) - S B exx
83 l/ w.ll2 a
+
+
E.
(17)
a
Proof: See Appendix D.10
Theorem 10. We assume that X is a convex set, and that for every 2 E Z, & is a-stonggly corvex and B-smooth. Let w. be an e-interpolation for (P). B), and suppose that > 28c. Further assume that 1) S 23. Then if we apply ALI-G with a maximal learning-rate of 1) to J, we have:
anT
28
14s8
f(WT+1) - f+ S Bexp
l| woll
(18)
4
a
Proof: See Appendix D.I1
C ON THE NEED FOR A MAXIMAL LEARNING- FOR NON-CONVEXITY
The Restricted Secant Inequality (RSI) is a milder assumption than convexity. It can be defined as follows:
Definition 3. Let f RR R be a lower-hounded differentiable function achieving its minimum at W.. We say that f satisfies the RSI if there exists > O such that:
Vw E RP, vf(w) (w- w.) 2 a -.,l
(19)
The RSI is sometimes used to prove convergence optimization algorithms without assuming convexity /Vaswani et al. 2019bb.
As we prove below, the Polyak step-size may not convergence under the RSI assumption, even in a non-stochastic setting with the exact minimum known.
We introduce the function f w E 17 glle for simplicity purposes show that ff fulfills the RSI assumption, and then that it oscillates between two points for a well chosen initialization.
+ w² |w| 3 We restrict our domain of study to [=3,
extension to IR can easily be constructed by extending f. We will first
Let us show that f satisfies the RSI with a = J. First we note that f achieves its minimum at w, = and that f(w,) = O. In addition, we introduce the sign function (w)), which is equal to 1 if w 2
16

---

Under review as a conference paper at ICLR 2020
w + -² |w/* Linearizations of f
Figure 5: Illustration of the function f. which satisfies the RSI. When starting at 3//5, gradient descent with the Polyak step-size oscillates between w 3/5 and w = 3/5.
and -1 otherwise. Now let [=2; B1. Then we have that:
vf(w)(w w.) (w- w.)2 : (2w 30 30(ww) -0) (w 0)2.
9 w² 3
(20)
3 2
5 o(w)w)
2 0.
Now lct us show that if we apply gradient descent with a Polyak step-size to f. with starting point
-3
5 we obtain wi -. This will prove oscillation of the iterates by symmetry of the problem.
Let wp- -3 Then have ((w) 25
27
Furthermore, (((.)) 2( 2(53)) + 3( 3(2)
125
125
25 Therefore:
f(w)) (W(p),,
10 = 100
(w))))
(wp)
w00
V f(w))
3
125
(21)
5
25
-3
6
5'
3
5"
D PROOFS
D.1 PROPOSITION
Proposition 2. Suppose that the problem is unconstrained: Ω IRP. Let We+1
[W 3 V((w)). Then W verifies:
f(w:
We+1
argmin |[w - -ell subject to: f(w:) + V.(w.)) (w -w)- = sar
(6)
WERP
where remind that f. is the minimum of f. and + f(we) + V((w:) (w w.) is the linearization of f at w., In other words, W,-1 is the closest point to w. that lies on the hyper-plane
f(w) f((.)) (w wi) f..
Proof: First show that we+1 satisfies the linear equality constraint:
17

---

Under review as a conference paper at ICLR 2020
f(w.) + VV((w)) (We+1 -w))
f(w.) - (. [VV[(w)]]
-[(w.) v.((w.)
(((w)))
(22)
-((w)) - (((w)) +
= fa.
Now let show that has a minimal distance to W..
We take w E IR a solution of the linear equality constraint, and we will show that |[w+1 weel S |w wall. By definition, we have that w satisfies:
f(w.) V.(w.)) (w (W-w fa.
(23)
Now we can write:
| w.ll f(wi) fo V[(w))ll
IVS( (w:)
f(we) f.
[V
V (ww.) (w w.)
(24)
[
| f( [w.)]]]]]
wel
Seauchy-Scwarr
[f(w:)l
|
wall
D.2 THEOREM
Proposition 1. [Proximal Interpretation) Suppose that S2 = Rd and let 5 = 0. We consider
the update performed by SGD: wi+1 = W: Te Vlz 122,(W) (Wr); and the update performed by ALI-G: Ex, (we)
w = W. - 7/ Vlz, (W.), where 7/2 = min IiVe, (w,,,,,, Then we have:
SGD w r+1
argmin
_ ||w w.ll Ez (wr) Vlz (w:) wi)]
(4)
12)
wER"
W++1
AIG
argmin
ww
will max (w:)) + Vls, (w:) (i))T(w (w-w)),0) wo),
(5)
wER"
2n
We tackle the slightly more general case where B may be different from zero. In order to make the notation simpler, use d, & Vf,, (W.) and lx (w:) B.
Proof:
First, let us consider d; = 0.
Then we choose = and it is clear that We+1 W. 17 d, = w, is the optimal solution of problem
We can successively re-write the proximal problem as: now assume de
w wel max (w.)) Ve (wi) " w.).
min
WERP
21 w wel" max E2, (w:)- -B- B Vlal(we) (w (w- m.).
min
| wel max (1 + df d.(ww (w- (w-ww).00)) w.).of}
min weB weke
2n
min wER".
| w + subject to: v20, v 2 le + d, (w-wi w.)
2m
18

---

Under review as a conference paper at ICLR 2020
min WE P,M20
sup w well + wv vi( 41 di' (w wi))
sup
min
ww
wel + - pou - v(u - 4 di (w we))
(strong duality)
(25)
A.220
WERP
2q
The inner problem is now smooth in w and v. We write its KKT conditions:
Ø.
0:
1 1 = 0
(26)
0.
(w- wi) rdde 0:
(27)
plug in these results and obtain:
1 modell 112 v(le + di (-nudde) 2m
sup
p.v20
st:
1 + v ==
97 [ 1 + vl. nu ld ld 11)
sup
ve 0,
"1 {-2 |d + vla} vE
sup
(28)
This is a one-dimensional quadratic problem in v. It can be solved in closed-form by finding the global maximum of the quadratic objective, and projecting the solution [0, 1]. We have:
0: ll 1 1
(29)
dv
Since d, * O and 17 * O, this gives the optimal solution:
min max
le
0 .1]
min
(30)
< 2
1/ du
since le, 17, |1 2 0. Plugging this back in the KKT conditions, we obtain that the solution w of the primal prohlem be written as:
Wr+1 W. ryde,
4
w. mimin
de,
1 d/ 1|
Exx (w.)
(31)
minn
1/ Vl, (wa)]l3 1/ Vlz, (we).
Ls (w:) - BB
min
Viz, (w.)] 12. Ver (we).
D.3 THEOREM 2
Theorem 2. [Convex and Lipschitz] We assume that is a convex set, and that for every z Z. lz is convex and C- C-Lisschitz. Let be a uniform lower bound on (P) and w. be a solution of P Further suppose that w, is an E-interpolation for P B). Then ALI-G applied to f satisfies:
T
C +1) + (
Wo w- +8
We
- - S.
(10)
T+1
VT
1=
Proof:
We consider the update time f, which we condition the draw of 2, E Z:
|[w41 w.ll"
19

---

Under review as a conference paper at ICLR 2020
[[a[(:: 7t Ves (we)) w.ll?
|/w, "/s Vlz, (w.) w.ll (Ila projection)
||w, w.ll 27,, Vl., (w:))
"(w (w.)-w.) + Vé (w:)]l²
||w: 22 (we) "(wr (ww- w.) E- (.)
7t Vis (we) ||2 VV (we)]l
(definition of 7(e)
w. w.ll - V2,, (We) (wi-w.) + t, (w.)) B |e (w.))l
V
Vi. (we)
(because f,, (w:) B 2 and 0 0)
$ l|w, w.ll 27 (lz, (w.) Ex (w.)) (e (w,) - B) (convexity of Exc)
l|w, - w.ll - 7e (fz, (we) - E2 (w.)) - (w.) -B)
||w: w.ll? |V w3]] (L,, (w.) (W:, - L2, (w.))
(Cz, (w:)
B) (es, (w.) - B) (definition of 7t))
= ||wl - w-11? 1[Ve, (w:)]l2 + 8 (les. (w:) E2, (w..)) (we) - L2 (w.))
+ (w., (f,, (w:) - L2, (w.)) (La, (w.) (w. () (w.) B)
-(e,, (b,, (w.) ( (B) B)
(we use twice Lx (w.) - B L2 (we) - Lz. (w.) + Lz, (w.) )- B3
-l/w. w.ll" le, (w.)l12 + (lc. Coo (w.))² (l2, (W,) - -B)*)
(middle terms cancel out)
||w, w-1l (wee) Cz (..,w.. (w-)) )}²
(Es, (w.) - -B)
[ez (F +88 8
Vi (w:) w:)]] )1
< |w, w-ll (Lz, (w.)
La (w.)))
(Lz, (w.) B)²
(0 S VV.,, (we)l $c)
5
< (: w.ll? (Lz, (W,) lale(wWw) (w.))²
(definition of E)
(32)
C 0
5
re-write this inequality as:
( +1) +1)
(we) - Lz, (w.)) 1)² S
+ (C² + 6) (Ilw. w.ll? (w41-w..19))
(33)
We can now use the Cauchy-Schwarzz inequality to bound the over the iterations:
T
(T 1)
Σ (Cz((w.) - Lee (w.))² 2
Σ
la (w.) - Lea (w.))
(34)
Therefore we can write:
T
2
Σ (wee) - (vr(w.))
< (T 1) Σ (la (w.)
-w,
1m/
(35)
C
< (1'+1)²
+1]
+ + + 1) (C² +6) (1(wo - -w.12- -||wr4+ ww.l.).
8
C
S ST+1)22
8 +1
+(T (C² 6) ||wo -w.l?
20

---

Under review as a conference paper at ICLR 2020
which yields:
2. (we) - l2 (w.) S (T (T+1)
C2 ( + (T +6) lww w.ll?
(36)
C² 8 < E(T+
+1+ (T+ +8)
We take the expectation the Z+:
T -.
C 8 -1 IT +6) wo w.1l.
(37)
1=
Dividing by + 1 and exploiting convexity of f. we finally get:
1
Σ
We
-
f(w.) - (convexity of f)
T+1
T+ t=0
t=0
(38)
C $ Σ
(C² +6) || w..l?
1
T+
D.4 THEOREM
Theorem 3. We assume that X' is convex set, and that for every E 2, lg is convex and C-Lipschitz. Let w. be an E-interpolation for (()), B). We further assume that 1) > 3. Then if we apply ALI-G with maximal learning-rate -rate n to have:
T
WW w.
8
(02 8)1 wo - w.ll2
C
Wt t=
- S
+
+
+ 1.
T
(1 IT
8(n - ))
T 1+1
(11)
Proof:
We consider the update time t, which we condition on the draw of 2t E
| 1l
[[[[: 7o Ve. - 1=
< |w: Vl. (wi) wwll? (Il projection)
|[w: w.112 - 27 Ve=, (w:) w.) + 70 VV.., (w.)
Lx, (w.) -B
|/w: w.11? 27t Vl., (w.) (ww.)((w.. (w. w.) + 70 Vil, (w. 12 +
|ee, (w:))l?
(because 76 5 Lx, (w:)
Ve., (wo) +
Lx (w.) (ow))-1
IW: w-11 2%t Vl., (w:) (w, -w. + 7t-
Vlz, )l
VVl, (w.))
(because E11 (w.) 2 0 and 5 522 0)
< I: w.11 27, (w.) (w.(w)) + (k (wi) - B) (convexity Exr)
|W: w.ll" (f,, (w:) ls, (w.)) )- + (L2, (W.) - la (w.)) 712,, (W.) -BB -B)
|w:
w.11? (e., (w:) (w.)) 76 (k2, (w.) B)
(39)
Lx (we)- or (ws)))
We now consider different cases, according to the value that takes:
21

---

Under review as a conference paper at ICLR 2020
First, suppose that 7 11 (wx)l Then we can follow the proof of Theorem 2 to obtain:
Ex (we)
|i+1 w.ll l/w, w.ll (Lze (we) Lz (w.))²
e²
(40)
+8
5
Now suppose "ye = 1) and Lx (we) Loe (w-) S.. We can use 74 -
[7 (welll to write:
2x (we)
W w.ll* 1 < l|w, w.ll (e (We) E22 (w.)) + +rc(ls. (w.) B), 82. (Wa) ) - B
$ || - w.1l || V2 (w:)ll2 + (e (w.)) (w.().))
(41)
(w.) B
(Lz, (w.) - B),
(w:))ll) + 0
where the last inequality has used S [iV (we [ lz. (we) Pze (w.) S 0 and (w.)
Cz. (we)-B
B 0. Therefore are exactly in the same situation as the first case (where used yo Fey (we)-B
E, (wo))
). and thus have again:
| ww. S ||wc w.ll2 (Ls, (we) lze (w.)))
8²
(42)
C +
5
Now suppose that 7/- 17 and Es. (w:) Lz (w.) 2 0. The inequality 39 gives:
| wl
< w. -
-w.l w.11 - ((( - l2, (w.)) + (e(e,, - B), - B), (7: = 1))
= w: w.11? ((2,, (wi) - Ls, (w.)) +
< ||:: - w.ll" Nl,,, (wi) - L2, (w.)) + 755 (definition of E, "/t 2 0)
Es2 (w:)
< ||w, w.1l² -
- L2, (w.)) + |V,, (w, )1 +
Pzz (w:)
(because 74 - 1Vl2, (w.)]l² + 8. e 0)
(43)
- n(2,, (w.) - (w.)) + Ex (w.)) -B (lVV2, (wo))l 2 0)
< ||w: - w.112 -w.l"
(w.) L2, (W.) + la (w.) -B
||w- w.11? (/(,, (w.) 4,, (w.))
6
- l2, (w.)) + Lz (w.) -s.( +
< I|: - w.ll - (/2,, (w:)
(hecause Eze (w.) B BBSa) ()
-l]w--w.ll - w.ll (1)
8 5
(Le, (w.)) - Lx (w.)) + 6²
=
We now introduce Ir and Jr as follows:
Ir 2 (1 (O....,)) : 1 and Ls, (we) - (v. 2 0}
(44)
Jr + (0, Ir
Then, by combining inequalities (40)
42 and (43
and using telescopic sum, we obtain:
(L., (w:) - Lx, (w.)))
+ + 2
Wr+1 s.wll v..11 |/ w.ll 2 + Σ
1EJT
(45)
Σ (-(1- 3) (W:)) - (w.(w + 52)
1ETT
22

---

Under review as a conference paper at ICLR 2020
Using WT+1
w-ll2
obtain:
o²
Σ (1x, Eze (w.))²
(17 77-8)
Σ 1EZT
(es, (es, (we) (2. woo w.w.--..l++0 +
TEJT
(46)
In particular, the inequality 44 gives that:
(1
(wi) - ls (w.)) S || - -w.1l + (T+++)))))))) 1)
(47)
8
Furthermore, for every E Tr, we have (fz((w)) -1a) (w.)) 2 0, which yiclds (1 5)
Σ (1,,
1E2T
La, (w.)) )) 2 since > Thus the incquality (46) also gives:
(w.) fz, (w.))² S llwo w.1l2+ (T (T+11) 1)
(48)
C 6
IEJT
Using the Cauchy-Schwarc inequality, can further write:
2
Σ EEJT
Eze (we) L2e (w.)) s 1JTT Σ
(Ez, (w:) L2e (w.)))
(49)
KEJT
Therefore we have:
Σ TEJT
la (wi) - (w.)) S
[Tl Σ (C,,(Wi) - (w.())))
tEJr
(50)
|Trl[C2 -8)
w. (100
We can now put together inequalities 47 and 49
by writing:
L, (w.) (w.)
0=0
la (wi) lx (w.)= + Σ
lx (w:) (v.(w.)
IT
8EJT
||wo w.ll + 11)
||rr((C2 +0)
w. (1N 2
1)
(Iwo- w.l ( (T+ +88 (lww -. ww. (10
17 1
(51)
Dividing by T' + 1 and taking the expectation, we obtain:
Wz
fo T+1 1=0
S(we) S., (f is convex)
T
1=
|wo w.ll?
6²
(02 -0)+0) |/Wo w.
w.l
$
+
+ +V
+
(1 - (T +1)
8(n 5)
T 1
8
Wo w.ll?
2a
2Ca 8) [wo -w. w.
+
(T (T++) +1
8(11 3
T ++1
C
+ +EV 8 +1.
(52)
23

---

Under review as a conference paper at ICLR 2020
D.5 THEOREM
Theorem 4. We assume that X' is a convex set, and that for every E 2, & is convex and C-Lipschitz. Let w, be e-interpolation for (). Then we apply ALI-G with maximal learning- of
to S. we have:
Wo w.ll f.
(Ca + 8) o)llwo w.ll? + +NEV C2+ + (12)
f
Σ Wt
+
T
n(T +
T+1
Proof:
We consider the update at time t, which we condition on the draw of 21 E Z. We re-use the inequality from the proof of Theorem 3
39
|| w. & || w.ll? (w()).(w.) Le, (w.)) + 7i(E2, (w.) (w.)- - B)
(53)
We consider again different cases, according the value of 7 and the sign of Ex (ws) lzs (w.).
Suppose that Lx (we) - lea (w.) S O. Then the inequality 53 gives:
w w.1l
W w. 112 - (e,s, (We) - (w.(). + Yele,, (w.) - B),
|w w.ll -1((e, (we) (w.(w.) + +7 (e..).W..) B),
(54)
(because $ 1/, 2s, (we) lx, (w.) $
| w. 11 - (f,,, (w.) - lx, (w.)) + twe,
(definition of E, yv 2 0)
WW w. - (n1(, (we) (w-)) + ne, (71 Sn, 0)
Now suppose (x,(wi) - Lx, (w.) 2 and "/c = 1). Then the inequality
53 gives:
||+1 w.ll l|w, w. 11² - (e,,, (wz) l2, (w.)) + (el2, (w.) B),
||w, w.ll 112 n/(,,, (w.) (w.)) (w.) B), (7 = 7) (55)
|w, w.ll" in((,, (w.) (w.)) ne, (definition of a, 0)
Finally, suppose that (w:)) - lu, (w.) 2 0 and 70 = (w()) gives:
(ws)) Then the inequality 53
||i++
w-11
|ww w 2|
(x(2x((w)) L2, (w.)) + (w.)) B);
S || w. 11
(es, (W:)
Es, (w.)) + ([(2,.(.) B), (7e S m.. (w.) - B 0)
l!w; w. 11
(ex, (w.)
lz (w.)) + mE, (definition E. 2 0)
||we w.ll
Lx (w.)
B
+ 8 (f2, (w.) - (w.)) + nE, (7)
L. (w.) -
12, (w.
)l?
| (w:)l +
(Le, (w.)
L,, (w.))²
||we w=1l
mj. (w:) B 2 Le (we()) L2 (w.) 20)
1V.. (we)]l +
(Ez, (w:)
le, (w,))²
1|w wlll
+ ne
(w:)) S C3)
C +
(56)
We now introduce Ir and Jr as follows:
Es e,, (Wr) - B
and Es, (w.) (. (w.) 2 20
Tr ② t E (O...,T) T).,,
: = Ve, (w:))l² 2
(57)
Iy (0.... T3 Ir
24

---

Under review as a conference paper at ICLR 2020
Then, combining inequalities (54 (55 and (56).
and using telescopic sum, obtain:
(62. (w:) - E2e (w.))
WT+1 w. 112 - || Ww -.....l w.1122 +
Σ
+
+2
8EJT
(58)
Σ
(-n(ea, (We)) - (w.))
tEIr
Using | WT+1 w-112 2 we obtain:
E
(w:) L2 (w.))² +1
Σ (ws,(Ws) L2 (w,()) Wo w.1l + (T + 1)ne (59)
Ca 4
1ETT
TETT
We now take the expectation and obtain:
Σ E [(e,, (w.) (w.))) +n (s(w))
- f.) [[wo w. (I' 1)ne (60)
C +
LEJT
LETT
Since E[U]² s E(U2) for any real-valued random variable, we can write:
E (s(we) f-)² +
Σ (((m)) f4) s l| w. + (T 1)me
(61)
1ETT
TE
Since each f(w,) 2 0, the inequality
(61 gives that:
n Σ (S(w.) f.) & l[wo w.ll + +(T (I'+1) 1)ne,
(62)
and:
( S l|wo w.11? (T+ 1)ye.
(63)
C +
tE.JT Using the Cauchy-Schwarz Schwarz inequality, can further write:
Σ f(wi) ((wi)-
-5o
S |JT Σ (f(w.) f.)..
(64)
rEJT
tEJr
Therefore we have:
Σ f(wi) - S-5 |Jr] Σ (f(w.) - f-)2,
16JT
lEJT
(65)
VIJr((C2 +8) Wo w.l. + (T+ 1)mE).
We can now put together inequalities 62 and 65 by writing:
f(w:)- S.
f(wi) - fa+ Σ f(we) f.
1E.J
(66)
< (llwo- w.ll2 + (T + 1)mE)
(I - w.ll+ (T 1)mE)
(l/wo- w.|l (T 1)ms) +)
()(C +)) (/wo w.l2 2 + (T + 1)mE)
25

---

Under review as a conference paper at ICLR 2020
Dividing by T obtain:
Σ w.
fa S
f(w:)= - for (f is convex)
P+1
| w.ll
[wo w.ll2
+e+ V (C*+
+ me
(67)
n(I' +1)
T+
Iwo w-ll?
10 + +P)+llloo - w.ll
+
+ mEE C²
(( + 1)
T+1
D.6 THEOREM
Lemma 1. Let E 2. Assume that &g is convex, B-smooth and is lower-bounded on RP by B E IR.
Then we have:
V & (w) - B 2 28 [W)(1)]
(68)
Proof: Let R and suppose that & reaches its infimum at (R U (-oo, +
First, let consider the case w R.. Then by Lemma 3.5 of Bubeck 2015), we have:
E. (w) (w) < Vl.
w) 2.3 VV (w) Ves(w)]l
(69)
23 [e2(w)]1 (V)=(w) 0).
Therefore can write:
(w) B 2 (w())
(w)
28 [W)
(70)
Now let us assume that w & R2_ Then we can construct sequence (We) E (RP) that converges to Since &g and Vl, are continuous functions (they respectively convex and smooth), we have:
lim Eg (We) = inf E..
k--00
(71)
lim
Vl, (w,,) 0.
Therefore the previous case gives the wanted result by using W, in place of w and then taking the limit DC.
Lemma 2. Let E 2. Assume that Eg is convex, B-smooth and is lower-bounded on TRP by B E IR.
Then we have:
(w(w)= B 1
8
VWERD.
(72)
Vl. w 2 +
23
(.3((2( - B))
Proof:
Let R.P We apply Lemma and write successively:
(w) B 2
(w)
(Lemma
[Vl 2 +0 28((s(w) - B) +
((w) B
28((,(w) B + 23
(73)
1
23
28
28(6= (w)
B +
(8 >
2
4.84(s( B)
26

---

Under review as a conference paper at ICLR 2020
Theorem 5. [Convex and Smooth] We assume that X' is convex set, and that for every 2, la is
convex and 5 smooohhh Let be a uniform lower bound on (P) and w. be a solution of P.. Further suppose that w. is E-interpolation for (PP) B). and that à >> 23s. Then A applied to satisfies:
T We - -.
8
28
Wo W. 11
+
(13)
T+
3(1
28c
1
2
T + 1
Proof:
We consider the update at time t, which we condition on the draw of 2 E Z:
|we+1 w-ll
[[s[W: - 76 V6 (w:)) - w.ll
S W: V.V... - ww.l? (Lla projection)
[: w-ll² - 27y (We. ( (w. w.) + 78 || Vl=, (we()))))
Es, (we) B
||w: w.11? - -2y, Ves. ((w. 1o--ww. w.) ) + 7t
Vi.. (we))? 2 + | (w:)ll
(definition of 7r))
272 (we)
|w: w. 27 Vl,, (w:) ( (W: (ww--.)-- (y.)+ 72
(w:))l
|2 (w.)]l
(because L, (w.) 2 and 82 0)
|W: w=112 (f2, (W₂) f,2 (w.)) + (e B)) (convexity of (xx)
[w: w.11? - (2, (w.) (w.)) )) + 71 (Ez, (wi) Lx, (w.)) (w.) B)
I/: w.ll" (f2, (w:) - (w.)) (L2, (w.) -B)
(74)
We now lower bound (x(22 2z (w.)) and upper bound 7/ (f., (w.) B) individually.
We begin with re(Es, (w:) Ez2 (w.)). )). for which we distinguish two cases according to its sign:
Suppose (Lz, (wx,(w)) - Ex2 (w.)) 2 0. Then we can write:
2e(2, (w.) - L2, (w.))
Ls (W.) - B Vlze (2
(Le, (w.) lx (w.)),
(definition 7v))
1
(le, (w.) Leo (w.))
(Lemma 2 (Wi,( - Lx (w.)) 2 0)
23 4B32(z(ww:) - B))
1
lu (w:) - (w.))
(ls, (w:) Ez (w.))
23
4,32
(Lz, (ws) B)
2
(cn, (l..(w)) (W.) lc,((w))
(L., 2 B. (Lee (W:) Le. 2 0)
23
4,3a
(75)
27

---

Under review as a conference paper at ICLR 2020
Now suppose (fz, (w:)) - (w.()))) & O, and let us show that the same result holds. We have:
Lae (Wa)
VE (w:)ll
Lze (W.)
((62, (w,)) L22 (w.)) s 0)
Vez (we)ll² +
(definition of E)
(76)
Ve,, (w:)ll2
8
(/V,,, (w.)ll 2 0)
8
1
$
(8 2 23c)
23
Therefore have:
7ele,, (w.) L2e (w-))
1
2 (Le (we)) - -2,,
(W:) (w.)) S
28
(77)
1
6
2 (1., (we) - lze (w.))
(6 2 0)
23
1
In conclusion, regardless of the sign, it always holds true that:
8
(w:)) (w.)) 2 2/ (E2, (W:)) L2, (w.))
(78)
1.2
We now upper bound ye(Les (W.)) B):
(Ez, (we) (L2, (w.) B))
(el2, (w.) - B)
Vl.. (wr)]l 2 + (definition of 7))
(Ee, (We) (lae (w.) B)
VL,,, (wx)ll 0)
8
(79)
(Lex (We) l2 (w.) +ee
(definition of twice)
((ez, (w.) - E2, (w.)) +
Putting inequalities 74
78) and 79
together, we obtain:
1
8
8² -owis-eaa Ca (w.))
[We+1 w.ll < |wi-w. w. 2B (e (wr) - Ez, (w.))
(ws)
5. (80)
482
Therefore we have:
1
(ws) - (w.(w)))
W: w.ll 1| -i:h---wwl? w.ll? (81)
2/3 8
4,32
By summing over and taking the expectation over the ze, we obtain:
28g
Σ
T
((wi)) f(w.) + 4.822
S || Wo //Woow.l w. - [|| w.]]]] S [[ w. 112
2,38
1,526
1=0
(82)
28

---

Under review as a conference paper at ICLR 2020
By assumption, have that 8 23c obtain:
Dividing by T + 1 and using the convexity of finally
T
T
Σ
Wt
1.
Σ (we) f.
(convexity of f):
T
T+1 1=0
t=
2,38
+ c.
2,30
Wo w.
8-2
4
2,55
T
8² E
2,6
Wo
w.ll" 11
(83)
23(6 23E
23c
T +
84
230
We W. |
23- 0)
3(B 288)
8
2,6
T+1
23
Wo w. 1
28c 3(1
1
28c 5
T
8
D.7 THEOREM 6
Theorem 6. We assume that X is convex set, and that for every 2, Egy is convex and B-smooth. Let w. be an s-interpolation for (P)). B), and suppose that > 28c. Further assume that r Z 2Ø" Then if we apply ALI-G with maximal learning-rate of n to J. we have:
T
6
233
Wo
Wx
- f+
+
(14)
T+1
3(1
232
1
28
T ++1 1
1=0
Proof:
By using the fact that Yo 5 (74 is still valid:
Rsy (we)-B V (wi)l++0
rather than 7/c
Esy (we)-B
that the inequality
1/7 (will=44
|| w. S l|w; wall? yo (lz.(1.))) (w.) Lee (w.)) + 71 (1 (w.) ) B)
(84)
As previously, we lower bound 7/e (fzz (we) Ezz (w.)) and upper bound ne (Pos (w.)
B)) individually.
We begin with to (L,, (w.) Lz (w.)). We remark that either ?
Aee (w I[ (wi3
Suppose T [wo)]]= and Ex, (w.) L., (w.)) 2 0. Then we are in the same condition as in
Es (we)-R
Theorem 5 and thus the inequality (88 holds true:
1 23 (We.) La (w.)) 4,32
Vele, (w.) Cz, (w.)) Z
(85)
Now suppose 7t = 1) and lx,, (w.) Ex (w.) 2 0. Then we have:
(x(,, (w.s) - Lx, (w.))
(l, (w.) L,, (w.))
8
n (w.) 22. (w.(w)))
4.32
8
2 23
(Rz, (w.) - 42, (w.))
1,32
(bocause 17 2,3 lz (w.) E2, (w.) ) 2
(86)
29

---

Under review as a conference paper at ICLR 2020
Ex (wr) Now suppose &x, (we) - l2, (w.) S By using " S
Fsz (we)
instead
[ P+=
([ (we)l we can see that the incquality 76 is still valid, which gives:
1
- 2/3
(87)
We now use Ex (w.) Ez, (w.) & to write:
To (42, (wa) Eze (w.))
(fze (ws) 2. (w.))
(Wx) b2 (w.) 0)
28
(88)
6
(fzz (ws) - L2, (w.))
23
482
In conclusion, in all cases, it holds true that:
1
8
(wa.)(Ww)) Le. (w.)) 2
2B (Lz, (w:)) L2e (w.))
(89)
4
fe, (w:)-n By using 7/ [ can remark that the incquality 79h holds true and gives:
(((zz((..) B. - 7 ((2z( - los (w.))
(90)
We now put together inequalities (84) and (00)
|| w.ll < || w.ll"
1
(Es. (we)
Lao (w.)) +
5
+ E
((f.. (Wi) - (w.)
g²
2,3
4,52
5
8
(lz, (wo) (w.)) + 6 e²
= |we wl
233
8)
1,32
(91)
This is exactly the same result as in the inequality 81 from the proof of Theorem the proof of Theorem follows and obtain the desired result.
Therefore the rest of
D.8 THEOREM
Theorem 7. We assumee that X' is convex set, and that for every E Z, ly is convex and B-smooth. Let w. be an e-interpolation for ( ((P). B), and suppose that 8 > 25s. Further assume that n S 20 Then if we apply ALI-G with a maximal learning-rai rate of 1 to f. we have:
T
Ww w.
f
Σ
We
- fo -
23 + E.
(15)
T+1
(T + 1)
Proof:
By using the fact that S
TT (w:) rather than
Rx [we]-B
T[V (w4) can see that the inequality
L2, (we)
74 is still valid:
[|e+ w. S || w.ll (x(6,, (w:) Lz, (w.)) + (k (w.) )) B)
(92)
As previously, lower bound (Lz, (we) lx (w.)) and upper bound 7 (C2, (w.) B) individually.
We begin with re(E,, (w:) (w.)). We remark that either ?/
Lxy (we) (w
or 7/2
30

---

Under review as a conference paper at ICLR 2020
Suppose "/t
Exy (We)
and le, (we) - Exe (W.) ) 2
First we write:
17 (welll++5
(We)
(wx,) 0
(wes - B 2/
29
1R (we)
122 +
21 (we) )12
+
[Re,, (weill
2/1
+ 27
8
1
(Lemma)
(93)
[| (w.)ll²
+
29
1| (we) 12 +
1
8
2/3
28
11 (w:)]l²
1
2
(n S 23
2/ | =3)]l3+d
Since E,, (w.) 2= (w.) 2 0. this yields:
1
7cles (wi) - L2, (w.)) 2 23 [le,, (w:)) )1 2+6
(Rs, (we) - Ex (w.))
La (we) -l, (w.)
= 77(2, (we) - l1 (w.))
(94)
2/3 ||2z (w+))l +
6 Lz (we)
2 (l2, (we) - l22 (w.))
(6,, (w.) 2 B)
2/3 [1 (w.)]
+
lo. (n and 7 1). then necessarily 1Wt,
Fez (w,))
We now notice that since 7 This gives:
TV [w S m..
176
(Ws) (w.)) (w., Les (w.))
(95)
23
Now suppose 7 = 1) and lx (we) - (. 2 0. Then we have:
(x(e, la, (w.)) = :w(),((.)) Ex, (w.))
176
2 nl2,, (w:) (vc(W.)) 23'
(96)
Now suppose Ex (w.) - L,, (w.) S Since 7s S v/ by definition, we that:
Nt. (Ez, (Ws) - l2 (w.)) (lz,(w:)) L2, (w.)) (l2,, - l..(w.))
(w.) Cz (w.) S 0)
178
(97)
2,8"
In conclusion, in cases, it holds true that:
1/6
Ye(E2, (We) (w.)) 2 n/(21 (w.))
(98)
We upper bound (f,, (w.) B) follows:
(k2, (w.) - B) S (l2, (w.) - B)
(Fx, 2 B)
(99)
I me (definition of E)
combine inequalities 92 and 99 and obtain:
w. 17(E, (w.) - lo. (w.)) + 118
W w. Iw:
233 me.
(100)
By taking the expectation and using a telescopic sum, we obtain:
176 0 |WT+ w.ll < |wo w.l ((f(ww)) ff)
2, M78
(101)
31

---

Under review as a conference paper at ICLR 2020
Re-arranging and using the convexity of f, we finally obtain:
Σ
We
Wo
w.ll
+ E.
(102)
T+
7(
1)
2/
D.9 THEOREM g
Lemma 3. For any a, E IR,,, we have that:
1 ||a bll2 2
||||2 + 108
(103)
Proof: This is simple application of the parallelogram law, but we give the proof here for completeness.
||a||2 ||bl| 2 Illa-
b11 ||a| ||b|| - |all*
|bbl + T
1 ||all
1 _ |1bb T
2
1
l|a - bbll
2
2
Lemma 4. Let z 2. Assume that lg is a-sttronly convex and is lower-bounded on I2 by B E IR
such that inf l B S s. In addition, suppose thut 8 2 20x.. Then we have:
(w)
B
YWER" R.
S
(104)
[V
(w)l +8
20
Proof:
Let I2" and suppose that ε, reaches its minimum E Re (this minimum exists because of strong convexity). By definition of strong convexity, we have that:
Vw EWERE E RR, (w) 2 & (w) + Vee(w) (w w) + - fl w|l
(105)
minimize the right hand-side over w. which gives:
YW RR, la (w) (w) (w) (w w) + _ || w|| 2 (w() 2a [IV( (106)
Thus by choosing w w and re-ordering, we obtain the following result (a.k.a. the Polyak-Lojasiewicz inequality):
8 (w( lg (w) S 2a
[V
(107)
Therefore we can write:
(w( I
(ww - Ex (w))
+
1.4 [W) (w)) 12 + IVe. (w) [w] +
<
(108)
VVL (w)l 2
[V 2 +
20 x +
1
We introduce the function e : + +
and we compute its derivative:
(x + 6)
(x)x)
20
(x +0)
(109)
Zn
2 0. (8 2 20s)
(x + 6)
Therefore vi is monotonically increasing, As result, we have:
V R* (xx) & lim b(x) 1
(110)
20000
2a
32

---

Under review as a conference paper at ICLR 2020
Therefore have that:
Ve. (w))l Ve, ( +8 = (IV()sw)11)) S 2a
(111)
which concludes the proof.
Theorem 8. /Strongly Convex and Smooth| We assume that X a convex set, and that for every
E Z, le is a-strongly convex and 3-smooth. Let be a uniform lower bound (P) and w. be solution of (P). Further suppose that w, is an E-interpolation for (P) B), and that à > 28c. Then ALI-G applied to f satisfies:
aT
28 +
1100
82 a²
f(WT+1) - J+ S Bexp
[wo
w.
+
e.
(16)
83
In other words, f approximately converges fa at rate of O(exp(-aT(88)
Proof:
We condition the update 2, drawn random. The beginning of the proof is identical to that of Theorem
(and in particular requires >> 2,z).. In addition, we remark that >> 28 2 20xe, because always
holds true that B 2 a. Combining incqualities (74) and (78). we obtain:
|| | w-1l & ||we- w-1l 2/8 (e., (We) Lz. (w-)) +
+ 7o (l2, (w-) - B),
1,32
5
lw w. 11.
(2,, (we) E2e (w.))
+ ne
(definition of E)
2B
4,32
5
Iw, w.ll?
(Lz, (w,)
lz2 (w.)) +
(Lemma
(112)
28
1,32
2a
Let w (5c) be the minimizer of Es, on its unconstrained domain R" (its existence is guaranteed by the strong convexity property). Then we exploit strong convexity to lower bound the progress made:
Ez (w.))) - Cx, (w.) = Es, (w:) - Exc ( (2)) - L2, (w.) ) Ez2 (w()))) 2((2, - Ex (w((()))
2 l. (w:) Lz, (w (2))) - (w.) Lzo (w (a)))) 2(fex - B)
(because L,, (w (w1)))) 2 B)
831 (W:) Lx. (w (2)) - L21 (w,) Lz (w (3)) -2 (definition of
|| w w2 + |. w/ (= 2e
(a-strong convexity)
I:: w.| 2 25 (Lemma
(113)
We now combine inequalities (122 and (13)
W w.l 11 s 1
a /w: w. w.1l
6
(114)
833
B
43
20
We use a trivial induction over i and write:
| w.1l 5
Iw
w.ll
83
3
4,2
2a
t-k
Wo
w.1l
Σ
a
85
4
8
h
8
1
WW w.1l
+
83
83
4,3
2a
WD
w. 2
1
E
8
8,8
1
4
2a
82
33

---

Under review as a conference paper at ICLR 2020
α
Wo w.ll
v.112= +
83
(115)
a
4
2ex
In particular, we remark that the right hand-side of the equation is independent on Rc-
Given an arbitrary w R., we now wish relate the distance || - ww 2 the function values ((w)-
Since each & is a-strongly convex and 8-smooth, is f I [e_]. We introduce the minimizer of its unconstrained domain R². Then can write that for any w E IR:
f f(w - fw..)= S f(w) f(w), (f(w) S f(w-)
<V/(w)
(w w)
2 || wwl" if 3-smooth)
8 || wll (Vf(w) 00)
2
S B[[[ w.ll 112 + [|w, -wll²), (Lemma
//[ w.ll 28 (f(w.) )) - f(w)), (f a-strongly convex)
28 (f(w.) B), S ((w ) by definition)
//1l w..12+
$ <B1w w. 1 3 (definition of e)
(116)
We combine the results to obtain the final result:
f(W(41) - f(w.) )) S B| W241 w.ll + BE a
89
E
Be
S 8
Wo w.
+
+
+ 2
83
a
18
1/32
2a
88
88
1
|| w.ll
83
48
2a
25
3
82
||w w-1l
+
10
4 a
83
28
82
Bexp
||o w. 1|
10
(117)
83
D.10 THEOREM
Theorem 9. We assume that X is convex set, and that for every Z, & is a-strongly convex and B-smooth. Let w. be an e-interpolation for ((P). B), and suppose that 2ßc. Further assume that n 2 23. Then if we apply ALI-G with a maximal learning-rate of f, we have:
aT
25
f(wr+1) S
wwo w.ll
10 a
(17)
8,3
a²
Proof: Re-using inequalities
84 and
from the proof Theorem we obtain:
|| - 2 w.
w.
(C., (w:) Es, (w.))
4,32 + Y (f., (w.)
B)
(118)
This is exactly the same result as the first line of the inequality 1122 in the proof Theorem g the proof is identical to the one of Theorem g
Then the rest of
D.11 THEOREM T0
Theorem 10. We assume that X is a convex set, and that for every 2 E Z, Eg is a-strongly convex and B-smooth. Let w,, be e-interpolation for B.), and suppose that > 28c. Further assume
34

---

Under review as a conference paper at ICLR 2020
that 17 S 1 23"
Then if we apply ALI-G with maximal learning-ratt of f. we have:
f(wr+1) - f. S exxp (-a4)
ann'
28 14xB
1wo
w. w.ll +
(18)
Proof: Re-using inequalities (92 and (98 from the proof of Theorem
write:
1/6
||w++ w.ll S ||we w.ll? (TZee (Wa) l2 (w.))
(f (w.) B):
2
176
x |/ w.ll? (wes) - Lz, (w.))
+
(% S Sn 0 S e, (w.) - BB S e).
2/3
(119)
Furthermore, the inequality 113 gives:
Ex (W.) - L2, (w.) 2 c
4 Il w.ll 20
(120)
Therefore, we can write:
|ee+1 w.ll² 11 < l|we w.ll2 112
av/
l/w, w-ll
11
+ 37e,
4
2,3
(121)
= (11 001 l/we w.1l? + 176
3mE
23
Then trivial induction gives that:
T Σ
WT+1 w.ll
1 (1-
anl
l/wo-
w.l +
+ 3mE
4
2/3
an
T || w.11
n76
3nE
(1
07
4
23
(122)
-1
am)
T
I/Wo
w.l +
176
3nje
4
23
07
om
||wo-
w. +
28
+
12g
4
039
We now re-use the incquality (16 to write:
w.11 20e
f(wT+1) - S. s B WT+1
a
- B ( (1-
an T
4 |wo w=
28 + 14s3
(123)
-aniT
l/wo w.l 2 25
14g8
< exp
35

---

Under review as a conference paper at ICLR 2020
E
ADDITIONAL EXPERIMENTAL DETAILS
E.
STANDARD DEVIATION OF CIFAR RESULTS
Task
Optimizer
Avg
Std
DN10
ADAMW
92.6
0.08
DNIO
ALIG
95.0
0.16
DNIO
AMSGRAD
91.7
0.25
DNTO
DFW
94.6
0.22
DNIO
L4ADAM
90.8
0.09
DNIO
L4MOM
91.9
0.17
DNIO
SGD
95.1
0.21
DN10
YOGI
92.1
0.38
DN100
ADAMW
69.5
0.54
DN100
ALIG
76.3
0.14
DN100
AMSGRAD
69.4
0.41
DN100
DFW
73.2
0.29
DN100
L4ADAM
60.5
0.64
DN100
L4MOM
62.6
1.98
DN100
SGD
76.3
0.22
DN100
YOGI
69.6
0.34
WRNI0
ADAMW
92.1
0.34
WRNI0
ALIG
95.2
0.09
WRNI0
AMSGRAD
90.8
0.31
WRNI0
DFW
94.2
0.19
WRNI0
L4ADAM
90.5
0.09
WRNI0
L4MOM
91.6
0.24
WRNI0
SGD
95.3
0.31
WRNI0
YOGI
91.2
0.27
WRN100
ADAMW
69.6
0.51
WRN100
ALIG
75.8
0.29
WRN100
AMSGRAD
68.7
0.70
WRN100
DFW
76.0
0.24
WRN100
L4ADAM
61.7
2.17
WRN1OM
L4MOM
61.4
0.86
WRN100
SGD
77.8
0.13
WRN100
YOGI
68.7
0.47
Table 4: Test Accuracy (%) CIFAR including standard deviations. Each experiment run three times.
36


Reviews:
[{"review_id": "rJg9gcITcB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Thanks for the responses and my concerns seem to be addressed. But since I do not know much about this area, I would like to stick to my initial rating 6.\n==================================================================================================\nThis work designs a new optimization SGD algorithm named ALI-G for deep neural network with interpolation property. \nThis algorithm only has a single hyper-parameter and doesn’t have a decay schedule. The authors provide the convergence guarantees of ALI-G in the stochastic convex setting as well as the experiment results on four tasks.This paper shows state-of-the-art results but I still have have two concerns.\n\nMy main concern is that the performances of other SGD algorithms may be potentially better than the results showed in section 5 because it is not easy to tune the parameter. It would be better if the authors can tune the hyper-parameter more carefully. Take figure 3 as an example. The settings where step size bigger than 1e+1 can hardly shows something, because the step-size is too big for SGD to converge. The settings where step size smaller 1e-2 can also hardly shows something, because the step-size is too small and the experiments only runs 10k steps. It would be better if authors can do more experiments in the settings where step size is from 1e-3 to 1e+0. Moreover, the optimal step size of different optimization algorithms may differ a lot. It would be much more fair if the authors can compare the best performance of different algorithms.\n\nAnother concern is that the authors only give the convergence rate of ALI-G in section 3 but haven’t make any comparisons. For example, it would be better if the authors can show that ALI-G has better convergence result than vanilla SGD without decay schedule.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Syxp4JxAKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new adaptive learning rate method which is tailored to the optimization of deep neural networks. The motivating observation is that over-parameterized DNNs are able to interpolate the training data (i.e. they are able to reach near-zero training error). This enables application of the Polyak update rule to stochastic updates and a simplification by assuming a zero minimal training loss. A number of proofs for convergence in various convex settings are provided, and empirical evaluation on several benchmarks demonstrates (a) ability to optimize complex architectures, (b) performance improvements over, and (c) performance close to manually tuned SGD learning rates.\n\nI vote for accepting this paper. The approach is well-motivated, the method is described clearly and detail, and the experiments support the paper's claims well. What I would still like to see are a few additional details regarding the experimental protocol. In particular, did you train a single or multiple models for each result that is reported? Do different runs start from the exact same weight initialization? What condition was used to stop the training? The results in section 5.2. are all very close to each other, and it would be helpful to have a sense of the variability of the different methods. The graphs in Figure 4 do look like the models did not converge yet.\n\nGenerally, it would be nice to examine the behavior of the method in cases where the neural network is underparameterized or is otherwise unable to effectively interpolate the training data. Does the method lead to divergence in this case, or is it subpar to other methods? I think section 2.2. could benefit from a short motivational introduction; on the first read, I was not clear about the purpose of introducing the Polyak step size as it is not mentioned explicitly in the text leading to it.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJgm9PbTqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses designing and analyzing an optimization algorithm. Like SGD, it maintains a low computational cost per optimization iteration, but unlike SGD, it does not require manually tuning a decay schedule. This work uses the interpolation property (that the empirical loss can be driven to near zero on all samples simultaneously in a neural network) to compute an adaptive learning rate in closed form at each optimization iteration, and results show that this method produces state-of-the-art results among adaptive methods. I can say the paper was very well written and easy to follow along/understand. Prior work seems comprehensive, and the intuitive comparisons to the prior methods were also useful for the reader. \n\nMy current decision is a weak accept, for a well-written paper, thorough results including meaningful baselines and numerous hyperparameter searches, and a seemingly high-impact tool. Some concerns are listed as follows:\n1-\tConvergence was only discussed in the stochastic convex setting, which seems limiting because we rarely deal with convex problems in problems requiring neural networks.\n2-\tRegularization of the weights during the optimization is dealt with by projecting onto the feasible set of weights, but it seems like there are other types of losses that don’t necessarily to go 0. For example, terms in the objective such as entropy seem worrisome.\n3-\tOne detail that I did not fully follow along with is section 3.1. How does Theorem 1 (Regarding convexity) related to the “each training sample can use its own learning rate without harming progress on the other ones” and/or “allow the updates to rely on the stochastic estimate rather than the exact”? \n4-\tUnfortunately, I am not an expert in this particular area, so I’m not confident about the novelty. For example, the difference between L4 and this is stated to be the utilization of the interpolation policy (which just sets f*=0) and the maximal learning rate, and the stated benefit of convergence guarantees in stochastic convex settings seems poor since most problems will not be convex anyway. More generally, it seems like all details of the algorithm came from elsewhere, although the presented synthesis of ideas does have clear benefits.\n\nAfter reading the author response: \n-I'm fine with points 4 and 3. \n-My feelings about 1 are still the same.\n-My comment on 2 wasn't about cross-entopy loss, but rather other types of objectives that people are often interested in optimizing (such as max-ent RL, where we aim for maximizing rewards as well as maximizing entropy of the policy), in which case, it's not clear to me how we could apply this optimizer. \n-My decision stays as a weak accept", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xbXQwnKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new gradient descent methods for training deep neural network which can take the adaptive step size with only one hyper-parameter to tune -- the maximum learning rate -- and achieve comparable results to stochastic gradient descent (SGD) on various tasks and models. In order to achieve that, they develop a stochastic extension of the Polyak step-size for the non-convex setting, namely the adaptive learning-rates for interpolation with gradients (ALI-G), in which the minimal value of the objective loss is set to 0 due to interpolation in neural networks and the learning rates are clipped by a chosen maximal value. The problem is formulated clearly, and the review on the Polyak step-size and related works are well done. Another main contribution of the paper is to provide the convergence guarantees for ALI-G in the convex setting where the objective loss is Lipschitz-continuous (Theorem 1 in the paper). Their theorem also takes into account the error in the estimate of the minimal value of the objective loss. In addition, they derive the connections between  ALI-G and SGD and show that compared to SGD, ALI-G take into consideration that the objective loss is non-negative and set the loss to 0 when it is negative. They perform empirical study to compare their algorithm with other methods including Adagrad, Adam, DFW, L4Adam and SGD on learning a differentiable neural computer, object recognition, and a natural language processing task. Their experimental results show that ALI-G performance is comparable with that of SGD with schedule learning rate.\n\nOverall, this paper could be an interesting contribution. However, some points in the theory and experiments need to be verified. I weakly reject this paper, but given these clarifications in an author response, I would be willing to increase the score. \n\nFor the algorithm and theory, there are some points that need to be verified and further clarification on novelty:\n\n1. When there are regularization such as the weight decay regularization, the minimal objective loss will not be 0. In such cases, Theorem 1 in the paper only guarantees that ALI-G reaches an objective loss less than or equal to a multiple of the estimate error \\epsilon of the true minimal objective loss. It cannot guarantee that the objective loss reached by ALI-G can converge to the true minimall objective loss. Furthermore, when training neural networks with, for example, the weight decay regularization, often times the value of the regularization loss, i.e.  the estimate error \\epsilon, is not small. Therefore, the upper bound given by Theorem 1 is rather loose. \n\n2.  The paper mentions that when no regularization is used, ALI-G and Deep Frank-Wolfe (DFW) are identical algorithms. The difference between the two algorithms are when regularization is used. However, given my concern for Theorem 1 above, the convergence of ALI-G and advantage of ALI-G over DFW in this setting is questionable, and the claim that “ALI-G can handle arbitrary (lower-bounded) loss functions” also needs to be verified. \n\nFor the experiments, the following should be addressed:\n1. In the experiment with the differentiable neural computers, even though ALI-G obtains better performance for a large range of \\eta, its best objective loss is still worse than RMSProp, L4Adam, and L4Mom.\n\n2. Given the merit of Theorem 1 is that the convergence guarantee takes into account the estimate error of the minimal objective loss, an ablation study that compares ALI-G with other methods in the same setting with and without regularization are needed. For example, it would be more convincing if similar results to those in Table 2 or 3 but without regularization are provided and discussed.\n\n3. In Section 5.5, given that ALI-G and DFW are related, why is there no result for DFW in Figure \n4.?\n\n4.  As the paper mentions, AProx algorithm and ALI-G are related, why is there no comparison with AProx in the experiments?\nThings to improve the paper that did not impact the score:\n1. In all experiments, the performance differences between ALI-G and competitive methods are small. Thus, error bars are needed for these results.\n\n2. In Table 3, the gap between SGD and ALI-G can be significantly different on different architectures. For example, in CIFAR-100 experiments, while ALI-G achieves the same result as SGD with the DenseNet, ALI-G’s performance on Wide ResNet is much worse than SGD. Do you have any explanation for this?\n\n3. How is ALI-G compared with the methods proposed in the paper “Stochastic Gradient Descent with Polyak's Learning Rate” (https://arxiv.org/abs/1903.08688)\n\n\nThe following paper also proved the convergence of adaptive gradient methods for nonconvex optimization:\nDongruo Zhou*, Yiqi Tang*, Ziyan Yang*, Yuan Cao, Quanquan Gu. On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization.\n\n-------------------------------------------------------------\nAfter rebuttal:\nI noticed that the authors:\n\n1. did not compare with SGD or Adam with good hyperparameters (https://arxiv.org/abs/1907.08610)\n\n2. did not test on the large scale datasets, e.g., imagenet\n\n3. the proposed algorithm is not as good as SGD on most numerical experiments.\n\nFor the above reasons, I think this paper should be rejected.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper uses the interpolation property to design a new optimization algorithm for deep learning, which computes an adaptive learning-rate in closed form at each iteration. The authors also analyzed the convergence rate of the proposed algorithm in the stochastic convex optimization setting. Experiments on several benchmark neural networks and datasets verify the effectiveness of the proposed algorithm. This is a borderline paper and has been carefully discussed. The main objection of the reviewers include: (1) The interplay between regularization and the interpolation property is not clear; and (2) the proposed algorithm  is no better than SGD in any of the benchmarks except one, where SGD's learning rate is set to be a constant. After the author response, this paper still does not gather sufficient support. So I encourage the authors to improve this paper and resubmit it to future conference.
Decision: Reject