summaries: 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. 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.
abstractText: 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.
references.authors: Vanhoucke Vijay Vasudevan Fernandaégas Vi Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu Xiaoqiang Zheng
references.title: TensorFlow: Large-Scale Machine
references.venue: Learning on Heterogeneous Systems,
references.authors: Hilal Asi John C Duchi
references.title: Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity
references.venue: SIAM Journal on Optimization,
references.authors: Atilim Gunes Baydin Robert Cornish David Martinez Rubio Mark Schmidt Frank Wood
references.title: Online learning rate adaptation with hypergradient descent
references.venue: International Conference on Learning Representations,
references.authors: Jeremy Bernstein Yu-Xiang Wang Kamyar Azizzadenesheli Anima Anandkumar
references.title: signsgd: Compressed optimisation for non-convex problems
references.venue: International Conference on Machine Learning,
references.authors: Leonard Berrada Andrew Zisserman M Pawan Kumar
references.title: Deep Frank-Wolfe for neural network optimization
references.venue: International Conference on Learning Representations,
references.authors: Samuel R Bowman Gabor Angeli Christopher Potts Christopher D Manning
references.title: A large annotated corpus for learning natural language inference
references.venue: Conference on Empirical Methods in Natural Language Processing,
references.authors: Ulf Brännlund
references.title: A generalized subgradient method with relaxation step
references.venue: Mathematical Programming,
references.authors: Sébastien Bubeck
references.title: Convex optimization: Algorithms and complexity
references.venue: Foundations and Trends in Machine Learning,
references.authors: Jinghui Chen Quanquan Gu
references.title: Padam: Closing the generalization gap of adaptive gradient methods in training deep neural networks
references.authors: Xiangyi Chen Sijia Liu Ruoyu Sun Mingyi Hong
references.title: On the convergence of a class of adam-type algorithms for non-convex optimization
references.venue: International Conference on Learning Representations,
references.authors: Alexis Conneau Douwe Kiela Holger Schwenk Loic Barrault Antoine Bordes
references.title: Supervised learning of universal sentence representations from natural language inference data
references.venue: Conference on Empirical Methods in Natural Language Processing,
references.authors: Alexandre Défossez Francis Bach
references.title: Adabatch: Efficient gradient aggregation rules for sequential and parallel stochastic gradient methods
references.venue: arXiv preprint,
references.authors: John Duchi Elad Hazan Yoram Singer
references.title: Adaptive subgradient methods for online learning and stochastic optimization
references.venue: Journal of Machine Learning Research,
references.authors: Marguerite Frank Philip Wolfe
references.title: An algorithm for quadratic programming
references.venue: Naval Research Logistics Quarterly,
references.authors: Alex Graves Greg Wayne Malcolm Reynolds Tim Harley Ivo Danihelka Agnieszka GrabskaBarwińska Sergio Gómez Colmenarejo Edward Grefenstette Tiago Ramalho John Agapiou
references.title: Hybrid computing using a neural network with dynamic external memory
references.authors: Gao Huang Zhuang Liu Kilian Q Weinberger Laurens van der Maaten
references.title: Densely connected convolutional networks
references.venue: Conference on Computer Vision and Pattern Recognition,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: International Conference on Learning Representations,
references.authors: Simon Lacoste-Julien Martin Jaggi Mark Schmidt Patrick Pletscher
references.title: Block-coordinate FrankWolfe optimization for structural SVMs
references.venue: International Conference on Machine Learning,
references.authors: Kfir Levy
references.title: Online to offline conversions, universality and adaptive minibatch sizes
references.venue: Neural Information Processing Systems,
references.authors: Xiaoyu Li Francesco Orabona
references.title: On the convergence of stochastic gradient descent with adaptive stepsizes
references.venue: International Conference on Artificial Intelligence and Statistics,
references.authors: Francesco Locatello Rajiv Khanna Michael Tschannen Martin Jaggi
references.title: A unified optimization view on generalized matching pursuit and frank-wolfe
references.venue: International Conference on Artificial Intelligence and Statistics,
references.authors: Ilya Loshchilov Frank Hutter
references.title: Fixing weight decay regularization in adam
references.venue: International Conference on Learning Representations,
references.authors: Liangchen Luo Yuanhao Xiong Yan Liu Xu Sun
references.title: Adaptive gradient methods with dynamic bound of learning
references.venue: rate. International Conference on Learning Representations,
references.authors: Siyuan Ma Raef Bassily Mikhail Belkin
references.title: The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning
references.venue: International Conference on Machine Learning,
references.authors: Mahesh Chandra Mukkamala Matthias Hein
references.title: Variants of rmsprop and adagrad with logarithmic regret bounds
references.venue: International Conference on Machine Learning,
references.authors: Angelia Nedić Dimitri Bertsekas
references.title: Convergence rate of incremental subgradient algorithms
references.venue: Stochastic optimization: algorithms and applications,
references.authors: Angelia Nedić Dimitri Bertsekas
references.title: Incremental subgradient methods for nondifferentiable optimization
references.venue: SIAM Journal on Optimization,
references.authors: Adam M Oberman Mariana Prazeres
references.title: Stochastic gradient descent with polyak’s learning rate
references.venue: arXiv preprint,
references.authors: Francesco Orabona Dávid Pál
references.title: Scale-free algorithms for online linear optimization
references.venue: International Conference on Algorithmic Learning Theory,
references.authors: Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga Adam Lerer
references.title: Automatic differentiation in pytorch
references.venue: NIPS Autodiff Workshop,
references.authors: Boris Teodorovich Polyak
references.title: Minimization of unsmooth functionals
references.venue: USSR Computational Mathematics and Mathematical Physics,
references.authors: Sashank J Reddi Satyen Kale Sanjiv Kumar
references.title: On the convergence of adam and beyond
references.venue: International Conference on Learning Representations,
references.authors: Herbert Robbins Sutton Monro
references.title: A stochastic approximation method
references.venue: The annals of mathematical statistics,
references.authors: Michal Rolinek Georg Martius. L
references.title: Practical loss-based stepsize adaptation for deep learning
references.venue: Neural Information Processing Systems,
references.authors: Tom Schaul Sixin Zhang Yann LeCun
references.title: No more pesky learning rates
references.venue: International Conference on Machine Learning,
references.authors: Frank Schneider Lukas Balles Philipp Hennig
references.title: DeepOBS: A deep learning optimizer benchmark suite
references.venue: International Conference on Learning Representations,
references.authors: Shai Shalev-Shwartz Tong Zhang
references.title: Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
references.venue: Mathematical Programming,
references.authors: Noam Shazeer Mitchell Stern
references.title: Adafactor: Adaptive learning rates with sublinear memory cost
references.venue: International Conference on Machine Learning,
references.authors: Naum Zuselevich Shor
references.title: Minimization methods for non-differentiable functions
references.venue: Springer Series in Computational Mathematics,
references.authors: Conghui Tan Shiqian Ma Yu-Hong Dai Yuqiu Qian
references.title: Barzilai-borwein step size for stochastic gradient descent
references.venue: Neural Information Processing Systems,
references.authors: Tijmen Tieleman Geoffrey Hinton
references.title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine
references.authors: Sharan Vaswani Francis Bach Mark Schmidt
references.title: Fast and faster convergence of sgd for overparameterized models and an accelerated perceptron
references.venue: International Conference on Artificial Intelligence and Statistics,
references.authors: Sharan Vaswani Aaron Mishkin Issam Laradji Mark Schmidt Gauthier Gidel Simon LacosteJulien
references.title: Painless stochastic gradient: Interpolation, line-search, and convergence rates
references.venue: arXiv preprint,
references.authors: Ashia C Wilson Rebecca Roelofs Mitchell Stern Nati Srebro Benjamin Recht
references.title: The marginal value of adaptive gradient methods in machine learning
references.venue: Neural Information Processing Systems,
references.authors: Xiaoxia Wu Rachel Ward Léon Bottou
references.title: WNGrad: Learn the learning rate in gradient descent
references.venue: arXiv preprint,
references.authors: Sergey Zagoruyko Nikos Komodakis
references.title: Wide residual networks
references.venue: British Machine Vision Conference,
references.authors: Manzil Zaheer Sashank Reddi Devendra Sachan Satyen Kale Sanjiv Kumar
references.title: Adaptive methods for nonconvex optimization
references.venue: Neural Information Processing Systems,
references.authors: Matthew Zeiler
references.title: ADADELTA: an adaptive learning rate method
references.venue: arXiv preprint,
references.authors: Ziming Zhang Yuanwei Wu Guanghui Wang
references.title: Bpgrad: Towards global optimality in deep learning via branch and pruning
references.venue: Conference on Computer Vision and Pattern Recognition,
references.authors: Shuai Zheng James T Kwok
references.title: Follow the moving leader in deep learning
references.venue: International Conference on Machine Learning,
references.authors: Yi Zhou Junjie Yang Huishuai Zhang Yingbin Liang Vahid Tarokh
references.title: Sgd converges to global minimum in deep learning via star-convex
references.venue: path. International Conference on Learning Representations,
sections.heading: 1 INTRODUCTION
sections.text: 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, Nedić & 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 L4 (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 L4 (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.
sections.heading: 2 THE ALGORITHM
sections.heading: 2.1 PROBLEM SETTING
sections.text: Loss Function. We consider a supervised learning task where the model is parameterized by w ∈ Rp. 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) , Ez∈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 L1 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 a constraint on the feasible domain: Ω = {w ∈ Rp : φ(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 L2 regularization: Ω = { w ∈ Rp : ‖w‖22 ≤ 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 Ω = Rp 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? , minw∈Ω f(w).
sections.heading: 2.2 THE POLYAK STEP-SIZE
sections.text: 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 Rp, and ΠΩ(w) is the Euclidean projection of the vector w ∈ Rp on the set Ω.
  Polyak Step-Size. At time-step t, using the Polyak step-size (Polyak, 1969, Shor, 1985, Brännlund, 1995, Nedić & Bertsekas, 2001a;b) yields the following update:
  wt+1 = ΠΩ (wt − γt∇f(wt)) , where γt , f(wt)− f? ‖∇f(wt)‖2 , (2)
  where we loosely define 00 = 0 for simplicity purposes.
  Interpretation. It can be shown that wt+1 lies on the intersection between the linearization of f at wt 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 Nedić & 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 augmen-
  tation. 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.
sections.heading: 2.3 THE ALI-G ALGORITHM
sections.text: 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 w0 ∈ Ω, small constant δ > 0
  1: t = 0 2: while not converged do 3: Get `zt(wt), ∇`zt(wt) with zt drawn i.i.d. 4: γt = min { `zt (wt) ‖∇`zt (wt)‖2+δ , η } 5: wt+1 = ΠΩ (wt − γt∇`zt(wt)) 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.
sections.heading: 3 JUSTIFICATION AND ANALYSIS
sections.heading: 3.1 INTERPOLATION ENABLES INEXPENSIVE STOCHASTIC UPDATES
sections.text: 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(wt) rather than the exact but expensive f(wt). 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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) ≤ ε √( C2
  δ + 1
  ) + ‖w0 −w?‖ √ C2 + δ√
  T + 1 . (3)
  In other words, by assuming interpolation, ALI-G provably converges while requiring only `zt(wt) and ∇`zt(wt) (stochastic estimation per sample) to compute its learning-rate. In contrast, the Polyak step-size, which does not exploit interpolation, would require f(wt) and∇f(wt) 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.
sections.heading: 3.2 A MAXIMAL LEARNING-RATE HELPS WITH NON-CONVEXITY
sections.text: 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 Ω = Rp and let δ = 0. We consider the update performed by SGD: wSGDt+1 = wt − ηt∇`zt(wt); and the update performed by ALI-G: wALI-Gt+1 = wt − γt∇`zt(wt), where γt = min { `zt (wt) ‖∇`zt (wt)‖2+δ , η } . Then we have:
  wSGDt+1 = argmin w∈Rp { 1 2ηt ‖w −wt‖2 + `zt(wt) +∇`zt(wt)>(w −wt) } , (4)
  wALI-Gt+1 = argmin w∈Rp { 1 2η ‖w −wt‖2 + max { `zt(wt) +∇`zt(wt)>(w −wt), 0 }} . (5)
  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 wt. 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 η.
sections.heading: 4 RELATED WORK
sections.text: 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.
  L4 Algorithm. The L4 algorithm (Rolinek & Martius, 2018) also uses a modified version of the Polyak step-size. However, the L4 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, L4 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(wt) only, instead of the expensive deterministic gradient ∇f(wt). However, they still require to evaluate f(wt), 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.
sections.heading: 5 EXPERIMENTS
sections.text: 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; (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 CIFAR100 are part of the DeepOBS benchmark Schneider et al. (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 L41. In the PyTorch (Paszke et al., 2017) experiments, we use our implementation of L4, which we unit-test against the official Tensorflow implementation. In addition, we employ the official implementation of DFW2 and
  1https://github.com/martius-lab/l4-optimizer 2https://github.com/oval-group/dfw
  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).
sections.heading: 5.1 DIFFERENTIABLE NEURAL COMPUTERS
sections.text: 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 104 for each method except for L4Adam and L4Mom. For L4Adam and L4Mom, 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, L4Adam and L4Mom (as recommended by Rolinek & Martius (2018)).
  Results. We present the results in Figure 3. ALI-G provides accurate optimization for any η within [10−1, 106], and is among the best performing methods by reaching an objective function of 4.10−8. On this task, RMSProp, L4Adam and L4Mom 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 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.
sections.heading: 5.2 WIDE RESIDUAL NETWORKS ON SVHN
sections.text: 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 L4Adam and L4Mom, 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 L2 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 L2-norm of the parameters, and its maximal value is set to 50. SGD,
  3https://github.com/deepmind/dnc
  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, L4Mom 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.
sections.heading: 5.3 BI-LSTM ON SNLI
sections.text: 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 L4Adam and L4Mom, 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 L2 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.
sections.heading: 5.4 WIDE RESIDUAL NETWORKS AND DENSELY CONNECTED NETWORKS ON CIFAR
sections.text: 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 L4Adam, L4Mom, 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 L4Adam and L4Mom, 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 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 AdamW, the weight-decay is cross-validated as a power of 10. For ALI-G, L2 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.
sections.heading: 5.5 TRAINING PERFORMANCE
sections.text: 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 L2 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 WRNCIFAR and 300 epochs for DN-CIFAR, following (Zagoruyko & Komodakis, 2016) and (Huang et al., 2017). The L4 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.
sections.heading: 6 DISCUSSION
sections.text: 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 Nedić & Bertsekas (2001b) and Rolinek & Martius (2018).
sections.heading: A LOCAL INTERPRETATION OF THE POLYAK STEP-SIZE
sections.text: Proposition 2. Suppose that the problem is unconstrained: Ω = Rp. Let wt+1 = wt − f(wt)−f? ‖∇f(wt)‖2∇f(wt). Then wt+1 verifies:
  wt+1 = argmin w∈Rp
  ‖w −wt‖ subject to: f(wt) +∇f(wt)>(w −wt) = f?, (6)
  where we remind that f? is the minimum of f , and w 7→ f(wt) + ∇f(wt)>(w − wt) is the linearization of f at wt. In other words, wt+1 is the closest point to wt that lies on the hyper-plane f(wt) +∇f(wt)>(w −wt) = f?.
  Proof : See Appendix D.1
sections.heading: B CONVERGENCE RESULTS
sections.text: Before we detail our convergence results, we introduce the notions of uniform lower bound and ε-interpolation.
sections.heading: B.1 NOTATION
sections.text: Intuitively, a uniform lower bound on the problem (P) is a lower bound on all loss functions `z on their unconstrained domain Rp. We formalize this below: Definition 1 (Uniform Lower Bound). We say that B is a uniform lower bound on (P) if:
  B ≤ inf z∈Z inf w∈Rp `z(w). (7)
  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:
  ∀z ∈ Z, `z(w?)− B ≤ ε. (8)
  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:
  γt = min
  { `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ , η
  } (9)
  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.
sections.heading: B.2 LIPSCHITZ CONVEX FUNCTIONS
sections.text: 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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ ε √( C2
  δ + 1
  ) + ‖w0 −w?‖ √ C2 + δ√
  T + 1 . (10)
  Proof : See Appendix D.3.
  Theorem 3. We assume thatX is a convex set, and that for every z ∈ Z , `z is convex andC-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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) −f? ≤ ‖w0 −w?‖2
  (η − εδ )(T + 1) +
  ε2
  δ(η − εδ ) +
  √ (C2 + δ)‖w0 −w?‖2
  T + 1 +ε
  √ C2
  δ + 1.
  (11)
  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 thatX is a convex set, and that for every z ∈ Z , `z is convex andC-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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ ‖w0 −w?‖2
  η(T + 1) + ε+
  √ (C2 + δ)‖w0 −w?‖2
  T + 1 + ηε
  √ C2 + δ. (12)
  Proof : See Appendix D.5.
sections.heading: B.3 SMOOTH CONVEX FUNCTIONS
sections.text: We now tackle the convex and β-smooth case. Our proof techniques naturally produce the separation η ≥ 12β and η ≤ 1 2β . Whenever η ≥ 1 2β , the convergence result is exactly the same as when η →∞. When η ≤ 12β , 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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤
  δ
  β(1− 2βεδ ) +
  2β
  1− 2βεδ
  ‖w0 −w?‖2
  T + 1 . (13)
  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 η ≥ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤
  δ
  β(1− 2βεδ ) +
  2β
  1− 2βεδ
  ‖w0 −w?‖2
  T + 1 . (14)
  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 η ≤ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ ‖w0 −w?‖2
  η(T + 1) +
  δ
  2β + ε. (15)
  Proof : See Appendix D.8.
sections.heading: B.4 SMOOTH AND STRONGLY CONVEX FUNCTIONS
sections.text: Finally, we consider the α-strongly convex and β-smooth case. Again, our proof yields a natural separation between η ≥ 12β and η ≤ 1 2β . In a similar way to the β-smooth case, when η ≥ 1 2β , Theorem 9 gives the exact same result as η →∞. And when η ≤ 12β , 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:
  f(wT+1)− f? ≤ β exp ( −αT
  8β
  ) ‖w0 −w?‖2 + 2δ
  α +
  ( 10 β
  α + 4
  β2
  α2
  ) ε. (16)
  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 η ≥ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f(wT+1)− f? ≤ β exp ( −αT
  8β
  ) ‖w0 −w?‖2 + 2δ
  α +
  ( 10 β
  α + 4
  β2
  α2
  ) ε. (17)
  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 η ≤ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f(wT+1)− f? ≤ β exp ( −αηT
  4
  ) ‖w0 −w?‖2 + 2δ
  α +
  14εβ
  α . (18)
  Proof : See Appendix D.11.
sections.heading: C ON THE NEED FOR A MAXIMAL LEARNING-RATE FOR NON-CONVEXITY
sections.text: The Restricted Secant Inequality (RSI) is a milder assumption than convexity. It can be defined as follows: Definition 3. Let f : Rp → 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:
  ∀w ∈ Rp, ∇f(w)>(w −w?) ≥ α‖w −w?‖2. (19)
  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 ∈ [−35 ; 3 5 ] 7→ w 2 − |w|3. We restrict our domain of study to [−35 ; 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 α = 15 . 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,
  and −1 otherwise. Now let w ∈ [−35 ; 3 5 ]. Then we have that:
  ∇f(w)(w − w?)− 1
  5 (w − w?)2, = (2w − 3σ(w)w2)(w − 0)−
  1 5 (w − 0)2,
  = 9
  5 w2 − 3σ(w)w3,
  = 3w2( 3
  5 − σ(w)w),
  ≥ 0.
  (20)
  Now let us show that if we apply gradient descent with a Polyak step-size to f , with starting point w0 = −3 5 , we obtain w1 = 3 5 . This will prove oscillation of the iterates by symmetry of the problem. Let w0 = −35 . Then we have f(w0) = 9 25 − 27 125 = 18 125 . Furthermore, ∇f(w0) = 2( −3 5 ) + 3( 9 25 ) = −3 25 . Therefore:
  w1 = w0 − f(w0)− 0 (∇f(w0))2 ∇f(w0),
  = w0 − f(w0)
  ∇f(w0) ,
  = −3 5 + 18 125 3 25 , = −3 5 + 6 5 , = 3
  5 .
  (21)
sections.heading: D PROOFS
sections.heading: D.1 PROPOSITION 2
sections.text: Proposition 2. Suppose that the problem is unconstrained: Ω = Rp. Let wt+1 = wt − f(wt)−f? ‖∇f(wt)‖2∇f(wt). Then wt+1 verifies:
  wt+1 = argmin w∈Rp
  ‖w −wt‖ subject to: f(wt) +∇f(wt)>(w −wt) = f?, (6)
  where we remind that f? is the minimum of f , and w 7→ f(wt) + ∇f(wt)>(w − wt) is the linearization of f at wt. In other words, wt+1 is the closest point to wt that lies on the hyper-plane f(wt) +∇f(wt)>(w −wt) = 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 ŵ ∈ Rp a solution of the linear equality constraint, and we will show that ‖wt+1 − wt‖ ≤ ‖ŵ −wt‖. By definition, we have that ŵ satisfies:
  f(wt) +∇f(wt)>(ŵ −wt) = f?. (23)
  Now we can write:
  ‖wt+1 −wt‖ = ‖ f(wt)− f? ‖∇f(wt)‖2 ∇f(wt)‖,
  = f(wt)− f? ‖∇f(wt)‖ , = |∇f(wt)>(ŵ −wt)|
  ‖∇f(wt)‖ ,
  ≤ ||∇f(wt)‖‖ŵ −wt‖‖∇f(wt)‖ , (Cauchy-Schwarz)
  = ‖ŵ −wt‖.
  (24)
sections.heading: D.2 THEOREM 1
sections.text: Proposition 1. [Proximal Interpretation] Suppose that Ω = Rp and let δ = 0. We consider the update performed by SGD: wSGDt+1 = wt − ηt∇`zt(wt); and the update performed by ALI-G: wALI-Gt+1 = wt − γt∇`zt(wt), where γt = min { `zt (wt) ‖∇`zt (wt)‖2+δ , η } . Then we have:
  wSGDt+1 = argmin w∈Rp { 1 2ηt ‖w −wt‖2 + `zt(wt) +∇`zt(wt)>(w −wt) } , (4)
  wALI-Gt+1 = argmin w∈Rp { 1 2η ‖w −wt‖2 + max { `zt(wt) +∇`zt(wt)>(w −wt), 0 }} . (5)
  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 , ∇`zt(wt) and lt , `zt(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 6= 0.
  We can successively re-write the proximal problem (5) as :
  min w∈Rp
  { 1
  2η ‖w −wt‖2 + max
  { `zt(wt) +∇`zt(wt) >(w −wt), B }} ,
  min w∈Rp
  { 1
  2η ‖w −wt‖2 + max
  { `zt(wt)− B +∇`zt(wt) >(w −wt), 0 }} ,
  min w∈Rp
  { 1
  2η ‖w −wt‖2 + max
  { lt + d > t (w −wt), 0 }} ,
  min w∈Rp,υ
  { 1
  2η ‖w −wt‖2 + υ
  } subject to: υ ≥ 0, υ ≥ lt + d>t (w −wt)
  min w∈Rp,υ sup µ,ν≥0
  { 1
  2η ‖w −wt‖2 + υ − µυ − ν(υ − lt − d>t (w −wt)) } sup µ,ν≥0 min w∈Rp,υ { 1 2η ‖w −wt‖2 + υ − µυ − ν(υ − lt − d>t (w −wt)) } (strong duality) (25)
  The inner problem is now smooth in w and υ. We write its KKT conditions:
  ∂· ∂υ = 0 : 1− µ− ν = 0 (26)
  ∂· ∂w = 0 : 1 η (w −wt) + νdt = 0 (27)
  We plug in these results and obtain:
  sup µ,ν≥0
  { 1
  2η ‖ηνdt‖2 + ν(lt + d>t (−ηνdt)) } st: µ+ ν = 1
  sup ν∈[0,1] {η 2 ν2‖dt‖2 + νlt − ην2‖d>t ‖2 } sup ν∈[0,1] { −η 2 ν2‖dt‖2 + νlt } (28)
  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:
  ∂· ∂ν = 0 : −ην‖dt‖2 + lt = 0 (29)
  Since dt 6= 0 and η 6= 0, this gives the optimal solution:
  ν = min { max { lt
  η‖dt‖2 , 0
  } , 1 } = min { lt
  η‖dt‖2 , 1
  } , (30)
  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:
  wt+1 = wt − ηνdt, = wt − ηmin {
  lt η‖dt‖2 , 1
  } dt,
  = wt − ηmin {
  `zt(wt)− B η‖∇`zt(wt)‖2 , 1
  } ∇`zt(wt),
  = wt −min { `zt(wt)− B ‖∇`zt(wt)‖2 , η } ∇`zt(wt).
  (31)
sections.heading: D.3 THEOREM 2
sections.text: 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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ ε √( C2
  δ + 1
  ) + ‖w0 −w?‖ √ C2 + δ√
  T + 1 . (10)
sections.heading: Proof :
sections.text: We consider the update at time t, which we condition on the draw of zt ∈ Z:
  ‖wt+1 −w?‖2
  = ‖ΠΩ(wt − γt∇`zt(wt))−w?‖ 2
  ≤ ‖wt − γt∇`zt(wt)−w?‖ 2 (ΠΩ projection) = ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γ2t ‖∇`zt(wt)‖ 2
  = ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γt `zt(wt)− B ‖∇`zt(wt)‖2 + δ ‖∇`zt(wt)‖ 2
  (definition of γt)
  ≤ ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γt `zt(wt)− B ‖∇`zt(wt)‖2 ‖∇`zt(wt)‖ 2
  (because `zt(wt)− B ≥ 0 and δ ≥ 0) ≤ ‖wt −w?‖2 − 2γt(`zt(wt)− `zt(w?)) + γt(`zt(wt)− B) (convexity of `zt )
  = ‖wt −w?‖2 − γt ( (`zt(wt)− `zt(w?))− (`zt(w?)− B) )
  = ‖wt −w?‖2 − 1
  ‖∇`zt(wt)‖2 + δ
  ( (`zt(wt)− B)(`zt(wt)− `zt(w?))
  − (`zt(wt)− B)(`zt(w?)− B) ) (definition of γt)
  = ‖wt −w?‖2 − 1
  ‖∇`zt(wt)‖2 + δ
  ( (`zt(wt)− `zt(w?))(`zt(wt)− `zt(w?))
  + (`zt(w?)− B)(`zt(wt)− `zt(w?))− (`zt(wt)− `zt(w?))(`zt(w?)− B) − (`zt(w?)− B)(`zt(w?)− B) )
  (we use twice `zt(wt)− B = `zt(wt)− `zt(w?) + `zt(w?)− B)
  = ‖wt −w?‖2 − 1
  ‖∇`zt(wt)‖2 + δ
  ( (`zt(wt)− `zt(w?)) 2 − (`zt(w?)− B) 2 )
  (middle terms cancel out)
  = ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2
  ‖∇`zt(wt)‖2 + δ +
  (`zt(w?)− B)2
  ‖∇`zt(wt)‖2 + δ
  ≤ ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2
  C2 + δ +
  (`zt(w?)− B)2
  δ (0 ≤ ‖∇`zt(wt)‖ 2 ≤ C)
  ≤ ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2 C2 + δ + ε2 δ (definition of ε) (32)
  We re-write this inequality as:
  (`zt(wt)− `zt(w?)) 2 ≤ ε2
  ( C2
  δ + 1
  ) + ( C2 + δ ) ( ‖wt −w?‖2 − ‖wt+1 −w?‖2 ) (33)
  We can now use the Cauchy-Schwarz inequality to bound the sum over the iterations:
  (T + 1) T∑ t=0 (`zt(wt)− `zt(w?)) 2 ≥ ( T∑ t=0 `zt(wt)− `zt(w?) )2 (34)
  Therefore we can write:( T∑ t=0 `zt(wt)− `zt(w?) )2
  ≤ (T + 1) T∑ t=0 (`zt(wt)− `zt(w?)) 2
  ≤ (T + 1)2 ε2 ( C2
  δ + 1
  ) + (T + 1) ( C2 + δ ) ( ‖w0 −w?‖2 − ‖wT+1 −w?‖2 ) ,
  ≤ (T + 1)2 ε2 ( C2
  δ + 1
  ) + (T + 1) ( C2 + δ ) ‖w0 −w?‖2,
  (35)
  which yields:
  T∑ t=0 `zt(wt)− `zt(w?) ≤
  √ (T + 1)2 ε2 ( C2
  δ + 1
  ) + (T + 1) (C2 + δ) ‖w0 −w?‖2,
  ≤ (T + 1) ε √ C2
  δ + 1 +
  √ (T + 1) (C2 + δ) ‖w0 −w?‖2,
  (36)
  We can now take the expectation over the zt:
  T∑ t=0 f(wt)− f? ≤ (T + 1) ε √ C2 δ + 1 + √ (T + 1) (C2 + δ) ‖w0 −w?‖2. (37)
  Dividing by T + 1 and exploiting convexity of f , we finally get:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ 1
  T + 1 T∑ t=0 f(wt)− f? (convexity of f )
  ≤ ε √ C2
  δ + 1 +
  √( C2 + δ ) ‖w0 −w?‖2
  T + 1 .
  (38)
sections.heading: D.4 THEOREM 3
sections.text: Theorem 3. We assume thatX is a convex set, and that for every z ∈ Z , `z is convex andC-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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) −f? ≤ ‖w0 −w?‖2
  (η − εδ )(T + 1) +
  ε2
  δ(η − εδ ) +
  √ (C2 + δ)‖w0 −w?‖2
  T + 1 +ε
  √ C2
  δ + 1.
  (11)
sections.heading: Proof :
sections.text: We consider the update at time t, which we condition on the draw of zt ∈ Z:
  ‖wt+1 −w?‖2
  = ‖ΠΩ(wt − γt∇`zt(wt))−w?‖ 2
  ≤ ‖wt − γt∇`zt(wt)−w?‖ 2 (ΠΩ projection) = ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γ2t ‖∇`zt(wt)‖ 2
  ≤ ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γt `zt(wt)− B ‖∇`zt(wt)‖2 + δ ‖∇`zt(wt)‖ 2
  (because γt ≤ `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ )
  ≤ ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γt `zt(wt)− B ‖∇`zt(wt)‖2 ‖∇`zt(wt)‖ 2
  (because `zt(wt)− B ≥ 0 and δ ≥ 0) ≤ ‖wt −w?‖2 − 2γt(`zt(wt)− `zt(w?)) + γt(`zt(wt)− B) (convexity of `zt ) = ‖wt −w?‖2 − 2γt(`zt(wt)− `zt(w?)) + γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) = ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) (39)
  We now consider different cases, according to the value that γt takes: γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ or γt = η.
  First, suppose that γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ . Then we can follow the proof of Theorem 2 to obtain:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2 C2 + δ + ε2 δ . (40)
  Now suppose γt = η and `zt(wt)− `zt(w?) ≤ 0. We can use γt ≤ `zt (wt)−B
  ‖∇`zt (wt)‖2+δ to write:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B),
  ≤ ‖wt −w?‖2 − `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ (`zt(wt)− `zt(w?))
  + `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ (`zt(w?)− B),
  (41)
  where the last inequality has used γt ≤ `zt (wt)−B
  ‖∇`zt (wt)‖2+δ , `zt(wt) − `zt(w?) ≤ 0 and `zt(w?) −
  B ≥ 0. Therefore we are exactly in the same situation as the first case (where we used γt = `zt (wt)−B ‖∇`zt (wt)‖2+δ ), and thus we have again:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2 C2 + δ + ε2 δ . (42)
  Now suppose that γt = η and `zt(wt)− `zt(w?) ≥ 0. The inequality (39) gives:
  ‖wt+1 −w?‖2
  ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B), = ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B), (γt = η) ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + γtε. (definition of ε, γt ≥ 0)
  ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ε `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ ,
  (because γt ≤ `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ , ε ≥ 0)
  ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ε `zt(wt)− B
  δ , (‖∇`zt(wt)‖ 2 ≥ 0)
  = ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ε `zt(wt)− `zt(w?) + `zt(w?)− B
  δ ,
  ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ε `zt(wt)− `zt(w?) + ε
  δ ,
  (because `zt(w?)− B ≤ ε) = ‖wt −w?‖2 − ( η − ε
  δ
  ) (`zt(wt)− `zt(w?)) + ε2
  δ .
  (43)
  We now introduce IT and JT as follows:
  IT , {t ∈ {0, ..., T} : γt = η and `zt(wt)− `zt(w?) ≥ 0} JT , {0, ..., T} \ IT
  (44)
  Then, by combining inequalities (40), (42) and (43), and using a telescopic sum, we obtain:
  ‖wT+1 −w?‖2 ≤ ‖w0 −w?‖2 + ∑ t∈JT ( − (`zt(wt)− `zt(w?)) 2 C2 + δ + ε2 δ )
  + ∑ t∈IT ( − ( η − ε δ ) (`zt(wt)− `zt(w?)) + ε2 δ ) (45)
  Using ‖wT+1 −w?‖2 ≥ 0, we obtain:
  1
  C2 + δ ∑ t∈JT (`zt(wt)−`zt(w?)) 2 + ( η − ε δ ) ∑ t∈IT (`zt(wt)−`zt(w?)) ≤ ‖w0−w?‖ 2 +(T +1) ε2 δ
  (46)
  In particular, the inequality (46) gives that:( η − ε
  δ ) ∑ t∈IT (`zt(wt)− `zt(w?)) ≤ ‖w0 −w?‖ 2 + (T + 1) ε2 δ . (47)
  Furthermore, for every t ∈ IT , we have (`zt(wt)−`zt(w?)) ≥ 0, which yields ( η − ε
  δ ) ∑ t∈IT (`zt(wt)−
  `zt(w?)) ≥ 0 since η > δ . Thus the inequality (46) also gives:
  1
  C2 + δ ∑ t∈JT (`zt(wt)− `zt(w?)) 2 ≤ ‖w0 −w?‖2 + (T + 1) ε2 δ . (48)
  Using the Cauchy-Schwarz inequality, we can further write:∑ t∈JT `zt(wt)− `zt(w?) 2 ≤ |JT | ∑ t∈JT (`zt(wt)− `zt(w?)) 2. (49)
  Therefore we have:∑ t∈JT `zt(wt)− `zt(w?) ≤ √ |JT | ∑ t∈JT (`zt(wt)− `zt(w?))2,
  ≤ √ |JT |(C2 + δ) ( ‖w0 −w?‖2 + (T + 1) ε2
  δ
  ) .
  (50)
  We can now put together inequalities (47) and (49) by writing:
  T∑ t=0 `zt(wt)− `zt(w?)
  = ∑ t∈IT `zt(wt)− `zt(w?) + ∑ t∈JT `zt(wt)− `zt(w?)
  ≤ 1 η − ε
  δ
  ( ‖w0 −w?‖2 + (T + 1) ε2
  δ
  ) + √ |JT |(C2 + δ) ( ‖w0 −w?‖2 + (T + 1) ε2
  δ
  )
  ≤ 1 η − ε
  δ
  ( ‖w0 −w?‖2 + (T + 1) ε2
  δ
  ) + √ (T + 1)(C2 + δ) ( ‖w0 −w?‖2 + (T + 1) ε2
  δ ) (51)
  Dividing by T + 1 and taking the expectation, we obtain:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ 1
  T + 1 T∑ t=0 f(wt)− f?, (f is convex)
  ≤ ‖w0 −w?‖ 2
  (η − ε δ )(T + 1)
  + ε2
  δ(η − ε δ )
  + √ (C2 + δ) ( ‖w0 −w?‖2
  T + 1 + ε2 δ
  ) ,
  ≤ ‖w0 −w?‖ 2
  (η − ε δ )(T + 1)
  + ε2
  δ(η − ε δ )
  +
  √ (C2 + δ)‖w0 −w?‖2
  T + 1
  + ε
  √ C2
  δ + 1.
  (52)
sections.heading: D.5 THEOREM 4
sections.text: Theorem 4. We assume thatX is a convex set, and that for every z ∈ Z , `z is convex andC-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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ ‖w0 −w?‖2
  η(T + 1) + ε+
  √ (C2 + δ)‖w0 −w?‖2
  T + 1 + ηε
  √ C2 + δ. (12)
sections.heading: Proof :
sections.text: We consider the update at time t, which we condition on the draw of zt ∈ Z . We re-use the inequality (39) from the proof of Theorem 3:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) (53)
  We consider again different cases, according to the value of γt and the sign of `zt(wt)− `zt(w?).
  Suppose that `zt(wt)− `zt(w?) ≤ 0. Then the inequality (53) gives:
  ‖wt+1 −w?‖2
  ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B), ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B),
  (because γt ≤ η, `zt(wt)− `zt(w?) ≤ 0) ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + γtε, (definition of ε, γt ≥ 0) ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ηε, (γt ≤ η, ε ≥ 0)
  (54)
  Now suppose `zt(wt)− `zt(w?) ≥ 0 and γt = η. Then the inequality (53) gives:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B), = ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + η(`zt(w?)− B), (γt = η) ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ηε, (definition of ε, η ≥ 0) (55)
  Finally, suppose that `zt(wt) − `zt(w?) ≥ 0 and γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ . Then the inequality (53)
  gives:
  ‖wt+1 −w?‖2
  ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B), ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + η(`zt(w?)− B), (γt ≤ η, `zt(w?)− B ≥ 0) ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + ηε, (definition of ε, η ≥ 0)
  = ‖wt −w?‖2 − `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ (`zt(wt)− `zt(w?)) + ηε, (γt = `zt(wt)− B ‖∇`zt(wt)‖2 + δ )
  ≤ ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2
  ‖∇`zt(wt)‖2 + δ + ηε, (`zt(wt)− B ≥ `zt(wt)− `zt(w?) ≥ 0)
  ≤ ‖wt −w?‖2 − (`zt(wt)− `zt(w?))2
  C2 + δ + ηε, (‖∇`zt(wt)‖ 2 ≤ C2) (56)
  We now introduce IT and JT as follows: JT , { t ∈ {0, ..., T} : γt =
  `zt(wt)− B ‖∇`zt(wt)‖2 + δ
  and `zt(wt)− `zt(w?) ≥ 0 }
  IT , {0, ..., T} \ IT (57)
  Then, by combining inequalities (54), (55) and (56), and using a telescopic sum, we obtain:
  ‖wT+1 −w?‖2 ≤ ‖w0 −w?‖2 + ∑ t∈JT ( − (`zt(wt)− `zt(w?)) 2 C2 + δ + ηε ) + ∑ t∈IT (−η(`zt(wt)− `zt(w?)) + ηε) (58)
  Using ‖wT+1 −w?‖2 ≥ 0, we obtain:
  1
  C2 + δ ∑ t∈JT (`zt(wt)− `zt(w?)) 2 + η ∑ t∈IT (`zt(wt)− `zt(w?)) ≤ ‖w0 −w?‖ 2 + (T + 1)ηε (59)
  We now take the expectation and obtain:
  1
  C2 + δ ∑ t∈JT E [ (`zt(wt)− `zt(w?)) 2]+ η ∑ t∈IT (f(wt)− f?) ≤ ‖w0 −w?‖2 + (T + 1)ηε (60)
  Since E[U ]2 ≤ E[U2] for any real-valued random variable, we can write:
  1
  C2 + δ ∑ t∈JT (f(wt)− f?)2 + η ∑ t∈IT (f(wt)− f?) ≤ ‖w0 −w?‖2 + (T + 1)ηε (61)
  Since each f(wt)− f? ≥ 0, the inequality (61) gives that: η ∑ t∈IT (f(wt)− f?) ≤ ‖w0 −w?‖2 + (T + 1)ηε, (62)
  and: 1
  C2 + δ ∑ t∈JT (f(wt)− f?)2 ≤ ‖w0 −w?‖2 + (T + 1)ηε. (63)
  Using the Cauchy-Schwarz inequality, we can further write:∑ t∈JT f(wt)− f? 2 ≤ |JT | ∑ t∈JT (f(wt)− f?)2. (64)
  Therefore we have:∑ t∈JT f(wt)− f? ≤ √ |JT | ∑ t∈JT (f(wt)− f?)2,
  ≤ √ |JT |(C2 + δ) (‖w0 −w?‖2 + (T + 1)ηε).
  (65)
  We can now put together inequalities (62) and (65) by writing:
  T∑ t=0 f(wt)− f?
  = ∑ t∈IT f(wt)− f? + ∑ t∈JT f(wt)− f?
  ≤ 1 η
  ( ‖w0 −w?‖2 + (T + 1)ηε ) + √ |JT |(C2 + δ) (‖w0 −w?‖2 + (T + 1)ηε)
  ≤ 1 η
  ( ‖w0 −w?‖2 + (T + 1)ηε ) + √ (T + 1)(C2 + δ) (‖w0 −w?‖2 + (T + 1)ηε)
  (66)
  Dividing by T + 1, we obtain:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ 1
  T + 1 T∑ t=0 f(wt)− f?, (f is convex)
  ≤ ‖w0 −w?‖ 2
  η(T + 1) + ε+
  √ (C2 + δ) ( ‖w0 −w?‖2
  T + 1 + ηε
  ) ,
  ≤ ‖w0 −w?‖ 2
  η(T + 1) + ε+
  √ (C2 + δ)‖w0 −w?‖2
  T + 1 + ηε
  √ C2 + δ.
  (67)
sections.heading: D.6 THEOREM 5
sections.text: Lemma 1. Let z ∈ Z . Assume that `z is convex, β-smooth and is lower-bounded on Rp by B ∈ R. Then we have:
  ∀w ∈ Rp, `z(w)− B ≥ 1
  2β ‖∇`z(w)‖2 (68)
  Proof : Let w ∈ Rp and suppose that `z reaches its infimum at w ∈ (R ∪ {−∞,+∞})p.
  First, let us consider the case w ∈ Rp. Then by Lemma 3.5 of Bubeck (2015), we have:
  `z(w)− `z(w) ≤ ∇`z(w)>(w −w)− 1
  2β ‖∇`z(w)−∇`z(w)‖2,
  = − 1 2β ‖∇`z(w)‖2 (∇`z(w) = 0).
  (69)
  Therefore we can write:
  `z(w)− B ≥ `z(w)− `z(w) ≥ 1
  2β ‖∇`z(w)‖2. (70)
  Now let us assume that w /∈ Rp. Then we can construct a sequence (wk)k∈N ∈ (R p)N that converges to w. Since `z and∇`z are continuous functions (they are respectively convex and smooth), we have:
  lim k→∞ `z(wk) = inf `z,
  lim k→∞
  ∇`z(wk) = 0. (71)
  Therefore the previous case gives the wanted result by using wk 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 Rp by B ∈ R. Then we have:
  ∀w ∈ Rp, `z(w)− B ‖∇`z(w)‖2 + δ ≥ 1 2β − δ 4β2(`z(w)− B)) (72)
sections.heading: Proof :
sections.text: Let w ∈ Rp. We apply Lemma 1 and we write successively:
  `z(w)− B ‖∇`z(w)‖2 + δ ≥ `z(w)− B 2β(`z(w)− B) + δ , (Lemma 1)
  = `z(w)− B + δ2β − δ 2β
  2β(`z(w)− B + δ2β ) ,
  = 1
  2β −
  δ 2β
  2β(`z(w)− B + δ2β ) ,
  ≥ 1 2β − δ 4β2(`z(w)− B) . (δ ≥ 0)
  (73)
  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:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤
  δ
  β(1− 2βεδ ) +
  2β
  1− 2βεδ
  ‖w0 −w?‖2
  T + 1 . (13)
sections.heading: Proof :
sections.text: We consider the update at time t, which we condition on the draw of zt ∈ Z:
  ‖wt+1 −w?‖2
  = ‖ΠΩ(wt − γt∇`zt(wt))−w?‖ 2
  ≤ ‖wt − γt∇`zt(wt)−w?‖ 2 (ΠΩ projection) = ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γ2t ‖∇`zt(wt)‖ 2
  = ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γt `zt(wt)− B ‖∇`zt(wt)‖2 + δ ‖∇`zt(wt)‖ 2
  (definition of γt)
  ≤ ‖wt −w?‖2 − 2γt∇`zt(wt) >(wt −w?) + γt `zt(wt)− B ‖∇`zt(wt)‖2 ‖∇`zt(wt)‖ 2
  (because `zt(wt)− B ≥ 0 and δ ≥ 0) ≤ ‖wt −w?‖2 − 2γt(`zt(wt)− `zt(w?)) + γt(`zt(wt)− B) (convexity of `zt ) = ‖wt −w?‖2 − 2γt(`zt(wt)− `zt(w?)) + γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) = ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) (74)
  We now lower bound γt(`zt(wt)− `zt(w?)) and upper bound γt(`zt(w?)− B) individually.
  We begin with γt(`zt(wt)− `zt(w?)), for which we distinguish two cases according to its sign:
  Suppose (`zt(wt)− `zt(w?)) ≥ 0. Then we can write:
  γt(`zt(wt)− `zt(w?))
  = `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ (`zt(wt)− `zt(w?)), (definition of γt) ≥ ( 1
  2β − δ 4β2(`z(wt)− B)
  ) (`zt(wt)− `zt(w?)) (Lemma 2, (`zt(wt)− `zt(w?)) ≥ 0)
  = 1
  2β (`zt(wt)− `zt(w?))−
  δ 4β2 `zt(wt)− `zt(w?)
  (`zt(wt)− B)
  ≥ 1 2β (`zt(wt)− `zt(w?))− δ 4β2 (`zt(w?) ≥ B, (`zt(wt)− `zt(w?)) ≥ 0)
  (75)
  Now suppose (`zt(wt)− `zt(w?)) ≤ 0, and let us show that the same result holds. We have:
  γt = `zt(wt)− B
  ‖∇`zt(wt)‖2 + δ
  ≤ `zt(w?)− B‖∇`zt(wt)‖2 + δ ((`zt(wt)− `zt(w?)) ≤ 0) ≤ ε‖∇`zt(wt)‖2 + δ (definition of ε) ≤ ε δ (‖∇`zt(wt)‖ ≥ 0) ≤ 1 2β (δ ≥ 2βε)
  (76)
  Therefore we have:
  γt(`zt(wt)− `zt(w?))
  ≥ 1 2β (`zt(wt)− `zt(w?)) ((`zt(wt)− `zt(w?)) ≤ 0)
  ≥ 1 2β (`zt(wt)− `zt(w?))− δ 4β2 (δ ≥ 0)
  (77)
  In conclusion, regardless of the sign, it always holds true that:
  γt(`zt(wt)− `zt(w?)) ≥ 1
  2β (`zt(wt)− `zt(w?))−
  δ
  4β2 (78)
  We now upper bound γt(`zt(w?)− B):
  γt(`zt(w?)− B) = (`zt(wt)− B)(`zt(w?)− B)
  ‖∇`zt(wt)‖2 + δ , (definition of γt)
  ≤ (`zt(wt)− B)(`zt(w?)− B) δ , (‖∇`zt(wt)‖ ≥ 0) ≤ (`zt(wt)− `zt(w?) + ε)ε δ , (definition of ε twice)
  = ε
  δ ((`zt(wt)− `zt(w?)) +
  ε2
  δ .
  (79)
  Putting inequalities (74), (78) and (79) together, we obtain:
  ‖wt+1−w?‖2 ≤ ‖wt−w?‖2− 1
  2β (`zt(wt)−`zt(w?))+
  δ 4β2 + ε δ ((`zt(wt)−`zt(w?))+
  ε2
  δ . (80)
  Therefore we have:( 1
  2β − ε δ
  ) (`zt(wt)− `zt(w?))− ( δ
  4β2 + ε2 δ
  ) ≤ ‖wt −w?‖2 − ‖wt+1 −w?‖2. (81)
  By summing over t and taking the expectation over the zt, we obtain:
  δ − 2βε 2βδ T∑ t=0 ( f(wt)− f(w?)− δ2 + 4β2ε2 4β2δ ) ≤ ‖w0−w?‖2−E [ ‖wT+1 −w?‖2 ] ≤ ‖w0−w?‖2.
  (82)
  By assumption, we have that δ − 2βε > 0. Dividing by T + 1 and using the convexity of f , we finally obtain:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ 1
  T + 1 T∑ t=0 f(wt)− f? (convexity of f ),
  = 2βδ δ − 2βε δ2 + 4β2ε2 4β2δ + 2βδ δ − 2βε ‖w0 −w?‖2 T + 1 ,
  = δ2 + 4β2ε2 2β(δ − 2βε) + 2βδ δ − 2βε ‖w0 −w?‖2 T + 1 ,
  ≤ δ 2 β(δ − 2βε) + 2βδ δ − 2βε ‖w0 −w?‖2 T + 1 , (δ − 2βε ≥ 0)
  = δ
  β(1− 2βε δ
  ) +
  2β
  1− 2βε δ
  ‖w0 −w?‖2
  T + 1 .
  (83)
sections.heading: D.7 THEOREM 6
sections.text: 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 η ≥ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤
  δ
  β(1− 2βεδ ) +
  2β
  1− 2βεδ
  ‖w0 −w?‖2
  T + 1 . (14)
sections.heading: Proof :
sections.text: By using the fact that γt ≤ `zt (wt)−B
  ‖∇`zt (wt)‖2+δ rather than γt = `zt (wt)−B ‖∇`zt (wt)‖2+δ
  , we can see that the inequality (74) is still valid:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) (84)
  As previously, we lower bound γt(`zt(wt)− `zt(w?)) and upper bound γt(`zt(w?)− B) individually.
  We begin with γt(`zt(wt)− `zt(w?)). We remark that either γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ or γt = η.
  Suppose γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ and `zt(wt)− `zt(w?) ≥ 0. Then we are in the same condition as in
  Theorem 5, and thus the inequality (78) holds true:
  γt(`zt(wt)− `zt(w?)) ≥ 1
  2β (`zt(wt)− `zt(w?))−
  δ
  4β2 . (85)
  Now suppose γt = η and `zt(wt)− `zt(w?) ≥ 0. Then we have:
  γt(`zt(wt)− `zt(w?)) = η(`zt(wt)− `zt(w?))
  ≥ η(`zt(wt)− `zt(w?))− δ
  4β2
  ≥ 1 2β (`zt(wt)− `zt(w?))− δ 4β2
  (because η ≥ 1 2β , `zt(wt)− `zt(w?) ≥ 0). (86)
  Now suppose `zt(wt) − `zt(w?) ≤ 0. By using γt ≤ `zt (wt)−B
  ‖∇`zt (wt)‖2+δ instead of γt =
  `zt (wt)−B ‖∇`zt (wt)‖2+δ , we can see that the inequality (76) is still valid, which gives:
  γt ≤ 1
  2β (87)
  We now use `zt(wt)− `zt(w?) ≤ 0 to write:
  γt (`zt(wt)− `zt(w?)) ≥ 1
  2β (`zt(wt)− `zt(w?)) (`zt(wt)− `zt(w?) ≤ 0)
  ≥ 1 2β (`zt(wt)− `zt(w?))− δ 4β2
  (88)
  In conclusion, in all cases, it holds true that:
  γt(`zt(wt)− `zt(w?)) ≥ 1
  2β (`zt(wt)− `zt(w?))−
  δ
  4β2 (89)
  By using γt ≤ `zt (wt)−B
  ‖∇`zt (wt)‖2+δ , we can remark that the inequality (79) holds true and gives:
  γt(`zt(w?)− B) ≤ ε
  δ ((`zt(wt)− `zt(w?)) +
  ε2
  δ . (90)
  We now put together inequalities (84), (89) and (90):
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − 1
  2β (`zt(wt)− `zt(w?)) +
  δ 4β2 + ε δ ((`zt(wt)− `zt(w?)) +
  ε2
  δ , = ‖wt −w?‖2 − ( 1
  2β − ε δ
  ) (`zt(wt)− `zt(w?)) + δ
  4β2 + ε2 δ .
  (91)
  This is exactly the same result as in the inequality (81) from the proof of Theorem 5. Therefore the rest of the proof of Theorem 5 follows and we obtain the desired result.
sections.heading: D.8 THEOREM 7
sections.text: 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 η ≤ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) − f? ≤ ‖w0 −w?‖2
  η(T + 1) +
  δ
  2β + ε. (15)
sections.heading: Proof :
sections.text: By using the fact that γt ≤ `zt (wt)−B
  ‖∇`zt (wt)‖2+δ rather than γt = `zt (wt)−B ‖∇`zt (wt)‖2+δ
  , we can see that the inequality (74) is still valid:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − γt(`zt(wt)− `zt(w?)) + γt(`zt(w?)− B) (92)
  As previously, we lower bound γt(`zt(wt)− `zt(w?)) and upper bound γt(`zt(w?)− B) individually.
  We begin with γt(`zt(wt)− `zt(w?)). We remark that either γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ or γt = η.
  Suppose γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ and `zt(wt)− `zt(w?) ≥ 0. First we write:
  γt = `zt(wt)− B ‖`zt(wt)‖2 + δ
  = `zt(wt)− B + δ2β ‖`zt(wt)‖2 + δ − δ 2β ‖`zt(wt)‖2 + δ
  ≥ ‖`zt (wt)‖
  2
  2β + δ 2β
  ‖`zt(wt)‖2 + δ − δ 2β
  1
  ‖`zt(wt)‖2 + δ (Lemma 1)
  = 1 2β − δ 2β
  1
  ‖`zt(wt)‖2 + δ
  ≥ η − δ 2β
  1 ‖`zt(wt)‖2 + δ (η ≤ 1 2β )
  (93)
  Since `zt(wt)− `zt(w?) ≥ 0, this yields: γt(`zt(wt)− `zt(w?)) ≥ ( η − δ
  2β
  1
  ‖`zt(wt)‖2 + δ
  ) (`zt(wt)− `zt(w?))
  = η(`zt(wt)− `zt(w?))− δ
  2β `zt(wt)− `zt(w?) ‖`zt(wt)‖2 + δ
  ≥ η(`zt(wt)− `zt(w?))− δ
  2β `zt(wt)− B ‖`zt(wt)‖2 + δ (`zt(w?) ≥ B)
  (94)
  We now notice that since γt = `zt (wt)−B
  ‖∇`zt (wt)‖2+δ , and γt ≤ η, then necessarily `zt (wt)−B ‖∇`zt (wt)‖2+δ
  ≤ η. This gives:
  γt(`zt(wt)− `zt(w?)) ≥ η(`zt(wt)− `zt(w?))− ηδ
  2β (95)
  Now suppose γt = η and `zt(wt)− `zt(w?) ≥ 0. Then we have:
  γt(`zt(wt)− `zt(w?)) = η(`zt(wt)− `zt(w?))
  ≥ η(`zt(wt)− `zt(w?))− ηδ
  2β . (96)
  Now suppose `zt(wt)− `zt(w?) ≤ 0. Since γt ≤ η by definition, we have that:
  γt (`zt(wt)− `zt(w?)) ≥ η(`zt(wt)− `zt(w?)) (`zt(wt)− `zt(w?) ≤ 0)
  ≥ η(`zt(wt)− `zt(w?))− ηδ
  2β .
  (97)
  In conclusion, in all cases, it holds true that:
  γt(`zt(wt)− `zt(w?)) ≥ η(`zt(wt)− `zt(w?))− ηδ
  2β (98)
  We upper bound γt(`zt(w?)− B) as follows:
  γt(`zt(w?)− B) ≤ η(`zt(w?)− B) (`zt(w?) ≥ B) ≤ ηε (definition of ε)
  (99)
  We combine inequalities (92), (98) and (99) and obtain:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ηδ
  2β + ηε. (100)
  By taking the expectation and using a telescopic sum, we obtain:
  0 ≤ ‖wT+1 −w?‖2 ≤ ‖w0 −w?‖2 − T∑ t=0 ( η(f(wt)− f?) + ηδ 2β + ηε ) . (101)
  Re-arranging and using the convexity of f , we finally obtain:
  f
  ( 1
  T + 1 T∑ t=0 wt
  ) ≤ ‖w0 −w?‖ 2
  η(T + 1) +
  δ
  2β + ε. (102)
sections.heading: D.9 THEOREM 8
sections.text: Lemma 3. For any a, b ∈ Rp, we have that:
  ‖a‖2 + ‖b‖2 ≥ 1 2 ‖a− b‖2 (103)
  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
  Lemma 4. Let z ∈ Z . Assume that `z is α-strongly convex and is lower-bounded on Rp by B ∈ R such that inf `z − B ≤ ε. In addition, suppose that δ ≥ 2αε. Then we have:
  ∀w ∈ Rp, `z(w)− B ‖∇`z(w)‖2 + δ ≤ 1 2α . (104)
sections.heading: Proof :
sections.text: Let w ∈ Rp and suppose that `z reaches its minimum at w ∈ Rp (this minimum exists because of strong convexity). By definition of strong convexity, we have that:
  ∀ ŵ ∈ Rp, `z(ŵ) ≥ `z(w) +∇`z(w)>(ŵ −w) + α
  2 ‖ŵ −w‖2 (105)
  We minimize the right hand-side over ŵ, which gives:
  ∀ŵ ∈ Rp, `z(ŵ) ≥ `z(w) +∇`z(w)>(ŵ −w) + α
  2 ‖ŵ −w‖2 ≥ `z(w)−
  1
  2α ‖∇`z(w)‖2 (106)
  Thus by choosing ŵ = w and re-ordering, we obtain the following result (a.k.a. the Polyak-Lojasiewicz inequality):
  `z(w)− `z(w) ≤ 1
  2α ‖∇`z(w)‖2 (107)
  Therefore we can write:
  `z(w)− B ‖∇`z(w)‖2 + δ ≤ `z(w)− `z(w) + ε‖∇`z(w)‖2 + δ ≤ 1 2α ‖∇`z(w)‖2 + ε ‖∇`z(w)‖2 + δ . (108)
  We introduce the function ψ : x ∈ R+ 7→ 1 2α x+ ε
  x+ δ , and we compute its derivative:
  ψ′(x) = 1 2α (x+ δ)− 1 2α x− ε
  (x+ δ)2 ,
  = δ 2α − ε
  (x+ δ)2 ≥ 0. (δ ≥ 2αε)
  (109)
  Therefore ψ is monotonically increasing. As a result, we have:
  ∀ x ∈ R+, ψ(x) ≤ lim x→∞
  ψ(x) = 1
  2α . (110)
  Therefore we have that: 1
  2α ‖∇`z(w)‖2 + ε ‖∇`z(w)‖2 + δ
  = ψ ( ‖∇`z(w)‖2 ) ≤ 1
  2α , (111)
  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:
  f(wT+1)− f? ≤ β exp ( −αT
  8β
  ) ‖w0 −w?‖2 + 2δ
  α +
  ( 10 β
  α + 4
  β2
  α2
  ) ε. (16)
  In other words, f approximately converges to f? at a rate of O(exp(−αT/8β)).
sections.heading: Proof :
sections.text: 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 ≤ ‖wt −w?‖2 − 1
  2β (`zt(wt)− `zt(w?)) +
  δ
  4β2 + γt(`zt(w?)− B),
  ≤ ‖wt −w?‖2 − 1
  2β (`zt(wt)− `zt(w?)) +
  δ
  4β2 + γtε, (definition of ε)
  ≤ ‖wt −w?‖2 − 1
  2β (`zt(wt)− `zt(w?)) +
  δ
  4β2 +
  ε
  2α . (Lemma 4) (112)
  Let w(zt) be the minimizer of `zt on its unconstrained domain Rp (its existence is guaranteed by the strong convexity property). Then we exploit strong convexity to lower bound the progress made:
  `zt(wt)− `zt(w?) = `zt(wt)− `zt(w (zt)) + `zt(w?)− `zt(w (zt))− 2(`zt(w?)− `zt(w (zt)))
  ≥ `zt(wt)− `zt(w (zt)) + `zt(w?)− `zt(w (zt))− 2(`zt(w?)− B)
  (because `zt(w (zt)) ≥ B)
  ≥ `zt(wt)− `zt(w (zt)) + `zt(w?)− `zt(w (zt))− 2ε (definition of ε) ≥ α 2 ‖wt −w(zt)‖2 + α 2 ‖w? −w(zt)‖2 − 2ε (α-strong convexity) ≥ α 4 ‖wt −w?‖2 − 2ε (Lemma 3) (113)
  We now combine inequalities (112) and (113):
  ‖wt+1 −w?‖2 ≤ (
  1− α 8β
  ) ‖wt −w?‖2 + ε
  β +
  δ
  4β2 +
  ε
  2α (114)
  We use a trivial induction over t and write:
  ‖wt+1 −w?‖2 ≤ (
  1− α 8β
  ) ‖wt −w?‖2 + ε
  β +
  δ
  4β2 +
  ε
  2α ,
  ≤ (
  1− α 8β
  )t ‖w0 −w?‖2 + t∑ k=0 ( 1− α 8β )t−k ( ε β + δ 4β2 + ε 2α ) ,
  ≤ (
  1− α 8β
  )t ‖w0 −w?‖2 + ∞∑ k=0 ( 1− α 8β )k ( ε β + δ 4β2 + ε 2α ) ,
  = ( 1− α
  8β
  )t ‖w0 −w?‖2 +
  1 α 8β
  ( ε
  β +
  δ
  4β2 +
  ε
  2α
  ) ,
  = ( 1− α
  8β
  )t ‖w0 −w?‖2 + 8β
  α
  ( ε
  β +
  δ
  4β2 +
  ε
  2α
  ) . (115)
  In particular, we remark that the right hand-side of the equation is independent on zt.
  Given an arbitrary w ∈ Rp, 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[`z]. We introduce w the minimizer of f on its unconstrained domain Rp. Then we can write that for any w ∈ Rp:
  f(w)− f(w?) ≤ f(w)− f(w), (f(w) ≤ f(w?))
  ≤ ∇f(w)>(w −w) + β 2 ‖w −w‖2, (f is β-smooth)
  = β
  2 ‖w −w‖2, (∇f(w) = 0)
  ≤ β(‖w −w?‖2 + ‖w? −w‖2), (Lemma 3)
  ≤ β‖w −w?‖2 + 2β
  α (f(w?)− f(w)) , (f is α-strongly convex)
  ≤ β‖w −w?‖2 + 2β
  α (f(w?)− B) , (B ≤ f(w) by definition)
  ≤ β‖w −w?‖2 + 2 βε
  α , (definition of ε) (116)
  We combine the results to obtain the final result:
  f(wt+1)− f(w?) ≤ β‖wt+1 −w?‖2 + 2 βε
  α ,
  ≤ β (( 1− α
  8β
  )t ‖w0 −w?‖2 + 8β
  α
  ( ε
  β +
  δ
  4β2 +
  ε
  2α
  )) + 2 βε
  α ,
  = β ( 1− α
  8β
  )t ‖w0 −w?‖2 + 8β
  α
  ( ε+ δ
  4β + εβ 2α
  ) + 2 βε
  α ,
  = β ( 1− α
  8β
  )t ‖w0 −w?‖2 + 2δ
  α +
  ( 10 β
  α + 4
  β2
  α2
  ) ε,
  ≤ β exp ( −αt
  8β
  ) ‖w0 −w?‖2 + 2δ
  α +
  ( 10 β
  α + 4
  β2
  α2
  ) ε. (117)
sections.heading: D.10 THEOREM 9
sections.text: 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 η ≥ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have:
  f(wT+1)− f? ≤ β exp ( −αT
  8β
  ) ‖w0 −w?‖2 + 2δ
  α +
  ( 10 β
  α + 4
  β2
  α2
  ) ε. (17)
  Proof : Re-using inequalities (84) and (89) from the proof of Theorem 6, we obtain:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − 1
  2β (`zt(wt)− `zt(w?)) +
  δ
  4β2 + γt(`zt(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.
sections.heading: D.11 THEOREM 10
sections.text: 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 η ≤ 12β . Then if we apply ALI-G with a maximal learning-rate of η to f , we have: f(wT+1)− f? ≤ β exp ( −αηT
  4
  ) ‖w0 −w?‖2 + 2δ
  α +
  14εβ
  α . (18)
  Proof : Re-using inequalities (92) and (98) from the proof of Theorem 7, we can write:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ηδ
  2β + γt(`zt(w?)− B),
  ≤ ‖wt −w?‖2 − η(`zt(wt)− `zt(w?)) + ηδ
  2β + ηε (γt ≤ η, 0 ≤ `zt(w?)− B ≤ ε).
  (119)
  Furthermore, the inequality (113) gives:
  `zt(wt)− `zt(w?) ≥ α
  4 ‖wt −w?‖2 − 2ε (120)
  Therefore, we can write:
  ‖wt+1 −w?‖2 ≤ ‖wt −w?‖2 − αη
  4 ‖wt −w?‖2 +
  ηδ 2β + 3ηε,
  = (
  1− αη 4
  ) ‖wt −w?‖2 + ηδ
  2β + 3ηε.
  (121)
  Then a trivial induction gives that:
  ‖wT+1 −w?‖2 ≤ (
  1− αη 4
  )T ‖w0 −w?‖2 + ( ηδ
  2β + 3ηε ) T∑ t=0 ( 1− αη 4 )t ,
  ≤ (
  1− αη 4
  )T ‖w0 −w?‖2 + ( ηδ
  2β + 3ηε ) ∞∑ t=0 ( 1− αη 4 )t ,
  = (
  1− αη 4
  )T ‖w0 −w?‖2 + ( ηδ
  2β + 3ηε
  ) 1
  1− (
  1− αη 4 ) , = (
  1− αη 4
  )T ‖w0 −w?‖2 + 2δ
  αβ +
  12ε
  α .
  (122)
  We now re-use the inequality (116) to write:
  f(wT+1)− f? ≤ β‖wT+1 −w?‖2 + 2βε
  α , ≤ β (
  1− αη 4
  )T ‖w0 −w?‖2 + 2δ
  α +
  14εβ
  α , ≤ β exp ( −αηT
  4
  ) ‖w0 −w?‖2 + 2δ
  α +
  14εβ
  α .
  (123)
sections.heading: E.1 STANDARD DEVIATION OF CIFAR RESULTS
sections.heading: E ADDITIONAL EXPERIMENTAL DETAILS