Title: TRAINING NEURAL NETWORKS FOR AND BY INTERPOLATION

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.

1. INTRODUCTION:

Training a deep neural network is a challenging optimization problem: it involves minimizing the average of many high-dimensional non-convex functions. In practice, the main algorithms of choice are Stochastic Gradient Descent (SGD) (Robbins & Monro, 1951) and adaptive gradient methods such as AdaGrad (Duchi et al., 2011) or Adam (Kingma & Ba, 2015) . In recent work, the ability to interpolate -i.e. to achieve near zero loss on all training samples simultaneously -has been used to show convergence of SGD (Ma et al., 2018 , Vaswani et al., 2019a , Zhou et al., 2019) . This property is usually satisfied in supervised deep learning because of the empirical success of over-parameterized 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 a call to a stochastic first-order oracle); and (ii) adaptive learning-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, 2001a; 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, we create a stochastic algorithm that provably converges fast in the convex setting and that obtains state-of-the-art results with neural networks.

Procedurally, ALI-G is close to many existing algorithms, such as Deep Frank-Wolfe (Berrada et al., 2019) , APROX (Asi & Duchi, 2019) and L 4 (Rolinek & Martius, 2018) . And yet uniquely, thanks to its careful design and analysis, ALI-G enables accurate optimization of a wide class of deep neural networks using only a single hyper-parameter 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 it can prove to be a 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 a single hyper-parameter for its learning-rate and does need any decaying schedule. In contrast, the closely related APROX (Asi & Duchi, 2019) and L 4 (Rolinek & Martius, 2018) use respectively two and four hyper-parameters 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-the-art results for ALI-G on learning a 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 a supervised learning task where the model is parameterized by w ∈ R p . Usually, the objective function can be expressed as an expectation over z ∈ Z, a random variable indexing the samples of the training set: f (w) E z∈Z [ z (w)],

(1) where each z is the loss function associated with the sample z. We assume that each z is nonnegative, 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 z, z (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 L 1 or L 2 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 a constraint on the feasible domain: Ω = {w ∈ R p : φ(w) ≤ r} for some value of r. In the deep learning setting, this will allow us 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 L 2 regularization: Ω = w ∈ R p : w 2 2 ≤ r , for which the projection is given by a simple rescaling of w. Finally, note that if we do not wish to use any regularization, we define Ω = R p and the corresponding projection is the identity.

Problem Formulation. The learning task can be expressed as the problem (P) of finding a feasible vector of parameters w ∈ Ω that minimizes f : w ∈ argmin w∈Ω f (w).

(P)

Also note that f refers to the minimum value of f over Ω: f min w∈Ω 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-G draws some fundamental ideas.

Setting. We assume that f is known and we use non-stochastic updates: at each iteration, the full objective f and its derivative are evaluated. We denote by ∇f (w) the first-order derivative of f at w (e.g. ∇f (w) can be a sub-gradient or the gradient). In addition, • is the standard Euclidean norm in R p , and Π Ω (w) is the Euclidean projection of the vector w ∈ R p on the set Ω.

Polyak Step-Size. At time-step t, using the Polyak step-size (Polyak, 1969 , Shor, 1985 , Brännlund, 1995 , Nedić & Bertsekas, 2001a; b) yields the following update:

EQUATION

where we loosely define 0 0 = 0 for simplicity purposes.

w t w w t+1 f Loss function f Linearization at w t Minimum f

Figure 1 : Illustration of the Polyak step-size in 1D. In this case, and further assuming that f = 0, the algorithm coincides with the Newton-Raphson method for finding roots of a function.

Interpretation. It can be shown that w t+1 lies on the intersection between the linearization of f at w t and the horizontal plane z = f (see Figure 1 , more details in Proposition 2 in the supplementary material). Note that since f is the minimum of f , the Polyak step-size γ t is necessarily non-negative.

Limitations. Equation (2) has two major shortcomings that prevent its applicability in a machine learning setting. First, each update requires a full evaluation of f and its derivative. Stochastic extensions have been proposed in Nedić & Bertsekas (2001a; b) , but they still require frequent evaluations of f . This is expensive in the large data setting, and even computationally infeasible when using massive data augmentation. Second, when applying this method to the non-convex setting of deep neural networks, the method sometimes fails to converge.

Therefore we would like to design an extension of the Polyak step-size that (i) is inexpensive to compute in a stochastic setting (e.g. with a 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 to near zero on 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, it computes a stochastic approximation of the learning objective and its derivative (line 3). Second, it computes a step-size decay parameter γ t based on the stochastic information (line 4). Third, it updates the parameters by moving in 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 1 The ALI-G algorithm:

Require: maximal learning-rate η, initial feasible w 0 ∈ Ω, small constant δ > 0 1: t = 0 2: while not converged do 3:

Get zt (w t ), ∇ zt (w t ) with z t drawn i.i.d.

4:

γ t = min z t (wt)

∇ z t (wt) 2 +δ , η 5:

w t+1 = Π Ω (w t -γ t ∇ zt (w t )) 6: t = t + 1 7: end while

Comparison with the Polyak Step-Size. There are three main differences to the update in equation (2). First, each update only uses the loss zt and its derivative rather than the full objective f and its derivative. Second, the learning-rate γ t is clipped to η, the maximal learning-rate hyper-parameter. We emphasize that η remains constant throughout the iterations, therefore it is a single hyper-parameter and does not need a schedule like SGD learning-rate. Third, the minimum f has been replaced by the lower-bound of 0. All these modifications will be justified in the next section.

The ALI-G ∞ Variant. When ALI-G uses no maximal learning-rate, we refer to the algorithm as ALI-G ∞ , since it is equivalent to use an infinite maximal learning-rate. Note that ALI-G ∞ requires no hyper-parameter for its step-size.

3. JUSTIFICATION AND ANALYSIS:



3.1. INTERPOLATION ENABLES INEXPENSIVE STOCHASTIC UPDATES:

By definition, the interpolation setting gives f = 0, which we used in ALI-G to simplify the formula of the learning-rate γ t . More subtly, the interpolation property also allows the updates to rely on the stochastic estimate zt (w t ) rather than the exact but expensive f (w t ). Intuitively, this is possible because in the interpolation setting, each training sample can use its own learning-rate without harming progress on the other ones. Recall that ALI-G ∞ is 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 1 (Convex and Lipschitz). We assume that Ω is a convex set, and that for every z ∈ Z, z is convex and C-Lipschitz. Let w be a solution of (P), and assume that the interpolation property is approximately satisfied: ∀z ∈ Z, z (w ) ≤ ε, for some interpolation tolerance ε ≥ 0. Then ALI-G ∞ applied to f satisfies:

EQUATION

In other words, by assuming interpolation, ALI-G provably converges while requiring only zt (w t ) and ∇ zt (w t ) (stochastic estimation per sample) to compute its learning-rate. In contrast, the Polyak step-size, which does not exploit interpolation, would require f (w t ) and ∇f (w t ) to 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 1, our careful analysis explicitly shows the dependency of the convergence result on the interpolation tolerance ε. It is reassuring to note that convergence is exact when the interpolation property is exactly satisfied (ε = 0).

In the supplementary material, we also establish convergence rates of O(1/T ) for smooth convex functions, and O(exp(-αT /8β)) for α-strongly convex and β-smooth functions. Similar results can be proved when using a maximal learning-rate η: the convergence speed then remains unchanged provided that η is large enough, and it is lowered when η is small. We refer the interested reader to the supplementary for the formal results and their proofs.

3.2. A 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 a maximal learning-rate allows ALI-G to behave like constant step-size SGD in non-convex regions where the Polyak step-size would be over-estimated, and to automatically use the Polyak step-size once reaching a convex basin of convergence.

Importantly, using a maximal learning-rate can be seen as a very natural extension of SGD when using a non-negative loss function:

Proposition 1. [Proximal Interpretation] Suppose that Ω = R p and let δ = 0. We consider the update performed by SGD: w SGD t+1 = w t -η t ∇ zt (w t ); and the update performed by ALI-G: w ALI-G t+1 = w t -γ t ∇ zt (w t ), where γ t = min z t (wt) ∇ z t (wt) 2 +δ , η . Then we have:

EQUATION

w ALI-G t+1 = argmin w∈R p 1 2η ww t 2 + max zt (w t ) + ∇ zt (w t ) (w -w t ), 0 .

(5)

w t =-3 5 w t+1 = 3 5 f : w → w 2 -|w| 3 Linearizations of f

Figure 2 : A simple example where the Polyak step-size oscillates due to nonconvexity. On this problem, ALI-G converges whenever its maximal learning-rate η is lower than 10.

In other words, at each iteration, ALI-G solves a proximal problem in closed form in a similar way to SGD. In both cases, the loss function zt is locally approximated by a first-order Taylor expansion at w t . The difference is that ALI-G also exploits the fact that zt is nonnegative. This allows ALI-G to use a constant value for η in the interpolation setting, while the learning-rate η t of SGD needs to be manually decayed.

It 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 η.

4. RELATED WORK:

Interpolation in Deep Learning. As mentioned in the introduction, recent works have successfully exploited the interpolation assumption to prove convergence of SGD in the context of deep learning (Ma et al., 2018 , Vaswani et al., 2019a , Zhou et al., 2019) . Such works are complementary to ours in the sense that they provide a convergence analysis of an existing algorithm for deep learning.

Adaptive Gradient Methods. Similarly to ALI-G, adaptive gradient methods also rely on tuning a single hyper-parameter, thereby providing a more pragmatic alternative to SGD that needs a specification of the full learning-rate schedule. While the most popular ones are Adagrad (Duchi et al., 2011) , RMSPROP (Tieleman & Hinton, 2012) , Adam (Kingma & Ba, 2015) and AMSGrad (Reddi et al., 2018) , there have been many other variants (Zeiler, 2012 , Orabona & Pál, 2015 , Défossez & Bach, 2017 , Levy, 2017 , Mukkamala & Hein, 2017 , Zheng & Kwok, 2017 , Bernstein et al., 2018 , Chen & Gu, 2018 , Shazeer & Stern, 2018 , Zaheer et al., 2018 , Chen et al., 2019 , Loshchilov & Hutter, 2019 , Luo et al., 2019) . However, as pointed out in Wilson et al. (2017) , adaptive gradient methods tend to give poor generalization in supervised learning. In our experiments, the results provided by ALI-G are significantly better than those obtained by the most popular adaptive gradient methods.

Adaptive Learning-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-rates 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., 2018 , Wu et al., 2018 , Li & Orabona, 2019) , but they have not demonstrated competitiveness against SGD with a well-tuned hand-designed schedule.

L 4 Algorithm. The L 4 algorithm (Rolinek & Martius, 2018 ) also uses a modified version of the Polyak step-size. However, the L 4 algorithm computes an online estimate of f rather than relying on a fixed value. This requires three hyper-parameters, which are in practice sensitive to noise and crucial for empirical convergence of the method. In addition, L 4 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.

Frank-Wolfe Methods. The proximal interpretation in Proposition 1 allows us to draw additional parallels to existing methods. In particular, the formula of the learning-rate γ t may remind the reader of the Frank-Wolfe algorithm (Frank & Wolfe, 1956) in some of its variants (Locatello et al., 2017) , or other dual methods (Lacoste-Julien et al., 2013 , Shalev-Shwartz & Zhang, 2016) . This is because such methods solve in closed form the dual of problem ( 5), and problems in the form of (5) naturally appear in dual coordinate ascent methods (Shalev-Shwartz & Zhang, 2016) .

When no regularization is used, ALI-G and Deep Frank-Wolfe (DFW) (Berrada et al., 2019) are procedurally identical algorithms. This is because in such a 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 (lower-bounded) loss functions, while DFW can only use convex piece-wise linear loss functions; and (ii) as seen previously, ALI-G provides convergence guarantees in 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 ∇ zt (w t ) only, instead of the expensive deterministic gradient ∇f (w t ). However, they still require to evaluate f (w t ), 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.

APROX Algorithm. Asi & Duchi (2019) have recently introduced the APROX algorithm, a 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 us 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 ε ≥ 0 rather than unrealistically assuming the perfect case ε = 0 (that would require infinite weights when using the cross-entropy loss for instance). Fourth, our analysis proves fast convergence in function space rather than iterate space.

5. 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 a differentiable neural computer; 2019), which aims at 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-parameter 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 L 41 . In the PyTorch (Paszke et al., 2017 ) experiments, we use our implementation of L 4 , which we unit-test against the official Tensorflow implementation. In addition, we employ the official implementation of DFW 2 and we re-use their code for the experiments on SNLI and CIFAR. All experiments are performed either on a 12-core CPU (differentiable neural computer) or on a single GPU (SVHN, SNLI, CIFAR).

5.1. DIFFERENTIABLE NEURAL COMPUTERS:

Setting. The Differentiable Neural Computer (DNC) (Graves et al., 2016) is a 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 to repeatedly copy a fixed size string given as 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 DNC3 . We vary the initial learning rate as powers of ten between 10 -4 and 10 4 for each method except for L 4 Adam and L 4 Mom. For L 4 Adam and L 4 Mom, 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, L 4 Adam and L 4 Mom (as recommended by Rolinek & Martius (2018) Learning-Rate (η):

AdaGrad Adam RMSProp SGD SGD w/ Mom 1e+1 9e+0 6e+0 2e+0 3e-3 1e-3 4e-4 6e-4 1e+2 6e-2 3e-4 2e-4 5e-5 3e-4 2e-4 5e+0 1e+2 1e+2 2e-1 7e-5 4e-7 5e-8 2e-7 2e-7 3e-7 7e+0 1e+2 1e+1 9e+0 6e+0 3e+0 7e-2 7e-3 2e-3 5e-4 1e+2 6e+0 2e+0 6e-2 6e-3 2e-3 4e-4 9e-5 5e+0 1e+2 1e-1 3e-1 1e+0 3e+0 1e+1 3e+1 1e+2 1e+3 1e+4 1e+5 1e+6 1e+7

Maximal Learning-Rate (η):

ALI-G 8e-3 2e-3 4e-4 2e-4 6e-5 3e-5 4e-6 5e-7 1e-7 1e-7 4e-8 2e-2 Results. We present the results in Figure 3 . ALI-G provides accurate optimization for any η within [10 -1 , 10 6 ], and is among the best performing methods by reaching an objective function of 4.10 -8 . On this task, RMSProp, L 4 Adam and L 4 Mom also provide accurate and robust optimization. In contrast to ALI-G and the L 4 methods, the most commonly used algorithms such as SGD, SGD with momentum and Adam are very sensitive to their main learning-rate hyper-parameter. Note that the difference between well-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 a total of 598k samples. We train a wide residual network 16-4 following Zagoruyko & Komodakis (2016) .

Method. For SGD, we use the manual schedule for the learning rate of Zagoruyko & Komodakis (2016) . For L 4 Adam and L 4 Mom, we cross-validate the main learning-rate hyper-parameter α 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 a power of 10. The L 2 regularization is cross-validated in {0.0001, 0.0005} for all methods but ALI-G. For ALI-G, the regularization is expressed as a constraint on the L 2 -norm of the parameters, and its maximal value is set to 50. SGD, ALI-G and BPGrad use a Nesterov momentum of 0.9. All methods use a dropout rate of 0.4 and a fixed budget of 160 epochs, following (Zagoruyko & Komodakis, 2016) .

Results. The results are presented in Table 1 . On this relatively easy task, most methods achieve about 98% test accuracy. Despite the cross-validation, L 4 Mom does not converge on this task. Even though SGD benefits from a hand-designed schedule, ALI-G and other adaptive methods obtain close performance to it.

A d a g r a d A d a m A M S G r a d B P G r a d D F W L 4 A d a m L 4 M o m A L I -G S G D S G D †

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 a hand-designed schedule for its learning-rate. In black, adaptive methods, including ALI-G, have a single hyper-parameter for their learning-rate. SGD † refers to 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 a pre-training corpus for transfer learning to many other natural language tasks where labeled data is scarcer (Conneau et al., 2017) -much like ImageNet is used for pre-training in computer vision.

We follow the protocol of Berrada et al. (2019) ; we also re-use their code and results for the baselines.

Method. For L 4 Adam and L 4 Mom, the main hyper-parameter α 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 a hand-designed schedule, where the learning-rate is decreased by 5 when the validation accuracy does not improve. Other methods use adaptive learningrates and do not require such schedule. The value of the main hyper-parameter η is cross-validated as a power of ten for the ALI-G algorithm and for previously reported adaptive methods. Following the implementation by Conneau et al. (2017) , no L 2 regularization is used. The algorithms are evaluated with the Cross-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) . Results. We present the results in Table 2 . ALI-G ∞ is the only method that requires no hyperparameter for its learning-rate. Despite this, and the fact that SGD employs a 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.

Loss A d a g r a d * A d a m * A M S G r a d * B P G r a d * D F W * L 4 A d a m L 4 M o m A L I -G ∞ A L I -G S G D * S G

5.4. WIDE RESIDUAL NETWORKS AND DENSELY CONNECTED NETWORKS ON CIFAR:

Setting. We follow the methodology of Berrada et al. (2019) ; we also re-use their code and we reproduce their results. We test two architectures: a 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 Berrada et al. (2019) , we also provide the performance of L 4 Adam, L 4 Mom, AdamW (Loshchilov & Hutter, 2019) and Yogi (Zaheer et al., 2018) .

Method. All optimization methods employ the cross-entropy loss, except for the DFW algorithm, which is designed to use an SVM loss. For DN and WRN respectively, SGD uses the manual learning rate schedules from Huang et al. (2017) and Zagoruyko & Komodakis (2016) . Following Berrada et al. (2019) , the batch-size is cross-validated in {64, 128, 256} for the DN architecture, and {128, 256, 512} for the WRN architecture. For L 4 Adam and L 4 Mom, the learning-rate hyperparameter α is cross-validated in {0.015, 0.15}. For AMSGrad, AdamW, Yogi, DFW and ALI-G, the learning-rate hyper-parameter η is cross-validated as a power of 10 (in practice η ∈ {0.1, 1} for ALI-G). SGD, DFW and ALI-G use a Nesterov momentum of 0.9. Following Berrada et al. (2019) , for all methods but ALI-G and AdamW, the L 2 regularization is cross-validated in {0.0001, 0.0005} on the WRN architecture, and is set to 0.0001 for the DN architecture. For AdamW, the weight-decay is cross-validated as a power of 10. For ALI-G, L 2 regularization is expressed as a constraint on the 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. ALI-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. In red, SGD benefits from a hand-designed schedule for its learning-rate. In black, adaptive methods, including ALI-G, have a single hyperparameter for their learning-rate. SGD † refers to 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 for ALI-G and SGD).

Data Set Architecture A M S G r a d A d a m W Y o g i D F W L 4 A d a m L 4 M o m A L I -G S G D S G D † CIFAR-

5.5. TRAINING PERFORMANCE:

The experiments have so far focused on testing accuracy (except for the DNC task), because that is 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. In order to have comparable objective functions, the L 2 regularization is deactivated. We do not use dropout. The learning-rate is selected as a power of ten for best final objective value, and the batch-size is set to its default value. All methods use a fix budget of 160 epochs for WRN-SVHN, 200 epochs for WRN-CIFAR and 300 epochs for DN-CIFAR, following (Zagoruyko & Komodakis, 2016) and (Huang et al., 2017) . The L 4 methods diverge on CIFAR-100 in this setting. For clarity, we only display the 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 hyper-parameter for their learning-rate. As can be seen, ALI-G provides better training performance than the baseline algorithms on all tasks. Figure 4 : Objective function over the epochs on CIFAR-10, CIFAR-100 and SVHN (smoothed with a moving average over 5 epochs). On SVHN, ALI-G obtains similar performance 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 an order of magnitude better than the baselines.

6. DISCUSSION:

We hope that the ALI-G algorithm is a 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 of Nedić & Bertsekas (2001b) and Rolinek & Martius (2018) .

A LOCAL INTERPRETATION OF THE POLYAK STEP-SIZE:

Proposition 2. Suppose that the problem is unconstrained: Ω = R p . Let w t+1 = w tf (wt)-f ∇f (wt) 2 ∇f (w t ). Then w t+1 verifies:

EQUATION

where we remind that f is the minimum of f , and w → f (w t ) + ∇f (w t ) (w -w t ) is the linearization of f at w t . In other words, w t+1 is the closest point to w t that lies on the hyper-plane f (w t ) + ∇f (w t ) (w -w t ) = f .

Proof : See Appendix D.1

B CONVERGENCE RESULTS:

Before we detail our convergence results, we introduce the notions of uniform lower bound and ε-interpolation.

B.1 NOTATION:

Intuitively, a uniform lower bound on the problem (P) is a lower bound on all loss functions z on their unconstrained domain R p . We formalize this below: Definition 1 (Uniform Lower Bound). We say that B is a uniform lower bound on (P) if:

EQUATION

Note that in the main paper, we have used the special case B = 0 as the uniform lower bound. The definition above makes B a useful statistic to analyze the behavior of each loss function z around w , in a uniform way (that is, independently of z). The quality of a uniform lower bound B can be quantified by the notion of ε-interpolation: Definition 2 (ε-Interpolation). Let B be a uniform lower bound on (P), w be a solution of (P) and ε ≥ 0 be a non-negative number. Then we say that w is an ε-interpolation for ((P), B) if:

EQUATION

By taking the expectation over equation ( 8), we can see that if w is an ε-interpolation for ((P), B), then we immediately have: f -ε ≤ B ≤ f . In other words, B is also an approximation of f by below, and its quality is quantified by ε. We further note that f does not satisfy the definition of a uniform lower bound in the general case. However when f actually is a uniform lower bound, for any solution w of (P), w is a ε = 0-interpolation for ((P), f ).

In the general case where B may be different from 0, the ALI-G step-size can be defined as:

EQUATION

We now turn to our convergence results, which give convergence rates in three settings: convex and Lipschitz functions, convex and smooth function, and strongly convex and smooth functions. In each setting, we 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 is a convex set, and that for every z ∈ Z, z is convex and C-Lipschitz. Let B be a uniform lower bound on (P) and w be a solution of (P). Further suppose that w is an ε-interpolation for ((P), B). Then ALI-G ∞ applied to f satisfies:

EQUATION

)

Proof : See Appendix D.3.

Theorem 3. We assume that X is a convex set, and that for every z ∈ Z, z is convex and C-Lipschitz.

Let w be an ε-interpolation for ((P), B). We further assume that η > ε δ . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

Proof : See Appendix D.4.

We note that for very large values of η (η → ∞), Theorem 3 gives the exact same result as Theorem 2. However when η is small, the convergence error of Theorem 3 is large. This is corrected in the following result which is informative in the regime where η is small: Theorem 4. We assume that X is a convex set, and that for every z ∈ Z, z is convex and C-Lipschitz.

Let w be an ε-interpolation for ((P), B). Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

)

Proof : See Appendix D.5.

B.3 SMOOTH CONVEX FUNCTIONS:

We now tackle the convex and β-smooth case. Our proof techniques naturally produce the separation η ≥ 1 2β and η ≤ 1 2β . Whenever η ≥ 1 2β , the convergence result is exactly the same as when η → ∞. When η ≤ 1 2β , the speed of convergence is limited by the value of η. Theorem 5. [Convex and Smooth] We assume that X is a convex set, and that for every z ∈ Z, z is convex and β-smooth. Let B be a uniform lower bound on (P) and w be a solution of (P). Further suppose that w is an ε-interpolation for ((P), B), and that δ > 2βε. Then ALI-G ∞ applied to f satisfies:

EQUATION

)

Proof : See Appendix D.6.

Theorem 6. We assume that X is a convex set, and that for every z ∈ Z, z is convex and β-smooth.

Let w be an ε-interpolation for ((P), B), and suppose that δ > 2βε. Further assume that η ≥ 1 2β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

)

Proof : See Appendix D.7.

Theorem 7. We assume that X is a convex set, and that for every z ∈ Z, z is convex and β-smooth.

Let w be an ε-interpolation for ((P), B), and suppose that δ > 2βε. Further assume that η ≤ 1 2β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

)

Proof : See Appendix D.8.

B.4 SMOOTH AND STRONGLY CONVEX FUNCTIONS:

Finally, we consider the α-strongly convex and β-smooth case. Again, our proof yields a natural separation between η ≥ 1 2β and η ≤ 1 2β . In a similar way to the β-smooth case, when η ≥ 1 2β , Theorem 9 gives the exact same result as η → ∞. And when η ≤ 1 2β , the rate of convergence given by Theorem 10 is limited by the value of η. Theorem 8. [Strongly Convex and Smooth] We assume that X is a convex set, and that for every z ∈ Z, z is α-strongly convex and β-smooth. Let B be a uniform lower bound on (P) and w be a solution of (P). Further suppose that w is an ε-interpolation for ((P), B), and that δ > 2βε. Then ALI-G ∞ applied to f satisfies:

EQUATION

)

In other words, f approximately converges to f at a rate of O(exp(-αT /8β)).

Proof : See Appendix D.9.

Theorem 9. We assume that X is a convex set, and that for every z ∈ Z, z is α-strongly convex and β-smooth. Let w be an ε-interpolation for ((P), B), and suppose that δ > 2βε. Further assume that η ≥ 1 2β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

)

Proof : See Appendix D.10.

Theorem 10. We assume that X is a convex set, and that for every z ∈ Z, z is α-strongly convex and β-smooth. Let w be an ε-interpolation for ((P), B), and suppose that δ > 2βε. Further assume that η ≤ 1 2β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

)

Proof : See Appendix D.11.

C ON THE NEED FOR A MAXIMAL LEARNING-RATE FOR NON-CONVEXITY:

The Restricted Secant Inequality (RSI) is a milder assumption than convexity. It can be defined as follows: Definition 3. Let f : R p → R be a lower-bounded differentiable function achieving its minimum at w . We say that f satisfies the RSI if there exists α > 0 such that:

EQUATION

)

The RSI is sometimes used to prove convergence of optimization algorithms without assuming convexity (Vaswani et al., 2019b) .

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 ∈ [ -3 5 ; 3 5 ] → w 2 -|w| 3 . We restrict our domain of study to [ -3 5 ; 3 5 ] for simplicity purposes -an extension to R can easily be constructed by extending f . We will first show that f fulfills the RSI assumption, and then that it oscillates between two points for a well chosen initialization.

Let us show that f satisfies the RSI with α = 1 5 . First we note that f achieves its minimum at w = 0, and that f (w ) = 0. In addition, we introduce the sign function σ(w), which is equal to 1 if w ≥ 0, 

EQUATION

)

Now let us show that if we apply gradient descent with a Polyak step-size to f , with starting point w 0 = -3 5 , we obtain w 1 = 3 5 . This will prove oscillation of the iterates by symmetry of the problem. Let w 0 = -3 5 . Then we have f (w 0 ) = 9 25 -27 125 = 18 125 . Furthermore, ∇f (w 0 ) = 2( -3 5 ) + 3( 9 25 ) = -3

25 . Therefore:

w 1 = w 0 - f (w 0 ) -0 (∇f (w 0 )) 2 ∇f (w 0 ), = w 0 - f (w 0 ) ∇f (w 0 ) , = -3 5 + 18 125 3 25 , = -3 5 + 6 5 , = 3 5 . (21) D PROOFS D.1 PROPOSITION 2

Proposition 2. Suppose that the problem is unconstrained:

Ω = R p . Let w t+1 = w t - f (wt)-f ∇f (wt) 2 ∇f (w t ).

Then w t+1 verifies:

EQUATION

where we remind that f is the minimum of f , and w → f (w t ) + ∇f (w t ) (w -w t ) is the linearization of f at w t . In other words, w t+1 is the closest point to w t that lies on the hyper-plane f (w t ) + ∇f (w t ) (w -w t ) = f .

Proof : First we show that wt+1 satisfies the linear equality constraint:

f (wt) + ∇f (wt) (wt+1 -wt) = f (wt) + ∇f (wt) - f (wt) -f ∇f (wt) 2 ∇f (wt) , = f (wt) -f (wt) + f , = f . (22)

Now let us show that it has a minimal distance to wt.

We take ŵ ∈ R p a solution of the linear equality constraint, and we will show that wt+1 -wt ≤ ŵwt . By definition, we have that ŵ satisfies:

EQUATION

)

Now we can write:

EQUATION

D.2 THEOREM 1 Proposition 1. [Proximal Interpretation] Suppose that Ω = R p and let δ = 0. We consider the update performed by SGD: w SGD t+1 = w t -η t ∇ zt (w t ); and the update performed by ALI-G: w ALI-G t+1 = w t -γ t ∇ zt (w t ), where γ t = min z t (wt)

∇ z t (wt) 2 +δ , η . Then we have:

EQUATION

w ALI-G t+1 = argmin

EQUATION

Proof : We tackle the slightly more general case where B may be different from zero. In order to make the notation simpler, we use dt ∇ z t (wt) and lt z t (wt) -B. First, let us consider dt = 0.

Then we choose γt = 0 and it is clear that wt+1 = wt -ηγtdt = wt is the optimal solution of problem (5).

We now assume dt = 0.

We can successively re-write the proximal problem (5) as :

EQUATION

The inner problem is now smooth in w and υ. We write its KKT conditions:

EQUATION

We plug in these results and obtain:

EQUATION

This is a one-dimensional quadratic problem in ν. It can be solved in closed-form by finding the global maximum of the quadratic objective, and projecting the solution on [0, 1]. We have:

EQUATION

Since dt = 0 and η = 0, this gives the optimal solution:

EQUATION

since lt, η, dt 2 ≥ 0. Plugging this back in the KKT conditions, we obtain that the solution wt+1 of the primal problem can be written as:

EQUATION

D.3 THEOREM 2:

Theorem 2. [Convex and Lipschitz] We assume that X is a convex set, and that for every z ∈ Z, z is convex and C-Lipschitz. Let B be a uniform lower bound on (P) and w be a solution of (P). Further suppose that w is an ε-interpolation for ((P), B). Then ALI-G ∞ applied to f satisfies:

EQUATION

)

Proof :

We consider the update at time t, which we condition on the draw of zt ∈ Z:

EQUATION

We re-write this inequality as:

EQUATION

We can now use the Cauchy-Schwarz inequality to bound the sum over the iterations:

EQUATION

Therefore we can write:

EQUATION

which yields:

EQUATION

We can now take the expectation over the zt:

EQUATION

)

Dividing by T + 1 and exploiting convexity of f , we finally get:

EQUATION

D.4 THEOREM 3

Theorem 3. We assume that X is a convex set, and that for every z ∈ Z, z is convex and C-Lipschitz.

Let w be an ε-interpolation for ((P), B). We further assume that η > ε δ . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

Proof :

We consider the update at time t, which we condition on the draw of zt ∈ Z:

EQUATION

We now consider different cases, according to the value that γt takes: γt

= z t (w t )-B ∇ z t (w t ) 2 +δ or γt = η.

First, suppose that γt = z t (w t )-B ∇ z t (w t ) 2 +δ . Then we can follow the proof of Theorem 2 to obtain:

EQUATION

Now suppose γt = η and z t (wt)z t (w ) ≤ 0. We can use γt ≤ z t (w t )-B ∇ z t (w t ) 2 +δ to write:

EQUATION

where the last inequality has used γt ≤ z t (w t )-B ∇ z t (w t ) 2 +δ , z t (wt)z t (w ) ≤ 0 and z t (w ) -B ≥ 0. Therefore we are exactly in the same situation as the first case (where we used γt = z t (w t )-B ∇ z t (w t ) 2 ), and thus we have again:

EQUATION

)

Now suppose that γt = η and z t (wt)z t (w ) ≥ 0. The inequality (39) gives:

EQUATION

We now introduce IT and JT as follows:

EQUATION

Then, by combining inequalities (40), ( 42) and ( 43), and using a telescopic sum, we obtain:

wT +1 -w 2 ≤ w0 -w 2 + t∈J T - ( z t (wt) -z t (w )) 2 C 2 + δ + ε 2 δ + t∈I T -η - ε δ ( z t (wt) -z t (w )) + ε 2 δ (45)

Using wT +1 -w 2 ≥ 0, we obtain:

1 C 2 + δ t∈J T ( z t (wt) -z t (w )) 2 + η - ε δ t∈I T ( z t (wt) -z t (w )) ≤ w0 -w 2 + (T + 1) ε 2 δ (46)

In particular, the inequality (46) gives that:

EQUATION

Furthermore, for every t ∈ IT , we have

( z t (wt) -z t (w )) ≥ 0, which yields η -ε δ t∈I T ( z t (wt) - z t (w )) ≥ 0 since η > δ .

Thus the inequality (46) also gives:

EQUATION

)

Using the Cauchy-Schwarz inequality, we can further write:

EQUATION

)

Therefore we have:

EQUATION

We can now put together inequalities ( 47) and ( 49) by writing:

EQUATION

)

Dividing by T + 1 and taking the expectation, we obtain:

EQUATION

Then, by combining inequalities ( 54), ( 55) and ( 56), and using a telescopic sum, we obtain:

EQUATION

Using wT +1 -w 2 ≥ 0, we obtain:

1 C 2 + δ t∈J T ( z t (wt) -z t (w )) 2 + η t∈I T ( z t (wt) -z t (w )) ≤ w0 -w 2 + (T + 1)ηε (59)

We now take the expectation and obtain:

1 C 2 + δ t∈J T E ( z t (wt) -z t (w )) 2 + η t∈I T (f (wt) -f ) ≤ w0 -w 2 + (T + 1)ηε (60) Since E[U ] 2 ≤ E[U 2

] for any real-valued random variable, we can write:

EQUATION

Since each f (wt) -f ≥ 0, the inequality (61) gives that:

EQUATION

and:

EQUATION

Using the Cauchy-Schwarz inequality, we can further write:

EQUATION

)

Therefore we have:

EQUATION

We can now put together inequalities ( 62) and ( 65) by writing:

EQUATION

Dividing by T + 1, we obtain:

EQUATION

D.6 THEOREM 5

Lemma 1. Let z ∈ Z. Assume that z is convex, β-smooth and is lower-bounded on R p by B ∈ R.

Then we have:

EQUATION

Proof : Let w ∈ R p and suppose that z reaches its infimum at w ∈ (R ∪ {-∞, +∞}) p .

First, let us consider the case w ∈ R p . Then by Lemma 3.5 of Bubeck (2015) , we have:

EQUATION

Therefore we can write:

EQUATION

)

Now let us assume that w / ∈ R p . Then we can construct a sequence (w k ) k∈N ∈ (R p ) N that converges to w. Since z and ∇ z are continuous functions (they are respectively convex and smooth), we have:

EQUATION

Therefore the previous case gives the wanted result by using w k in place of w and then taking the limit k → ∞.

Lemma 2. Let z ∈ Z. Assume that z is convex, β-smooth and is lower-bounded on R p by B ∈ R.

Then we have:

EQUATION

Proof :

Let w ∈ R p . We apply Lemma 1 and we write successively:

EQUATION

Theorem 5. [Convex and Smooth] We assume that X is a convex set, and that for every z ∈ Z, z is convex and β-smooth. Let B be a uniform lower bound on (P) and w be a solution of (P). Further suppose that w is an ε-interpolation for ((P), B), and that δ > 2βε. Then ALI-G ∞ applied to f satisfies:

EQUATION

)

Proof :

We consider the update at time t, which we condition on the draw of zt ∈ Z:

EQUATION

We now lower bound γt( z t (wt)z t (w )) and upper bound γt( z t (w ) -B) individually.

We begin with γt( z t (wt)z t (w )), for which we distinguish two cases according to its sign:

Suppose ( z t (wt)z t (w )) ≥ 0. Then we can write:

EQUATION

Now suppose ( z t (wt)z t (w )) ≤ 0, and let us show that the same result holds. We have:

EQUATION

Therefore we have:

γt( z t (wt) -z t (w )) ≥ 1 2β ( z t (wt) -z t (w )) (( z t (wt) -z t (w )) ≤ 0) ≥ 1 2β ( z t (wt) -z t (w )) - δ 4β 2 (δ ≥ 0) (77)

In conclusion, regardless of the sign, it always holds true that:

EQUATION

We now upper bound γt( z t (w ) -B):

EQUATION

Putting inequalities (74), ( 78) and ( 79) together, we obtain:

EQUATION

Therefore we have:

EQUATION

)

By summing over t and taking the expectation over the zt, we obtain:

EQUATION

Re-arranging and using the convexity of f , we finally obtain:

EQUATION

D.9 THEOREM 8 Lemma 3. For any a, b ∈ R p , we have that:

EQUATION

Proof : This is a simple application of the parallelogram law, but we give the proof here for completeness.

a 2 + b 2 - 1 2 a -b 2 = a 2 + b 2 - 1 2 a 2 - 1 2 b 2 + a b = 1 2 a 2 + 1 2 b 2 + a b = 1 2 a + b 2 ≥ 0 4. Let z ∈ Z.

Assume that z is α-strongly convex and is lower-bounded on R p by B ∈ R such that inf z -B ≤ ε. In addition, suppose that δ ≥ 2αε. Then we have:

EQUATION

Proof :

Let w ∈ R p and suppose that z reaches its minimum at w ∈ R p (this minimum exists because of strong convexity). By definition of strong convexity, we have that:

EQUATION

We minimize the right hand-side over ŵ, which gives:

∀ ŵ ∈ R p , z ( ŵ) ≥ z (w) + ∇ z (w) ( ŵ -w) + α 2 ŵ -w 2 ≥ z (w) - 1 2α ∇ z (w) 2 (106)

Thus by choosing ŵ = w and re-ordering, we obtain the following result (a.k.a. the Polyak-Lojasiewicz inequality):

EQUATION

Therefore we can write:

EQUATION

)

We introduce the function ψ :

x ∈ R + → 1 2α x + ε x + δ

, and we compute its derivative:

EQUATION

Therefore ψ is monotonically increasing. As a result, we have:

EQUATION

)

Therefore we have that:

EQUATION

which concludes the proof.

Theorem 8. [Strongly Convex and Smooth] We assume that X is a convex set, and that for every z ∈ Z, z is α-strongly convex and β-smooth. Let B be a uniform lower bound on (P) and w be a solution of (P). Further suppose that w is an ε-interpolation for ((P), B), and that δ > 2βε. Then ALI-G ∞ applied to f satisfies:

EQUATION

In other words, f approximately converges to f at a rate of O(exp(-αT /8β)).

Proof :

We condition the update on zt drawn at random. The beginning of the proof is identical to that of Theorem 5 (and in particular requires δ > 2βε). In addition, we remark that δ > 2βε ≥ 2αε, because it always holds true that β ≥ α. Combining inequalities ( 74) and ( 78), we obtain: 

wt+1 -w 2 ≤

Let w (z t ) be the minimizer of z t on its unconstrained domain R p (its existence is guaranteed by the strong convexity property). Then we exploit strong convexity to lower bound the progress made:

z t (wt)z t (w ) = z t (wt)z t (w (z t ) ) + z t (w )z t (w (z t ) ) -2( z t (w )z t (w (z t ) )) ≥ z t (wt)z t (w (z t ) ) + z t (w )z t (w (z t ) ) -2( z t (w ) -B)

(because z t (w (z t ) ) ≥ B)

≥ z t (wt)z t (w (z t ) ) + z t (w )z t (w (z t ) ) -2ε (definition of ε) ≥ α 2 wtw (z t ) 2 + α 2 ww (z t ) 2 -2ε (α-strong convexity)

EQUATION

We now combine inequalities ( 112) and ( 113):

EQUATION

We use a trivial induction over t and write:

EQUATION

In particular, we remark that the right hand-side of the equation is independent on zt.

Given an arbitrary w ∈ R p , we now wish to relate the distance w-w 2 to the function values f (w)-f (w ).

Since each z is α-strongly convex and β-smooth, so is f = Ez 

We combine the results to obtain the final result: D.10 THEOREM 9

EQUATION

Theorem 9. We assume that X is a convex set, and that for every z ∈ Z, z is α-strongly convex and β-smooth. Let w be an ε-interpolation for ((P), B), and suppose that δ > 2βε. Further assume that η ≥ 1 2β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

)

Proof : Re-using inequalities (84) and (89) from the proof of Theorem 6, we obtain:

wt+1 -w 2 ≤ wtw 2 -1 2β ( z t (wt)z t (w )) + δ 4β 2 + γt( z t (w ) -B).

(118) This is exactly the same result as the first line of the inequality (112) in the proof of Theorem 8. Then the rest of the proof is identical to the one of Theorem 8.

D.11 THEOREM 10:

Theorem 10. We assume that X is a convex set, and that for every z ∈ Z, z is α-strongly convex and β-smooth. Let w be an ε-interpolation for ((P), B), and suppose that δ > 2βε. Further assume that η ≤ 1 2β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:

EQUATION

Proof : Re-using inequalities ( 92) and ( 98) from the proof of Theorem 7, we can write:

wt+1 -w 2 ≤ wtw 2 -η( 

:

https://github.com/martius-lab/l4-optimizer

https://github.com/oval-group/dfw

https://github.com/deepmind/dnc

Figures and Tables:

(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 are part of the DeepOBS benchmark Schneider et al. (

Figure 3: Final objective function when training a Differentiable Neural Computer for 10k steps (lower is better). The intensity of each cell is log-proportional to the value of the objective function (darker is better). ALI-G obtains good performance for a very large range of η (10 -1 ≤ η ≤ 10 6 ).

Figure 5: Illustration of the function f , which satisfies the RSI. When starting at w = -3/5, gradient descent with the Polyak step-size oscillates between w = -3/5 and w = 3/5.

[ z ]. We introduce w the minimizer of f on its unconstrained domain R p . Then we can write that for any w ∈ R p :f (w) -f (w ) ≤ f (w) -f (w), (f (w) ≤ f (w )) ≤ ∇f (w) (w -w) + β 2 ww 2 , (f is β-smooth) = β 2 ww 2 , (∇f (w) = 0) ≤ β( ww 2 + ww 2 ), (Lemma 3) ≤ β ww 2 + 2β α (f (w ) -f (w)) , (f is α-strongly convex) ≤ β ww 2 + 2β α (f (w ) -B) , (B ≤ f (w) by definition) ≤ β ww 2 + 2 βε α, (definition of ε)

).

Table content: <table><tr><td/><td>0.05</td><td>0.10</td><td>0.15</td><td>0.20</td><td>0.25</td><td>0.30</td><td>0.35</td><td>0.40</td><td>0.45</td><td>0.50</td></tr><tr><td>L4Adam</td><td>2e-5</td><td>4e-8</td><td>5e-8</td><td>4e-8</td><td>5e-8</td><td>5e-8</td><td>6e-8</td><td>7e+0</td><td>6e-8</td><td>3e-1</td></tr><tr><td>L4Mom</td><td>3e-5</td><td>3e-7</td><td>3e-7</td><td>4e-7</td><td>2e+0</td><td>3e+0</td><td>1e+1</td><td>1e+1</td><td>1e+1</td><td>9e+1</td></tr><tr><td/><td>3e-4</td><td>1e-3</td><td>3e-3</td><td>1e-2</td><td>3e-2</td><td/><td>1e-1</td><td>3e-1</td><td>1e+0</td><td>3e+0</td></tr></table>

Test Accuracy (%) on SNLI. In red, SGD benefits from a hand-designed schedule for its learning-rate. In black, adaptive methods have a single hyper-parameter for their learning-rate. In blue, ALI-G ∞ does not have any hyper-parameter for its learning-rate. 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 fromBerrada et al. (2019). SGD † is the result fromConneau et al. (2017).

Table content: <table><tr><td>D  †</td></tr></table>

Test Accuracy (%) on the CIFAR data sets.

Table content: <table><tr><td>10</td><td>WRN DN</td><td>90.8 92.1 91.2 94.2 90.5 91.6 95.2 95.3 95.4 91.7 92.6 92.1 94.6 90.8 91.9 95.0 95.1 -</td></tr><tr><td>CIFAR-100</td><td>WRN DN</td><td>68.7 69.6 68.7 76.0 61.7 61.4 75.8 77.8 78.8 69.4 69.5 69.6 73.2 60.5 62.6 76.3 76.3 -</td></tr></table>

wtw 2 -1 2β ( z t (wt)z t (w )) + δ 4β 2 + γt( z t (w ) -B), ≤ wtw 2 -1 2β ( z t (wt)z t (w )) + δ 4β 2 + γtε, (definition of ε)

Table content: <table><tr><td>≤ wt -w 2 -</td><td>1 2β</td><td>( z t (wt) -z t (w )) +</td><td>δ 4β 2 +</td><td>ε 2α</td><td>. (Lemma 4)</td></tr></table>

z t (wt)z t (w )) + ηδ 2β + γt( z t (w ) -B), ≤ wtw 2 -η( z t (wt)z t (w )) + ηδ 2β + ηε (γt ≤ η, 0 ≤ z t (w ) -B ≤ ε).Test Accuracy (%) on CIFAR including standard deviations. Each experiment was run three times.

Table content: <table><tr><td>(119)</td></tr></table>

Peer review (iclr2020):
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. Overall, 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. For the algorithm and theory, there are some points that need to be verified and further clarification on novelty: 1. 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. 2. 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. For the experiments, the following should be addressed: 1. 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. 2. 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. 3. In Section 5.5, given that ALI-G and DFW are related, why is there no result for DFW in Figure 4.? 4. As the paper mentions, AProx algorithm and ALI-G are related, why is there no comparison with AProx in the experiments? Things to improve the paper that did not impact the score: 1. In all experiments, the performance differences between ALI-G and competitive methods are small. Thus, error bars are needed for these results. 2. 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? 3. 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) The following paper also proved the convergence of adaptive gradient methods for nonconvex optimization: Dongruo Zhou*, Yiqi Tang*, Ziyan Yang*, Yuan Cao, Quanquan Gu. On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization. ------------------------------------------------------------- After rebuttal: I noticed that the authors: 1. did not compare with SGD or Adam with good hyperparameters (https://arxiv.org/abs/1907.08610) 2. did not test on the large scale datasets, e.g., imagenet 3. the proposed algorithm is not as good as SGD on most numerical experiments. For the above reasons, I think this paper should be rejected.