Sharan Vaswani

Benjamin Dubois-Taine

Reza Babanezhad Amii

Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent

We design step-size schemes that make stochastic gradient descent (SGD) adaptive to (i) the noise σ 2 in the stochastic gradients and (ii) problem-dependent constants. When minimizing smooth, stronglyconvex functions with condition number κ, we first prove that T iterations of SGD with Nesterov acceleration and exponentially decreasing step-sizes can achieve a nearoptimal Õ exp ( -T / √ κ) + σ 2 /T convergence rate. Under a relaxed assumption on the noise, with the same step-size scheme and knowledge of the smoothness, we prove that SGD can achieve an Õ exp ( -T /κ) + σ 2 /T rate. In order to be adaptive to the smoothness, we use a stochastic line-search (SLS) and show (via upper and lower-bounds) that SGD converges at the desired rate, but only to a neighbourhood of the solution. Next, we use SGD with an offline estimate of the smoothness, and prove convergence to the minimizer. However, its convergence is slowed down proportional to the estimation error and we prove a lower-bound justifying this slowdown. Compared to other step-size schemes, we empirically demonstrate the effectiveness of exponential step-sizes coupled with a novel variant of SLS.

Our results thus demonstrate the difficulty of obtaining noise-adaptive rates while being adaptive to the problem-dependent parameters.

Introduction

We study unconstrained minimization of a finite-sum objective f : R d → R prevalent in machine learning, min

w∈R d f (w) := 1 n n i=1 f i (w). (1)
Correspondence to vaswani.sharan@gmail.com.

For supervised learning, n represents the number of training examples and f i is the loss of example i.

Throughout the main paper, we assume f to be a smooth, strongly-convex function and denote w * to be the unique minimizer of the above problem. We consider broader function classes in Appendix B.

We study stochastic gradient descent (SGD) and its accelerated variant for minimizing f [START_REF] Robbins | A stochastic approximation method[END_REF][START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF][START_REF] Bottou | Optimization methods for large-scale machine learning[END_REF]. The empirical performance and the theoretical convergence of SGD is governed by the choice of its step-size, and numerous ways of selecting it have been studied in the literature. For example, [START_REF] Moulines | Non-asymptotic analysis of stochastic approximation algorithms for machine learning[END_REF]; [START_REF] Gower | SGD: General analysis and improved rates[END_REF] use a constant step-size for convex and strongly convex functions. A constant step-size only guarantees convergence to a neighborhood of the solution. In order to converge to the exact minimizer, a common technique is to decrease the step-size at an appropriate rate, and such decreasing step-sizes have also been well-studied in the literature [START_REF] Robbins | A stochastic approximation method[END_REF][START_REF] Ghadimi | Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework[END_REF]. The rate at which the step-size needs to be decayed depends on the function class under consideration. For example, when minimizing smooth, strongly-convex functions using T iterations of SGD, the step-size is decayed at an O(1/k) rate where k is the iteration number. This results in an Θ(1/T ) convergence rate for SGD and is optimal in the stochastic setting [START_REF] Nguyen | Tight dimension independent lower bound on the expected convergence rate for diminishing step sizes in sgd[END_REF]. On the other hand, when minimizing a smooth, strongly-convex function with condition number κ, deterministic (full-batch) gradient descent (GD) with a constant step-size converges linearly and has an O(exp(-T /κ)) convergence rate. Augmenting constant step-size GD with Nesterov acceleration can further improve the convergence rate to Θ(exp(-T / √ κ)) which is optimal in the deterministic setting [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. Hence, the stochastic and deterministic variants of gradient descent use a different step-size strategy to obtain the optimal rates in their respective settings.

Towards noise adaptivity: Ideally, we want a noiseadaptive algorithm such that (i) it obtains the optimal rates in both the deterministic and stochastic settings (ii) its convergence rate depends on the noise in the stochastic gradients and (iii) the resulting algorithm does not require knowledge of the stochasticity (e.g. an upper bound on the variance in stochastic gradients).

There have been three recent attempts to obtain such an algorithm. For smooth, strongly-convex functions, if σ 2 is the noise level in the stochastic gradients, [START_REF] Stich | Unified optimal analysis of the (stochastic) gradient method[END_REF] achieves an Õ exp(-T /κ) + σ 2 T convergence rate using SGD that switches between two carefully designed step-sizes. When σ = 0, the resulting algorithm achieves the deterministic GD rate, whereas for a nonzero σ, its rate is governed by the σ 2 /T term. Unfortunately, setting the algorithm parameters requires the knowledge of σ and hence, it is not noise-adaptive. On the other hand, [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF] and [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF] do not require knowledge of σ, and can obtain the same rate for smooth functions satisfying the Polyak-Lojasiewicz (PL) condition [START_REF] Karimi | Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition[END_REF], a generalization of strong-convexity. For this, [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF] use an exponentially decreasing sequence of step-sizes, while [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF] use a constant then decaying step-size. However, neither of these methods match the optimal √ κ dependence in the linear convergence term.

Contribution: Since we consider the easier (compared to PL) strongly-convex setting, it is unclear if we can achieve the above rate by using the conventional polynomially decreasing step-sizes [START_REF] Robbins | A stochastic approximation method[END_REF]. Unfortunately, in Lemmas 3 and 4, we prove that no polynomially decreasing step-size of the form O1 k δ for δ ∈ [0, 1] can achieve the desired Õ exp(-T /κ) + σ 2 T rate 1 . Consequently, we will use an exponentially decreasing step-size.

Contribution:

In Section 3, we use SGD with an exponentially decreasing step-size and a stochastic variant of Nesterov acceleration (Vaswani et al., 2019a). Under a growth-condition similar to [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]; [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF]; [START_REF] Bottou | Optimization methods for large-scale machine learning[END_REF], we prove that the resulting algorithm achieves the near-optimal Õ exp(-T / √ κ) + σ 2 T convergence when minimizing smooth, strongly-convex functions. Our algorithm thus achieves the near-optimal rate in both the stochastic and deterministic settings and its rate smoothly varies between the two regimes. Furthermore, our algorithm does not require knowledge of σ 2 and hence satisfies three desiderata outlined above. To the best of our knowledge, this is the first such result.

Towards noise and problem adaptivity: Typi-cally, SGD also requires the knowledge of problemdependent constants (such as smoothness or strongconvexity) to set the step-size. In practice, it is difficult to estimate these problem-dependent constants, and one can only obtain loose bounds on them. Consequently, there have been numerous methods [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF][START_REF] Li | On the convergence of stochastic gradient descent with adaptive stepsizes[END_REF][START_REF] Kingma | Adam: A method for stochastic optimization[END_REF][START_REF] Bengio | Rmsprop and equilibrated adaptive learning rates for nonconvex optimization[END_REF][START_REF] Vaswani | Painless stochastic gradient: Interpolation, line-search, and convergence rates[END_REF][START_REF] Loizou | Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence[END_REF] that can adapt to the problem parameters, and adjust the step-size on the fly. We term such methods as problem-adaptive. Unfortunately, it is unclear if such problem-adaptive methods can also be made noiseadaptive. On the other hand, all the noise-adaptive methods [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF][START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF][START_REF] Stich | Unified optimal analysis of the (stochastic) gradient method[END_REF] including the algorithm proposed in Section 3 require the knowledge of problem-dependent constants and are thus not problem-adaptive.

In order to make progress towards an SGD variant that is both noise-adaptive and problem-adaptive, we only consider algorithms that can achieve the (non-optimal) Õ exp(-T /κ) + σ 2 T convergence rate. We note that the noise-adaptive algorithm in [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF] only requires knowledge of the smoothness constant and we try to relax this requirement.

Contribution: In Section 4.2, we use stochastic linesearch [START_REF] Vaswani | Painless stochastic gradient: Interpolation, line-search, and convergence rates[END_REF] to estimate the smoothness constant on the fly. We prove that SGD in conjunction with exponentially decreasing step-sizes and stochastic line-search (SLS) converges at the desired noise-adaptive rate but only to a neighbourhood of the solution. This neighbourhood depends on the noise and the error in estimating the smoothness. We prove a corresponding lower-bound that shows the necessity of this neighbourhood term. Our lower-bound shows that if the step-size is set in an online fashion (using the sampled function like in SLS), no decreasing sequence of step-sizes can converge to the minimizer.

Contribution: In Section 4.3, we consider estimating the smoothness constant in an offline fashion (before running SGD). SGD with an offline estimate of the smoothness and exponentially decreasing stepsizes converges to the solution, though its rate is slowed down by a factor proportional to the estimation error in the smoothness. Our upper-bound shows that even if we misestimate the smoothness constant by a multiplicative factor of ν, the convergence can slow down by a factor as large as O(exp(ν)). We complement this result with a lower-bound that shows that such a misestimation in the smoothness necessarily slows down the rate by a potentially exponential factor.

Contribution:

In Section 5, we compare the performance of different step-size schemes on convex, supervised learning problems. Furthermore, we propose a novel variant of SLS that guarantees converges to the minimizer and demonstrate its practical effectiveness.

Contribution: Finally, in Appendix B, we prove matching results for SGD on strongly star-convex functions [START_REF] Hinder | Nearoptimal methods for minimizing star-convex functions and beyond[END_REF], a class of structured non-convex functions. We also show the explicit dependence of our results on the mini-batch size. Finally, we prove upper-bounds for (non-strongly-) convex functions, showing that even when the smoothness constant is known, exponentially decreasing stepsizes converge to a neighbourhood of the solution. We give some justification as to why any polynomial/exponentially decreasing step-size sequence is unlikely to be noise-adaptive in this setting.

Problem setup and Background

We will assume that f and each f i are differentiable and lower-bounded by f * and f * i , respectively. Throughout the main paper, we will assume that f is µ-strongly convex, and each f i is convex. Furthermore, we assume that each function f i is L i -smooth, implying that f is L-smooth with L := max i L i . We include definitions of these properties in Appendix A.

We use stochastic gradient descent (SGD) or SGD with Nesterov acceleration [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]) (referred to as ASGD) to minimize f in Eq. (1). In each iteration k ∈ [T ], SGD selects a function f ik (typically uniformly) at random, computes its gradient and takes a descent step in that direction. Specifically,

w k+1 = w k -γ k α k ∇f ik (w k ), (2)
where w k+1 and w k are the SGD iterates, and ∇f ik (•) is the gradient of the loss function chosen at itera-

tion k. Each stochastic gradient ∇f ik (w) is unbiased, implying that E i [∇f i (w)|w k ] = ∇f (w).
The product of scalars η k := γ k α k defines the step-size for iteration k. The step-size consists of two parts -a problem-dependent scaling term γ k that captures the (local) smoothness of the function, and a problemindependent term α k that controls the decay of the step-size. Typically, α k is a decreasing sequence of k, and lim k→∞ α k = 0. The α k sequence depends on the properties of f , for example, for convex functions,

α k = O( 1 / √ k) while for strongly-convex func- tions, α k = O( 1 /k).
Throughout the paper, we will assume that T is known in advance (this requirement can be relaxed via the standard doubling trick), and consider exponentially decreasing step-sizes [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF] where α := β T 1/T ≤ 1 for some parameter β ≥ 1 and α k := α k . Unlike SGD, ASGD has two sequences {w k , y k } and an additional extrapolation parameter b k . ASGD computes the stochastic gradient at the extrapolated point y k and takes a descent step in that direction. Specifically, the update in iteration k of ASGD is:

y k = w k + b k (w k -w k-1 ), (3)
w k+1 = y k -γ k α k ∇f ik (y k ). (4)
In the next section, we will analyze the convergence of ASGD with exponentially decreasing step-sizes for smooth, strongly-convex functions.

Convergence of ASGD

For analyzing the convergence of ASGD, we will assume that the stochastic gradients satisfy a growth condition similar to [START_REF] Bottou | Optimization methods for large-scale machine learning[END_REF]; [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]; [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF] -there exists a (ρ, σ) with ρ ≥ 1 and σ ≥ 0, such that for all w,

E i ∇f i (w) 2 ≤ ρ ∇f (w) 2 + σ 2 . ( 5
)
Note that in the deterministic setting (when using the full-gradient in Eq. ( 4)), ρ = 1 and σ = 0. Similarly, σ = 0 when the stochastic gradients satisfy the stronggrowth condition when using over-parameterized models [START_REF] Schmidt | Fast convergence of stochastic gradient descent under a strong growth condition[END_REF][START_REF] Ma | The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning[END_REF]Vaswani et al., 2019a). Under the above growth condition, we prove the following theorem in Appendix C.

Theorem 1. Assuming (i) convexity and L ismoothness of each f i , (ii) µ strong-convexity of f and (iii) the growth condition in Eq. (5), ASGD (Eqs.

(3) and ( 4)

) with w 0 = y 0 , γ k = 1 ρL , α = β T 1/T , α k = α k , r k = µ ρL β T k/2T
and b k computed as:

b k = (1 -r k-1 ) r k-1 α r k + r 2 k-1 α , (6)
has the following convergence rate:

E[f (w T ) -f * ] ≤ 2c 3 exp - T √ κρ α ln( T /β) [f (w 0 ) -f * ] + 8σ 2 c 4 κ ρLe 2 (ln( T /β)) 2 α 2 T where κ = L µ , c 3 = exp 1 √ ρκ 2β ln( T /β) and c 4 = exp 1 α √ ρκ 2β ln( T /β) .
The above theorem implies that ASGD achieves an Õ exp [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF]; [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]. Under the stronggrowth condition (when σ = 0), ASGD improves (by a √ ρ factor) over the rate in Vaswani et al. (2019a) and matches (upto log factors) the rate in [START_REF] Mishkin | Interpolation, growth conditions, and stochastic gradient descent[END_REF].

In the general stochastic case, when σ = 0, [START_REF] Cohen | On acceleration with noise-corrupted gradients[END_REF]; Vaswani et al. (2019a) prove convergence to a neighbourhood of the solution, while we show convergence to the minimizer at a rate governed by the O(σ 2 /T ) term. In the fully-deterministic setting (ρ = 1 and σ = 0), Theorem 1 implies an Õ(exp(-T / √ κ)) convergence to the minimizer, matching the optimal rate in the deterministic setting [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. We note that ASGD does not require knowledge of σ 2 and is thus completely noise-adaptive. To smoothly interpolate between the stochastic (mini-batch size 1) and fully deterministic (mini-batch size n) setting, we generalize the growth condition (and the above result) to show an explicit dependence on the mini-batch size in Appendix B.

Finally, we note that ASGD requires the knowledge of both µ and L and is thus not problem-adaptive. In the next section, we consider strategies towards achieving problem-adaptivity.

Misspecified ASGD

Computing the exact values of µ and L are a challenging problem and in practice we estimate them with some error. In this section we assume that we µ and L are misspecified by factor ν µ and ν L i.e. μ = ν µ µ and L = L ν L . The following theorem shows the effect of this misspecification over the convergence of ASGD. Theorem 2. Assuming (i) convexity and L ismoothness of each f i , (ii) µ strong-convexity of f and (iii) the growth condition in Eq. (5), ASGD (Eqs. (3) and ( 4)

) with w 0 = y 0 , γ k = ν L ρL , α = β T 1/T , α k = α k , r k = ν L νµµ ρL β T k/2T
and b k computed as:

b k = (1 -r k-1 ) r k-1 α r k + r 2 k-1 α , (7)
has the following convergence rate:

E[f (w T ) -f * ] ≤ 2c 3 exp - √ νT √ κρ α ln( T /β) [f (w 0 ) -f * ] + 8c 4 κ(ln( T /β)) 2 (eα) 2 ρLT νσ 2 + 2c 4 κ(ln( T /β)) 2 (eα) 2 LT min{ ln(ν) + ln(T /β) , 1}νG 2 where ν = ν L ν µ , κ = L µ , c 3 = exp 1 √ ρκ 2β √ ν ln( T /β) and c 4 = exp 1 α √ ρκ 2β √ ν ln( T /β) and G := max j∈[k0] E[ ∇f (y k ) 2 ] with k 0 := T ln(ν) + ln(T /β)
and x + = max{ x , 0}.

The above theorem implies that misspecified ASGD achives Õ(exp

( -T √ ν √ κρ ) + σ 2 ν T + G 2 ν T
) such that comparing against ASGD rate it has an extra term due to misspecification. Assessing the upper bound of suboptimality in Theorem 2, we note that: (i) the term concerning the noise and the misspecification are independent i.e. the second term of RHS just depends on σ and the third term just depends on G; (ii) the bound is both noise adaptive and misspecification adaptive i.e. if ν = 1 we recover the result of Theorem 1; (iii) and interestingly the bound depends on the multiplication of misspecifications of L and µ i.e. ν = ν L ν µ and therefore we still can have misspecification i.e. ν L , ν µ = 1 but ν = 1 and benefit the speed of ASGD. The proof of Theorem 2 is presented in Appendix G.

Towards noise and problem adaptivity

In this section, we consider approaches for achieving both noise and problem adaptivity when minimizing smooth, strongly-convex functions. In order to make progress towards this objective, we will only consider SGD and aim to obtain the non-accelerated noiseadaptive rate matching Stich (2019); [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]; [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF], but do so without knowing problem-dependent constants.

For this section, we will consider a different weaker notion of noise in the stochastic gradients. Instead of using the growth condition in Eq. ( 5) or the more typical assumption of finite gradient noise z 2 := E i [ ∇f i (w * ) 2 ] < ∞, we assume a finite optimal objective difference. Specifically, we redefine the noise as

σ 2 := E i [f i (w * ) -f * i ] ≥ 0.
This notion of noise has been used to study the convergence of constant step-size SGD in the interpolation setting for overparameterized models [START_REF] Zhang | Stochastic approximation of smooth and strongly convex functions: Beyond the o(1/t) convergence rate[END_REF][START_REF] Loizou | Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence[END_REF][START_REF] Vaswani | Adaptive gradient methods converge faster with overparameterization (and you can do a line-search[END_REF]. Note that when interpolation is exactly satisfied, σ = z = 0. In general, if each function f i is µ-strongly convex and L-smooth, then 1 2L z 2 ≤ σ 2 ≤ 1 2µ z 2 . We will continue to use exponentially decreasing stepsizes. As a warm-up towards problem-adaptivity, we first assume knowledge of the smoothness constant in Section 4.1 and analyze the resulting SGD algorithm. In Section 4.2, we consider using a stochastic line-search [START_REF] Vaswani | Painless stochastic gradient: Interpolation, line-search, and convergence rates[END_REF][START_REF] Vaswani | Adaptive gradient methods converge faster with overparameterization (and you can do a line-search[END_REF] in order to estimate the smoothness constant and set the stepsize on the fly. Finally, in Section 4.3, we analyze the convergence of SGD when using an offline estimate of the smoothness.

Known smoothness

We use the knowledge of smoothness to set the problem-dependent part of the step-size for SGD, specifically, γ k = 1 /L. With an exponentially decreasing α k -sequence, we prove the following theorem in Appendix D.1.

Theorem 3. Assuming (i) convexity and L i - smoothness of each f i , (ii) µ strong-convexity of f , SGD (Eq. (2)) with γ k = 1 L , α = β T 1/T , α k = α k , has the following convergence rate, E w T +1 -w * 2 ≤ w 1 -w * 2 c 2 exp - T κ α ln( T /β) + 8σ 2 c 2 κ 2 Le 2 (ln( T /β)) 2 α 2 T where κ = L µ and c 2 = exp 1 κ • 2β ln( T /β) .
Compared to [START_REF] Moulines | Non-asymptotic analysis of stochastic approximation algorithms for machine learning[END_REF] that use a polynomially decreasing step-sizes, the proposed step-size results in a better trade-off between the bias (initial distance to the minimizer) and variance (noise) terms. We use exponentially decreasing stepsizes rather than the step-size schemes used in [START_REF] Stich | Unified optimal analysis of the (stochastic) gradient method[END_REF]; [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF] because both of these also require the knowledge of the strongconvexity parameter which is considerably more difficult to estimate.

Since strongly-convex functions also satisfy the PL condition [START_REF] Karimi | Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition[END_REF], the above result can be deduced from [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]. However, unlike [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]

, E[f (w T ) -f * ].
In contrast, our proof uses an expansion of the iterates to obtain the rate in terms of the distance to the minimizer, E w T +1 -w * 2 . This change allows us to handle the case when the smoothness constant is unknown and needs to be estimated.

Next, we use stochastic line-search techniques to estimate the unknown smoothness constant and set the step-size on the fly.

Online estimation of unknown smoothness

In this section, we assume that the smoothness constant is unknown, aim to estimate it and set the step-size in an online fashion. By online estimation, we mean that in iteration k of SGD, we use knowledge of the sampled function i k to set the stepsize, i.e. setting γ k depends on i k . We only consider methods that use the knowledge of i k in iteration k and are not allowed to access the other functions in f (for example, to compute the full-batch gradient at w k ). Recent methods based on a stochastic linesearch [START_REF] Vaswani | Painless stochastic gradient: Interpolation, line-search, and convergence rates[END_REF][START_REF] Vaswani | Adaptive gradient methods converge faster with overparameterization (and you can do a line-search[END_REF], stochastic Polyak step-size [START_REF] Loizou | Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence[END_REF][START_REF] Berrada | Training neural networks for and by interpolation[END_REF] or stochastic Barzilai-Borwein-like step-size [START_REF] Malitsky | Adaptive gradient descent without descent[END_REF] are techniques that can set the step-size by only using the current sampled function.

We use stochastic line-search (SLS) to estimate the local Lipschitz constant and set γ k , the problemdependent part of the step-size. SLS is the stochastic analog of the traditional Armijo line-search [START_REF] Armijo | Minimization of functions having Lipschitz continuous first partial derivatives[END_REF] used for deterministic gradient descent [START_REF] Nocedal | Numerical optimization[END_REF]. In each iteration k of SGD, SLS estimates the smoothness constant L ik of the sampled function using f ik and ∇f ik . In particular, starting from a guess (γ max ) of the step-size, SLS uses a backtracking procedure and returns the largest step-size γ k that satisfies the following conditions: γ k ≤ γ max and

f ik (w k -γ k ∇f ik (w k )) ≤ f ik (w k ) -cγ k ∇f ik (w k ) 2 . ( 8
)
Here, c ∈ (0, 1) is a hyper-parameter to be set according to the theory. SLS guarantees that resulting the step-size γ k lies in the min 2(1-c) L ik , γ max , γ max range (see Lemma 11 for the proof). If the initial guess is large enough i.e. γ max > 1/L ik , then the resulting step-size γ k ≥ 2(1-c) L ik . Thus, with c = 1 /2, SLS can be used to obtain an upper-bound on 1 /L ik .

In the interpolation (σ = 0) setting, a constant stepsize suffices (α k = 1 for all k), and SGD obtains a linear rate of convergence (for c ≥ 1 /2) when minimizing smooth, strongly-convex functions [START_REF] Vaswani | Painless stochastic gradient: Interpolation, line-search, and convergence rates[END_REF]. In general, for a non-zero σ, using SGD with SLS and no step-size decay (α k = 1) results in O exp(-T /κ) + γ max σ 2 rate [START_REF] Vaswani | Adaptive gradient methods converge faster with overparameterization (and you can do a line-search[END_REF], implying convergence to a neighbourhood determined by the γ max σ 2 term.

In order to obtain a similar rate as Theorem 3 but without the knowledge of L, we set γ k with SLS and use the same exponentially decreasing α ksequence. We prove the following theorem in Appendix D.2. , α k = α k and γ k as the largest step-size that satisfies γ k ≤ γ max and Eq. (8) with c = 1 /2, has the following convergence rate,

E w T +1 -w * 2 ≤ w 1 -w * 2 c 1 exp - T κ α ln( T /β) + 8σ 2 c 1 (κ ) 2 γ max e 2 (ln( T /β)) 2 α 2 T + 2σ 2 c 1 κ ln(T /β) eα γ max -min γ max , 1 L with κ = max L µ , 1 µγmax , c 1 = exp 1 κ • 2β ln( T /β) .
We observe that the first two terms are similar to those in Theorem 3. For γ max ≥ 1 L , κ = κ and the above theorem implies the same Õ exp(-T /κ) + σ 2 T rate of convergence. However, as T → ∞, w T +1 does not converge to w * , but rather to a neighbourhood determined by the last term 2 σ 2 κ c1 ln(T /β) eα γ max -min γ max , 1

L

. The neighbourhood thus depends on the noise σ 2 and γ max -min γ max , 1 L , the estimation error (in the smoothness) of the initial guess.

When σ 2 = 0, this neighbourhood term disappears, and SGD converges to the minimizer despite the estimation error. This matches the result for SLS in the interpolation setting [START_REF] Vaswani | Painless stochastic gradient: Interpolation, line-search, and convergence rates[END_REF]. Conversely, when the smoothness is known and γ max can be set equal to 1 L , we also obtain convergence to the minimizer and recover the result of Theorem 3. In fact, if we can "guess" a value of γ max ≤ 1 L , it would result in the neighbourhood term becoming negative, thus ensuring convergence to the minimizer. In this case, the stochastic line-search does not decrease the stepsize in any iteration, and the algorithm becomes the same as using a constant step-size equal to γ max . Finally, we contrast our result for SGD with SLS and α k = 1 [START_REF] Vaswani | Adaptive gradient methods converge faster with overparameterization (and you can do a line-search[END_REF] and observe that instead of the dependence on γ max , our neighbourhood term depends on the estimation error in the smoothness.

In the next section, we prove a lower-bound that shows the necessity of such a neighbourhood term.

Lower bound on quadratics

In order to prove a lower-bound, we consider a pair of 1-dimensional quadratics f i (w) = 1 /2 (x i w -y i ) 2 for i = 1, 2. Here, w, x i , y i are all scalars. The overall function to be minimized is

f (w) = (1/2) • [f 1 (w) + f 2 (w)].
We assume that x 1 = x 2 , and since L i = x i 2 , this assumption implies different smoothness constants for the two functions. For a sufficiently large value of Lemma 11). With these choices, we prove the following lower-bound in Appendix E.1.

γ max i.e. γ max ≥ 1 min i∈[2] Li , using SLS with c ≥ 1/2 (required for convergence) results in γ k ≤ 1 /L ik 2 (see
Theorem 5. When using T iterations of SGD to minimize the sum f (w) = f1(w)+f2(w)

2 of two one- dimensional quadratics, f 1 (w) = 1 2 (w -1) 2 and f 2 (w) = 1 2 (2w + 1 /2)
2 , setting the step-size using SLS with γ max ≥ 1 and c ≥ 1 /2, any convergent sequence of α k results in convergence to a neighbourhood of the solution. Specifically, if w * is the minimizer of f and w 1 > 0, then,

E(w T -w * ) ≥ min w 1 , 3 8
.

The above result shows that using SGD with SLS to set γ k and any convergent sequence of α k (including the exponentially-decreasing sequence in Theorem 4) will necessarily result in convergence to a neighbourhood.

The neighbourhood term can thus be viewed as the price of misestimation of the unknown smoothness constant. This result is in contrast to the conventional thinking that choosing an α k sequence such that lim k→∞ α k = 0 will always ensure convergence to the minimizer. This result is not specific to SLS and would hold for other methods [START_REF] Loizou | Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence[END_REF][START_REF] Berrada | Training neural networks for and by interpolation[END_REF][START_REF] Malitsky | Adaptive gradient descent without descent[END_REF]) that set γ k in an online fashion. Since the lower-bound holds for any convergent α k sequence, a possible reason for convergence to the neighbourhood is the correlation between i k (the sampled function) and the computation of γ k . We verify this hypothesis in the next section.

Offline estimation of unknown smoothness

In this section, we consider an offline estimation of the smoothness constant. By offline, we mean that in iteration k of SGD, γ k is set before sampling i k and cannot use any information about it. This ensures that γ k is decorrelated with the sampled function i k . The entire sequence of γ k can even be chosen before running SGD.

For simplicity of calculations, we consider a fixed γ k = γ for all iterations. Here γ is an offline estimate of 1 L , and can be obtained by any method. Without loss of generality, we assume that this offline estimate is off by a multiplicative factor ν that is γ = ν L for some ν > 0. Here ν quantifies the estimation error in γ with ν = 1 corresponding to an exact estimation of L. In practice, it is typical to be able to obtain lower-bounds on the smoothness constant. Hence, the ν > 1 regime is of practical interest.

For SGD with γ k = γ = ν L and an exponentially decreasing α k -sequence, we prove the following theorem in Appendix D.3.

Theorem 6. Assuming (i) convexity and L i - smoothness of each f i , (ii) µ strong-convexity of f , SGD (Eq. (2)) with α = β T 1/T , α k = α k and γ k = ν L for ν > 0 has the following convergence rate, w T +1 -w * 2 ≤ w 1 -w * 2 c 2 exp - ν T κ α ln( T /β) + 8σ 2 L T exp ν κ 2β ln( T /β) 4κ 2 ln(T /β) 2 e 2 α 2 +   max j∈ T [ln(ν)] + ln( T /β) {f (w j ) -f * } (ν -1) L   × exp ν κ 2β ln( T /β) 8κ 2 νe 2 α 2 [ln(ν)] + ln(T /β) T , where κ = L µ , c 2 = exp ν κ 2β ln( T /β) and [x] + = max{x, 0}.
Observe that as T → ∞, SGD converges to the minimizer w * . The first two terms are similar to that in Theorem 3 and imply an O exp(-T ) + σ 2 T convergence to the minimizer. The third term can be viewed as the price of misestimation of the unknown smoothness constant. Unlike in Theorem 4 where this price was convergence to a neighbourhood, here, the price of misestimation is slower convergence to the minimizer.

Analyzing the third term, we observe that when ν ≤ 1, the third term is zero (since [ln(ν)] + = 0), and the rate matches that of Theorem 3 up to constants that depend on ν. For ν > 1, the convergence rate slows down by a factor that depends on ν. The third term depends on max j∈[T [ln(ν)] +/ln(T /β)] {f (w j ) -f * } because if ν > 1, SGD can diverge and move away from the solution for the initial T [ln(ν)]+ ln(T /β) iterations. This can be explained as follows: for ν > 1, the step-size

γ k = ν L α k ≥ 1
L initially, and SGD diverges in this regime. However, since α k is an exponentially decreasing sequence, after k 0 := T ln(ν) ln(T /β) iterations, ν L α k ≤ 1 L , and the distance to the minimizer decreases after iteration k 0 , eventually resulting in convergence to the solution.

Finally, observe that the third term depends on O (exp(ν)[ln(v)] + ) meaning that if we misestimate the smoothness constant by a multiplicative factor of ν, it can slow down the convergence rate by a factor exponential in ν. In the next section, we justify this dependence by proving a corresponding lower-bound.

Lower bound on quadratics

In this section, we consider gradient descent on a onedimensional quadratic and study the effect of misestimating the smoothness constant by a factor of ν > 1. For simplicity, we consider minimizing a single quadratic, thus ensuring σ 2 = 0. We prove the following lower-bound in Appendix E.2.

Theorem 7. When using gradient descent to minimize a one-dimensional quadratic function f

(w) = 1 2 (xw -y) 2 , with α = β T 1/T , α k = α k and γ k = ν L for ν > 3 we have w k+1 -w * = (w 1 -w * ) k i=1
(1 -να i ).

After k := T ln(T /β) ln ν 3 iterations, we have that

|w k +1 -w * | ≥ 2 k |w 1 -w * |.
Instantiating this lower-bound, suppose the estimate of L is off by a factor of ν = 10, then ln ν 3 ≥ 1, which implies that k ≥ T ln( T /β) . In other words, we do not make any progress in the first T ln( T /β) iterations, and at this point the optimality gap has been multiplied by a factor of 2 T / ln( T /β) compared to the starting optimality gap. This simple example thus shows the (potentially exponential) slowdown in the rate of convergence by misestimating the smoothness.

In the next section, we design a variant of SLS that ensures convergence to the minimizer while obtaining good empirical control over the misestimation.

Experiments

For comparing different step-size choices, we consider two common supervised learning losses -squared loss for regression tasks and logistic loss for classification. Observe that (i) exponentially decreasing step-sizes result in more stable performance compared to using a constant step-size (for both SGD and ASGD) and (ii) consistently outperform the noise-adaptive method in [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF]) and (iii) the stochastic line-search in Eq. ( 9) matches the performance of the variant with known smoothness.

With a linear model and an 2 regularization equal to λ 2 w 2 , both objectives are strongly-convex. We use three standard datasets from LIBSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] -mushrooms, ijcnn and rcv1, and use λ = 0.01. For each experiment, we consider 5 independent runs and plot the average result and standard deviation. We use the (full) gradient norm as the performance measure and plot it against the number of gradient evaluations.

For each dataset, we fix T = 10n, use a batch-size of 1 and compare the performance of the following optimization strategies: (i) the noise-adaptive "constant and then decay step-size" scheme in Khaled and Richtárik (2020, Theorem 3) (denoted as KR-20 in the plots). Specifically, for b = max{ 2L 2 µ , 2ρL}, we use a constant step-size equal to 1/b when T < b/µ or k < T /2 . Otherwise we set the step-size at iteration k to be 2 µ((2b/µ)+k-T /2 ) , (ii) constant step-size SGD with γ k = 1 L and α k = 1 for all k (denoted as K-CNST in the plots) (iii) SGD with an exponentially decreasing step-size with knowledge of smoothness [START_REF] Li | A second look at exponential and cosine step sizes: Simplicity, convergence, and performance[END_REF]

i.e. γ k = 1 L and α k = α k for α = β T 1/T
(de-noted as K-EXP) (iv) Accelerated SGD (ASGD) with a constant step-size (α k = 1 for all k) (Vaswani et al., 2019a;[START_REF] Cohen | On acceleration with noise-corrupted gradients[END_REF] (denoted as ACC-K-CNST) and (v) ASGD with exponentially decreasing stepsizes, analyzed in Section 3 and denoted as ACC-K-EXP.

None of the above strategies are problem-adaptive, and all of them require the knowledge of the smoothness constant L. Additionally, KR-20 and the ASGD variants also require knowledge of ρ, the parameter of the growth condition in Eq. ( 5) and µ, the strong-convexity parameter. If x i is the feature vector corresponding to example i, then we obtain theoretical upper-bounds on the smoothness and set L = max i x i 2 + λ for the squared-loss and L = max i 1 4 x i 2 + λ for the logistic loss. Similarly, we set µ = λ for both the squared and logistic loss. To set ρ, we use a grid search over {10, 100, 1000} and plot the variant that results in the smallest gradient norm.

Using a stochastic line-search (SLS) can result in convergence to the neighbourhood (Section 4.2) because of the correlations between i k and γ k . To alleviate this, and still be problem-adaptive, we design a decorrelated conservative variant of SLS: at iteration k of SGD, we set γ k using a stochastic line-search on the previously sampled function i k-1 (we can use a randomly sampled j k as well). This ensures that there is no correlation between i k and computing γ k , but requires computing the gradient of two functions -one for the update and the other for the line-search. The overall procedure can be described as follows: starting with a backtracking line-search from γ k-1 (the conservative aspect) (with γ 0 = γ max ) for a random or previously sampled functio n (j k ), find the largest step-size γ k that satisfies

f j k (w k -γ k ∇f j k (w k )) ≤ f j k (w k ) -cγ k ∇f j k (w k ) 2 , (9)
and update w k according to Eq. ( 2). The above procedure with c = 1 /2 ensures that

γ k ∈ [min{γ k-1 , 1 /L}, γ k-1 ]. Since γ k is fixed before com- puting ∇f ik (w k )
, this strategy can be analyzed using the framework in Section 4.3. Specifically, it results in γ k = ν k L for some sequence of ν k ≥ 1. The conservative aspect ensures that ν k ≤ ν k-1 . Hence, the convergence rate can be analyzed according to Theorem 6 with ν = ν 1 and the initial line-search controlling the misestimation error. We use this variant of SLS with exponentially decreasing step-sizes and denote it as SLS-EXP in the plots. We emphasize that this strategy is both noise-adaptive and problem-adaptive.

From Fig. 1, we observe that exponentially decreasing step-sizes (i) result in more stable performance compared to the constant step-size variants (for both SGD and ASGD) and (ii) consistently outperform the noise-adaptive method in [START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF]. We also observe that (iii) the stochastic linesearch in Eq. ( 9) (SLS-EXP) matches the performance of the variant with known smoothness (K-EXP) and (iv) ASGD does not result in improvements over SGD. This is because these methods are quite sensitive to their parameter values and we set these parameters by using loose theoretical upper-bounds on both L and µ.

Conclusion

In this paper, we first developed a variant of SGD with Nesterov acceleration and exponentially decreasing step-sizes, and proved that it achieves the nearoptimal convergence rate in both the deterministic and stochastic regimes. We then considered two strategies for making SGD both noise-adaptive and problemadaptive. Using upper and lower-bounds, we showed that there is always a price to pay for problemadaptivity -estimating the smoothness constant in an online fashion results in convergence to a neighbourhood of the solution, while an offline estimation results in a slower convergence to the minimizer. We empirically demonstrated the effectiveness of a noise-adaptive, problem-adaptive method that uses exponential step-sizes coupled with a novel variant of stochastic line-search. In the future, we hope to develop a problem-adaptive variant of ASGD.

Supplementary material Organization of the Appendix

A Definitions

Our main assumptions are that each individual function f i is differentiable, has a finite minimum f * i , and is L i -smooth, meaning that for all v and w,

f i (v) ≤ f i (w) + ∇f i (w), v -w + L i 2 v -w 2 , ( Individual Smoothness)
which also implies that f is L-smooth, where L is the maximum smoothness constant of the individual functions.

A consequence of smoothness is the following bound on the norm of the stochastic gradients,

∇f i (w) 2 ≤ 2L(f i (w) -f * i ).
We also assume that each f i is convex, meaning that for all v and w,

f i (v) ≥ f i (w) -∇f i (w), w -v , (Convexity)
Depending on the setting, we will also assume that f is µ strongly-convex, meaning that for all v and w,

f (v) ≥ f (w) + ∇f (w), v -w + µ 2 v -w 2 , ( Strong Convexity)

B Additional theoretical results

In this section, we relax the strong-convexity assumption to handle broader function classes in Appendix B.1 and prove results that help provide an explicit dependence on the mini-batch size (Appendix B.2) and in Appendix B.3 show that polynomially decreasing step-sizes cannot obtain the desired noise-adaptive rate.

B.1 Relaxing the assumptions

In this section, we extend our theoretical results to a richer class of functions -strongly quasar-convex functions [START_REF] Hinder | Nearoptimal methods for minimizing star-convex functions and beyond[END_REF] in Appendix B.1.1, and (non-strongly) convex functions in Appendix B.1.2.

B.1.1 Extension to strongly star-convex functions

We consider the class of smooth, non-convex, but strongly star-convex functions [START_REF] Hinder | Nearoptimal methods for minimizing star-convex functions and beyond[END_REF][START_REF] Gower | Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation[END_REF], a subset of strongly quasar-convex functions. Quasar-convex functions are unimodal along lines that pass through a global minimizer i.e. the function monotonically decreases along the line to the minimizer, and monotonically increases thereafter. In addition to this, strongly quasar-convex functions also have curvature near the global minimizer. Importantly, this property is satisfied for neural networks for common architectures and learning problems [START_REF] Lucas | Analyzing monotonic linear interpolation in neural network loss landscapes[END_REF][START_REF] Kleinberg | An alternative view: When does sgd escape local minima?[END_REF].

Formally, a function is (ζ, µ) strongly quasar-convex if it satisfies the following for all w and minimizers w * ,

f (w * ) ≥ f (w) + 1 ζ ∇f (w), w * -w + µ 2 w -w * 2 . ( 10
)
Strongly star-convex functions are a subset of this class of functions with ζ = 1. If L is known, it is straightforward to show that the results of Theorem 3 carry over to the strongly star-convex functions and we obtain the similar O exp(-T /κ) + σ 2 T rate. In the case when L is not known, it was recently shown that SGD with a stochastic Polyak step-size [START_REF] Gower | Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation[END_REF] results in linear convergence to the minimizer on strongly star-convex functions under interpolation and achieves an O exp(-T ) + γ max σ 2 convergence rate in general. The proposed stochastic Polyak step-size (SPS) does not require knowledge of L, and matches the rate achieved for stronglyconvex functions [START_REF] Loizou | Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence[END_REF]. However, SPS requires knowledge of f * i , which is usually zero for machine learning models under interpolation but difficult to get a handle on in the general case.

Consequently, we continue to use SLS to estimate the smoothness constant. Our proofs only use strong-convexity between w and a minimizer w * , and hence we can extend all our results from strongly-convex functions, to structured non-convex functions satisfying the strongly star-convexity property, matching the rates in Theorem 4 and Theorem 6. Finally, we note that given knowledge of ζ, there is no fundamental limitation in extending all our results to strongly quasar-convex functions. In the next section, we relax the strong-convexity assumption in a different way -by considering convex functions without curvature.

B.1.2 Handling (non-strongly)-convex functions

In this section, we analyze the behaviour of exponentially decreasing step-sizes on convex functions (without strong-convexity). As a starting point, we assume that L is known, and the algorithm is only required to adapt to the noise σ 2 . In the following theorem (proved in Appendix D.4), we show that SGD with an exponentially decreasing step-size is not guaranteed to converge to the minimizer, but to a neighbourhood of the solution. Theorem 8. Assuming (i) convexity and (ii) L i -smoothness of each f i , SGD with step-size η k = 1 2L α k has the following convergence rate,

E[f ( wT +1 ) -f (w * )] ≤ 2L w 1 -w * 2 T k=1 α k + σ 2 T k=1 α 2 k T k=1 α k (11)
where

wT +1 = T k=1 α k w k T k=1 α k . For α k = β T k/T
, the convergence rate is given by,

E[f ( wT +1 ) -f (w * )] ≤ 2L ln(T /β) w 1 -w * 2 αT -2β + σ 2 T T -β
We thus see that even with the knowledge of L, SGD converges to a neighbourhood of the solution at an O(1/T ) rate. We contrast our result to AdaGrad [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF][START_REF] Levy | Online adaptive methods, universality and acceleration[END_REF] that adapts the step-sizes as the algorithm progresses (as opposed to using a predetermined sequence of step-sizes like in our case), is able to adapt to the noise, and achieves an

O 1 T + σ 2 √ T rate.
In order to be noise-adaptive and match the AdaGrad rate, we can use Eq. ( 11) to infer that a sufficient condition is for the α k -sequence to satisfy the following inequalities, (i)

α k ≥ C 1 T and (ii) α 2 k ≤ C 2 √
T where C 1 , C 2 are constants. Unfortunately, in Lemmas 12 and 13, we prove that it is not possible for any polynomially or exponentially-decreasing sequence to satisfy these sufficient conditions. While we do not have a formal lowerbound in the convex case, it seems unlikely that these α k -sequences can result in the desired rate, and we conjecture a possible lower-bound. Finally, we note that to the best of our knowledge, the only predetermined (non-adaptive) step-size that achieves the AdaGrad rate is min 1 2L , 1 σ √ T [START_REF] Ghadimi | Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework[END_REF]. We also conjecture a lower-bound that shows that there is no predetermined sequence of step-sizes (that does not use knowledge of σ 2 ) that is noise-adaptive and can achieve the

O 1 T + σ 2 √ T rate.

B.2 Dependence on the mini-batch size

In this section, we prove two results in order to explicitly model the dependence on the mini-batch size. We denote a mini-batch as B, its size as B ∈ [1, n] and the corresponding mini-batch gradient as ∇f B (w) = 1 B fi∈B ∇f i (w). The mini-batch gradient is also unbiased i.e. E B [∇f B (w)] = ∇f (w), implying that all the proofs remain unchanged, but we need to use a different growth condition for the ASGD proofs in Section 3 and a different definition of σ for the SGD proofs in Section 4. We refine these quantities here, and show the explicit dependence on the mini-batch size.

Lemma 1. If E i ∇f i (w) 2 ≤ ρ ∇f (w) 2 + σ 2 ,
then,

E B ∇f B (w)) 2 ≤ (ρ -1) n -B nB + 1 ∇f (w) 2 + n -B nB σ 2 .
Proof.

E B ∇f B (w)) 2 = E B ∇f B (w) -∇f (w) + ∇f (w) 2 = E B ∇f B (w) -∇f (w) 2 + ∇f (w) 2 (Since E B [∇f B (w)] = ∇f (w))
Since we are sampling the batch with replacement, using [START_REF] Lohr | Sampling: Design and Analysis: Design and Analysis[END_REF],

≤ n -B nB E i ∇f i (w) 2 -∇f (w) 2 + ∇f (w) 2 ≤ n -B nB (ρ -1) ∇f (w) 2 + σ 2 + ∇f (w) 2 (Using the growth condition) =⇒ E B ∇f B (w)) 2 ≤ (ρ -1) n -B nB + 1 ∇f (w) 2 + n -B nB σ 2 . Lemma 2. If σ 2 := E[f i (w * ) -f * i ],
and each function f i is µ strongly-convex and L-smooth, then

σ 2 B := E B [f B (w * ) -f * B ] ≤ L µ n -B nB σ 2 .
Proof.

By strong-convexity of f i ,

E B [f B (w * ) -f * B ] ≤ 1 2µ E B ∇f B (w * )) 2
Since we are sampling the batch with replacement, using [START_REF] Lohr | Sampling: Design and Analysis: Design and Analysis[END_REF],

≤ 1 2µ n -B nB E i ∇f i (w * ) 2 ≤ L µ n -B nB E[f i (w * ) -f * i ] (By smoothness of f i ) =⇒ σ 2 B ≤ L µ n -B nB σ 2 .

B.3 Polynomially decaying stepsizes

In this section, we analyze polynomially decreasing step-sizes, namely when η k = η (k+1) δ for some constants η > 0 and 0 ≤ δ ≤ 1. We argue that even with knowledge of the smoothness constant, these step-sizes fail to converge at the desired noise-adaptive rate even on simple quadratics. In particular, the next lemma shows that gradient descent (GD) applied to a strongly-convex quadratic with a polynomially decreasing step-size fails to obtain the usual linear rate of the form O(ρ -T ) for some ρ < 1.

Lemma 3. When using T iterations of GD to minimize a one-dimensional quadratic f

(w) = 1 2 (xw -y) 2 , setting η k = 1 L 1 (k+1) δ for some 0 < δ ≤ 1 results in the following lower bounds. If δ = 1, w T +1 -w * = (w 1 -w * ) 1 T + 1 If 0 < δ < 1, w 1 -w * > 0 and T is large enough, w T +1 -w * ≥ (w 1 -w * ) 1 - 1 2 δ 2 1/δ -1 4 2δ-1 1-δ 4 -(T +1) 1-δ 1-δ
Proof. Observe that w * = y /x and L = x 2 . The GD iteration with

η k = 1 L 1 (k+1) δ reads w k+1 = w k - 1 L 1 (k + 1) δ x 2 w k -xy = w k 1 - 1 (k + 1) δ + y x 1 (k + 1) δ = w k 1 - 1 (k + 1) δ + w * 1 (k + 1) δ and thus w k+1 -w * = (w k -w * ) 1 - 1 (k + 1) δ ⇒ w T +1 -w * = (w 1 -w * ) T k=1 1 - 1 (k + 1) δ If δ = 1, w T +1 -w * = (w 1 -w * ) T k=1 k k + 1 = (w 1 -w * ) 1 T + 1 If 0 < δ < 1 and w 1 -w * > 0, w T +1 -w * = (w 1 -w * ) T k=1 1 - 1 (k + 1) δ = (w 1 -w * ) T k=1 1 - 2 2(k + 1) δ
We wish to use the inequality 1 -2x 2 ≥ 2 -2x which is true for all x ∈ [0, 1/2]. In our case it holds for 1

(k + 1) δ ≤ 1 2 ⇒ k ≥ 2 1/δ -1 Let k 0 = 2 1/δ . Then for T ≥ k 0 , w T +1 -w * = (w 1 -w * ) k0-1 k=1 1 - 1 (k + 1) δ T k=k0 1 - 2 2(k + 1) δ Now, for k ≤ k 0 -1, we have that 1 (k+1) δ ≤ 1 2 δ and thus k0-1 k=1 1 - 1 (k + 1) δ ≥ 1 - 1 2 δ k0-1 = 1 - 1 2 δ 2 1/δ -1 For k ≥ k 0 , we have 1 - 2 2(k+1) δ ≥ 2 -2 1 (k+1) δ and thus T k=k0 1 - 2 2(k + 1) δ ≥ 2 -2 T k=k 0 1 (k+1) δ = 2 -2 T +1 k=1 1 k δ - k 0 k=1 1 k δ ≥ 2 -2 T +1 k=1 1 k δ
Using the bound in the proof of Lemma 12, we have

T +1 k=1 1 k δ ≤ 1 + 1 1 -δ (T + 1) 1-δ -1
Putting this together we have that

2 -2 T +1 k=1 1 k δ ≥ 2 -2(1+ 1 1-δ ((T +1) 1-δ -1)) = 4 1/(1-δ) 4 4 -(T +1) 1-δ 1-δ = 4 2δ-1 1-δ 4 -(T +1) 1-δ 1-δ
Putting everything together we get that

w T +1 -w * ≥ (w 1 -w * ) 1 - 1 2 δ 2 1/δ -1 4 2δ-1 1-δ 4 -(T +1) 1-δ 1-δ
The next lemma shows that when δ = 0, namely when the step-size is constant, SGD applied to the sum of two quadratics fails to converge to the minimizer.

Lemma 4. When using SGD to minimize the sum f (w) = f1(w)+f2(w) 2 of two one-dimensional quadratics:

f 1 (w) = 1 2 (w -1) 2 and f 2 (w) = 1 2 (2w + 1 /2) 2 with a constant step-size η = 1 L , the following holds: whenever |w k -w * | < 1 /8, the next iterate satisfies |w k+1 -w * | > 1 /8.
Proof. First observe that w * = 0 and that L = 4. The updates then read

If i k = 1 : w k+1 = w k -η(w k -1) = w k (1 - 1 4 ) + 1 4 = 3 4 w k + 1 4 If i k = 2 : w k+1 = w k -η2(2w k + 1 2 ) = w k (1 - 4 4 ) - 1 4 = - 1 4
Suppose that |w k -w * | =|w k | < 1 /8. We want to show that |w k+1 | > 1 /8. We can separate the analyses in three cases.

If w k ∈ (-1 /8, 0) and i k = 1 then

w k+1 = 3 4 w k + 1 4 > - 3 4 × 1 8 + 1 4 = 5 32 > 1 8
If w k ∈ (0, 1 /8) and i k = 1 then

w k+1 = 3 4 w k + 1 4 > 1 8 If i k = 2 then w k+1 = - 1 4 < - 1 8
implying that in each case, |w k+1 | > 1 /8.

C Proof for ASGD

C.1 Reformulation

Let us consider a general ASGD update whose parameters satisfy the following conditions.

r 2 k = (1 -r k )r 2 k-1 η k η k-1 + r k µη k . ( 12
) b k = (1 -r k-1 )r k-1 η k η k-1 r k + r 2 k-1 η k η k-1 , (13)
It can be verified that setting

η k = γ k α k = 1 ρL β T k/T , r k = µ ρL β T k/2T
satisfies Eq. ( 12).

We first show that the update in Eq. (3)-Eq. ( 4) satisfying the conditions in Eq. ( 13) and Eq. ( 12) can be written in an equivalent form more amenable to the analysis.

Lemma 5. The following update:

y k = w k - r k q k q k + r k µ (w k -z k ) ( 14
)
w k+1 = y k -η k ∇f ik (y k ) ( 15
)
z k+1 = w k + 1 r k [w k+1 -w k ] ( 16
)
where,

q k+1 = (1 -r k )q k + r k µ (17) r 2 k = q k+1 η k (18) z k+1 = 1 q k+1 [(1 -r k )q k z k + r k µy k -r k ∇f ik (y k )] ( 19
)
is equivalent to the update in Eq. (3)-Eq. (4).

Proof.

First we check the consistency of the update (Eq. ( 16)) and definition (Eq. ( 19)) of z k . Using Eq. ( 19),

z k+1 = 1 q k+1 [(1 -r k )q k z k + r k µy k -r k ∇f ik (y k )] = - (1 -r k ) r k w k - r k q k+1 ∇f ik (y k ) + y k (1 -r k )(q k + r k µ) q k+1 r k + r k µ q k+1 = - (1 -r k ) r k w k - r k q k+1 ∇f ik (y k ) + y k q k (1 -r k ) + (r k µ -r 2 k µ) q k+1 r k + r 2 k µ q k+1 r k = - (1 -r k ) r k w k - r k q k+1 ∇f ik (y k ) + y k (q k+1 -r k µ) + (r k µ -r 2 k µ) + r 2 k µ q k+1 r k (From Eq. (17)) = w k - w k r k + 1 r k [y k -η k ∇f ik (y k )]
(From Eq. ( 18))

z k+1 = w k + 1 r k [w k+1 -w k ]
(From Eq. ( 15)) which recovers Eq. ( 16) showing that the definition of z k and its update is consistent. Now we check the equivalence of Eq. ( 12) and Eq. ( 17)-Eq. ( 18). Eliminating q k using Eq. ( 17)-Eq. ( 18),

r 2 k η k = (1 -r k ) r 2 k-1 η k-1 + r k µ
Multiplying by η k recovers Eq. ( 12).

Since Eq. ( 4) and Eq. ( 15) are equivalent, we need to establish the equivalence of Eq. ( 3) and the updates in Eq. ( 14)-Eq. ( 16). From Eq. ( 16)

z k = w k-1 + 1 r k-1 [w k -w k-1 ] =⇒ z k -w k = 1 -r k-1 r k-1 (w k -w k-1 )
Starting from Eq. ( 14) and using the above relation to eliminate z k ,

y k = w k + r k q k q k + r k µ 1 -r k-1 r k-1 [w k -w k-1 ]
which is in the same form as Eq. ( 3). We now eliminate q k from r k q k q k +r k µ 1-r k-1 r k-1 . From Eq. ( 17) and Eq. ( 18),

r 2 k η k = (1 -r k )q k + r k µ =⇒ q k + r k µ = r 2 k η k + r k q k
Using this relation,

r k q k q k + r k µ 1 -r k-1 r k-1 = q k η k r k + q k η k 1 -r k-1 r k-1
Using Eq. ( 18), observe that

η k q k = η k η k-1 η k-1 q k = η k η k-1 r 2 k-1 . Using this relation, r k q k q k + r k µ 1 -r k-1 r k-1 = η k η k-1 r 2 k-1 r k + η k η k-1 r 2 k-1 1 -r k-1 r k-1 = (1 -r k-1 )r k-1 r k η k-1 η k + r 2 k-1 = b k
which establishes the equivalence to Eq. ( 3) and completes the proof.

C.2 Estimating sequences

Similar to [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF][START_REF] Mishkin | Interpolation, growth conditions, and stochastic gradient descent[END_REF], we will use the estimating sequence {φ k , λ k } ∞ k=1 such that λ k ∈ (0, 1) and

λ 0 = 1 ; λ k+1 = (1 -r k )λ k , (20)
φ k (w) = [inf w φ k (w)] + q k 2 w -z k 2 , ( 21
)
and satisfies the following update condition

φ k (w) ≤ (1 -λ k )f (w) + λ k φ 0 (w) (22)
The above definitions impose the following update for φ *

k := [inf w φ k (w)], φ * k+1 = (1 -r k )φ * k + r k f (y k ) - r k 2q k+1 ∇f (y k ) 2 + (1 -r k ) q k q k+1 µ 2 y k -z k 2 + ∇f (y k ), z k -y k (23)
Finally note that the definition of φ k can be used to rewrite Eq. ( 14) as

y k = w k - r k q k + r k µ ∇φ k (w k ). ( 24
)

C.3 Proof of Theorem 1

Given the definitions in Appendix C.2, we first prove the descent lemma for η k = 1 ρL α k , where α k ≤ 1 is the exponentially decreasing step-size. Lemma 6. Using the update in Eq. ( 15) with η k = 1 ρL α k , we obtain the following descent condition.

E[f (w k+1 )] ≤ E[f (y k )] - η k 2 ∇f (y k ) 2 + 1 2ρ 2 L α 2 k σ 2
Proof. By smoothness, and the update in Eq. ( 15),

f (w k+1 ) ≤ f (y k ) -η k ∇f (y k ), ∇f ik (y k ) + L 2 η 2 k ∇f ik (y k ) 2 Taking expectation w.r.t. i k , E[f (w k+1 )] ≤ E[f (y k )] -η k ∇f (y k ) 2 + L 2 η 2 k E[ ∇f ik (y k ) 2 ] (η k is independent of the randomness in i k .) ≤ E[f (y k )] -η k ∇f (y k ) 2 + ρL 2 η 2 k E[ ∇f (y k ) 2 ] + L 2 η 2 k σ 2
(By the growth condition in Eq. ( 5)

) = E[f (y k )] -η k ∇f (y k ) 2 + η k α k 2 E[ ∇f (y k ) 2 ] + 1 2ρ 2 L α 2 k σ 2 ≤ E[f (y k )] - η k 2 ∇f (y k ) 2 + 1 2ρ 2 L α 2 k σ 2
The main part of the proof is to show that φ * k is an upper-bound on f (w k ) (upto a factor governed by the noise term N k depending on σ 2 ) for all k and is proved in the following lemma.

Lemma 7. For the estimating sequences defined in Appendix C.2 and the updates in Eq. ( 14)-Eq. ( 19), for all k,

E[φ * k ] := E[inf w φ k (w)] ≥ E[f (w k )] -N k where N k := 2σ 2 ρ 2 L k-1 j=0 α 2 j k-1 i=j+1 (1 -r i ).
Proof. We will prove the lemma by induction. For k = 0, we define φ * 0 = f (w 0 ), and since N k ≥ 0 for all k, E[φ * ] ≥ f (w 0 ) -N 0 , thus satisfying the base-case for the induction. For the induction, we will use the fact that

N k+1 = (1 -r k )N k + 2σ 2 ρ 2 L α 2 k . Assuming the induction hypothesis, E[φ * k ] ≥ E[f (w k )]
-N k , we use Eq. ( 23) to prove the statement for k + 1 as follows. Taking expectations w.r.t to the randomness in j = 1 to k,

E[φ * k+1 ] = (1 -r k )E[φ * k ] + r k E f (y k ) - r k 2q k+1 ∇f (y k ) 2 + (1 -r k ) q k q k+1 µ 2 y k -z k 2 + ∇f (y k ), z k -y k ≥ (1 -r k )E[f (w k ) -N k ] + r k E f (y k ) - r k 2q k+1 ∇f (y k ) 2 + (1 -r k ) q k q k+1 µ 2 y k -z k 2 + ∇f (y k ), z k -y k (by the induction hypothesis) = (1 -r k )E[f (w k )] + r k E[f (y k )] - r 2 k 2q k+1 E ∇f (y k ) 2 + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k -(1 -r k )N k = (1 -r k )E[f (w k )] + r k E[f (y k )] - η k 2 E ∇f (y k ) 2 + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k -(1 -r k )N k (Using Eq. ( 18
)) By convexity, f (w k ) ≥ f (y k ) + ∇f (y k ), w k -y k , ≥ (1 -r k )E[f (y k ) + ∇f (y k ), w k -y k ] + r k E[f (y k )] - η k 2 E ∇f (y k ) 2 + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k -(1 -r k )N k = E f (y k ) - η k 2 ∇f (y k ) 2 + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k + (1 -r k )E[ ∇f (y k ), w k -y k ] -(1 -r k )N k By Lemma 6, ≥ E f (w k+1 ) - 1 2ρ 2 L α 2 k σ 2 + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k + (1 -r k )E[ ∇f (y k ), w k -y k ] -(1 -r k )N k = E [f (w k+1 )] + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k + (1 -r k )E[ ∇f (y k ), w k -y k ] -(1 -r k )N k + 1 2ρ 2 L α 2 k σ 2 Since N k+1 = (1 -r k )N k + 1 2ρ 2 L α 2 k σ 2 , E[φ * k+1 ] ≥ E [f (w k+1 )] -N k+1 + (1 -r k )E[ ∇f (y k ), w k -y k ] + r k (1 -r k ) q k q k+1 E µ 2 y k -z k 2 + ∇f (y k ), z k -y k Now we show that the remaining terms (1-r k )E ∇f (y k ), w k -y k + r k q k q k+1 µ 2 y k -z k 2 + ∇f (y k ), z k -y k ≥ 0.
For this, we use Eq. ( 14)

y k = w k - q k r k q k + r k µ (w k -z k ) =⇒ z k -y k = z k -w k + q k r k q k + r k µ (w k -z k ) = 1 - q k r k q k + r k µ (z k -w k ) = q k (1 -r k ) + r k µ q k + r k µ (z k -w k ) = q k+1 q k + r k µ (z k -w k ) (By Eq. (17)) =⇒ r k q k q k+1 ∇f (y k ), z k -y k = ∇f (y k ), - r k q k q k + r k µ (w k -z k ) = ∇f (y k ), y k -w k Using this relation to simplify, (1 -r k )E ∇f (y k ), w k -y k + r k q k q k+1 µ 2 y k -z k 2 + ∇f (y k ), z k -y k = (1 -r k )E r k q k q k+1 µ 2 y k -z k 2 + (1 -r k ) [ ∇f (y k ), w k -y k + ∇f (y k ), y k -w k ] = (1 -r k )E r k q k q k+1 µ 2 y k -z k 2 ≥ 0 (Since r k ≤ 1.)
Putting everything together,

E[φ * k+1 ] ≥ E [f (w k+1 )] -N k+1
and we conclude that

E[φ * k ] ≥ E [f (w k )] -N k for all k by induction.
We now use the above lemma to prove the rate for strongly-convex functions.

Theorem 1. Assuming (i) convexity and L i -smoothness of each f i , (ii) µ strong-convexity of f and (iii) the growth condition in Eq. (5), ASGD (Eqs.

(3) and ( 4)

) with w 0 = y 0 , γ k = 1 ρL , α = β T 1/T , α k = α k , r k = µ ρL β T k/2T
and b k computed as:

b k = (1 -r k-1 ) r k-1 α r k + r 2 k-1 α , ( 6
)
has the following convergence rate:

E[f (w T ) -f * ] ≤ 2c 3 exp - T √ κρ α ln( T /β) [f (w 0 ) -f * ] + 8σ 2 c 4 κ ρLe 2 (ln( T /β)) 2 α 2 T where κ = L µ , c 3 = exp 1 √ ρκ 2β ln( T /β) and c 4 = exp 1 α √ ρκ 2β ln( T /β) .
Proof. Using the reformulation in Lemma 5 gives us q k = µ for all k and z 0 = w 0 . For the estimating sequences defined in Appendix C.2, using Lemma 18, we know that the (reformulated) updates satisfy the following relation,

E[f (w T )] ≤ E[φ * T ] + N T ≤ E[φ T (w * )] + N T
From Eq. ( 22), we know that for all w and k,

φ k (w) ≤ (1 -λ k )f (w) + λ k φ 0 (w)
Using these relations,

E[f (w T )] ≤ (1 -λ T )f * + λ T φ 0 (w * ) + N T =⇒ E[f (w T ) -f * ] ≤ λ T [φ 0 (w * ) -f * ] + N T By Eq. (21), ≤ λ T φ * 0 + q 0 2 w * -z 0 2 -f * + N T Choosing φ * 0 = f (w 0 ), ≤ λ T f (w 0 ) -f * + q 0 2 w * -z 0 2 + N T Since z 0 = w 0 , q 0 = µ, =⇒ E[f (w T ) -f * ] ≤ λ T f (w 0 ) -f * + µ 2 w * -w 0 2 + 2σ 2 ρ 2 L T -1 j=0 α 2 j T -1 i=j+1 (1 -r i )
Using the fact that λ 0 = 1 and λ k+1 = (1 -r k )λ k , we know that that λ T = T k=1 (1 -r k ), and

E[f (w T ) -f * ] ≤ T k=1 (1 -r k ) f (w 0 ) -f * + µ 2 w * -w 0 2 + 2σ 2 ρ 2 L T -1 j=0 α 2 j T -1 i=j+1 (1 -r i ).
Now our task is to upper-bound bound the 1 -r k terms. From Eq. ( 18), we know that

r k = √ q k+1 η k = q k+1 ρL √ α k ≥ q k+1 ρL α k (Since α k ≤ 1 for all k) =⇒ (1 -r k ) ≤ 1 - q k+1 ρL α k
Since q k = µ for all k, putting everything together,

E[f (w T ) -f * ] ≤ T k=1 1 - 1 ρκ α k f (w 0 ) -f * + µ 2 w * -w 0 2 + 2σ 2 ρ 2 L T -1 j=0 α 2 j T -1 i=j+1 1 - 1 ρκ α i Denoting ∆ k = E[f (w k ) -f * ],
and using the exponential step-size

α k = α k /T = 1 T k /T , ∆ T ≤ 2 exp - 1 ρκ T k=1 α k ∆ 0 + 2σ 2 ρ 2 L T -1 k=0 α 2k exp - 1 ρκ T -1 i=k+1 α i
Using Lemma 8, we can bound the first term as

2 exp - 1 ρκ T k=1 α k ∆ 0 ≤ 2 exp - 1 ρκ αT ln( T /β) - 2β ln( T /β) ∆ 0 = 2c 3 exp - T √ κρ α ln( T /β) [f (w 0 ) -f * ]
where c 3 = exp 2β √ ρκ ln( T /β) . We can now bound the second term by a proof similar to Lemma 9. Indeed we have

T -1 k=0 α 2k exp - 1 ρκ T -1 i=k+1 α i = T -1 k=0 α 2k exp - 1 ρκ α k+1 -α T 1 -α = exp 1 √ ρκ α T 1 -α T -1 k=0 α 2k exp - 1 ρκ α k+1 1 -α ≤ exp 1 √ ρκ α T 1 -α T -1 k=0 α 2k 2(1 -α) √ ρκ eα k+1 2 (Lemma 15) = exp 1 √ ρκ α T 1 -α 4ρκ e 2 α 2 T (1 -α) 2 ≤ exp 1 √ ρκ α T 1 -α 4ρκ e 2 α 2 T ln( 1 /α) 2 = exp 1 √ ρκ α T 1 -α 4ρκ ln( T /β) 2 e 2 α 2 T Finally, exp 1 √ ρκ α T 1 -α = exp 1 α √ ρκ α T +1 1 -α ≤ exp 2β α √ ρκ ln( T /β)
where the inequality comes from the bound in Eq. ( 25) in the proof of Lemma 8. Putting everything together we obtain

E[f (w T ) -f * ] ≤ 2c 3 exp - T √ κρ α ln( T /β) [f (w 0 ) -f * ] + 8σ 2 c 4 κ ln( T /β) 2 ρLe 2 α 2 T where c 4 = exp 2β α √ ρκ ln( T /β) .

C.4 Lemmas for acceleration proofs

Lemma 8.

A := T t=1 α t ≥ αT ln( T /β) - 2β ln( T /β) Proof. T t=1 α t = α -α T +1 1 -α = α 1 -α - α T +1 1 -α
We have

α T +1 1 -α = αβ T (1 -α) = β T • 1 1 /α -1 ≤ β T • 2 ln( 1 /α) = β T • 2 1 T ln( T /β) = 2β ln( T /β) (25)
where in the inequality we used Lemma 14 and the fact that 1 /α > 1. Plugging back into A we get,

A ≥ α 1 -α - 2β ln( T /β) ≥ α ln( 1 /α) - 2β ln( T /β) (1 -x ≤ ln( 1 x )) = αT ln( T /β) - 2β ln( T /β) Lemma 9. For α = β T 1/T and any κ > 0, T k=1 α 2k exp - 1 κ T i=k+1 α i ≤ 4κ 2 c 2 (ln( T /β)) 2 e 2 α 2 T where c 2 = exp 1 κ 2β ln( T /β Proof. First observe that, T i=k+1 α i = α k+1 -α T +1 -α
We have

α T +1 1 -α = αβ T (1 -α) = β T • 1 1 /α -1 ≤ β T • 2 ln( 1 /α) = β T • 2 1 T ln( T /β) = 2β ln( T /β)
where in the inequality we used 14 and the fact that 1 /α > 1. These relations imply that,

T i=k+1 α i ≥ α k+1 1 -α - 2β ln( T /β) =⇒ exp - 1 κ T i=k+1 α i ≤ exp - 1 κ α k+1 1 -α + 1 κ 2β ln( T /β) = c 2 exp - 1 κ α k+1 1 -α
We then have , α k = α k , has the following convergence rate,

T k=1 α 2k exp - 1 κ T i=k+1 α i ≤ c 2 T k=1 α 2k exp - 1 κ α k+1 1 -α ≤ c 2 T k=1 α 2k 2(1 -α)κ eα k+1 2 (Lemma 15) = 4κ 2 c 2 e 2 α 2 T (1 -α) 2 ≤ 4κ 2 c 2 e 2 α 2 T (ln(1/α)) 2 = 4κ 2 c 2 (ln( T /β)) 2 e 2 α
E w T +1 -w * 2 ≤ w 1 -w * 2 c 2 exp - T κ α ln( T /β) + 8σ 2 c 2 κ 2 Le 2 (ln( T /β)) 2 α 2 T where κ = L µ and c 2 = exp 1 κ • 2β ln( T /β) .
Proof.

w k+1 -w * 2 = w k -η k ∇f ik (w k ) -w * 2 = w k -w * 2 -2η k ∇f ik (w k ), w k -w * + η 2 k ∇f ik (w k ) 2 = w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + γ 2 k α 2 k ∇f ik (w k ) 2 w k+1 -w * 2 ≤ w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + γ 2 k α 2 k 2L[f ik (w k ) -f * ik ] (Smoothness) = w k -w * 2 - 2 L α k ∇f ik (w k ), w k -w * + 2 L α 2 k [f ik (w k ) -f ik (w * )] + 2 L α 2 k [f ik (w * ) -f * ik ] (Since γ k = 1/L.) Taking expectation w.r.t i k , E w k+1 -w * 2 ≤ E w k -w * 2 - 2 L α k ∇f (w k ), w k -w * + 2 L α 2 k [f (w k ) -f (w * )] + 2 L α 2 k σ 2 ≤ E w k -w * 2 - 2 L α k ∇f (w k ), w k -w * + 2 L α k [f (w k ) -f (w * )] + 2 L α 2 k σ 2 (Since α k ≤ 1) E w k+1 -w * 2 ≤ 1 - µα k L E w k -w * 2 + 2 L α 2 k σ 2 (By µ-strong convexity of f )
Unrolling the recursion starting from w 1 and using the exponential step-sizes,

E w T +1 -w * 2 ≤ w 1 -w * 2 T k=1 1 - µα k L + 2σ 2 L T k=1 T i=k+1 α 2k 1 - µα i L Writing ∆ k = E w k -w * 2 ∆ T +1 ≤ ∆ 1 exp - µ L T k=1 α k :=A + 2σ 2 L T k=1 α 2k exp - µ L T i=k+1 α i :=Bt
Using Lemma 8 to lower-bound A, we obtain A ≥ αT ln( T /β) -2β ln( T /β) . The first term in the above expression can then be bounded as,

∆ 1 exp - µ L A = ∆ 1 c 2 exp - T κ α ln( T /β) ,
where κ = L µ and c 2 = exp 1 κ 2β ln( T /β) . Using Lemma 9 to upper-bound B t , we obtain

B t ≤ 4κ 2 c2(ln( T /β)) 2 e 2 α 2 T
, thus bounding the second term. Putting everything together,

∆ T +1 ≤ ∆ 1 c 2 exp - T κ α ln( T /β) + 8σ 2 c 2 κ 2 Le 2 (ln( T /β)) 2 α 2 T D.2 Proof of Theorem 4 Theorem 4. Assuming (i) convexity and L i -smoothness of each f i , (ii) µ strong-convexity of f , SGD (Eq. (2)) with α = β T 1/T
, α k = α k and γ k as the largest step-size that satisfies γ k ≤ γ max and Eq. ( 8) with c = 1 /2, has the following convergence rate,

E w T +1 -w * 2 ≤ w 1 -w * 2 c 1 exp - T κ α ln( T /β) + 8σ 2 c 1 (κ ) 2 γ max e 2 (ln( T /β)) 2 α 2 T + 2σ 2 c 1 κ ln(T /β) eα γ max -min γ max , 1 L with κ = max L µ , 1 µγmax , c 1 = exp 1 κ • 2β ln( T /β) .
Proof.

w k+1 -w * 2 ≤ w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + γ k α 2 k f ik (w k ) -f * ik c (By Lemma 11) Setting c = 1/2, = w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + 2γ k α 2 k [f ik (w k ) -f * ik ] = w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + 2γ k α 2 k [f ik (w k ) -f ik (w * )] + 2γ k α 2 k [f ik (w * ) -f * ik ] Adding, subtracting 2γ k α k [f ik (w k ) -f ik (w * )], = w k -w * 2 + 2γ k α k [-∇f ik (w k ), w k -w * + [f ik (w k ) -f ik (w * )]] -2γ k α k [f ik (w k ) -f ik (w * )] + 2γ k α 2 k [f ik (w k ) -f ik (w * )] + 2γ k α 2 k [f ik (w * ) -f * ik ] ≤ w k -w * 2 + 2γ min α k [-∇f ik (w k ), w k -w * + [f ik (w k ) -f ik (w * )]] -2γ k (α k -α 2 k )[f ik (w k ) -f ik (w * )] + 2γ max α 2 k [f ik (w * ) -f * ik ]
where we used convexity of f ik to ensure that -∇f ik (w k ),

w k -w * +[f ik (w k )-f ik (w * )] ≤ 0. Taking expectation, E w k+1 -w * 2 ≤ w k -w * 2 + 2γ min α k [-∇f (w k ), w k -w * + [f (w k ) -f (w * )]] -(α k -α 2 k )E [2γ k [f ik (w k ) -f ik (w * )]] + 2γ max α 2 k σ 2 E w k -w * 2 ≤ (1 -α k γ min µ) w k -w * 2 -(α k -α 2 k )E [2γ k [f ik (w k ) -f ik (w * )]] + 2γ max α 2 k σ 2 Since α k ≤ 1, and α k -α 2 k ≥ 0, let us analyze -E[[γ k [f ik (w k ) -f ik (w * )]]. -E[[γ k [f ik (w k ) -f ik (w * )]] = -E[[γ k [f ik (w k ) -f * ik ]] -E[[γ k [f * ik -f ik (w * )]] ≤ -E[[γ min [f ik (w k ) -f * ik ]] -E[[γ max [f * ik -f ik (w * )]] (γ k ≤ γ max ) = -E[[γ min [f ik (w k ) -f * ik ]] + γ max σ 2 = -E[[γ min [f ik (w k ) -f ik (w * )]] -E[[γ min [f ik (w * ) -f * ik ]] + γ max σ 2 = -γ min [f (w k ) -f (w * )] -γ min σ 2 + γ max σ 2 ≤ (γ max -γ min )σ 2
Putting this relation back,

E w k -w * 2 ≤ (1 -α k γ min µ) w k -w * 2 + 2(α k -α 2 k ) (γ max -γ min )σ 2 + 2γ max α 2 k σ 2 ≤ (1 -α k γ min µ) w k -w * 2 + 2α k (γ max -γ min )σ 2 + 2γ max α 2 k σ 2 . Setting κ = max{ L µ , 1 µγmax } we get that 1 -α k γ min µ ≤ 1 -1 κ . Writing ∆ k = E w k -w * 2
and unrolling the recursion we get

∆ T +1 ≤ T k=1 1 - 1 κ α k ∆ 1 + 2γ max σ 2 T k=1 α 2k T i=t+1 1 - 1 κ α i + 2 σ 2 T k=1 α k (γ max -γ min ) T i=k+1 1 - 1 κ α i ≤ ∆ 1 exp - 1 κ T k=1 α k :=A + 2γ max σ 2 T k=1 α 2k exp - 1 κ T i=k+1 α i :=Bt + 2 σ 2 (γ max -γ min ) T k=1 α k exp - 1 κ T i=k+1 α i :=Ct
Using Lemma 8 to lower-bound A, we obtain A ≥ αT ln( T /β) -2β ln( T /β) . The first term in the above expression can then be bounded as,

∆ 1 exp - 1 κ A ≤ ∆ 1 c 1 exp - T κ α ln( T /β) ,
where c 1 = exp , thus bounding the third term. Finally, by Lemma 11 we have that γ min ≥ min γ max , 1 L . Putting everything together, , α k = α k and γ k = ν L for ν > 0 has the following convergence rate,

∆ T +1 ≤ ∆ 1 c 1 exp - T κ α ln( T /β) + 8σ 2 c 1 (κ ) 2 γ max e 2 (ln( T /β)) 2 α 2 T + 2c 1 σ 2 κ ln(T /β) eα γ max -min γ max , 1
w T +1 -w * 2 ≤ w 1 -w * 2 c 2 exp - ν T κ α ln( T /β) + 8σ 2 L T exp ν κ 2β ln( T /β) 4κ 2 ln(T /β) 2 e 2 α 2 +   max j∈ T [ln(ν)] + ln( T /β) {f (w j ) -f * } (ν -1) L   × exp ν κ 2β ln( T /β) 8κ 2 νe 2 α 2 [ln(ν)] + ln(T /β) T , where κ = L µ , c 2 = exp ν κ 2β ln( T /β) and [x] + = max{x, 0}.
Proof. Following the steps from the proof of Theorem 3,

w k+1 -w * 2 ≤ w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + 2Lγ 2 k α 2 k [f ik (w k ) -f ik (w * )] + 2Lγ 2 k α 2 k [f ik (w * ) -f * ik ]
Taking expectation wrt i k , and since both γ k and α k are independent of i k ,

E w k+1 -w * 2 ≤ w k -w * 2 -2γ k α k ∇f (w k ), w k -w * + 2Lγ 2 k α 2 k [f (w k ) -f * ] + 2Lγ 2 k α 2 k σ 2 E w k+1 -w * 2 ≤ (1 -µγ k α k ) w k -w * 2 + 2Lγ 2 k α 2 k σ 2 + [f (w k ) -f * ] (2Lγ 2 k α 2 k -2γ k α k ) (By strong convexity)
Since γ k = ν L for some ν ≥ 1, we require α k ≤ 1 ν for the last term to be negative. By definition of α k , this will happen after k ≥ k 0 := T ln(ν) ln( T /β) iterations. However, until k 0 iterations, we observe that (2Lγ

2 k α 2 k -2γ k α k ) ≤ 2ν (ν-1) L α 2 k , meaning that for k < k 0 , E w k+1 -w * 2 ≤ (1 -µγ k α k ) w k -w * 2 + 2Lγ 2 k α 2 k σ 2 + max j∈[k0] {f (w j ) -f * } 2ν (ν -1) L α 2 k Writing ∆ k = E w k -w * 2
, and unrolling the recursion for the first k 0 iterations we get

∆ k0 ≤ ∆ 1 k0-1 k=1 (1 - µν L α k ) +      2L ν 2 L 2 σ 2 + max j∈[k0] {f (w j ) -f * } 2ν(ν -1) L :=c5      k0-1 k=1 α 2 k k0-1 i=k+1 (1 - µν L α i )
Bounding the first term similar to Lemma 8,

k0-1 k=1 (1 - µν L α k ) ≤ exp - µν L α -α k0 1 -α
Bounding the second term similar to Lemma 9,

k0-1 k=1 α 2 k k0-1 i=k+1 (1 - µν L α i ) ≤ k0-1 k=1 α 2 k exp - µν L k0-1 i=k+1 α i = k0-1 k=1 α 2 k exp - ν κ α k+1 -α k0 1 -α = exp να k0 κ(1 -α) k0-1 k=1 α 2 k exp - να k+1 κ(1 -α) ≤ exp να k0 κ(1 -α) k0-1 k=1 α 2 k 2(1 -α)κ νeα k+1 2 ≤ exp να k0 κ(1 -α) 4(1 -α) 2 κ 2 ν 2 e 2 α 2 k 0 ≤ exp να k0 κ(1 -α) 4κ 2 ν 2 e 2 α 2 k 0 ln(T /β) 2 T 2
Putting everything together, we obtain,

∆ k0 ≤ ∆ 1 exp - µν L α -α k0 1 -α + c 5 exp να k0 κ(1 -α) 4κ 2 ν 2 e 2 α 2 k 0 ln(T /β) 2 T 2
Now let us consider the regime k ≥ k 0 where α k ≤ 1 ν , so that we have

E w k+1 -w * 2 ≤ (1 -µγ k α k ) w k -w * 2 + 2ν 2 σ 2 L α 2 k Writing ∆ k = E w k -w * 2
, and unrolling the recursion from k = k 0 to T ,

∆ T +1 ≤ ∆ k0 T k=k0 (1 - µν L α k ) + 2ν 2 σ 2 L T k=k0 α 2 k T i=k+1 (1 - µν L α i )
Bounding the first term similar to Lemma 8,

T k=k0 (1 - µν L α k ) ≤ exp - µν L T k=k0 α k = exp -µν L α k0 -α T +1 1 -α
Bounding the second term similar to Lemma 9,

T k=k0 α 2 k T i=k+1 (1 - µν L α i ) ≤ T k=k0 α 2 k exp - µν L T i=k+1 α i = T k=k0 α 2 k exp - ν κ α k+1 -α T +1 1 -α = exp να T +1 κ(1 -α) T k=k0 α 2 k exp - να k+1 κ(1 -α) ≤ exp να T +1 κ(1 -α) T k=k0 α 2 k 2(1 -α)κ νeα k+1 2 = exp να T +1 κ(1 -α) 4(1 -α) 2 κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ≤ exp να T +1 κ(1 -α) 4κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ln(T /β) 2 T 2
Putting everything together,

∆ T +1 ≤ ∆ k0 exp -µν L α k0 -α T +1 1 -α + 2ν 2 σ 2 L exp να T +1 κ(1 -α) 4κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ln(T /β) 2 T 2
Combining the above bounds, we get,

∆ T +1 ≤ exp -µν L α k0 -α T +1 1 -α ∆ 1 exp - µν L α -α k0 1 -α + c 5 exp µνα k0 L(1 -α) 4κ 2 ν 2 e 2 α 2 k 0 ln(T /β) 2 T 2 + 2c 2 σ 2 L exp να T +1 κ(1 -α) 4κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ln(T /β) 2 T 2 = ∆ 1 exp -µν L α -α T +1 1 -α + c 5 exp µν L α T +1 1 -α 4κ 2 ν 2 e 2 α 2 k 0 ln(T /β) 2 T 2 + 2ν 2 σ 2 L exp να T +1 κ(1 -α) 4κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ln(T /β) 2 T 2
Using Lemma 8 to bound the first term

∆ T +1 ≤ ∆ 1 c 2 exp - ν T κ α ln( T /β) + c 5 exp µν L α T +1 1 -α 4κ 2 ν 2 e 2 α 2 k 0 ln(T /β) 2 T 2 + 2ν 2 σ 2 L exp να T κ(1 -α) 4κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ln(T /β) 2 T 2
where κ = L µ and c 2 = exp ν κ 2β ln( T /β) .

For bounding the second and third terms, note that α T +1 1-α ≤ 2β ln( T /β) , and k 0 = T ln(ν) ln( T /β) . Using these relations and the fact that α ≤ 1,

∆ T +1 ≤ ∆ 1 c 2 exp - ν T κ α ln( T /β) + c 5 exp ν κ 2β ln( T /β) 4κ 2 ν 2 e 2 α 2 ln(ν) ln(T /β) T + 2ν 2 σ 2 L exp ν κ 2β ln( T /β) 4κ 2 ν 2 e 2 α 2 (T -k 0 + 1) ln(T /β) 2 T 2
Putting in the value of c 5 and rearranging, we get

∆ T +1 ≤ ∆ 1 c 2 exp - ν T κ α ln( T /β) + 2ν 2 σ 2 L T exp ν κ 2β ln( T /β) 4κ 2 ln(T /β) 2 ν 2 e 2 α 2 + max j∈[k0] {f (w j ) -f * } 2ν(ν -1) L exp ν κ 2β ln( T /β) 4κ 2 ν 2 e 2 α 2
E[f ( wT +1 ) -f (w * )] ≤ 2L w 1 -w * 2 T k=1 α k + σ 2 T k=1 α 2 k T k=1 α k (11)
where

wT +1 = T k=1 α k w k T k=1 α k . For α k = β T k/T
, the convergence rate is given by,

E[f ( wT +1 ) -f (w * )] ≤ 2L ln(T /β) w 1 -w * 2 αT -2β + σ 2 T T -β
Proof. Following the proof of Theorem 3,

w k+1 -w * 2 ≤ w k -w * 2 -2γ k α k ∇f ik (w k ), w k -w * + 2Lγ 2 k α 2 k [f ik (w k ) -f ik (w * )] + 2 L γ 2 k α 2 k [f ik (w k ) -f * ik ] w k+1 -w * 2 ≤ w k -w * 2 - α k L ∇f ik (w k ), w k -w * + α 2 k 2L [f ik (w k ) -f ik (w * )] + α 2 k 2L [f ik (w k ) -f * ik ] (γ k = 1 2L for all k.) ≤ w k -w * 2 - α k L [f ik (w k ) -f ik (w * )] + α 2 k 2L [f ik (w k ) -f ik (w * )] + α 2 k 2L [f ik (w k ) -f * ik ] (By convexity) Taking expectation, E w k+1 -w * 2 ≤ w k -w * 2 - α k L [f (w k ) -f (w * )] + α 2 k 2L [f (w k ) -f (w * )] + α 2 k 2L σ 2 ≤ w k -w * 2 - α k 2L [f (w k ) -f (w * )] + α 2 k 2L σ 2 (Since f (w k ) -f (w * ) ≥ 0 and α k ≤ 1)
Rearranging and summing from k = 1 to T ,

T k=1 α k [f (w k ) -f (w * )] ≤ 2L w 1 -w * 2 + σ 2 T k=1 α 2 k
By averaging and using Jensen. Denote wT Bounding the ratio and any κ > 0,

+1 = T k=1 α k w k T k=1 α k , E[f ( wT +1 ) -f (w * )] ≤ 2L w 1 -w * 2 T k=1 α k + σ 2 T k=1 α 2 k T k=1 α k Next, we bound
T k=1 α 2 k T k=1 α k = T k=1 α 2k T k=1 α k where α = β T 1/T , T k=1 α 2k T k=1 α k ≤ α 2 1 -α 2 1 -α α -α T +1 = α 1 + α 1 1 -α T ≤ 1 1 -α T = T T -β Putting everything together, E[f ( wT +1 ) -f (w * )] ≤ 2L ln(T /β) w 1 -w * 2 αT -2β + σ 2 T T -β D
T k=1 α k exp - 1 κ T i=k+1 α i ≤ c 2 κ ln(T /β) eα for c 2 = exp 1 κ 2β ln(T /β)
Proof. Proceeding in the same way as Lemma 9, we obtain the following inequality,

T k=1 α k exp - 1 κ T i=k+1 α i ≤ c 2 T k=1 α k exp - 1 κ α k+1 1 -α Further bounding this term, T k=1 α k exp - 1 κ T i=t+1 α i ≤ c 2 T k=1 α k (1 -α)κ eα k+1 (Lemma 15) ≤ c 2 (1 -α) κT eα ≤ c 2 ln(1/α) κT eα = c 2 κ ln(T /β) eα Lemma 11. If f i is L i -smooth, stochastic lines-searches ensures that γ ∇f i (w) 2 ≤ 1 c (f i (w) -f * i ), and
min γ max , 2 (1 -c) L i ≤ γ ≤ γ max . Moreover, if f i is a one-dimensional quadratic, γ = min γ max , 2 (1 -c) L i Proof. Recall that if f i is L i -smooth, then for an arbitrary direction d, f i (w -d) ≤ f i (w) -∇f i (w), d + L i 2 d 2 .
For the stochastic line-search, d = γ∇f i (w). The smoothness and the line-search condition are then Smoothness:

f i (w -γ∇f i (w)) -f i (w) ≤ L i 2 γ 2 -γ ∇f i (w) 2 , Line-search: f i (w -γ∇f i (w)) -f i (w) ≤ -cγ ∇f i (w) 2 .
The line-search condition is looser than smoothness if

Li

2 γ 2 -γ ∇f i (w) 2 ≤ -cγ ∇f i (w) 2 .
The inequality is satisfied for any γ ∈ [a, b], where a, b are values of γ that satisfy the equation with equality, a = 0, b = 2(1-c) /Li, and the line-search condition holds for γ ≤ 2(1-c) /Li. As the line-search selects the largest feasible step-size, γ ≥ 2(1-c) /Li. If the step-size is capped at γ max , we have η ≥ min{γ max , 2(1-c) /Li}, and the proof for the stochastic line-search is complete.

From the previous discussion, observe that if γ > 2(1-c) Li , then we have

Li 2 γ 2 -γ ∇f i (w) 2 > -cγ ∇f i (w) 2 .
If f is a one-dimensional quadratic, the smoothness inequality is actually an equality, and thus

f i (w -γ∇f i (w)) -f i (w) = L i 2 γ 2 -γ ∇f i (w) 2 So if γ > 2(1-c) Li , f i (w -γ∇f i (w)) -f i (w) ≥ -cγ ∇f i (w) 2
and the line-search condition does not hold. This implies that for one-dimensional quadratics γ = min{γ max , 2(1-c) Li }

E.2 Proof of Theorem 7

Theorem 7. When using gradient descent to minimize a one-dimensional quadratic function

f (w) = 1 2 (xw -y) 2 , with α = β T 1/T , α k = α k and γ k = ν L for ν > 3 we have w k+1 -w * = (w 1 -w * ) k i=1
(1 -να i ).

After k := T ln(T /β) ln ν 3 iterations, we have that

|w k +1 -w * | ≥ 2 k |w 1 -w * |.
Proof. One has w * = y x and L = x 2 . Therefore

w k+1 -w * = w k -w * -α k η k x (xw k -y) = w k -w * -α k ν L Lw k + α k ν L xy = w k -w * -α k νw k + α k ρw * = (1 -να k )(w k -w * )
Iterating gives the first part of the result. Now, k ≤ k , we have

1 -να k ≤ 1 -να k ≤ 1 -να T ln(T /β) (ln ν-ln 3) = 1 -ν β T 1 ln(T /β) (ln ν-ln 3) = 1 -ν 3 ν = -2
and thus

|w k +1 -w * | =|w 1 -w * | k i=1 |1 -να k | ≥|w 1 -w * |2 k E.
3 Lemmas for convex setting Lemma 12. The polynomial stepsize defined as

α k = ( 1 /k) δ for some 0 ≤ δ ≤ 1 cannot satisfy T k=1 α k ≥ C 1 T and T k=1 α 2 k ≤ C 2 √ T for positive constants C 1 and C 2 .
Proof. If δ = 0, α k = 1 for all k, and then

T k=1 α 2 k = T . If δ = 1, then T k=1 α k = Θ(ln T ). If 0 < δ < 1, basic calculus shows that T +1 1 1 x δ ≤ T k=1 1 k δ ≤ 1 + T 1 1 x δ and thus 1 1 -δ (T + 1) 1-δ -1 ≤ T k=1 1 k δ ≤ 1 + 1 1 -δ T 1-δ -1 which shows that T k=1 α k = Θ(T 1-δ
), and thus we cannot have

T k=1 α k ≥ C 1 T for all T .
Lemma 13. The exponential stepsize defined as α k = α k for some α < 1 cannot satisfy

T k=1 α k ≥ C 1 T and T k=1 α 2 k ≤ C 2 √ T for positive constants C 1 and C 2 .
Proof. Suppose by contradiction that the exponential stepsize satisfies the two conditions. Then

C 2 √ T ≥ T k=1 α 2 k = T k=1 α 2k = 2T k=1 α k - T k=1 α 2k-1 = 2T k=1 α k - 1 α k=1 α 2k
By assumption,

2T k=1 α k ≥ C 1 2T and T k=1 α 2k ≤ C 2 √ T . Therefore 2T k=1 α k - 1 α T k=1 α 2k ≥ 2C 1 T - 1 α C 2 √ T But then we obtain C 2 √ T ≥ 2C 1 T - 1 α C 2 √ T
which is a contradiction by taking T to infinity.

F Helper Lemmas

Lemma 14. For all x > 1,

1 x -1 ≤ 2 ln(x) Proof. For x > 1, we have 1 x -1 ≤ 2 ln(x) ⇐⇒ ln(x) < 2x -2 Define f (x) = 2x -2 -ln(x). We have f (x) = 2 -1
x . Thus for x ≥ 1, we have f (x) > 0 so f is increasing on [1, ∞). Moreover we have f (1) = 2 -2 -ln(1) = 0 which shows that f (x) ≥ 0 for all x > 1 and ends the proof.

Lemma 15. For all x, γ > 0,

exp(-x) ≤ γ ex γ Proof. Let x > 0. Define f (γ) = γ ex γ -exp(-x). We have f (γ) = exp (γ ln(γ) -γ ln(ex)) -exp(-x) and f (γ) = γ • 1 γ + ln(γ) -ln(ex) exp (γ ln(γ) -γ ln(ex)) Thus f (γ) ≥ 0 ⇐⇒ 1 + ln(γ) -ln(ex) ≥ 0 ⇐⇒ γ ≥ exp (ln(ex) -1) = x
So f is decreasing on (0, x] and increasing on [x, ∞). Moreover,

f (x) = x ex x -exp(-x) = 1 e x -exp(-x) = 0
and thus f (γ) ≥ 0 for all γ > 0 which proves the lemma.

Lemma 16. For any sequence α

k T k=1 (1 -α k ) + T k=1 α k T i=k+1 (1 -α i ) = 1
Proof. We show this by induction on T . For T = 1,

(1 -α 1 ) + α 1 = 1 Induction step:

T +1 k=1 (1 -α k ) + T +1 k=1 α k T +1 i=k+1 (1 -α i ) = (1 -α T +1 ) T k=1 (1 -α k ) + α T +1 + T k=1 α k T +1 i=k+1 (1 -α i ) = (1 -α T +1 ) T k=1 (1 -α k ) + α T +1 + (1 -α T +1 ) T k=1 α k T i=k+1 (1 -α i ) = (1 -α T +1 )       T k=1 (1 -α k ) + T k=1 α k T i=k+1 (1 -α i ) =1       + α T +1 (Induction hypothesis) = (1 -α T +1 ) + α T +1 = 1
G Proof for misspecified ASGD

New proofs not included in current Arxiv version

Misspecified ASGD uses the same two sequences {w k , y k } and an additional extrapolation parameter b k . However, we do not have information about the smoothness L or the strong-convexity constant µ. Instead we estimate these problem-dependent parameters in an offline fashion (no correlation between i k and the estimation), and obtain L and μ. W.l.o.g, we will assume that 1 L = ν L L and μ = ν µ µ for some ν L , ν µ > 0. Specifically, the extrapolation parameter is now computed as follows:

r 2 k = (1 -r k )r 2 k-1 η k η k-1 + r k μη k . ( 26
) b k = (1 -r k-1 )r k-1 η k η k-1 r k + r 2 k-1 η k η k-1 , ( 27
)
where

η k = γ k α k = ν L ρL β T k/T , r k = ν L νµµ ρL β T k/2T
satisfy the above equations.

The above equations can be rewritten as:

r 2 k = (1 -r k )r 2 k-1 η k η k-1 + r k µ ν µ η k . ( 28
)
Defining ηk := ν µ η k and noting that the ratio ηk ηk-1 = η k η k-1 , satisfy the above equations.

r 2 k = (1 -r k )r 2 k-1 ηk ηk-1 + r k µ ηk . (29
For notational convenience we will redefine γ k := νγ k where ν = ν L ν µ and hence redefine η k := νη k . With these redefinitions, it is easy to see that the updates can be reformulated as a 3 variable sequence as in Appendix C.1 with a different choice of η k . Similarly, we can use the same definition of the estimating sequences as in Appendix C.2.

Given the definitions in Appendix C.2, we first prove the descent lemma for η k = ν ρL α k , where α k ≤ 1 is the exponentially decreasing step-size. 2 ], we obtain the following descent lemma.

E[f (w k+1 )] ≤ E[f (y k )] - η k 2 ∇f (y k ) 2 + ν 2 2ρ 2 L α 2 k σ 2 (For k ≥ k 0 ) E[f (w k+1 )] ≤ E[f (y k )] + G 2 ν 2 2ρL α 2 k + ν 2 2ρ 2 L α 2 k σ 2 (For k < k 0 )
Proof. By smoothness, and the update in Eq. ( 15),

f (w k+1 ) ≤ f (y k ) -η k ∇f (y k ), ∇f ik (y k ) + L 2 η 2 k ∇f ik (y k )
Taking expectation w.r.t. i k ,

E[f (w k+1 )] ≤ E[f (y k )] -η k ∇f (y k ) 2 + L 2 η 2 k E[ ∇f ik (y k ) 2 ]
(η k is independent of the randomness in i k .

)

≤ E[f (y k )] -η k ∇f (y k ) 2 + ρL 2 η 2 k E[ ∇f (y k ) 2 ] + L 2 η 2 k σ 2
(By the growth condition in Eq. ( 5))

= E[f (y k )] -η k ∇f (y k ) 2 + η k να k 2 E[ ∇f (y k ) 2 ] + ν 2 2ρ 2 L α 2 k σ 2 = E[f (y k )] - η k 2 ∇f (y k ) 2 - η k 2 (1 -να k ) ∇f (y k ) 2 + ν 2 2ρ 2 L α 2 k σ 2
For k ≥ k 0 , 1 -να k ≥ 0, and

E[f (w k+1 )] ≤ E[f (y k )] - η k 2 ∇f (y k ) 2 + ν 2 2ρ 2 L α 2 k σ 2
whereas for k < k 0 , 1 -να k > -να k , and since

η k = να k ρL , E[f (w k+1 )] ≤ E[f (y k )] + α 2 k ν 2 2ρL ∇f (y k ) 2 + ν 2 2ρ 2 L α 2 k σ 2 Defining G := max j∈[k0] E[ ∇f (y k ) 2 ], E[f (w k+1 )] ≤ E[f (y k )] + G 2 ν 2 2ρL α 2 k + ν 2 2ρ 2 L α 2 k σ 2
With this change, the proof of Lemma 18 can be modified, and the new result can be stated as follows:

Lemma 18. For the estimating sequences defined in Appendix C.2 and the updates in Eq. ( 14)-Eq. ( 19),

E[φ * k ] := E[inf w φ k (w)] ≥ E[f (w k )] -N k where N k := σ 2 ν 2 2ρ 2 L k-1 j=0 α 2 j k-1 i=j+1 (1 -r i ) + G 2 ν 2 2ρL min{k0,k}-1 j=0 α 2 j k-1 i=j+1 (1 -r i )
We now use the above lemma to prove the rate for strongly-convex functions.

≤ λ T φ * 0 + q 0 2 w * -z 0 2 -f * + N T Choosing φ * 0 = f (w 0 ), ≤ λ T f (w 0 ) -f * + q 0 2 w * -z 0 2 + N T Since z 0 = w 0 , q 0 = µ, =⇒ E[f (w T ) -f * ] ≤ λ T f (w 0 ) -f * + µ 2 w * -w 0 2 + σ 2 ν 2 2ρ 2 L T -1 j=0 α 2 j T -1 i=j+1 (1 -r i ) + G 2 ν 2 2ρL min{k0,T }-1 j=0 α 2 j T -1 i=j+1 (1 -r i )
Using the fact that λ 0 = 1 and λ k+1 = (1 -r k )λ k , we know that that λ T = T k=1 (1 -r k ), and

E[f (w T ) -f * ] ≤ T k=1 (1 -r k ) f (w 0 ) -f * + µ 2 w * -w 0 2 + 2σ 2 ν 2 ρ 2 L T -1 j=0 α 2 j T -1 i=j+1 (1 -r i ) + G 2 ν 2 2ρL min{k0,T }-1 j=0 α 2 j T -1 i=j+1
(1 -r i ).

Now our task is to upper-bound bound the 1 -r k terms. From Eq. ( 18), we know that

r k = √ q k+1 η k = q k+1 ν ρL √ α k ≥ q k+1 ν ρL α k (Since α k ≤ 1 for all k)
=⇒ (1 -r k ) ≤ 1 -q k+1 ν ρL α k

Since q k = µ for all k, putting everything together,

E[f (w T ) -f * ] ≤ T k=1 1 - ν ρκ α k f (w 0 ) -f * + µ 2 w * -w 0 2 + 2σ 2 ν 2 ρ 2 L T -1 j=0 α 2 j T -1 i=j+1 1 - ν ρκ α i + G 2 ν 2 2ρL min{k0,T }-1 j=0 α 2 j T -1 i=j+1 1 - ν ρκ α i .
Denoting ∆ k = E[f (w k ) -f * ], and using the exponential step-size

α k = α k /T = 1 T k /T , ∆ T ≤ 2 exp - ν ρκ T k=1 α k ∆ 0 + 2σ 2 ν 2 ρ 2 L T -1 k=0 α 2k exp - 1 ρκ T -1 i=k+1 α i + G 2 ν 2 2ρL min{k0,T }-1 k=0 α 2k exp - 1 ρκ T -1 i=k+1 α i
Using Lemma 8, we can bound the first term as

α i = T -1 k=0 α 2k exp - ν ρκ α k+1 -α T 1 -α = exp √ ν √ ρκ α T 1 -α T -1 k=0 α 2k exp - ν ρκ α k+1 1 -α ≤ exp √ ν √ ρκ α T 1 -α T -1 k=0 α 2k 2(1 -α) √ ρκ eα k+1 √ ν 2 (Lemma 15) = exp √ ν √ ρκ α T 1 -α 4ρκ e 2 να 2 T (1 -α) 2 ≤ exp √ ν √ ρκ α T 1 -α 4ρκ e 2

Theorem 4 .

 4 Assuming (i) convexity and L ismoothness of each f i , (ii) µ strong-convexity of f , SGD (Eq. (2)) with α = β T 1/T

Figure 1 :

 1 Figure1: Comparison of step-size strategies for (a) squared loss and (b) logistic loss. Observe that (i) exponentially decreasing step-sizes result in more stable performance compared to using a constant step-size (for both SGD and ASGD) and (ii) consistently outperform the noise-adaptive method in[START_REF] Khaled | Better theory for sgd in the nonconvex world[END_REF] and (iii) the stochastic line-search in Eq. (9) matches the performance of the variant with known smoothness.

  Assuming (i) convexity and L i -smoothness of each f i , (ii) µ strong-convexity of f , SGD (Eq. (2)) with γ k = 1 L ,

  Assuming (i) convexity and L i -smoothness of each f i , (ii) µ strong-convexity of f , SGD (Eq. (2)) with α = β T 1/T

  Assuming (i) convexity and (ii) L i -smoothness of each f i , SGD with step-size η k = 1 2L α k has the following convergence rate,

T

  k=1 α k and T k=1 α 2 k for the exponentially-decreasing α k sequence, when α k = β T k/T . From Lemma 8, we know that, T k=1 α k ≥ αT ln( T /β) -2β ln( T /β) .

  .5 Additional lemmas for upper-bound proofs Lemma 10. For α = β T 1/T

Lemma 17 .

 17 Using the update in Eq. (15) with η k = ν ρL α k , and defining k 0 := T [ln(ν)]+ ln(T /β) and G := max j∈[k0] E[ ∇f (y k )

Theorem 2 .

 2 Assuming (i) convexity and L i -smoothness of each f i , (ii) µ strong-convexity of f and (iii) the growth condition in Eq. (5), ASGD (Eqs. (3) and (4)) with w 0 = y 0 , γ k = ν L ρL , (ln( T /β)) 2 (eα) 2 LT min{ ln(ν) + ln(T /β) , 1}νG 2 where ν = ν L ν µ , κ = L µ , c 3 = exp 1 √ ρκ 2β √ ν ln( T /β) and c 4 = exp 1 α √ ρκ 2β √ ν ln( T /β) and G := max j∈[k0] E[ ∇f (y k )2 ] with k 0 := T ln(ν) + ln(T /β) and x + = max{ x , 0}.Proof. Using the reformulation in Lemma 5 gives us q k = µ for all k and z 0 = w 0 . For the estimating sequences defined in Appendix C.2, using Lemma 18, we know that the (reformulated) updates satisfy the following relationE[f (w T )] ≤ E[φ * T ] + N T ≤ E[φ T (w * )] + N T From Eq. (22), we know that for all w and k,φ k (w) ≤ (1 -λ k )f (w) + λ k φ 0 (w) Using these relations, E[f (w T )] ≤ (1 -λ T )f * + λ T φ 0 (w * ) + N T =⇒ E[f (w T ) -f * ] ≤ λ T [φ 0 (w * ) -f * ] + N TBy Eq. (21),

√

  ρκ ln( T /β) . We can now bound the second term by a proof similar to Lemma 9. Indeed we have

√

  να 2 T ln( 1 /α) 4ρκ ln( T /β) 2 min{k 0 , T } e 2 να 2 T 2 = exp √ ν √ ρκ α T 1 -α 4ρκ ln( T /β) 2 min ln(ν) ln(T /β) , 1 e 2 να 2 T ln( T /β)where the inequality comes from the bound in Eq. (25) in the proof of Lemma 8. Putting everything together we obtainE[f (w T ) -f * ] ≤ 2c 3 exp -√ νT √ κρ α ln( T /β)[f (w 0 ) -f * ] + 8ρc 4 κ ln( T /β) ρκ ln( T /β) .

Note that this result does not cover step-size sequences that switch between two values of δ, for example in(Khaled and Richtárik,

2020)

Acknowledgements

We would like to thank Si Yi Meng for helpful feedback on the paper. Benjamin Dubois-Taine would like to acknowledge funding by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

E Lower-bound proofs for Section 4 E.1 Proof of Theorem 5 Theorem 5. When using T iterations of SGD to minimize the sum f (w) = f1(w)+f2(w) 2 of two one-dimensional quadratics, f 1 (w) = 1 2 (w -1) 2 and f 2 (w) = 1 2 (2w + 1 /2) 2 , setting the step-size using SLS with γ max ≥ 1 and c ≥ 1 /2, any convergent sequence of α k results in convergence to a neighbourhood of the solution. Specifically, if w * is the minimizer of f and w 1 > 0, then,

Proof. For SLS with a general c ≥ 1 /2 on quadratics, we know that

(see Lemma 11 for a formal proof). Recall that we consider two one-dimensional quadratics

Using Lemma 16 and the fact that 2(1 -c)α k ≤ 1 for all k, we have that if w 1 -w * = w 1 > 0, E(w T -w * ) ≥ min w 1 , 3