Evgenii Chzhen
email: evgenii.chzhen@universite-paris-saclay.fr

Christophe Giraud
email: christophe.giraud@universite-paris-saclay.fr

Gilles Stoltz
email: gilles.stoltz@universite-paris-saclay.fr

Parameter-free projected gradient descent

We consider the problem of minimizing a convex function over a closed convex set, with Projected Gradient Descent (PGD). We propose a fully parameter-free version of AdaGrad, which is adaptive to the distance between the initialization and the optimum, and to the sum of the square norm of the subgradients. Our algorithm is able to handle projection steps, does not involve restarts, reweighing along the trajectory or additional gradient evaluations compared to the classical PGD. It also fulfills optimal rates of convergence for cumulative regret up to logarithmic factors. We provide an extension of our approach to stochastic optimization and conduct numerical experiments supporting the developed theory.

Introduction

In this work we study the problem of minimizing a convex function f over a closed, possibly unbounded, convex set Θ ⊆ R d . Our main goal is to provide a variant of AdaGrad [START_REF] Streeter | Less regret via online conditioning[END_REF][START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF] which is adaptive to the distance x 1x * between the initialization x 1 ∈ Θ and a minimizer x * ∈ Θ, which is assumed to exist. More precisely, we provide a Projected Gradient Descent (PGD) algorithm of the form

x t+1 = Proj Θ (x t -η t g t ) with η t = 2 kt H s t g s 2 ,
where g t ∈ ∂f (x t ) is a sub-gradient of f at x t , Proj Θ (•) is the Euclidean projection operator onto closed convex Θ, H(x) = (x + 1) log(e(1 + x)) and k t is an automatically tuned sequence by Algorithm 1. Unlike recent works on the subject [START_REF] Defazio | Learning-rate-free learning by D-adaptation[END_REF][START_REF] Carmon | Making sgd parameter-free[END_REF], we provide bounds on the cumulative regret of the form

R T := T t=1 f (x t ) -f (x * ) ,
where x * is any minimizer of f over Θ. Using standard online-to-batch conversion, we also have by convexity f (x T )f (x * ) R T /T , for xT being the average of x 1 , . . . , x T .

In the classical case where f is assume to be L-Lipschitz, it is well known that setting

η t = x1-x * L √ T
gives the optimal rate of convergence [N + 18]:

R T x 1 -x * L √ T .
However, such a choice requires f to be Lipschitz, and the knowledge of three quantities: 1) distance to the optimum x 1 -x * ; 2) Lipschitz constant L; 3) optimization horizon T . Should the distance x 1x * be known, one could set η t = x1-x * √ t s=1 gs 2 , resulting in ADAGRAD algorithm [START_REF] Streeter | Less regret via online conditioning[END_REF][START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF].

Preprint. Under review.

Algorithm 1: FREE ADAGRAD For this choice of η t , without Lipschitz assumption, we have the upper bound on the regret

Input: x 1 ∈ R d , Θ ⊂ R d , γ 0 > 0 Initialization: Γ 2 1 = 0, k 0 = 1, S 0 = 0, γ k = γ 0 2 k for k 1 for t
R T c x 1 -x * T t=1 g t 2 .
(1)

In practice the distance x 1x * is unknown. When an upper bound D * on x 1x * is available, typically the diameter of Θ when Θ is bounded, x 1x * can be replaced by D * in η t . The ADAGRAD algorithm then fulfills (1) with x 1x * replaced by D * . This bound can be very sub-optimal yet, when x 1x * is much smaller than D * . Worse, when Θ is unbounded, no bound D * on x 1x * is available, without additional information.

Our objective is to provide a variant of the ADAGRAD step-size tuning, not requiring f to be Lipschitz, nor any knowledge on x 1x * or T , while still fulfilling the regret bound (1) up to a log factor. Our contribution can be placed alongside the ever expanding literature of parameter-free optimization algorithm [DM23, CH23, Cut19, MS12, MO14a, MK20, OP21, OT17, ZCP22, JC22, OP16], discussed below Theorem 1. Main contributions. Let us describe our three main contributions 1. we propose a simple tuning of PGD, we call FREE ADAGRAD, with no line-search, no cold-restart, no gradient transformation, and no computations of extra gradients; 2. we handle any finite convex function f (no Lipschitz condition), over any possibly unbounded constraint set Θ; 3. we provide regret bounds like R T = O ( x 1x * + 1) 1 + t T g t 2 , where Õ hides log-factor, but no additional terms.

We also partially extend our results to the Stochastic Gradient Descent setting.

Notation. For any a, b ∈ R we denote by a ∨ b (resp. a ∧ b) the largest (resp. the smallest) of the two. We denote by • the Euclidean norm and by •, • the standard inner product in R d . For Θ ⊂ R d , we denote by Proj Θ (•) the Euclidean projection operator onto Θ. We denote by log 2 (•) and log(•) the base 2 and the natural logarithms respectively. The base of the natural logarithm is denoted by e.

Main result

We make the following assumption, which is necessary for the meaningful treatment of the problem. Let us highlight that we do not assume that the subgradients g t are uniformly bounded, that is, we do not require f to be globally Lipschitz. This stays in contrast with the literature on online convex optimization (OCO). Indeed, OCO lower bounds imply that without any prior knowledge a regret O(

x 1 -x * ( t T g t 2 )
1 /2 ) is not achievable [CB17, Cut19, MK20] and higher order terms either in T or in x 1x * are necessary. For example, we are able to handle Θ = [0, +∞) d and f (x) = n i=1 exp( xa i /σ i ) for some a i ∈ R d and σ i > 0. The proposed method, that we call FREE ADAGRAD, is summarized in Algorithm 1. It consists in simple projected gradient steps at every round t 1, but with additional cheap condition on Line 7 that is checked on every iteration. If the condition on this line is satisfied for k = k t-1 , then the algorithm makes (almost) the usual ADAGRAD step, otherwise, the step size is doubled and the condition is checked again. We underline that the sequence of integers {k t : t 1} in Algorithm 1 is non-decreasing, and we prove in Eq. ( 12) that it is upper-bounded by 2(log 2 (1 + x 1x * /γ 0 ) + 1). Thus, there are only a finite number of doublings in the sequence. The only input parameter of the algorithm is γ 0 that can be seen as an initial lower-bound guess for x 1x * and can be taken arbitrary small only incurring additional log(1/γ 0 ) factor. Note that once the step-size is doubled at some time t 1, Algorithm 1 continues the optimization from x t without cold-restart.

Theorem 1. Let Assumption 1 be satisfied. Let S T = T t=1 g t 2 . For any γ 0 > 0, let D γ0 := x 1 -x * ∨ γ 0 , Algorithm 1 satisfies for some universal c > 0 R T cD γ0 (S T +1 + 1) log(1 + S T +1 ) log(1 + D γ0 ) log log(1 + S T ) .
A large part of the literature on parameter-free optimization considers the context of online convex optimization with L-Lipschitz functions. A series of papers [MO14a, ZCP22, JC22, CO18] have produced algorithms, mainly based on coin betting, enjoying regret bounds O(D γ0 S T log(1 + D γ0 S T /γ 0 )), up to lower order terms. Such a regret bound is not achievable in online convex optimization when L is unknown as shown in [START_REF] Cutkosky | Online learning without prior information[END_REF]. Some papers [Cut19, MK20, JC22] consider yet the case where L is unknown, and provide regret bound including additional terms depending on L and on higher order of D γ0 .

If only the optimization error is of concern (and not the regret), bounds with log-factors replaced by log-log factors have been produced by [START_REF] Carmon | Making sgd parameter-free[END_REF][START_REF] Defazio | Learning-rate-free learning by D-adaptation[END_REF], breaking the barrier of online-to-batch conversion, but still requiring some knowledge about the Lipschitz constant L. Relying on binary search, [START_REF] Carmon | Making sgd parameter-free[END_REF] construct an adaptive algorithm for the problem of stochastic optimization, while [START_REF] Defazio | Learning-rate-free learning by D-adaptation[END_REF] provide an adaptive version of dual averaging and gradient descent algorithms, without allowing for projection step and requiring a careful weighted averaging along the trajectory to obtain the final solution. In contrast, we do not require Lipschitz condition, we handle the projection step and our bounds are valid for the usual average.

The closer to us, in a setting of online convex optimization with L-Lipschitz functions, [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF] propose a tuning of GD (without projection) which is based on a doubling trick with cold-restarts and which requires the knowledge of L. This algorithm is shown to be adaptive to x 1x * at the price of loosing a log factor log(D γ0 T /γ 0 ) in the regret bound. In Appendix D, we show that the algorithm of [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF] can be seen as a specific instantiation of Algorithm 1, with the major difference that cold-restart are performed when doubling the step-size.

Warm-up: simple analysis and intuition

Before proceeding to the analysis of the FREE ADAGRAD algorithm 1, we explain the main ideas behind our step-size scheme in the following simpler setup.

Simple warm-up setup 1) the norm of the subgradients are uniformly bounded by some known L, i.e. g t L,

2) the optimization is unconstrained, i.e. Θ = R d , 3) the time horizon T is fixed in advance.

In this case, we can replace (h t ) t 1 set on Line 4 of Algorithm 1 by the constant sequence h t = L √ T , and the choice γ = x 1x * is known to achieve the optimal rates for the regret x 1x * L √ T , see e.g. [N + 18]. In this context, the overall strategy of Algorithm 1 is to start from a small value

x T 1 = x 1 x T 2 x T 3 x T k T -1 x T k T x T k T +1 = x T η t = 2γ 0 L √ T η t = 4γ 0 L √ T . . . η t = 2 k T γ 0 L √ T η t = 2 k T -1 γ 0 L √ T η t = 2 k T -1 γ 0 L √ T x + T3-1 (2) -x * > BT 3 (2) x + Tk T -1 (kT -1) -x * > BT k T (kT -1)
Figure 1: Schematic illustration of the algorithm in the simplest case.

γ 0 for γ, and then track x tx 1 in order to detect if γ < x 1x * . If so, γ is doubled. The algorithm then increases the value γ until reaching the level x tx 1 .

In order to keep the analysis simple in this warm-up section, we replace the threshold B t+1 (k) Line 5 of Algorithm 1 by

B simple t+1 (k) = 3γ k (recall that γ k = γ 0 2 k )
, what eventually leads to a slightly worse bound. The gradient step and the step-size choice are then simply

x + t (k) = x t - γ k L √ T g t and k t = min k k t-1 : x + t (k) -x 1 3γ k . (2)
Below, we sketch the main arguments, and we refer to Appendix A for all the details. The first ingredient is the text-book decomposition using subgradient upper-bound: for any k 1

0 f (x t ) -f (x * ) g t , x t -x * = γ k 2L √ T g t 2 + L √ T 2γ k x * -x t 2 -x + t (k) -x * 2 γ k L 2 √ T + L √ T 2γ k x * -x t 2 -x + t (k) -x * 2 . (3)
It follows from this bound, a one-step deviation upper-bound

x + t (k) -x * 2 x t -x * 2 + γ 2 k /T .
Summing this bound over t, we get a first important bound on the distance to optimum

x + t (k) -x * 2 x 1 -x * 2 + t-1 s=1 γ 2 ks T + γ 2 k T x 1 -x * 2 + γ 2 k , for all k k t-1 , (4)
and then another important bound on the distance to initialization

x + t (k) -x 1 x 1 -x * + x + t (k) -x * 2 x 1 -x * + γ k , for all k k t-1 , (5)
where the last inequality follows from (4) and the sub-additivity of square-root.

Controlling the number of phases. The bound (5) plays a central role in our step-size tuning. Indeed, we observe that if x + t (k t-1 )x 1 > 3γ kt-1 , then it means that γ kt-1 < x 1x * , and our step-size tuning then increases k until the condition x + t (k)x 1 3γ k is met. In addition, we check below that the design of B simple t+1 (k) ensures that we have k t k * for all t T , where k * 1 is the integer defined by γ k * -1 D γ0 := x *x 1 ∨ γ 0 < γ k * , and fulfilling

k * 1 + log 2 x * -x 1 γ 0 ∨ 1 = log 2 2D γ0 γ 0 , and
γ k * 2D γ0 . (6)
Indeed, if k t-1 k * , then (5) ensures that

x + t (k * ) -x 1 2γ k * + γ k * = B simple t+1 (k * ) , so k t k * ,
R T = k T k=1 T k+1 -1 t=T k (f (x t ) -f (x * )) k * k=1 γ k L 2 √ T (T k+1 -T k ) + L √ T 2γ k x T k -x * 2 -x T k+1 -x * 2 L √ T 2 γ k * + k * k=1 1 γ k x T k -x * 2 -x T k+1 -x * 2 . ( 7
)
From the step-size rule, we have that x T k+1x 1 B T k+1 (k T k+1 -1 ) = 3γ k , and from (4) we have

x T k -x * 2 x 1 -x * 2 + γ 2 k-1
, so we can upper bound the last term in the right-hand side of (7)

x T k -x * 2 -x T k+1 -x * 2 x 1 -x * 2 + γ 2 k-1 -x 1 -x * -x T k+1 -x 1 2 + γ 2 k-1 + x 1 -x * 2 -[ x 1 -x * -3γ k ] 2 + 1 4 γ 2 k + 6γ k x 1 -x * , (8)
where the last inequality follows from the basic inequality

∆ 2 -[∆ -B] 2 +
2∆B, for all ∆, B 0. Substituting (8) in (7) and using the bound (6), we end with the upper-bound

R T L √ T 2 γ k * + γ k * +1 4 + 6k * x 1 -x * L √ T 3 x 1 -x * log 2 2D γ0 γ 0 +2D γ0 . (9)
The bound (9) for Algorithm 1, then matches the optimal rate x 1x * L √ T obtained with the oracle step size η = x 1x * /(L √ T ), up to a factor log 2 (D γ0 /γ 0 ).

It turns out that, in this L-Lipschitz setting, it is possible to adapt to x 1x * with a bound O D γ0 L T log 2 (D γ0 /γ 0 ) on the regret, by, for example, using coin betting [START_REF] Mcmahan | Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations[END_REF][START_REF] Orabona | Coin betting and parameter-free online learning[END_REF].

We achieve such tighter bound with PGD with a better tuning of the threshold B t+1 (k) which is explained in the next section.

3.1 Improving log factor by better tuning of B t+1 (k)

Previous section gave the basic intuition, explaining why such a doubling strategy works. Yet, our choice of B t+1 on Line 5 of Algorithm 1 differs from B simple t+1 (k) = 3γ k . Remaining in the simple setup of warmup, let us explain two key ingredients, which eventually lead to our choice of B t+1 on Line 5 of Algorithm 1. The first ingredient is to track more tightly the upper-bound on x + t (k)x 1 . Indeed, we can improve the Bound (4) by keeping x + t (k)x * 2

x 1 (k)x 1 2 + Γ 2 t + γ 2 k /T instead of relying on the last bound in (4). Hence, we can replace (5) by

x + t (k) -x 1 2 x 1 -x * + Γ 2 t + γ 2 k /T , (10)
in order to implicitly track the value x 1 -x * . This improved tracking alone is not enough in order to improve the log factor. Indeed, choosing

B t+1 (k) = 2γ k + Γ 2 t + γ 2 k /T , still introduces log(D γ0 ) term.
To improve the log factor, our second ingredient is to choose a slightly smaller threshold B t+1 , at the price of possibly moderately increasing the number k T of doubling. In particular, setting

B t+1 (k) = 2γ k √ k + Γ 2 t + γ 2 k /T , (11)
we get that k T k * + 0.5 log 2 (k * ) + 1.25, and instead of log(D γ0 ) we have log(D γ0 ) in the regret bound (see Appendix A for details). Combining everything together, we get the bound

R T 10D γ0 L √ T 2 log 2 (2D γ0 /γ 0 ) ,
for algorithm in (2) with 3γ k replaced by B t+1 (k) in (11) (see Theorem 4 in Appendix A). While, the above discussion was still assuming the simple setup of L-Lipschitz function f , known L and T , we are able to generalize the above argument to nearly arbitrary convex f and unknown T .

4 Meta theorem: a general case of Algorithm 1

In this section, we provide a unified analysis of Algorithm 1, that is valid under the minimal Assumption 1, and for the choice of any positive non-decreasing sequence (h t ) t 1 on Line 4 of Algorithm 1. Our main result, stated in Theorem 1, is obtained as a consequence of this general result, and is made precise in Corollary 1. Theorem 2. Let Assumption 1 be satisfied. For any γ 0 > 0, for any positive non-decreasing (h t ) t 1 on Line 4 of Algorithm 1, Algorithm 1 satisfies

T t=1 (f (x t ) -f (x * )) h T +1   2 x 1 -x * k T   2+ 1 3 T t=1 g t 2 h 2 t   + γ k T T t=1 g t 2 h 2 t   .
It is interesting to observe that the term t T g t 2 /h t , that often appears in the analysis of ADAGRAD is absent in our bound. Instead, we have t T g t 2 /h 2 t which behaves slightly worse and hence requires additional correction of h t (extra log factor) to ensure convergence. The proof of Theorem 2, which can be found in Appendix B, is based on the following general lemma. Lemma 1. Let Assumption 1 be satisfied. Consider the following algorithm for t 1

x t+1 = Proj Θ x t - γ h t g t ,
where g t ∈ ∂f (x t ), (h t ) t 1 is non-decreasing and positive, and x 1 ∈ R d . For all T > 1, and all

x 1 ∈ R d , we have T t=1 (f (x t ) -f (x * )) h T +1 x 1 -x * 2 -x T +1 -x * 2 2γ + γ 2 T t=1 g t 2 h 2 t .
The above lemma replaces the key inequality (3) that was available for one step of PGD in the simplest case. However, since the step-size in our case is time-varying, we rather need a variant of this inequality over the whole trajectory. While simple to prove, it seems that this result is novel and could be of independent interest.

Finally, to obtain the bound of Theorem 1, we only need to bound the number of phases k T . Note that the intuition of the previous section still applies in this case, yet, the actual bound on k T is more refined-it gives better constants and improves logarithmic factors. Lemma 2. Let Assumption 1 be satisfied. For any γ 0 > 0, and any non-decreasing positive (h t ) t 1 , Algorithm 1 satisfies for T 2

k T k * + 1 2 log 2 (k * ) + 5 4 and γ k T 5 2 √ k * γ 0 2 k * .
where

k * is such that γ 0 2 k * -1 x 1 -x * ∨ γ 0 γ 0 2 k * . Furthermore, k T = 1 if k * = 1.
As a direct consequence of the above lemma and recalling that

D γ0 = x 1 -x * ∨ γ 0 , we obtain k T √ 2 log 2 D γ0 γ 0 + 1 and γ k T 5D γ0 log 2 D γ0 γ 0 + 1 , (12)
that is, k t takes at most 2(log 2 (D γ0 /γ 0 ) + 1) values.

Proof of Lemma 2. Lemma 4 in Appendix, applied by phases, implies that for all t 1 and k 1 we have

x + t (k) -x * 2 x 1 -x * 2 + Γ 2 t + γ 2 k g t 2 h 2 t .
Thus, the triangle inequality, yields

x + t (k) -x 1 2 x 1 -x * + Γ 2 t + γ 2 k g t 2 h 2 t 2D γ0 + Γ 2 t + γ 2 k g t 2 h 2 t ,
where

D γ0 = x 1 -x * ∨ γ 0 . Let k be the smallest integer such that 2 k/ √ k 2 k * .
Then, for any k 1 and any t 1

x + t (k) -x 1 2γk √ k + Γ 2 t + γ 2 k g t 2 h 2 t .
In particular, the above implies that x + t ( k)x 1 B t+1 ( k) for all t 1. Thus, once k t reaches k on Line 7 of Algorithm 1, it never changes its value. That is, k T k. Lemma 12 in Appendix shows that k k * + 0.5 log 2 (k * ) + 1.25 and k = 1 if k * = 1, which concludes the proof.

4.1 Applications of Theorem 2: specific choices of (h t ) t 1 Theorem 2 and Lemma 2 yield the main result of this work-theorem announced in Section 2.

Corollary 1. Under assumptions of Theorem 2. Let H(x) = (x + 1) log(e(x + 1)). Setting

h t = H(S t ) and D γ0 = x 1 -x * ∨ γ 0 , Algorithm 1 satisfies T t=1 (f (x t ) -f (x * )) D γ0 H(S T +1 ) log 2 2D γ0 γ 0 6 log(log(e(1 + S T ))) + 6.5 .
While the above choice of (h t ) t 1 gives nearly optimal rates, it is not standard in the literature. Let us highlight the usefulness of Theorem 2 by providing some instantiations which correspond to other, more common, but less optimal, examples.

The standard ADAGRAD corresponds to h t = √ S t [START_REF] Streeter | Less regret via online conditioning[END_REF]. The main inconvenience of this choice, is that the term t T g t 2 /S t is not bounded uniformly by a non-decreasing function of S T . Indeed, assume that g t 2 = 1/T for all t = 1, . . . , T , then S t = t/T 1 and t T g t 2 /S t ≈ log(T ).

It is possible, however, to write t T g t 2 /S t 1 + log(S T / g 1 2 ), which involves additional dependency on the gradient at initialization. All in all, we can state the following corollary. Corollary 2. Under assumptions of Theorem 2. Setting h t = √ S t and

D γ0 = x 1 -x * ∨ γ 0 , Algorithm 1 satisfies T t=1 (f (x t ) -f (x * )) D γ0 S T +1 log 2 2D γ0 γ 0 6 log eS T g 1 2 + 6.5 .
An attractive feature of this bound is its scale-invariance-multiplying f by some constant, multiplies the bound by the same constant.

The dependency on the initial gradient can be avoided setting h t = √ ε + S t with arbitrary ε > 0, as it is usually done in practice with ADAGRAD, and initially proposed in [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF]. Corollary 3. Under assumptions of Theorem 2. Let

h t = √ ε + S t , for some ε > 0. Setting D γ0 = x 1 -x * ∨ γ 0 , Algorithm 1 satisfies T t=1 (f (x t ) -f (x * )) D γ0 (S T +1 + ε) log 2 2D γ0 γ 0 6 log 1 + S T ε + 6.5 .
Note that compared to Corollary 1, the above bound contains an additional log(1 + S T ) multiplicative factor, but it improves upon that of Corollary 2. Finally, we can also recover the results claimed in the end of Section 3, where f is assumed to be L-Lipschitz, see Appendix B.2 for details.

An extension to stochastic optimization

In this section we demonstrate that at least the warm-up analysis provided in Section 3 extends to the setup of stochastic optimization (see Algorithm 2), where the objective function takes the form

f (x) = E[F (x, ξ)] ,
and where we only have access to g t ∈ ∂F (x t , ξ t ), for some i.i.d. (ξ t ) t 1 . As in [START_REF] Carmon | Making sgd parameter-free[END_REF], we make the following standard assumption on the regularity of F (•, ξ).

Algorithm 2: Stochastic case

Input: x 1 ∈ R d , Θ ⊂ R d , γ 0 > 0, L > 0, T, δ > 0 Initialization: Γ 2 1 = 0, k 0 = 1, S 0 = 0, h : R → R, γ k = γ 0 2 k for k 1, T (δ) := 1 ∨ log(log 2 (2T )/δ) for t = 1, . . . , T do g t ∈ ∂F (x t , ξ t ) // get subgradient h t = L T T (δ/(1 + k t-1 ) 2 ) // update ht x + t (k) = Proj Θ x t -γ k ht g t // probing step k t = min k k t-1 : x + t (k) -x 1 38γ k // find the step size x t+1 = x + (k t ) // make the step end Output :Trajectory (x t ) T t=1 Assumption 2. The mapping x → F (x, ξ) is L-Lipschitz almost surely.
In some applications (e.g., linear contextual bandits), L is actually known and the control of regret is necessary. For example, in linear Contextual Bandits with Knapsacks (lin-CBwK), having PGD strategy for unbounded Θ, while still controlling the regret is needed [see e.g., AD16]. Thus, our Algorithm 2, could bring new results in CBwK and related contexts.

We can state the following result concerning Algorithm 2. Theorem 3. Let Assumptions 1 and 2 be satisfied. Define T (δ) = 1 ∨ log(log 2 (2T )/δ) and

D γ0 = x 1 -x * ∨ γ 0 . For any γ 0 > 0, Algorithm 2 satisfies with probability at least 1 -δ T t=1 (f (x t ) -f (x * )) 3500D γ0 L √ T log 2 2D γ0 γ 0 1 /2 T δ /log 2 2 (4Dγ 0 /γ0) .
The above bound is of order O(LD γ0 √ T log(D γ0 ) log log(T D γ0 )). Note that if only the optimization error is of concern, and one does not wish to control the regret, [START_REF] Carmon | Making sgd parameter-free[END_REF] provide a bound without log 2 (2D γ0 /γ 0 ) using bisection algorithm and several restarted runs of SGD.

Experiments

We have implemented our FREE ADAGRAD (with γ 0 = 1 throughout) algorithm and compared it to the ADAGRAD that requires the knowledge of x 1x * and to the Oracle choice of step x 1x * /(L √ T ). We consider three functions f (x) = x p for p ∈ {1, 2} and f (x) = n -1 i n | a i , x | where a i ∈ R d are generated i.i.d. from standard multivariate Gaussian. The initialization point is picked the same for the three algorithms and is sampled from uniform distribution on [-1, 1] d . For our experiments, we set d = 625 and n = 1000. Note that in the first case, the considered function is Lipschitz with L = 1 and for the second one L

1 n ( a 1 + . . . + a n ). A subgradient at x ∈ R d in the second case is given by n -1 i n a i sign( a i , x
) and since a i 's are i.i.d. Gaussian, it is expected that g 1 n ( a 1 + . . . + a n )-algorithms that are adaptive to the norm of the gradient should perform better in this case. For all three functions, a global minimizer is given by x * = (0, . . . , 0) . All the algorithms run for T = 10000 iterations. All the plots are reported on loglog scale. The first results are reported on Figure 2. The second column displays the step-sizes used by the three algorithms. As a sanity check, we observe that the step size of ADAGRAD decreases over time and the step size of the ORACLE remains constant. One can also observe the characteristic jumps of the proposed FREE ADAGRAD method-the step size decreases withing a fixed phase and is doubled from one phase to the other. On the first row of Figure 2 we display the regret, on initial stages our algorithm behaves similarly to the ORACLE one, while surpassing the performance of the ADAGRAD on the later stages. The third row of Figure 2 displays the case of the averages. Note that in this case the ORACLE algorithm performs worse than the other two, since it takes the worst-case Lipschitz constant and does not adapt to the actual norms of the seen gradients. Step size: ηt

Step sizes: f (x) = x 1, x1x * = 14.36 Step size: ηt

Step sizes: f (x) = x 2, x1x * = 14.36 Step size: ηt

Step sizes:

f (x) = 1 n n i=1 | ai, x |, x1 -x * = 14.38

Discussion

We have introduced FREE ADAGRAD-a simple fully adaptive version of ADAGRAD, that does not rely on any prior information about the objective function. Our bounds are optimal up to logarithmic factors and are applicable to non-globally Lipschitz functions. We have extended our approach to stochastic optimization in a Lipschitz context, at the cost of the knowledge of the Lipschitz constant and sub-optimal logarithmic factors. Numerical illustrations suggest that FREE ADAGRAD performs on par or outperforms ADAGRAD with knowledge of x 1x * and the ORACLE choice of step-size.

Limitations. Let us also list the main limitations and future directions of our work.

1)

We are only dealing with batch optimization. The extension of our analysis to the case of Online Convex Optimization (OCO) seems non-trivial, since the bounds that we obtain are known to be unachievable without prior knowledge in the OCO context [START_REF] Cutkosky | Online learning without prior information[END_REF]. The investigation of FREE ADAGRAD in the OCO setting is left for future work;

2) If f is assumed to be L-Lipschitz with known constant L, slightly better bounds-with improved log-factors-can be obtained in OCO setting [see e.g., OP16, CO18]. It remains an open question wether such bounds, can be obtained in batch optimization in the non-Lipschitz (or unknown L) and unknown x 1x * case;

3) Concerning stochastic optimization, we require f to be L-Lipschitz for some known L. We note, however, that even in the state-of-the-art bound of [START_REF] Carmon | Making sgd parameter-free[END_REF], the knowledge of L is required. A Proofs of the results of the warm-up Section 3

We prove here with full details the results of the warm-up Section 3, in the setting where the norm of the subgradients are bounded by a known constant L, and where the time horizon T is known. We set h t = L √ T , and we analyze simultaneously FREE ADAGRAD algorithm 1 with this choice of h, and the simple variant, where we set B simple t+1 (k) = 3γ k for the threshold, as in Section 3. Theorem 4. Assume that f is a convex L-Lipschitz function, such that there exists x * ∈ arg min x∈Θ f (x) bounded. Let γ 0 > 0 and

D γ0 = x 1 -x * ∨ γ 0 . The FREE ADAGRAD algorithm 1 with h t = L √ T and B t+1 (k) = γ k 2 √ k + 1 √ T + Γ t fulfills T t=1 (f (x t ) -f (x * )) 10D γ0 L √ T 2 log 2 2D γ0 γ 0 .
The simple variant with

h t = L √ T and B simple t+1 (k) = 3γ k fulfills T t=1 (f (x t ) -f (x * )) 3 x 1 -x * L √ T log 2 2D γ0 γ 0 + 2D γ0 L √ T .
Proof of Theorem 4.

We start by emphasizing that the algorithm runs without diverging, in the sense that

k t := min k k t-1 such that x + t (k) -x 1 B t+1 (k) (13)
is finite for any t. Indeed, we observe that x + t (k)x 1 grows at most like γ k / √ T when k goes to infinity, while B t+1 (k) grows faster than γ k 2/ √ k + 1/ √ T and B simple t+1 (k) grows like 3γ k . In fact, we will prove below that k t remains upper-bounded by a quantity independent of T .

The starting point of the proof is the classical analysis for a projected gradient step Proj Θ (x tηg t )

f (x t ) -f (x * ) g t , x t -x * = η 2 g t 2 + 1 2η x t -x * 2 -x t -ηg t -x * 2 η 2 L 2 + 1 2η x t -x * 2 -Proj Θ (x t -ηg t ) -x * 2 ,
where the last inequality follows from the fact that x * ∈ Θ. Since x * is a minimizer of f in Θ, the left hand side is non-negative, so the above inequality with η = γ k /(L √ T ) gives that for any k 1

0 f (x t ) -f (x * ) g t , x t -x * γ k L 2 √ T + L √ T 2γ k x * -x t 2 -x + t (k) -x * 2 . ( 14
)
It follows from this bound, a one-step deviation upper-bound

x + t (k) -x * 2 x t -x * 2 + γ 2 k T .
Summing this bound over t, we get a bound on the distance to optimum

x + t (k) -x * 2 x 1 -x * 2 + t-1 s=1 γ 2 ks T + γ 2 k T = x 1 -x * 2 + Γ 2 t + γ 2 k T , (15)
and then a bound on the distance to initialization

x + t (k) -x 1 x 1 -x * + x + t (k) -x * x 1 -x * + x 1 -x * 2 + Γ 2 t + γ 2 k T 2 x 1 -x * + Γ 2 t + γ 2 k T , (16)
where the two inequalities follow from (15) and the sub-additivity of square-root.

Controlling the number k T of phases. The Inequality ( 16) is the key to get an upper-bound on k T = max {k t : 1 t T }. Let us define the integer k * 1 by

γ k * -1 D γ0 := x * -x 1 ∨ γ 0 < γ k * , which fulfills k * 1 + log 2 x * -x 1 γ 0 ∨ 1 = log 2D γ0 γ 0 , and
γ k * 2D γ0 . (17)
To upper bound k T , we rely on the following estimate derived from (16)

x + t (k) -x 1 2γ k * + Γ 2 t + γ 2 k T . (18)
• Simple case: B simple t+1 (k) = 3γ k . A basic induction ensures that k t k * for all t T . Indeed, if the property k t-1 k * holds, then, since Γ 2 t t-1 T γ 2 kt-1 , we have

x + t (k * ) -x 1 2γ k * + γ k * = B simple t+1 (k * ) , which, in turn, ensures that k t k * . So k * is an upper-bound on k T = max {k t : 1 t T } in this case. • FREE ADAGRAD case: B t+1 (k) = 2γk k1/2 + Γ 2 t + γ 2 k T .
Let us define k as the smallest integer fulfilling k-1/2 γk γ k * . Then, from (18), we have

x + t ( k) -x 1 2γk k1/2 + Γ 2 t + γ 2 k T = B t+1 ( k) ,
so, by induction, we get k t k for all t T . In addition, we prove in Lemma 12 page 27 that k k * + 0.5 log 2 (k * ) + 1.25 .

Bounding the regret on phase k t = k. We denote by [T k , T k+1 -1] the interval where k t = k, with the convention T k+1 = T k if we never have k t = k. For t ∈ [T k , T k+1 -1], we have x t+1 = x + t (k). So from (14), we get

T k+1 -1 t=T k (f (x t ) -f (x * )) T k+1 -1 t=T k γ k L 2 √ T + L √ T 2γ k x * -x t 2 -x t+1 -x * 2 = γ k L 2 √ T (T k+1 -T k ) + L √ T 2γ k x T k -x * 2 -x T k+1 -x * 2 , ( 20
)
with the convention that

T k -1
t=T k = 0. We bound the second term in the right-hand side of (20), with (15)

x

T k -x * 2 x 1 -x * 2 + Γ 2 T k -1 + γ k T = x 1 -x * 2 + Γ 2
T k , and for the third term, we combine (13) with a triangular inequality to get

x T k+1 -x * 2 x 1 -x * -x T k+1 -x 1 2 + x 1 -x * -B T k+1 2 + ,
where we used the condensed notation B T k+1 := B T k+1 (k T k+1 -1 ) = B T k+1 (k). Plugging these two upper and lower bounds in (20), and applying the simple inequality

∆ 2 -[∆ -B] 2 + 2∆B, for all ∆, B 0, (21)
we get

T k+1 -1 t=T k (f (x t ) -f (x * )) γ k L 2 √ T (T k+1 -T k ) + L √ T 2γ k x 1 -x * 2 + Γ 2 T k -x 1 -x * -B T k+1 2 + L √ T 2 γ k T k+1 -T k T + Γ 2 T k γ k + 2B T k+1 γ k x 1 -x * , using Γ 2 T k γ 2 k-1 T k /T / γ k-1 γ k /2 for k 1, we get T k+1 -1 t=T k (f (x t ) -f (x * )) L √ T 2 γ k T k+1 -T k T + γ k-1 2 + 2B T k+1 γ k x 1 -x * .
Bounding the total regret. Summing the above inequality over k, we get the upper-bound on the total regret

T t=1 (f (x t ) -f (x * )) L √ T 2 1 k k T γ k T T k+1 -T k T + γ k-1 2 + 2B T k+1 γ k x 1 -x * L √ T 2   3γ k T 2 + 1 k k T 2B T k+1 γ k x 1 -x *   . ( 22
)
We point out that the bound ( 22) is valid for any choice of B t+1 (k). Let us treat apart the two cases.

• Simple case:

B simple t+1 (k) = 3γ k . Using that k T k * in this case, B T k+1 = B T k+1 (k) = 3γ k ,
and recalling the upper bound (17) on k * and γ k * , we get from (22

) T t=1 (f (x t ) -f (x * )) L √ T 2   3 2 γ k * + 1 k k * 6 x 1 -x *   = L √ T 2 3 2 γ k * + 6k * x 1 -x * L √ T 3 x 1 -x * log 2 2D γ0 γ 0 + 2D γ0 .
• FREE ADAGRAD case:

B t+1 (k) = 2γ k k 1/2 + Γ 2 t + γ 2 k T .
We have proved in this case that k T k with k upper bounded by (19). Combining ( 19) and ( 17), the first term in the right-hand side of ( 22) can be readily bounded by

3 4 γk 3 4 γ k * +0.5 log 2 (k * )+1.25 4D γ0 log 2 2D γ0 γ 0 .
The last term in the right-hand side of ( 22), can be bounded as follows. We notice that

Γ 2 T k+1 -1 + γ 2 k T k+1 -1 T = Γ 2 T k+1 , so we have 1 k k B T k+1 γ k = 1 k k 2 √ k + Γ T k+1 γ k 4 k + 1 k k Γ T k+1 γ k .
For the last term, we observe that

1 k k Γ T k+1 γ k = 1 k k γ -1 k j k γ 2 j ∆T j /T 1 k k j k γ -1 k γ j ∆T j /T 1 j k γ j ∆T j /T k:k j γ -1 k = 2 1 j k ∆T j /T 2 k ,
where the last inequality follows from Cauchy Schwarz. Then, plugging these bounds in (22), and using that k = 1 when k * = 1, and k k * + 0.5 log 2 (k * ) + 1.25 2k * , for k * 2 , we get from (17)

T t=1 (f (x t ) -f (x * )) L √ T 3 4 γk + 6 x 1 -x * k 10D γ0 L √ T 2 log 2 2D γ0 γ 0 .
which concludes the proof of Theorem 4.

B Proofs for Section 4

Proof of Theorem 2. First of all, observe that the algorithm in question can be written as

x t+1 = Proj Θ x t - γ kt h t g t ,
where we recall that (h t ) t 1 is assumed to be non-decreasing and positive. As before, we denote by

[T k , T k+1 -1] the interval where k t = k. In particular, T k T +1 -1 = T . On the interval [T k , T k+1 -1],
the algorithm is simply AdaGrad (slightly modified) started from the point x T k and with the final point at x T k+1 . Thus, within each phase, we can apply the analysis of the AdaGrad that we recall and slightly adapt in Appendix B.1, page 18. The proof closely follows that of the warm-up setup: observing that

T t=1 (f (x t ) -f (x * )) = k T k=1 T k+1 -1 t=T k (f (x t ) -f (x * )) ,
1. We start with one phase analysis, using the results of Appendix B.1, page 18, which contains Lemma 1 displayed in the main body;

2. Then, we sum-up the total regret over k T phases, using the previous analysis, and bound the key quantities;

One phase analysis. Fix some k k T and assume that the the kth phase is non-empty, that is, T k+1 > T k . Thus, in view of the above discussion, Lemma 5, page 18, yields

T k+1 -1 t=T k (f (x t ) -f (x * )) h T k+1 x T k -x * 2 -x T k+1 -x * 2 2γ k + γ k 2 T k+1 -1 t=T k g t 2 h 2 t = Γ 2 T k+1 -Γ 2 T k γ 2 k = h T k+1 x T k -x * 2 -x T k+1 -x * 2 2γ k + Γ 2 T k+1 -Γ 2 T k 2γ k . (23)
Note that by design x T k+1x * x 1x * -B T k+1 (k) + . Furthermore, iteratively applying Lemma 4 by phases, we deduce that

x T k -x * 2 x 1 -x * 2 + Γ 2 T k . That is, we have x T k -x * 2 -x T k+1 -x * 2 2γ k x 1 -x * 2 -x 1 -x * -B T k+1 (k) 2 + 2γ k + Γ 2 T k 2γ k . Furthermore, recalling that ∆ 2 -[∆ -B] 2 + 2∆B
, the above can be further bounded as

x T k -x * 2 -x T k+1 -x * 2 2γ k x 1 -x * B T k+1 (k) γ k + Γ 2 T k 2γ k . ( 24
)
Substitution of (24) into (23), yields

T k+1 -1 t=T k (f (x t ) -f (x * )) h T k+1 x 1 -x * B T k+1 (k) γ k + h T k+1 Γ 2 T k+1 2γ k . ( 25
)
Summing up over phases. Summing up all the inequalities (25) for k T phases, we obtain

T t=1 (f (x t ) -f (x * )) x 1 -x * k k T h T k+1 B T k+1 (k) γ k =:I + k k T h T k+1 Γ 2 T k+1 2γ k =:II . ( 26
)
Bounding the sum of h Γ 2γ terms (I). Observe that, by definition of thereof,

Γ 2 T k+1 = j k γ 2 j   Tj+1-1 t=Tj g t 2 h 2 t   . (27)
Hence, using trivial bound h T k+1 h T +1 , we deduce

I = k k T h T k+1 Γ 2 T k+1 2γ k h T +1 2 k k T Γ 2 T k+1 γ k = h T +1 2 k k T j k γ -1 k γ 2 j   Tj+1-1 t=Tj g t 2 h 2 t   = h T +1 2 j k T k j γ -1 k γ 2 j   Tj+1-1 t=Tj g t 2 h 2 t   h T +1 j k T γ j   Tj+1-1 t=Tj g t 2 h 2 t   h T +1 γ k T T t=1 g t 2 h 2 t , (28)
where the penultimate inequality is due to the fact that k j 2 -k 2 -j+1 and the last one holds since γ k γ k T .

Bounding the sum of B terms (II). We observe that by definition of B t (k), we have

B T k+1 (k) = B T k+1 -1+1 (k) = 2γ k √ k + Γ 2 T k+1 .
Hence, the term of interest is bounded as

II = k k T h T k+1 B T k+1 (k) γ k = 2 k k T h T k+1 √ k + k k T h T k+1 γ -1 k Γ T k+1 4h T +1 k T + h T +1 k k T γ -1 k Γ T k+1 .
For the third term, similarly to the previous paragraph, but additionally invoking Jensen's inequality, we can write

k k T γ -1 k Γ T k+1 = k T k k T 1 k T j k γ 2 j γ -2 k   Tj+1-1 t=Tj g t 2 h 2 t   k T j k T k j γ 2 j γ -2 k   Tj+1-1 t=Tj g t 2 h 2 t   2 √ k T √ 3 T t=1 g t 2 h 2 t ,
where in the last inequality we used the fact that b k=a 2 -2k 4 3 2 -2a . Thus, overall, we have

II = k k T h T k+1 B T k+1 (k) γ k 2h T +1 k T   2 + 1 3 T t=1 g t 2 h 2 t   (29)
The end (combining bounds for I and II). Substituting (28) and ( 29) into (26), we deduce that for any non-decreasing

(h t ) t 1 T t=1 (f (x t )-f (x * )) h T +1   2 x 1 -x * k T   2 + 1 3 T t=1 g t 2 h 2 t   + γ k T T t=1 g t 2 h 2 t   .
B.1 Basic analysis for AdaGrad and Proof of Lemma 1

In this section we extend the standard analysis of ADAGRAD for our purposes and prove Lemma 1 restated below. Throughout, we consider the following algorithm for t 1

x t+1 = Proj Θ x t - γ h t g t , (30)
where g t ∈ ∂f (x t ), S t = t s=1 g s 2 and (h t ) t 1 is non-decreasing and positive, and

x 1 ∈ R d .
We start with some elementary results. Lemma 3. For all t 1 and all

x 1 ∈ R 0 2γ h t (f (x t ) -f (x * )) x t -x * 2 -x t+1 -x * 2 + γ 2 h 2 t g t 2 .
Proof. By the property of projection

x t+1 -x * 2 x t -x * 2 - 2γ h t x t -x * , g t + γ 2 h 2 t g t 2 x t -x * 2 - 2γ h t (f (x t ) -f (x * )) + γ 2 h 2 t g t 2 , (31)
where we used the fact that f is convex. The result follows after re-arranging.

Lemma 3 applied iteratively yields the following result. Lemma 4. For all T 1, γ > 0 and all x 1 ∈ R, Algorithm (30) satisfies

Proj Θ x T - γ h T g T -x * 2 x 1 -x * 2 + γ 2 T -1 t=1 g t 2 h 2 t + γ2 g T 2 h 2 T .
Finally, we are in position to prove Lemma 1 brought up in the main body of the paper. Lemma 5 (Restated Lemma 1 from Section 4). For all T > 1 and all x 1 ∈ R d we have

T -1 t=1 (f (x t ) -f (x * )) h T x 1 -x * 2 -x T -x * 2 2γ + γ 2 T -1 t=1 g t 2 h 2 t .
Proof. Using Lemma 3, we deduce that

T -1 t=1 (f (x t ) -f (x * )) 1 2γ T -1 t=1 h t x t -x * 2 -x t+1 -x * 2 + γ 2 T -1 t=1 g t 2 h t . (32)
Let us bound the first sum on the right hand side, adding and subtracting h t+1 x t+1x * 2 and using telescoping summation, we obtain

T -1 t=1 h t x t -x * 2 -x t+1 -x * 2 = h 1 x 1 -x * 2 -h T x T -x * 2 + T -1 t=1 (h t+1 -h t ) x t+1 -x * 2 . (33)
Furthermore, by Lemma 4 with γ = γ and the fact that (h t ) t 1 is non-decreasing, we get

T -1 t=1 (h t+1 -h t ) x t+1 -x * 2 T -1 t=1 (h t+1 -h t ) x 1 -x * 2 + γ 2 t s=1 g s 2 h 2 s (h T -h 1 ) x 1 -x * 2 + γ 2 T -1 t=1 (h t+1 -h t ) t s=1 g s 2 h 2 s .
For the second term in the above bound, we can write

T -1 t=1 (h t+1 -h t ) t s=1 g s 2 h 2 s = T -1 s=1 g s 2 h 2 s T -1 t=s (h t+1 -h t ) = T -1 s=1 g s 2 h 2 s (h T -h s ) = h T T -1 t=1 g t 2 h 2 t - T -1 t=1 g t 2 h t .

Substitution of the above into the penultimate inequality yields

T -1 t=1 (h t+1 -h t ) x t+1 -x * 2 (h T -h 1 ) x 1 -x * 2 +γ 2 h T T -1 t=1 g t 2 h 2 t - T -1 t=1 g t 2 h t , (34)
Substituting (34) into (33), we deduce that

T -1 t=1 h t x t -x * 2 -x t+1 -x * 2 h T x 1 -x * 2 -x T -x * 2 + γ 2 h T T -1 t=1 g t 2 h 2 t -γ 2 T -1 t=1 g t 2 h t .
Combination of the above with (32) concludes the proof.

B.2 Proofs of corollaries in Section 4

In this section we provide proofs of four corollaries presented in Section 4.

Proof of Corollary 1. Substituting our choice of h t into Theorem 2, we prove in Lemma 9 in Appendix E, page 27, that

T t=1 g t 2 h 2 t log(log(e(1 + S T ))) .
Substituting the above into Theorem 2 and using (12), we deduce that R T (S T +1 + 1) log(e(S T +1 + 1))

√ 8 x 1 -x * log 2 D γ0 γ 0 + 1 2+ 1 3 log(log(e(1 + S T ))) + 5D γ0 log(log(e(1 + S T ))) log 2 D γ0 γ 0 + 1 .
The proof is concluded after re-arranging and using 2ab a 2 + b 2 .

Proof of Corollary 2. Theorem 2 and Lemma 2 (rather Eq. ( 12)) and Lemma 10 give

T t=1 (f (x t ) -f (x * )) S T +1 log 2 2D γ0 γ 0 2 x 1 -x * √ 2 2+ 1 3 log e S T g 1 2 + 5D γ0 log e S T g 1 2 D γ0 S T +1 log 2 2D γ0 γ 0 2 √ 2 2+ 1 3 log e S T g 1 2
+ 5 log e S T g 1 2 .

The proof is concluded after re-arranging and using 2ab a 2 + b 2 .

Proof of Corollary 3. From Lemma 11 we have

T t=1 g t 2 ε + S t log 1 + S T ε .
Hence, substituting the above into Theorem 2 and using (12), we obtain

R T ε + S T +1 log 2 D γ0 γ 0 + 1 √ 8 x 1 -x * 2+ 1 3 log 1 + S T ε + 5D γ0 log 1 + S T ε .
The proof is concluded after re-arranging and using 2ab a 2 + b 2 .

As promised in Section 4, Theorem 4 of Appendix A can be obtained as a corollary of Theorem 2.

Corollary 4. Under assumptions of Theorem 2, with f an L-Lipschitz function. Setting

h t = L √ T and D γ0 = x 1 -x * ∨ γ 0 , Algorithm 1 satisfies T t=1 (f (x t ) -f (x * )) 12.3D γ0 L T log 2 2D γ0 γ 0 . Proof of Corollary 4. Substituting h ≡ L √ T into Theorem 2 gives R T L √ T 2 x 1 -x * k T 2+ 1 3 + γ k T + L √ T γ k T 2 ,
Eq. ( 12) applied to the above, yields

R T L √ T √ 8 x 1 -x * log 2 D γ0 γ 0 + 1 2+ 1 3 + 5D γ0 log 2 D γ0 γ 0 + 1 L √ T √ 8 2+ 1 3 + 5 12.3 D γ0 log 2 D γ0 γ 0 + 1 .
The proof is concluded.

C Analysis for stochastic PGD in Section 5: proof of Theorem 3

Proof of Theorem 3. We recall that (δ) = 1 ∨ log(log 2 (T )/δ). As in all the previous sections, we denote by [T k , T k+1 -1], the interval where k t = k. The regret of the algorithm can be expressed as

T t=1 (f (x t ) -f (x * )) = k T k=1 (f (x T k ) -f (x * )) =:T1(k) + k T k=1 T k+1 -1 t=T k +1 (f (x t ) -f (x * )) =:T2(k)
.

We are going to apply Lemma 7 of Appendix C.1 on page 23, to the second term and provide deterministic bound on the first one. First let us explain the reason of such separation of terms.

Observe that for t = T k

x t+1 = Proj Θ x t - γ kt L T (δ/(1 + k t-1 ) 2 ) g t .
Meanwhile, for t ∈ [T k + 1, T k+1 -1] we have

x t+1 = Proj Θ x t - γ kt L T (δ/(1 + k t ) 2 ) g t .
That is, the x T k +1 step is outside the pattern and requires additional splitting. The proof proceeds as follows 1. First we give deterministic bound on T 1 (k) terms using Lipschitzness of the objective function f ;

2. Then we use Lemma 7 to bound each T 2 (k);

3. Finally, we show that k T is still bounded by k * as in the warmup analysis.

Analysis for T 1 (k). Since f is assumed to be Lipschitz, we can write

T 1 (k) L x T k -x * .
Then, simply by the triangle inequality and property of the Euclidean projection, we deduce that for all k 2

x T k -x * x T k-1 +1 -x T k-1 + x T k-1 -x * + (T k -T k-1 -1) γ k-1 T (δ/k 2 ) x T k-1 +1 -x T k-1 + x T k-1 -x * + (T k -T k-1 -1) γ k T -1 T (δ) .
Furthermore, we have

x T k-1 +1 -x T k-1 γ k-1 T (δ/(k -1) 2 ) γ k T -1 T (δ) .
Hence, we have

x T k -x * x T k-1 -x * + (T k -T k-1 ) γ k T -1 T (δ) .
Unfolding the above recursion, we deduce that

x T k -x * x T1 -x * + T k γ k T -1 T (δ) x 1 -x * + 0.5γ k T √ T .
We conclude that

k T k=1 (f (x T k ) -f (x * )) Lk T x 1 -x * + 0.5γ k T √ T L T T (δ/(1 + k T ) 2 )k T ( x 1 -x * + 0.5γ k T ) . ( 35
)
Analysis for T 2 (k). Let us first fix the high-probability event on which we are going to work. Note that ρ = T k + 1 is a stopping time and T k+1 -1ρ T . Thus, by Lemma 7 with probability at least 1δ/(1 + k) 2 , it holds that

T 2 (k) L T T (δ/(1 + k) 2 ) γ k 2 + x T k +1 -x * 2 -x T k+1 -x * 2 2γ k + 10 x T k +1 -x * + 68γ k .
We observe that

x T k +1 -x * 2 -x T k+1 -x * 2 x T k +1 -x * 2 -x T k +1 -x * -x T k +1 -x T k+1 2 + 2 x T k +1 -x * x T k +1 -x T k+1 .
Let us bound each term of the product. By the design of the rule,

x T k +1 -x T k+1 x T k +1 -x 1 + x 1 -x T k+1 38γ k + 38γ k 76γ k ,
where B = 28. Furthermore, by Lemma 7 and the fact that the

x T k +1 -x T k γ k for all k 1 x T k +1 -x * x T k -x * + 2γ k-1 x T k-1 +1 -x * + 18γ k-1 x 2 -x * + 18 k-1 j=1 γ j x 2 -x * + 18γ k x 1 -x * + 18γ k + γ 1 x 1 -x * + 19γ k . (36)
Thus, we have shown that with probability at least 1

-δ/(1 + k) 2 T 2 (k) L T T (δ/(1 + k) 2 ) γ k 2 + 76 ( x 1 -x * + 19γ k ) + 10( x 1 -x * + 19γ k ) + 68γ k L T T (δ/(1 + k T ) 2 ) 86 x 1 -x * + (259 + 38 2 )γ k L T T (δ/(1 + k T ) 2 ) (86 x 1 -x * + 1703γ k T ) .
Overall, by the union bound, we have with probability at least 1 -

∞ k=1 δ/(1 + k) 2 1 -δ k T k=1 T 2 (k) L T T (δ/(1 + k T ) 2 )k T (86 x 1 -x * + 1703γ k T ) (37)
Regret bound Putting together (35) and (37), we obtain with probability 1δ

T t=1 (f (x t ) -f (x * )) L T T (δ/(1 + k T ) 2 )k T (87 x 1 -x * + 1704γ k T ) . (38)
Bounding the number of phases It remains to bound the number of phases k T . Fix some t 1 and k k t-1 . Observe that for any k 1, x + t (k)x t γ k . Then thanks to Lemma 7 and Eq. (36) (which hold on exact same event that we consider in (38)), we have

x + t (k) -x * x t -x * + γ k x T k t +1 -x * + 16γ kt + γ k x 1 -x * + 35γ kt + γ k x 1 -x * + 36γ k .
Hence, for all k k t-1

x + t (k) -x 1 2 x 1 -x * + 36γ k 2γ k * + 36γ k .
Implying that k T k * .

Concluding In view of the bound k T k * log 2 (2D γ0 /γ 0 ) and γ k * 2D γ0 , we conclude that with probability at least 1δ

T t=1 (f (x t ) -f (x * )) 3500LD γ0 T T (δ/(1 + k * ) 2 ) log 2 (2D γ0 /γ 0 ) .
Note that the constant 3500 is certainly extremely pessimistic as we did not attempt to optimize it.

C.1 High probability bound

We slightly adapt a version of the Bernstein-Freedman inequality, derived in [CBLS05, Corolary 16], improving log(T ) dependency to log log(T ). Lemma 6 (a version of the Bernstein-Freedman inequality by [START_REF] Cesa-Bianchi | Minimizing regret with label-efficient prediction[END_REF]). Let X 1 , X 2 , . . . be a martingale difference with respect to the filtration F = (F s ) s 0 and with increments bounded in absolute values by K. For all t 1, let

S 2 t = t τ =1 E X 2 τ F τ -1
denote the sum of the conditional variances of the first t increments. Then, for all δ ∈ (0, 1) and T 1, with probability at least 1δ,

max t T t τ =1 X τ 2S T ln log 2 (2T ) δ + 3K ln log 2 (2T ) δ .
Proof. Let X * T = max t T t s=1 X s . For k 1 we have

P X * T > 4(S 2 T + K 2 ) + √ 2K /3; K -2 S 2 T ∈ [2 k-1 -1, 2 k ] P X * T > √ 2 k+1 K 2 + √ 2K /3; K -2 S 2 T ∈ [2 k-1 -1, 2 k ] P X * T > √ 2 k+1 K 2 + √ 2K /3; K -2 S 2 T 2 k e -,
where the last inequality follows from Lemma 15 in [START_REF] Cesa-Bianchi | Minimizing regret with label-efficient prediction[END_REF]. Since 0 K -2 S 2 T T , we take a union bound over k = 1, . . . , log 2 (T ) and notice that

4(S 2 T + K 2 ) + √ 2K /3 2 S 2 T + 3K .
The next result is a version of Lemma 1, that was used to analyze deterministic setup, which accounts for the stochasticity. Lemma 7. Let ρ be a bounded stopping time with respect to the filtration F of the stochastic gradients. Let δ ∈ (0, 1), T 1, x 1 ∈ F ρ and consider T (δ) := 1 ∨ log(log 2 (2T )/δ),

x t+1 = x t - γ L T T (δ) g ρ+t .
Assume that T, δ are such that T 1, then with probability at least 1δ we have for all τ T

x τ -x * x 1 -x * + 16γ , τ t=1 (f (x t ) -f * ) L T T (δ) γ 2 + x 1 -x * 2 -x τ +1 -x * 2 2γ + 10 x 1 -x * + 68γ simultaneously.
Proof. To simplify the expressions, we drop the primes, writing x t for x t , and we set η

= γ L √ T T (δ)
.

Using classical analysis of projected gradient descent, we obtain

t τ g ρ+t , x t -x * ηL 2 2 + x 1 -x * 2 -x τ +1 -x * 2 2η . (39)
Introducing the following martingale difference

X t = ∇f (x t ) -g t+ρ , x t -x * ,
we deduce from the above, and the fact that τ T

τ t=1 (f (x t ) -f (x * )) ηL 2 T 2 + 1 2η x 1 -x * 2 -x τ +1 -x * 2 + τ t=1 X t . (40)
Dealing with randomness. Now we are in position to apply Freedman-Bernstein inequality recalled in Lemma 6.

To this end, we need to bound X t and get an appropriate expression for S t . First observe that each martingale difference satisfies

|X t | 2L x t -x * almost surely . (41)
Furthermore, by the triangle inequality, property of projection and the fact that g t L almost surely, we obtain

x t -x * x t-1 -ηg ρ+t-1 -x * x t-1 -x * + ηL x 1 -x * + ηLT, ∀t T + 1 .
Hence,

|X t | K := 2L x 1 -x * + 2L 2 T η, ∀t T + 1.
The conditional variance S 2 T can be bounded using (41) as

S T 2L T t=1 x t -x * 2 2L √ T max t T
x tx * almost surely .

Thus, invoking Lemma 6, for any δ ∈ (0, 1) with probability at least 1δ,

max τ T τ t=1 X t 4L max t T x t -x * T T (δ) + 6L( x 1 -x * + LηT ) T (δ) . (42)
From now on, we work on this event which holds with probability at least 1δ.

Substituting (42) into (40), we get for all τ T τ t=1

(f (x t ) -f (x * )) ηL 2 T 2 + x 1 -x * 2 -x τ +1 -x * 2 2η + 4LΦ T T T (δ) + 6L( x 1 -x * + LηT ) T (δ) , (43)
where Φ T = max t T x tx * .

Bounding the trajectory. Observing that the left hand side of (43) is non-negative and that it holds for all τ T , we deduce max

0 τ T x τ +1 -x * 2 x 1 -x * 2 + 12Lη T (δ) x 1 -x * + (1 + 12 T (δ)) η 2 L 2 T + 8LηΦ T T T (δ) .
Solving the above inequality, we deduce that Φ T ( x 1x * + 6Lη T (δ)) 2 + (1 + 28 T (δ)) η 2 L 2 T + 4Lη T T (δ)

x 1x * + 6Lη T (δ) + ηL (1 + 28 T (δ)) T + 4Lη T T (δ) .

Substituting the value of η, we further deduce that max t T

x tx * x 1x * + γ 1 + 28 T (δ) x tx * T T (δ) + 6(L x 1x * + L 2 ηT ) T (δ) .

Substitution of (44) into the above inequality, yields Recalling that η = γ/(L T T (δ)) and using some rough bounds, we deduce that The proof is complete.

D On a relation with [MS12]

In case where there exists a known bound g t L on the norms of the subgradients, MacMahan and Streeter [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF] propose to tune the step size of gradient descent with a scheme based on a reward doubling argument and cold-restart. Their theory works in a setup of unconstrained online convex optimization with L-bounded subgradients. Since we do not require Lipschitz functions, and we additionally handle the projection step, the two results cannot be directly compared. Nevertheless, there are some similarities and, in a specific instantiation of our Algorithm 1, we recover that of [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF].

Below, we sketch the relation between the two, considering the setting of MacMahan and Streeter [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF], where the norms of the subgradients are bounded by some known L and the optimization is unconstrained, i.e. Θ = R d . We also assume that the time horizon T is known, since unknown T is handled in MacMahan and Streeter [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF] by a time-doubling trick. Using our notation, their analysis starts with a simple bound

T t=1 (f t (x t ) -f t (x * )) T t=1 g t , x t -x * = T t=1 g t , x 1 -x * + T t=1 g t , x t -x 1 T t=1 g t =:G T x 1 -x * - T t=1 g t , x 1 -x t =:Q T = G T x 1 -x * -Q T .
They observe, using a duality argument, that it is sufficient to show that

Q T a -1 exp G T /(bL √ T ) -c, (45)
in order to derive

T t=1 (f t (x t ) -f t (x * )) b x 1 -x * L √ T log ab x 1 -x * L √ T + c .
The principle of their algorithm is to perform gradient descent by phases and, during a phase, to track the reward Q t relative to this phase, and restart with a doubled step-size when the condition Q t > ηL 2 t is met. This step-size doubling ensures that the Condition (45) is met at the time horizon T .

Let us relate this algorithm with a specific instantiation of our Algorithm 1. When the algorithm is the simple Gradient Descent (GD), that does not involve the projection step, we have x T +1 -x 1 = -ηG T for the GD with a fixed step size η. Hence, it holds that

Q T = T t=1 g t , x 1 -x t = η T t=1 g t , G t-1 = η 2 T t=1 G t 2 -G t-1 2 -g t 2 = η 2 G T 2 - T 1 g t 2 = 1 2η x T +1 -x 1 2 - 1 2η Γ2 T +1
where Γ2 T +1 = T 1 η 2 g t 2 . Thus, if in Algorithm 1 we allow cold restarts (the exact thing that we want to avoid), then the condition

x + T (η) -x 1 2 2η 2 L 2 T + Γ2 T + η 2 g T 2
is equivalent to their doubling condition Q T ηL 2 T .

In our notation, the algorithm of MacMahan and Streeter [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF] corresponds to a variant of Algorithm 1 with

Bt+1 (k) = 2 + g t 2 L 2 T γ 2 k + Γ 2 t -Γ 2 T k -1 ,
with the major difference that a cold-restart is performed when k t is increased, and the minor difference that step-size doubling happens after (and not before) the condition x + t (k)x 1 Bt+1 (k) is broken.

Assumption 1 .

 1 The set Θ ⊆ R d is closed convex, D ⊆ R d is open such that Θ ⊆ D. The function f : D → R is convex on Θ and there exists a bounded minimizer x * ∈ arg min x∈Θ f (x).

  RtRegret: f (x) = x 1, x1x * = 14.36

  RtRegret: f (x) = x 2, x1x * = 14.36

|

  ai, x |, x1x * = 14.38 FREE ADAGRAD ORACLE: η = x1-x

Figure 2 :

 2 Figure 2: Regret (left) and step-sizes (right) of three algorithms on loglog scale.

4)

  When translating our regret bound on a rate for the optimization error, using xT -average along the trajectory-we have additional log-factors compared to[START_REF] Carmon | Making sgd parameter-free[END_REF][START_REF] Defazio | Learning-rate-free learning by D-adaptation[END_REF], which is an artifact of online-to-batch conversion[START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF] Theorem 7]. Contrary to us, the algorithms in[START_REF] Carmon | Making sgd parameter-free[END_REF][START_REF] Defazio | Learning-rate-free learning by D-adaptation[END_REF] require yet some knowledge about the Lipschitz constant L.

  x t )f * ) ηL 2 T 2 + x 1x * 2x τ +1x * 2 2η + 4L ( x 1x * + 15.5γ) T T (δ) + 6(L x 1x * + L 2 ηT ) T (δ) .

  x t )f * ) L T T (δ)

  1 do g t ∈ ∂f (x t ) // get subgradient

	S t = S t-1 + g t	2		// cumulative grad-norm
	h t = (S t + 1) log(e(1 + S t )) B t+1 (k) = 2γ k √ k + Γ 2 t + γ 2 k g t 2 /h 2 t		// update ht ht-1 // define the threshold
	x + t (k) = Proj Θ x t -γ k ht g t k t = min k k t-1 : x + t (k) -x 1 x t+1 = x + (k t )	B t+1 (k)	// probing step // find the step size // make the step
	Γ 2 t+1 = Γ 2 t + γ 2 kt	gt 2 h 2 t		// update Γ 2 t
	end
	Output :Trajectory (x t ) t 1

  and by induction the property holds for all t T . Bounding the regret. Let us now upper-bound the regret. We denote by [T k , T k+1 -1] the interval where k t = k, with the convention T k+1 = T k if we never have k t = k, see Figure1for schematic illustration. Summing the central equation (3), the regret can then be decomposed as follows

  Bounding the regret On the other hand, substituting (42) into (40), we obtain

	τ t=1	(f (x t ) -f * )	ηL 2 T 2	+	x 1 -x *	2 -x τ +1 -x * 2η	2
			+ 4L max t T
								T (δ)	+ 4 + 6	T (δ) T
				x 1 -x * + γ	√	29 + 4 + 6	.	(44)
								15.5

  + 1), for all k * 2 , to prove the induction. The concavity of log 2 ensures that log 2 (1 + x) x/ ln(2) for all x > -1.

	Thus, it suffices to show that
	1 2 log 2 (k or equivalently log 2 (k * ) + √ 2 -1 1 2
		1 2	log 2 1 +	1 k * + 1	√	2, for all k * 2 ,
	Thus, for all k * 2
	1 2	log 2 1 +	1 k * + 1	1 2 ln(2)k * + 1	1 4 ln(2)	+ 1	√	2 ,
	which concludes the proof of Lemma 12.

*

Supplementary material for "Parameter-free projected gradient descent"

Appendix A provides details for the proof of Section 3 of the main body. Appendix B contains all the proof for Theorem 2 and Lemma 1. Appendix B.2 provides proof for corollaries in Section 4. Appendix C deals with stochastic version of our algorithm and contains the proof of Theorem 3. Appendix D gives detailed connection with the reward doubling algorithm of [START_REF] Mcmahan | No-regret algorithms for unconstrained online convex optimization[END_REF]. Finally, Appendix E contains auxiliary results that are used in different parts of the proofs.

Below we provide a basic python implementation of our FREE ADAGRAD.

E Auxiliary results

Let (a t ) t 1 be a non-negative sequence, and S t = t τ =1 a τ . For any concave function F on [0, +∞), we have

Applying (46) with Proof. We observe that k = 1 for k * = 1. We will prove that k k * + 0.5 log 2 (k * ) + 0.25 k * + 0.5 log 2 (k * ) + 1.25 .

For proving the first inequality, we only need to prove that 2 y / √ y 2 k * for y = k * + 0.5 log 2 (k * ) + 0.25. Plugging the value of y and taking the square, we get