A Regret-Variance Trade-Off in Online Learning
Authors: Dirk van der Hoeven
Nikita Zhivotovskiy
Nicolò Cesa-Bianchi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online learning
statistical learning
corrupted feedback
selective sampling
abstention

Abstract: We consider prediction with expert advice for strongly convex and bounded losses, and investigate trade-offs between regret and ``variance'' (i.e., squared difference of learner's predictions and best expert predictions).
With $K$ experts, the Exponentially Weighted Average (EWA) algorithm is known to achieve $O(\log K)$ regret.
We prove that a variant of EWA either achieves a \textsl{negative} regret (i.e., the algorithm outperforms the best expert), or guarantees a $O(\log K)$ bound on \textsl{both} variance and regret.
Building on this result, we show several examples of how variance of predictions can be exploited in learning.
In the online to batch analysis, we show that a large empirical variance allows to stop the online to batch conversion early and outperform the risk of the best predictor in the class. We also recover the optimal rate of model selection aggregation when we do not consider early stopping.
In online prediction with corrupted losses, we show that the effect of corruption on the regret can be compensated by a large variance.
In online selective sampling, we design an algorithm that samples less when the variance is large, while guaranteeing the optimal regret bound in expectation.
In online learning with abstention, we use a similar term as the variance to derive the first high-probability $O(\log K)$ regret bound in this setting.
Finally, we extend our results to the setting of online linear regression.

A Regret- Variance Trade-Off in Online Learning
Dirk van der Hoeven di hirredirrvanderroeeenn com Dept. of Computer Science Università degli Studi Milano, Italy
Nikita Zhivotovskiy zhi shivotooskkiybbekkeeeyy
Dept. of Statistics University of California, Berkeley
Nicolò Cesa-Bianchi
nicolo. cesa-bianchi @unimi. it Dept. of Computer Science Università degli Studi di Milano, Italy
Abstract
We consider prediction with expert advice for strongly convex and bounded losses, and investigate trade-offs between regret and "variance" (i.e., squared difference learner's predictions and best expert predictions). With K experts, the Exponen- tially Weighted Average (EWA) algorithm known to achieve Ollog K)) regret. We prove that variant of EWA either achieves negative regret (i.e., the algorithm outperforms the best expert), or guarantees a O(log K") bound on both variance this result, show several examples of how variance
and regret. Building of predictions can be exploited in learning. In the online to batch analysis, we show that a large empirical variance allows stop the online to batch conversion early and outperform the risk of the best predictor in the class. We also recover the optimal rate of model selection aggregation when we do not consider early stopping. In online prediction with corrupted losses, we show that the effect of corruption the regret can be compensated by a large variance. In online selective sampling, we design an algorithm that samples less when the variance is large, while guaranteeing the optimal regret bound in expectation. In online learning with abstention, we use a similar term as the variance to derive the first high-probabilin (log K)) regret bound in this setting. Finally, we extend our results the setting of online linear regression.
Introduction
In the online learning protocol, the learner interacts with an unknown environment in sequence of rounds. In each round / 1, 2, T the learner makes prediction Dt E [- M and suffers loss (Tre), where ε₁, f2 ... a sequence differentiable loss functions unknown to the learner. The goal is to achieve small regret Ry. defined by R = ΣT1 (Le(i) (x())) where ył are the predictions of some reference forecaster. We consider two special cases of online learning. In prediction with expert advice, the learner receives the predictions yı (l),... Mx (f) E [ ]M] of K experts at the beginning of each round The learer then predicts with a convex combination
Dt = EK (i)) of the experts' predictions, where P: = (p: Pr (K) is probability distribution over experts updated after each round. The goal in this setting to have small regret with respect to the predictions yf = ye(i*) of any fixed expert i* online linear regression, the learner has access to a feature vector 2, E Rdd at each round. This used compute predictions (w,, Zt), where
Rd is parameter vector to be updated at the end of the round. The goal
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is to have small regret with respect to the predictions vi (s)) of any fixed linear forecaster t E IRd such that ||ul22 S D and 1y4 S 2 M for all t.
In both settings, assume that the losses E are u-strongly convex, which is to say that there exists a > such that for all y, x E - M, M).
(vv) ((x) - x)
2 1( (x= y)²
H
t..,,,
where we write e, to denote the derivative of 4. Without loss of generality, throughout the paper we assume that μ S 2.
A typical example of strongly convex loss is the squared loss (x(w) (y y²)²² with μe = 2. While standard online learning algorithms, such as, for example, Exponentially Weighted Average (EWA) [Vovk, 1990, Littlestone and Warmuth, 1994], are directly applied to the (mixable) losses &,, we take a different approach. Our algorithms provide bounds on the linearized regret Ry of the form
T R₂ = Σ U - vi Σ Cr + Br + 1
T
(J Σ 1=1
v1)²
(2)
for some 77 (0, H| to be chosen freely by the learner and where H, Cr. Br Ore problem-specific parameters. In the expert setting, several algorithms provide such a guarantee: Squint [Koolen and Van Erven, 2015], Adapt-MI-Prod [Gaillard et al., 2014], BOA [Wintenberger, 2017], Squint+C and Squint+L. [Mhammedi et al., 2019]. In online linear regression, the MetaGrad algorithm [Van Erven al., 2021] and its variants by Mhammedi al. [2019], Wang et al. [2020], Chen al. [2021] satisfy bounds like (2). Although in both settings the aforementioned algorithms achieve the optimal tuning of 7 in (2) without any preliminary information, our applications do not require this tuning property. As a consequence, the algorithms we derive in Section 3 are simpler and have slightly better guarantees. More importantly, unlike the aforementioned algorithms, we focus on exploiting the curvature of the loss. In particular, by combining equations (1) and (2), we obtain the following lemma, which features the central inequality of our work.
Lemma 1. Consider a sequence .,...., ly of u-strongly convex differentiable losses. Suppose that predictions In guarantee the second-order bound (2). Then
Rr S 1
CT Br
1 2
1
V 1=1
v7)²
Next, we show prototypical example of the bounds derive in the rest of this work. Example 1. Consider the expert setting with the squared loss, Ee(y) = (y - 3t)², where E [-1, 1] for all 2 1. Then the predictions Ht of our algorithm satisfy
1 Σ T -22)² 2
Rr S 32log(K))K
Even though (3) seems relatively inconsequential, exploit the negative variance term in several applications. A straightforward implication is that (3) recovers the usual constant regret bound Rr (K)). More interestingly, however: if we attain the worst-case performance Olog (K)). then the variance is small and bounded by O(log(K) ()), )) if the variance is large enough, then the regret becomes negative. For the role of negative variance terms in the analysis of statistical and online learning, we refer to Section 2.
Remark. Negative quadratic terms similar to the one Lemma I appear in online convex opti- mization, for example in the analysis of the online gradient descent [Hazan, 2016, Theorem 3.3]. However, as far as we are aware, in online convex optimization the algorithms are not tuned obtain a negative term in the regret bounds. In this paper we argue that for online regression, and especially for prediction with expert advice, setting 1) < /1/2 in Lemma I and thus obtaining a negative term can be powerful tool, which plays a central role in all of our applications. In prediction with expert advice the standard approach to exploit the curvature of the loss is through mixability rather than through the negative quadratic terms. In particular, we show that the regret bound in (3) cannot be achieved by EWA with a fixed learning rate, despite the fact that constant regret is achievable by this algorithm via mixability.

---

Proposition 1 (Informal). Consider the setup of online prediction with expert advice and bounded strongly convex losses. The bound (3) cannot be achieved by the standard EWA algorithm.
For the sake of presentation, defer the formal description of this result to Section 3.1. The proof of Proposition is motivated by a result of Audibert [2007] on the sub-optimality of online to batch converted EWA in deviation.
Contributions and Outline. In Section 4, we show our first three applications of Lemma 1 in the framework of statistical learning. In the expert setting, we show that online batch conversion may be stopped early if the empirical variance of our predictions is sufficiently large. In particular, in high-variance regimes we may stop early because the excess risk bound is negative with high probability, and when the variance is small, we recover the optimal excess risk bound up to log log T factor. By exploiting the negative variance term again, we show an optimal nigh-probabilite excess risk bound for online to batch conversion of algorithms that satisfy (2). The optimal high-probability excess risk bound (called the optimal rate of model selection aggregation) was previously known to be achieved by several estimators appearing in [Audibert, 2007, Lecué and Mendelson, 2009, Lecué and Rigollet, 2014] whose analyses are specific to the statistical learning setup. Our result can also be seen simplification and strengthening of result by Wintenberger [2017]. We also show prob-bbbbbbblitty excess risk bound for online to batch conversion of an online regression algorithm in the bounded setup, which is say that both the feature vectors and derivatives of the losses bounded. It was previously shown by Mourtada et al. [2021] that online to batch converted versions of the optimal Vovk-Azoury- Warmuth forecaster [Vovk, 2001, Azoury and Warmuth, 2001] have constant excess risk with constant probability.
In Section 5, we use the negative variance term counteract corrupted feedback in online learning. Our result complements previous results where losses are assumed to be stochastic and corrupted by an adversary see, e.g., Lykouris et al. [2018], Zimmert and Seldin [2021], Amir et al. [2020], Ito [2021]. In Section 6 we consider the selective sampling setting [Atlas et al., 1989]. where the learner's goal is to control regret while saving on the number of time the current loss is observed. We show that the optimal bound can be recovered while only observing fraction of all losses if losses observed proportionally to the cumulative variance. Finally, in Section 7 we discuss how our ideas are not limited to online learning with strongly convex losses, but may also be applied to online learning with abstention and online multiclass classification. All bounds in the main text with suppressed constants have detailed statements in the appendix. Before discussing our applications, we introduce some notation and discuss the related work. The algorithms that we use derive most of our results are introduced in Section 3.
Notation. We use the standard O()) to suppress constants and use Ö(-) to suppress constants and (fg(tr)- We use log(-) to denote the logarithm with base e. The symbol L[A] denotes the indicator the event A. For an integer K we denote [K] = {l,..., KK.. We use p(i) x g() to [Ek=
denote p(1) = g(i)/ /
and 0yE(y. Y) denote the derivative of with respect to y. The symbol / denotes the identity matrix whose dimensions are clear from the context. For set of Xr-1 we write [ =
random variables Y, ",,
2 Related work
Online learning with losses with curvature. For a thorough introduction to online learning, we refer the reader to [Cesa-Bianchi Bianchi and Lugosi, 2006, Hazan, 2016, Orabona, 2019]. Strongly convex losses are a special case of mixable losses. With mixable losses, EWA on a finite set of experts achieves Olog( ()) regret- see, e.g., [Cesa-Bianchi and Lugosi, 2006, Mhammedi and Williamson, 2018). Mhammedi and Williamson [2018) observe that-in some cases-regee may be negative for mixable losses, but they do not explore this topic further.
The role of the negative terms due to curvature in online and statistical learning. Although bounds of the form (3) are not explicitly present in the literature, the appearance of negative terms is common when proving fast rates in statistical learning with squared loss. In particular, the empirical star algorithm of Audibert [2007]-as well as other aggregation algorithms [Lecué and Mendelson, 2009, Lecué and Rigollet, 2014, Wintenberger, 2017)-exploi the curvature of the loss
3

---

Algorithm 1: An algorithm for prediction with expert advice
Input o E (0, (0.2).10 M > 0:
Initialize 7 1/2 P1 (t)
K for all i;
for / = ,,...,7 7 do
Receive expert predictions ( (c(K) Predict Dr- - Σ (1)
Receive yt and Kig
Set (t) >7(( (i) Te )9t ke-1(7((x(1) )))))
Set (1) x exp( -Ke Ei=1 (1))
through the negative term which compensates the variance term. We also refer to some recent statistical learning results whose analysis is based on the same idea [Mendelson, 2019, Bousquet and Zhivotovskiy, 2021, Puchkin and Zhivotovskiy, 2022, Saad and Blanchard, 2021]. Similarly, in the context of online learning the negative quadratic term appears in Rakhlin and Sridharan [2014], where the so-called sequential offset Rademacher complexity is studied. Van Erven al. [2021] also obtain a bound that is very similar to the bound in Lemma (specifically in the proof of their Theorem 1), but they choose 7) to match the negative term in their bound. Importantly, in these papers the role of the negative term is only to get the fast rate by compensating the variance term. In contrast, in our case the negative variance terms also appear in the final regret bound and play their role in applications.
Suboptimality of EWA for prediction with expert advice. In the setup of prediction with expert advice, the classical Exponentially Weighted Average (EWA) algorithm [Vovk, 1990, Littlestone and Warmuth, 1994] is known to give constant regret in the case of strongly convex losses. However, despite being optimal in this setting, this algorithm has several known drawbacks. In the case of general losses, EWA does not deliver the second-order bound (2). As a result, unlike more advanced algorithms such as Squint [Koolen and Van Erven, 2015], EWA with a fixed learning rate (and even a decreasing learning rate) cannot adapt to certain benign stochastic environments where, for example, the Bernstein assumption holds [Mourtada and Gaiffas, 2019]. The second source of suboptimality comes from online to batch conversions in the strongly convex case. Although in the statistical setting EWA performs optimally in expectation, does not do so with high probability [Audibert, 2007]. As matter of fact, it will be clear from our analysis that this is related to the fact that EWA does not satisfy bound of the form (3) (see Theorem 1). This problem is one of the motivations behind the work of Wintenberger [2017].
Exploiting negative regret. The possibility of getting negative excess risk has been recently explicitly exploited by Puchkin and Zhivotovskiy [2022, see their Algorithm 3.3 and Theorem 3.4] in the setup of active learning with abstentions. In the context of online to batch conversion of online learning algorithms, a similar idea is exploited in Section 4.1. Moreover, our selective sampling results in Section 6 are of the same flavor.
3 Our Algorithms
In the following, 91 ........... are real numbers bounded interval. However, in most applications we use 9t (.c)). The algorithms in this section are simplified versions of algorithms in the literature. Namely, in Section 3.1 we present a simplified version of Squint [Koolen and Van Erven, 2015] and in Section 3.2 we present simplified version of MetaGrad [Van Erven et al., 2021]. The simplifications lie the tuning the learning rate. Squint and MetaGrad optimize the learning rate online a small cost, whereas in our applications we only need fixed learning rate that is known in advance, in which case we do not pay the small cost for optimizing the learning rate. The proofs of the results in this section are postponed to Appendix A.

---

Algorithm 2: An algorithm for online linear regression
Input v) > 0, > 0, G > 0, Z > 0:
Initialize 84. w1 = 0, and Σ1 0
for t I..... do
Receive 2;
Set W; = =
(w (w,, xz)) S ]}
Set w, = argmin weW (w wx Ln (w -w,)
Predict Dr = (t)
Receive Gt. and Kit
Set 7attt
Set - = 1i/211z + Lt
Set W1+11 We 24 Ex+1
3.1 A Simple Algorithm for Prediction with Expert Advice
Algorithm is a simplified version of Squint [Koolen and Van Erven, 2015]. The K2 parameter is relevant only to the selective sampling setting, where it used control the range of loss estimates. In all other settings we set update the algorithm. This is due technicality in the analysis of the algorithm, where (4-1
for all 1. Note that in round /. both Ky and Kz-1 are used to
term appears and we want to use the inequality x - x² < log(1 + x) for [x] S (specifically in equation (7)). The regret bound of Algorithm can be found in Lemma
Lemma 2. For all g1..... gT E [-M, M] and Ko = 61 2 K2.... 2 AT such that Re E [0,1], the predictions Us of Algorithm I run with input M and (0, 2 satisfy
T
T
Σ
( (e())))
+
Σ
kr-1 1 (01-)))
Kt
KTT)
t=1
provided max; (vc(1) vts S M for all 1 21
As an immediate corollary of Lemma 2 and Lemma we have the following regret bound.
Corollary 1. Fix arbitrary sequence f,,..., lT of p-strongly convex differentiable losses such that maxe [e] S M. Provided that max; lyī yr (i) I M for all t 2 1, the predictions Te of Algorithm I run with inputs M and [0, 2). for all and feedbuck gr = (We), satisfy
RT S lolog(K)
(5 1)
Σ
As an example, let us consider the squared loss, which is 2-strongly convex. In the setup of Example 1, since ( = 2 (Tr - yt)l < 4, Algorithm with gr = (ūt) and rj = 2 gives us the regret bound claimed in Example 1, namely Rr <. 32 log(K) - D (#t 2 Our next result is a formal version of Proposition saying that the above regret bound cannot be achieved by the standard EWA algorithm. For standard notation and explicit details this algorithm
refer Appendix E.
and (2) = 1 1 all f 2 1. Let EWAA be the EWA predictions. There is sequence U1, 1/2 ... such that yc [0. 1). t 2 1 and, for
Theorem 1. Consider the squared loss and two experts ye (1)
large enough T, the regret of EWA with = 2 satisfies - 12 log < Rr I 2 log 2 and, at the same time,
T
EWA
-22²2 T/2.
3.2 A Simple Algorithm for Online Regression
In the following we use (u) = (u. zz).. We prove a regret bound for Algorithm 2, which is a the algorithm
simplified version of MetaGrad [Van Erven et al., 2021]. The role of the parameter is to ensure the predictions W/ are bounded, which will be important in the statistical learning setting Section 4. Similarly to Algorithm 1, the Ky parameter is only used in the selective sampling setting.
5

---

Lemma 3. For all g1.................. .1 E I and M1 2 ... - E (0, 11. the predictions T. of Algorithm 2 run with inputs 1i 0, D2, G N max, (et and 0
T Σ C - (c(u))g
2KT
dG²
log
[1+D2r
max LL,...,?
|
T
d
+
G² 21
n
Σ
T Ke - vo(())²
for any 21,-.-, 2T TR. and for any Wr Wr =i=ni= kw,, 224) S 7 such that ||aa|22 D. Example 2. Consider the setup of Example and suppose that max, ||xelle, ||aal/2 S 1 and M = 1. We have that 16, (Tx) = 12( - y/t] I and thus, by Lemma 3, an appropriately taned Algorithm
with gr E, (De) satisfies (2) with Cr 8 + 8d (1 n/2 () and By- O. Thus, by Lemma 1,
setting 1j = 1/2
2 gives us
Rr S 16+ 16d 16d (1 T 1 vo(()))
Statistical Learning
We discuss an application of our general results in the context of statistical learning where we are interested in the generalization of estimators to unseen samples. A tool often used in converting online learning algorithms to the statistical learning setting online to batch conversion [Cesa-Bianchi Bianchi et al., 2004]. Let us recall the setup.
Assume that we are given a family F of real-valued functions defined the instance space X. We observe T i.i.d. observations (X,, Y.), distributed according to some unknown distribution P on X' x R. Given the loss function f R - R, define the risk R(f) of f X + R as R(f) = E ((f(),, Y), where the expectation is taken with respect to the joint distribution of X and Y. We are interested in bounding the excess risk R(f) inf R(J), where î is constructed
JEF
based on the sample (Xe, Yo)_ Assume that there is a sequence of predictors fi..... Fr trained in an online manner using (X,, Ti)Tm, (that is, fr depends on (X,, ())==) such that almost surely S RT, where Ht is non-random. In this case, a standard online to batch conversion approach gives an in-expectation excess risk bound E R. ( Ei inf R(f) < R/ for any loss convex in its first argument and where the expectation is taken with JEF
Ei. (elF((X.),,, e() (
respect to the learning sample (X,, Yo) However, getting a high-probability version of this result is a known challenge if one wants to get the fast rate O (+). A standard way of proving a high-probabillity result is to apply Freedman's 's inequality for martingales [Kakade and Tewari, 2008]
VT For example, Audibert [2007] showed that this is the case one wants to prove high-probability excess risk bounds based on EWA. A way to handle the variance term in Freedman's 's inequality is by exploiting the Bernstein assumption as in Kakade and Tewari [2008]. Unfortunately, this assumption is not necessarily satisfied by the stochastic environments we are considering. The main idea in this section is use the negative term from Lemma to cancel out this variance term appearing due to Freedman's 's inequality'. We use the following notation when applying the online algorithms in the statistical setting: le(-) E(,, Y)) and ye(5) = (X.))
that leads to variance term scaling as O
4.1 Statistical Learning: Model Selection Aggregation
In this section, we discuss the application of our results to the model selection (MS) aggregation. This setup was introduced by Nemirovski [2000] and further studied by Tsybakov [2003] and by Audibert [2007]. Lecué and Mendelson [2009], Lecué and Rigollet [2014], Wintenberger [2017], Mourtada et al. [2021] among other works. We introduce some notation. Assume that we are given a finite dictionary F = (fi...., fK of real-valued functions defined on the instance space X.. We observe i...d. observations (X,, YOT distributed according to some unknown distribution P on X x IR.
We remark that Wintenberger [2017] uses a similar but technically more involved idea to compensate the variance of predictions using the term appearing because of the curvature of the loss.

---

Algorithm 3: Early Stopping online to batch for Model Selection Aggregation
Input T, M, 7), stopping threshold S
Initialize 5 = 0, provide 1), and M as input for Algorithm 1;
while < T and S > &/2 minnge Σi= (Tt {(x do
Receive X, and send fi())), ..... (Xe) ) as expert predictions to Algorithm
Receive p. and Øt Σ f:( from Algorithm
Predict 71 and receive &
Send 9t (,(0)) and Ri to Algorithm
Set S = S-1
Output f = 3
Given the loss function 8: R R, define the risk R(f) of Ras R(f) =()))
where the expectation is taken with respect to the joint distribution of X and Y. In the model selection aggregation, one is interested in constructing an estimator f based on the random sample (X, Y)) such that, with probability at least 5,
R(F) min R(F) = [oog(H ()) + log(1/0) JEF
(4)
T
under appropriate boundedness and curvature assumptions on the loss function f. Analogously to Tsybakov [2003], the bound of the form (4) will be called the optimal rate of aggregation. We make use of a variant of online to batch conversion procedure early if the empirical variance of predictions is sufficiently large. We sketch the idea. Let S be the number of samples we have used before we terminated the procedure. We use Algorithm I as our aggregation procedure and use f= Ei= Ei) R(F) S 3 D le (ΣK- ((().
bessa-Bianchi et al., 2004] where we stop the
By Jensen's 's inequality we have To motivate stopping early, observe that if the empirical variance in Lemma is sufficiently large, we may conclude that the excess risk is negative and we have outperformed the best E F. The result can be found in Theorem 2 below, whose proof is implied by Theorem 8 in Appendix B.
Theorem 2. Suppose that for all f E F [f(X) S almost surely, that (0gE(y, Y)1 S 1 almost surely for all y such that lul S 3. and that & is p-stroonly convex in its first argument. Then, with probability at least - 5, Algorithm 3 with input parameters T, S = 0 (o)((K))o(loo(TT))
7) g. and M = satisfies
mminser R(f)
ifS if T,
B(
minjer R(f) + +0
log(()) (lgglg))))
uI
where S is the number of steps of Algorithm 3.
When Algorithm 3 terminates step S T, we recover the optimal high probability bound for model selection aggregation (4) up to an additive log log T term. However, when S = our bound tells
us slightly more, because know that for all t' < minser Et (ot f(x))) O(log K log log T') which means that on the sequence (Xe, Yo our predictions are essentially following the prediction of the currently best expert at each round.
In the special case where we are solely interested in the best possible performance of the online to batch conversion of Algorithm we can remove the log log term appearing in the previous bound. We remark that, apart from the work of Wintenberger [2017], no known analysis based on the online to batch conversion achieved the optimal rate of aggregation (4). We also believe that our analysis simpler than for previously known algorithms. The result can be found in Theorem 3 below, whose result implied by Theorem in Appendix B.
Theorem 3. Suppose that for all f F If(X) S 1 almost surely, that (0ge(y. Y) S almost surely for all y such that lyl & 1, and that & pusttrongly corvex in its first argument. Then, with probability at least 1 ö, Algorithm 3 with input parameters T, n7 H. S = co, and M 1.
7

---

guarantees
R(F) min R(f) =0 (log(K) + logg(1/))
JeJ
1/
4.2 Statistical Learning: Regression
We consider the statistical learning setting where one has access to T i.i.d. samples of pairs (X,, Yt) _ x R. In this case, we consider F S {æ + (w, (0) E Rd). J. For w E R we define the risk as R(w) [e((w, x)) Y)]. We assume that & is y--stroglly convex in its first argument.
To the best of our knowledge there are no known high probability excess risk bounds in regression based on online batch conversions with convergence rate O (dlog( (dlog(T)) We provide such result in the bounded setup where the feature vectors, derivatives of the losses, and the norm of the reference vector are bounded. Similarly to before, for result that holds with high probability, one needs to control the cumulative variance of our prediction. For standard online learning algorithms the control of the variance may prove troublesome, For example, Mourtada et al. [2021] showed that version of Vovk-Azoury-
Aazuury-Waaruth Warmuth forecaster [Vovk, 2001, Azoury and Warmuth, 2001] may have O(1) excess risk bound with constant probability, whereas expectation the Vovk-Azoury-Wa -armmuh forecaster (og((T)) T
excess risk bound. Instead, leverage the negative empirical variance of Lemma 1 to control the variance of the online to batch conversion, leading to the following excess risk bound, whose result is implied by Theorem 10 in Appendix B.
guarantees O
Theorem 4. Suppose that |||||2 S 1 and su.pe(-1.1] 10yE(y, Y)I S 1 almost surely, | 1, and that l is p-strongly convex in its first argument. Then, with probability at least - 8,
R(w) 0 dllo(T)) + log(1/0)
R
T
Σ
mi
nT
where wi are given by Algorithm 2 with (ww,, X.)) for I.
1' = 2 = G 1, and feedback
Corrupted Feedback
In this section, we study a setting where the loss derivatives (0e) observed by the learner each round may be adversarially corrupted by unknown additive constants Ct, and we are interested in the best possible dependence on Ci...., CT in the regret bound. To better explain our setting, we start with the following example.
Example 3. In the online regression setting, suppose that - = (Dr-y,² for all I, but the learner observes corrupted oulcomes t/: cz/2. Hence, the squared loss derivative computed by the learner is 2( yt + c2/2) = (T() + Ct. which can be handled by the algorithms developed in this section.
Several variants of this setting have been studied in prior work, see for example [Lykouris al., 2018, Amir et al., 2020. Zimmert and Seldin, 2021. Ito, 2021] and the references therein. The main difference between our setting and these previous settings that we assume our losses be strongly convex and the environment is not necessarily stochastic. Although the results in this section are rather straightforward corollaries of our bounds, we believe that is instructive to provide some explicit results. All proofs of the results in this section are postponed to Appendix C.
Our first result shows the performance of Algorithm 1 in the setup with corrupted gradients. The proof follows from observing that & (T)))) - yi) (G.) + ct) (ū. - wt) -r cr. yi) and that for any À 0, the inequality (cr - vt)l < & + ( - )² holds. The 1 (Te - yī term can be compensated for by the negative (0: )2 appearing in Lemma 1, leading to ΣT of additive term in the regret bound. In particular, our result implies that as long as Σ of is of order Ollog K), the same regret bound as if the losses were not cornupted. The formal statement can be found in Theorem 5 below.
Theorem 5. Fix an arbitrary sequence l1,..., lT of p-strongly convex differentiable losses and corruptions CT R. Then the predictions ÿr of Algorithm I run with inputs M Z
8

---

max; ((((0) + cel. 4- feedback 9: = (30 + ct2 and = 1 satisfy
Rx SM (og(K)
T c
M 5 1=1 (Tte ye
T
1
provided max; max, 10 ye - M.
Next we prove an analog of Theorem 5 in the online regression setup.
Theorem 6. Fix an arbitrary sequence fi...., er of p-strongly convex differentialee losses and
corruptions C1...., CT E I.. Then the predictions Tn of Algorithm 2 run with inputs = 5. D²,
G 2 max, (e,( + cz), Z > 0, feedback 9t (,( + Ct. and Rig = 1, satisfy
RT S log 1 1
4dG
TD p max, 2 12
4G
T
Σ t=1
T
Dt - y7)²
2d
1=1
for any 21...., Dr Rd, for any E W4 and yi = (u. x.) for all t 2.
N (w
kw, S Z} such that ||u||2 D
Selective Sampling
We consider a variant of the selective sampling setting-sec, e.g., [Atlas al., 1989, Freund et al., 1997, Cesa-Bianche et al., 2003, 2006, Orabona and Cesa-Bianchi Bianchi,n 201l]-where the learner has access the expert predictions (or, equivalently, feature vectors), but can observe its own loss only upon upo request. The goal is to trade off the number of loss requests with regret guarantees. We show that if the variance is high, with only a fraction of all losses requested we obtain the same guarantee (in expectation and up to constants) as when all losses are requested.
Let 0₁ = with probability at and o, O with probability 1 qi- In each round, if o, the loss & at round t is requested, and we use the loss estimator 4- & to update. Note that this is not the importance weighted estimator, as EE- |
ب. The reason for choosing this particular 9
loss estimator that we have better control of the range of the loss which allows us to tune Re in Algorithm 1 accordingly. The probability of requesting a loss is
min > (T. (e))
= min 1,
(5)
where B >> 0 is chosen by the learner. Our result for the selective sampling setting can be found in Theorem 7 below, whose statement is implied by Theorem 11 in Appendix D. Theorem 7 implies the following: if 3 = Op--3 log( ()), then with only an expected number Σ/= 9. of loss requests, we obtain (up to constants) the same regret guarantee as we would have obtained we had requested all losses. With this particular choice of 3, 4 < 1 as soon the bound in Lemma becomes negative. In other words, when the variance high we only need fraction of the losses to recover the worst-case optimal regret bound (in expectation). A similar result can be obtained in the regression setting, see Appendix D.I.
Theorem 7. Fix an arbitrary sequence E,, .1....,8 lT of p-strongly convex differentiable losses. Provided max, max; 1ūe - (i)) < 1, the predictions Yr of Algorithum run with inputs M = 1 2 max, (C)
1 3.4 feedbacck gt qi (Tt), and Ki ge satisfy
(((()))) -((x))))))) =0 2o(lo((
(K) +
log (K)
1
11 32
7 Further Extensions
In Appendix G we present another application of Lemma Namely, we show that we may restart Algorithm 1 for free whenever the regret becomes negative. This gives us regret bound where we compete with a new expert after each restart, which is stronger notion of regret than when we compete with fixed expert in all rounds.

---

The ideas of Lemma also naturally extend beyond online learning with strongly convex losses. We discuss one such extension to the online prediction with expert advice setting. The online prediction with abstention setting was introduced by Neu and Zhivotovskiy [2020] and proceeds as follows. In each round = I,.... T the learner receives expert predictions ye (t) E [-1,1),
1,.... K and the learner can then either predict Vi {-1.1} or abstain from prediction. If the learner predicts with le. the learner suffers the binary loss (Wee) = 1 lite # yel. where yt E {-1, 13. the learners abstains from prediction, the learner suffers abstention cost p E [0, 2). Let = 1 for prediction and a, for abstention. The total loss of the learner is therefore equal to
Σ (a, v.l + az)p).
Assume that the prediction strategy is random is sense that a are Bernoulli random variables whose means might depend on previous observations. The work of Neu and Zhivotovskiy [2020] shows that there is a randomized prediction strategy such that for any data generating mechanism it holds that
10 + vu = (1 log K (a. 1 [ūe + yel + - (aa))))) E
E
(6)
(1-2p) 2p
independently of T, where the expectation is taken with respect the randomness of a, here Vi = (i*) and 1 = argmin, Σ [[ (i) A ye] Although it was shown that the randomization is necessary to achieve the regret bound (6), it is unclear if the same regret bound can be achieved with high probability with respect to the randomization of the algorithm. In Appendix F, we answer this question using the techniques we developed and provide a randomized algorithm such that, with probability at least d 8.
log K + log log((/6)
Σ (a,10 Fv val +11 a.)p) Σ Lly vol O
2p
In Appendix we prove Lemma 7, which the analog of Lemma for the abstention setting. The equivalent of the negative term in Lemma is used to compensate for the variance of the high- probability statement, which allows us to recover the above bound. This also implies that our other applications of Lemma 1 can be exported to the online learning with abstention setting.
Acknowledgments and Disclosure of Funding
Dirk van der Hoeven and Nicolò Cesa-Bianchi gratefully acknowledge partial support from the MIUR PRIN grant Algorithms, Games, and Digital Markets (ALGADIMAR)) the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 951847, project ELISE (European Learning and Intelligent Systems Excellence), and the project "One Health Action Hub: University Task Force for the resilience of territorial ecosystems" funded by Università degli Studi di Milano. A significant part of this work was done while Nikita Zhivotovskiy Zhivotovskiy was funded in part by ETH Foundations of Data Science (ETH-FDS).
at ETH, Zürich. During this period, Nikita
References
Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33:14315-14325, 2020.
Les Atlas, David Cohn, and Richard Ladner. Training connectionist networks with queries and selective sampling. Advances in Neural Information Processing Systems, 2, 1989.
lves Audibert. Progressive mixture rules deviation suboptimal. Advances in Neural Information Processing Systems, 2007.
Katy Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 43(3):211 (113)2111224,, 2001.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In International Conference on Artificial Intelligence and Statistics, pages 19-26, 2011.
10

---

Olivier Bousquet and Nikita Zhivotovskiy. Fast classification rates without standard margin assump- tions. Information and Inference: Journal of the IMA, 10(4):1389-144 1421, 2021.
Sébastien Bubeck. Introduction online optimization. Lecture Notes, 2011.
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. Learning probabilistic linear-threshold classifiers via selective sampling. In Learning Theory and Kernel Machines, pages 373-387. Springer, 2003.
Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050-2053 2004.
Nicolo Cesa- DesaaBianchi, Claudio Gentile, Luca Zaniboni, and Manfred Warmuth. Worst-case analysis of selective sampling for linear classification. Journal of Machine Learning Research, 7(7), 2006.
Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pages 1216-12555 1259, 2021.
Ashok Cutkosky, Artificial constraints and hints for unbounded online learning. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 874-894, 25-28 Jun 2019.
Tim van Erven, Wouter M. Koolen, and Dirk van der Hoeven. Metagrad: Adaptation using multiple learning rates in online learning. Journal of Machine Learning Research, 22(161):1-61, 2021.
Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning, (3(2):133-166) 1997.
Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In Conference on Learning Theory, pages 176-196, 2014.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Dirk van der Hoeven. Exploiting the surrogate gap online multiclass classification. Advances in Neural Information Processing Systems, 11:9562-95722 2020.
Dirk van der Hoeven, Tim van Erven, and Wojeiech Kotlowski. The many faces of exponential weights in online learning. In Conference On Learning Theory, pages 2067-2092, 2018.
Shinji Ito, On optimal robustness to adversarial corruption in online decision problems. Advances in
Neural Information Processing Systems, 34:7409-7445 7420, 2021.
Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. Advances in Neural Information Processing Systems, 21, 2008
Wouter M. Koolen and Tim van Erven. Second-order quantile methods for experts and combinatorial games. In Conference Learning Theory, pages 1155 1175, 2015.
Guillaume Lecué and Shahar Mendelson. Aggregation via empirical risk minimization. Probability Theory and Related Fields, 145(3-4)5591-613 2009.
Guillaume Lecué and Philippe Rigollet. Optimal learning with Q-aggregation. The Annals of Statistics, 42(1):211 1-22224, 2014.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and Computation, 10822):12-261,, 1994.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 14-122, 2018.
Shahar Mendelson. An unrestricted learning procedure, Journal of the ACM (JACM), 66(6):1-44 2019.

---

Carl D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM, 2001.
Zakaria Mhammedi and Robert C Williamson. Constant regret, generalized mixability, and mirror descent. Advances in Neural Information Processing Systems, 31, 2018.
Zakaria Mhammedi, Wouter M Koolen, and Tim van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Conference on Learning Theory, pages 2490-2511, 2019.
Jaouad Mourtada and Stéphane Gaïffas. On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
Jaouad Mourtada, Tomas Vaskevicius, and Nikita Zhivotovskiy. Distribution-free robust linear regression. Mathematical Statistics and Learning, 4(3-4):253 292, 2021.
Arkadi Nemirovski. Topics in non-parametric statistics. Ecole d' Esé de Probabilités de Saint-Flour, 28:85, 2000.
Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Conference on Learning Theory, pages 3030-3048, 2020.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912. 2019.
Francesco Orabona and Nicolò Cesa-Bianchi. Better algorithms for selective sampling. In Interna- tional Conference on Machine Learning, page 433-440, 2011.
Nikita puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through abstention. IEEE Transactions on Information Theory, 68(7):4651-4655 2022.
Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 1232-1264, 2014.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Conference Machine Learning, page 1571-1578, 2012.
Steven de Rooij, Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the Leader if you can, Hedge you must. Journal of Machine Learning Research, 15:121111316, 2014.
El Mehdi Saad and Gilles Blanchard. Fast rates for prediction with limited expert advice. Advances in Neural Information Processing Systems, 34:23582-23591, 2021.
Alexandre B Tsybakov. Optimal rates of aggregation. In Learning Theory and Kernel Machines, pages 303-313 Springer, 2003.
Volodimir G Vovk. Aggregating strategies. In Proceedings of the 3rd Annual Workshop on Computa- tional Learning Theory, 1990.
Volodimir Vovk. Competitive on-line statistics. International Statistical Review, 69(2):233-248 2001.
Guanghui Wang. Shiyin Lu, and Lijun Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Uncertainty in Artificial Intelligence, pages 659-668, 2020.
Olivier Wintenberger. Optimal learning with Bernstein online aggregation. Machine Learning, 106 (1:119-141, 2017.
Lijun Zhang, Tianbao Yang, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In International Conference on Machine Learning, pages 5882-5891, 2018.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28): 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] All the results claimed the abstract have proofs either in the main body appendix
(b) Did you describe the limitations of your work? [Yes] For each result we state the parameters under which the result holds.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work primarily theoretical and we do not foresee any potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Although some proofs may only appear in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "fLg7N4Xs3-o", "reviewer": "Reviewer_JCyM", "summary": "This paper introduces a new proof technique applicable to many online learning problems where the loss function is strongly convex and bounded, and they show how this new analysis leads to an additional negative term in the regret bound. In different applications, they show how to exploit this negative term to obtain improved bounds for existing algorithms. In particular, for the online prediction with expert advice problem with a well-known $O(\\log K)$ regret bound (where $K$ is the number of experts), they show how to obtain either a negative regret or an $O(\\log K)$ bound for both variance (-variance is the new negative term in the bound) and regret. In addition, the authors show how to apply the same technique to online regression, statistical learning, online learning with corrupted feedback, selective sampling, and online prediction with abstention.", "questions": "- Could the results be generalized to exp-concave loss functions or is the strong convexity assumption necessary?\n- Algorithm 1 introduced in the paper is a variation of the EWA algorithm and it is clear how the new idea obtains tighter bounds for these algorithms. Could the same idea be applied to the Multiplicate Weights algorithm and its variations (where $p_{t+1}(i)\\propto p_t(i)(1-\\kappa_t \\tilde{\\ell}_t(i))$)?\n- The term ``mixability'' is used a couple of times on page 2 without a proper definition and explanation.\n- There is a Lemma 1 on page 2 and there is another one on page 4.\n- Using both $S$ and $\\mathcal{S}$ in Algorithm 3 is a bit confusing and it's hard to distinguish these two from each other.\n", "limitations": "Yes, the limitations are stated.\nNo need for potential negative societal impacts discussion for this theoretical work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The introduced proof technique is significant and novel and it has been motivated throughout the paper via several applications.\n- While most of the technical details have been provided in the appendix, the authors have done a great job providing proof sketches and intuition to highlight how the new idea is applied in several applications and where the improvements come from.\n- Looking into numerous learning problems in detail and showing how the new idea addresses many of the current research questions in each of these areas.\n\nWeaknesses:\n- The paper is a bit hard to follow because of the amount of information that is provided in the text. The authors have tried to highlight all of the applications that benefit from this new idea, however, given the page limit, the discussion regarding each application is very short, and readers with limited exposure to each of these research areas may find it hard to follow the discussions and appreciate the new contributions. \n- Some numerical experiments (particularly for the model selection aggregation problem and Algorithm 3) would have been very helpful to verify the theoretical findings in practice.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bXJe_QQG2bc", "reviewer": "Reviewer_ToYU", "summary": "The authors consider the problems of prediction with expert advice and online linear regression with bounded, differentiable and strongly convex losses. They analyzed variants of the Squint algorithm in the expert advice problem and MetaGrad algorithm in the online linear regression problem. Using curvature of the strongly-convex loss functions and properly tuning the learning rate depending on the strong-convexity parameter, they make appear a negative term in the respective regret bounds of both the algorithm, whose magnitude is proportional the squared difference of learner’s predictions and the best (expert's) predictions. The authors call this term as the \"variance\" and present trade-offs between regret and variance in applications like online-to-batch conversion, online learning with corrupted loss and with abstentions.\n\nIn $K$-experts problem, the authors show that Squint algorithm enjoys negative regret if the \"variance\" term is large. Else, they prove that both regret and variance are upper bounded by $\\log K$. They apply this result to show that early stopping can be achieved in standard online-to-batch conversion scheme when variance is large. If variance is bounded, then the authors show optimal high-probability excess risk bound can be achieved by online-to-batch conversion scheme. \n\nIn online regression problem, the authors show that MetGrad enjoys negative regret if the corresponding variance term is large, and apply this result to obtain optimal high probability excess risk bound using online-to-batch-conversion scheme.\n\nAs corollaries of above results, the authors show how the negative variance term can mitigate the effect of adversarial corruptions and abstentions in corresponding regret bounds.", "questions": "I would like the authors to comment whether the curvature assumption can be relaxed or not, and whether the results can be extended to tackle, say, heavy-tailed corruptions.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors give a nice trick to intelligently combine the curvature of the loss function with a quadratic term that appear in the standard regret analysis of online learning algorithms, which yields some improvements over existing regret bounds in the literature.\n\n2. This intelligent trick is then applied to derive first high-probability optimal excess risk bound in model selection aggregation problem, which is a novel contribution of this paper.\n\n3. The trick has useful applications in interesting online learning problems with corrupted feedback and with abstentions.\n\nWeaknesses:\n\n1. The main results of this paper heavily depend on strong convexity of the loss functions making practical applicability for the results limited.\n\n2. The results also assume boundedness of the gradients, which is fine. However, when applied to the corrupted feedback setting, this assumptions restricts the corruptions to be bounded too. In many practical scenarios, however, corruptions can be unbounded (with some non-zero probability). The current frame work can't capture this properly.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NloRZLx6ApT", "reviewer": "Reviewer_9Zba", "summary": "For the prediction with expert advice problem, the paper considers a modification of the Exponentially Weighted Average algorithm and shows that when variance is large, it is possible to achieve negative regret, i.e., outperform the best expert, otherwise, variance is small (bounded by O(log K), and they fall back to the well-known O(log K) regret bound.\n\nFurther, they use this concept (with the algorithm and its bound) in several other settings and prove regret bounds, essentially trying to make algorithms make use of large observed variance in the loss.", "questions": "1.\tCan it explicitly be stated upfront why strongly convex property of losses is required and where it is used?\n2.\tIn my review (and score), based on my complete reading and understanding, I have assumed Sections 3 and 4 are the crux of the work, and Sections 5, 6, and 7 do not form the main contribution of the work. Is that fair? If not, please help me understand.\n3.\tIn Appendix, equation 7, how does the KL divergence term taken from the literature become $\\ln K$ here? Please elaborate.\n4.\tIn Appendix, line 508, What choice of $\\gamma$ and how does the previous inequality hold? Did I miss something here?\n\nIn the Appendix, I only checked the proof of Lemma 1, and did not read the other proofs.\n\nMinor suggestions:\n\n1.\tLine 21 – Explicitly mention what M is.\n\n2.\tLine 37 - How does assuming $\\mu \\leq 2$ qualify as \"without loss of generality\"?\n\n3.\tLine 56 - “Informal lemma”?\n\n4.\t\"Our Algorithms\" section doesn’t contain all algorithms. Consider re-arranging them to accommodate Algo 3, or perhaps say “Core Algorithms/Results”?\n\n5.\tLines 201-204 and Lines 226-230 have commonalities. Consider defining it once and referring from both places.\n\n6.\t$\\cal{F}$ is defined as a family/set/dictionary in different places like Line 201, 227. Maintain uniformity.\n\n7.\tLine 201, 227 – Further elaborate/define an instance space $\\Chi$.\n\n8.\tLines 203, 229 – Improve readability. Move $f: \\Chi \\Rightarrow \\Real$ two lines up to “real-valued functions defined on..” part.\n\n9.\tLines 204, 229 – Expectation term is missing square brackets?\n\n10.\tLine 234 – Slightly elaborate on why the term is called `optimal rate of aggregation’. I didn’t follow.\n\n11.\tAppendix, Line 510 – “we write”.\n\n", "limitations": "The authors have given adequate references to papers where the original algorithms are taken from, to papers that have considered almost similar settings, to papers whose results are recovered by the current work.\n\nThe authors have been upfront about the limitations of the work.\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.\tCentered around a common theme of utilizing large variance, the paper shows the applicability of this result in several different settings to get auxiliary results.\n\nWeakness:\n\n1.\tThe writing and clarity can be improved. For instance, almost all of the technical stuff is in the Appendix. While I realize the constraints of the page limit, most of the main paper content was overloaded. I suggest showing Lemma 1 and its proof in greater detail in the main paper and moving some of the auxiliary results entirely into the Appendix.\n\n2.\tAll the existing literature work mentioned considers slightly different settings. Given there is no apples-to-apples comparison of the current work with literature, it becomes difficult to assess the quality of the work in the absence of showing lower bounds or showing how close to optimal these algorithms are.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept