Best-case lower bounds in online learning
Authors: Cristóbal A Guzmán
Nishant A Mehta
Ali Mortazavi
Venue: NeurIPS 2021 Poster (2021)
Keywords: online learning
online convex optimization
learning theory

Abstract: Much of the work in online learning focuses on the study of sublinear upper bounds on the regret. In this work, we initiate the study of best-case lower bounds in online convex optimization, wherein we bound the largest \emph{improvement} an algorithm can obtain relative to the single best action in hindsight. This problem is motivated by the goal of better understanding the adaptivity of a learning algorithm. Another motivation comes from fairness: it is known that best-case lower bounds are instrumental in obtaining algorithms for decision-theoretic online learning (DTOL) that satisfy a notion of group fairness. Our contributions are a general method to provide best-case lower bounds in Follow The Regularized Leader (FTRL) algorithms with time-varying regularizers, which we use to show that best-case lower bounds are of the same order as existing upper regret bounds: this includes situations with a fixed learning rate, decreasing learning rates, timeless methods, and adaptive gradient methods. In stark contrast, we show that the linearized version of FTRL can attain negative linear regret. Finally, in DTOL with two experts and binary losses, we fully characterize the best-case sequences, which provides a finer understanding of the best-case lower bounds.

Best-case lower bounds in online learning
Cristóbal Guzmán 1,2 Nishant A. Mehta 3 Ali Mortazavi
'Department of Applied Mathematics, University of Twente Institute for Mathematical and Computational Eng., Pontificia Universidad Católica de Chile Department of Computer Science, University of Victoria
wwggunaauutwente..e.mmm maaieeeenn,mmmmmmmmae www.tatuuvvi.ccmmmmmmmmm ca, alithemorty@gmail.com
Abstract
Much the work online learning focuses on the study sublinear upper bounds the regret. In this work, we initiate the study of best-case lower bounds in online convex optimization, wherein we bound the largest improvement an algorithm can obtain relative the single best action in hindsight. This problem is motivated by the goal of better understanding the adaptivity of a learning algorithm. Another motivation comes from fairness: instrumental in obtaining algorithms for that satisfy a notion of group fairness. Our contributions are general method to provide best-case lower bounds in Follow the Regularized Leader (FTRL) algorithms with time-varying regularizers, which we use to show that best-case lower bounds are of the same order as existing upper regret bounds: this includes situations with a fixed learning rate, decreasing learning rates, timeless methods, and adaptive gradient methods. In stark contrast, show that the linearized version of FTRL can attain negative linear regret. Finally, in DTOL with two experts and binary losses, we fully characterize the best-case sequences, which provides a finer understanding of the best-case lower bounds.
known that best-case lower bounds are
online learning (DTOL)
1 Introduction
typical work in online learning would develop algorithms that provably achieve low regret for some family of problems, where low regret means that learning algorithm's cumulative loss is not much larger than that of the best expert (or action) hindsight. Such work often focuses on algorithms that exhibit various forms of adaptivity, including anytime algorithms, which adapt an unknown time horizon T; timeless algorithms, which obtain "first-order" regret bounds that replace dependence on the time horizon by the cumulative loss of the best expert; and algorithms like AdaGrad [8], which adapt to the geometry of the data. These examples of adaptivity all involve competing with the best expert in hindsight, but adaptivity comes many guises. Another form of adaptivity involves upgrading the comparator itself: in the shifting regret (also known as the tracking regret) [11], the learning algorithm competes with the best sequence of experts that shifts, or switches. & times for some small k. Naturally, an algorithm with low shifting regret can potentially perform much better than the single best expert in hindsight, thereby obtaining classical regret that is substantially negative.
Our work serves as a counterpoint to previous works: we show that a broad class learning strategies provably fails, against any sequence of data, to substantially outperform the best expert in hindsight. Thus, these strategies are unable to obtain low shifting regret and, more generally, low regret against any comparator sequence that can be substantially better than the best expert in hindsight. More concretely, this paper initiates the study of best-case lower bounds online convex optimization (OCO) for the general family of learning strategies known Follow the Regularized Leader (FTRL) [1]. That is, we study the minimum possible regret of learning algorithm over all possible sequences.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

As we will show, many instances of FTRL including adaptive instances that are anytime, timeless, or adapt to gradients like AdaGrad never have regret that is much less than the negation of the corresponding regret upper bounds. Thus, while these instances can be adaptive in some ways, they are in a sense prohibited from uniformly obtaining low regret for adaptive notions of regret like the shifting regret. For example, in the setting of decision-theoretic online learning (DTOL) with d experts 19], the well-known anytime version of Hedge (which uses the time-varying learning rate T/e x /log(d)/)) enjoys O(yT d) worst-case regret and, as we show, has (v log d) bast-case regret. Moreover, in the same setting under the restriction of two experts and binary losses, we exactly identify the bast-case sequence, thereby showing that our best-case lower bound for this setting is tight. The structure of this sequence is surprisingly simple, but the arguments we use to pinpoint this sequence are playfully complex, bearing some similarity to the techniques of [20] and [15]. The latter work [15] considers the regret of Thompson Sampling in adversarial bit prediction; they use swapping rules and identify best-case sequences, as do we. However, the algorithms and problem settings have important differences.
A key motivation for our work is a recent result [4] which shows, in the setting of DTOL, that Hedge with constant learning rate has best-case regret lower bounded by (V(VT). This result, taken together with worst-case upper bounds of order ((VT), is then used to show that each of finitely many experts approximately satisfies certain notion of group fairness, then clever use of the Hedge algorithm (running it separately on each group) also approximately satisfies the same notion of group fairness while still enjoying (VVT) regret. However, we stress that their result is very limited in that it applies only to Hedge when with a known time-horizon. The fixed time horizon assumption also implies that their notion of group fairness also is inherently tied to a fixed time horizon (see Section 4.2 for a detailed discussion), and this latter implication can lead to experts that seem very unfair but which, based on a fixed horizon view of group fairness, are technically considered to be fair. Our best-case lower bounds enable the results of [4] to hold in much greater generality; in particular, our results enable the use of an anytime version of group fairness, which we feel is truly needed.
To our knowledge, our work is the first to study best-case lower bounds for Adaptive FTRL [16], i... FTRL with time-narying regularizers that can adapt to the learning algorithms'' past observations. The most closely related work is paper by Gofer and Mansour (GM) [10] which, in the setting of online linear optimization (OLO) and when using FTRL with a fixed regularizer,' provides various lower bounds on the regret. For instance, they show that for any sequence of data, the regret is nonnegative; we recover this result as a special case of our analysis, and our analysis extends to OCO as well. GM also lower bound what they call the anytime regret, which superficially may seem similar to our providing best-case lower bounds for anytime algorithms. Yet, as we explain in Section 3, these two notions greatly differ. In short, their analysis lower bounds the maximum regret (over all prefixes of sequence) for fixed horizon algorithms, whereas our analysis lower bounds the regret for all prefixes (including the minimum) for adaptively regularized algorithms, which includes anytime algorithms.
A natural question is whether results similar to our results for FTRL also hold for online mirror descent (OMD). In some situations, such as in OLO when the action space is the probability simplex, the regularizer is the negative Shannon entropy, and the learning rate is constant, our results automatically apply to OMD because the methods are then the same. More generally, is known that OMD with a time-varying learning rate can fail spectacularly by obtaining linear regret (see Theorem 4 of (18)). Since so much of our work is tied to obtaining anytime guarantees (which would require time-varying learning rate), we forego providing best-case lower bounds for OMD.
Our main contributions are follows:
1. We give general best-case lower bound on the regret for Adaptive FTRL (Section 3). Our analysis crucially centers on the notion of adaptively regularized regret, which serves as a potential function to keep track of the regret.
2. We show that this general bound can easily be applied to yield concrete best-case lower bounds for FTRL with tire-varying negative regularizers, one special case being the negative Shannon entropy. We also show that an adaptive gradient FTRL algorithm (which can be viewed as a "non-linearized" version of the dual averaging version of AdaGrad [8]; see Section 4.3 for details) admits a best-case lower bound that is essentially the negation of its upper bound (Section 4).
'[10] uses learners that follow the gradient of concave potential, which is essentially equivalent to FTRL.

---

3. A widely used variant of FTRL for OCO is to first linearize the losses, leading to linearized FTRL. This method works well with respect upper bounds, basic argument involving convexity goes in the right direction. However, with regards to best-case lower bounds, we show simple construction (Section 5) for which linearized FTRL obtains -T) regret.
4. In the setting of DTOL with 2 experts and binary losses, we explicitly identify the best-case sequence, proving that our best-case lower bounds are tight in this setting (Section 6).
The next section formalizes the problem setting and FTRL. We then develop the main results.
2 Problem Setting and General Prediction Strategies
Before giving problem setting, we first set some notation. denote the norm of vector w E W as ||w|| the corresponding dual norm is denoted as || ||x. and log is always the natural logarithm.
Problem setting. We consider the OCO setting. This is a game between Learner and Nature. In each round 1.2,..., T, Learner selects an action w, belonging to closed, bounded, convex set W S Rd. Then, with knowledge of Wi...., Nature responds with convex loss function fe: W R. Learner then observes ft and suffers loss f((w)). Learner's goal is minimize its regret, defined as
RT == sup WEW
- -
which is the gap between Learner's cumulative loss and that of the best action in hindsight.
This paper will cover several examples of OCO. The first example is the subelass of OLO problems. In OLO, the loss functions Je are linear, with fe(w) = (le, w² for some loss vector & Rdd A noteworthy special case of OLO is DTOL, also known the Hedge setting. In DTOL, we take W to be equal to the simplex Aa over outcomes and restrict the loss vectors as l E [0, 1J We introduce some notation that will be useful in the DTOL setting. For any expert j E [d], let Lr,j := E.= l denote the cumulative loss of expert j until the end of round L. We denote the loss of Learner in round t as & :- (l,, wx) and Learner's cumulative loss the end of round as L, -- l. In this work, we consider the general prediction strategy of FTRL.
FTRL. Let 1 22.... .. be possibly data-dependent sequence of regularizers where, for each t, the regularizer .; is mapping Φ, W > R which is allowed to depend on (fa)age. Then FTRL chooses actions according to the past regularized cumulative loss:
w++1 = arg min wEW
Σ fa(w)+ Dc(w)
(I)
We would like to emphasize that this is very general template. It includes fixed learning rate regularization, Φ, = 1.0, as well as its variable learning rate counterpart, Q; = forms of adaptive choices of de based on the past. Despite this adaptivity, in the next section we will show that proving best-case lower bounds for this strategy is quite straightforward.
nh - and arbitrary
The regret attained by FTRL is summarized in the following known result.
Theorem (Theorem of [16]). Let (#:)22 be sequence of nonnegative regularizers such that, for each t 2 1, & is 1-strongly convex with respect to a norm || algorithm (1) with this sequence of regularizers upper bounded as
-l(te)- The regret of the FTRL
Rr < (T(w") + ET= [V
where w² E W is the best action in hindsight. we do not require the regularizers to be nonnegative but instead assume that, for each w W. the sequence (2,()))22 is non-increasing, then (2) still holds if we replace (r(w*) by (T(")) inf (w)).
"This negative construction, combined with the fact that the dual averaging version of AdaGrad is a linearized version of FTRL, is why only prove best-case lower bounds for the adaptive gradient FTRL algorithm.

---

3 A general best-case lower bound
We now present our general best-case lower bound for FTRL. Key our analysis is the concept of adaptively regularized regret (hereafter abbreviated as "regularized regret"), defined as
th R²
sup
Eif.(w.) (((..))-(ww))) (.(w))
(3)
WEW
The regularized regret can easily be related to the regret as
R < R₂
inf 4(w).
(4)
NEW
Also, applying (I), the following re-expression of the regularized regret is immediate:
R2
(is.(w)) - fa(w++1)] - (e(we+1).
(5)
==1
Theorem 2 (Best-case lower bound on regret for adaptive FTRL). Consider the setting of online convex optimization and the adaptive FTRL strategy (I), Suppose that there exists a sequence (oo)r such that (e(w)) S Φ1-1(w)) + ore for all I E (T). Then
Rr inf PT(w)= inf Po(w) WEW
Σ 0t2.
wEW
Proof. We start by inductively bounding the adaptively regularized regret:
4+1
4+1
R R+11
Pr+1
R2
sup wEW
i... fs(w)] - 2111(1))
-is((w)) fs(we41)) P.(w)+1)
- (1 (w++1)
-4+1
where the first equality is from (5). We conclude that RTTT 2 Rg - Ete ar Next, from (4),
Dr RT 2 RT
inf Pr(w)
2
inf weW
TT(w) + Ro
- ar
wEW
tm
inf (w) inf (o(w) wew
at
weW
where in the last equality we used that R supwewt (oW))
The closest results to Theorem 2 of which we are aware are in the intriguing work of Gofer and Mansour (GM) [10], who provided lower bounds for FTRL with fixed regularizer for OLO. Their Theorem 1 shows that the best-case regret is nonnegative. One wonders if the doubling trick can extend their results to anytime best-case lower bounds; regrettably, the doubling trick's restarts can allow the algorithm to achieve -I((T) regret (see Appendix A). GM also lower bound notion they call the anytime regret (see Theorem of [10]). The anytime regret for a sequence as they define it is actually the maximum regret over all prefixes of the sequence (where the sequence has fixed time horizon): ultimately, the lower bound they obtain depends on the quadratic variation of the sequence computed on a fixed time horizon. Related to this, GM's analysis is for algorithms that use the same regularizer all rounds. They lament that it is unclear how to extend their analysis to handle time-varying learning rates?. Our goal is rather different, over all prefixes says nothing about how large (in the negative direction) the regret could be for some particular prefix. Thus, our style of analysis, which provides a lower bound on the regret for all time horizons (which, in particular, provides a lower bound on the minimum over all prefixes), differs greatly from theirs and is what is needed. We think the different styles of our work and theirs stems from the regret being nonnegative in their paper, whereas it need not be for time-varying regularizers.
taking the maximum regret
Theorem 2 possesses considerable generality, owing to its applying to FTRL with adaptive regularizers. We highlight just a few applications the next section.
A time-vate time-varying learning rate gives rise to perhaps the most basic form of an adaptive regularizer.

---

Best-case lower bounds in particular settings
Theorem presented in last section, despite its simplicity, is extremely powerful method, capable of addressing several of the settings where FTRL attains sublinear regret. Next, we proceed to enumerate some important examples of instances of FTRL, comparing existing worst-case upper bounds on the regret with our best-case lower bounds.
4.1 Non-increasing learning rates and timeless algorithms
We first present several examples in which the elements of the sequence (#+))21 take the form P & for fixed regularizer & and time-varying learning rate 7)--
Constant learning rate. The simplest example is that of a fixed learning rate ?e 7) which means (w)) = (wv). Taking o = O for all f, Theorem immediately implies that the regret always nonnegative; this implication was previously shown by Gofer and Mansour (see Thm. of [10]). A simple consequence that the Follow the Leader (FTL) strategy (i.e., 4, 0) has nonnegative regret, which also can be inferred from the results of [10]. Although we cannot find a precise reference, we believe that it was already known that FTL always obtains nonnegative regret (even prior to [10]).
Time-varying learning rate.
More generally, taking a time-varying learning rate, Theorem 2 gives
T
Rr
inf (w)
Σ
1 (w++1)) T
(6)
1/
WEW
typical strategy obtain sublinear anytime worst-case regret to set the learning rate as 1// + for some constant that depends on various known mroblem-dependenn constants. Continuing from (6) with this setting further implies that
T
R 2 1 (V+++-11 inf ((w) 17
1 sup ((w) wew
wEW
77
2
If & is nonpositive holds when i'ss the d-dimensional simplex and 4 is the negative Shannon entropy the above is further lower bounded by
(VV++I- inf ((w) WEW
sup ((w) VT ((w)VT+) +1 1) weW
particularly interesting example is the DTOL setting. In this setting, when we take to be the nega-
tive Shannon entropy ((w) = Σラ wj log wy and set 2 so that 7)t = 2 -2 dt recovers the standard anytime version of Hedge which has also been called Decreasing Hedge [17]. In round f, this algorithm plays wa such that Wt.j exp(-1)- T4-1,)) for j [d], and have the following anytime best-case lower bound and worst-case upper bound on the regret:
F Toog d S RT S Tlog.
The lower bound holds from (7) combined with VT+I-1+-1 - VT and log < 1 S O, while the upper bound is from Theorem 2 of [6]. The upper bound is minimax optimal in terms of the rate and, asymptotically (letting both d and T go infinity) has a constant that is optimal to factor of /2. As we show in Section 6, in the case
the lower bound also has the optimal rate.
Timeless algorithms. In the context of DTOL, it is straightforward to adapt analysis for Decreasing Hedge to Hedge with any non-inene con-increasing learning rate. One example interest is
T log (1 min {
log L;
where LΙ minjeld Lrg is the cumulative loss of the best expert. This choice of adaptive learning rate yields an anytime upper bound on the regret of O (v TTg. log log d) in the DTOL. setting (see Theorem 2.1 of [2], who actually prove this result in the more general setting of prediction with
5

---

expert advice). Such bound is called timeless because rounds in which all experts suffer the same loss have no effect on the bound [7]. This is natural property to have in this setting, and with the above choice of learning rate, we have the following timeless" best-case lower bound:
Lip
log
R min
0,
4 log d
(8)
a brief derivation is in Appendix B. Again, notice the similarity between the upper and lower bounds.
4.2 Group fairness in online learning
In a pioneering work, Blum, Gunasekar, Lykouris, and Srebro (BGLS) [4] considered notion of group fairness DTOL. their setup, the DTOL protocol is augmented so that, at the start of each round I, Nature selects and reveals to Learner a group Ii belonging to set of groups G prior to Learner's playing its action wt. They assume that for a known, fixed time horizon T. each expert E [d] has balanced mistakes across groups in the following sense: For any g G, let T(g) = {t E : 9: = g} denote the rounds belonging to group g. and let LT(g).) == EIET(E) las denote the cumulative loss of expert j E [d] when considering only the rounds in T(g); then we say that expert is fair in isolation if
LTGSSs Ligna for all 9.9 E G. [T(g]] [T('']
=
BGLS devised strategy based on the multiplicative weights algorithm which simultaneously satisfies an approximate notion of group fairness while still enjoying O PTo d) worst-case regret. The multiplicative weights algorithm (which we hereafter refer to Hedge the algorithms are equivalent for constant learning rate) sets Wi as Wt, x (1 - (1- -e-1. for E [d] for a learning rate parameter vj. Their strategy to run separate copy of Hedge for each group, that for any group g, the copy corresponding to group is run on the subsequence corresponding to the rounds in T(g). For brevity, we call this "Interleaved Hedge". In BGLS's analysis (see the proof of their Theorem 3), they first give worst-case regret upper and lower bounds for Hedge. Specifically, they show that if Hedge is run with constant learning rate, then
(1 4r) LTp S LT S (1 + 1 (log d)/
An optimal, non-anytime worst-case tuning of 7j then yields upper bounds of -O(VT log d) and O(vT log d) respectively. Then on the one hand, the regret of Interleaved Hedge satisfies Ry D(V/g)/log d). In addition, by virtue of BGLS's -0(VT d) lower bound for Hedge when fed T rounds (along with the standard upper bound), their Interleaved Hedge enjoys the following group fairness guarantee:
regret lower and
LTW [T0
TTT( [TG
(v
logd To
for all g.g6 G and To ming [T(g),
where we adopt the notation
LT(9) = EIETG) l.
By using our improved nonnegative best-case lower bound for Hedge with constant learning rate (which again, is not new result) together with an optimal, non-anytime worst-case tuning of we can obtain the following improvement over (9):
5 L S logg
As explained in the appendix (the remaining steps are essentially due to BGLS), we can then obtain the following improved group faimesss guarantee:
Lria) T
logd To
for all g. g.g't e G and To == ming [T(g))
The above result holds when the learning rate for each group is set as ry(9) / log d (T Of course,
running Hedge instances for each group with the correct constant learning rates means that the
'Technically, the upper and lower bounds as stated are not timeless, but it is easy to see that any round for which all experts have the same loss can be replaced by a round where all experts have zero loss, with no change in the algorithm's 's behavior its regret. Our regret bounds on the modified loss sequence then become timeless.

---

algorithm must know (T(9) for each group 9 E G, at least within a reasonable constant factor. This a far stronger assumption than the already strong assumption of known time horizon.
Using our anytime best-case lower bound for Decreasing Hedge, combined with the analysis of BGLSS it is straightforward to vastly extend their results in each of the following ways:
1. Using BGLS's fixed horizon notion of fairness and copy of Decreasing Hedge for each group's instance, we can drop the assumption that each group's 's cardinality (T(g) is known.
2. The most interesting extension, whose possibility was the original basis our entire work, is that
now upgrade BGLS's notion of group fairness to its anytime sibling. This involves measuring. for every prefix of the length-T' game, the discrepancy between the error rates of any pair of groups. This is arguably more natural notion of faimess, as it avoids situations where an expert purports to be fair while having all of its mistakes for one group occur in the first half of the game. Since we have anytime best-case lower bound for Decreasing Hedge, have the requisite piece needed to show that Interleaved (Decreasing) Hedge satisfies the same notion of anytime group fairness. Our timeless best-case lower bounds also apply here, giving that extension as well.
We now briefly sketch each of these extensions, leaving more detailed derivations to the appendix.
Decreasing Hedge (Anytime results). Suppose now that Interleaving Hedge uses copies of De- creasing Hedge with time-varying learning rate 7/s 2/ (log d)/(1 +11+ 1). Note that in this case, the copy for group g increments its internal round only each time a new round for group g appears. We can then automatically apply our anytime lower bound on the regret of Decreasing Hedge obtain
iT( ITT (T
(7 I
logd (T)
+ 1 log [7(
IT(e") for g" such that (7 = mingeg (7))
Therefore, in hindsight we have To = mingeg (T(g),, then the following fairness guarantee holds:
LTID's (7
logd To
for all g. g/ G.
Note that even though Learner need not know the time horizon T nor [T(g) for each g, the above guarantee still can only hold for a fixed time horizon T. This is because the definition of fairness in isolation only holds for fixed time horizon.
Anytime fairness. As mentioned earlier, the fixed horizon view of fairness in isolation can very limiting. Rather than opting for fairness in isolation to hold for fixed time horizon, we argue that it is more natural for this definition to hold in the following anytime sense:
Lriahs L for all g.96 E 9 and for all T; [T())
(T('))
note that the time horizon T is implicit in each T(g).
The attentive reader may notice that this definition can be overly restrictive on Nature (perhaps impossibly so), and therefore it is natural to allow the equality to hold only approximately (which BGLS did explore). Just as in BGLS's work, is possible to extend our results to cases where fairness holds only approximately, and such an extension is certainly warranted in the case of anytime fairness. This extension requires only straightforward modifications to the analysis and so we do not give further details here. In the case of anytime faimesss it further makes sense for approximate fairesss to be defined according to a rate. We leave this extension to a future, longer paper.
Using the above anytime version of fairness in isolation, it is straightforward to extend the previous result the following new result. Just like above, suppose now that Interleaved Hedge uses copies of Decreasing Hedge with time-varying learning rate. Then, for all time horizons T,3
V
logd T5
for all g, g G.
Mini-conclusion. Whereas a key message of [4] is adaptive algorithms (in the sense of low shifting regret) cannot satisfy group fairness, at least when using the interleaved approach, our best-case lower bounds do cover many other types of adaptivity. This shows that with regards to group fairness and the interleaved strategy, the group-fair adversarial online learning tent is actually quite large.
Note that in the below, each T(g) (and hence To) implicitly depends the time horizon T..
7

---

4.3 Adaptive gradient FTRL
Inspired by the adaptive gradient (AdaGrad) algorithm for OCO [8), we consider adaptive gradient FTRL algorithm with quadratic regularizers, (r(w) = 2nj (w, Hww): this corresponds to the adaptive
FTRL (I) with regularizers 2, as above. We include its two variants. In the below, we use the
notation Jr :- (wx) and 5 > 0 is fixed number:
(a) Diagonal: H, 81 Diag (t), where St -( ((VE-- (
(b) Full-matrix: H, aT G. where Gt = E+=1 9:91
We emphasize that the proposed algorithm does not exactly match AdaGrad from [8]. To resolve this inconsistency, we use the regret upper bounds from Theorem 1, combined with upper bounds on the gradient norms that appear in such upper bounds, proved in [8]. This leads the following result.
Theorem 3 (From [8]. Consider the setting of OCO. Given 1 S Co, we denote by Dy the diameter of W in the || lp norm, and Mp bound the -llp norm of the gradients for any possible loss. Then the adaptive gradient FTRL algorithm satisfies the following bounds:
(a) Diagonal: If 8 = Mo then E (u(()))ll
(1-1), S 2n Ei=1 V G.. In particular, (t-
D2 M Doc Ei=1 VIL
setting 1) Dos obtain upper bound on the regret D
(b) Full matrix: If = M2. then Σ ( I 2n TM(TT (2) In particular, setting D2, we obtaïn an upper bound on the regret [2 TTG
We proceed to best-case lower bounds, deferring the proof to Appendix D. The proof strategy follows similar telescopic recursions to those used [8, 16]. Notice that these bounds closely match the respective worst-case upper bounds.
Proposition In the OCO setting, the adaptive gradient FTRL strategy with parameter tuning as in Theorem 3 atlains best-case lower bounds on the regret of (D Ei= /2) v /Eeem gh,3 in the
diagonal case and -D22/2)/t(( in the full-matrix case.
On best-case lower bounds for other algorithms
So far, study of best-case lower bounds has focused adaptive FTRL algorithms. A major drawback of FTRL is that the iteration cost of each subproblem grows linearly with the number of rounds. It is then tempting to consider efficient algorithms attaining comparable regret upper bounds. We discuss such possibilities for two natural algorithms: linearized FTRL and OMD.
5.1 Linearized FTRL
In this section, we give a simple construction in which linearized FTRL obtains negative linear regret, ie., regret which is (TT). The problem is a forecasting game with binary outcomes, the action space D equal to the 2-simplex [0, 1], and the squared loss E y) = 1 (p z) This can be cast as an OCO problem by taking W [0, 1] and, for each [T], setting (p) = (p y for some outcome E {0, 1} selected by Nature.
We consider linearized FTRL using the negative Shannon entropy regularizer; this is equivalent to exponentiated gradient descent [12] and uses the update p. I+exp(n, where G,-1 Σ Is and each ys Ps - y/ the gradient of the loss with respect ps under outcome ya- In this situation, O(VT) anytime regret upper bound can be obtained by employing the time-varying learning rate We 1/vī (see Theorem 2.3 of [5] or Theorem of [6]).
Let Nature's outcome sequence the piecewise constant sequence consisting T/2 zeros followed by T/2 ones. Therefore, the best action in hindsight is y" = 0.5. We now state our negative result and briefly sketch a proof; the full proof can found in Appendix E.
Theorem 5. In the construction above, linearized FTRL obtains regret RT -Q(T).

---

Proof (sketch). The core idea behind the proof is that linearized FTRL exhibits type of switching behavior. Let go and qı be constants satisfying 0 < 90 < 1/2 qi 1. Observe that in the first half of the game (considered in isolation), the optimal action is 0. Thus, if drops below go in the first half of the game, then for all rounds thereafter in the first half, Learner picks up negative constant regret in each round. We show that this drop happens after only a constant number of rounds for simple reason: the gradient must be at least go whenever Pt > qo in the first half, and Pt changes according to the exponentiated cumulative gradient. Thus, Learner picks up negative linear regret in the first half of the game, Next, consider the second half of the game. For this half (considered in isolation), the optimal action is 1. Thus, once Pt surpasses Qı, for all rounds thereafter Learner will again pick up negative constant regret. Via an arguably coarse analysis, we show that the number of rounds in the second half before Learner's 's' action Pt surpasses 91 is at most small constant fraction T. To show this, we rely on the fact that whenever Pt < 91 in the second half, we have that the gradient must be least -Q1 (combined with the exponential effect of the gradients on pt)- That is, Learner quickly switches from having Pt below qo to having Pt above F1. Thus, for most of the second half, Learner again picks up negative linear regret.
5.2
Online mirror descent
For OLO over the simplex, the online mirror descent method with entropic regularization and constant learning rute attains best-case lower bounds - ((v7 log d) [4]. This algorithm is known to attain upper bounds on the regret of the same order. The extension of this result for non-increasing learning rates, albeit possible, seems of limited interest, this algorithm is known to achieve linear regret in the worst case [18], which is attributed to the unboundedness of the Bregman divergence.
Best-case loss sequence for binary DTOL with two experts
In this section, we characterize the binary loss sequence for DTOL with two experts in which the regret for Decreasing Hedge minimized. Recall that Decreasing Hedge chooses expert at round t with probability Ps, = Eee( exp(-1t 1,3,-11) where = v1/t. Losses are the form &, where L,,,, f E (0, 1]. Note that 7h41 < 1/t for all 4.
exp(-
(61,) (e.))
Our approach is to introduce a set of operations that do not increase the regret of Decreasing Hedge. Using this set of operations, we will show that any loss sequence with T = 2K rounds E, .2,2..... L2x, can be converted to specific loss sequence which we call the canonical best-case sequence.
..... sequence of binary loss vectors L1 le...... er
Definition 6. For any length T 2K 16, the canonical best-case loss sequence is defined
Canonical = (1) K- ()))))))))***
(10)
We now sketch our proof that (10) is indeed the best-case sequence. The full proof is in Appendix
First, consider an arbitrary binary loss sequence for two experts e,,...,&y lr. (1, 1) loss vectors with (0, 0) loss vectors it can be easily shown that this operation does not change the regret. Thus, there is no need for (1, 1) loss vectors in the best-case sequence.
We can substitute all
Next, we introduce the notion of leader change and show that there is no leader change in the best-case sequence. Therefore, we only need to consider loss sequences without leader changes. Formally, say expert j is leader at round t if Lj.- = minig (1.2) Li,t- Moreover, if is the only leader at round f, then we call 87 = j the strict leader in round t. We say that sequence has a leader change if there exists times t and t2 where in both times the strict leader is defined? and i it Defining A, == L2, LI, observe that if a sequence has a leader change, then the sign of Á should change least once. We show (Lemma 15) that any loss sequence L1, l2 ... lr can be converted, without increasing the regret, to a sequence L' Ez.... Cr where A is always nonnegative (hence, the resulting sequence has leader change). Removing all leader changes facilitates the next operation to successfully convert loss sequences.
Next, consider the operation of swapping two consecutive loss vectors. When we swap loss sequence ,,, 1, Le. le+1, l..2...., lx at round (t, t + 1), the resulting sequence becomes
II fact, we have found a simple argument showing the regret is nonnegative, strengthening the result in [4]. If in round t, LL. L2, then the strict leader is not defined in that round.

---

A.....,--11,41 Le, ... It can be easily shown that this swap only changes the loss of Decreasing Hedge at rounds and + 1. Since we only consider loss sequences with no leader change, we can assume without loss of generality that expert 1 is the only leader. Now based on the swapping rule lemma (Lemma 16), we can always move (!) to the earlier rounds and (o) to the later rounds. By repeatedly applying this swapping rule, the resulting loss sequence will be of the form
Li...., lT (2) (a) (a) Note that as we have shown that A is always nonnegative,
b.
So far, we have shown that any loss sequence can be converted a loss sequence of the form li...., lT ()) (w) (a) We then show in Lemma 17 that if c is not even, then the sequence ())
2 b. Therefore, we only need to consider loss sequences of the form (9) a (o) (a) where a 2 b and e is even. As we assume T is even, a + b is also even. Now is shown (in Lemma 18) that among all sequence of losses of form l,..... ......,, by =
( has smaller regret and
(1) ()) where a + 6 2K, the loss sequence (1) K ())))) has the least regret. Therefore, we only need to consider loss sequences of this latter form where 2K" + T.
Finally, among all possible (K,c) c) for loss sequences (1) (0) (o) such that 2K + T, we show that the regret is minimized when e = 2. This form coincides with the canonical best-case sequence.
Bounding the regret. As shown in Appendix F.6, the regret on the canonical best-case loss sequence can be lower and upper bounded as follows:
- S R(T) &
Ite
2-
As both the lower and upper bounds are - -O(VT) the analysis in Section 3 is tight in this case.
7 Discussion
In this work, we provided a systematic treatment of best-case lower bounds in online learning for adaptive FTRL algorithms, discussed the impossibility of certain natural extensions, and also provided tighter analysis of such lower bounds in the binary prediction experts setting. As one application, we have shown that our results for adaptive FTRL enable the use a broad class of adaptive online learning algorithms that satisfy a balanced mistakes notion of group faimess. Naturally, many questions still remain open, and we hope this work motivates further research in this intriguing topic. A first question relates to algorithms that can achieve negative regret: can characterize the conditions under which this happens? The goal would be to reveal, beyond the particular example we gave in Section 5. structural properties of an instance that lead to substantial outperformance of the best fixed action. Returning to that example, another question arises. We have shown an example of OCO with a strongly convex loss (the squared loss) for which linearized FTRL obtains negative linear regret, whereas our best-case lower bounds for (non-linearized) FTRL with constant learning rate imply (VVT) regret and known upper bounds imply O(log Z') regret. Thus, while in this situation, linearized FTRL pays a price with respect to regret upper bounds, can exhibit a switching behavior that might allow it to compete with a shifting sequence of comparators. Investigating this "blessing" of linearization would be a fascinating direction for future work. Finally, for DTOL with two experts, we showed that our best-case lower bounds are tight by constructing the best-case sequence. It would be interesting to show tightness without an explicit construction, as we could then say that the best-case lower bounds are achievable more generally. For instance, while our swapping- technique most related to that of [20] for worst-case sequences and [15] (who give both worst- and best-case sequences), it could also be worthwhile to draw from previous works [19, 13, 3. 14] which explicitly work out the minimax regret and minimax strategies. Even so, our results on identifying the structure of the best-case loss sequence show that Decreasing Hedge has the lowest regret for loss sequences for which the best shifting sequence of experts has precisely one shift. One research direction would be to see if this pattern holds more generally, for other FTRL-type algorithms.
We conclude our discussion pointing out that the theoretical nature of our work does not entail direct negative societal consequences. As far as our discussions on group faimess are concerned, one should be careful when applying these methods as the notion of balanced mistakes may be susceptible to strong forms of discrimination (see, e.g., the Discussion section in [4]). In particular, balanced mistakes is a sound notion of non-discrimination when all examples that contribute towards the performance also contribute towards fairness.
10

---

Acknowledgments and Disclosure of Funding
CG's work was partially supported by FONDECYT Regular project 1210362, INRIA through the INRIA Associate Teams project, and ANID Millennium Science Initiative Program NCN17 059. NM and AM were supported by the NSERC Discovery Grant RGPIN-2018-0394 We also thank Sajjad Azami for his involvement in the earlier stages of this work.
References
[1] Jacob Abernethy, Elad E Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. 2 Annual Conference on Learning Theory, COLT 2008, pages 263-273, 2008.
[2] Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
[3] Peter L Bartlett, Wouter M Koolen, Alan Malek, Eiji Takimoto, and Manfred K Warmuth. Minimax fixed-design linear regression. In Conference on Learning Theory, pages 226-239. PMLR, 2015.
[4] Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, and Nati Srebro. On preserving non- discrimination when combining expert advice. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biance and Garnett, editors, Advances Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc., 2018. URL htttps://proceeeiin 2aw.aaaeee.7..2aa0aa0aeeeeeeaaaa iaaaaaappppe pdf.
[5] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[6] Alexey Chernov and Fedor Zhdanov, Prediction with expert advice under discounted loss. In International Conference Algorithmic Learning Theory, pages 255-269. Springer, 2010.
[7] Steven De Rooij, Tim Van Erven, Peter Grünwald, and Wouter M Koolen. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, 15(1):1281-131) 2014.
[8] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learming Research, 12:2121-2159, 2011.
99] Yoav Freund and Robert Schapire. A decision-theoretic generalization on-line learning and an application to boosting. Journal of computer and system sciences, 15(1):119-133 1997.
[10] Eyal Gofer and Yishay Mansour. Lower bounds individual sequence regret. Machine Learning, 103(1):1-26, 2016.
[11] Mark Herbster and Manfred K Warmuth. Tracking the best expert. Machine learning, 32(2): 151-178, 1998.
[12] Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(1):1-63, 1997.
[13] Wouter M Koolen, Alan Malek, and Peter L Bartlett. Efficient minimax strategies for square loss games. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Cur- Associates, Inc., 2014. URL https: /ttpr//eeeeeee.sseee/eeee/c neurips..... cctp.cccppppppppp hpappe/2014/fiil// Paper. .df..
[14] Wouter M Koolen, Alan Malek, Peter L Bartlett, and Yasin Abbasi Yadkori. Minimax time series prediction. In C. Cortes, N. Lawrence, Lee, M. Sugiyama, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https: / Acc4455439944449224455666666 http///pocceeeeeee//ee////e
/ www.eeeeiinnnn.uuiiiii.....eeepp www.nnnuu..... httpripss.c//pprr/1////1ee Paper, pdf.
11

---

[15] Yuval Lewi, Haim Kaplan, and Yishay Mansour. Thompson sampling for adversarial bit prediction. In Algorithmic Learning Theory, pages 518 553.. PMLR, 2020.
[16] H. Brendan McMahan, A survey algorithms and analysis for adaptive online learning, Journal org
of Machine Learning Research, 18(90): 1-50, 2017. URL http://jmii httpj//i..o//ppprpeeeeeee pappra/v18/
14- 41-.428.40 html.
[17] Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28. 2019.
[18] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
[19] Eiji Takimoto and Manfred K Warmuth. The minimax strategy for gaussian density estimation. pp. In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, pages 100-106, 2000.
[20] Tim Van Erven, Wojeiech Kottowski, and Manfred K Warmuth. Follow the leader with dropout perturbations. Conference on Learning Theory, pages 949-974. PMLR, 2014.
12


Reviews:
[{"review_id": "jsJEchchsnV", "reviewer": "Reviewer_3Dws", "summary": "Inspired by applications of fair online learning, the authors initiate the study of *lower bounds* on the regret of OCO algorithms. They provide a general lower bound for FTRL algorithms and show the implications for fixed regularizers and for some special kinds of time-varying regularizers (such as fixed regularizers with time-varying learning rates or regularizers dependent on the past losses). They also provide regret lower bounds on AdaGrad-like algorithms derived from the FTRL framework, and show how linearizing the losses can yield to algorithms with potentially $-\\Omega(T)$ regret in $T$ rounds. They also explicitly build the best-case losses for the experts problem with 2 experts, giving sharp bounds for this special case;\n\nTheir main application is to fairness for decision theoretic online learning (experts' problem), strengthening previous fairness bounds. They show a way to get fairness guarantees without needing to know the size of the groups, and extending the fairness notion in online learning in a way that is independent of the length of the game.", "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": "# Strengths\n- A solid theoretical paper, with a novel perspective on online optimization/learning and initiating a possibly fruitful direction of research;\n- A solid contribution to fairness for DTOL, analyzing a natural fair algorithm that does not need to know the size of the groups ahead of time, and a good discussion on how the current notion of fairness from previous work is highly dependent on the time horizon;\n- Very good characterization of the connection between fairness and lower-bounds on the regret;\n- An example of an algorithm with a sublinear regret upper bound but with a linear regret lower bound, leaving open interesting questions about the characterization of algorithms that suffer from linear best-case lower-bounds. \n\n# Weaknesses\n- Implicit assumption on boundedness of the feasible set in the more general analysis of FTRL and some hidden assumptions on the regularizers that are not mentioned anywhere (and can even render the results false), details later;\n- A lack of motivation (very interesting theoretically, but the broad NeurIPS audience might have a hard time understanding the motivation of the work);\n- Regret bounds for the AdaGrad-like algorithms have an (apparently) extra dependence on a bound on the gradients that is not present in the original AdaGrad algorithm;\n- The result for 2 experts, although exact, seems to lack a bit of discussion/motivation;\n\n# Summary of the decision\n\nA solid theoretical contribution with strong connections to fairness. So I consider it to be a good paper (7), although not higher since the motivation and applications, although interesting, are still narrow. I still expect comments of the authors on some of my points (mainly (3)) to maintain my score, but I believe none of these are serious problems.\n\n# Detailed discussion\n\n1) I really believe this paper is a solid theoretical contribution and initiates a direction of research that, beyond the clear applications to fairness already discussed, can have connections to stability of online learning algorithms and give some intuition on algorithms that can perform \"extraordinarily\" well in practice. Of course, it is not a completely new field, but it is an interesting perspective. However, I think the authors should make an extra-effort to sell this theoretical work to a broader community. NeurIPS has a vast audience, and having a better discussion of why studying these best-case lower-bounds is interesting. Even the gist of the discussion on fairness is deferred to the appendix. Bringing some of that discussion to the main body might already give a broader and strong motivation for the work. I really enjoyed the discussion from the appendix.\n\n2) On Section 3 the authors state that $\\mathcal{W}$ is a closed set, but do not mention necessarily that it is bounded. However, in the definition of regret itself the supremum may easily be infinite if $\\mathcal{W}$ is the whole space. On Theorem 1 something similar happens, where the authors assume that there is a optimal action in hindsight, which might not be true (again, take the feasible set as being the whole space). A more fine-grained analysis shows that the regret against some comparison point is dependent on the regularizer at this comparison point, so boundedness is not necessary for (at least some) results to follow. Since all the application in the paper only look at cases where the the feasible region is bounded, this is not a serious problem, but clearly stating these assumptions would be good. \n\n3) Another problem is that Theorem 1 requires the regularizers to be non-negative (not mentioned) and strongly convex (mentioned, but only inside the theorem, so it is not clear that the regularizers in the paper are assumed to be strongly convex throughout). These conditions **should** be explicitly stated and enforced, or at least the the statement of the FTRL regret bound should be adapted (subtracting the infimum of the last regularizer in the right hand side might be enough, but I haven't checked carefully). These assumptions on the regularizers and/or boundedness of $\\mathcal{W}$ would help a lot in making the analysis in Section 2 less bumpy (without boundedness or strong-covexity, taking the infimum of the regularizer over the feasible set can lead to $-\\infty$). In fact, if I'm not mistaken the authors themselves stumble onto these problems: on line 172 the authors *EXPLICITLY* use that the regularizer is non-positve on the entire feasible set. Applying this same regularizer to Theorem 1 we would have that the sup is also non-positive and we could get a logarithmic regret upper bound, and this is clearly false. Thus, this can make the readers very confused about which are the conditions required on the regularizers at each step for the results to hold. My suggestion is to adapt Theorem 1 for the case where the regularizers may be negative, but still strongly convex (and, thus, lower-bounded). But above all else, **make the assumptions on the regularizers clear**. (Another lesser point, the iterate from (1) might not be unique if the regularizers are not strictly convex).\n\n4) On Sec 4.2 the authors should be a bit more explicit about the difference between AdaGrad and your algorithm (linear approx vs whole function). But something that is bugging me that I did not have the time to verify carefully is the dependence on bounds of the p-norms of the gradient in the regret bounds. I believe this FTRL-AdaGrad algorithm should get similar bounds to the original linearized version (in particular, if the functions are linear these algorithms match exactly). Although this is not the focus of the paper, this extra dependency is a bit unsettling, and I couldn't verify the proof since it is not provided in the appendix. So I suggest you to give the proof in the appendix, if time allows. But beyond that, I think a careful analysis (possibly using the strong FTRL Lemma from McMahan) should yield bounds without the extra dependency on the bounds of the gradients. I'd really love the thoughts of the authors on that.\n\n5) The result on identifying exactly the best sequence for two experts is interesting, but I did not get much of the motivation for it. The discussion on why it shows that the previous result was tight is not clear (do you mean asymptotically only? Because the constants do not seem to match). But this part I might have simply misunderstood and is not a serious problem", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "cjYX3sTpXnS", "reviewer": "Reviewer_fZb1", "summary": "The paper establishes lower bounds on the best-case regret of the classical FTRL algorithm in online convex optimization. Specifically, the FTRL algorithm is considered in the general form where the regularizer can change over time (e.g., due to a time-varying learning rate). In the case of a fixed regularizer, it is known from earlier work that the regret is always non-negative, i.e., the algorithm never performs better than the best static expert. For time-varying regularizers, this is no longer the case, meaning that the best-case regret can be negative. The paper proves a simple generic lower bound theorem and applies it to several standard settings (Decreasing Hedge; a standard timeless method for decision-theoretic online learning (DTOL); an adaptive gradient version of FTRL), where it is found that the best-case lower bounds are roughly symmetrical to the known worst-case upper bounds on the regret (i.e., if A is a worst-case upper bound, then -O(A) is a best-case lower bound). In other words, these algorithms cannot outperform the best static expert by much, for any input. For DTOL with 2 experts, they show their lower bound to be tight.\n\nFor a different setting of the linearized FTRL algorithm, they show that an analogue result does not hold: Although the known regret upper bound is O(sqrt(T)), the best-case regret can be as low as -Omega(T).\n\nAn application and the original motivation for the work is in the setting of \"group fairness\" for DTOL: Here, time steps are partitioned into groups, and the algorithm knows which group the current time step belongs to. It is assumed that for each expert, the average loss per time step is balanced across the groups. Then recent work of Blum et al shows that the learning algorithm also has comparable loss in each group. This assumes that the time horizon T is known. This paper allows extending this result to an unknown time horizon, and shows an \"anytime\" extension of the result: If the assumption is strengthened so that for each expert, the losses are balanced across the groups not only after the last time step but also on every prefix of the input, then the learning algorithm also has balanced losses per group at all timesteps.", "questions": "", "limitations": "", "rating": 7, "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": "The results seem to be an interesting generalization of previous work by allowing time-varying regularizers. In particular, they show limitations on outperforming the best static expert in several standard settings (as would be necessary in a \"shifting regret\" settings) and the extension of previous group fairness results seem relevant. However, someone more familiar with the related work might be a better judge of the overall significance then me.\n\nThe paper is well-written and ideas easy to understand.\n\nMinor comments:\n- On pages 3-4, there are at least superscripts of w that should be subscripts.\n- line 175: factor 2 is missing eta_t\n- In the math after line 206 and after 209, it seems the terms on the LHS should be divided by the number of time steps in the group.\n- line 365: \"me\" -> \"be\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "asXscjt3Xi", "reviewer": "Reviewer_9AF3", "summary": "This work investigates the best-case lower bounds in the online learning setting -- meaning a lower bound on the regret value of an algorithm. Even though an algorithm is usually concerned with minimizing the regret and thus upper bounds on regret are used to describe algorithm performance, information about lower bounds on the regret can also provide information about the algorithm performance, its adaptivity, and in some cases certain notions of fairness. In this submission, the authors consider the FTRL family of algorithms, anytime (no prior knowledge of $T$) and timeless (first-order bounds), with constant, time-varying or adaptive learning rates. The results mainly show that the magnitude of regret of such algorithms stays within the range of the upper bound (or is nonnegative sometimes) with some exceptions. An application to online learning with group fairness is provided as a use case for such bounds.", "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": "This work concerns itself with algorithm-specific regret lower bound in online learning, i.e. characterizing not only how low the regret of an algorithm is guaranteed to be but completing the range of it. It is true that the upper bounds are the important part of an algorithm's guarantee, they indicate how well the algorithm is sure to perform. These best-case lower bounds simply provide more information in regards to the algorithm's adaptivity -- a truly adaptive algorithm should be able to attain $-T$ regret for certain sequences. On the other hand, these results can be used in devising \"fair\" online algorithms, e.g. ones with group fairness as in this submission, in which case negative linear regret is not desirable at all (informally, one is aiming to balance mistakes out uniformly). Overall, this is work that can have sufficient significance in completing the community's knowledge about the online algorithms such as FTRL types that are used ubiquitously.\n\nThe paper is written clearly, is easy to follow, and the results are presented in an honest and straightforward fashion. The main criticism in my opinion can be its significance, but I believe such work can encourage more results in this direction and resolve most such questions in several years. Applications other than fairness might be born along the way too. I believe this submission is ready for publication and simply have some questions to the authors.\n\nAs shown, FTRL type algorithms can have $\\geq 0$, $-\\sqrt{T}$ and even $-T$ (linearized) regret while all have $\\sqrt{T}$ regret upper bound. What is the end goal in characterizing such results then? Is the idea to exhaust all the algorithms that are around just to have the best-case lower bound results? Are there notions about what is desired? \n\nSeems like general minimax bounds can't be shown since $-T$ is achievable, so what can be said in a general manner that doesn't depend on a specific algorithm? And these results still don't rule out the possibility of an unknown algorithm having desired upper bound *and* lower bound properties, so pessimistically seems like there is nothing substantial to say in here.\n\nThe authors emphasize that their analysis applies to anytime algorithms: just a question, if you have analysis for known horizon algs, then can't you similarly analyze such the algorithm of alg + doubling trick which is anytime.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact was adequately addressed. Limitations of the work and possible future directions also discussed in a sufficient manner.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "NnsvBrxkqMY", "reviewer": "Reviewer_M8jx", "summary": "This paper studies the best-case lower bound, which characterizes the minimum regret that a specific algorithm can achieve in the most benign environments. The authors provide the best-case lower bound for the general FTRL algorithm and show that the bound can be applied for many instances, including Hedge with non-increasing step size, adaptive gradient FTRL. The best-case lower bound for the Hedge algorithm can be used to prove the group fairness in the prediction with expert advice setting. Case studies on the linearized FTRL and Hedge with two experts are also provided.", "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": "This paper provides a notion of best-case lower bound and analysis for the adaptive FTRL algorithm. The best-case bound is novel to me, and the analysis is simple yet general to be applied for many specific cases. In Section 3, the authors further show that the analysis can be applied to Hedge with time-varying step sizes, which can finally lead to group fairness in prediction with expert advice setting without knowing the time horizon in advance.\n\nAlthough the analysis best-case lower bound can be used to ensure the group fairness for Interleaved Hedge algorithm, I still quite catch the significance of this study in a more general OCO setting. It seems that the best-case bound is neither a good measure for the performance of algorithms nor reflects the hardness of the problem. I think it would be nice for the author to illustrate more the significance of the study in a more general case.  For example, what would imply if we could obtain a best-case lower bound for adaptive gradient FTRL (Section 4.2)?  \n\nBesides, I am confused by the title of Section 5. Why the $-\\\\Omega(T)$ best-case lower bound of linear FTRL is called \"negative result.\" Low regret seems good news for the OCO problem. Perhaps, the result is negative for achieving group fairness. But, the case study in Section 5 is presented in the OCO setting, and there is no concern about fairness. The confusion might be related to the main concern of the significance of the best-case lower bound in the OCO setting,\n\nOverall, although the paper shows that the proposed best-case lower bound can be used to achieve group fairness of Hedge, its significance in the OCO setting is unclear. It would be better if the authors can illustrate more about some more applications of the best-case lower bound.\n\n=====update=====\n\nThank you for the response. After reading other reviews and the author's feedback, my concerns are largely addressed. I would like to raise my score to a positive evaluation (7).\n\nMy original concern is that the motivation for studying the best-case lower bound in general OCO problem is unclear. By point (1),(2) of the first answer, the authors show that the best-case lower bound can be used to achieve group fairness beyond the expert advice setting. Although group fairness is an important notion, the extension could be limited to a narrow scope of audience. This concern is somewhat addressed by the third point, where authors have shown that the best-case lower bound can be used to show some negative side of the adaptive algorithms. For example, the adaptive FTRL does not perform that well in extraordinarily benign environments (it seems that the adaptive FTRL even is even inferior to the linearized FTRL in such a case). So, I am convinced that the best-lower bound can indeed provide a unique view to understand the adaptivity of the online learning algorithms.\n\nRegarding the second question, I think the confusion might come from a lack of further discussion about the best-case lower bound. For the fairness problem, the less negative regret bound means better results. But, that is not the case for regret minimization. So, I think it would be better to provide a more clear discussion about the signification of the best-case lower bound for both scenarios (especially for the regret minimziation part).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers all liked the paper, which seems to provide an interesting new take on analysis of adaptive online learning.

Decision: Accept (Poster)