Luckiness in Multiscale Online Learning
Authors: Wouter M Koolen
Muriel Felipe Pérez
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Learning
Multiscale Experts Problem
Second-order Regret Bounds
Stochastic Luckiness
FTRL

Abstract: Algorithms for full-information online learning are classically tuned to minimize their worst-case regret. Modern algorithms additionally provide tighter guarantees outside the adversarial regime, most notably in the form of constant pseudoregret bounds under statistical margin assumptions. We investigate the multiscale extension of the problem where the loss ranges of the experts are vastly different. Here, the regret with respect to each expert needs to scale with its range, instead of the maximum overall range. We develop new multiscale algorithms, tuning schemes and analysis techniques to show that worst-case robustness and adaptation to easy data can be combined at a negligible cost. We further develop an extension with optimism and apply it to solve multiscale two-player zero-sum games. We demonstrate experimentally the superior performance of our scale-adaptive algorithm and discuss the subtle relationship of our results to Freund's 2016 open problem.


Luckiness in Multiscale Online Learning
Muriel Felipe Pérez-Ortiz Centrum Wiskunde Informatica (CWI) muriel. pwwez@ewi.ie.
Wouter M. Koolen CWI and University of Twente wmkoolen@cwi.. .11
Abstract
Algorithms for full-information online learning are classically tuned minimize their worst-case regret. Modern algorithms additionally provide tighter guarantees outside the adversarial regime, most notably in the form constant pseudoregret bounds under statistical margin assumptions. We investigate the multiscale exten- sion the problem where the loss ranges of the experts are vastly different. Here, the regret with respect to each expert needs scale with its range, instead of the maximum overall range. We develop new multiscale algorithms, tuning schemes and analysis techniques show that worst-case robustness and adaptation to easy data can be combined at a negligible cost. We further develop an extension with optimism and apply it to solve multiscale two-player zero-sum games. We demon- strate experimentally the superior performance of our scale-adaptive algorithm and discuss the subtle relationship of our results Freund 2016 problem.
Introduction
The abstract problem of online prediction with expert advice Littlestone and Warmuth 1994 Freund
and Schapire 1997] is of fundamental importance in computational learning theory. Efficient and optimal algorithms for solving it have a substantial impact on various problems in general online convex optimization Hazan 2019] online model selection [Foster et al. [2017]. boosting [Freund and Schapire 1997], and maximal probabilistic inequalities (Rakhlin and Sridharan 2017). to name Tew. Concretely, decision maker chooses among experts' advices sequentially, and the environment assigns each advice a scalar loss. If all losses have the same numerical range [-or, or), the situation is well understood. Indeed, Freund and Schapire [1997] showed that, for K experts and rounds, the 2 In K. Furthermore, modern algorithms additionally guarantee lower or even constant regret when the sequence of losses is more benign [see De Rooij al. 2014, Koolen and Van Erven 2015 Mourtada and Gaiffas 2019).
Hedge algorithm guarantees the minimax regret (defined below) a 2t
In the multiscale setting, where the experts' loss ranges may differ by orders of magnitude, it is natural to ask about the existence of algorithms that guarantee an optimal worst-case regret bound that scales with the loss range of the best expert instead of the maximum range. This question has been answered affirmatively [Chen al. 2021 Bubeck et al.) 2019 Cutkosky and Orabonal 2018 Foster et al.. 2017]. The algorithms developed in this line of work have had a significant impact in different areas of computational learning theory and practice. Unfortunately, as we will see, the best known algorithms still fail to guarantee lower regret even for the simplest benign statistical cases. Ensuring these goals poses serious technical challenges. In particular, Bernstein's inequality, the engine of classical same-scale luckiness arguments, has no suitable multiscale upgrade. Moreover, intuitive candidate upgrades of same-scan results would contradict recent lower bounds (see Section (7). To make things worse, in order to obtain multiscale regret bounds, close attention needs to be paid to terms that are conventionally insignificant but now carry the maximum scale of the problem. This motivates our main question: can single algorithm huve multiscale worst-case regret guarantees and, in addition, exhibit constant (pseudo)regrer in stochastic lucky cases?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We answer the previous question affirmatively. The key contribution in this article is MUSCADA (multiscale adaptive), a computationally efficient algorithm that simultaneously guarantees a worst- case regret that grows with the scale of the best expert, and constant expected pseudoregret under a stochastic margin condition. MUSCADA uses a refined version of Follow the Regularized Leader based on the multiscale entropy of Bubeck et al. [209]] Its crucial improvement is a second-order variance-like adaptation, the tightest possible for the analysis of this regularizer. This second-ordes adaptation is close in spirit to, and an improvement of, that of AdaHedge by De Rooij et al. (2014)
and those Chen et al. [202T] J. As a result of careful analysis, MUSCADA has the following attractive properties: it does not need knowledge of the length of the game in advance without resorting to
any doubling trick, the presence of zero-regret rounds does not change the state of the algorithm or
its regret guarantees; it is invariant both under per-round, possibly unknown, translations of each expert's ss losses, and under a global known scaling common to all losses and ranges.
As an application of MUSCADA and its analysis techniques, we build an optimistic variant of the algorithm and use to solve two-person zero-sum games that have a multiscale structure. The optimistic variant makes use of a guess of what the losses in the next round will be, and achieves lower regret when the guesses are adequate. This interest originates in the fact that optimistic algorithms converge to the solutions of such games at faster rates than their nonoptimistic counterparts (Syrgkanis) jet al. 2015]. We find experimentally that MUSCADA outperforms existing single-scal algorithms when the payoff matrix of the game exhibits multiscale structure.
In the rest of this introduction we lay out formally the multiscale experts problem, review existing work, present summary of the main contributions (Section 1.1 and outline the rest of the article.
Full-inforrmation online learning. In its simplest form, we must decide sequentially in rounds how to aggregate the predictions made by a fixed number K of experts. At each round t, we choose an aggregation strategy, a probability distribution wt PPK) over experts. After choosing wt. we assess the quality of the experts' predictions with numerical loss & (Lg,))EK and judge the performance of our aggregation strategy by the w,-weighted losses (w,, L,) ΣxER Wr,KLe, Our objective is to minimize the cumulative gap between the losses incurred by our aggregation strategy /. - wy, and the best expert in hindsight. This cumulative gap is the regret R. = Σ (w., La) minkeK Σnm le,k- Other than range restrictions on the losses, no assumptions are made about the mechanism that generates them. More precisely, for each expert A E K and all rounds I, we only assume that lx,e E [- σ for known nonnegative scales [ We call R. the vector of regrets with respect to each expert, that is, the vector with entries Re = = ((w,, La) - la
Existing results. Several algorithms have been proposed that achieve the worst-case regret in the multiscale setting, but none of them achieve constant regret in stochastic lucky cases. Motivated by the problem of online model selection, Foster et al. 2017 used a technique of adaptive relaxations to produce randomized algorithms that guarantee
Ep & O ( /(nn + In(1 m + In(ax//minn) as (. 00,
where π is a prior distribution on experts that generalizes the uniform 1/K of the Hedge algorithm and the expectation is over the algorithm's randomness. [Bubeck et al. [2019] first proposed a Follow-the- Sellow-thh-Rguulrizeeee Regularized-Leadee algorithm with multiscale entropy regularization that guarantees
RA, = (o% (o tttn/tnn + In(omaxxoonin
as 00
when the number of rounds / is known in advance. Bubeck et al.) 20019 Theorem 20] also construct an instance of the K- 2 experts problem in which there exists a time t for which any algorithm must have Re, 2 oee / (In K In (amaxx (onax//opae /mmi)) )} for some expert K', shedding some light on the minimax picture. Recently, Chen et al. [202T] designed an optimistic algorithm that uses the same regulatization as Bubeck et al. 2019] with an additional ingredient: at each round, a second-order correction is added to the losses before computing the next round's ''s weights. At every round, their algorithm makes use of a guess vector m, that can depend on the losses up to time 1. The scale of the guesses m, are assumed to be the same as that of the losses; |ma,el S o&- For instance, valid choices for the guess m, are O and the loss 4-1 of the previous round. The algorithm of Chen et al. [022] achieves
R₂, = O (O(v Be Ind + max Int) as + 00,
2

---

now scaling with the expert-dependent "time" Be, = (b-=-m, I 4t. Furthermore, they o%
show that different single-scale tuning of their algorithm exhibits stochastic luckiness. Namely, if the losses are sampled from distribution with gap dmin between the expected loss of the best expert k* and that of any other expert, their algorithm guarantees that
Int
RE Op
as o0,
diii
where P the distribution of the losses. Their technique for stochastic luckiness uses the upcoming learner's loss the guess Me,, = (wr, Lx). Unfortunately, this approach cannot be extended to the multiscale case, as these guesses may violate the experts' loss ranges.
1.1 Main results
In this section we present succinctly the regret guarantees for MUSCADA. Firstly, we present multiscale worst-case regret guarantees. Secondly, we present the stochastic luckiness results and Massart's s margin condition. We then prove analogs of these results for an optimistic modification of MUSCADA in Section 4 We close this introduction with an outline of the rest of the article.
Worst-case bounds. We propose two tunings for MUSCADA; they cover the cases where there is or is not expert with loss range equal zero. Our results imply Theorem [eceorem[.]]bellee beloo: it contains the regret guarantees for MUSCADA, expressed in terms of Uz. an implicitly defined variance-like second-order data-dependent quantity. The quantity Ur, defined by the algorithm, allowed by our analysis and enables our luckiness result, Theorem 3.1 We interpret it through the upper bounds of Theorem 1.2, also below, as an internal scale-free measure of time, as i S 4t.
the tightest
Theorem 1.1 (Regret Bounds). Consider MUSCADA, t + defined in Figure] 7 and any initial probability distribution ा.
If mmin = minkeK σ > 0, Tuming 1 guarantees, for any loss sequence,
R1 S cα (lm(/mm)) + In(ox/omin)) + 0(1) as - 00;
(1)
where e is constant depending only on The constant c is well-behaved: if m'XaaX T - E, then S. 4v2(11 1/22mm/ +
Even if minkeR d% = 0. Tuning ensures. for any loss sequence,
R S 2 ve (In(1/Tx) + In(1 (1) o(1)) as t oc.
(2)
The following theorem (proven in Appendix G shows that v bounded by a second-order quantity. If wr,k are the weights played by MUSCADA at round f and 7h- are its learning rates, is bounded by the variance over experts of the losses w.r.t. tilted probability distribution Wr, X Wr. 1,1-- The shape of this quantity may seem surprising, but it is not artificial; our analysis shows that it is the tightest and, consequently, the natural second-order quantity associated this choice of regularization. In Appendix G we further motivate, via a Taylor approximation, the shape of the resulting upper bound.
Theorem 1.2. Let Wr.k be the probability distribution Wi.k We 1,6 and let Av U/ 04-1- satisfies
Then, with either tuning from Figure 2 Ut. from Figure 7
Au < var@ (le) (w) 2
< 4.
where
var (ex) = (1i:, (E+ (wi, 22)
Stochastic luckiness. We now turn to our results for stochastic easy data. Not all stochastic scenarios are easy (in fact, worst-case regret lower bounds are proved using stochastic data). We use Massart's margin condition, a standard benchmark for easy data.
Definition 1.3 (Massart's easiness condition). The losses l, l2.... satisfy Massart's easiness condition if they generated i.idd. from distribution P with the following property: there exists constant Cм and an expert k* E such that
Ep[(er, - (e,x- ) S CMEP be,k-]
for all & K and 2 1. In that case, A² arg min Ep (c..) for all t.

---

Massart's s condition is implied by more interpretable gap condition [Koolen et al. 2016, Lemma 3]. If there exist gap dmin > in expectation between the loss any expert and that of the best one k", that is, if, for every lo o k., Ep (f] 2 dman + Ep (1,x=), Massart's 's condition is satisfied with CM 1/dmin- We show the following theorem.
Theorem 1.4 (Constant regret under Massart's 's condition). Under Massart's 's condition (Definition I.3 MUSCADA with either Tuning I or 2 has constant expected pseudoregre over time, that is,
Ep 1
Outline. The of this article is organized as follows. In Section 2 we introduce and analyze MUSCADA. In Section [ we state the main results on stochastic luckiness for MUSCADA. In Section E we introduce
optimistic variant of MUSCADA, give remarks about its numerical implementation in Section and apply it to accelerating the solution of multiscale games in Section 6 We end this article with discussion of our results in Section
2 The MUSCADA Multiscale Online Learning Algorithm
In this section, we describe our algorithm and motivate its design. We present two useful tunings and prove the corresponding worst-case regret guarantees. For the sake of intuition, we specialize the algorithm to the case of same-scale experts with uniform prior and compare its resulting closed form to AdaHedge (De Rooij et al. 2014). Stochastic luckiness results are found in Section We begin by introducing some notation.
Notation. We use boldface type for vectors in R (Re, L,, pe, Tr. σ, u) and distributions on K experts (p, w. TT. We number rounds that all quantities indexed by & depend on the information witnessed by the learner in the first t rounds. Exceptionally. we use weights w; at round f. For two functions f and we write "f = Og)) as t oc" if there exists > 0 such that lim;-+oo f(t)/((t) < c. Similarly, we write "f(t) ~ (t) as t - 2o" if lim,- f(t)/g(t) = 1, and f S g if there is c > so that S cg. We denote the simplex of probability distributions K experts by P(K) and use K interchangeably for a number K E N and the set (1,..., [,...,,), K}.
We define MUSCADA in Figure I and give its two main tunings in Figure 2 At round f, after observing cumulative corrected losses L + M4-1, MUSCADA plays weights
Wr.k uge (4
where Ws > 0 is tuning parameter related to the prior weights, Vi=1 are learning rates that decrease over time, f4g are corrections incrementally computed at every round, and the scalar a;_1 ensures normalization (see Lemma F.7 The weights w, are reminiscent of those played by the Hedge algorithm, but the normalization at cannot be computed explicitly in general. The weights w, are the result of Follow-the Follow-the-Regularieee regularizer employed is the multiscale entropy: for fixed u its Bregman divergence is
update on a vector of corrected losses L,-1 + 44-1. The
In(wx/ /ux) (1 us/wk)
ト Dw u.)
wk
E P(K)
1]
KEK
2021]. The goal substracting the dependee second-order corrections #4; from the experts' regrets is to keep scalar potential function & negative. Here, the potential H 4, is defined by convex conjugacy with respect to the multiscale entropy as
[see Bubeck et al., 2019 Chen et al.
Φ(R, Pt, nc)
WEP(K) (w, R. pa) Day (w, (1),
for which Wi+1 is the maximizer. The corrections μ4 and the consequent negativity of the potential i are the main ingredients in the regret analysis of MUSCADA. We next motivate these choices.
The shape of the corrections μ4: We designed MUSCADA favor experts with low corrected regret R,- μ4,- For the sake of informal discussion, goal is to obtain μ4, Rs o&yuu /v, In(1/TT)) TT). The algorithm achieves this by additively correcting the regrets in each round. Indeed, from the analysis
of entropy-regularrized algorithms, one would expect learning rates of the shape Th & Rs 1. [mml1/m))
81

---

Parameters: A vector 0 of initial weights, initial strictly positive learning rates No, & 1/(2))), and real, continuous nonincreasing functions Hę IR+ - with (0) Initialization: Let Po, = 0, to = 0. Ro = 0 and Lo, = 0. For each round = 1,2.3....
1. Play (follow the multiscale-entropy regularized leader of the corrected losses)
Wp arg min wEP(K)
L: + pc-1) + D 10:-1(2; u)
(w,
(5)
where D, is the multiscale relative entropy given in 3b.
2. Observe loss L. Update Rt, = R + (we, Li) Ee and Lt = L1-1,8 + lek-
3. Compute Au, the value Av such that
(RR. P4-1 o ' n AA.
1b o( 11-177--1) m1-1) -
(6)
where & is the potential function defined (4)
4. Compute Aju,s o 1, Update Mr. 14-1, Ayt,e and - + Avt.
5. Set the new learning rate 4 = 1/o,k (v)).
Figure 1: MUSCADA
to be optimal. With this learning rates in mind, the desired correction μ4 can be approximated using a Riemann-sum approximation of Vu, = I' 2o Indeed, for the conjectured learning rates, our target Pt.k satisfies Pe, o E.ge ? 1,-1, where Ar; = 1 - 4/-1- This implies that the choice A = - as our per-round additive correction is helpful for achieving our goal. We discuss precise choice of learning rates after the formal statement of Proposition 2.2 below.
Negativity of t. Our regret bounds are a direct consequence of the negativity the potential t + pt. Indeed, by its definition, ty I 0, and, because of our choice of nonincresing learning rates and corrections, the change in potential A = Q P.-1 can be bounded by
AØ, < Φ R. 14: 7 1) + R 14-11 7) 7/-1) 0,
where the last equality follows from (6) the choice of corrections Apt. This implies the following lemma, of which we give more general proof in Section C.I
Lemma 2.1. The potential f - c starts at t S 0 and is decreasing for t 2 0.
Once we prove that the potential + is negative, we are ready to derive regret guarantees for Mus- CADA. The maximal nature of the potential t. + o; and its nonpositivity together imply that, simultaneously for all distributions p E P(K),
(p, R. Me) < Dr, (p, u).
We choose p concentrated on each expert k: K deduce the next proposition (proof Section C.I Proposition 2.2. Assume that the learning rates Tp. are decreasing. MUSCADA guarantees that, for any 1= 1,2,3, and all & E K,
In(1/ux)
Uj
Re, S Me, +
(8)
Tt.
T/t,j
jEK
where H4, of E.ES No- Av. Furthermore, for Tj. 7o as in Figure 1
μg satisfies
Me, o.no. (" Ha(x)dx + oR Tp,N) max Av..
Choice learning rates. Proposition 2.2 guides us choosing the learning rates presented in Figure 2
The starting value of the learning rates influences our ability to control in terms of the variance of the losses the algorithm while their behavior for large v, determines the long- term growth of the regret bounds. The learning rates presented in Figure interpolate smoothly
5

---

Let P(K) be probability distribution on K experts.
Tuning 1 Requires min O. Set ug Ty
Smin 10,
9k 82imax 1n(1/2x) and
ok 20max
d
H1,((1) du
4/74+2
2(1-0/70)873 V100/6
Tuning 2 Set un = Tk, 10,, 20max OCk 32
"ma of
= Or In (1/z)) and
d
[o22 (1 (1+1//// In + v/ - 1/ w/ook 2(1+0/(276))
H2 = de
a In (1 + (1 + 2n 2
(1+00
2 {(1 + v/ax) In (1 v/ax) u/an} + 2(1+0/(27e))
v²
for some k, o% 0, define H2 be the limit value limo (2))( 1.
Figure 2: Tunings
1i.k to, H (w:) and n = 'oo H2, (w+). Here, the starting learning rates are set to 7uukk = m2/ The functions H1 H2, I 1 decrease monotonically from their initial values H1 H2) = 1 in such way that, as U 00.
between these two regimes by taking the form (1)
V2 Ok
ln(1/=k) Ut
V2
In mx) In
(1) Mi.k
and
(2) Wi
ok
0t
(1)
The asymptotic expresion for Wi.k is reminiscent the optimal learning rates for the Hedge algorithm with the number of rounds replaced by the refined v2 and the uniform In K replaced by In(1 (1/Tx)). Finally, with the Riemann sum bound (9) from Proposition 2.2 in mind, the learning rates were chosen the derivatives of functions that will become the dominant term in the regret guarantees.
Tuned regret bounds. The learning rates from Figure can be readily used in Proposition 2.2 derive regret guarantees for MUSCADA. However, to facilitate interpretation, we bound the learning rates and their reciprocals in order to obtain the regret bounds contained in the following proposition (proof in Appendix C.2). After its statement, we prove Theorem [.1 from the introduction.
Proposition 2.3. Let be probability distribution on K.
MUSCADA run with Tuning depicted in Figure 2 guarantees that, for any f = 1,2,....
R1, S 20 20, In(1/))))))))))) + Co, n min v 20 + 80 1n(1/m/ 40 +
0k
max Aes, (10)
2
a5t
where the constant Ca. = EKEK TA (1/ (11//nn(1///) and us = T. Tuin
MUSCADA run with Tuning depicted in Figure
guarantees that, for any t 1, 1.......
Re.k S 2 (In (1
vvv. 320
+ In(1/T=)) +oR In(1/=x)) Zx
Σ
max Aut.
jEK
22
min (1/xx))))) IGo
= 0 (v
where 74
1
11 luve
122
x.
r
2lu
1+
320
1+ 32 max

---

Proof of Main Theorem 1.7 With Proposition 2.3 at hand, we can prove the claims made in Sec- tion Use the fact that o min S T2 to conclude from (T0) that, as t oc,
R1, S 20 20 22, ln(1/4x + 20 Th kV 20r + O(1).
We can bound Co / /In(1/u3 S 1/ [n(1//111///1 mmx)) where Tmax maXKEK K Tk. Consequently,
Re, S 2 {1 1/ (2)+++))))+ 220, In(1/ug) + O(1)
as any time that max
This coincides with I Similarly, 11 implies
2.1 Closed-form solutions in the single-scale uniform-prion
To help in the interpretation and to illustrate the challenges of the multiscale problem, we instantiate MUSCADA a situation where all calculations can be carried out in closed form: when all scales are the same and equal to ar, and the initial weights Unif are uniform; TUnif & = 1/KK This is the setting in which AdaHedge by De Rooij et al. (0014) operates. In this case, the learning rates and corrections of MUSCADA are the same for all experts; A π) and Aj4,k Ap4. The potential 4 and the corrections Aye take the familiar form
p.
1 T
1 K
C.. ) and
Apc
In Σ we 1((m).))-e)))
T7--1
kEK
kEK
These two quantities play a central role in the analysis of AdaHedge, where De Rooij et al. 2014 called Au4 the mixability gap, the difference between the average (we, le) and the mixed average In ΣBER Wr 1 The main quantity in our analysis, Av, becomes
7l-
AC
W (((o).)))) -le))
12-102 KEK
Using well-known estimates for cumulant generating functions, Au can be bounded by the ratio var w. (lz)/o². Indeed, Hoeffding's 's inequality implies the worst-case bound Ae, S 1. Bernstein's the second-order Au, S varw, (fe)/o². Since it is i that appears the regret bounds in Proposi- tion 2.3 they are refinement over those of AdaHegde[ Additionally, the present analysis yields improvements that are apparent in lower-order terms. Indeed, the last two terms in the regret bound (8) in Proposition 2.2 vanish, and the analysis used in the proof of Proposition with with n/ v2/a and the instantiation of Hi from Figure 2 11 (1(x) 2(1+0/ ()(3) give the regret bound
2/ =/In(K)-2
Clou C20 In K + 0/2 20 22, K + 0/2
vf S In K, if > In K
R2 5
with c = 3/V2 and 02 1/v2.. Unfortunately, multiscale analogs of Bernstein and Hoeffding's inequalities on Ae, are not available; considerably more technical work needs to be carried out to prove Theorem [.2] A multiscale analog of Bernstein's estimate for Av, is only available when all the learning rates are smaller than 1/(20 max) (see the proof of Theorem 1.2 in Appendix G
3 Multiscale Stochastic Luckiness
In this section we show, under easiness conditions, that the expected pseudoregret of MUSCADA constant. Assume that the loss vectors L,, f2... are i.i.d. and are generated according distribution P that satisfies Massart's 's easiness condition (see Definition 1.3). For Tuning 1, assume that the minimum scale among experts Twin is strictly positive. The analysis technique in this case is similar to that of Koolen et al. 2016 with extra step. A use of Theorem 1.2 shows that Ar; can be estimated in terms of var w. (4) This estimate possibly incurs in a multiplicative factor that can be as high as 1/02 //o... There are examples for which this constant is necessary (not shown). After this, standard arguments show that the expected pseudoregret is constant. See Appendix for proofs.
Our algorithm with learning rate tuning function (vv)=
I comes closest to AdaHedge.
7

---

Theorem 3.1. Under Massart's condition and using Tuning from Figure 2 the expected pseu- doregret of MUSCADA bounded by a constant in the number of rounds. Specifically, for any t 1 0,
Ep adoom +
{ 1 In(1 Haloe where 1 mmax,,j { asa; (1///))) (nmm b max In(1/ux=) + 4a + 20r..
} (40 (2ln(1/ux)) + 2 x and
For Tuning 2, where we do not assume that min > O, still Ep [ S using different proof technique. Using the expression for the weights of the algorithm, we show that they concentrate on the best expert k". The analysis here is similar to that Mourtada and Gaïffas (2019). but the lack of an expression for the normalizing aj presents with an additional technical difficulty. The result the following theorem.
Theorem 3.2.
Let de = Ep|<LA lxxx=] and assume that min dy > 0. Using Tuning 2 in Figure MUSCADA guarantees constant expected pseudoregret. Specifically,
Ep (R Es f(dk), KEK
where f(d) 0
mmax In
) d - O.
Standard modifications of the arguments presented may be used to prove that the pseudoregret is constant with P-high probability (not shown).
Optimism
In this section we show an optimistic variant of MUSCADA. Suppose that, before round I, count on guesses m, for what &, will be. Assume that m, is the same scale as l,, that is, |m,,x S dk- In particular, this entails that [e, mm,k < 20k. A modification of MUSCADA, presented in Figure [ puts these guesses to good use. These modifications allow for regret guarantees similar to those contained in Proposition 2.3 but in this case Auf I var (fe mz)/ (wff , where the superscript o signals the optimistic analogs of the quantities from MUSCADA. These modifications shown in Figure 3 and the regret bounds in the following proposition (proofs in Appendix DD-
Proposition 4.1. Ift + vi is the variance process defined by Optimistic MUSCADA in Figure 3 the same regret bounds presented Proposition 2.3 3hold with two modifications: vf instead of 0t and all scales doubled, that is, 20 instead 4 varm; m (le m.)/ (w0 o I 4t, where w. x -.
Furthermore, for each t 1,2,..., Ae? <
1' Compute the guess m, and play
e = arg min (w. L,-1 + m. + p1-1) - D (w
WEP(K)
3' Let Aug be the value A 2 0 such that
D(Re-HI-1 HI-1 70-10² Au 7h-1) = ( mm)) -m; - 7-11) (12)
Tuning 1' and Tuning 2'. As Figure but with halved starting learning rate 7o0, 40man
Figure Optimistic MUSCADA, given as update w.r.t. Figure
5 Computation
At each round, MUSCADA requires two computations. We now argue that both can be executed to machine precision in O(K) time. First, computing the weights (5) given the losses L,- and correction terms 14-1 can be reduced, by Lemma to a single scalar convex minimization problem. Cancelling the derivative of the objective amounts searching for the normalizing offset ae. To that

---

10²
80
Easy Hard
Juning='(--.a) Tunings' (o)
Saddle Point Gap
Gmax't bound
60
100
Craaft bound
Regret
40
10-3
10-6
2500
7500
10000
10
10
10
10
10
Rounds(t)
Rounds(t)
Figure 4: Left: empirical mean and quartiles of 2000 realizations the regret H R of MUSCADA, For easy ii.d Massart distribution, the regret is constant; for hard distribution without gap, 2( ((vt). Right: optimistic MUSCADA (solid red) achieves iterate-avcrage saddle-point gap of Treal/t where Treal max/100 is the relevant scale the Nash equilibrium. Other methods scale as maxx/t.
end, binary search to machine precision takes OK) time per round. Notice that this also allows us to compute the potential value. Second, for computing the variance contribution (6), we observe that the right hand side of (6) is decreasing in Ary Since the potential can be computed O(k) time, we use an outer binary search to compute Au, to machine precision in O(K) time well. Alternatively, Newton's method may be employed; both of the previous problems require finding root of convex function. When deferring to convex optimization library, convenient expression the jointly convex minimization form (see Lemma F.6)
t L.v( (e)) -a)--Ppa fLN x- 1 S 0.
Au inf Au subject to A,
Wt.k
17-1,
kEK
6 Experiments on Synthetic Data
We investigate the performance of our multiscale method on two experiments: one for illustrating the performance MUSCADA under Massart's condition, another for solving multiscale two-player zero-sum games.
The aim of the first experiment is compare the performance of MUSCADA in easy and hard stochastic data sequences. To this end, we compared sequence of hard stochastic data with no gap vs. easy data sampled i.i.d. from distribution satisfying Massart's condition. We witnessed constant regret for the easy data, as shown in Figure 4 (Left). We take K 50 experts and set data, fix some mean A [-oky σk] and generate binary expert losses lg,k E {-Tk, + independently between rounds and experts, with probability
a 1/K for each & E K. To generate
P [L, ) tA For the hard case, we set A 0 for all k. For the lucky case, we set A₂ 1/5 instead. Generating this figure with the code in the supplementary material takes seconds on an Intel i7-7700 processor.
The aim of the second experiment is to show the performance of MUSCADA for solving multiscale zero-sum games. Here, the payoff matrix is unknown, but row and column scales are available and vastly different. As detailed in Appendix A
two instances of appropriately tuned Optimistic MUSCADA against each other. As shown in Figure 4 (Right), the pair of time-average iterates converges to the saddle point with suboptimality gap of order Treal/t instead of the worst-case Fuax/ t. where Treal the maximum range within the support the saddle point. In Appendix conjecture that this rate holds for any such game and prove weaker result: without optimism, the slower but scale-adaptive rate reelt/ Vt achieved.

---

7 Discussion
We developed new algorithm for multiscale online learning that is both worst-case safe and achieves constant pseudoregret in stochastic lucky cases. Our method is a refinement of the Follow-the- Regularized-Leadee template with a weighted entropy. The main innovation is in the correction terms added to the losses, which are the tightest the technique admits. This suggests that these variance-like terms are in fact intrinsic to the problem of obtaining scale-dependent regret bounds. Lastly, we relate this newfound variance to the variance asked for by Freund] (2016), we comment on the advantage of second-order guarantees over zeroth-order ones, and we state an open problem.
Quantile bounds and solving Freund's problem. Freund (0066 asked whether quantile adaptivity and variance adaptivity are compatible, that is, whether one can have Rs) S
V /KL(,, u) Eeso var (f,) for all comparator distributions p E P(K) simultaneously. Even though our tuning of n7 does not yield quantile bounds, these can, however, be added employing a now-standard method [Koolen and Van Erven 2015). Namely, instead of only including every expert with a private learning rate tuned to its prior complexity level (the typical in K or (n(1/Tg) term), we include multiple copies of each expert, each with a learning rate tuned to a smaller complexity level. We then start from 7 with comparator distribution p concentrated on the e-quantile of interest and carry out all future steps (from Proposition 2.2 on), ending up with the quantile regret bound (p. R&) I ma 2x / U/ (In C + D (P. JJ), where C is the number of learning rates thus created. As these learning rates can be exponentially spaced in an interval of width In K, C' is of order In In K. Does this procedure answer Freund's question? For our notion of variance, vt. which our results suggest is a rather useful notion, the answer is yes. However, to relate Ar, to varw. (e,), we incur multiplicative ratio T/t,aax/ / min, which, for the quantile case, is of order bound into a prior-outside-tth--suaaaee
bound. The latter was already achievable by not tuning 77 to the prior complexities at all. This problem does not arise in the same-scale uniform-ppl -ario case; there, Au, is bounded by a small multiple of var (l,) [De Rooij et al., [0144). Note that this problem is present even when K is fixed while t grows. which is narrowly outside the scope of the impossibility results of Marinov and Zimmert (202T). This discussion sheds light from another angle on why Freund's problem is hard; we present a desirable multiscale alternative.
VIn turning the tant-in-the-quarree
Luckiness, gap, and Massart's condition. We now address the advantage of MUSCADA'S refined second-order measure of time i/ over the zeroth-orde number of rounds t. Multiscale zeroth- order regret bounds (growing with t) can be guaranteed either by tuning MUSCADA crudely to a constant multiple of / or by building an any-time improvement of the algorithm of Bubeck et al. [2019), also tuned to I. Both (-tuned and ey-tundd algorithms have constant expected pseudoregret stochastic lucky cases, but the constant can be widely different. Indeed, the constant for (-tuned algorithms scales with the inverse 1/dmin of the gap amin = min E(e,, - f,,x-), while the constant for ve-tuned algorithms scales with the constant CM from Massart's ' condition (see Definition 1.3) The difference stems from the fact that CM is at most 1/dmin- but it can be arbitrarily smaller. This separation appears to be fundamental. In the single-scale uniform-prie -prior case, the above t-tuned algorithms are closely related to Decreasing Hedge [Mourtada and Gaitfas 2019]. just as MUSCADA is related to AdaHedge (see Section 2.I). [Mourtada and Gaiffas [2019] show that, in the single-scale case, even under Massart's 's condition with сы = 1, Decreasing Hedge and, consequently. [ubeck et al. ss algorithm with decreasing learning rates, has expected pseudoregret E[RØ, 2 1/dmin- If the smallest scale miin O, by taking dmin small, this lower bound can be made arbitrarily worse than the guarantee of MUSCADA, E [
MUSCAADA] S CM + 1, from Theorem 3.1
Open problem. Our ability to incorporate an arbitrary prior suggests that the results should extend to countably many experts. However, the current techniques do break down. When max d < oo MUSCADA with Tuning (if inf a% > 0) or Tuning 2 would still deliver the worst-case bound. Yet our luckiness result currently requires max3,1.1 n.
f < xo. Even with a common scale o,
this is never the case due to the dependence of 7) on the prior π, which is necessarily decreasing. Is luckiness actually possible, for example, in the online learning analog of the elegant challenge example presented by Talagrand 20044] Chapter 2]?
10

---

References
Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang, and Rad Niazadeh. Multi-scale online learning: Theory and applications to online auctions and pricing. Journal of Machine Learning Research, 20 (62):1-37, 2019.
Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications. arXiv:2102.01046 [cs], June 2021. arXiv: 2102.01046.
Ashok Cutkosky and Francesco Orabona. Black Box Reductions for Parameter- free Online Learning in Banach Spaces. In Conference On Learning Theory, pages 1493-1529. PMLR, July 2018.
Dylan J. Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter- Free Online Learning via Model Selection. In Advances in Neural Information Processing Systems 30, pages 6020-6030. Curran Associates, Inc., 2017.
Yoav Freund. Open Problem: Second order regret bounds based on scaling time. In Conference Learning Theory, pages 1651-1654, 2016.
Yoav Freund and Robert E. Schapire. A Decision-Theoretcc Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1):119-133) August 1997.
Elad Hazan. Introduction to Online Convex Optimization. arXiv:1909.05207 [cs. math, stat], September 2019. arXiv: 1909.05207.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages
PMLR, 15-19 Aug 2021.
Wouter M. Koolen and Tim van Erven. Second-order Quantile Methods for Experts and Combinatorial Games, In Conference on Learning Theory, pages 1155-1175. PMLR, June 2015.
Wouter M Koolen, Peter Grünwald, and Tim van Erven. Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning. In Advances Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Nick Littlestone and Manfred K. Warmuth. The Weighted Majority Algorithm. Information and Computation, 108(2):212-261, February 1994.
Teodor Vanislavov Marinoy and Julian Zimmert. The pareto frontier of model selection for general contextual bandits. Advances in Neural Information Processing Systems, 2021.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20(83):1 1-228, 2019.
Alexander Rakhlin and Karthik Sridharan. Equivalence of Martingale Tail Bounds and Deter- ministic Regret Inequalities. In Conference on Learning Theory, pages 1704-1722. PMLR, June 2017.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
Steven de Rooij, Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the Leader You Can, Hedge If You Must. Journal of Machine Learning Research, 15(37):281-1136, 2014.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast Convergence of
Regularized I. Learning in Games. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Michel Talagrand. Upper and Lower Bounds for Stochastic Processes, pages 1-12. 01 2014. ISBN 978-3-642-54074-5.


Reviews:
[{"review_id": "mvf0hhoIMpa", "reviewer": "Reviewer_eZu6", "summary": "The paper considers the setting of prediction with expert advice where the (known) loss ranges for each expert ($\\sigma_k$ for expert $k$) may vary drastically (the “multi-scale” setting). They improve existing regret bounds that currently have the optimal dependence on $\\sigma_k$ by replacing dependence on $t$ with a novel variance-like term $v_k$, which they show leads to constant regret in the multi-scale stochastic-with-a-gap setting. Until now, constant regret was only known in the single-scale case; the multi-scale case resulted in regret of size $\\log(t)$. They also extend this to an optimistic variant, and apply this in the now-standard way to the game-matrix setting.", "questions": "1. If you pick an expert to compete against, the $\\sigma_k$’s do not need to be known in advance. Can the authors confirm that there are *no* multi-scale results that similarly do not require $\\sigma_k$ knowledge, and can they comment on whether relaxing the assumption of their prior knowledge seems possible?\n\n2. Can the authors include in their simulations a comparison with multi-scale dependence on quantities that become small in in stochastic settings, such as the adaptive variants of PROD? This would be useful to see that they do not obtain multi-scale constant regret in the stochastic setting, and it is not just the fact that we don’t know how to prove they achieve this because of the limitations of Bernstein’s inequality.\n\n3. The author’s arguments seem to rely rather heavily depend on limiting statements in $t$. It would be good if they can state some finite-time bounds (with additive errors that may be bounded as $t$ gets large) to allow for comparison with other finite time regret bounds for quantile regret, even if the main informal theorem statement is asymptotic in $t$ to highlight the salient terms.\n", "limitations": "I see no negative societal impacts of this theoretical work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is very clearly written, provides a well-defined and useful contribution that I think will be valued in the literature, and does so using some new algorithmic and technical tools that can hopefully be reused. I read the proofs at a high level and did not find any issues. I have no major concerns, just a few questions for the authors that may help place this work in the literature slightly more clearly and provide a picture of what the follow-up works might be. ", "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": "OKioU7ufsLc", "reviewer": "Reviewer_jvH3", "summary": "In multiscale online learning, the range of losses differs from an expert to another. People aims at designing algorithms with regret depending on the scale of the best experts instead of the maximum scaling. Several algorithms have already be proposed in the literature with worst-case analysis. However, none of them achieves a constant regret under Massart's condition. The authors introduce a new algorithm called Muscada which entails similar guarantees as previous algorithms in the worst case but also achieves constant regret in benign statistical case (Massart's condition). They also analyze an optimistic version of their algorithm and conduct numerical experiments.", "questions": "Would be interesting to compare numerically Muscada against FTRL with multiscale entropy (without your refinement).\nDo you observe non-constant regret for other algorithms under Massart distribution ?\n\nTypos:\nl.232: incurrs -> incurs \nl'281 an refinement -> a refinement", "limitations": "As discussed at the end of the paper, the main limitation is that it does not extend to countable may experts but it offers a good opportunity to future work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work follows the line of research of FTRL with multiscale entropy regularization. The main contribution is to refine this method with corrections terms added to the losses and to give an analysis under Massart's condition. But it is not limited to this key result and explore several aspects of the proposed method with an analysis of several tunings, an optimistic version, a discussion with Freund's open problem...\nThe paper is well written. Theorems and proofs are clear and precise.\nI checked only a tiny fraction of the proofs and arguments seems to add up.\nThe contribution is significant and the techniques developed are interesting. It is a nice contribution to the multiscale literature.", "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": "H9XadHevc7", "reviewer": "Reviewer_iHr2", "summary": "This paper studies algorithms for the online prediction with experts problem in the multi-scale setup where the losses of the different experts have varying (and unknown) scale parameters. Within this setup, the work looks for an algorithm which is adaptive to the simpler stochastic (or lucky) case. The solution is an algorithm, called MUSCADA, and its regret analysis in both the worst-case and stochastic setup. The paper also presents an optimistic version of this and applies the resulting algorithm to zero-sum multiscale games.", "questions": "- Is there a lower bound for the algorithm proposed by Bubeck et al. 2019 under the Massart's easiness condition which shows that it cannot obtain the constant regret bound?\n- What are some example applications where multiscale zero-sum games and the techniques proposed in this paper would be useful?", "limitations": "The paper is a theoretical work and does not have potential social negative impact. It clearly mentions the assumptions under which the results hold and also provides several directions for future work. \n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proposes a simple algorithm based on Follow the Regularized Leader approach and analyses its regret bound. The overall algorithm and its intuition is well explained as are the problem setup. The paper even instantiates the results for a simple example, that of single scale uniform prior, to provide some intuition about the algorithm.\n\nIn terms of techniques, the paper does not bring out the challenge and novelty which prohibit existing techniques from working for this particular setup. For instance, would a simple application of the Chen et al 2021 to Bubeck et al.'s 2019 algorithm work or is something more nuanced required here?", "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": "0TCm9rF7UL6", "reviewer": "Reviewer_R47f", "summary": "The paper extends online prediction with expert advice to a multiscale setting, where the experts' losses have different ranges. The proposed MUSCADA algorithm simultaneously guarantees the minimax regret that grows with the scale of the best expert and has a constant expected pseudo regret in the stochastic lucky case.  MUSCADA refined the Follow The Regularized Leader (FTRL) with a multiscale entropy regularizer, which has a second-order variance-like adaptation. Regret bounds for MUSCADA under two tuning schemes are further provided. Moreover, the authors build an optimistic version of MUSCADA and apply it to solve multiscale zero-sum games, then further experimentally demonstrate its superiority compared to the single-scale algorithms. Finally, the results are discussed with Freund's 2016 open problem.", "questions": "I suggest the authors modify the paper structure for better presentation. ", "limitations": "Yes, the limitations are discussed in the open problem section. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe proposed algorithm, tuning schemes, and theoretical results seem interesting and novel. The algorithm does not need knowledge of the game's length in advance and does not need to store any doubling trick. Stochastic luckiness is studied with quantified data easiness. And the constant regret for easy data is witnessed in the experiments on synthetic data.\nHowever, I am not an expert in the related domain, and I did not carefully check the proof, so I cannot precisely assess the quality and significance of this work. \n\n### Weaknesses\n\n1. The structure of the paper causes some difficulties in understanding\n\nSection 1.1 presents the results before the introduction of MUSCADA with some notations and concepts unknown. \n\n2. The experiment setting is unclear, and some important descriptions are put in Appendix.\n\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