Rémi Jézéquel
email: remi.jezequel@inria.fr

Pierre Gaillard
email: pierre.gaillard@inria.fr

Alessandro Rudi
email: alessandro.rudi@inria.fr

MIXABILITY MADE EFFICIENT: FAST ONLINE MULTICLASS LOGISTIC REGRESSION

)) achieves a regret of O(log(Bn)) whereas Online Newton Step achieves O(e B log(n)) obtaining a double exponential gain in B (a bound on the norm of comparative functions). However, this high statistical performance is at the price of a prohibitive computational complexity O(n 37 ).

In this paper, we use quadratic surrogates to make aggregating forecasters more efficient. We show that the resulting algorithm has still high statistical performance for a large class of losses. In particular, we derive an algorithm for multi-class logistic regression with a regret bounded by O(B log(n)) and a computational complexity of only O(n 4 ).

Introduction

In online learning, a learner sequentially interacts with an environment and tries to learn based on data observed on the fly [START_REF] Cesa-Bianchi | Prediction, learning, and games[END_REF], [START_REF] Hazan | Introduction to online convex optimization[END_REF]). More formally, at each iteration t ≥ 1, the learner receives an input x t in some space X ; makes a prediction y t in a decision domain Y and the environment reveals the output y t ∈ Y. The inputs x t and the outputs y t are sequentially chosen by the environment and can be arbitrary. No stochastic assumption (except boundedness) on the data sequence (x t , y t ) 1≤t≤n is made. The accuracy of a prediction y t ∈ Y at instant t ≥ 1 for the outcome y t ∈ Y is measured through a loss function : Y × Y → R. The learner aims at minimizing his cumulative regret

R n (f ) = n t=1 y t , y t - n t=1 f (x t ), y t , (1)
with respect to any function f ∈ F in a reference class. All along this paper, we will consider parametric class of functions f θ indexed by θ ∈ Θ ⊂ R d . We will also assume convexity of the loss according to index θ, which we denote x,y : θ → (f θ (x), y) for any (x, y) ∈ X × Y. In this general context, many algorithms have been designed based on different assumptions and obtaining different trade-offs for regret. We review below the most relevant ones for our purpose.

Assuming only convexity of the loss , a well-known strategy for the learner is Online Gradient Descent [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF]) with an optimal regret of order O( √ n). However, if the loss is α-mixable, the learner may achieve the faster rate O( 1 α log(n)) by using an aggregating forecaster (see [START_REF] Vovk | Competitive on-line statistics[END_REF], [START_REF] Van Erven | Fast rates in statistical and online learning[END_REF]). Yet, such an algorithm is not constructive in general and when it is, the computational complexity is often very high (a notable exception is the least-squares setting). To reduce it, a stronger assumption has been introduced by [START_REF] Hazan | Logarithmic regret algorithms for online convex optimization[END_REF] with η-exp concavity. Under the latter hypothesis, Online Newton Step (ONS) has a regret bounded by O( 1η log(n)) and a computational complexity of O(n). However this efficiency comes at the price of deteriorating statistical performance. Indeed, η-exp concavity implies α-mixability for η ≥ α and in some cases, the gap between η and α can be very large.

The most spectacular case of this phenomenon occurs for logistic regression. In this setting, the loss is defined as

( y t , y t ) = -log (σ( y t ) yt )
where σ(z) i = e zi j e zj and the regret is computed with respect to linear functions F = {x → W x, W ∈ Θ}, where Θ = B(R K×d , B) is the Frobenius bounded ball of radius B > 0. On this subset, the logistic loss is η-exp concave only for η ≤ e -B . The regret of Online Newton Step can thus be of order O(e B log(n)). On the other hand, as remarked by [START_REF] Kakade | Online bounds for bayesian algorithms[END_REF] (binary case) and [START_REF] Foster | Logistic regression: The importance of being improper[END_REF], the logistic loss is 1-mixable and an aggregating algorithm may achieve O(log(nB)). Nevertheless, the algorithm relies on Monte Carlo methods and must sample from log-concave probability distributions which is extremely computationally expensive (see Table 1). Therefore, in this framework, the exp-concavity assumption leads to an efficient algorithm with low dependence on B while mixability yields an inefficient algorithm with much better statistical performance.

Between these two extremes, other algorithms and trade-offs have been analyzed. First, it has been shown that in some situations, Follow The Regularized Leader (FTRL) can achieve a fast rate without an exponential constant [START_REF] Bach | Self-concordant analysis for logistic regression[END_REF], [START_REF] Marteau-Ferey | Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance[END_REF], [START_REF] Ostrovskii | Finite-sample analysis of m-estimators using self-concordance[END_REF]). However, several additional assumptions are necessary to achieve these rates. Unfortunately, they are essentially unavoidable. Indeed, [START_REF] Hazan | Logistic regression: Tight bounds for stochastic and online optimization[END_REF] showed a polynomial lower bound for the proper algorithm (i.e., with linear prediction function) in the regime B = log(n). This prevents algorithms like ONS and Follow The Regularized Leader from reaching logarithmic regret without an exponential constant in B. This result motivates the search for improper algorithms with better computational complexity than [START_REF] Foster | Logistic regression: The importance of being improper[END_REF].

For binary logistic regression, two efficient improper algorithms have been proposed in the literature. First, in the i.i.d. framework, [START_REF] Mourtada | An improper estimator with optimal excess risk in misspecified density estimation and logistic regression[END_REF] have proposed the Sample Minmax Predictor (SMP). It achieves an excess risk of order O((B 2 + d)/n) with computational complexity equivalent to Follow The Regularized leader. In the online framework, [START_REF] Jézéquel | Efficient improper learning for online logistic regression[END_REF] proposed AIOLI, which is based on quadratic approximations of the logistic loss as well as virtual labels to regularize. The regret is upper-bounded O(dB log(n)) and the computational complexity is

O(n(d 2 + log(n))).
These previous works left open the question of achieving the same type of performance in a setting other than binary logistic regression. In particular, for multi-class logistic regression, no other algorithm than Foster et al. ( 2018) is known to achieve logarithmic regret without an exponential constant.

Contributions We introduce in Section 3 a new generic online learning algorithm, that we call Gaussian Aggregating Forecaster (GAF) . GAF achieves logarithmic regret with a small multiplicative constant for a large class of convex loss functions (see Theorem 1). The latter includes several popular loss functions such as squared loss, binary and multi-class logistic loss. Our assumptions on the loss functions are slightly stronger than α-mixability but generally weaker than assumptions widely used in the statistical framework such as generalized self-concordance (see [START_REF] Bach | Self-concordant analysis for logistic regression[END_REF]).

In the particular but significant setting of multi-class logistic regression, GAF has a regret bounded by O(dKB 2 + dKB log(n)) and a total computational complexity of O(nK 3 d 2 + K 2 n 4 ), thus significantly improving on the O(B 6 n 25 (Bn + dK) 12 ) complexity of [START_REF] Foster | Logistic regression: The importance of being improper[END_REF], which was the best known to date for algorithms without exponential dependence on B. Table 1 summarizes the regrets and computational cost obtained by the relevant algorithms in this framework. It is worth pointing out that, by using standard online-to-batch conversion [START_REF] Helmbold | On weak learning[END_REF], this paper also provides new results on the excess risk in the statistical i.i.d. Indeed, even in this extensively used framework, the only existing improper algorithms without exponential constant in B so far are GAF and [START_REF] Foster | Logistic regression: The importance of being improper[END_REF]. [START_REF] Jézéquel | Efficient improper learning for online logistic regression[END_REF] and [START_REF] Mourtada | An improper estimator with optimal excess risk in misspecified density estimation and logistic regression[END_REF] are in fact restricted to binary outputs only.

Our new algorithm is inspired by the aggregating forecaster of [START_REF] Vovk | Competitive on-line statistics[END_REF] that we apply to quadratic approximations of the loss, in order to make it more efficient. The high-level idea is that these quadratic approximations replace complicated log-concave distributions with Gaussian distributions, from which it is much easier to sample and thereby drastically reducing the complexity of the algorithm. We believe that this approach can be applied to much broader contexts than those analyzed here.

Setting

We recall here the setting and introduce the main notations and assumptions that will be used throughout the paper.

Setting and notation Our framework is formalized as a sequential game between a learner and an environment. At each forecasting instance t ≥ 1, the learner is given an input x t ∈ X ; forms a prediction y t ∈ Y ⊆ R K (possibly based on the current input x t and on the past information x 1 , y 1 , . . . , x t-1 , y t-1 ). Note that the prediction space Y ⊆ R K may be uni-dimensional (K = 1) in some settings (least-square regression) or multi-dimensional (K ≥ 1) in some cases (e.g., vector-valued regression, multi-class classification). Then, the environment chooses y t ∈ Y; reveals it to the learner which incurs the loss ( y t , y t ). Finally, the performance of the learner is assessed by the regret

R n (θ) = n t=1 ( y t , y t ) - n t=1 xt,yt (θ) ,
with respect to all θ ∈ Θ ⊂ R d . Here, x,y (θ) = (f θ (x), y) where F = {f θ : X → Y} is the reference class of functions. For simplicity of notation, we also define t (θ) = xt,yt (θ) and L t (θ) = t s=1 s (θ) + λ θ 2 for all t ≥ 1 and λ > 0.

In all specific examples considered in this work, the learner will be compared to linear functions f θ : x → θ Φ(x), where θ ∈ Θ = B(R d , B) and Φ is a function from X to R d×K such that for any x ∈ X and i ∈ [K], Φ(x) .,i ≤ R. We introduce and discuss below our main assumptions on the losses.

Assumptions We assume that, for all (x, y) ∈ X × Y, the losses x,y are convex, C 2 and satisfy the following assumptions.

(A1) The loss function is α-mixable. In other words, for all (Gaussian) probability distributions π over R d and input x ∈ X , there exists y ∈ Y such that for all y ∈ Y, ( y, y) ≤ -1 α log E θ∼π e -α x,y (θ) .

(A2) There exists ζ > 0 such that, for all (x, y) ∈ X × Y and

θ 1 , θ 2 ∈ R d , x,y (θ 1 ) ≤ x,y (θ 2 ) + ∇ x,y (θ 2 ) (θ 1 -θ 2 ) + e ζ θ1-θ2 2 θ 1 -θ 2 2 ∇ 2 x,y (θ2) .
(A3) There exists β > 0 such that, for all (x, y) ∈ X × Y and

(θ 1 , θ 2 ) ∈ Θ × R d , x,y (θ 1 ) ≥ x,y (θ 2 ) + ∇ x,y (θ 2 ) (θ 1 -θ 2 ) + β 2 (θ 1 -θ 2 ) ∇ 2 x,y (θ 2 )(θ 1 -θ 2 ) . (A4) is γ-smooth i.e., for all x ∈ X , y ∈ Y, θ ∈ R d , ∇ 2
x,y (θ) ≤ γI. In general, these assumptions are rather weak and related to standard assumptions of (online) convex optimization. (A1) follows from instance from exp-concavity. As we illustrate in Section 4, all are satisfied for broadly used loss functions such as squared loss, binary and multi-class logistic loss. We provide more details on these assumptions below. Mixability (A1) is a standard assumption in online learning to achieve fast rates for the regret [START_REF] Van Erven | Fast rates in statistical and online learning[END_REF], which was introduced by [START_REF] Vovk | Competitive on-line statistics[END_REF]. It is a weaker condition than exp-concavity because (A1) holds with y = E θ∼π [θ] for η-exp concave loss functions when η ≥ α.

Assumption (A2) basically prevents the Hessian from changing too quickly on θ. This condition is new but not very restrictive because, as we prove in Lemma 6, it is weaker than other widely accepted assumptions such as generalized self-concordance [START_REF] Bach | Self-concordant analysis for logistic regression[END_REF].

The lower bound (A3) is the most original assumption and is crucial to make aggregating forecaster efficient. This bound is close to the one needed in the analyses of ONS, which can be derived from η-exp-concavity. However, the key difference is that (A3) uses the Hessian in the quadratic term and not the outer product of the gradient. This makes the right-hand-side closer to the third Taylor series approximation of the loss and allows much larger values for β. For example, as we will show in the section 4.2, this change allows us to remove the exponential constant for the logistic regression setting. In this case, (A3) is verified with β B -1 , while η-exp-concavity would require η e -B .

Algorithm and regret bound

GAF is a new sequential forecasting rule inspired by the aggregating forecaster of [START_REF] Vovk | Competitive on-line statistics[END_REF]. It may be implemented if the loss function is mixable (A1) and ensures fast performance guarantees on the regret under Assumptions (A1)-(A4) as shown in Theorem 1. GAF requires the following hyper-parameters: a regularization parameter λ > 0 and α, β > 0 such that the loss satisfies assumptions (A1)-(A4).

Algorithm (GAF) At each time step, the prediction y t is formed by GAF by following a two steps procedure. A first estimator θ t ∈ R d is computed by solving

θ t = argmin θ∈R d t-2 s=1 ˜ s (θ) + t-1 (θ) + λ θ 2 2 .
(2)

Basically, θ t follows a regularized leader where the losses s for s ≤ t -2 are substituted with quadratic approximations ˜ s . Then, GAF computes the quadratic approximation of t-1 at point θ t . For any θ ∈ R d , it defines

˜ t-1 (θ) = t-1 (θ t ) + ∇ t-1 (θ t ) (θ -θ t ) + β 2 (θ -θ t ) ∇ 2 t-1 (θ t )(θ -θ t ). (3)
Finally, GAF predicts y t ∈ Y such that for all y ∈ Y,

( y t , y) ≤ - 1 α log E θ∼ Pt-1 e -α x t ,y (θ) , where Pt-1 (θ) = e -α Lt-1(θ) R d e -α Lt-1(θ) dθ , (4)
with Lt-1 (θ) =

t-1 s=1

˜ s (θ) + λ θ 2 . Such a prediction y t exists as soon as Assumption (A1) is true. In Section 4, we present some specific cases where y t can be computed in a closed form.

We now state our main theoretical result, which is an upper bound on the regret suffered by GAF. Theorem 1. Let d, n ≥ 1, B > 0, and Θ ⊂ B(R d , B). Let (x 1 , y 1 ), ..., (x n , y n ) ∈ X × Y be an arbitrary sequence of observations and a loss function that verifies Assumptions (A1)-(A4) with α, ζ, β, γ > 0. GAF (4), run with regularization parameter λ ≥ max{4, d}ζα -1 , satisfies the following upper-bound on the regret

R n (θ) ≤ λ θ 2 + d α 1 2 + 2 √ 3 β log 1 + nβγ 2λ , ∀θ ∈ Θ .
In particular, the choice λ = max{4, d}ζα -1 yields

R n (θ) ≤ max{4, d} ζB 2 α + d α 1 2 + 2 √ 3 β log 1 + nαβγ dζ , ∀θ ∈ Θ .
Theorem 1 states that GAF has a logarithmic regret in the number of samples with a multiplicative constant proportional to α -1 (1 + β -1 ). Recalling that α is the mixability parameter, α -1 is the optimal multiplicative constant that can be obtained using an (computationally expensive) aggregating forecaster. The constant β is the curvature parameter in the quadratic lower-bound assumption (A3). Having β -1 as a multiplicative constant can be seen as similar to the regret bound of ONS. However, it is important to note the crucial difference that, unlike ONS, it is the Hessian that is used in the quadratic substitutes of Assumption (A3) and not the gradient outer product. Thus, in some cases, it is possible to have a much larger value for β, than would be attainable using the exp-concavity. For example, for multiclass logistic regression, the loss is 1-mixable (Proposition 1, [START_REF] Foster | Logistic regression: The importance of being improper[END_REF] but only e -B -exp concave. We prove in Lemma 4 that this loss verifies Assumption (A3) with parameter β (log(K) + BR) -1 . Therefore, GAF achieves, in the logistic case, a regret upper bounded by O(dB 2 R 2 + d(log(K) + BR) log(n)). More details on this specific case are given in Section 4.2.

We provide below a sketch of the proof of Theorem 1 that highlights the key steps in the proof. The full proof is available in Appendix B.

Sketch of proof.

The proof starts from the definition (4) of the prediction y t formed by the algorithm. It satisfies the mixability assumption (A1) for all y ∈ Y

( y t , y) ≤ - 1 α log E θ∼ Pt-1(θ) e -α t(θ) , where Pt-1 (θ) = e -α Lt-1(θ)
R d e -α Lt-1(θ) dθ .

Next, we decompose the term on the right side of the inequality into two terms: an approximation error that will be small for well-chosen parameters; and a term, which telescopes and is standard for aggregating forecaster's analysis [START_REF] Vovk | Competitive on-line statistics[END_REF], except that here it is written with quadratic surrogate losses. We have,

( y t , y t ) ≤ - 1 α log R d e -α( t(θ)-˜ t(θ))-α Lt(θ) dθ R d e -α Lt-1(θ) dθ = - 1 α log E θ∼ Pt e -α[ t(θ)-˜ t(θ)] Ωt + 1 α log R d e -α Lt-1(θ) dθ R d e -α Lt(θ) dθ Ψt .
Now, the core idea is that since Lt is quadratic, the integrals inside Ψ t are Gaussian, which allows closed form formulas for the analysis (and fast computational time). Using that ∇ ˜ t (θ t+1 ) = ∇ t (θ t+1 ) and the expression of Gaussian integrals, it is possible to show that

Ψ t = Lt (θ t+1 ) -Lt-1 (θ t ) + 1 2α log |A t | |A t-1 | ,
where A t is the Hessian of Lt /2. Therefore, summing over t = 1, . . . , n and using L0 (θ 1 ) = 0, it yields

n t=1 ( y t , y t ) -Ln (θ n+1 ) ≤ n t=1 Ω t + 1 2α log |A n | |A 0 | .
But, from Assumption (A3) together with the definition (2) of θ t+1 , for any θ ∈ Θ, L t (θ) ≥ Lt (θ) ≥ Lt (θ t+1 ). Thus, the regret can be bounded for any θ ∈ Θ by

R n (θ) = n t=1 ( y t , y t ) -L n (θ) ≤ λ θ 2 + n t=1 Ω t + 1 2α log |A n | |λI| . (5)
Finally, Assumption (A2) allows to bound the approximation error Ω t by a telescopic term close to the usual one but with 1 β as multiplicative constant instead of 1 α ,

Ω t ≤ C β log |A t | |A t-1 | .
The proof is concluded by applying Assumption (A4).

4 Specific settings: squared loss and multi-class logistic

In this section we show how our general framework cover several interesting settings. In particular, we prove that our Assumption (A1)-(A4) are satisfied and provide concrete implementations of GAF in those contexts.

Squared loss

For linear regression with squared loss, we recover classical results by [START_REF] Vovk | Competitive on-line statistics[END_REF]. This framework is defined, as a special case of our generic setting of Section 2, by setting: input domain

X = B(R d , R), output domain Y = [-Y, Y ]
with Y > 0, decision domain Y = R, loss function ( y t , y t ) = ( y t -y t ) 2 and input feature Φ(x) = x. Now we can verify that all assumptions are true: (A1) By Lemma 2 and Lemma 3 of [START_REF] Vovk | Competitive on-line statistics[END_REF], the squared loss is mixable with parameter α = 1/(2Y 2 ).

(A2) The inequality is true for any ζ > 0 as e x > 1/2 for all x > 0. We will take ζ = (8Y 2 dB 2 ) -1 . (A3) It holds with β = 1 because the Taylor expansion of order 2 of a quadratic function is an equality.

(A4) It is true with γ = R 2 since ∇ 2 x,y (θ) = 2xx ≤ 2R 2 I.
In particular, in this particular case the quadratic approximations are exact ˜ t = t for all t ≥ 1. Therefore, GAF reduces to the classical non-linear Ridge regression of [START_REF] Vovk | Competitive on-line statistics[END_REF] and [START_REF] Azoury | Relative loss bounds for on-line density estimation with the exponential family of distributions[END_REF] that predicts

y t = θ t x t with θ t = argmin θ∈R d L t-1 (θ) + θ x t + λ θ 2 .
A direct consequence of Theorem 1, by substituting the constants derived above, yields

R n (θ) ≤ 1 + 8Y 2 d log 1 + 16nB 2 R 2 .
This result essentially recovers the existing regret bound for the non-linear Ridge regression (see e.g., Theorem 11.8 of Cesa-Bianchi and Lugosi ( 2006)).

Logistic regression

The most interesting application of our general framework is logistic regression. In this section, we show the validity of our assumptions and the concrete implementation of GAF in this context. We present the theoretical results obtained and discuss the computational complexity.

The goal of logistic regression is to form a

K-dimensional prediction y ∈ Y = R K of a categorical label y ∈ Y = {1, ..., K} from the observation of an input label x ∈ X = B(R d , R), d ≥ 1.
The performance of y is measured by the logistic loss defined by ( y, y) = -log (σ( y) y ) where σ(z) i = e z i j e z j . Defining the input feature Φ(x) ∈ R d×K with d = d K and the linear predictions respectively as

Φ(x) i,j = x i-d j if d j ≤ i < d (j + 1) 0 otherwise and f θ (x) = θ Φ(x), for θ ∈ B(R d , B),
one can check that our setting recovers the standard multi-class logistic regression setting (see [START_REF] Foster | Logistic regression: The importance of being improper[END_REF] for an equivalent convention). We check below Assumptions (A1)-( A4).

= θ 2 Φ(x) ∈ [-BR, BR] K . (A4) It is valid with γ = R 2 . Indeed, ∇ 2 x,y (θ) = Φ(x)(diag(p) -pp )Φ(x) ≤ Φ(x)Φ(x) ≤ R 2 I, where p = σ(θ Φ(x)).
In particular, the proof of the mixability assumption (A1) provides us a concrete expression for Equation (4) of GAF by setting

y t = σ + (E θ∼ Pt-1(θ) (σ(θ x t ))) . (6)
Substituting the above parameters into Theorem 1 yields the following corollary.

Corollary 2. Let R, B > 0 and d , n, K ≥ 1. Let (x 1 , y 1 ), ..., (x n , y n ) ∈ X × Y be an arbitrary sequence of observations and ( y, y) = -log (σ( y) y ). GAF, run with λ = 32d KR 2 , β = (log(K)/2 + BR + 1) -1 , and

α = 1, satisfies R n (θ) d KB 2 R 2 + d K [log(K) + BR] log 1 + n d K(log(K)+BR) , (7)
for all θ ∈ B(R d , B), where denotes an approximate inequality which is up to universal multiplicative and additive constants.

Computationally efficient approximation Yet, a key difficulty remains to compute exactly y t in Equation ( 6): the calculation of the expectation. In general, there is no closed-form expression and an approximation algorithm, such as Monte Carlo sampling, must be used. We provide now a fully implementable approximated version of GAF, which satisfies the same regret guarantees up to negligible additive constants. It is described in Algorithm 1.

First, to ensure that our approximation of the expectation produces forecasts close to those of the exact algorithm, we must smooth the function σ + in Equation ( 6). Following the idea of [START_REF] Foster | Logistic regression: The importance of being improper[END_REF], we thus define for some µ ∈ [0, 1 2 ], the smoothing operator smooth µ :

∆ K → ∆ K by smooth µ (p) = (1 -µ)p + µ1/K, ∀p ∈ ∆ k . Parameters λ, µ, β, ε, δ > 0, m ≥ 1 initialize A 0 = λI, b 0 = 0, θ 1 = 0 for t = 1, ..., n do receive x t ∈ R d sample independently ω 1 , ..., ω m ∼ N (θ t Φ(x t ), Φ(x t ) A -1 t-1 Φ(x t )) predict ỹt = σ + (smooth µ ( 1 m m i=1 σ(ω i ))) where σ(z) i = e z i j e z j , σ + (z) i = log(z i ) and smooth µ (z) := (1 -µ)z + µ1/K. receive y t ∈ {1, ..., K} update θ t+1 = argmin θ∈R Kd b t-1 θ + θ A t-1 θ + xt,yt (θ) b t = b t-1 + ∇ xt,yt (θ t+1 ) -β∇ 2 xt,yt (θ t+1 )θ t A t = A t-1 + β 2 ∇ 2 xt,yt (θ t+1 ) end
Algorithm 1: Efficient-GAF for K-class logistic regression Now, we can show that σ + (smooth µ (•)) is µ-Lispchitz. Denoting the smoothed approximation of y t by ȳt = σ + (smooth µ (E θ∼ Pt-1 (σ(θx t ))), Lemma 16 of [START_REF] Foster | Logistic regression: The importance of being improper[END_REF] shows that using ȳt instead of y t worsens the regret bound only by an additional constant µn; hence our choice µ = n -1 . The last step of the approximated algorithm consists in using Monte Carlo sampling to approximate the expectation by a finite sum

ỹt = σ + smooth µ 1 m m i=1 σ(ω i ) where ω i i.i.d. ∼ N (θ t Φ(x t ), Φ(x t ) A -1 t-1 Φ(x t )) .
Using Chernoff's inequality, we show below that ỹt concentrates well to ȳt which entails the following guarantee. Proposition 3. Let δ > 0. Efficient-GAF, run with parameters λ = 32d KR 2 , β = (log(K)/2 + BR + 1) -1 , m ≥ 1, and µ = (log(n/δ)/m) 1/3 satisfies with probability 1 -δ the regret bound

R n (θ) d KB 2 R 2 + d K [log(K) + BR] log 1 + n d K(log(K) + BR) + n K m log n δ 1 3
with a computational cost O(nK 3 d 2 + K 2 nm). In particular, the choice m = n 3 log(n/δ), yields the regret bound (7) with probability 1 -δ and a total computational time of order O nK 3 d 2 + K 2 n 4 log(n/δ) .

Proof. We first prove the computational complexity upper-bound. At each iteration t = 1, . . . , n, the algorithm performs the following computations: (i) Update A -1 t : since the rank of A t -A t-1 is K, the inverse A -1 t can be updated in O(K 3 d 2 ) operations. (ii) Update θ t+1 : by Theorem 4 of [START_REF] Jézéquel | Efficient improper learning for online logistic regression[END_REF], this can be done in O(log(n) + K 2 d 2 ). (iii) Compute ỹt : to do so, it must sample m times from a Gaussian of dimension K. The cost is thus O(mK 2 ). Therefore, the overall time complexity of the algorithm is O nK 3 d 2 + K 2 nm .

We now prove the corresponding regret bound. First, we define

pt := smooth µ 1 m m i=1 σ(ω i ) and pt := E[p t ] = smooth µ E θ∼ Pt-1 (σ(θ Φ(x t )) .
With this notation, ỹt = σ + (p t ) and ȳt = σ + (p t ). Using that σ(σ + (p)) = p for any p ∈ ∆ K yields for all

y t ∈ [K] (ỹ t , y t ) = -log σ(ỹ t ) yt = -log σ(σ + (p t )) yt = -log(p t,yt ) ,
where pt,i denotes the i-th component of pt . Similarly, (ȳ t , y t ) = -log(p t,yt ). Therefore, fixing some ε > 0, we have

P (ỹ t , y t ) -(ȳ t , y t ) > ε = P -log pt,y t pt,y t > ε = P [p t,yt -pt,yt < (e -ε -1)p t,yt ] .
Using that e -ε -1 ≤ 1 -2ε for ε ∈ (0, 1 2 ) together with the multiplicative Chernoff's bound (see e.g., Theorem 1.10.5 of Doerr (2020)), entails for all 0 < ε < 1 2 ,

P [ (ỹ t , y t ) -(ȳ t , y t ) > ε] ≤ P [p t,yt < (1 -2ε)p t,yt ] ≤ e -2ε 2 m pt,y t ≤ e -ε 2 mµ/K , (8)
where the last inequality is because smooth µ (p

) i ≥ µ/K for all i ∈ [K]. Taking ε = K µm log(n/δ),
( p t ) yt = log p t,yt (1 -µ) p t,yt + µ K = log 1 1 -µ 1 -1 K pt,y t ≤ 2µ 1 - 1 K p t,yt ≤ 2µ . ( 10
)
Combining ( 9) and ( 10), and using a union bound yields with probability at least 1 -δ n t=1 (ỹ t , y t ) -( y t , y t ) ≤ n K µm log n δ + µn .

Optimizing µ = (log(n/δ)K/m)1/3 and using Corollary 3 concludes the proof.

Using Gaussian distribution improves significantly the computation time with respect to log-concave distribution as considered by [START_REF] Foster | Logistic regression: The importance of being improper[END_REF]. Indeed, it allows to get exact and efficient samples from Pt-1 which leads to a computation time of order O(n 4 ). On the contrary, since it is not possible to draw an exact sample from a log-concave distribution, [START_REF] Foster | Logistic regression: The importance of being improper[END_REF] must resort to expensive random walks to approximately sample from it. Using the method from [START_REF] Bubeck | Sampling from a log-concave distribution with projected langevin monte carlo[END_REF], as suggested by [START_REF] Foster | Logistic regression: The importance of being improper[END_REF], leads to a O(B 6 n 24 (Bn + dK) 12 ) computation time per iteration (see their Example 3 with the choices ε = n -2 and µ = n -1 ).

Note that our analysis shows a clean trade-off between the computational time and the regret bound. One could set a smaller value for m at the price of a larger regret. In particular, it is worth pointing out that our analysis consider the worst case scenario. In the experiments that we considered, it seems that much less samples are sufficient to reach a good accuracy. This is partly because the lower-bound pt,yt ≥ µ ≈ 1/n in Inequality ( 8) may be very coarse for many t. If the pt,yt were of order Ω(1), one could choose m = O(n 2 ) instead of m = O(n 3 ). Another possible explanation comes from the fact that, if A t is large enough, the variance of the samples is small and the convergence is much faster. In our experiments, the choice of m = 100 already provides a good approximation. We leave to future work the possibility to improve the complexity in favorable scenarios.

Comparison with [START_REF] Jézéquel | Efficient improper learning for online logistic regression[END_REF] In the binary case, a more efficient algorithm called AIOLI has been introduced in [START_REF] Jézéquel | Efficient improper learning for online logistic regression[END_REF]. The latter achieves a similar regret bound as GAF, while having a computational complexity of only O(n(d 2 + log(n))). This was possible because AIOLI does not rely on Monte Carlo sampling at all and uses only convex optimization instead. Therefore, one may wonder if it is possible to extend directly AIOLI to the multiclass setting avoiding Monte Carlo methods used in this work. In fact, we first tried to analyse the regret of natural extensions of AIOLI but we found the following inherent difficulties. On the intuitive side, AIOLI was based on the observation that when θ t is far from 0 (let say θ t 0) either y t = 1 and the curvature was advantageous or y t = -1 and θ t tends to the oracle θ t+1 . This intuition is a bit lost in the multiclass setting as several oracles are possible if y t = 1. On a more technical side, the analysis in [START_REF] Jézéquel | Efficient improper learning for online logistic regression[END_REF] crucially relies on the relation g -yt t = -(1 + BR)η t g t (Equation 20) which seems to have no equivalent in the multiclass setting. Thus, it remains an open question if an extension of AIOLI to the multiclass setting is possible.

Experiments

Although GAF is primarily theoretically motivated in a worst-case analysis, here we study its performance on real data sets. We consider three datasets (vehicle, shuttle, and segmentation taken from LIBSVM Data 1 ) and compare the performance of GAF with two well-used algorithms: Online Gradient Descent (OGD) [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] and Online Newton Step (ONS) [START_REF] Hazan | Logarithmic regret algorithms for online convex optimization[END_REF]. The algorithm of [START_REF] Foster | Logistic regression: The importance of being improper[END_REF] is not considered because of prohibitive computational complexity. Concerning the hyper-parameters, the values suggested by the theory are generally too conservative. We thus choose the best ones in a grid for each algorithm (λ, β ∈ [0.01, 0.03, 0.1, 0.3, 1, 3, 10]).

The averaged losses over time are reported in Figure 1. We can remark that the performance of GAF is similar to the one of ONS when the number of samples is high. However, the learning of GAF seems more stable than ONS which leads sometimes (vehicle and segment) to better performance when there are few samples. This is not surprising as aggregating forecasters are hedging against worst-case scenario. Those results show that GAF is not only a theoretical oriented algorithm but could also be used successfully in practice. However, we expect it to perform best in a hard adversarial regime (close to the one described in [START_REF] Hazan | Logistic regression: Tight bounds for stochastic and online optimization[END_REF]).

Conclusion and future work

We have shown how to leverage both mixability and quadratic approximations to design an algorithm GAF which achieves high statistical performance while being more efficient than existing algorithms. In particular, it achieves a new trade-off for multiclass logistic regression.

Some interesting questions are still remaining and left for future work. The linear dependence in B although better than what can be achieved by any proper algorithm is still sub-optimal compared to Foster et al. ( 2018) (logarithmic dependence). It may be possible to improve it by using other surrogates than quadratics. The essential point would be to prove an equivalent of Lemma 4 for those surrogates. The computational complexity of computing Equation ( 6) should remain low. The computational complexity may also be improved. Like previous point, other surrogates could be used to make Equation ( 6) easier to compute. Finally, we believe that GAF should easily be extended to kernels. One would need to adapt the analysis depend on the effective dimension [START_REF] Jézéquel | Efficient online learning with kernels for adversarial large scale problems[END_REF] of the RKHS instead of d. It would of interest to see how classical approximation algorithms, like Nystrom and random Fourier features, deteriorate statistical performance. Finally, we have only provided two examples of loss functions (multi-class logistic loss and squared loss). An intriguing question would be to see if the algorithm can be used to improve existing results for other losses such as Huber loss.

Supplementary material

A Notations and relevant equations

In this section, we give notations and useful identities which will be used in following proofs. At each forecasting instance t ≥ 1, the learner is given an input x t ∈ X ; forms a prediction y t ∈ Y. Then, the environment chooses y t ∈ Y; reveals it to the learner which incurs the loss ( y t , y t ). The regret is defined as

R n (θ) = n t=1 ( y t , y t ) - n t=1 xt,yt (θ) ,
with respect to all θ ∈ Θ ⊂ R d . Here, x,y (θ) = (f θ (x), y) where F = {f θ : X → Y} is the reference class of functions. We assume that, for all (x, y) ∈ X × Y, the losses x,y are convex, C 2 and satisfies Assumptions (A1)-(A4) with parameters α, ζ, β, γ > 0. We also use the following notations:

• t (θ) = xt,yt (θ) • θ t = argmin θ∈R d t-2 s=1 ˜ s (θ) + t-1 (θ) + λ θ 2 2 • ˜ t-1 (θ) = t-1 (θ t ) + ∇ t-1 (θ t ) (θ -θ t ) + β 2 (θ -θ t ) ∇ 2 t-1 (θ t )(θ -θ t ) • L t (θ) = t s=1 s (θ) + λ θ 2 and Lt (θ) = t s=1 ˜ s (θ) + λ θ 2 • Pt-1 (θ) = e -α Lt-1 (θ) R d e -α Lt-1 (θ) dθ • A t = t s=1 β 2 ∇ 2 s (θ s+1 ) + λI .

B Main proof

Proof of Theorem 1. Let t ≥ 1. By definition, the prediction y t (see Equation ( 4)) satisfies the Mixability property (A1).

Applied in y = y t , it yields θ) , where Pt-1 (θ) = e -α Lt-1(θ)

( y t , y t ) ≤ - 1 α log E θ∼ Pt-1(θ) e -α t(
R d e -α Lt-1(θ) dθ = - 1 α log R d e -α( t(θ)-˜ t(θ))-α Lt(θ) dθ R d e -α Lt-1(θ) dθ = - 1 α log E θ∼ Pt e -α[ t(θ)-˜ t(θ)] + 1 α log R d e -α Lt-1(θ) dθ R d e -α Lt(θ) dθ . ( 11
)
We recall that Lt : θ → t s=1

˜ s (θ) + λI where for all s ≥ 1

˜ s (θ) = s (θ s+1 ) + ∇ s (θ s+1 ) (θ -θ s+1 ) + β 2 (θ -θ s+1 ) ∇ 2 s (θ s+1 )(θ -θ s+1 ).
Thus, Lt is a quadratic function with Hessian 2A t where

A t = t s=1 β 2 ∇ 2 s (θ s+1 ) + λI . (12)
Moreover, by definition (2) of θ t+1 and since 0 = ∇ Lt-1 (θ t+1 ) + ∇ t (θ t+1 ) = ∇ Lt (θ t+1 ), we have

θ t+1 = argmin θ∈R d Lt (θ) . (13)
Therefore,

Lt (θ) = (θ -θ t+1 ) A t (θ -θ t+1 ) + Lt (θ t+1 ) ,
and recognizing the integral of a multivariate Gaussian distribution Pt ∼ N θ t+1 , 1 2α A -1 t , we get θt+1) , which substituted into (11) gives

R d e -α Lt(θ) dθ = e -α Lt(θt+1) R d e -α(θ-θt+1) At(θ-θt+1) dθ = (π/α) d |A -1 t |e -α Lt(
( y t , y t ) + Lt-1 (θ t ) -Lt (θ t+1 ) ≤ - 1 α log E θ∼ Pt e -α( t(θ)-˜ t(θ)) Ωt + 1 2α log |A t | |A t-1 | .
Summing over t and using L0 (θ 1 ) = 0, the sum telescopes,

n t=1 ( y t , y t ) -Ln (θ n+1 ) ≤ n t=1 Ω t + 1 2α log |A n | |A 0 | . Denote L n (θ) = n t=1 t (θ) + λ θ 2
. By Assumption (A3) followed by ( 13), for all θ ∈ R d

L n (θ)

(A3) ≥ Ln (θ) (13)
≥ Ln (θ n+1 ) .

Therefore, plugging into the previous inequality, the regret can be bounded as

R n (θ) = n t=1 ( y t , y t ) -L n (θ) + λ θ 2 2 ≤ λ θ 2 2 + n t=1 Ω t + 1 2α log |A n | |λI| . (14)
Now it remains to bound the approximation terms Ω t . Using Jensen's inequality and the concavity of log, yields

Ω t := - 1 α log E θ∼ Pt e -α( t(θ)-˜ t(θ)) ≤ E θ∼ Pt t (θ) -˜ t (θ) = E θ∼ Pt t (θ) -t (θ t+1 ) -∇ t (θ t+1 ) (θ -θ t+1 ) - β 2 (θ -θ t+1 ) ∇ 2 t (θ t+1 )(θ -θ t+1 ) ≤ E θ∼ Pt t (θ) -t (θ t+1 ) -∇ t (θ t+1 ) (θ -θ t+1 ) .
By Assumption (A2) and Cauchy-Schwartz inequality,

Ω t ≤ E θ∼ Pt e ζ θ-θt+1 2 θ -θ t+1 2 ∇ 2 t(θt+1) ≤ E θ∼ Pt e 2ζ θ-θt+1 2
Ωt,1

E θ∼ Pt θ -θ t+1 4 ∇ 2 t(θt+1) √ Ωt,2 . ( 15
)
Now remarking that Pt = N θ t+1 , 1 2α A -1 t , let us bound Ω t,1 the term on the left of the product. There exists an orthonormal basis e 1 , . . . , e d in R d such that θ -θ t+1 follows the same distribution as

d i=1 1 2α λ i (A -1 t )X i e i where X i i.i.d.
∼ N (0, 1), i = 1, . . . , d , and λ i (A -1 t ) denotes the i-th largest eigenvalue of A -1 t . Thus, since λ

i (A -1 t ) ≤ λ -1 , Ω t,1 = E θ∼ Pt e 2ζ θ-θt+1 2 ≤ d i=1 E e ζ α λi(A -1 t )X 2 i ≤ d i=1 E e ζ αλ X 2 i = E X∼χ 2 e ζ αλ X d/2
Then, because λ ≥ 4ζα -1 by assumption and using that the moment-generating function of the χ 2 distribution (with one degree of freedom) is E X∼χ 2 exp(tX) = (1 -2t) -1/2 for t < 1/2 and thus E X∼χ 2 [exp(X/4)] = √ 2, the term can be further upper-bounded as

Ω t,1 ≤ E X∼χ 2 e ζ αλ X d/2 ≤ E X∼χ 2 e 1 4 X 2dζ λα ← Jensen's inequality ≤ 2 dζ λα ≤ 2 ← since λ ≥ dζα -1 . (16)
We now upper-bound Ω t,2 in (15),

Ω t,2 := E θ∼ Pt θ -θ t+1 4 ∇ 2 t(θt+1) = E θ∼N 0, 1 2α A -1 t (θ ∇ 2 t (θ t+1 )θ) 2 = E θ∼N (0,Σt) θ 4 where Σ t = 1 2α (∇ 2 t (θ t+1 )) 1/2 A -1 t (∇ 2 t (θ t+1
)) 1/2 . If we write λ i the i-th largest eigenvalue of Σ t , there exists an orthonormal basis e 1 , . . . , e d such that

Ω t,2 = E θ∼N (0,Σt) θ 4 = E (Xi) iid ∼ N (0,1) d i=1 λ i X i e i 4 = E (Xi) iid ∼ N (0,1) d i=1 λ i X 2 i 2 = d i=1 d j=1 λ i λ j E (Xi) iid ∼ N (0,1) X 2 i X 2 j .
Then remarking that E

iid ∼ N (0,1)

[X 2 i X 2 j ] equals to 3 if i = j and 1 otherwise, we get the following upper-bound

Ω t,2 ≤ 3 i,j λ i λ j = 3 d i=1 λ i 2 = 3 Tr(Σ t ) 2 = 3 Tr 1 2α A -1 t ∇ 2 t (θ t+1 ) 2 = 3 α 2 β 2 Tr A -1 t β 2 ∇ 2 t (θ t+1 ) 2 .
Then, by Lemma 7,

Ω t,2 ≤ 3 α 2 β 2 log |A t | A t -β 2 ∇ 2 t (θ t+1 ) 2 = 3 α 2 β 2 log |A t | |A t-1 | 2 . ( 17
)
Then combining equations ( 15), ( 16) and ( 17), we have

Ω t ≤ 2 √ 3 αβ log |A t | |A t-1 | (18)
which, by summing over t = 1, . . . , n, telescopes

n t=1 Ω t ≤ 2 √ 3 αβ log |A n | |A 0 | .
Combining this upper bound with equation ( 14) yields

R n (θ) ≤ λ θ 2 + 1 α 1 2 + 2 √ 3 β log |A n | |λI| , (19)
which concludes the proof since by (12) and Assumption (A4)

|A n | (12) = λI + β 2 n t=1 ∇ 2 t (θ t+1 ) (A4) ≤ λ + nγβ 2 I = 1 + nγβ 2λ d |λI| .

C Technical Lemmas

The following lemma shows that the logistic loss satisfies Assumption (A3) with β = (log(K)/2 + BR + 1) -1 . Indeed, it suffices to apply it with a = θ 1 φ(x), b = θ 2 φ(x) and C = BR. Indeed, one can check that

y (a) = x,y (θ 1 ) y (b) = x,y (θ 2 ) ∇ y (b) (a -b) = ∇ x,y (θ 2 ) (θ 1 -θ 2 ) (a -b) ∇ 2 y (b)(a -b) = (θ 1 -θ 2 ) ∇ 2 x,y (θ 2 )(θ 1 -θ 2 ) ,
where the terms on the left correspond to the notation of Lemma 4 and the terms on the right to Assumption (A3).

Lemma 4. Let C > 0, a ∈ [-C, C] K , y ∈ [K]
, and b ∈ R K . Denote y (a) = -log e ay j e a j . Then,

y (a) ≥ y (b) + ∇ y (b) (a -b) + 1 log(K) + 2(C + 1) (a -b) ∇ 2 y (b)(a -b) .
Proof. We start the proof by rephrasing our objective. Noting that y (a) = -a e y + log( K j=1 e aj ), one can subtract the linear part on both sides of the inequality. Thus, it suffices to prove the inequality for the function

f : a → log( K j=1 e aj ). Defining ξ(a, b) = f (a) -f (b) -∇f (b) (a -b) - β 2 (a -b) ∇ 2 f (b)(a -b), (20)
with β = (log(K)/2 + C + 1) -1 , it is thus enough to prove that ξ(a, b) ≥ 0 for all a ∈ [-C, C] K and b ∈ R K . But, because ξ(a, a) = 0, the latter is implied by ∇ b ξ(a, b) (b -a) ≥ 0 .
Substituting the definition (20) of ξ(a, b), this can be rewritten as

(1 -β)(b -a) ∇ 2 f (b)(b -a) - β 2 ∇ 3 f (b)[b -a, b -a, b -a] ≥ 0
where for all h ∈ R K ,

∇ 3 f (b)[h, h, h] = i,j,k (∇ 3 f (b)) i,j,k h i h j h k . (21)
Rearranging the terms gives the following condition

∇ 3 f (b)[b -a, b -a, b -a] ≤ 2 1 β -1 ∇ 2 f (b)[b -a, b -a]. (22)
where Then using that ∂ ∂bj p i = 1[i = j]p i -p i p j and chain rules of the derivative, the third derivative may be computed as follows

∇ 2 f (b)[h, h] = i,j (∇ 2 f (b)) i,j h i h j . Let p ∈ ∆ K defined as p i = e b i
(∇ 3 f (b)) i,j,k = ∂ ∂b k (1[i = j]p i -p i p j ) = 1[i = j] ∂p i ∂b k - ∂p i ∂b k p j -p i ∂p j ∂b k = 1[i = j](1[i = k]p i -p i p k ) -(1[i = k]p i -p i p k )p j -p i (1[j = k]p j -p j p k ) = 1[i = j = k]p i -1[i = j]p i p k -1[i = k]p i p j -1[j = k]p i p j + 2p i p j p k . ( 23
)
Let X be a random variable which takes the values b i -a i with probability p i , for i = 1, . . . , K. Now, note that

E[X 3 ] = K i=1 p i (b i -a i ) 3 = i,j,k 1[i = j = k]p i (b i -a i )(b j -a j )(b k -a k ) , E[X 2 ]E[X] = K i=1 p i (b i -a i ) 2   K j=1 p k (b k -a k )   =   i,j p i (b i -a i )(b j -a j )1[i = j]     K j=1 p k (b k -a k )   = i,j,k 1[i = j]p i p k (b i -a i )(b j -a j )(b k -a k ) , E[X] 3 = i,j,k p i p j p k (b i -a i )(b j -a j )(b k -a k ) .
Therefore, summing Equation ( 23) over i, j, k and recognizing the above values of E[X 3 ], E[X 2 ]E[X] and E[X] 3 , the term on the left-hand-side of Inequality ( 22) can be rewritten as

∇ 3 f (b)[b -a, b -a, b -a] (21) = i,j,k (∇ 3 f (b)) i,j,k (b i -a i )(b j -a j )(b k -a k ) (23) = E[X 3 ] -3E[X 2 ]E[X] + 2E[X] 3 = E[(X -E[X]) 3 ]. (24)
Similarly,

∇ 2 (b)[b -a, b -a] = E[X 2 ] -E[X] 2 = E (X -E[X]) 2 .
(25) Substituting ( 24) and ( 25) and replacing η = (log(K)/2 + C + 1) -1 into Inequality ( 22), the latter can be rewritten in the following way

E (X -E[X]) 3 ≤ (2C + log K)E (X -E[X]) 2 . ( 26
)
Recall that X takes values b i -a i with probability p i ∝ e bi and that by assumption a ∞ ≤ C. Almost surely, X is upper-bounded as X ≤ max The following lemma shows that the logistic loss satisfies Assumption (A2). The proof follows from generalized self-concordance. Lemma 6. The logistic loss verifies for all y ∈ [K], x ∈ R d and θ 1 , θ 2 ∈ R d ,

x,y (θ 1 )x,y (θ 2 ) -∇ x,y (θ 2 )(θ 1 -θ 2 ) ≤ e 4R 2 θ1-θ2 2 θ 1 -θ 2 2 ∇ 2 x,y(θ2) .

Proof. By example 2 of [START_REF] Marteau-Ferey | Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance[END_REF], the logistic loss is generalized self-concordant with coefficient 2R. By equation ( 30) of proposition 4 of the same paper, using λ = 0 and µ = δ (x,y) we have

x,y (θ 1 )x,y (θ 2 ) -∇ x,y (θ 2 )(θ 1 -θ 2 ) ≤ ψ( θ 1 -θ 2 ) θ 1 -θ 2 2 ∇ 2 x,y (θ2)

with ψ(t) = (e t -1 -t)/t 2 . Using that ψ(t) ≤ e t 2 for t ≥ 0 concludes the proof.

The following lemma is a classical technical result of linear algebra.

  (A1) It holds with α = 1, since by Proposition 1 of[START_REF] Foster | Logistic regression: The importance of being improper[END_REF], the logistic loss is 1-mixable. Indeed, given a distribution π on R K , the choicey π = σ + (E y∼π σ( y)), where σ + (z) k := log(z k ), satisfiesE y∼π exp(-( y, y)) = E y∼π σ( y) y = σ( y π ) y = exp(-( y π , y)) , for any y ∈ [K]. (A2) It is true for ζ = 4R 2 by Lemma 6 in Appendix C. (A3) It holds with β = (log(K)/2 + BR + 1) -1 by Lemma 4 in Appendix C applied with the choices a = θ 1 Φ(x) and b

Figure 1 :

 1 Figure 1: Averaged losses over time incurred by ONS, GAF, and OGD. The experiments were repeated 20 times and the empirical quantiles 0.25, 0.5, and 0.75 are reported.

K

  j=1 e b j . The first two derivatives of f satisfy∇f (b) = p, ∇ 2 f (b) = diag(p) -pp .

  surely X -E[X] ≤ 2C + log K , which implies Inequality (26) and thus conclude the proof.Lemma 5. For all b ∈ R K , Let p ∈ ∆ K defined as p i = e b iK j=1 e b j . We can write the left term asK i=1 p i b i = -K i=1 p i log(e -bi ).By concavity of the logarithm, it follows from Jensen inequality thatK i=1 p i b i ≥ -log K K i=1 e bi = log K i=1 e bi -log(K) ≥ max 1≤i≤K b i -log(K).

Lemma 7 .

 7 Let d ∈ N and A, B ∈ S + (R d ) such that A > B, then Tr(A -1 B) ≤ log |A| |A -B| .Proof. Using the concavity of X → log |X|, we havelog |A| |A -B| = log |A(A -B) -1 | ≥ Tr(I -(A -B)A -1 ) = Tr(A -1 B).

Table 1 :

 1 Total complexity ndK nd 3 K 3 B 6 n 25 (Bn + dK) 12 nK 3 d 2 + K 2 n 4 Regret bounds and computational complexities (in O(•)) of relevant algorithms for logistic regression with K classes.

	Algorithm	OGD	ONS	Foster et al. (2018)	GAF (Ours)
	Regret	B	√	n dKe B log(n)	dK log(Bn)	dK(B 2 + B log(n))

  Furthermore, denoting p t = E θ∼ Pt-1 (σ(θ Φ(x t )) so that pt = smooth µ ( p t ) and following Lemma 16 of[START_REF] Foster | Logistic regression: The importance of being improper[END_REF], we get (ȳ t , y t ) -( y t , y t ) = log p

	t,yt pt,yt	= log	p t,yt smooth µ
			K µm log n δ	≤ δ n .	(9)

we have

P (ỹ t , y t ) -(ȳ t , y t ) >

https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html


Carine Vaxelaire

Florence Souquet

Marie-Isabelle Lannou

Janick Ardisson

Jacques Royer

Anodic Oxidation: An Attractive Alternative to CAN-Mediated Cleavage of para-Methoxyphenyl Ethers

Keywords: Oxidation, Electrochemistry, Protecting groups, Cleavage reactions

para-Methoxyphenyl (PMP) ether is a very convenient protecting group for the alcohol function; however, its cleavage requires strong oxidative conditions. In this field, the use of powerful ceric ammonium nitrate has been widely described, despite the fact that its strong nature results in the formation of degradation products in acid-or oxidation-sensitive sub-

Introduction

para-Methoxyphenyl (PMP) ether has emerged as a very interesting and useful protecting group for the alcohol function, as this ether is stable under strongly acidic or basic conditions and is specifically cleaved under oxidative conditions. Moreover, this ether possesses unique properties in inducing high stereoselectivities in enantioselective reactions. For instance, according to Corey et al., [1] asymmetric dihydroxylation of homoallylic alcohols has been shown to provide enantiopure diols with good enantiomeric excesses (96 % ee) exclusively when the hydroxy group is protected as a PMP ether. When the PMP group was replaced by any other protecting group, for example, the para-methoxybenzoate group, a severe loss of enantioselectivity was observed. Thus, the PMP group is a powerful hydroxy protecting group; however, its synthetic usefulness relies on the availability of a general and efficient cleavage method. Although ceric ammonium nitrate (CAN) remains the most widely used reagent for this purpose, [2] in our case some difficulties were encountered.

In the course of our work, we have been interested in the preparation of alcohol 3 according to a procedure reported by Tietze (Scheme 1). [3] In our hands, the CAN cleavage step unfortunately failed to give alcohol 3 within the same strates. In this paper, a new anodic oxidation method for the cleavage of para-methoxyphenyl ethers in weakly basic medium is reported. This process is an attractive alternative to circumvent the use of ceric ammonium nitrate. ( yield as that reported (91 %). In fact, compound 3 was isolated in 20-80 % yield, the rest of the mass balance accounting mainly for degradation products.

Scheme 1. Procedure outlined by Tietze for the preparation of compound 3.

Exploitation of the oxidizing properties of CAN for synthetic purposes remains limited due to a striking lack of selectivity in the cleavage of PMP ethers with regard to other hydroxy protecting groups. This drawback is particularly well evidenced in reactions involving acid-sensitive moieties, as the mechanism of CAN-induced removal of PMP ethers involves the liberation of hydronium ions in the reaction medium. This can be circumvented by the use of bases like pyridine or an aqueous solution of sodium hydrogen carbonate, [4] but even under these conditions, CAN still leads to partial decomposition of material. Finally, from an experimental point of view, purified compounds systematically reveal a red colour, which implies that trace amounts of cerium salts still remain.

However, despite the disadvantages mentioned above, to date only a few alternative methods have been reported and are anecdotally used, among these are: lithium in liquid ethylamine, [5] silver oxide/nitric acid in dioxane [6] silver(II) dipicolinate-H 2 O complex in a MeCN/H 2 O/MeOH mixture [7] and silver oxide/2,6-pyridine dicarboxylic acid in MeCN/H 2 O. [8] Thus, in case of highly functionalized substrates and more particularly in the field of total synthesis, selective and efficient cleavage of PMP protecting groups has turned out to be of primary interest.

Electrochemical deprotection methods are scarcely reported [9] while generally providing mild conditions respective of many sensitive functional groups. In 2005, our group described the deprotection of N-para-methoxyphenylamines (N-PMP) by anodic oxidation. [10] To date, very few papers deal with the anodic cleavage of the carbon-oxygen bond in PMP ethers. The first example concerns diaryl ethers. [11] The reaction, conducted in methanol, provides bis(acetal)s. This method is directed by p-methoxy substitution.

The second example deals with the deprotection of paramethoxyphenyl pyranosides. [12] In this particular case, the removal of anomeric PMP groups was described without investigation of the scope of the reaction and, as such, cannot be extended to the standard regeneration of aliphatic alcohols. Noteworthy, experiments have only been carried out on analytical scale (0.006 to 0.139 mmol). Thus, the lack of preparative scale methods is obvious.

In this paper, a preparative anodic cleavage of primary and secondary alkyl para-methoxyphenyl ethers is reported.

Results and Discussion

In order to establish a general method, the reaction was first carried out on PMP ether 4 derived from 2-phenylethanol. The results are presented in Table 1. All the experiments were conducted in a separated cell at a controlled potential (i.e, vs. saturated calomel electrode, SCE) at platinum electrodes. The very first assay was performed at a concentration of 1.5 m in a 9:1 mixture of acetonitrile/water at room temperature, and the oxidation potential was fixed at a constant value of 1.55 V (Table 1, Entry 1). [START_REF]substrate revealed an oxidation wave around 1[END_REF] Under these conditions, alcohol 5 was obtained with a satisfactory 77 % yield within 1 h. It was then observed that the use of a saturated aqueous solution of sodium hydrogen carbonate instead of water had a beneficial effect, giving a cleaner reaction. In parallel, increasing the potential to 1.7 V resulted in an increased yield. Finally, it was found possible to work under more concentrated conditions (from 1.5 to 15 m) without loss of yield, thus giving access to a preparative method. Finally, the combination of the three abovementioned conditions led to excellent results (92 % yield; Table 1, Entry 2) and was elected as a standard for the cleavage of a set of PMP ether compounds (Scheme 2). [START_REF]The anodic oxidation of compound 4 was also done under constant current conditions (120 mA) and alcohol 5 was obtained with a good yield of 70 %[END_REF] The course of the electrolysis can be monitored by TLC or by measurement of residual intensity (the reaction was stopped when the intensity reached less than 5 % of its initial value).

In order to establish a comparison, most relevant substrates were submitted to both anodic oxidation (AO) and buffered CAN-mediated cleavage of PMP ethers.

Table 1. Oxidative cleavage of primary and secondary alkyl paramethoxyphenyl ethers.

[a] Reactions were conducted on 3.75 mmol at C =1 5 m . Compared to AO, model compound 4 was easily deprotected by using CAN, despite a lower yield, [START_REF]Two batches of commercial CAN were used for testing. Slight differences in yields were observed, depending on the batch used[END_REF] showing that CAN-mediated cleavage is more degradative (Table 1, Entry 1).

Various diols bearing both a PMP and an acid-sensitive protecting group (tert-butyldimethylsilyl 6, tetrahydropyran 8 and dimethylacetonide 2, 10) evidenced selective PMP ether cleavage under buffered-anodic oxidation conditions (Table 1, Entries 3-6). Interestingly, the protocol for AO was successfully applied to ether 2 and target alcohol 3 was easily regenerated in high yield (Table 1, Entry 5). In contrast, the CAN-mediated cleavage of ethers 2 and 6 (Table 1, Entry 5 and 3, respectively) resulted in degradation products, whereas 8 (Table 1, Entry 4) was cleanly cleaved. Finally, anodic oxidation gave the best yield in the selective removal of the PMP group of 12 bearing a basesensitive pivaloate function (Table 1, Entry 7).

Anodic oxidation using NaHCO 3 as buffer is suitable to the cleavage of PMP ethers in the presence of acid-and base-sensitive substrates. Consequently, a wide range of hydroxy protecting groups is compatible with buffered-anodic oxidation method.

The reaction was further checked on oxidation sensitive substrates. Enyne 14 was successfully converted into alcohol 15 (Table 1, Entry 8), and neither decomposition nor allylic oxidation was observed. In the same manner, the PMP group of substrate 16 was cleanly cleaved in the presence of a para-methoxybenzyl (PMB) group (Table 1, Entry 9). However, in this latter case, the potential was fixed at 1.4 V to avoid PMB group oxidation. At the opposite, under CAN-mediated cleavage conditions, enynol 15 was isolated in low yields from 14, whereas PMP ether function of 16 was selectively cleaved in the presence of PMB ether.

Finally, cleavage of the secondary para-methoxyphenyl ether group of 18 was also carried out, leading to menthol (19; Table 1, Entry 10) in satisfactory, although unoptimized, yield.

As a conclusion, in all cases studied, anodic oxidation provided the required alcohols in better yields than buffered CAN-mediated reaction. These examples have efficiently demonstrated that the anodic oxidation reaction was highly selective, contrary to CAN-induced cleavage of PMP ethers, which has exhibited side reactions such as cleavage of acidlabile functions. Moreover, contrary to the CAN-mediated reaction, the AO process is highly reproducible.

The mechanism of the anodic oxidation is similar to the one assumed for CAN-mediated cleavage of para-methoxyphenyl ethers. In both cases, stepwise oxidation of the para-methoxyphenyl function led to the formation of quinone together with the expected aliphatic alcohol. It is worth specifying that the reaction was complete when a quantity of electricity of 2.2 F mol -1 was delivered into the reaction medium; thus the coulometric yield is close to the theoretical amount of electricity (2 F/mol).

Conclusions

In summary, we have demonstrated that primary and secondary alkyl para-methoxyphenyl ethers can easily be cleaved by anodic oxidation. The reaction is rapid (0.5 to 1 h) and constitutes an attractive, nondegradative alternative to CAN-mediated cleavage, which provides desired alcohols in a cleaner manner and with more reproducible yields. Moreover, this is also an original orthogonal process for the selective deprotection of para-methoxyphenyl protecting groups, as a wide range of acid-, base-and even oxidation-sensitive functions are tolerated. Finally, this method can be easily carried out by using basic electrochemical equipment and on preparative scale.

  [a] Laboratoire de Synthèse et Structure de Molécules d'Intérêt Pharmacologique UMR 8638-CNRS Université Paris Descartes Faculté des Sciences Pharmaceutiques et Biologiques 4, av. de l'Observatoire, 75270 Paris cedex 06, France Fax: +33-1-43291403 E-mail: janick.ardisson@parisdescartes.fr Supporting information for this article is available on the WWW under http://dx.doi.org/10.1002/ejoc.200900262.

  Scheme 2. General procedure for the oxidative cleavage of alkyl para-methoxyphenyl ethers.

© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim Eur. J. Org. Chem. 2009, 3138-3140

Eur. J. Org. Chem. 2009, 3138-3140 © 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim www.eurjoc.org

www.eurjoc.org © 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim Eur. J. Org. Chem. 2009, 3138-3140

Acknowledgments

This work was supported by the Centre National de la Recherche Scientifique (CNRS) and the University Paris Descartes. We thank M. Pulicani for kind loan of integrator AMEL 731.

Supporting Information (see footnote on the first page of this article): Detailed procedures and characterization data for ethers and alcohols illustrated in Table 1.