Vincent Roulet
email: vroulet@uw.edu

Alexandre D'aspremont
email: aspremon@ens.fr

SHARPNESS, RESTART AND ACCELERATION

. The constants quantifying these sharpness bounds are of course unobservable, but we show that optimal restart strategies are robust, in the sense that, in some important cases, finding the best restart scheme only requires a log scale grid search. Overall then, restart schemes generically accelerate accelerated first-order methods.

INTRODUCTION

We study1 convex optimization problems of the form minimize f (x) (P)

where f is a convex function defined on R n . The complexity of these problems using first order methods is usually controlled by smoothness assumptions on f such as Lipschitz continuity of its gradient. Additional assumptions such as strong or uniform convexity provide respectively linear and faster polynomial rates of convergence [Nesterov, 2013b, Juditski and[START_REF] Juditski | Primal-dual subgradient methods for minimizing uniformly convex functions[END_REF]. However, these assumptions are often too restrictive to be applicable. Here, we make a much more generic assumption that describes the growth of the function around its minimizers using constants µ > 0 and r ≥ 1 such that µ r d(x, X * ) r ≤ f (x) -f * , for every x ∈ K, (Loja)

where f * is the minimum of f , K ⊃ X * is a given set and d(x, X * ) = min y∈X * x -y 2 is the Euclidean distance from x to the set X * of minimizers of f . This defines a lower bound on the function around its minimizers and quantifies the sharpness of the minimum. We exploit this property using restart schemes on classical convex optimization algorithms. The sharpness assumption (Loja) is also known as a Hölderian error bound on the distance to the set of minimizers. [START_REF] Hoffman | On approximate solutions of systems of linear inequalities[END_REF] first introduced error bounds to study systems of linear inequalities. Natural extensions were then developed for convex optimization by [START_REF] Robinson | An application of error bounds for convex programming in a linear space[END_REF], [START_REF] Mangasarian | A condition number for differentiable convex inequalities[END_REF], [START_REF] Auslender | Global regularity theorems[END_REF], notably through the concept of sharp minimum [Burke and[START_REF] Burke | Weak sharp minima in mathematical programming[END_REF][START_REF] Burke | Weak sharp minima revisited part i: basic theory[END_REF]. But the most striking result in this vein is due to Łojasiewicz [1963, 1993] who proved that inequality (Loja) holds generically for real analytic and subanalytic functions. This result has then been extended to non-smooth subanalytic convex functions by [START_REF] Bolte | The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF]. Overall then, condition (Loja) essentially measures the sharpness of minimizers, and holds generically. On the other hand, this inequality is purely implicit as r or µ are neither observed nor known a priori, and deriving adaptive schemes is thus crucial to ensure practical relevance.

Łojasiewicz inequalities either in the form of (Loja) or as gradient dominated properties [START_REF] Polyak | Gradient methods for minimizing functionals[END_REF] led to new convergence results for composite problems and for alternating or splitting methods [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality[END_REF][START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF][START_REF] Frankel | Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates[END_REF][START_REF] Karimi | Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition[END_REF]. Here we use this inequality to produce accelerated rates for restart schemes.

Restart schemes have already been studied for strongly or uniformly convex functions in e.g. [START_REF] Nemirovskii | Optimal methods of smooth convex minimization[END_REF], Nesterov, 2013a[START_REF] Juditski | Primal-dual subgradient methods for minimizing uniformly convex functions[END_REF][START_REF] Lin | An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization[END_REF]. In particular, [START_REF] Nemirovskii | Optimal methods of smooth convex minimization[END_REF] link a "strict minimum" condition akin to (Loja) with faster convergence rates using restart schemes which form the basis of our results, but they do not study the cost of adaptation and do not tackle the non-smooth case. In a similar spirit, weaker versions of this strict minimum condition were used more recently to study the performance of restart schemes in [START_REF] Renegar | Efficient first-order methods for linear programming and semidefinite programming[END_REF], Freund and Lu, 2018, Roulet et al., 2019].

The fundamental question regarding restart schemes is to define when to restart. Several heuristics have been presented that used some criterion on the iterates to restart the accelerated algorithm and speed up convergence [START_REF] O'donoghue | Adaptive restart for accelerated gradient schemes[END_REF], Su et al., 2014[START_REF] Giselsson | Monotonicity and restart in fast gradient methods[END_REF]. However, they did not theoretically establish improved complexity bounds. The robustness of restart schemes was also studied by [START_REF] Fercoq | Restarting accelerated gradient methods with a rough strong convexity estimate[END_REF] for quadratic error bounds, i.e. (Loja) with r = 2, satisfied by the LASSO problem for example. [START_REF] Fercoq | Adaptive restart of accelerated gradient methods under local quadratic growth condition[END_REF] recently extended this work to produce adaptive restarts with theoretical guarantees of optimal performance, again for quadratic error bounds. In the same vein, [START_REF] Liu | Adaptive accelerated gradient converging method under hölderian error bound condition[END_REF] presented adaptive accelerated methods given Hölderian error bounds, but their results are not adaptive to the exponent of the error bound. The references above focus on smooth problems, but error bounds appear also for non-smooth ones, with [START_REF] Gilpin | First-order algorithm with O(log 1/ǫ) convergence for ǫequilibrium in two-person zero-sum games[END_REF] proving for example linear convergence of restart schemes in bilinear matrix games where the minimum is sharp, i.e. (Loja) with r = 1. Recently [START_REF] Renegar | A simple nearly-optimal restart scheme for speeding-up first order methods[END_REF] presented simple generic schemes inspired by an early draft of this work, and provide adaptive schemes in all regimes (not only the smooth case).

Our contribution here is to derive optimal scheduled restart schemes for general convex optimization problems on smooth, non-smooth or Hölder smooth functions satisfying a sharpness assumption. We then show that for smooth functions these schemes can be made adaptive with nearly optimal complexity (up to a squared log term) for a wide array of sharpness assumptions. We also analyze restart schemes based on a sufficient decrease of the primal gap, when the optimal value of the problem is known. In that case, restart schemes are shown to be optimal without requiring a log scale grid search on the parameters. Our proofs only rely on having access to the convergence bound of an accelerated method, therefore our results are directly extended to the non-Euclidean case with composite objective and to non-smooth functions that can be smoothed.

REGULARITY ASSUMPTIONS

1.1. Smoothness. Convex optimization problems (P) are generally divided in two classes: smooth problems, for which f has Lipschitz continuous gradients, and non-smooth problems for which f is not differentiable. Following [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF], we use a unified framework that extends the definition of Hölder smooth functions.

Definition 1.1. A function f is s-smooth for given 1 ≤ s ≤ 2 if there exists a constant L > 0 such that ∇f (x) -∇f (y) 2 ≤ L x -y s-1 2 , for all x, y ∈ dom f (Hölder)
and any subgradients ∇f (x) ∈ ∂f (x), ∇f (y) ∈ ∂f (y) of f at x, y respectively. We write H s,L the set of s-smooth functions with parameter L.

For s = 2, we retrieve the classical definition of smoothness [Nesterov, 2013b]. For s = 1 we get a classical assumption made in non-smooth convex optimization, i.e. that sub-gradients of the function are bounded. For s ∈]1, 2[ we get the definition of Hölder smooth functions. We generalize our results for functions smooth with respect to a non-Euclidean norm in Section 5.

1.2. Sharpness, Error Bounds. We study convex optimization problems whose objective satisfies a growth condition as defined below.

Definition 1.2. A function f satisfies a Łojasiewicz growth condition on a set K if there exist constants

r ≥ 1, µ > 0, such that µ r d(x, X * ) r ≤ f (x) -f * , for every x ∈ K, (Loja)
where f * is the minimum of f , d(x, X * ) = min y∈X * x -y 2 is the Euclidean distance from x to the set X * of minimizers of f . We write L r,µ (K) the set of functions satisfying a Łojasiewicz growth condition on a set K with parameters r ≥ 1, µ > 0.

Condition (Loja) holds almost generically, and is notably satisfied by analytic and subanalytic functions (see [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF] for more details). However, the proof (see e.g. Bierstone and Milman [1988, Theorem 6.4]) uses topological arguments that are far from constructive. Hence, outside of some particular cases (e.g. strong convexity), we cannot assume that the constants in (Loja) are known, even approximately.

Error bounds are directly related to a Łojasiewicz inequality bounding the magnitude of the gradient [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF]. These properties underlie many recent results in optimization [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality[END_REF][START_REF] Frankel | Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates[END_REF][START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF]. Here, the sharpness condition in (Loja) allows us to accelerate convex optimization algorithms using restart schemes.

Our analysis relies on the condition that (Loja) is satisfied for any output of the algorithms we restart. By enforcing monotonicity of the objective values produced by those algorithms, this reduces to assume that (Loja) is satisfied on sublevel sets of the objective.

1.3. Sharpness and Smoothness. Given a convex function f ∈ H s,L , by using its Taylor expansion and the smoothness property, we get f (x) ≤ f * + L s x -y s 2 , for x ∈ dom f and y ∈ X * . Setting y to be the projection of x onto X * , this yields the following upper bound on suboptimality

f (x) -f * ≤ L s d(x, X * ) s . (1)
Now, assume moreover that f ∈ L r,µ (K) for a given set K such that X * ⊂ K ⊂ dom f . Combining ( 1) and (Loja) leads to sµ rL ≤ d(x, X * ) s-r , for every x ∈ K \ X * . This means that necessarily s ≤ r by taking x close enough to X * . Moreover if s < r, the set K must satisfy sup x∈K d(x, X * ) < +∞.

For the following, we define

κ L 2 s µ 2 r and τ 1 - s r ∈ [0, 1) (2)
a generalized condition number for the function f and a condition number based on the ratio of powers in inequalities (Hölder) and (Loja), respectively. Note that if r = s = 2, κ matches the classical condition number of the function.

SCHEDULED RESTARTS FOR SMOOTH CONVEX PROBLEMS

In this section, we seek to solve (P) assuming that the function f is smooth, i.e. satisfies (Hölder) with s = 2 and L > 0. Without further assumptions on f , an optimal algorithm to solve the smooth convex optimization problem (P) is Nesterov's accelerated gradient method [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate O(1/k 2 )[END_REF]. Given an initial point x 0 , this algorithm outputs, after t iterations, a point

x = A(x 0 , t) such that f (x) -f * ≤ cL t 2 d(x 0 , X * ) 2 , (3)
where c > 0 is a universal constant (whose value will be allowed to vary in what follows, with c = 4 here).

The accelerated algorithm can be enforced to output solutions whose objective decays monotonically as detailed in Appendix A. Consequently, if f satisfies a Łojasiewicz growth condition on the initial sub-level set K = {x : f (x) ≤ f (x 0 )}, then it is satisfied for any point output by the algorithm. Note that the arguments that we develop below are not specific to the algorithm of [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate O(1/k 2 )[END_REF] and would apply to any method satisfying the complexity bound (3) as shown for example in Section 5 that generalizes the results to the non-Euclidean setting. We now describe a restart scheme exploiting the extra regularity (Loja) to improve the computational complexity of solving problem (P) using accelerated methods.

2.1. Scheduled restarts. Here, we schedule the number of iterations t k made by the accelerated gradient algorithm between restarts, with t k being the number of (inner) iterations at the k th algorithm run (outer iteration). Our scheme is described in Algorithm 1 below.

Algorithm 1 Scheduled restarts for smooth convex minimization Inputs : x 0 ∈ R n and a sequence t k for k = 1, . . . , R.

for k = 1, . . . , R do

x k := A(x k-1 , t k ) end for Output : x := x R
The analysis of this scheme and the following ones rely on two steps. We first choose schedules that ensure linear convergence of the objective values f (x k ) w.r.t. k at a given rate. We then adjust this linear rate to minimize complexity, i.e. the total number of inner iterations. We begin with a technical lemma which assumes linear convergence holds, and connects the growth of t k , the precision reached and the total number of inner iterations N .

Lemma 2.1. Let x k be a sequence whose k th iterate is generated from the previous one by an algorithm that runs t k iterations and write N = R k=1 t k the total number of iterations to output a point x R . Suppose setting t k = Ce αk , (k = 1, . . . , R) for some C > 0 and α ≥ 0 ensures that the outer iterations satisfy

f (x k ) -f * ≤ νe -γk , ( 4
)
for all k ≥ 0 where ν ≥ 0 and γ ≥ 0. Then, precision at the output is given by,

f (x R ) -f * ≤ ν exp(-γN/C), when α = 0, and f (x R ) -f * ≤ ν (αe -α C -1 N + 1) γ α
, when α > 0.

Proof. When α = 0, N = RC, and inserting this in (4) at the last point x R yields the desired result. On the other hand, when α > 0, we have N = R k=1 t k = Ce α e αR -1 e α -1 , which gives R = log e α -1 e α C N + 1 /α. Inserting this in (4) at the last point, we get

f (x R ) -f * ≤ ν exp - γ α log e α -1 e α C N + 1 ≤ ν (αe -α C -1 N + 1) γ α
, where we used e x -1 ≥ x. This yields the second part of the result.

The last approximation in the case α > 0 simplifies the analysis that follows, without significantly affecting the bounds. We also show in Appendix B that using integer values tk = ⌈t k ⌉ does not significantly affect the bounds above.

We now analyze restart schedules t k that ensure linear convergence. Our choice of t k will heavily depend on the ratio between r and s (with s = 2 for smooth functions here), measured by τ = 1 -s/r defined in (2). Below, we show that if τ = 0, a constant schedule is sufficient to ensure linear convergence. When τ > 0, we need a geometrically increasing number of iterations for each cycle.

Proposition 2.2. Let f be a convex function and x 0 ∈ dom f . Denote K = {x : f (x) ≤ f (x 0 )} and assume that f ∈ H 2,L ∩ L r,µ (K). Run Algorithm 1 from x 0 with iteration schedule t k = C * κ,τ e τ k , for k = 1, . . . , R, where

C * κ,τ e 1-τ (cκ) 1 2 (f (x 0 ) -f * ) -τ 2 , ( 5
)
with κ and τ defined in (2) and c = 4e 2/e here. The precision reached at the last point x is given by,

f (x) -f * ≤ exp -2e -1 (cκ) -1 2 N (f (x 0 ) -f * ) = O exp(-κ -1 2 N ) , when τ = 0, (6)
while,

f (x) -f * ≤ f (x 0 ) -f * τ e -1 (f (x 0 ) -f * ) τ 2 (cκ) -1 2 N + 1 2 τ = O N -2 τ , when τ > 0, (7)
where N = R k=1 t k is the total number of iterations.

Proof. Our strategy is to choose t k such that the objective is linearly decreasing, i.e.

f (x k ) -f * ≤ e -γk (f (x 0 ) -f * ), (8)
for some γ ≥ 0 depending on the choice of t k . This directly holds for k = 0 and any γ ≥ 0. Combining (Loja) with the complexity bound in (3), we get

f (x k ) -f * ≤ cκ t 2 k (f (x k-1 ) -f * ) 2 r , (9)
where c = 4e 2/e using that r 2/r ≤ e 2/e . Assuming recursively that ( 8) is satisfied at iteration k -1 for a given γ, we have

f (x k ) -f * ≤ cκe -γ 2 r (k-1) t 2 k (f (x 0 ) -f * ) 2 r ,
and to ensure (8) at iteration k, we impose

cκe -γ 2 r (k-1) t 2 k (f (x 0 ) -f * ) 2 r ≤ e -γk (f (x 0 ) -f * ).
Rearranging terms in this last inequality, using τ defined in (2), we get

t k ≥ e γ(1-τ ) 2 (cκ) 1 2 (f (x 0 ) -f * ) -τ 2 e τ γ 2 k . ( 10
)
For a given γ ≥ 0, we can set t k = Ce αk where

C = e γ(1-τ ) 2 (cκ) 1 2 (f (x 0 ) -f * ) -τ 2 and α = τ γ/2, (11)
and Lemma 2.1 then yields,

f (x) -f * ≤ exp -γe -γ 2 (cκ) -1 2 N (f (x 0 ) -f * ), when τ = 0, while f (x) -f * ≤ f (x 0 ) -f * τ 2 γe -γ 2 (cκ) -1 2 (f (x 0 ) -f * ) τ 2 N + 1 2 τ
, when τ > 0. These bounds are minimal for γ = 2, which yields the desired result.

When τ = 0, bound (6) matches the classical complexity bound for smooth strongly convex functions [Nesterov, 2013b]. When τ > 0 on the other hand, bound (7) highlights a faster convergence rate than accelerated gradient methods. The sharper the function (i.e. the closer r is to 2), the faster the convergence. This matches the lower bounds for optimizing smooth and sharp functions functions up to constant factors [Nemirovskii and Nesterov, 1985, Eq. 1.21]. Also, setting t k = C * κ,τ e τ k yields continuous bounds on precision, i.e. when τ → 0, bound (7) converges to bound (6), which also shows that for τ near zero, constant restart schemes are almost optimal.

Note that for N ≤ C * κ,τ , the bounds ( 6), ( 7) are not informative. Precisely, the lower bounds for this problem as presented in [Nemirovskii and Nesterov, 1985, Eq. 1.21] are not informative for small N . In that case, the optimal rate is given by the accelerated scheme and consequently by Algorithm 1 before the first restart.

2.2. Adaptive scheduled restart. The previous restart schedules depend on the sharpness parameters (r, µ) in (Loja). In general of course, these values are neither observed nor known a priori. Making the restart scheme adaptive is thus crucial to its practical performance. Fortunately, we show below that a simple logarithmic grid search on these parameters is enough to guarantee nearly optimal performance.

We begin with the following Proposition that stems from the proof of Proposition 2.2.

Proposition 2.3. Let f be a convex function and

x 0 ∈ dom f . Denote K = {x : f (x) ≤ f (x 0 )} and assume that f ∈ H 2,L ∩ L r,µ (K).
Run Algorithm 1 from x 0 with general schedules of the form

t k = C if τ = 0, t k = Ce αk if τ > 0. If τ = 0 and C ≥ C * κ,0 , then f (x) -f * ≤ cκ C 2 N C (f (x 0 ) -f * ), (12)
while, if τ > 0 and C ≥ C(α), then

f (x) -f * ≤ f (x 0 ) -f * (αe -α C -1 N + 1) 2 τ , ( 13
)
where

C(α) e α(1-τ ) τ (cκ) 1 2 (f (x 0 ) -f * ) -τ 2 , ( 14
)
and N = R k=1 t k is the total number of iterations. Proof. Given general schedules of the form

t k = C if τ = 0, t k = Ce αk if τ > 0,
the best value of γ satisfying condition (10) for any k ≥ 0 in Proposition 2.2 is given by

γ = log C 2 cκ if τ = 0 and C ≥ C * κ,0 , γ = 2α τ if τ > 0 and C ≥ C(α).
As in Proposition 2.2, plugging these values into the bounds of Lemma 2.1 yields the desired result.

We run several schemes with a fixed number of inner iterations N to perform a log-scale grid search on τ and κ. We define these schemes as follows.

S i,0 : Restart Algorithm 1 with

t k = C i , S i,j : Restart Algorithm 1 with t k = C i e τ j k , ( 15
)
where C i = 2 i and τ j = 2 -j . We stop each of these schemes when the total number of its inner iterations has exceeded N , i.e. at the smallest R such that R k=1 t k ≥ N . The size of the grid search in C i is naturally bounded as we cannot restart the algorithm after more than N total inner iterations, so i ∈ [1, . . . , ⌊log 2 N ⌋].

We also show that when τ is smaller than 1/N , a constant schedule where t k = C performs as well as the optimal geometrically increasing schedule where t k = C * κ,τ e τ k . This crucially means we can also choose j ∈ [1, . . . , ⌈log 2 N ⌉], hence limiting the cost of the grid search.

The following proposition details the convergence of this grid-search, using the same notations as in Proposition 2.2. As observed at the end of Section 2.1, the optimal bounds (6), ( 7) are only informative after a sufficient number of iterations, which is why we analyze the adaptive scheme only for a number of iterations N ≥ 2C * κ,τ . To get optimal bounds in all regimes, it suffices to run an additional non-restarted algorithm that will also capture the best rate in the case N < 2C * κ,τ . Proposition 2.4. Let f be a convex function and

x 0 ∈ dom f . Denote K = {x : f (x) ≤ f (x 0 )}, assume that f ∈ H 2,L ∩ L r,µ (K) and denote by N ≥ 2C * κ,τ a given number of iterations. Run schemes S i,j defined in (15) to solve (P) for i ∈ [1, . . . , ⌊log 2 N ⌋] and j ∈ [0, . . . , ⌈log 2 N ⌉],
stopping each time after N total inner algorithm iterations, i.e. for R such that R k=1 t k ≥ N . If τ = 0, there exists i ∈ [1, . . . , ⌊log 2 N ⌋] such that the scheme S i,0 achieves a precision given by

f (x) -f * ≤ exp -e -1 (cκ) -1 2 N (f (x 0 ) -f * ).
If τ > 0, there exist i ∈ [1, . . . , ⌊log 2 N ⌋] and j ∈ [0, . . . , ⌈log 2 N ⌉] such that the scheme S i,j achieves a precision given by

f (x) -f * ≤ f (x 0 ) -f * τ e -1 (cκ) -1 2 (f (x 0 ) -f * ) τ 2 (N -1)/4 + 1 2 τ .
Overall, running the logarithmic grid search has a complexity (log 2 N ) 2 times higher than running N iterations using the optimal (oracle) scheme.

Proof. Denote R the number of restarts of a scheme S ij , we have for j = 0, R = ⌈N/C i ⌉ and for j = 0, R = ⌈log e τ j -1

e τ j C i N + 1 /τ j ⌉. Denote N ′ = R k=1 t k ≥ N
the number of iterations of a scheme S i,j . We necessarily have N ′ ≤ 2e 1/2 N for our choice of C i and τ j . Hence the cost of running all methods is of the order of N (log 2 N ) 2 .

If τ = 0 and N ≥ 2C * κ,0 , then i = ⌈log 2 C * κ,0 ⌉ ≤ ⌊log 2 N ⌋. Therefore S i,0 has been run and bound (12) shows then that the last iterate x satisfies

f (x) -f * ≤ cκ C 2 i N C i (f (x 0 ) -f * ). Using that C * κ,0 ≤ C i ≤ 2C * κ,0 , f (x) -f * ≤ cκ (C * κ,0 ) 2 N 2C * κ,0 (f (x 0 ) -f * ) ≤ exp -e -1 (cκ) -1 2 N (f (x 0 ) -f * ). If τ ≥ 1 N and N ≥ 2C * κ,τ , then j = ⌈-log 2 τ ⌉ ≤ ⌈log 2 N ⌉ and i = ⌈log 2 C * κ,τ ⌉ ≤ ⌊log 2 N ⌋. Therefore scheme S i,j has been run. As C i ≥ C * κ,τ ≥ C(τ j )
, where C(τ j ) is defined in ( 14), bound (13) shows that the last iterate x of scheme S i,j satisfies

f (x) -f * ≤ f (x 0 ) -f * τ j e -τ j C -1 i N + 1 2 τ .
Finally, by definition of i and j, 2τ j ≥ τ and

C i ≤ 2C * κ,τ , so f (x) -f * ≤ f (x 0 ) -f * τ e -τ j (C * κ,τ ) -1 N/4 + 1 2 τ = f (x 0 ) -f * τ e -1 (cκ) -1 2 (f (x 0 ) -f * ) τ 2 N/4 + 1 2 τ
, where we concluded by expanding C * κ,τ = e 1-τ (cκ)

1 2 (f (x 0 ) -f * ) -τ 2 and using that τ ≥ τ j . If 1 N > τ > 0 and N > 2C * κ,τ , then i = ⌈log 2 C * κ,τ ⌉ ≤ ⌊log 2 N ⌋,
so scheme S i,0 has been run. As in (9), its iterates x k satisfy, with 1 -τ = 2/r,

f (x k ) -f * ≤ cκ C 2 i (f (x k-1 ) -f * ) 2 r ≤ cκ C 2 i (1-(1-τ) k )/τ (f (x 0 ) -f * ) (1-τ ) k ≤ cκ(f (x 0 ) -f * ) -τ C 2 i (1-(1-τ) k )/τ (f (x 0 ) -f * ). Now C i ≥ C * κ,τ = e 1-τ (cκ) 1 2 (f (x 0 ) -f * ) -τ 2 and C i R ≥ N , therefore last iterate x satisfies f (x) -f * ≤ exp -2(1 -τ ) 1 -(1 -τ ) N/C i τ (f (x 0 ) -f * ). As N ≥ C i , since h(τ ) = (1-τ ) 1-(1-τ ) N C i 1-(1-τ )
is decreasing with τ and 1 N > τ > 0, we have

f (x) -f * ≤ exp -2(N -1) 1 -1 - 1 N N/C i (f (x 0 ) -f * ) ≤ exp -2(N -1) 1 -exp - 1 C i (f (x 0 ) -f * ) ≤ exp -2 N -1 C i 1 - 1 2C i (f (x 0 ) -f * ).
having used the facts that

(1 + ax) b x ≤ exp(ab) if ax ≥ -1, b x ≥ 0 and 1 -x + x 2 2 ≥ exp(-x) when x ≥ 0. As C i = 2 i ≥ 1, we finally get f (x) -f * ≤ exp - N -1 C i (f (x 0 ) -f * ) ≤ exp - N -1 2C * κ,τ (f (x 0 ) -f * ) ≤ f (x 0 ) -f * τ (C * κ,τ ) -1 (N -1)/4 + 1 2 τ ≤ f (x 0 ) -f * τ (f (x 0 ) -f * ) τ 2 e -1 (cκ) -1 2 (N -1)/4 + 1 2 τ .
using the fact that e τ ≥ 1.

In the strongly convex case, this adaptive bound is similar to the one of [Nesterov, 2013a] to optimize smooth strongly convex functions in the sense that we lose approximately a log factor of the condition number of the function. However our assumptions are weaker and our bound also handles all sharpness regimes, i.e. any exponent r ∈ [2, +∞], not just the strongly convex case. Finally the step size chosen for the grid search was set to 2. The proof can be adapted for a generic step size h, the size of the grid may be reduced but corresponding bounds will suffer an h 2 approximation loss compared to the best schedule.

Note that the scheduled restart schemes we present here adapt to a global sharpness hypothesis on the sublevel set defined by the initial point and are not locally adaptive to potentially better constant µ on smaller sublevel sets. On the other hand, restart schemes based on a primal gap, presented in Section 4, do adapt to the local value of µ, although these schemes require having access to the primal gap.

2.3. Comparison to gradient descent. We end this section by analyzing the behavior of gradient descent in light of the sharpness assumption in order to compare the advantage of restarted accelerated method to plain gradient descent. While the bounds we obtain using the basic gradient method are suboptimal compared to the ones above, the gradient algorithm having no memory will automatically adapt to the best "restart" schedule. Given only the smoothness hypothesis, the gradient descent algorithm, presented in e.g. [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF], starts from a point x 0 and outputs iterates

x t = G(x 0 , t) such that f (x t ) -f * ≤ L t d(x 0 , X * ) 2 .
While accelerated methods use the last two iterates to compute the next one, simple gradient descent algorithms use only the last iterate, so the algorithm can be seen as (implicitly) restarting at each iteration. Formally we use that its convergence can be bounded as, for k ≥ 1,

f (x k+t ) -f * ≤ L t d(x k , X * ) 2 . ( 16
)
and we analyze it in light of the restart interpretation using the sharpness property.

Proposition 2.5. Let f be a convex function and

x 0 ∈ dom f . Denote K = {x : f (x) ≤ f (x 0 )} and assume that f ∈ H 2,L ∩ L r,µ (K).
Denote by x t = G(x 0 , t) the iterate sequence generated by the gradient descent algorithm started at x 0 to solve (P) and define

t k = e 1-τ cκ(f (x 0 ) -f * ) τ e τ k ,
with κ and τ defined in (2) and c = e 2/e here. The precision reached after N = n k=1 t k iterations is given by,

f (x N ) -f * ≤ exp -e -1 (cκ) -1 N (f (x 0 ) -f * ) = O exp(-κ -1 N ) , when τ = 0, while, f (x N ) -f * ≤ f (x 0 ) -f * (τ e -1 (cκ) -1 (f (x 0 ) -f * ) τ N + 1) 1 τ = O N -1 τ , when τ > 0.
Proof. For a given γ ≥ 0, we construct a subsequence x φ(k) of x t such that

f (x φ(k) ) -f * ≤ e -γk (f (x 0 ) -f * ). (17)
Define x φ(0) = x 0 . Assume that ( 17) is true at iteration k -1, then combining complexity bound ( 16) and (Loja), for any t ≥ 1,

f (x φ(k-1)+t ) -f * ≤ cκ t (f (x φ(k-1) ) -f * ) 2 r ≤ cκ t e -γ 2 r (k-1) (f (x 0 ) -f * ) 2 r .
where c = e 2/e , using that r 2/r ≤ e 2/e . Taking t k = e γ(1-τ ) cκ(f (x 0 )-f * ) -τ e γτ k and φ(k) = φ(k-1)+t k ensures that (17) holds at iteration k. Using Lemma 2.1, we obtain at iteration

N = φ(n) = n k=1 t k , f (x N ) -f * ≤ exp -γe -γ (cκ) -1 N (f (x 0 ) -f * ), if τ = 0, and f (x N ) -f * ≤ f (x 0 ) -f * (τ γe -γ (cκ) -1 (f (x 0 ) -f * ) τ N + 1) 1 τ , if τ > 0.
These bounds are minimal for γ = 1 and the results follow.

We observe that restarting accelerated gradient methods reduces complexity from O(ǫ -τ ) to O(ǫ -τ /2 ) compared to simple gradient descent. More general results on the convergence of (sub)gradient descent algorithms under a Łojasiewicz inequality assumption were developed by [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF].

UNIVERSAL SCHEDULED RESTARTS FOR CONVEX PROBLEMS

In this section, we generalize previous results to s-smooth functions as defined in Definition 1.1 to tackle both smooth and non-smooth convex optimization problems. Without further assumptions on f , the optimal rate of convergence for this class of functions is bounded as O(1/N ρ ), where N is the total number of iterations and ρ = 3s/2 -1, (18) which gives ρ = 2 for smooth functions and ρ = 1/2 for non-smooth functions. The universal fast gradient method [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF] achieves this rate by requiring only a target accuracy ǫ and a starting point x 0 . It outputs after t iterations a point

x = U (x 0 , ǫ, t), such that f (x) -f * ≤ ǫ 2 + cL 2 s d(x 0 , X * ) 2 ǫ 2 s t 2ρ s ǫ 2 , ( 19
)
where c is a constant (c = 2 4s-2 s ). A simplified implementation of the universal fast gradient method that enforces monotonicity in objective values of the outputs of the algorithm is presented in Appendix A.

We assume again that f satisfies a Łojasiewicz growth condition on its initial sublevel set. The key difference with the smooth case described in the previous section is that here we schedule both the target accuracy ǫ k used by the algorithm and the number of iterations t k made at the k th run of the algorithm. Our scheme is described in Algorithm 2.

Algorithm 2 Universal scheduled restarts for convex minimization

Inputs : x 0 ∈ R n , ǫ 0 ≥ f (x 0 ) -f * , γ ≥ 0 and a sequence t k for k = 1, . . . , R. for k = 1, . . . , R do ǫ k := e -γ ǫ k-1 , x k := U (x k-1 , ǫ k , t k ) end for Output : x := x R
Our strategy is to choose a sequence t k that ensures

f (x k ) -f * ≤ ǫ k ,
for the geometrically decreasing sequence ǫ k . The overall complexity of our method will then depend on the growth of t k as described in Lemma 2.1.

Proposition 3.1. Let f be a convex function and

x 0 ∈ dom f . Denote K = {x : f (x) ≤ f (x 0 )} and assume that f ∈ H s,L ∩ L r,µ (K). Run Algorithm 2 from x 0 for a given ǫ 0 ≥ f (x 0 ) -f * with γ = ρ, t k = C * κ,τ,ρ e τ k , where C * κ,τ,ρ e 1-τ (cκ) s 2ρ ǫ -τ ρ 0
where ρ is defined in (18), κ and τ are defined in (2) and c = 8e 2/e here. The precision reached at the last point x is given by,

f (x) -f * ≤ exp -ρe -1 (cκ) -s 2ρ N ǫ 0 = O exp(-κ -s 2ρ N ) , when τ = 0, while, f (x) -f * ≤ ǫ 0 τ e -1 (cκ) -s 2ρ ǫ τ ρ 0 N + 1 -ρ τ = O N -ρ τ , when τ > 0,
where N = R k=1 t k is total number of iterations. Proof. Our goal is to ensure that the target accuracy is reached at each restart, i.e.

f (x k ) -f * ≤ ǫ k . ( 20
)
By assumption, (20) holds for k = 0. Assume that ( 20) is true at iteration k -1, combining (Loja) with the complexity bound in (19), then

f (x k ) -f * ≤ ǫ k 2 + cκ(f (x k-1 ) -f * ) 2 r ǫ 2 s k t 2ρ s k ǫ k 2 ≤ ǫ k 2 + cκ t 2ρ s k ǫ 2 r k-1 ǫ 2 s k ǫ k 2 , (21)
where c = 8e 2/e using that r 2/r ≤ e 2/e . By definition ǫ k = e -γk ǫ 0 , so to ensure (20

) at iteration k this imposes cκe γ 2 r e -γ( 2 r -2 s )k t 2ρ s k ǫ 2 r -2 s 0 ≤ 1.
Rearranging terms in last inequality, using τ defined in (2),

t k ≥ e γ 1-τ ρ (cκ) s 2ρ ǫ -τ ρ 0 e γτ ρ k .
Choosing t k = Ce αk , where

C = e γ 1-τ ρ (cκ) s 2ρ ǫ -τ ρ 0 and α = γτ ρ ,
and using Lemma 2.1 then yields,

f (x) -f * ≤ exp(-γe -γ ρ (cκ) -s 2ρ N )ǫ 0 , (22)
when τ = 0, while,

f (x) -f * ≤ ǫ 0 γτ ρ e -γ ρ (cκ) -s 2ρ ǫ τ ρ 0 N + 1 ρ τ . ( 23
)
when τ > 0. These bounds are minimal for γ = ρ and the results follow.

This bound matches the lower bounds for optimizing smooth and sharp functions up to constant factors [Nemirovskii and Nesterov, 1985, Eq. 1.21]. Notice that, compared to [START_REF] Nemirovskii | Optimal methods of smooth convex minimization[END_REF], we can tackle non-smooth convex optimization by using the universal fast gradient algorithm of [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF]. The rate of convergence in Proposition 3.1 is controlled by the ratio between τ and ρ. If these are unknown, a log-scale grid search will not be able to reach the optimal rate, even if ρ is known since we will miss the optimal rate by a constant factor, see Appendix C. If both are known, in the case of nonsmooth strongly convex functions for example, a grid-search on C recovers a nearly optimal bound. Finally note that our bound is provided with respect to the number of iterations of the accelerated algorithms, the corresponding bounds in terms of numbers of calls to the oracles can be found by analyzing the line-search cost of the fast universal gradient method.

RESTART WITH KNOWN PRIMAL GAP

Here, we assume that we know the optimum f * of (P). This is the case for example in zero-sum matrix game problems or over-parametrized least-squares without regularization. We assume again that f satisfies the generic smoothness assumption (Hölder) and the Łojasiewicz growth condition (Loja) on its initial sublevel set. We use again the universal gradient method U . Here however, we can stop the algorithm when it reaches the target accuracy as we know the optimum f * , i.e. we stop after t ǫ inner iterations such that x = U (x 0 , ǫ, t ǫ ) satisfies f (x) -f * ≤ ǫ, and write x C(x 0 , ǫ) the output of this method.

Here we simply restart this method and decrease the target accuracy by a constant factor after each restart. Our scheme is described in Algorithm 3. The following proposition describes its convergence.

Algorithm 3 Restart with known primal gap for convex minimization

Inputs : x 0 ∈ R n , f * , γ ≥ 0, ǫ 0 = f (x 0 ) -f * for k = 1, . . . , R do ǫ k := e -γ ǫ k-1 , x k := C(x k-1 , ǫ k ) end for Output : x := x R Proposition 4.1.
Let f be a convex function and x 0 ∈ dom f . Denote K = {x : f (x) ≤ f (x 0 )} and assume that f ∈ H s,L ∩ L r,µ (K). Run Algorithm 3 from x 0 with parameter γ = 1. The precision reached at the last point x is given by,

f (x) -f * ≤ exp -e -1 ρ (cκ) -s 2ρ N (f (x 0 ) -f * ) = O exp(-κ -s 2ρ N ) , when τ = 0, while, f (x) -f * ≤ f (x 0 ) -f * τ ρ e -1 ρ (cκ) -s 2ρ (f (x 0 ) -f * ) τ ρ N + 1 ρ τ = O N -ρ τ , when τ > 0,
where N is the total number of iterations, ρ is defined in (18), κ and τ are defined in (2) and c = 8e 2/e here. Those bounds are suboptimal to the best scheduled restarts by a factor at most e/2 ≈ 1.3.

Proof. Given γ ≥ 0, the linear convergence of our scheme is ensured by our choice of target accuracies ǫ k . It remains to compute the number of iterations t ǫ k needed by the algorithm before the k th restart. Following the proof of Proposition 3.1, for k ≥ 1 we know that the target accuracy is necessarily reached after tk = e γ 1-τ ρ (cκ)

s 2ρ ǫ -τ ρ 0 e γτ ρ k
iterations, such that t ǫ k ≤ tk . So Algorithm 3 achieves linear convergence while needing less inner iterates than the scheduled restart presented in Proposition 3.1, its convergence is therefore at least as good. For a given γ bounds ( 22) and ( 23) follow with ǫ 0 = f (x 0 ) -f * . The dependency in γ of the restart scheme in bounds ( 22) and ( 23) is a factor

h(γ) = γe -γ/ρ
of the number of iterations, whose maximum value is reached for γ = ρ. Taking γ = 1, then leads to a bound suboptimal by a constant factor of at most h(ρ)/h(1) ≤ e/2 ≈ 1.3 for ρ ∈ [1/2, 2], so running this scheme with γ = 1 makes it parameter-free while producing nearly optimal complexity.

When f * is known, the above restart scheme is adaptive, contrary to the general non-smooth case in Proposition 3.1. It can even adapt to the local values of L or µ as we use a criterion instead of a preset schedule. Here, stopping using f (x k ) -f * implicitly yields optimal choices of C and τ . Note that this approach generalizes to algorithms for which a bound on the primal gap is available as in the Frank-Wolfe algorithm, see [START_REF] Kerdreux | Restarting frank-wolfe[END_REF].

EXTENSIONS

Previous analyses of restart schemes only require bounds of the form (3) or (19). Our results extend then readily to non-Euclidean composite settings or structured objectives as presented below.

5.1. Composite Problems & Bregman Divergences. We extend previous schemes to more general convex optimization problems of the form

minimize f (x) φ(x) + g(x), ( 24
)
where g is a simple convex function (the meaning of simple will be clarified later), φ is a convex s-smooth function with respect to a given norm • (potentially non-Euclidean) as defined below, and φ is defined on an open-set containing dom g, i.e. dom f = dom g.

Definition 5.1. A function φ is s-smooth for a given 1 ≤ s ≤ 2 with respect to a norm • if there exists a constant L > 0 such that ∇φ(x) -∇φ(y) * ≤ L x -y s-1 , for all x, y ∈ dom φ and any subgradients ∇φ(x) ∈ ∂φ(x), ∇φ(y) ∈ ∂φ(y) of φ at x, y respectively, with • * being the dual norm of • . We denote by H s,L, • the set of s-smooth functions with respect to a norm • with parameter L.

To exploit the smoothness of φ with respect to a generic norm, we assume that we have access to a potential function h dom(f ) ⊂ dom(h), strongly convex with respect to the norm • with convexity parameter equal to one, which means

h(y) ≥ h(x) + ∇h(x) T (y -x) + 1 2
x -y 2 , for any x, y ∈ dom(h).

We define the Bregman divergence associated to h as, for given x, y ∈ dom(h),

D h (y; x) = h(y) -h(x) -∇h(x) T (y -x) ≥ 1 2 x -y 2 .
For h(x) = 1 2 x 2 2 , we get D h (y; x) = 1 2 x -y 2 2 and recover the Euclidean setting. Given the problem geometry, appropriate choices of potential functions and associated Bregman divergences can lead to significant performance gains in high dimensional settings. We now formally state the assumption that g is simple. Given x, y ∈ dom(f ) and λ ≥ 0 we assume that

min z y T z + g(z) + λD h (z; x) ( 25
)
can be solved either in a closed form or by some fast computational procedure. This setting includes some constrained optimization problems, where g is the indicator function of a closed convex set, on which we can easily project the points. It also includes sparse optimization problems, such as the LASSO, where φ

(x) = Ax -b 2 2 , with A ∈ R m×n , b ∈ R m , g(x) = λ x 1 , with λ ≥ 0 and h(x) = 1 2 x 2 2 .
To apply our analysis of restart schemes we need two things: an accelerated algorithm and an appropriate notion of sharpness. In the spirit of [START_REF] Bauschke | A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications[END_REF], Lu et al., 2018], we thus introduce the notion of relative sharpness.

Definition 5.2. A function f satisfies a relative Łojasiewicz growth condition with respect to a strictly convex function h on a set

K if there exist r ≥ 1, µ > 0 such that µ r D h (x, X * ) r 2 ≤ f (x) -f * for any x ∈ K (26)
where D h (x, X * ) = min x * ∈X * D h (x * ; x) and D h is the Bregman divergence associated to h. We denote by L r,µ,h (K) the set of functions satisfying a relative Łojasiewicz growth condition w.r.t to h on a set K with parameters r, µ.

If h = 1 2 x 2 2 we recover the definition of the Łojasiewicz growth in the Euclidean setting (with slightly modified constants). This assumption is as generic as our first one in (Loja) as it is satisfied if f and h are subanalytic [Bierstone and Milman, 1988, Th. 6.4].

The algorithms are essentially the same as before, except that the distance to the set of minimizers is replaced by the Bregman divergence to the set of minimizers. We keep the same notations for the algorithms as the implementations are the same as presented in Section A. Formally, if φ is smooth with respect to a norm • , the accelerated algorithm outputs after t iterations a point

x = A(x 0 , t) such that f (x) -f * ≤ cL t 2 D h (x 0 , X * ), (27)
where c = 8 here. The next Corollary generalizes Proposition 2.2.

Corollary 5.3. Let f = φ + g be a composite convex function, x 0 ∈ dom f and

K = {x : f (x) ≤ f (x 0 )}. Assume that φ ∈ H 2,L,
• for a given norm • , that f ∈ L r,µ,h (K) for h strongly convex with respect to • and that g is simple such that problems (25) can be computed efficiently. Run Algorithm 1 from x 0 with iteration schedule t k = C * κ,τ e τ k , for k = 1, . . . , R, where

C * κ,τ e 1-τ (cκ) 1 2 (f (x 0 ) -f * ) -τ 2 ,
with κ and τ defined in (2) and c = 8e 2/e . The precision reached at the last point x is given by,

f (x) -f * ≤ exp -2e -1 (cκ) -1 2 N (f (x 0 ) -f * ) = O exp(-κ -1 2 N ) , when τ = 0, while, f (x) -f * ≤ f (x 0 ) -f * τ e -1 (f (x 0 ) -f * ) τ 2 (cκ) -1 2 N + 1 2 τ = O N -2 τ , when τ > 0,
where N = R k=1 t k is the total number of iterations. Proof. The proof of Proposition 2.2 only relies on the bound in (9) that combines the growth condition (Loja) with the complexity bound in (3). For the case with composite problems and Bregman divergences we combine (26) with the bound ( 27), which ensures for the k th iterate of the restart scheme, f

(x k ) -f * ≤ cκ t 2 k (f (x k-1 ) -f * ) 2 r
, with here c = 8e 2/e . The rest of the proof follows as in Proposition 2.2.

For general convex functions, given a target accuracy ǫ and an initial point x 0 , the universal fast gradient method outputs after t iterations a point

x = U (x 0 , ǫ, t) such that f (x) -f * ≤ ǫ 2 + cL 2 s D h (x 0 , X * ) ǫ 2 s t 2ρ s ǫ 2 , (28)
where c = 2 5s-2 s here. The following Corollary generalizes then Proposition 3.1.

Corollary 5.4. Let f = φ + g be a composite convex function,

x 0 ∈ dom f and K = {x : f (x) ≤ f (x 0 )}. Assume that φ ∈ H s,L,
• for a given norm • , that f ∈ L r,µ,h (K) for h strongly convex with respect to • and that g is simple such that problems (25) can be computed efficiently. Run Algorithm 2 from x 0 for given

ǫ 0 ≥ f (x 0 ) -f * , γ = ρ, t k = C * κ,τ,ρ e τ k , where C * κ,τ,ρ e 1-τ (cκ) s 2ρ ǫ -τ ρ 0
where ρ is defined in (18), κ and τ are defined in (2) and c = 16e 2/e . The precision reached at the last point x is given by,

f (x) -f * ≤ exp -ρe -1 (cκ) -s 2ρ N ǫ 0 = O exp(-κ -s 2ρ N ) , when τ = 0, while, f (x) -f * ≤ ǫ 0 τ e -1 (cκ) -s 2ρ ǫ τ ρ 0 N + 1 ρ τ = O N -ρ τ , when τ > 0,
where N = R k=1 t k is total number of iterations.

Proof. The proof of Proposition 3.1 only relies on the bound in ( 21) that combines the growth condition (Loja) with the complexity bound in (19). For the case with composite problems and Bregman divergences we combine (26) with the bound (28), which ensures for the k th iterate of the restart scheme,

f (x k ) -f * ≤ ǫ k 2 + cκ(f (x k-1 )-f * ) 2 r ǫ 2 s k t 2ρ s k ǫ k
2 with here c = 16e 2/e . The rest of the proof follows as in Proposition 3.1.

The results regarding adaptive schemes and those for which f * is known, i.e. Propositions 2.4 and 4.1 respectively, generalize similarly under the relative growth assumption. Those results apply then to generic ℓ 1,p regularized prediction problems where g is an ℓ 1,p norm and φ is a data-fitting term. Indeed error bounds were proven to hold for those problems by Zhou et al. [2015]. Those error bounds are then equivalent to quadratic growth conditions, i.e. (Loja) with r = 2 [START_REF] Drusvyatskiy | Error bounds, quadratic growth, and linear convergence of proximal methods[END_REF]. Previous works demonstrate then linear convergence of proximal gradient descent [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF]. Here the restart schemes allow to get accelerated rates similar as for smooth strongly convex problems. Note that adaptive schemes were also developed by [START_REF] Fercoq | Adaptive restart of accelerated gradient methods under local quadratic growth condition[END_REF] in that case. 5.2. Smoothing non-smooth problems. Our approach extends also to problems that can be smoothed, i.e. problems of the form minimize f (x) φ(Ax) + g(x) (29) where A ∈ R m×n , g is a simple convex function and φ is a non-smooth convex function whose infconvolution with some smooth convex function ψ can be computed analytically, i.e. one has access for any µ > 0 to

φ µψ ⋆ (x) = sup u∈dom φ ⋆ u ⊤ x -φ ⋆ (u) -µψ ⋆ (u) , (30)
where for a function f we denote by f ⋆ its convex conjugate. Those problems were notably considered by [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF], who proved that, though they a priori suffer from their non-smoothness, they can still be solved in O(ε) calls to an oracle by using their structure. Formally, we have access to an algorithm S that, given an initial point x 0 and a target accuracy ε, outputs after t iterations a point

x = S(x 0 , ǫ, t) such that f (x) -f * ≤ ǫ 2 + cL 2 ψ ⋆ ,A D h (x, X * ) ǫ 2 t 2 ǫ 2 , and f (x) ≤ f (x 0 ), (31)
where h is some potential function and L ψ ⋆ ,A is a smoothing constant, see Appendix A for more details. The scheduled restarts of this algorithm will follow the same strategy as for the fast universal gradient method as presented in the following proposition.

Proposition 5.5. Let f (x) = φ(Ax) + g(x) be a non-smooth objective that can be smoothed using (30), x 0 ∈ dom f and K = {x : f (x) ≤ f (x 0 )}. Assume that we have access to a smoothing method S ensuring (31) for a given strongly convex function h and that f ∈ L r,µ,h (K). Given ǫ 0 ≥ f (x 0 ) -f * , restart the method S such that for k ≥ 1,

x k = S(x k-1 , ǫ k , t k ), ǫ k = e -1 ǫ k-1 , t k = C * κ,τ e τ k , C * κ,τ e 1-τ (cκ)
1 2 ǫ -τ 0 , where κ and τ are defined as in (2) with s = 1 and L ψ * ,A in place of L.

The precision reached at a point x = x R after R restarts is given by,

f (x) -f * ≤ exp -e -1 (cκ) -1 2 N ǫ 0 = O exp(-κ -1 2 N ) , when τ = 0, while, f (x) -f * ≤ ǫ 0 τ e -1 (cκ) -1 2 ǫ τ 0 N + 1 1 τ = O N -1 τ , when τ > 0,
where N = R k=1 t k is total number of iterations.

Proof. The smoothing method has a bound of the same form as the universal fast gradient method, i.e. we have

x = S(x 0 , ǫ, t) such that f (x) -f * ≤ ǫ 2 + cL 2 s D h (x 0 , X * ) 2 ǫ 2 s t 2ρ s ǫ 2 ,
with here L = L ψ ⋆ ,A , s = 1 and ρ = 1. The optimal restart schedule and corresponding rates follow then from Proposition 3.1 by replacing s = 1 and ρ = 1.

As for the universal fast gradient method, a grid-search will not get optimal rates if r and so τ is unknown. However if it is known, a grid-search will ensure optimal rates up to a constant factor. It is illustrated for sparse recovery problems by Roulet et al. [2019].

If f * is known, Proposition 4.1 is modified into the following proposition. Note that the resulting restart scheme is the one presented by [START_REF] Gilpin | First-order algorithm with O(log 1/ǫ) convergence for ǫequilibrium in two-person zero-sum games[END_REF] for zero-sum matrix games.

Proposition 5.6. Let f (x) = φ(Ax) + g(x) be a non-smooth objective that can be smoothed using (30), x 0 ∈ dom f and K = {x : f (x) ≤ f (x 0 )}. Assume that f * is known, that we have access to a smoothing method S ensuring (31) for a given strongly convex function h and that f ∈ L r,µ,h (K). Denoting ǫ 0 = f (x 0 ) -f * , consider the restart scheme defined by

x k = S(x k-1 , ǫ k , t k ) s.t. ǫ k = e -1 ǫ 0 t k = argmin{t : x = S(x k-1 , ǫ k , t) satisfies f (x) -f * ≤ ǫ k }.
The precision reached at a point x = x R after R restarts is given by,

f (x) -f * ≤ exp -e -1 (cκ) -1 2 N ǫ 0 = O exp(-κ -1 2 N ) , when τ = 0, while, f (x) -f * ≤ ǫ 0 τ e -1 (cκ) -1 2 ǫ τ 0 N + 1 1 τ = O N -1 τ , when τ > 0,
where N = R k=1 t k is total number of iterations and κ and τ are defined as in (2) with s = 1 and L ψ * ,A in place of L.

Proof. As in Proposition 4.1, the proposed scheme with a termination criterion on the gap cannot do worse than the optimal scheduled restart. The rate is then given by Proposition 5.5.

NUMERICAL RESULTS

We illustrate our results by testing our adaptive restart schemes, the adaptive scheme Adap of Section 2.2, and the scheme with stopping criterion on the primal gap Crit in Section 4, on several problems to compare them against simple gradient descent (Grad), accelerated gradient methods (Acc), and the restart heuristic enforcing monotonicity (Mono) proposed by [START_REF] O'donoghue | Adaptive restart for accelerated gradient schemes[END_REF]. For Adap we plot the convergence of the best method found by grid search to compare with the restart heuristic. This implicitly assumes that the grid search is run in parallel with enough servers. For Crit we use the optimal f * found by another solver. This gives an overview of its performance when such information is available. All restart schemes were performed using the accelerated gradient with backtracking line search detailed in Appendix A, with large dots representing restart iterations.

In Figure 1, we solve classification problems with various losses on the UCI Sonar data set [START_REF] Newman | UCI machine learning repository[END_REF]. For the least square loss on sonar data set, we observe much faster convergence of the restart schemes compared to the accelerated method. These results were already observed by O'Donoghue and Candes [2015]. For the logistic loss, we observe that restart does not provide much improvement for a budget of 1000 iterations. For the hinge loss, we regularized by a squared norm and optimize the dual, which means solving a quadratic problem with box constraints. We observe here that the scheduled restart scheme converges much faster, while restart heuristics may be activated too late. We observe similar results for the LASSO problem. This highlights the benefits of a sharpness assumption for these last two problems.

In general Crit ensures the theoretical accelerated rate but Adap exhibits more consistent behavior. Again, precisely quantifying sharpness from data/problem structure is a key open problem.

To account for the grid search effort, in Figure 6, we multiplied the number of iterations made by the Adap method by the size of the grid. This is for the LASSO problem on Sonar data set with a grid step size of 4. This shows that the benefits of the restart schemes make the grid search effort acceptable both on paper and in practice. More clever grid search strategies for scheduled restarts run in parallel would even reduce this effort. A.2. Universal fast gradient method. Our simplified version of the Universal Fast Gradient method is presented in Algorithm 4. Proposition A.1 shows the convergence of Algorithm 4. Proposition A.2 ensures that the line-searches terminate. The total number of oracle calls can be bounded as done by [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF], using a termination criterion, we only give the complexity in terms of iterations of the algorithm. Monotonicity is enforced by simply taking the best of the new and old iterate at each iteration.

Proposition A.1. Consider problem (32) where φ satisfies (33) with parameters (s, L). Algorithm 4, started at an initial point x 0 for a target accuracy ǫ and an initial estimate L 0 , outputs after t iterations a point x t such that

f (x t ) -f * ≤ ǫ 2 + 2 5s-2 s L 2 s D h (x 0 , X * ) ǫ 2 s t 2ρ s ǫ 2 and f (x t ) ≤ f (x 0 ), where D h (x, X * ) = min x * ∈X * D h (x * ; x) with X * = argmin x f (x).
Proof. Monotonicity of the objective values is ensured by ( 43). We fix in the following x ∈ dom f . Consider the k th iteration of Algorithm 4 for k ≥ 1. We have

f (x k ) (43) ≤ f (x k ) (42) ≤ ℓ f (x k ; y k-1 ) + L k 2 xk -y k-1 2 + ǫθ k 2 (i) ≤ (1 -θ k )ℓ f (x k-1 ; y k-1 ) + θ k ℓ f (z k ; y k-1 ) + L k θ 2 k 2 z k -z k-1 2 + ǫθ k 2 (34) ≤ (1 -θ k )ℓ f (x k-1 ; y k-1 ) + θ k (ℓ f (z k ; y k-1 ) + L k θ k D h (z k ; z k-1 )) + ǫθ k 2 (45) ≤ (1 -θ k )ℓ f (x k-1 ; y k-1 )+θ k (ℓ f (x; y k-1 )+L k θ k [D h (x; z k-1 ) -D h (x; z k )]) + ǫθ k 2 (36) ≤ (1 -θ k )f (x k-1 ) + θ k f (x) + L k θ 2 k [D h (x; z k-1 ) -D h (x; z k )] + ǫθ k 2 where in (i) we used that xk = (1 -θ k )x k-1 + θ k z k , the convexity of ℓ f (•; y k-1 ) and xk -y k-1 = θ k (z k -z k-1 ). Subtracting f (x) on both sides and dividing by L k θ 2 k , we get 1 L k θ 2 k (f (x k ) -f (x)) ≤ 1 -θ k L k θ 2 k (f (x k-1 ) -f (x)) + D h (x; z k-1 ) -D h (x; z k ) + ǫ 2L k θ k If k = 1, we have, using the initialization θ 1 = 1, z 0 = x 0 , 1 L 1 θ 2 1 (f (x 1 ) -f (x)) ≤ D h (x; x 0 ) -D h (x; z 1 ) + ǫ 2L 1 θ 1 (37)
Otherwise we have using the definition of θ k in (41),

1 L k θ 2 k (f (x k ) -f (x)) ≤ 1 L k-1 θ 2 k-1 (f (x k-1 ) -f (x)) + D h (x; z k-1 ) -D h (x; z k ) + ǫ 2L k θ k (38)
Using inequality (38) recursively from k to 2 and inequality (37) for k = 1 we get

1 L k θ 2 k (f (x k ) -f (x)) ≤ D h (x; x 0 ) -D h (x; z k+1 ) + k j=1 ǫ 2L j θ j (47) = D h (x; x 0 ) -D h (x; z k+1 ) + ǫ 2L k θ 2 k Finally a bound on L k θ 2
k can be found by combining Proposition A.2 and Proposition A.1 such that L k θ 2 k ≤ Algorithm 4 Simplified Universal Fast Gradient Method x = U (x 0 , t, ǫ)

1: Problem oracles: Convex functions φ, g, first-order oracles (x, y, λ) → argmin z y T z + g(z) + λD h (z; x) and x → ∇φ(x) with ∇φ(x) ∈ ∂φ(x) 2: Inputs: Initial point x 0 , number of iterations t, target accuracy ǫ, smoothness estimate L 0 3: Initialize: z 0 = x 0 , θ 1 = 1 4: for k = 1, . . . , t do

7: if k > 1 then 8: Compute θ k ≥ 0 s.t. 1 -θ k Lk θ 2 k = 1 L k-1 θ 2 k-1 (41) 9: end if 10: Compute y k-1 = (1 -θ k )x k-1 + θ k z k-1 z k = argmin z ℓ f (z; y k-1 ) + Lk θ k D h (z; z k-1 ) xk = (1 -θ k )x k-1 + θ k z k 11: if f (x k ) > ℓ f (x k ; y k-1 ) + Lk 2 xk -y k-1 2 + θ k ǫ 2 then Lk ← 2 Lk end if 12: until f (x k ) ≤ ℓ f (x k ; y k-1 ) + Lk 2 xk -y k-1 2 + θ k ǫ 2 (42) 13:
Pick any

x k such that f (x k ) ≤ min(f (x k ), f (x k-1 )) (43) 14:
Update L k = Lk 15: end for 16: Output: x t Proposition A.2. Consider problem (32) where φ satisfies (33) with parameters (s, L). The line-searches of Algorithm 4 terminate with

L k ≤ 2ǫ s-2 s L 2 s θ s-2 s k Proof. Lemma A.4 ensures that the line-search for x 1 stops for L1 ≥ ǫ s-2 s L 2 s . Therefore we have L 1 ≤ 2ǫ s-2 s L 2 s . For k ≥ 2, during the line-search procedure, the parameter θ k reads, denoting a = θ 2 k-1 L k-1 / Lk , θ k ( Lk ) = -a+ √ a 2 +4a 2 = 2 1+ √ 1+4/a = 2 1+ 1+4 Lk /(θ 2 k-1 L k-1 )
. Using again Lemma A.4, the stopping criterion ( 42) is then ensured if there exists Lk such that A.3. Accelerated algorithm. The accelerated algorithm is obtained as a special case of the universal fast gradient algorithm for s = 2 and a choice of ǫ = 0, i.e., A(x 0 , t) = U (x 0 , t, 0). Its rate follows from the one given by the universal fast gradient method as recalled below.

Corollary A.3. Consider problem (32) where φ satisfies (33) with parameters (2, L). Algorithm 4 with ǫ = 0, started at an initial point x 0 with an initial estimate L 0 , outputs after t iterations a point x t such that f (x t ) -f * ≤ 8L t 2 D h (x 0 , X * ) and f (x t ) ≤ f (x 0 ), where D h (x, X * ) = min x * ∈X * D h (x * ; x) with X * = argmin x f (x).

A.4. Lemmas for proving convergence.

≥ 2, 1 -θ k L k θ 2 k = 1 L k-1 θ 2 k-1 , (46)
for some α ≥ 0, β ∈ [0, 1], with θ k ≥ 0. Then for any k ≥ 1,

1 L k θ 2 k = k j=1 1 L j θ j and L k θ 2 k ≤ α2 2-β k 2-β (47)
Proof. The first property of ( 47) is true for k = 1 since θ 1 = 1. The definition of θ k for k ≥ 2 reads then

1 L k θ 2 k = 1 L k-1 θ 2 k-1 + 1 L k θ k
A γ k -A γ k-1 ≥ A k -A k-1 A 1-γ k + A 1-γ k-1 ≥ A k -A k-1 2A 1-γ k ≥ 1 2α 1 2-β . Therefore we conclude that A k ≥ k 1 γ 2 1 γ α = k 2-β 2 2-β α .
A.5. Smoothing non-smooth problems. We present here the smoothing algorithm used in Section 5. We recall the problem minimize f (x) φ(Ax) + g(x) (48) where A ∈ R m×n , g is a simple convex function and φ is a non-smooth convex function whose infconvolution with some smooth convex function ψ can be computed analytically, i.e. one has access for any µ > 0 to . Injecting it in (51) at the R th point the result follows.

φ µψ ⋆ (x) = inf

APPENDIX C. GRID-SEARCH FOR UNIVERSAL RESTART SCHEMES

We briefly explain why a grid-search on the parameters for the general case s ∈ [1, 2] does not provide near-optimal bounds. Consider general restart schemes as presented in Algorithm 2 for a function f ∈ H s,L ∩ L r,µ (K) with K the initial sublevel set of f at a given x 0 . Assume that the decreasing factor is γ and the schedules have the form t k = Ce αk such that t k ≥ e and α ≥ γτ ρ . Consider the case τ > 0. Then following the proof of Proposition 3.1, we get that f (x R ) -f * ≤ γ k ǫ 0 and applying Lemma 2.1 we obtain a convergence rate

f (x R ) -f * ≤ ǫ 0 (αe -α C -1 N + 1) γ α
,

where N is the total number of iterations. For this rate to be optimal or nearly optimal we need γ α = ρ τ . Any grid search on this ratio will then suffer from a constant factor such that we won't get a rate of the form N -ρ τ except if we know r and s which gives us ρ/τ .

  FIGURE 1. Sonar data set. From left to right: least square loss, logistic loss, dual SVM problem and LASSO. We use adaptive restarts (Adap), gradient descent (Grad), accelerated gradient (Acc) and restart heuristic enforcing monotonicity (Mono). Large dots represent the restart iterations. Regularization parameters for dual SVM and LASSO were set to one.

  FIGURE 2. Comparison of the methods for the LASSO problem on Sonar dataset where number of iterations of the Adaptive method is multiplied by the size of the grid. Grid search step size is set to 4.

  repeat

s

  c : x → x -α(1 + √ 1 + βx) γ for α > 0, β > 0, 0 ≤ γ ≤ 1. We have lim x→+∞ c(x) = +∞.Therefore there exists Lk > 0 satisfying (40). Moreover the line-search terminates withL k ≤ 2 (θ k ǫ) otherwise, L k /2 > (θ k (L k )ǫ) s-2 s L 2 s ≥ (θ k (L k /2)ǫ) , and the line-search would have stopped before.

  Lemma A.4 ([Nesterov, 2015, Lemma 2]). Let φ satisfying (33). Then for any δ > 0 and L ≥ 2have, for any x, y ∈ dom φ and ∇φ(x) ∈ ∂φ(x), φ(y) ≤ φ(x) + ∇φ(x) ⊤ (y -x) 5 ([Tseng, 2008, Property 1]). For any proper l.s.c. convex function ψ, and any z ∈ dom h, denote z + = argmin x {ψ(x) + D h (x; z)}. Then for any x ∈ dom h,ψ(x) + D h (x; z) ≥ ψ(z + ) + D h (z + ; z) + D h (x; z + ). (45)Lemma A.6. Consider two sequences (L k ) k≥1 , (θ k ) k≥1 initialized by L 1 > 0, θ 1 = 1 and satisfying for k

  which shows the first property (47) by induction.For k ≥ 1, denote a k = 1 L k θ k and A k = k j=1 a j , such that A k = 1 L k θ 2 k = L k a 2 k .We have from (46), a k . Denote γ = 1 2-β and A 0 = 0. Since γ ≥ 1/2 and A k ≥ A k-1 , we have for any k ≥ 1,

.

  y φ(y) + µψ x -y µ = sup u u ⊤ x -φ ⋆ (u) -µψ ⋆ (u) , Now, if t k = ⌈Ce αk ⌉, define ǫ k = ⌈Ce αk ⌉-Ce αk , such that 0 ≤ ǫ k < 1. On one hand N ≥ R k=1 Ce αk , such that R ≤ log((e α -1)e -α C -1 N +1)α On the other hand, -1) + log (e α -1)e -α C -1 N + 1 α , such that R ≥ log(αe -α C -1 N ′ +1) α

A subset of these results appeared at the NIPS

conference under the same title. 1

ACKNOWLEDGMENTS

AA is at CNRS, attached to the Département d'Informatique at École Normale Supérieure in Paris, INRIA-Sierra team, PSL Research University. VR is in the Statistics Department of the University of Washington, working for the Algorithmic Foundations of Data Science Institute. The authors would like to acknowledge support from the fonds AXA pour la recherche, a gift from Société Générale Cross Asset Quantitative Research, an AMX fellowship and a Google focused award.

Roulet, V., Boumal, N. and dAspremont, A. [2019], 'Computational complexity versus statistical performance on sparse recovery problems', Information and Inference: A Journal of the IMA . Su, W., Boyd, S. and Candes, E. [2014], A differential equation for modeling nesterov's accelerated gradient method: Theory and insights, in 'Advances in Neural Information Processing Systems ', pp. 2510', pp. -2518', pp. . Tseng, P. [2008]], On accelerated proximal gradient methods for convex-concave optimization, Technical report, University of Washington. Zhou, Z., Zhang, Q. and So, A. M.-C. [2015], ℓ 1,p -norm regularization: error bounds and convergence rate analysis of first-order methods, in 'Proceedings of the 32nd International Conference on International Conference on Machine Learning', Vol. 37, pp. 1501-1510.

APPENDIX A. ALGORITHMS & COMPLEXITY BOUNDS

We present here the algorithms that we restart. In particular we present a simplified version of the universal fast-gradient method of [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF] and shows how we can enforce monotonicity of the objective values, while keeping the optimal rate. The classical accelerated algorithm for smooth convex function is then derived as a special case of the universal method.

In both cases the smoothness constant do not need to be known in advance. A line-search is provided whose complexity can be bounded as done in [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF]. In practice when restarting the algorithm we use the last smoothness constant provided by the algorithm.

A.1. Problem formulation. We focus on composite optimization problems of the form

where φ, g are proper lower semi-continuous convex functions on R n and φ is defined on an open-set containing dom g, i.e. dom f = dom g. We denote • a given norm on R n and • * the dual norm of • .

We assume that φ is s-smooth with respect to • for a given s ∈ [1, 2], i.e. that there exists L > 0 such that ∇φ(x) -∇φ(y) * ≤ L x -y s-1 (33) for all x, y ∈ dom f and any ∇φ(x) ∈ ∂φ(x), ∇φ(y) ∈ ∂φ(y). We assume that we have access to a function h, differentiable on its domain dom h ⊇ dom f , strongly convex with respect to the norm • with convexity parameter equal to one, i.e.

x -y 2 , for any x, y ∈ dom h.

We define the Bregman divergence associated to h as, for given x, y ∈ dom h,

Finally we assume that, for any x, y ∈ dom f and λ ≥ 0 we can solve

either in a closed form or by some cheap computational procedure. In the following, we denote for any x, y ∈ dom f ,

where ∇φ(y) ∈ ∂φ(y) is any sub-gradient of φ at y. This partial linearization of the objective is convex and satisfies by convexity of φ,

where for a function f we denote by f ⋆ its convex conjugate, see [START_REF] Beck | Smoothing and first order methods: A unified framework[END_REF]

The smoothed objective is a composite objective as in (32), i.e.,

where, denoting [Pillutla et al., 2018, Lemma 42]). We can then apply the accelerated algorithm on (50) with a potential function h strongly convex w.r.t. the norm • α , assuming that g is simple such that we have access to oracles of the form (25). Precisely, given an initial point x 0 and a target accuracy ǫ, by applying the accelerated algorithm on (50) with µ = ǫ/(2D), where D = sup u∈dom φ * ψ * (u)inf u∈dom φ * ψ * (u), we get after t iterations a point x such that for x * ∈ argmin f ,

where in (i) we use the definition of µ and the convergence bound (39) of the accelerated algorithm (ǫ = 0) applied on x = x * . We denote then x = S(x 0 , ǫ, t) any point such that f (x) ≤ min{f (x), f (x 0 )} such that it satisfies both the rate above and belongs to the initial sub-level set. The bound presented in equation ( 31) is obtained by taking x * ∈ argmin x∈X * D h (x; x 0 ) and defining c = 32 and L ψ * ,A = √ D A α,β .

APPENDIX B. ROUNDING ISSUES

We presented convergence bounds for real sequences of iterate counts (t k ) ∞ k=1 but in practice these are integer sequences. The following Lemma details the convergence of our schemes for an approximate choice tk = ⌈t k ⌉.

Lemma B.1. Let x k be a sequence whose k th iterate is generated from previous one by an algorithm that needs t k iterations and denote N = R k=1 t k the total number of iterations to output a point x = x R . Suppose setting t k = ⌈Ce αk ⌉, k = 1, . . . , R for some C > 0 and α ≥ 0 ensures that objective values f (x k ) converge linearly, i.e.

for all k ≥ 0 with ν ≥ 0 and γ ≥ 0. Then precision at the output is given by, f , when α > 0.

Proof. At the R th point generated, N = R k=1 t k . If t k = ⌈C⌉, define ǫ = ⌈C⌉ -C such that 0 ≤ ǫ < 1. Then N = R(C + ǫ), injecting it in (51) at the R th point,