Mixability made efficient: Fast online multiclass logistic regression
Authors: Rémi Jézéquel
Pierre Gaillard
Alessandro Rudi
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Online learning
Logistic regression

Abstract: Mixability has been shown to be a powerful tool to obtain algorithms with optimal regret. However, the resulting methods often suffer from high computational complexity which has reduced their practical applicability. For example, in the case of multiclass logistic regression, the aggregating forecaster (see Foster et al. 2018) 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 multiclass regression with a regret bounded by $O(B\log(n))$ and computational complexity of only $O(n^4)$.

Mixability made efficient:
Fast online multiclass logistic regression
Rémi Jézéquel
Pierre Gaillard Univ. Grenoble Alpes, Inria,
INRIA Département d' I'Infommttquue de l'École Normale Supérieure, PSL Research University
CNRS, Grenoble INP, LJK Grenoble, France pierre gierre.gaillarddiniiie
Paris, France
remi jenn.jeezquellinia.fff
Alessandro Rudi
INRIA Département d' Informatique de l'
Normale Supérieure, PSL. Research University
Paris, France
al alessandro cwwprandroouuuuiee. Sinrian ian.idiiiardiiiiii.aa.aaa
Abstract
Mixability has been shown be a powerful tool obtain algorithms with optimal regret. However, the resulting methods often suffer from high computational complexity which has reduced their practical applicability. For example, the case of multiclass logistic regression, the aggregating forecaster (Foster et al. (2018) achieves regret of O(log(Bv) whereas Online Newton Step achieves OlE log(n)) obtaining double exponential gain in B (a bound on the norm of comparative functions). However, this high statistical performance at the price of prohibitive computational complexity (
In this paper, we quadratic surrogates make aggregating forecasters efficient. We show that the resulting algorithm has still high statistical performance for large class of losses. In particular, we derive algorithm for multi-class logistic regression with a regret bounded by O(B log(n)) and a computational complexity of only O(n²).
Introduction
In online learning, a learner sequentially interacts with an environment and tries to learn based on data observed on the fly (Cesa-Bianchh and Lugosi (2006), Hazan et al. (2016). More formally, at each iteration > 1, the learner receives an input 2; some space X: makes a prediction Ør in decision domain 3r and the environment reveals the output Yt E y. The inputs x, and the outputs y are sequentially chosen by the environment and can be arbitrary. No stochastic assumption (except boundedness) on the data sequence (I+, We) grgnn is made. The accuracy of prediction Te E y at instant 2 for the outcome Y/ ) is measured through a loss function e: e x y - R. The learner aims at minimizing his cumulative regret
Ra(
Σ (Te.
Σ (((()))
with respect to any function f F in reference class. All along this paper, will consider parametric class of functions fe indexed by 0 E C Rdd We will also assume convexity of the loss according index 0, which we denote la ((fo(z)))) y) for any (a, v) E X Y. In this
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Algorithm
OGD
ONS
Foster et al. 20188)
GAF (Ours)
Regret
Byn ndK
dKe log(n) nd K
dK log Bn) B 2Bn + dK) 12
dK + B Bl)g(n) 3 ² + K2n
Total complexity
Table 1: Regret bounds and computational complexities (in O()) of relevant algorithms for logistic regression with K classes.
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 l, well-known strategy for the learner is Online Gradient Descent ZZikeviich/ (2003) with an optimal regret of order O()n). However, if the loss is o-mixable, the learner may achieve the faster rate O a lo)( by using an aggregating forecaster (see Vovk (2001). Van Erven et al. (2015)). Yet, such an algorithm is not constructive in general and when it IS, the computational complexity often very high notable exception is the least-squares setting). To reduce it, stronger assumption has been introduced by Hazan et al. (2007) with ey-exp concavity. Under the latter hypothesis, Online Newton Step (ONS) has regret bounded by O log(n)) and a computational complexity of (m). However this efficiency comes at the price of d'deteriorating statistical performance. Indeed, 17-exp concavity implies a- o-mixability for rj 2 a and some cases, the gap between 1 and a can be very large.
The most spectacular case of this phenomenon occurs for logistic regression. In this setting, the loss is defined as
é (Tt, vt.) = - -log (W)))))
where
a(z); E,
and the regret is computed with respect to linear functions F= fo + WI, W E 0), where = (R k xd B) is the Frobenius bounded ball of radius > O. On this subset, the logistic loss is 77-xxp concave only for 1j S e- The regret of Online Newton Step can thus be of order O Ing(n)). ). On the other hand, as remarked by Kakade and Ng (2008) (binary case) and Foster et al. 2018), the logistic loss is 1-mixable and an aggregating algorithm may achieve Olog Nevertheless, the algorithm relies on Monte Carlo methods and must sample from tog-concave probability distributions which is extremely computationally expensive (see Table [D. Therefore, in this framework, the exp-concvvity 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-off' have been analyzed. First, has been shown that in some situations, Follow The Regularized Leader (FTRL) can achieve fast rate without an exponential constant (Bach et al. (010)) Martcau-Ferey et al. 2019),, Ostrovskii et al. (2021)) However, several additional assumptions are necessary achieve these rates. Unfortunately, they are essentially unavoidable, Indeed, Hazan et al. 2014) 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 Foster et al. (2018).
For binary logistic regression, two efficient improper algorithms have been proposed in the literature. First, in the i.i.d. framework, Mourtada and Gaïtfas (2019) have proposed the Sample Minmax Predictor (SMP). It achieves an excess risk of order O ( + d)/n) with computational complexity equivalent to Follow The Regularized leader. In the online framework, Jézéquel et al.; (2020) proposed AIOLI, which is based on quadratic approximations of the logistic loss as well as virtual labels to regularize. The regret is upper-bounded (d log(n)) and the computational complexity is O(n(d2 + log(n))).
These previous works left open the question of achieving the same type of performance a setting other than binary logistic regression. In particular, for multi-class logistic regression, no other algorithm than Poster 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 D. 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 a-mixability but generally weaker than assumptions widely used in the statistical framework such as generalized self-concordance (see Bach et al. (2010))
In the particular but significant setting of multi-class logistic regression, GAF has regret bounded by O(dk + dK log(n) (n) and total computational complexity of O(nK" + K²n*) thus significantly improving on the O(B"n (Bn dK) 12) complexity of Foster et al. (0188), which was the best known to date for algorithms without exponential dependence on B. Table summarizes the regrets and computational cost obtained by the relevant algorithms in this framework. It is worth pointing out that, by using standard toline-to-batch conversion Helmbold and Warmuth (1995), 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 Foster et al. (011)). Jézéquel et al. (2020) and Mourtada and Gailfas (2019) are in fact restricted to binary outputs only.
Our new algorithm is inspired by the aggregating forecaster of Vovk (001) that we apply to quadratic approximations of the loss, in order to make more efficient. The high-level idea 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.
2 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 i 2 1, the learner is given input H, E X:; forms a prediction Tt. E ) C R.K (possibly based on the current input Ie and on the past information Ii, 11, -z- 1, 1)) Note that the prediction space ) C R.K may be uni-dimensional (K 1) in some settings (least-square regression) or multi-dimennional (K 2 1) in some cases (e.g., vector- valued regression, multi-class classification). Then, the environment chooses yt E Y: reveals it to the learner which incurs the loss E(Tt. Vt). Finally, the performance of the learner is assessed by the
regret
(0) Σ E(Tr, ve)
Σ (e) t=1
with respect to all E θ c Rdd Here, (0) = (()(())))) where F (fo : X - 5) is the reference class of functions. For simplicity of notation, we also define (,) = lx
w (0) and
(0) = - (,( 2llla2 for all 2 1 and 0.
In all specific examples considered in this work, the learner will be compared linear functions fo x 0 (zz), where 0 E θ B(R B) and &b is function from X' to Rd K such that for any x E X and i E [K], (f)... S R. We introduce and discuss below our main assumptions on the losses.
Assumptions We assume that, for all (4,y) E X x V, the losses Ex,y are convex, C2 and satisfy the following assumptions.
(A1) The loss function is a-mixable. In other words, for all (Gaussian) probability distributions æ over Rdd and input x E X, there exists ÿ E y such that for y E V.
(( v) < - log [Eo-IE ( -ao
1 a
(A2) There exists < > 0 such that, for all (I, v) E X x y and 01, 02 E Rd.
(0:) S (02) + Vla., (02) TT))(()))))))))) [(1 02) + S10: -021 110 -2 02112re,,,,00))
3

---

(A3) There exists 3 > 0 such that, for all (z, y) E X x y and (01, 02) E O R
(x1)((1) 2 (z.y (02) + (er,y(02) - -02) + 2 (01 - 02) T2)TT([ (02) - 02)
(A4) is 7-smooth Le., for all X, 0 R. v 2 S nT.
In general, these assumptions are rather weak and related to standard assumptions (online) convex optimization. [AI]folsss 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. provide more details these assumptions below.
Mixability (AT) is a standard assumption in online learning to achieve fast rates for the regret (Van Erven et a... 2013), which was introduced by Vovk (200T). It is a weaker condition than exp-concavity because (A1) holds with R for 7/-exp concave loss functions when vj 2 a.
Assumption (A2) basically prevents the Hessian from changing too quickly on A. This condition new but not very restrictive because, we prove in Lemma it weaker than other widely accepted assumptions such as generalized self-concordance (Bach et al., 2010).
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 the analyses of ONS, which can be derived from 7-exp-concavitty However, the key difference is that 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 B. For example, as will show in the section (42, this change allows us to remove the exponential constant for the logistic regression setting. In this case, (A3) is verified with B = B-1 while --exp-concavity would require 7) = e-
Algorithm and regret bound
GAF is new sequential forecasting rule inspired by the aggregating forecaster of Vovk (2001)
may be implemented if the loss function É is mixable (A1) and ensures fast performance guarantees on the regret under Assumptions (AI) (A4) as shown in Theorem [ GAF requires the following hyper-parameters: regularization parameter À 0 and a, B such that the loss & satisfies assumptions (Al) (A4)
Algorithm (GAF)
At each time step, the prediction ÿe is formed by GAF by following a two steps procedure. A first estimator 0g Rd is computed by solving
0, argmin DER
Σ +. + +1101
Basically, 6, follows regularized leader where the losses L, for < t 2 are substituted with quadratic approximations l.. Then, GAF computes the quadratic approximation of f at point 0, For any f Rd. it defines
(4)-1(0)) 01) + 8000 0.) V 0.).
(3)
Finally, GAF predicts De 5 such that for all y y,
c
1 ((Tr, v) < log (Ba-Ah_,e- e-afe.))()))
where P=-1(0) =
(4)
Jg - 1(8)
with i
(.(0) + 211011 Such prediction Tn exists true. In Section we present some specific cases where T. can be computed in a closed form.
as Assumption (A1)
We now state main theoretical result, which is an upper bound on the regret suffered by GAF.

---

Theorem 1. Let d, 2 1, >>> O, and θ C B(TRA B). Let (01,31);, (n) E X y be
arbitrary sequence of observations and E a loss function that verifies Assumptions (SttmpptionsAA))AA (A4) with an 6, > O. GAF 4 run with regularization parameter 2 max 4, d](a= satisfies the following upper-bound the regret
d
1
2 B
ngy 2A
R,( - \110122
log 1
40 O.
a
2
In particular, the choice À max dj<a yields
CB²
d
2v3 B
na,37 YA e
Rn(0) max d)
+ a
log 1+
dc
a
Theorem states that GAF has logarithmic regret in the number of samples with a multiplicative constant proportional to (1 + 3-1). Recalling that a is the mixability parameter, a- is the optimal multiplicative constant that can be obtained using an (computationally expensive) aggregating forecaster. The constant 3 is the curvature parameter in the quadratic lower-bound assumption (A3) Having 3-1 as multiplicative constant can be seen as similar to the regret bound of ONS. However, 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 3, than would be attainable using the exp-concavity. For example. for multiclass logistic regression, the loss is 1-mixable (Proposition 1, Foster et al. 2018) but only e -cx concave. We prove in Lemma that this loss verifies Assumption (A3) with parameter B = (log( K BR) -1 Therefore, GAF achieves, in the logistic case, regret upper bounded by O(dB R + d(log( K) + BR) log(n)). More details on this specific case are given in Section 4
We provide below a sketch of the proof of Theorem | 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 It satisfies the mixability assumption (AI) for all y E
the prediction De formed by the algorithm.
ala-1(9))
E(Tr, v) log PF -a)((1)) where Pt-1(0) Jg
al, 119)
Next, we decompose the on the right side of the inequality into two terms: an approximation eиror that will be small for well-chosen parameters; and a term, which telescopes and is standard for aggregating forecaster's analysis (Vovk 200I), except that here it written with quadratic surrogate losses. We have,
(100)) -at (0) Jne 1al--aai-10)
E(0e, v1) S - log a
log 00l1)))001())) + log Sgs (a
1
Sgs e eate
W.
Now, the core idea is that since L, is quadratic, the integrals inside V Gaussian, which allows closed form formulas for the analysis (and fast computational time). Using that (l,(0++1) (0.4))) and the expression of Gaussian integrals, it is possible show that
|Ael
V = (((44)) -,-1(0)) + 2a
log
A
where A, is the Hessian of L./2. Therefore, summing over 1,..., n and using (o()) = 0, yields
[Aull
Σ (Tr (0n41) < S4 +
log
2a
Ap
5

---

But, from Assumption (A3) together with the definition ( of 01+1, for any 0 E O, L,()) 2 L,(0)
2
(0(+1)). Thus, the regret can be bounded for any 0 E θ by
1
[An
e(v,. vo) - (0) - X 1 + Rs (0) = Σ
Σ [=1
24 +
log
(5)
2a
X1
1=1
Finally, Assumption [A2) allows to bound the approximation error S2 by telescopic term close to the usual one but with aB as multiplicative constant instead of 7
C ax3
|Ael
log
AA-11
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. particular, we prove that our Assumption (AI)(A) (A4) are satisfied and provide concrete implementations of GAF in those contexts.
4.1 Squared loss
For linear regression with squared loss, we recover classical results by Vovk 2001). This framework is
defined, special case of our generie setting Section 2 by setting: input domain X (3 R)). output domain y = [-Y,Y] with Y > 0, decision domain = IR, loss function E(Tr, yt) = (W:- ( ye
and input feature (z) = x. Now we can verify that all assumptions are true:
(A1)
By Lemma and Lemma 3 of Vovk (200T), the squared loss is mixable with parameter
a= =)
A2
The inequality is true for any Ç 0 as e" 1/2 for all 0. We will take
(8Y22dB²-1
A3
because the Taylor expansion of order 2 of quadratic function is an is true with 7 R² since V2lz. (0) 2x. s 2R
It holds with equality.
(A4)
In particular, in this particular case the quadratic approximations are exact & for all t > Therefore, GAF reduces the classical non-linear Ridge regression Vovk (200] and Azoury and Warmuth 2001) that predicts
T 0, Xt with
argminger* (0) 0T x, + \|0113]
direct consequence of Theorem I by substituting the constants derived above, yields
R (n) < 8Y (1 16 RR)
This result essentially recovers the existing regret bound for the non-linear Ridge regression (see e.g.. Theorem l 1.8 of aaCCea--iindee and Lugosi (2006)).
Logistic regression
The most interesting application of our general framework is logistic regression. In this section, 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
form K -ddimnnsional prediction e EK of categorical label ) = {1,... K} from the observation of an input label x E X' =BR(" RR. d' 2 1. The performance of y measured by the logistic loss defined by
( y) log (g)
where a(2); Σ, 65
Defining the input feature (fx:) E d with d = d' K and the linear predictions respectively
Ti-d'; if j < d'(j 1) and fo(x) 0 (xx) for f E B(R B), otherwise
1 (T))
0
one can check that our setting recovers the standard multi-class logistic regression setting (see Foster al. (018)) for an equivalent convention). We check below Assumptions (Al) (A4)

---

Parameters X, μ. 5, > 0, m 21 initialize Ag XI, 0, 01 = for / = 1,.,.., do
receive 2t E TRdd
sample independently w1, Wm ~ NO, ((x,), 2(xx) T (x=))
predict 1/ = a (smooth, ( (1 Di=1 o(wi))) where o(2); E o t (z); log(2;) and
smooth = (1 p))z + p1/K.
receive y1 E {_,... K}
update
B1+1 = argmingERKa b,_ 0 + A,-10 e (0)
by b-11 + Vlr.v. (0(+1) 2 2z (0141)
A, = A--1 + 2 V (0++1)
end
Algorithm 1: Efficient-GAF for K-class logistic regression
(1
It holds with 1, since by Proposition of Foster et al. (2018), the logistic loss is 1-mixable. Indeed, given a distribution π on I the choice V/ ( where
(z)x log(=x), satisfies
Enga exp( E(T. v)) Eg (1, o = exp(-e(0x..))
for any E [K].
A2
is true for ( - 4 by Lemma 6 in Appendix C.
A3
It holds with = (log K2/2 BR + 1) by Lemma 4 in Appendix C appliied with the choices a = 0, (z)) and i = 0, (xx) ) E BR, BR]K
(44)
R² Indeed, (0) = (z)) - ) (x)) where p p=o(0" (=x)) which can be bounded by bz,g s (c))((a) S RFI.
It valid with
In particular, the proof of the mixability assumption (A1) provides concrete expression for Equation (4) of GAF by setting
Te = - (Bpp(( (a x1))).
(6)
Substituting the above parameters into Theorem yields the following corollary.
Corollary 2. Let R, B O and d', n, K 1. Let (2 v1,, .... (In, Un) X x be an ar-
bitrary sequence of observations and { y) = - log (a(W),) GAF, run with X 32d' KR, B = (log(K)/2 /2/2 + BR + +1= and a = 1, satisfies
(0) S d'KB2R² + d'K [log(K) BR] log (1+ (K()o(()++BB)
for all O E B(R B), where S denotes approximate inequality which is up to universal multi- plicative and additive constants.
Computationally efficient approximation Yet, key difficulty remains to compute exactly ÿe in Equation (6: the calculation of the expectation. general, there no dosedd-frm expression and an approximation algorithm, such Monte Carlo sampling, must be used. We provide now fully implementable approximated version of GAF, which satisfies the same regret guarantees up to negligible additive constants. It is described in Algorithm [
First, ensure that our approximation of the expectation produces forecasts close those of the exact algorithm, we must smooth the function o+ in Equation (6). Following the idea Foster et al. (2018), we thus define for some μ E [0, b) the smoothing operator smooth,.
AA AK by
smooth, (p) = (1 p)p + p1/K,
Vp Ap=As.
Now, we can show that o (smooth, ())) is j--isscchtzz. Denoting the smoothed approximation of De by Dt = o (smooth,, (E (o((xx)))) Lemma 16 Foster et al. (0118) shows that using 7t instead of D. worsens the regret bound only by an additional constant μm; hence our choice The last step of the approximated algorithm consists using Monte Carlo sampling to approximate the expectation by finite sum
ū: = = (smoothy
o+
M o(wi)) 1=1
m
where
wi iid. NOO,, (Ix:), ((x)) A710(xx))
7

---

Using Chernoff's 's inequality, we show below that Ye concentrates well to T/ which entails the following guarantee.
Proposition Let 8 > Officient-GAF, run with parameters À 32d'KR', 3 (log(K) ( / /2-
BR BR+11 1) m 2 and μ (log(//)/mm) satisfies with probability the regret bound
(0) S d'KB'R + K [log K) BR) log (1+ d'K (log( K) BR)
71
K
11
+
log
8
with computational cost Onn de + K2 K2mm). In particular, the choice m n log(n/6 18, yields
the regret bound (7) with probability 1 8 and a total computational time of order O 3 K2 n² log(n/8)).
Proof. We first prove the computational complexity upper-hound. At each iteration = =1, ....., n, the algorithm performs the following computations:
(i) Update A, since the rank of A, - Ar-1 is K, the inverse A," can be updated in 0(K operations.
(ii) Update 0241: by Theorem 4 of Jézéquel et al. (2020). this can be done in (log((n) + K²d
(iii) Compute Yt: to do so. must sample m times from Gaussian of dimension K. The cost is thus (mm?²).
Therefore, the overall time complexity of the algorithm is On + K²nm).
We now prove the corresponding regret bound. First, we define
Pt == smooth, ( Σm o (wi) and
Pr == Epp smooth, (Eg_P, (a(00
With this notation, Dt = a+ (ft) and Ttt (mr). Using that (p)) = for any p E ÅR yields for all ye E [K]
(ūr. vt) - log (o()))..) = log (a(a (pt)) - log(pr...)
where Pe.: denotes the i-th component of Pt. Similarly, E(Ur: v1) -og((rr.)) Therefore, fixing some E > O, we have
P((( E(ūt. v.) > o] -P log
Po.us Pt..
IP Pt.yy Pt.m. < ( 11)--11)t p)
Using that e 5 for & E (0. () together with the multiplicative Chernoff's bound (see e.g., Theorem 1.10.5 of Doerr 2020)), entails for all < 2
P(((Tr, va) (ir, we) > < PP.. < (1 (1-26) Pr.ul Se
222mmp -22 Se -e=emmp/K
(8)
where the last inequality is because smooth, (p); 2 p/K for all i E [K]. Taking
K log(n/o), we have
[e( vi) ((Te,
K log (3) S um
Furthermore, denoting P: EgnFr_ (T (fxx)) so that Pt smooth, (p:) and following
Lemma 16 Foster al. 2018), get
Pt.M De.y.
Pt.s
pr.m
(Te,, vc) E(Te.y)) yr) = log
log
smoothh, (Pt) = =log (1 (1- -M) + K
= =log
24(11 KP
S 2ps (10)
sa(1 KP....
Combining 9 and (10), and using union bound yields with probability at least 1 - 5
E ((je, wr) - ((Tr, yr) < "V
Jam log (7) + pr.
Optimizing μ (log(n/0)K//))//² and using Corollary concludes the proof.
8

---

Using Gaussian distribution improves significantly the computation time with respect to log-concave distribution as considered by Foottrr et al. (2018). Indeed, it allows to get exact and efficient samples from Pt-1 which leads to computation time of order O(n"). On the contrary, since it is not possible to draw an exact sample from a log-concave distribution, Foster et al. (2018) must resort to expensive random walks to approximately sample from it. Using the method from Bubeck et al. (2018), as suggested by Foster et al. (2018), leads to a (B [Bn + " computation time per iteration (see their Example 3 with the choices E = n and μ n ))
Note that our analysis shows a clean trade-off 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 good accuracy. This is partly because the lower- bound Pt. 2 J R 1/n in Inequality (8) may be very coarse for many t. If the Pt.y, were of order (2(1), one could choose m Onn²) instead of m = O(n"). Another possible explanation comes from the fact that, if A, 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 good approximation. We leave to future work the possibility to improve the complexity in favorable scenarios.
Comparison with Jézéquel et al. (2020) In the binary case, more efficient algorithm called AIOLI has been introduced in Jézéquel et al. (2020). The latter achieves a similar regret bound as GAF, while having a computational complexity of only (n + 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 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 0g is far from 0 (ler say 02 >> 0) either 3/2 = 1 and the curvature was advantageous or y -1 and 0e tends to the oracle 8 This intuition is a bit lost in the multiclass setting as several oracles are possible if ye * 1. On a more technical side, the analysis in inīéééquel et al. (2020) crucially relies on the relation 9t y/- -11 + n: (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.
5 Experiments
Although GAF is primarily theoretically motivated in a worst-case analysis, here we study its performance real data sets. We consider three datasets (vehicle, shuttle, and segmentation taken from LIBSVM Data and compare the performance of GAF with two well-used algorithms: Online Gradient Descent (OGD) (Zinkevich] 2003) and Online Newton Step (ONS) (Hazan et al.) [007). The algorithm of Foster et al. (2018) is not considered because of prohibitive computational complexity. Concerning the parameearameters the values suggested by the theory are generally too conservative. We thus choose the best ones in a grid for each algorithm (A, 8 E [0.01, 0.03, 0.1, 0.3, 1, 3, 10).
The averaged losses over time reported in Figure I 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 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 Hazan et al. 2014)
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
https: :/twws:://ww.... csie. ntu. wtt.:eedddddddeeeeeeee ht/p://a///bbbooool//aaaaatattaa
.ttll

---

10.
10f
101
10
10"
131
10
10'
10
10'
107
(a) Vehicle
(b) Shuttle
(c) Segment
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.
to Foster et al. (0188) (logarithmic dependence). It may be possible to improve it by using other surrogates than quadratics. The essential point would be prove an equivalent Lemma for those surrogates. The computational complexity of computing Equation 66 should also remain low. The computational complexity may also be improved. Like previous point, other surrogates could be used to make Equation (6) easier compute. Finally, we believe that GAF should casily be extended to kernels. One would need to adapt the analysis to depend on the effective dimension (Jézéquel et al.) 2019) of the RKHS instead of d. It would of interest to 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 the algorithm can be used to improve existing results for other losses such Huber loss.
References
Azoury, K. S. and Warmuth, M. K. (2001). Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Leurning, 43(3):211-246.
Bach, al. (2010). Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384-414.
Bubeck, S., Eldan, R., and Lehec, J. (2018). Sampling from log-concave distribution with projected langevin monte carlo. Discrete Computational Geomeiry, 59(4)7757-783
Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
Doerr, B. (2020). Probabilistic tools for the analysis of randomized optimizatioon heuristics. In Theory of Evolutionary Computation, pages 1-87. Springer.
Foster, D. J., Kale, S., Luo, H., Mohri, M., and Sridharan, (2018). Logistic regression: The importance of being improper. arXiv preprint arXiv: 1xXiv:/803.09344
Hazan, E., Agarwal, A., and Kale, S. (2007). Logarithmic regret algorithms for online convex optimization. Machine Learning, 1692-1))169-19.
Hazan, E. al. (2016). Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325.
Hazan, F.,, Koren, T., and Levy, K. Y. (2014). Logistic regression: Tight bounds for stochastic and online optimization. In Conference on Learning Theory, pages 197-209. PMLR.
Helmbold, D. P. and Warmuth, M. K. (1995). weak learning. Journal of Computer and System Sciences, 50(3)5551-573.
Jézéquel, R., Gaillard, P., and Rudi, A. (2019). Efficient online learning with kernels for adversarial large scale problems. arXiv preprint arXiv:1902.09911
Jézéquel, R., Gaillard, P., Rudi, A. (2020). Efficient improper learning for online logistic regression, In Conference Learning Theory, pages 2085-2108. PMLR.
10

---

Kakade, S. and Ng, A. Y. (2008). Online bounds for bayesian algorithms.
Marteau-Ferey, U., Ostrovskii, D., Bach, F,, and Rudi, A. (2019). Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance. arXiv preprint arXiv:1902.03046.
Mourtada, J. and Gaiffas, S. (2019). An improper estimator with optimal excess risk in misspecified density estimation and logistic regression. arXiv preprint arXiv:
Ostrovskii, D. M., Bach, F., et al. (2021). Finite-sample analysis of m-estimators using self- concordance. Electronic Journal of Statistics, 15(1):326-391
Van Erven, T., Grunwald, P., Mchta, N. A., Reid, M., Williamson, R., et al. (2015). Fast rates in statistical and online learning.
Vovk, V. (2001). Competitive on-line statisties. International Statistical Review, 69(2):113-248
Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936.


Reviews:
[{"review_id": "fOTPlNI5aPZ", "reviewer": "Reviewer_uuaZ", "summary": "In this paper, the authors consider some online prediction/convex optimization problems, where it is assumed that the losses satisfy a mixability condition, as well as additional assumptions inspired by logistic regression.\nWhile these problems can be addressed by Vovk's aggregating algorithm, the resulting procedure would be computationally expensive and involved.\nEfficient and more direct procedures have been proposed for least-squares regression by Vovk and Azoury-Warmuth (VAW), and more recently for (binary) logistic regression by Mourtada and Gaiffas (MG) and Jezequel, Gaillard and Rudi (JGR).\nThe present paper sets out to extend these constructions; the considered losses are assumed to be mixable, and satisfy conditions such as smoothness and a (weakened) self-concordance satisfied by logistic regression (lines 215-223).\nA procedure for this setting, called Gaussian aggregation forecaster (GAF), is proposed.\n\nThe main outcomes are the following:\n- In Sec 4.1, for linear regression the authors recover the VAW procedure and its guarantee. [However, there seems to be a possible issue with this derivation.]\n- In Sec 4.2, the authors consider multi-class logistic regression, and obtain a procedure and guarantee for this problem. These extend those of MG and JGR for binary logistic regression to the multi-class setting. They also go beyond what can be achieved by procedures such as online gradient descent, online Newton step or follow-the-regularized-leader. This is the main result of this work.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "At present, I do not have a particularly strong recommendation for this submission.\n\nOn the one hand, the paper is overall very clear, and fairly well-written (apart from some small typos). While I did not check the detailed proofs in the supplementary material, the provided sketch in the main text appears to be correct, the main arguments are the right ones (similar to prior work), and the bounds looks the way they should, so I would say that the paper seems correct.\n\nOn the other hand, there are two main possible limitations:\n- It seems that as stated, the derivation for square loss may be incorrect. The reason for this is that the predictions of linear functions need not be bounded by the range Y of outputs y_t's. This can compromise the application of mixability, since the square loss is only mixable on bounded intervals (so both the outputs and prediction need to be bounded). One could in principle fix this by clipping the predictions of linear functions before aggregating, but then the resulting might not have a closed-form expression (?) and would not in any case correspond to VAW. I think this part should be fixed or adapted/removed.\n- At a high level, the procedure, assumptions and analysis seem to essentially \"abstract\" those of JGR, extending them to general losses satisfying the conditions that are used in the analysis. The main extension from the works of MG and JGR on binary logistic regression is to handle the multi-class setting; while this is a practically relevant extension, it might perhaps also be a slightly limited one. \n\nThis being said, I would be happy to increase my score if the authors could: (1) describe a possible fix for the square loss case (or correct me if I got something wrong); and/or (2) point out to specific insights or difficulties in their setting, beyond those that appear in binary logistic regression. \n\n---\nMinor comments\n\n- In the abstract and line 44, the provided regret bounds depend on sample size n and parameter norm B, but the dependence on dimension d is left implicit; it would perhaps be better to indicate it (e.g., O(d log(Bn)) instead of O(log(Bn))), as correctly done in other parts of the text.\n- In addition to Foster et al., bounds for logistic regression through Vovk's aggregation algorithm were also obtained by Kakade and Ng \"Online Bounds for Bayesian Algorithms\".\n- Line 112: \"there exists\"\n- Line 125: \"the most original assumptions\"\n- On a minor note: the optimal mixability constant for square loss is obtained by combining predictions in a non-linear way; if one uses the linear/convex combination (which typically leads to a closed-form expression), then the resulting constant is 4 times larger. This makes little difference, but it may be worth checking that the correct constant is used--this may already be the case, but please verify it.\n\n----\nUpdate after authors' reply: \nThank you for the clarification about square loss. This addresses my concern about the boundedness issue, which turns out to be ill-funded. I have updated my evaluation to account for this.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None, as far as I can tell", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cEao0XLARvK", "reviewer": "Reviewer_TSZ4", "summary": "This paper considers the online convex optimization setting with mixable losses. The exponential weights algorithm is known to have constant regret with mixable losses, but it is also known to have prohibitively high running time for certain mixable losses. A mixable loss function of interest is the logistic loss used in logistic regression, for which faster algorithms such as Online Newton Step (ONS) suffer a double exponentially larger regret bound compared to exponential weights.\n\nAs a solution the authors propose a mix between ONS and exponential weights called GAF. To update, the algorithm computes a quadratic surrogate loss akin to the surrogate loss used in ONS, but uses the actual hessian rather than an approximation to the hessian to compute the surrogate loss. Another interesting trick that the authors use is that the point around which the quadratic surrogate loss is defined: it is the minimizer of the $l_2$ regularization plus the loss of the previous round and the surrogate losses of all rounds preceding the previous round.  The predictions of the algorithms are the same predictions that would be used for exponential weights. While for arbitrary priors this would pose a computational problem, the algorithm uses a gaussian prior. As is observed in prior work, with a gaussian prior and quadratic losses the posterior of exponential weights is also a gaussian. This allows the authors to devise more efficient predictions. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem considered in this paper is an important problem and the proposed solution is elegant. While the additional assumptions over the mixability assumption appear to be tailored to the logistic loss, I think that the ideas behind the algorithm can be used for other problems as well. \n\nThe paper is well written. In particular, the ideas behind the algorithm and its analysis are well explained. \n\nAnother natural approach to the problem would be to extend the algorithm of Jézéquil et. al. (2020) to $K >2$, especially since it appears to be significantly faster in $K = 2$. I suppose that the authors have at least considered this approach and if so I would like to have an idea on the difficulties in extending their approach.\n\nAs a final comment, $\\beta$ is used for both exp-concavity and in (A3). While it is stated that these are different at a glance one might think they are the same, so I recommend changing the notation. \n\n\nminor comments\n- I think there is a typo in the definition of $\\tilde{L}_t$ in line 406. Should it not be $+\\lambda ||\\theta||_2^2$?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "NwgKvUXPjL", "reviewer": "Reviewer_uznP", "summary": "With online learning for multiclass logistic regression, its regret has a trade-off against the computational cost. For example, ONS can be computed in $O(n)$ time ($n$: number of instances) while the regret is $O(e^B \\log n)$: exponentially increased against the radius of regret computation $B$. [Foster 2018] can provide the regret $O(\\log(Bn))$ but requires $O(n^{37})$ time.\nThe proposed method can provide another trade-off between them, and achieved the regret $O(B^2 + B\\log n)$ with the computational cost of $O(n^4)$. This is much faster than [Foster 2018] with acceptable computational cost.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It seems valuable that the paper found a new trade-off between the regret and the computational cost, that can improve conventional methods. Compared to OGD and ONS, the proposed method GAF improved the regret at the expense of increase of the computational cost. Compared to [Foster 2018], GAF greatly improved the computational cost at the expense of small increase of the regret. In addition, the paper experimentally showed regrets compared to OGD and ONS; it showed that GAF can provide smaller regret for many cases.\n\nFor this result, the reviewer considers that it is more useful to discuss the real-life usage. For example, how about experimenting GAF with various $m$? In case the computational cost of $O(n^4)$ is unacceptable, we may reduce $m$ to reduce the cost (at the expense of the regret). In such cases, we may be also interested in how the regret becomes large.\n\nQuestions and comments:\n\n-   Overall:\n    -   What is essentially difficult if we consider the multiclass logistic regression instead of the binary logistic regression? As far as I read Table 1, the difficulty is not found by $K$ between 2 and 3. Is it a difficulty in the algorithm?\n-   Section 3, first paragraph:\n    -   The paper states that we have three hyperparameters $\\lambda$, $\\alpha$ and $\\beta$. However, it seems that $\\lambda$ and $\\beta$ are tuning hyperparameters while $\\alpha$ is a hyperparameter automatically determined from $\\ell$. It is good to clarify the difference.\n-   Section 3, Expression (4), definition of $\\tilde{P}_{t-1}(\\theta)$:\n    -   Doesn't $\\theta$ in the denominator of the right hand depend on $\\theta$ in the left hand? If so, consider using a different variable name.\n-   Section 4.1, (A4):\n    -   It seems that the definition of operator $\\leq$ for matrices is not provided. Is it defined by the positive definiteness?\n-   Section 5:\n    -   Since it is an online setting (i.e., we cannot see all data values beforehand), how to choose the hyperparameters seems to be a difficult problem and thus it should be clarified. For example, it choosed hyperparameters by first $n^\\prime$ instances, or it updated hyperparameters whenever retrieving $n^\\prime$ instances.\n    -   According to the source code, it seems that the hyperparameters are chosen beforehand. If they are chosen by whole data, then it does not reflect the online setting and therefore experimental results may not be appropriate.\n-   Section 5:\n    -   Does the following experimental setups match: those GAF did not work well experimentally, and those GAF is not theoretically advantageous compared to OGD and ONS?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper seems to state adequately the impact and the limitation. It provided an essential theoretical improvement, while it is not always reflected for real data by an experiment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Ha1FIKuSGsn", "reviewer": "Reviewer_4Prw", "summary": "The authors propose a new computationally efficient algorithm for multi-class logistic regression. The propose method is based on a tight quadratic approximation of the loss function (extended from Lemma 5 of Jezequel et al.) and utilizing the mixability of the logistic loss (and other properties) to compute the prediction like AA of vovk. They show that their regret bound does not have the infamous exponential constant while being computationally efficient (n^4).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\nOriginality 4/5: using the quadratic approximation to compute AA prediction fast is novel.\n\nQuality 4/5:\n\nClarity 4/5: \n\nSignificance 4/5: performing online logistic regression with statistical & computational efficiency is of great interest in theory and practice.\n\nThe paper is very clear about the contribution and it is concise. The proof of the quadratic lower bound (Lemma 4) seems much simlper than then one from Jezequel et al. The solution is novel. While $n^4$ time complexity would not belong to a practical algorithm, I believe it achieves an important mildstone.\n\nA question: What would be the difficulty of extending Jezequel et al. for the multi-class case? We can use Lemma 4 and perform similar improper learning, right?\n\nAnother question:  Q: what's the importance of using the actual loss function for the last iterate $t-1$ when computing the estimator?\n\n[etc]\n\n* L40 $\\Phi(x)$: did you define this before L40?\n* L178: was $L_n(\\theta)$ defined before?\n* L178: \"$L_t(\\theta) \\ge \\tilde L_t(\\theta)$ \": I think $L_t(\\theta)$ here should be $L_t(\\theta) + \\lambda \\|\\theta\\|_2^2$. \n* L212: it would be easier to follow if the range of $i$ and $j$ is provided here.\n\n[after rebuttal]\nThanks for explaining why Jezequel et al.'s technique is not easily transferred. I am fully satisfied with the rebuttal given by the authors. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors did not provide it, but I doubt there is a negative societal impact from this.", "review_text": "", "extra_scores": {"ethical_concerns": "no concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes significant progress on the problem of computationally efficiently achieving logarithmic regret for multi-class logistic regression. The closest comparator work of Foster et al. (2008) achieves regret $O(d K \log (B n))$ but at the prohibitive $O(n^{37})$ total cost. In contrast, ignoring other factors, the present paper devises the algorithm Efficient-GAF, which obtains regret $O(d K (B^2 + (\log(K) + B) \log(n))$ at a total runtime that is $O(n^4)$, ignoring other factors. Although the regret of the present work is exponentially higher in $B$ relative to (Foster et al., 2008), the regret is also exponentially lower than the $O(e^B \log n)$ regret achieved by Online Newton Step, while still keeping the runtime reasonable. Although Efficient-GAF's $O(n^4)$ runtime is not yet practical by some standards, this is still immense progress towards the goal of a practical runtime.

This work contains several techniques that appear to be original and also could see use in future works. Also, as the authors mentioned in the discussion phase, there is a fundamental roadblock in trying to generalize the results of Jézéquel, Gaillard, and Rudi (COLT 2020), hereafter referred to as (JGR), to the multi-class setting, and the reviewers agreed with the authors' assessment here. Given that all four reviewers asked whether such a generalization is possible, I would like to suggest that the authors, either in the paper, or in an appendix, try to mention the issue with extending JGR to the multi-class setting. Future readers may wonder about this question otherwise.

One side note: For clean comparison to results in the binary logistic regression setting (such as the work of JGR), it is worth mentioning that both of the results of Foster et al. (2008) and the present paper hold with high probability and the runtime dependence is logarithmic in $1/\delta$, whereas the work of JGR gives guarantees that hold deterministically. This was not really apparent until far into the paper. Therefore, it seems that another question is whether something close to practical efficiency can be achieved deterministically in the multi-class case.

In summary, this is a strong paper that I expect to be influential, and it deserves to be accepted at NeurIPS 2021.
Decision: Accept (Spotlight)