Expected Worst Case Regret via Stochastic Sequential Covering
Authors: Changlong Wu
Mohsen Heidari
Ananth Grama
Wojciech Szpankowski
Venue: Accepted by TMLR ()

Abstract: We study the problem of sequential prediction and online minimax regret with stochastically generated features under a general loss function. In an online learning setting, Nature selects features and associates a true label with these features. A learner uses features to predict a label, which is compared to the true label, and a loss is incurred. The total loss over $T$ rounds, when compared to a loss incurred by a set of experts, is known as a regret. We introduce the notion of *expected worst case minimax regret* that generalizes and encompasses prior known minimax regrets. For such minimax regrets, we establish tight upper bounds via a novel concept of *stochastic global sequential covering*. We show that for a hypothesis class of VC-dimension $\mathsf{VC}$ and $i.i.d.$ generated features over $T$ rounds, the cardinality of stochastic global sequential covering can be upper bounded with high probability (w.h.p.) by $e^{O(\mathsf{VC} \cdot \log^2 T)}$. We then improve this bound by introducing a new complexity measure called the *Star-Littlestone* dimension, and show that classes with Star-Littlestone dimension $\mathsf{SL}$ admit a stochastic global sequential covering of order $e^{O(\mathsf{SL} \cdot \log T)}$. We further establish upper bounds for real valued classes with  finite fat-shattering numbers. Finally, by applying information-theoretic tools for the fixed design minimax regrets, we provide lower bounds for  expected worst case minimax regret.  We demonstrate the effectiveness of our approach by establishing tight bounds on the expected worst case minimax regrets for logarithmic loss and 
general mixable losses.

Published in Transactions on Machine Learning Research (08/2023)
Expected Worst Case Regret via Stochastic Sequential Covering
Changlong Wu!
wuchangl hawaii. edu mheidar edu ayg @ cs.cccuuuee.ee edu szpan @ purdue. edu
Mohsen Heidari
Ananth Grama
Wojciech Szpankowskil
Center for Science of Information (CSol). Purdue University DDportment of Computer Science, Indiana University, Bloomington
Reviewed OpenReview: httppp//ggeareeeo.../e/////oeecp
Abstract
We study the problem of sequential prediction and online minimax regret with stochastically gen- crated features under general loss function. In an online learning setting, Nature selects features and associates true label with these features. learner uses features predict label, which is compared the true label, and loss incurred. The total loss over T rounds, when compared loss incurred by set of experts, is known regret. We introduce the notion of expected worst case minimax regret that generalizes and encompasses prior known minimax regrets. For such minimax regrets, we establish tight upper bounds via novel concept of stochastic global sequential covering. We show that for hypothesis class of VC-dimension VC and i.i.d. generated features over T rounds, the cardinality of stochastic global sequential covering can be upper bounded with high probability (w.h.p.) by cO(VC-log" T)) We then improve this bound by introducing a new com- plexity measure called the Star-Litlestone dimension, and show that classes with Star-Littlestone dimension SL admit stochastic global sequential covering of order (O(SL-logT) T), We further estab- lish upper bounds for real valued classes with finite fat-shattering numbers. Finally, by applying iiformationnthhoreti tools for fixed design minimax regrets, we provide lower bounds for expected worst case minimax regret. We demonstrate the effectiveness of our approach by establishing tight bounds on the expected worst case minimax regrets for logarithmic loss and general mixable losses.
Introduction
Online learning (Shalev-Swarrzz Shwartz & Ben-David 2014) can be viewed as a game between Nature and predictor/learner. each time step f, Nature selects feature x; E X and presents to the learner. The learner then makes prediction where x' and y are the features up time respectively. Nature then reveals the true label ye ) and the learner incurs some loss lūt, We), where we assume É(-, M/) is convex for all yt E y. The game continues up time T and the goal is to minimize the pointwise regret defined as:
fe y based on history x² (xi,-.. } and y (....... 1t-1hh
1, and the true labels up time
R ". H. H
Σ (G.. inf Σ ((h(xe).
where t: 5 x y - R+ is a loss function and H C Dd'' is a class of experts. We say sequences x" and y are realizable for some E we have l(x;)) = Yt for t [T], and agnostic otherwise.
Regret analysis for general class H. of experts often studied via sequential cover g of H. which is defined as set of functions mapping X 5) (where x is the set of all finite sequences over 2') such that for all H

---

Published in Transactions on Machine Learning Research (08/2023)
and xT= XT, there exists 9 9 satisfying hxxx) = g(x') for all [T]. In the seminal work of (Ben-David et al. (2009), the authors established a striking connection between the regrets of agnostic and realizable cases through the concept of sequential covering. One of the core arguments of Ben-Davi et al. (2009) is the following observation (see Lemma 2 for more formal assertion):
If a binary valued class H admits a predictor with cumulative error upper bounded by B for realiz- able samples of length T,, then H has a sequential cover of size O(
This is established by considering all the possible error patterns of the predictor in the realizable case. Using standard expert algorithms (e-g., Exponential Weighted Average), one then relates agnostic regrets to the size of G. For example, for absolute loss, the regret bound is of the form Oly T log 9 O(VBT log 7"), while for general mixable losses one finds Ollog [g]) = O B log T). In Ben-David et al. 2009). the authors derived upper bounds for B through Littlestone dimension. This was further generalized in Daniely et al. (201T) to multi-label cases, and in Rakhlin et al. (2010) the real valued case. However, all of these results assumed that features are presented adversarially. This may be too pessimistic and restrictive for modeling real scenarios of prediction, see e.g. (Rakhlin al. 201T).
This paper generalizes the adversarial online learning setting into more relaxed (and broader) stochastic scenario by restricting the adversary to generate the features x" from some unknown distribution over X (not necessarily i.i.d.) in known class P of distributions (i.e., the so called universal or distribution blind scenario). We introduce a novel general expected worst case regret defined as:
"T,,,P,
sup Ber sup R(O". y", ,,,,,',")))) NEP
where de X² x y + y is any (deterministic) prediction rule (i.e., algorithm), and Øe xxx))""11), We also define the following expected worse case minimax regret:
ir (H, P) = inf fr (H, P,
where o² runs over all possible (deterministic) prediction rules. The expected worst-case regret not only recovers previously known regrets by considering different classes of P (see Proposition [ but also provides new analysis framework for regret analysis in broader stochastic scenarios.
To capture the stochastic nature of the expected worst-case regret, we introduce a novel concept that we term stochas- tic (global) sequential covering that generalizes the classical (adversary) sequential covering. We say a class G of functions X + 5 is a stochastic (global) sequential covering of H w.r.t. P scales a 2 0 and confidence 5 0, if for all μ E P, we have:
Promop [3h E H. A4 E G E [T] s.t. [h(x)) g(x)) > a] S 5.
Similar to the adversarial case, we will show that the expected worst case minimax regret can be upper bounded by the size of a stochastic (global) sequential covering set G via standard expert algorithms. For instance, if H. is binary valued and G is a stochastic sequential covering of 76 at scale 0 and 5 7. for absolute loss, show that (H, P) = O(VTlog (9]), while for logarithmic loss and general mixable loss (c.g., square loss), we find (H, P) = (log [ see Theorem aand 2 for more general statements of this fact.
Our goal is derive tight regret bounds that go beyond the conventional VT bounds for general loss and provide explicit prediction rules (algorithms) that achieve such upper bounds. To retain focus, will mainly consider the case when P is the class of all i.i.d. distributions over X", We emphasize that our results also work for general exchangeable distributions (Aldous) 1985).
Summary of main contributions. We formulate the notion of expected worst case regrer that generalizes and en- compasses prior known online regret into a unified framework, which allows us to study broader classes of feature generating processes, c.g., the distribution blind (i.e., universal) scenarios. We provide a comprehensive analysis of the expected worst case regret when the processes are i.i.d. (and more generally the exchangeable processes) for a wide range of hypothesis classes and losses, via a novel concept of stochastic sequential covering. This allows to derive tighter regret bounds and design new algorithms that achieve these bounds in both previously studied and
2

---

Published in Transactions on Machine Learning Research (08/2023)
novel settings. Specifically, for binary valued class H. of finite VC-dimension, we show that the stochastic sequential covering number is upper bounded w.h.p. by O(VC(H) log T) under i.i.d. processes; this is tight upto a log 7 factor. Using this result we establish an ((V log" 7)) regret bound for expert classes generated by embedding H. into real valued classes under logarithmic loss. This improves substantially the O( ((VVC()) regret bound in Bhatt & Kim (202T), and subsumes the averuge (and well-specified) regrets implied by [Bilodeau et al. (202T). We then extend this result in several directions. We show that the stochastic sequential covering number for binary valued classes is upper bounded by O(SL(H) log T where SL(H) is the Star-Litlestone dimension of H new dimension measure introduced in this paper. This bound is optimal on the logarithmic factor, and the technique for establishing this result is new in literature, and of independent interest. For small real valued classes H of finite Pseudo-dimension P(H), we show that the stochastic sequential covering at scale a is upper bounded w.h.p. by O(P(H) (Tg)(T/a)). For general real valued class H with e-fat-shattering numbers (i.e., the scale sensitive VC-dimension) of order d(a), we show that the stochastic sequential covering at scale a is upper bounded w.h.p. by D(d(a/32)) Using this result, we show that the expected worst case regret under logarithmic loss is upper bounded by (TT//++1) if d(a) = O(a this is tight up to a poly-logarithmic factor. Finally, we introduce general approach for lower bounding the expected worst case regret via the fixed-design regret introduced in Wu et al. (202bb) that provides matching (upto poly- moly-logarithmic factors) lower bounds for most of the our upper bounds presented above.
Related work. Regret analysis of online learning problems dates back to the work of Littlestone & Warmuth (9944) and Vovk (1990), where the authors developed a general framework for the Exponential Weighted Average algorithm for finite expert classes. We refer to
& Lugosi 2006) for an excellent discussion of this topic and its extensions. In(Ben-David et al. (2009), the authors extended the framework to infinite classes with binary labels via the concept of sequential covering and subsequently generalized to the multi-class case in Daniely et al. (20TT). In a series of papers Rakhlin et al. 2210)); Rakhlin & Sridharan (2015): ) Rakhlin et al. (2015); Rakhlin & Sridharan (2014). the
authors established a comprehensive framework for regret analysis of real valued classes via the concept of sequential Rademacher complexity. One of the core techniques in this line of work is to express regret in terms of an iterated minimax formulation, which then be controlled by an expected majorizing of martingales via the minimax theorem. The latter is then computed using sequential covering I number and the standard technique of chaining and Dudley integral. However, all of these efforts consider adversarial cases that may be too restrictive for real word scenarios.
In Lazaric& & Munos 2009), the authors introduced a scenario where the features generated by an unknown i.i.d. source but the labels are still presented adversarially. In particular, Lazaric & Munos (2009) showed that for finite VC-dimensional classes and for absolute loss, regret grows as O( VC(H)T log T). One of the core techniques in this work is an epoch approach that reduces infinite class to a finite class case using successive covering. However, their upper bound is dominated by a VT term of the approximation error of covering that is too loose for many loss functions, e.g., logarithmic loss. Indeed, the same epoch approach (and its analysis of the approximation error) was used in Bhatt& & Kim (021) for logarithmic loss, resulting an O(VT) regret bound. In Bilodeau et al, (022)) I. the authors showed that for logarithmic loss and finite VC-dimensional classes, the risk grows as O((VC(H) log T)TT). However, their proof applies only to the average case minimax regret (see Section 2 and in the realizable (i.e., well- specified) case. In |Rahlin et al. (201T). the authors considered scenario where at each time step Nature selects adversarially some distribution to sample, from a restricted class of distributions that are determined by previously generated samples (not previously selected distributions). This is characterized by the concept of distribution depen- dent Rademacher complexity, using a similar minimax approach as discussed above. However, their result only holds for the distribution non-blind case (i.e., when the distribution known in advance), see (Rakhlin et al. 201 Section 7). Note that all regrets analyzed in this paper are for the distribution blind case. We note also a recent line of research smooth adversaries in Rakhlin al. (201T): (Haghtalab et al. (200)) 2022); Block et al. (2022) that share some technical similarity (e.g., symmetries of samples) with our work.
2 Problem Formulation
Let X' be feature space, Y' be the true label space, and 5 be the space of outputs of the learner. We assume throughout the paper that j [0, 1]. We denote by 7. C j a class of functions X' + Y. which is also referred to as a hypothesis or experts class. For any time horizon T, we consider a class P of distributions over X We consider the following game between Nature and predictor. At the beginning of the game, Nature selects a distribution μa E P and samples
Note that the sequential covering as in Rakhlin al. 2010 slightly different from the one we adopt our work, since their definition relies on some underlying trees.
3

---

Published in Transactions on Machine Learning Research (08/2023)
input sequence x μs, where x" XT. At each time step t I T, Nature reveals the t-th sample x, of x" to the predictor. The predictor then makes a prediction Gt E Y using strategy Φi : x y + 5 potentially using the history observed thus far, that is, Dr- = 0x (x', y )) After the prediction, Nature reveals the true label Yr and the predictor incurs a loss (g... De) for some predefined convex loss function f: y y - [0, oo). We are interested in the following expected worst case minimax regret:
)]
ir (T, P) = inf sup ExT mp
sup Σ e(Dr. v.)
inf DER
Σ
e(h((x)).
(1)
6 PEP
where worst case indicates the predictor needs to compete with the best expert in H. for any x".
We now introduce two particular convex losses, the absolute loss and logarithmic loss as defined:
1. Let c ý [0, 1J. the absolute loss is defined as (() y) = 10-yl, loss can be interpreted as the expected miss-classification loss, i.e., L(. v) ()) [1 # y}l. see (Shalev-Shwartz & Ben-David 2014] Chapter 21);
y/. Note that when y - (0, 13. the absolute
2. Let y = 10, } and y = [0, 1]: the logarithmic loss (Log-loss) is defined as E(), y) = - log(() - (1 y) log(1 - 9). The Log-loss appears naturally in many different scenarios, e.g., sequential probability assign- ment and portfolio optimization, see (Cesa-Bianchi Lugosi 2006 Chapter 9 & 10).
We note that the expected worst case minimax regret ¹T (H, P) recovers previously known minimax regrets by se- lecting appropriate distribution class P. Indeed, in (Shamir & Szpankowski (202T); Jacquet et al. (202T; Wu et al.) (2022a), the following regrets are defined. The fixed design minimax regret for any given x E X² is:
iH x²) = inf sup o y
Ellieo
- inf Σ ((h(x)). NEW
(2)
The maximum fixed design minimax regret is then: (70) supxr r7 )) Furthermore, the sequential minimax regret is
T
( = inf sup 6" x" .T
Σ E ) - inf NCH
Σ
E(h(xx), 36)
(3)
which equivalen to the iterated minimax regret as in Rakhlin et al. 2011
We also introduce the following expected average case minimax regret:
TT (H, P) inf sup MEP,EH
E Np
sup TT
Σ e(i,, 3t) - ((((((())))))) 36)
(4)
where the main difference with Fr (H, P) is the position of supn. Note that this concept subsumes the setups of Bhatt & Kim (2021); Bilodeau et al. (2021) except that the authors of Bhatt & Kim (2021): Bilodeau et al. (2021) consider weaker well well-specified setting for generating yT.
The following observation is easy to prove and shows that ir is indeed a more general concept:
Proposition 1. P is a class of all singleton distributions over X., then (r, P) = (H) for all H. If is the singleton distribution that assigns probability for xT, then ir (H. (H xT). Furthermore, (H, Z (H, for any H and P.
Example 1. To understand differences between ir and アT, consider the following example. Let H. be the class of all functions [0, 1] + {0. 1} that takes value on at most T positions and otherwise. Let v be the uniform distribution over [0, 1), and E(Gt, Dt) = 0 -yl, where dr E [0. 1] and ys. E {0, 1}. We will denote by oT the i.idd distribution of length T with marginal v. We have Foy (H, {v²'}) = O, since for any h, w.p. 1 we have h((x)) = 0 for all t E [T'), meaning that a strategy that predicts all the time incurs regret. However, we also have (T, {u2 2 T To see this, we choose of E 10, uniformly at random and observe that any strategy will make at least 2 accumulated losses, however, for any x" and y", there exists h E H such that Vt E {TT, 1(xx.) Vt-
The equivalence well-known result, see egg, (Cesa-Bianchi Rianchi Lugosi
2006
Exercise 2.18) Wa 2022a Lemma 2).
4

---

Published in Transactions on Machine Learning Research (08/2023)
Remark 1. We should remark that definition of both Fr and Pr are distribution blind in the sense of (Rakhlin et al. 2017 Section 7), since the dependency of marginals of Ii is not just through previously generated samples in Rakhlin et al. (2017). For instance, suppose P is the class of all i.i.d processes, one may express the regret in the following iterated minimax manner:
sup E we inf sup 91 vn
Bay inf sup R(y", .V" H x²).
vr
We note that this expression implicitly assumed that the distribution is known to the learner (otherwise the optimiza- tion function for each inf., g. is not well defined).
3 Stochastic Sequential Cover
Let X be the set of all finite sequences over X. We introduce one of our main technical ingredient of this paper, i.e., the stochastic (global) sequential covering, as follows:
Definition 1 (Stochastic sequential cover). We say a class 9 functions X - [0,1] is stochastic global sequential cover of a class H C [o, 1] w.r.f. the class P of distributions over X at scale a > O and confidence > 0, if for all J. E P. we have
PIęT [3h HY E G [T] s.t. [1(x,)) - g(x') > al s ó.
We define the minimal size of 9 to be the stochastic globul sequential covering number H.
Note that the distribution class P in Definition is completely general and recovers the classical sequential covering as in Bee-Benniiii David et al. (:009); Rakhlin et al. (2010) if P is the class of all singleton distributions over X", Likewise, all the results established in this section hold for any distribution class P.
To begin with, we first establish the following simple (but useful) composition property of stochastic sequential cover. Let Hı, Hm C [0, 1]xd be m function classes over the same domain and θ be a parameter space equipped with some norm || ||- For any function F [0. 11mh x >> [0. 1] such that V21, Zg E [0, 1]m², 0,,02 E e we
have 01) [z 0g) < L max(llz, zelloo 01 021l} for some constant L R the F-composition of "i,... Hm and @ defined to be the class:
H = (1(x)= = (x), ... fm (x), 0) Vi E [m], h E H4 and 0 E O}.
Let Hi.... Hm C [0, 1e be any classes, ④ be any parameter space equipped with norm -| and F' be any function satisfying the conditions above. If E [m], Hi admits statistical sequential covering set Gi at scale az L and confidence 6/m w.r.l. distribution class P, and O admits an a/ L cover C under norm || 11, then the F E-composition class H. of H1, Hm and admits a statistical sequential covering set G w.r.. P at scale a and confidence 8 such that:
Proposition 2.
|9 s |C|
G.l.
Proof. For any tuple of indices (Ji," Im) with j. E [[9,]] and 0' E C, we construct a function such that:
g(x²) Flg,, (x'),...,.9) 19i... (x),,"),
where 9j, is the jæth function in G. The covering set G is defined be the class containing of all such functions g. For any function h E H. there exist h,, Im with h; E H4 and 0 θ such that for all F(h, (x).
X, h(x)
... hm (x), 0). By union bound and definition of stochastic sequential covering of G,, w.p. 2 8 over x for
all [m]] there exist 9j. E G; such that VI E [T], 19j, (x') - hx(x)) S a/L. One can verify that the function g corresponding to (ji,... .mm) and 0' E C closest to 0 under || - is the desired function that covers h on x"", due to the L-Liccchitz property of F.
We provide several examples below that demonstrate how F-composition can be exploited to generate interesting complex classes from simple classes.
5

---

Published in Transactions on Machine Learning Research (08/2023)
Example 2. Ler [0. 1]2 and H₂ C {0, 1] be binary valued class of VC-dimension. Ie take Fl,,0)
y0, (1 y)02 for E (0, and 0 E [0, the F-composition class ' C [0, 1, Hi and O recovers the setup of Bhatt & Kim 2021). p. We note that in this case the set θ admits an a-covering set of size O(a under Loo norm for all a > O and F 1-Lipschitz in the sense of Proposition 2
+.................... + Og S 1 0 E [0, 11"h for some d E N+ and H1,.... Ha C 10,13 be d binary valued classes of finite VC-dimension. If we take F(y",0) = y for y" E {0,1]² and 0 E O, the F- composition class H C [0,1]x of H4s and O defines a natural class. We note that in this case θ is a-covered by a set of size a ad under L1 norm and F is 1-Lipschitz in the sense of Proposition 2 Moreover, if we take d and H2 {1 h(x): h E Hi} we subsume the senup of Example 2
Example 3. Let θ = {0, +
Example 4. Let θ be empty, X = R and H4 (1)a [x][i]] E (a, 6]3 [a, [0, x R for i [d]. ie., Hi is the class of indicators of interval on the ith coordinate of x. If we take Flyn.... , = I Us for vd E {0, 1]a, the F-composition class H. C. 10, 1]x of His defines the class of indicators of rectangular cuboids in Rd and is 1-Lipschitz.
3.1 Upper bounds on regret via stochastic sequential covering
We now prove two general results below that demonstrate how a bound on the stochastic sequential covering number implies bounds on the expected worst case regret fr in an algorithmic fashion.
Theorem 1. Let H be a set of functions mapping X' + [0, 1] and Ga be a stochastic global sequential covering of H at scale a and confidence T/T w.r.t distribution class P. If ((..)) is convex, I.-Lipschitz and bounded by 1 on y for any y V, then:
(H, < inf 0Sa51
{OLT+ + (T/2)) log Ga + +1]
If, in addition, ? 17-Mxxble (Cesa-Bianchi & Lugosi 2006
Chapter 3.5) then:
(rH inf OSagi
aLT log 1aal + +1
Proof. We run the Exponential Weighted Average (EWA) algorithm (Cesa- Bianchi & Lugosi 2006 Page 14) on Ga- We split the regret into two parts, one that is incurred by the predictor against Ga and the other that is incurred by the discrepancy between G. and H. For the first term, we have by standard result (Cesa-Bianchi & Lugosi 2006 Theorem 2.2) that with probability on x
e inf gEG.
Σ ((g(x)) + / (T/2) log Gal.
For the second term, we denote by A the event described in the probability of Definition Since Pr[A] S + and E(O. y) I by assumption, the expected regret contributed by the event A is at most 1. We now condition on the event that does not happen. By Definition] 1 we obtain Yh E Hig E G.Vi E (7), [π(x,) - g(xt) x a. Since é is bounded by and L-Lipschitz, we have:
T
inf NEW
E(h(x)))
v.) 2 inf geg.
Σ ((g(x)), aLT.
1=1
The result follows by combining these inequalities.
For m-mixable loss, replace the EWA algorithm with the Aggregation Algorithm Cesa-Biiaich & Lugosi (2006 Chapter 3.5) and apply the result in Cesa- Bianchi & Lugosi 20066) Proposition 3.2).
We assume the loss to be convex for clarity of presentation. However the result in Theorem 7 can be easily extended to bounded non-comvex Lipschitz losses by replacing the EWA algorithm with its randomized counterpart as in CTesa-Biancha & Lugosi 2006 Chapter 4.2).
Remark 2.

---

Published in Transactions on Machine Learning Research (08/2023)
Let y = {0.1). 5 [0. 1] and be the logarithmic loss. If for all 2 0 there exists stochastic sequential covering set Ga of class H C [0, 1jx w.r.f distribution class P at scale a and confidence ō = 1.
Theorem 2.
T. then:
iT (H,
inf (2aTr + logglo + 1) log(19a + 1)/
05a51
Proof. The proof is similar the proof of Theorem but replacing the EWA algorithm with the Smooth truncated Bayesian Algorithm introduced recently in Wu et al. (022b) and running the algorithm on Ga U {u} with truncation parameter a and uniform prior, where is the function that maps to 1 for all x'. We again split the regret into two parts, one incurred by the Smooth truncated Bayesian Algorithm, and the other incurred by the error of covering. By Wu et al. (2022b) Theorem 1), the first term is upper bounded by 2aT + log([G.. + 1). For the error term, we note that we have added all 1 valued functions u into the expert class when running the Smooth truncated Bayesian Algorithm. This implies that the prediction rule can only ineur the actual accumulated losses upper bounded by T + log(IG. + 1). Therefore, when the event A (defined in Theorem | happens, the expected regret only contributes (T + log(IG. + 1)) Pr[A] (T' + log + 1)) The result follows by combining the inequalities.
4 Stochastic Cover for Binary Valued Classes
This section focuses on the stochastic sequential covering number of binary valued classes We assume that P is the class of all i.id. distributions over X"; however, our results hold for general exchangeable processes (Aldous 1985 over X as well, i.., distributions that invariant under permutation of the indexes.
Note that the selection of H being binary valued is for clarity of exposition for bounding the stochastic covering num- ber, since binary valued classes present arguably the simplest case yet provide enough structure to develop interesting insights. It is easy to extend the results established in this section to the real valued case via the composition property as in Proposition 2
4.1 Stochastic sequential cover for finite VC-class
Let H C {0, 1}x be binary valued class with finite VC-dimension. We write VC(H) for the VC-dimension of H. We show that the stochastic global sequential covering number can be upper bounded by e(VC(HH) log" T) w.h.p. using the 1-inclusion graph algorithm that was introduced Haussler et al. (1994). Without going into the technical details of the 1-inclusion graph algorithm, any given t > 1. For H of finite VC-dimension and any function + (X' x {0, 1)) x X - {0, 1}. we define the following quantity (here, we follow the notation in Haussler et al. (1994):
understand it as function that maps (X' x {0, 1))==1 x X + {0, 1}. for
(t. = sup sup E, [[0((-(0) h((x 11) + h (xxx(1)) x'e NER
where a is the uniform random permutation over [t). x0 (xo(1).-'. fo()) and h((x)(1-1)))
(h(No(1)):*. hxxx(t-1)). The main result of Haussler et al. (1994) stated as follows:
Theorem 3 (Haussler et al., Theorem 2.3(i)). For any binary valued class H of finite VC-dimension and for any 2 there exists function & (X (0, ( x X {0, 1}, i.e., the 1-inclusion graph algorithm, that satisfies
Ma.H(1)= < VC(H)
Our main result for this part is as follows, with the proof presented below Lemma
Theorem 4. For any binary valued class Ht with fintt VC-dimension, there exists global sequential covering set G of H w.t.. the class of all i..dd distributions over XT at scale a = and confidence such that for T 2 e we have:
log |g| < 5VV(()))og2 + +log Tlog(1/5) + log T.
The main idea for proving Theorem is to show that for the l-inclusion graph predictor b we have w.p. 2 over the sample T sid μe, the cumulative error is upper bounded by O(VC(H) + log(1/8)). Assuming this holds, one will be able to construct the covering functions in similar fashion as Bav-David al. (2009 Lemma 12).

---

Published in Transactions on Machine Learning Research (08/2023)
The bound will follow by counting the error patterns. However, direct application of Theorem will only give an expected VC(H) log 7 error bound. The main challenge follows from the fact that even though the samples x are generated i.i.d., the predictions made by the 1-inclusion predictor are not independent (neither a martingale), and therefore the standard concentration inequalities do not apply directly.
Our main proof technique exploits permutation invariance of the 1-inclusion graph predictor, which allows us to relate the cumulative error reversed martingald Using Bernstein inequality for martingales, we then establish the following key lemma, see Appendix for detailed proof.
Lemma 1. Ler tb (X'x 1))* x & - {0, } and h X + {0. y be functions such that + is permutation invariant on (X x {0, 10)" ffr all E [T] and x" E X we have:
Pro, ((x (, ((((x((0-11)) + h h(xx.10)) C
where of is the uniform random permutaaion on [t] and C E N+, then for all 5 > 0 and T 2 e
PLaT Σ 1 , M(xxr((-11)) + h(xx (1)) 2 4o' T + llog(1/))
8..
Lemma 2 (From error bound covering). Let 10,1] x be hinary valued class and E N For any Ω X suppose there exists a prediction rule such that Vh E H. Vx" E S2 Ei= 1 h((xx-1))) + h(xx)) S err. Then, there exists a covering set c. 1)x such that for all T Ω and H. one can find g E G that satisfies g(x") = h((x,) for all [T]. and
19
< Ter+1
t=0
Proof. For any I C [T] with |1| S err, we construct a function gr as follows. Let x² be the input, if E I, (xx', gr (xx))) else, we set gx')
((x',rr((x')(1)) where gr gr((x' {gr(x'), .gr(( (xt-1 )] We claim that the G that consists of all such grs the desired covering set. To see this, for any h E H and x" E Ω we have Σ 1{ (x"('', h((x'=1)) + h(x,)} I err. Let be the positions i E [7] for # 1xxx),, where 77| S err. By construction,
we set gx()x)
which (xx', (x((xx(x1111x
easy to check that Vt E [T], gr (x') = h(x,). Lemma 12).
The upper bound for [G] follows by counting the number of Is. See (Ben-David al. 2009
Proof of Theorem f Let + be the 1-inclusion graph predictor. We have that & is permutation invariant, since the nodes in the 1-inclusion graph are determined by subsets of X' that do not depend on the order of elements in the set. By symmetries of i.i.d distributions, for any event A(x²) on X i.s.d. μ. we have:
Exr P = E, Pryr [A [A(Xa()) ... Xo(T))ll = E, 1 ((A(x(()) " (x(()))) (.)
((A(xx())))))))) (X))))))))
S sup Pr, (A(x()) ... (x,T))).
x²
where the interchange of the expectations follows from Fubini's theorem. is therefore sufficient to show that for any x" XT, w.p. 8 over random permutation a (T).
sup Σ (1) (00(xx(),,,((( (((x)(-1))) + Mxxx()) s 5VC(H) + (18)) BET
To see this, we observe that by Sauer's 's lemma Shalev-Shwartz & Ben-David 2014), there are at most VC(H)) func- tions of H restricted on any given xT. Let now ò in Lemma be नvenn and C = VC(H). When applying Theorem 3 ô is of the form 5VC log T + log(1/8). The upper bound for the size of covering set G follows from Lemma by taking C X to be the set for which & makes at most 5VC(H) log T' + log(1/5) accumulated errors, where Pr[[]
o
together with a union bound, the error bound w.p. 2 11-5
ö.
Note that Vovk al. 2005 Proposition 10.2) also considers similar martingale hased approach only for an almost sure rate.
8

---

Published in Transactions on Machine Learning Research (08/2023)
Theorem 4 and Theorem immediately imply the following regret bound.
Corollary 1. Let H c {0, 11 be binary valued class with finite VC-dimension, P be the class of all i.idd distribu- tions over X and T 2 eh. If e(- y) is convex, L-lipschitz and bounded by 1 for all y E V, then:
(H,, S 3TVC(H) log T 0(1)
If in addition l is n1Mixable then
6 VVC(H) log +
Pr (r - 17
The first bound of Corollary | recovers Lazaric Munos 2009) but with worse log term. However, our result establishes the (essentially) same result by using completely different technique. Moreover, our technique can be applied to more general problems than the epoch based approach of Lazaric & Munos 2009). Indeed, our log T sequential covering bound is the key to finding a Ollog T) regret for mixable losses while the analysis of Lazaric & Munos (2009) can only give Ov)T) bound.
For logarithmic loss, we have the following regret bound:
Corollary 2. Let H. be F F-composition class of Hi,..., ,Ha C. 10, with θ as in Example P be the class of all i.i.d. distributions over XT, and T 2 e._ 1f is the logarithmic loss, then:
((+t VC(HH.) log2T) T
iT(H, P) So
Proof. Taking = 7. we note that θ can be a-covered by a set C of size upper bounded by 7 under L1 norm. Applying Proposition 2 and Theorem + and noticing that the composition function F is 1-Lipschitz, there exists a stochastic sequential covering set of w.r.t. i.i.d. processes at scale a = and confidence such that:
log |9] S dlog
5
VC(H.) log") log2
d log(d/T) d
The result follows by applying Theorem 2 and taking a = δ +.
Note that when d 2 and H. being the class in Example Corollary substantially improves the O(VT) regret bound
of Bhatt & Kim 2021 Moreover, Bilodeau et al. 2021 derive an VC(H) log" risk bound under Log-loss, which
T
can be converted to O(VC(H) log" T) regret bound via the epoch approach of Lazaric & Munos 2009 This is off by log T factor when compared to our regret in Corollary 2 Furthermore, our results hold for general regret FT not average (and well specified) regrets रr as in Bhatt & Kim 2021); Bilodeau et al. (202T).
Remark 3. Note that using similar argument as in the proof of Theorem 4 ladd the multi-class one one-inclusion graph algorithm in (Rubinstein et al. 2006), one can establish an O(P(H) log (T/o) + log(T log (1/5)) stochastic sequential covering bound for any class C. [0, 1]x with dimension P(H). See Appendix
4.2 Tight bounds for classes with finite Star number
In the previous section, we demonstrated that the stochastic sequential covering number of finite VC class upper bounded w.h.p. by Ollog" T), We now show that if assume additional structure on the class, we can improve the bound to (logg) matching the naive fixed design lower bound for many non-trivial classes. In Appendix F we show that even for 1-dimensional threshold functions the realizable cumulative error is lower bounded by 2(log T). thus arguing that the error pattern counting argument in Lemma 2 cannot provide bound better than O(log" T). To resolve this issue, we introduce the notion of Star number that was used originally in Hanneke & Yang (2015) for analyzing the sample complexity of active learning; however, we use it here in completely different context. For
We believe the regret bound as the second part of Bilodeau al. 2021 Theorem missed log factor.

---

Published in Transactions on Machine Learning Research (08/2023)
any binary valued class H and x" Xd, say H. Star-shatters x" if there exist h, h1. ha E H such that for all i.J E [d] with j # i we have:
1(x.) + (x.) but h(xx)) - lx(xx)
i.e., a sequence x" is Star-shattered by H. if there exists a function h E H such that any labeling on x", which differs by one position from the realization of h, is also realizable by some function h E H. Such a sequence x is called a star set H. The Star number Star(H) of defined to be the maximum number d such that there exists x" that is Star-shattered by H. Clearly, we have SHa 2 VC(H) for all H.
We now introduce a new notion of certification, which is the key for our following arguments. For any sequence and E H. we say x certifies x, under
Vf E H. e 1], f(x)) h(x,) then f(x.) h(xx).
We have the following property of finite Star number classes w.r.t. certification:
Lemma 3. If H. has Star number upper bounded by s, then for any x² E X² and h E H. we have:
Pro (1x ())(t-1) certifies Xo(() under ht] 2 1 s 8
where a is the uniform random permutation over [t].
Proof. We only need to show that there are at most points in x' that can not be certified by the others under h. Suppose otherwise, that we have + 1 such points. Consider the realization of h on these points. By definition of certification, we can find functions h,,-.. h as in the definition of Star-shattering. This contradicts the fact that the Star number is upper bounded by s.
We prove high probability bound the number of non-certified positions for finite Star number class, which is similar to Lemma
Lemma 4. Let H C 10,1)* be class with finite Star number and T 2 cb. Then, with probability 2 1 - 8 over x (sampled from some i.i.d. distribution over X²) for all h H.:
T
1xx-11 does not certify x, under h] < &VC(H) T (ogr(H)ooog + log(1/6).
Proof. Note that the event (x'-1 does not certify x, under h} can be viewed the event ( makes an error step in Lemma (since certification is permutation invariant). By Lemma and Lemmal with C Star(H), we have, for all h E H and xT E XT w.p. 2 1 - over uniform random permutation on [T):
T Σ
(t-1) does not certify Xo(x) under h} $ 4Star(H) log + (1g(1
The result then follows from a similar path as in the proof of Theorem
Lemma allows to construct the sequential covering set explicitly without relying on error pattern counting shown next.
Theorem 5. Let H binary valued class with finite Star number. Then, there exists a stochastic sequential covering G of H w.r.l. the class of all i.i.d. distributions over XT scale a O and confidence ó such that for T e::
log [ < 5Star(H)) log T log(1/0).
10

---

Published in Transactions on Machine Learning Research (08/2023)
[Ai kk
X1
01 90
1
h1
h2
h3
h4
h5
X
0
1
X2
X2
{/u les (9s
X2
0
1
[1 24
0
1
X3
0
0
(br h2)
the ho (os
X3
X3
X3
Lax 92]
(os 94
1
0
(Ar [ox))
{ [0a]
{ha} (gs 94)
{ha } (gs 9a3)
{hs} (07 gs}
Figure 1: Realization tree of H defined in left table and partition of g
Sketch of Proof. We only sketch the main idea here (illustrated in Figure D and refer to Appendix B for full proof. We will construct set 9 of sequential functions with index set K. We select K to be fixed with |K| 2 where We will assign sequentially the value gu (x*) for each k K after observing the samples x'. To do so, maintain binary tree called the realization tree, where at each time after receiving sample x,, expand the leaves of the tree with one or two children depending whether the functions in H consistent with the leaf agree on X2 or not. Meanwhile, we also associate with each node in the realization tree a subset of K (i.e., a subset of 9) in a top-down fashion. Initially, we assign K to the root. Any time we encounter a node with one child, we pass the set associated with that node to its child, else we split the set into two disjoint subsets of equal size and pass them to its two children, respectively. The process is said to have failed, if node with two children has the size of associated set S 1. If the procedure does not fail until time T, for any the realization tree with nodes that have the associated sets containing k. The value of gu (x') is determined by tracing the path. Clearly, if the procedure does not fail, the set {gr: k K} sequentially covers H. The key observation is
M +oogr/)))ool(///))
K, there will be exactly one path (from root to leaf) in
that if we choose M to be large enough, the procedure does not fail with high probability due to Lemma 4 (since only non-certified positions incur splits on associated sets that reduce the size of the sets for children by 1/2).
Example 5. We illustrate the construction of the realization tree in this example. We set H = (hi,.... hs), }. as shown in the table of Figure with sample X2, The realization tree is shown in Figure where each function h E H is consistent with some path of the tree, and each path has some function h E H. consistent with it. We assign a subset of G for each node the tree denoted as {.). Observe that if a node has only one child then the child has the same assigned set as the parent, else we assign an arbitrary partition of the parent set with equal sizes to its two children. The final partitions of the set with two children) are in gray color. The maximum number of binary nodes in any path is 3, by selecting [ > 2 8. which guarantees that the assigning procedure does not fail until the leaf. Each gl is associated with a unique path from root to the leaf with (the only) assigned sets on the nodes that contain Je- The values of 9k are defined to be the labels of out edges along the path in the obvious way. One can verify that 91 covers hi, covers h22 Ias 94 covers ha, gs, G6 covers h4, and gr, gs covers hgg. Generally, by Lemma the number of binary nodes in any path is of order (log T) with high probability (i.e., setting |g| 20(1og T) ensures the process success w.h.p.).
-g,..... .98) are the leaf nodes of the tree. In the figure, binary nodes (i.e., nodes
Corollary 3. Let H. C [0, 11x be the F-composition class as in Example 2 with Hi C 10,11* being a class of finite Star number, P being the class of all i.i.d. distributions over XT. If is the Log-loss, then:
iT,,, S ((ttr((H)) log
Proof. By Proposition 2 and Theorem 5| H admits stochastic sequential covering set G at scale a and confidence 8 such that log [g] < (1/a)) + 5Star(H,, log log(1/8). Taking a 5 and applying Theorem 2 the result follows.
11

---

Published in Transactions on Machine Learning Research (08/2023)
Note that a natural class that has finite star number is the threshold functions H {1fz 2 a} Z,a [0, 1]}. which has Star number 2. Corollary 3 implies the regret under Log-loss is upper bounded by Ollog T). We refer to (Hanneke & Yang, 2015) for more non-trivial examples. We note also that the Ollog 7") regret bound is not likely to be established by the epoch based approach (which Lazaric & Munos (2009); Bhatt & Kim (2021 Bilodeau et al.) (2021) have used to establish their regret bounds), since the epochs will inevitably introduce an additional log 7 factor.
We observe that being finite Star number is not a necessary condition to achieve a e (llog cover. To see this, consider the class that labels only one sample being 1 and zeros otherwise, which admits a (exact) sequential covering of size T T but has infinite Star number.
4.3 Tight bounds with finite Star-Littlestone dimension
In this section, we introduce new complexity measure that we call Star-Litlestone dimension The main purpose of this measure is to incorporate the Star number and Littlestone dimension that goes beyond simple finite Star number, and allows us expand the class of H. with (logg) cover.
Definition 2 (Star-Litllestone dimension). Let {0, 1). be the set of binary sequences of length less than or equal to d. For any numbers d and s, we say binary tree T : {0, 1):2 + X' Star- Litt-eitlestone shattered by H. at star scale s if for any path e {0, 1) we have Star In words, Star-Littlestone shattering implies that the Star number of the class of hypothesis consistent with any path in T has Star number greater than s. We define the Star-Littlestone dimension SL(s) of H at star scale s to be the maximum number d such that there exists tree T of depth d that is Star-Littlestone shattered at star scale s by H.
where He* (h E H VI [d), h((((c-1)) = = and H = Haa.
Applying Theorem and the SOA argument as in Ben-David al. 2009). establish our next main theorem with detailed proof in Appendix C
Theorem 6. Let H. be a binary valued class with Saar-Littlesooee dimension SL(s) at star scale s. Then, there exists stochastic sequential covering set 9 of H w.r.. the class of all i.i.d. distributions over X7 at scale a = and confidence 8 such that:
log | < O(max(5L(s) + 1, log log(1/6)).
Example 6. In this example, we show a class H that has both infinite Star number and Littlestone dimension but finite Star-Litlestone dimension. Let H. (1) = 1fx E [a, b]} [a, b] C [0, 1]} be the indicators of intervals. It is easy to see that H. has both infinite Star number and Littlestone dimension. However we can show that it has Star-Littlestone dimension O at star scale 4. To see this, consider any point E [0,1] and the hypothesis class 1}. We show that the Star number of H2 is S 4. For any 5 points in [0, 1), there must be at least 3 points on the same side relative to x, the restriction of Hi such points is equivalent to threshold functions (either of form 1fx 2 a} or 1fx < 6}), thus it cannot Star-shatter these 3 points. This implies that the
H4 (h E H h(x)
global sequential covering size of H is upper bounded by e T)oogT as in Theorem 6
Example 7. Let
H. hb(x) 1fx B): B II Jas, bi] C Rdd
be the class of indicators of rectangular cuboids in Rdd Note that H has infinite Star-Lätleesone dimension for any finite star scale when d > 2 and the VC-dimension of H. is upper bounded by O(d). By Example we have H can be expressed as function in terms of indicators of intervals. Applying Proposition 2 and Example 6 we obtain a covering set G of H. with log [g] < O(dlog T + +d log(d//)). This implies a regret bound of mixable losses (including logarithmic loss) of order (oloog T + d d).
Remark 4. We leave it as an open problem to determine if the upper bound ş (logT) can be achieved for any finite VC-dimensional class. Establishing such result even for the threshold functions H (x) = (((w,x) 2 a}
W,X E Rd, a E R} with d 2 2 seems to be hard task.
Thhis conceptually similar VCL as introduced in the recent paper (Bousquet al. 2021) but they considered a completely different problem using similar idea.
12

---

Published in Transactions on Machine Learning Research (08/2023)
5 Real Valued Class with Finite Fat-shattering
We have established tight stochastic sequential covering bound for finite VC-class (and small real valued classes such finite Pseudo-dimensional classes) in the previous section. We now assume that H C [0,1] 1] is general [0, 1]- valued function class with bounded fat-shattering number.
We first recall the notion of fat-shattering number, which can be viewed scale sensitive VC-dimension. For any class H. C [0, 1]x² we say H. c-fat shatters x" E X if there exists sd E [0, 1] such that for all I [d] there exists h E H such that for all E [d]: (i) If t I, then h(x,) 2 + and (ii) If t & 1, then h(xx) s 8t Then, the fat shattering number of H. at scale a is defined to be the maximum number d == d(aa such that there exists x" E X with H o-fat shatters x4.
We now state our main result for this section.
Theorem 7. Let H be class of functions X + [0, 1] with the c-fatt shattering number d(a). Then there exists stochastic global sequential covering set 9 of H w.rl the class of all ii.d. distributions over x2 at scale a and confidence 8 such that:
log | S
log(4/))) + (log T log T loglog/
where O hides absolute constant which is independent of o, T, and 5.
Remark 5. It is easy to show that for any class H with a--at shattering number of order ).))) the stochastic sequential covering number must be lower bounded by d(a.). This can be seen by considering the sample xd)aa) that is o-fat shattered by H. since one cannot a-cover any two distinct functions that witness the a-fat shattering on xalo) using a single (sequential) function. However, our logarithmic dependency may not be tight, and we leave as an open problem obtain the optimal dependency.
We first introduce the notion local a-covering. We say that a class F locally a-covers H at x" E X2 for h H there exists F such that:
Vt E [T), (b(x;) f(x)) S a.
Here, also assume that F H (we always convert a-covering set F of H 2a-covering set F c such that [F| < F.).
The following lemma upper bounds the local a-covering size w.r.t. the a-fat shattering number of H. which is due to Alon al. (1997).
Lemma Suppose the a fat-shattering number of is d(a)). Then for all x" X", there exists F (which depends x²) that locally a-covers H. at xx" such that:
2)
[d(a
TeT
F 2
T
2 a +11
24aa44((ogg
T+2 T42/44 (12+0210))0000))
Our proof of Theorem is based on the following key lemma (which is an application the classical symmetrization argument), and an epoch approach similar to Lazaric & Munos (2009).
Lemma Let H C [o, x be a class with a-fat shattering number d(a)). Let S 2 be two i.i.d. samples from the same distribution over X. both of size For any S, with E {1,2), we define a distance for all h1, hog E H. as:
d3 (11, = Σ (1) h2(s)l a3.
SES,
Then
Pre [3h,, h2 E H s.t. d3, (hi, (2) = 0 and de (h h22 2 rr < 220(d(/88)-r
where O(d(a/8) 2l(g 2oo (1/a) + +(1))
13

---

Published in Transactions on Machine Learning Research (08/2023)
Proof. We symmetrization argument. We denote by A the event that 3/1 h2 H. such that d3, (h1, but ds, (h1, 2 r. Let be random permutation that switches the ith positions of S1, S2 w.p. 1/2 and independently for different i E [R.]. By symmetries, it is sufficient to fix S1, S2 and upper bound Pr, [ By Lemma know that there exists set FF that a 22ccovs H S1 U S2 with:
F S (0(a k+2 (420)
If the event happens, then there exist ;1, F such that (using property of covering):
(fi. (f. f2) 0 but S (f). r.
Clearly, in order for to happen, any position s E S2 such that (ff(() f2(s) 2 3a must not be switched S under a, which happens with probability upper bounded by 2 Applying union bound over all pairs of F, we have
sr 22d(a/88)(og" 142
which completes the proof.
Proof of Theorem 7 We partition the time horizon into epochs, where each epoch ranges from time step 2--1 2 1. For each epoch s, will construct covering set Gs. The global covering set 9 will be con- structed by considering all the combinations of functions in G, with E {1, (1..... [log )
For any epoch s, we construct G. as follows. Let F C H be the local a-covering set on the samples X,, -2--1-1-
By Lemma 5
we have
F <
Let
r. (d(o + 2 2oo 2log((1/o) 0 log(log T/8).
By Lemma w.p. 2 1- log for any E H there exists f E F such that f 4a-covers h on samples X22 1,' X2--1 except r, positions (the f e F that a-covers on 2- the desired function since F is a local a-covering). Let J be discretization of interval [0, 1] such that for any a E [0, 1]. there exists so that la - bl s 4a. We have [J] S Na Now, for any 1 C (2>-1,". .... ,.., ,2 - 1} with / S rss (ki)ier J11 and f E F, we construct function fi. r1 as follows:
1. Ift I, set fr,uni (xe) Kig
2. If t & T, we set fr,Au (x:) = =f]==[(x) f(xx).
The class Go is defined the class of all such fr,mn By definition of r., and by Lemma have w.p. 2 1 for all E 7. there exists g E G. such that for all E {2a-1, "e........ ,2. 1--1] we have:
8 Tog
(x(x;) h(xx)l S 4a.
We observe that:
|G.1 < [F] (2* <
We now construct the global covering & follows. For any index (Ji.-.. iog with ja [|G=]], we define function g such that it uses the j, function in G, to make prediction during epoch By union bound on the epochs, we have w.p. 2 8 for any h H. there exists g such that:
VI [T], [M(x;) - g(x*) S 4a.
This implies that G is a 4a global sequential covering set of H. Thus
Dog
G
II
G.l < log((//)) +(log" T+log T loo((//)) log(log T T/8)).
==1
The result follows by taking in the above expression to be a/4.
14

---

Published in Transactions on Machine Learning Research (08/2023)
We complete this section with two results regarding the expected worst case minimax regret.
Corollary 4. Let H be a j-valued class with a-fatt shattering number of order a- for some 2 0, and P be a class of all i.i.d. distributions over X² If ) convex. L-Lipschita and bounded by for all y y. then:
PT, ( (((I))(+)((42)
where Ô hides a poly-log factor.
Proof. Apply Theorem to Theorem find (r(H,P) I infosasi {aLIT + +6 (VTa-)) and taking
(LT)-1/14+2) finishes the proof.
Note that Block et al. 2022. Theorem 3) demonstrated that for known i.i.d. processes one can achieve an ((T((-1)1) regret bound (in fact they establish the result for the smooth adversary processes). However, extending such an chaining based argument to our unknown i.i.d. processes as in Corollary seems to be an non-trivial task, since for unknown i.i.d. processes one cannot express the expected worst case regret in the iterated minimax formulation as in |Rakhinn al.] (20TT) (see Remark [. We leave it an open problem to determine if the bound in Corollary 4 is tight or not for the unknown i.i.d. processes.
Corollary 5. Let H be a 10, 10,1]- I-valued class with a-fat shattering number of order a- with l 2 0, and P be the class of all i. distributions over X². offix is Log-loss, then Tr (H. P) S ((T
Proof. Applying Theorem to Theorem 2 we have iT, P) < infosaai {2all + O(a=))) and taking T 1/(+1) completes the proof.
We can show that the regret bound in Corollary is actually tight upto poly-logarithmic factors for general classes of a-fat shattering number of order a -1 (with / 2 I). see Proposition in Section 6 However, it is known by Bilodeau et al. (2020): Wu et al. (2022b) that this bound is not tight for all classes even for the adversary case. Comparing to the results in Bilodeau al. (2021), Corollary | shows that the regret behaviour under Log-loss for Fr is closer to the adversary case in Wu et al. (202bb) instead of the (well-specified) average case as in Bilodeau et al. (202I).
6 Lower Bounds For Regret
We now provide a general approach for lower bounding the regret F(H. P) using the fixed design regret defined in (2) and analyzed in Wu et al. (202b)) as well as (Shamir (2020); (Shamir & Szpankowski (202T) )) Jacquet et al. (202T). We will assume throughout this section that H [0, 1] is general real valued function class and P is the class of all i.i.d. processes over X². We first introduce the following well known tail bound for the coupon collector problem,
sec e.g. (Doemr 2020 Theorem 1.9.2).
Lemma 7. Let X2....... be i.i.d. samples from the uniform distribution over [T], and p be the first time such that [T] c. X². Then for any 2 0 we have Pr[p 2 T lol T cT] -
For any function & that maps sequences from X to I, we say /b is monotone for any x C ZTT we have (xx S (zTT),, where x C Ti means that for any s X, the number of appearances in x is no more than the number of appearances of in Ti We also assume regularity condition for the loss such that for all ÿ1, f2 E y there exists y Y with E(51, y) > v). We also recall that (H) sup r" (H)x²).
Theorem Let H. be any [0, 1l-valued class. If the fixed design regret (H xT)), as defined in 2 is monotone over T and satisfies the above regularity condition, then:
0(1001111)))) (oogT)))r (TT kog (H), Pr (H, 2 (1- O(1 To ()) 2 (1
where is the class of all i. distributions over X and (T)) T log T + + log log T.
15

---

Published in Transactions on Machine Learning Research (08/2023)
Proof. Let x be the feature that achieves the maximum of (7 x²) (i.e., (4)))) We define the distribution to be the uniform distribution over {x1.-.. ,xr} (with possibly repeated elements). Let T₃ = T Tlog T + To log T. We have
Ti
T1 inf NEW
inj (H, = inf sup B mip 4 PEP
sup T
E(0s, vc)
((1(xx), ya)
(5)
2 inf E.Tr
sup x
Σ
((ee Me)
inf NEH
Σ e(d((x). me)
(6)
(2)
T2
2 inf Pr(x" C cx=1--
sup L
E(De.
inf MEN
((h(x)),
1x cx
2
(1)
2 Pr(x' cx
inf sup (a) y
Eldt, Ue)
inf BEN
e(h(xe), v4)
15" Cx
(8)
= -PiK"" c cx
[ri (H x
x Cx+
② Pr|x" (x x")
1
log (H))
(10)
where (a) follows by conditioning on the event (x" C xx and observing that the regret is positive for all x": (b)
follows by inf E 2 E inf, (c) follows from the fact that ri; (H x²1) 2 r7 x²) which further follows from the
monotonicity of n (H x²) (d) follows by Lemma To complete the proof we have T = x x=1((T) and notice that x x (Ti( 2
Ti 1i
The following lemma shows the monotonicity for Log-loss
Lemma 8. For Log-loss we have ri, (H (x 2 (H x
so long as x" cX
Proof. Note that for any x², we have JJaqqeet et al. 2021
T II (1 (1- KEH
(H = log
sup
Therefore, any permutation over x" does not change the value rÿ. Now, suppose X- C xx;; we can permute xTi so that the first 7' samples match with x"" The result follows from the fact that playing more rounds does not decrease the regret. To see this, we let h H to be the hypothesis that achieves minimal accumulated loss in the first T rounds, we regret.
then select the label ye for which E(ft, 3+) 2 E(h(X:), v.) for the following steps > T, which ensures non-decreasing
Finally, we apply the above general lower bound to the expected worst case minimax regret.
Corollary 6. Assume is the Log-loss. If f (H) 2 C'log* T then
ir (H, P) 2 Coog T o(log" T),
where P is the class of i.i.d. distributions.
If (H) 2 CTa, then CT o(T log"
iT (HH,P) log T
Remark 6. A question arises whether the log T factor in Corollary 6 can be eliminated. We do not have a complete answer for this question at this point; however, we will show in Appendix D that there exists a class H. such that (r, P) S (1 (1-e-1)re ( where P is the class of all i.i.d. processes. Meaning that the reduction as Corollary will necessarily introduce factor < 1 for polynomial regrets (H).
Using the result Cesa- Bianchi Lugosi
2006 Theorem 8. I), can establish similar result absolute loss.
16

---

Published in Transactions on Machine Learning Research (08/2023)
We refer to Wu et al. following lower bound is complement to Corollary 5
2022b) for the lower bounds on r7-()) of various classes H. under Log-loss. In particular, the
Proposition 3. For any I 1, there exists a [0, 1|-valued class H with a-fat-shattering number of order (aa and P is the class of all i.i.d. distributions over X2, such that
ir(H,P) 2 ((TT/C+))
under logarithmic loss.
Proof. Let X' = [2]; we define H. {h E [0, Ei= h(t)' I 1]. We claim that the a-fat shattering number of H. is upper bounded by a!. To see this, we assume there exist d points x" E [T] such that d > a and x is a-fat shattered by H. By definition of a-fat shattering, there exist two functions h1, h2 E H such that Vi [d]. h1 (x;)
(x,) 2 2o. This implies that Σ [8) h22(t)² 2 d- (2a)' > 2', i..., ||, halli 2. However, this contradicts the fact that ||/, hall S ||aale + ||h2l|: S by the triangle inequality of norm. In conclusion, by Wu et al. 2022b Theorem 6) we have (H( 2 ((TT/(+)) Invoking Corollary 6 and the result follows.
Note that Proposition 3 only shows that the lower bound ((TV/((+1) holds for certain hard classes. We prove in the following proposition lower bound that holds for all classes.
Proposition 4. Let 1 2 1, H be any [0, 1]-valued class with a-fattshattering number of order S((aT and P is the class of all i.i.d. distributions over X Then
(r. 5((((-11))))
under logarithmic loss.
Proof. Let x be samples that are a-fat-shattered by and witnessed by s", where a 2 1/T"1//).. We now describe adversary strategy that achieves the (2(T lower bound for the fixed design regret r7 x""). To this, for any E [T), if the predictor predicts 0r 2 8t, we set = O, else, we set V: = 1. By definition of a-fat shattering, there exists h E H such that Vt E [T], (h(xx) Del 2 and E(Dr, vi) 2 E(h(x)) vt). We assume without loss of generality, = 1. By definition of Log-loss, we have:
f(Ee. v:) E(h((x), v1) log(h(x))/0)) log((ū: + aa) 2 a/2,
The last inequality follows by log(1 + +x) 2 x/(e /x( 1). Therefore, we have r (H x²) > Ta/2 2 R(T(1-1)/1)) The
proposition now follows by Corollary 6
Note that when 2 2 the lower bound in Proposition achieved by Logistic regression (Foster et al. 2018 Example 2). Therefore, the lower bound is not universally improvable (this is similar to Corollary 5).
Example 8 (Well-specified v.s. worst case y²). In this example we demonstrate that the expected worst case regret Pr can be substantially different than the well-specifee average case regret Pr as in Bilodeau et al. (2027). This will explain why our Theorem 8 is a necessary technique for establishing lower bondl for ēr. To see this, for any X with
|X| 2 T we define:
1 b(x) H hx(x)= = VT
be =b11-1,1
This class admits an O(1) uniform KL-cover at scale O(1/T), and therefore by Bilodeau et al. (2021), the well- specified regret is of order (1). However, by Wu et al. 2202b Page 6), the fixed design regret (H) 2 2(1/TT)T 2 S(VT). Invoking Corollary 6 this implies an Q(vT)) lower bound for îT. This also demonstrates that the KL-cover (or equivalently the Hellinger cover) as in Bilodeau et al. (207)) cannot capture the behaviour of frp under Log-loss even with values bounded away from 0.
17

---

Published in Transactions on Machine Learning Research (08/2023)
7 Conclusion
In this paper introduced general minimax regret called the expected worst minimax regret when the features are generated by stochastic source. This new minimax regret recovers previously known online minimax regrets in unified way. We analyzed the regret via a novel concept of stochastic global sequential covering and provide tight bounds on the covering size when the underlying process i.i.d.. A direct generalization is to extend our results to some interesting general random processes. We also expect that the technique of stochastic global sequential covering can exploited beyond problems studied in this paper, e.g., for contextual bandits with general reference policy sets, From an algorithmic perspective, our prediction rules derived from Theorems [ and 2 are based on the Exponential Weighted Average algorithm, which is generally not computationally efficient. We believe that investigating compu- tationally efficient algorithms (such as the oracle efficient algorithms in Block et al. (2022) represents an intriguing direction for future research. We leave these extensions and applications to future work.
Acknowledgements
This work was partially supported by the NSF Center for Science of Information (CSol) Grant CCF-0939370, by NSF Grants CCF-2006440, CCF-2207238, CCF- 221 2211423, and OAC-1908691 and in addition by a Google Research Grant,
References
David Aldous. Exchangeability and related topics. In École d' Été de Probabilités de Saint-Flour XIII-1983, pp. 1-198. Springer, 1985.
Noga Alon, Shai Ben-David, Nicolo Desa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform conver- gence, and learnability. Journal of the ACM (JACM), 41(4))61 1997.
András Antos and Gábor Lugosi. Strong minimax lower bounds for learning. Machine learning, 30(1):31-56, 1998.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In Conference on Learning Theory (COLT), 2009.
Alankrita Bhatt and Young- Han Kim. Sequential prediction under log-loss with side information. In Algorithmic Learning Theory (ALT), pp. 340-344. PMLR, 2021.
Blair Bilodeau, Dylan Foster, and Daniel Roy. Tight bounds on minimax regret under logarithmic loss via self- concordance. In International Conference on Machine Learning (ICML), pp. 919-929, PMLR, 2020.
Blair Bilodeau, Dylan J Foster, and Daniel M Roy. Minimax rates for conditional density estimation via empirical entropy. arXiv preprint arXiv:2109.10461 2021.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. arXiv preprini arXiv:2202.046690, 2022.
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 532- 541, 2021.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning and Games. Cambridge University Press, 2006.
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shward Multiclass learnability and the principle. In Conference Learning Theory (COLT), pp- 207-232, 2011.
Benjamin Doerr. Probabilistic tools for the analysis randomized optimization heuristics. In Theory of evolutionary computation, pp. 1-87. Springer, 2020.
Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The impor- tance of being improper. In Conference On Learning Theory (COLT), pp. 167-208. PMLR, 2018.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems (NeurlPS), 33:9203-215 2020.
18

---

Published in Transactions on Machine Learning Research (08/2023)
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty, Smoothed analysis with adaptive adversaries. In IEEE 62nd
Annual Symposium on Foundations of Computer Science (FOCS), pp. 942-953. IEFF, 2022.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn, Res., 16(12):3487-3002, 2015.
David Haussler and Philip M Long. A generalization of sauer's lemma. Journal of Combinatorial Theory, Series 71(2)22192400) 1995.
David Haussler, Nick Littlestoee, and Manfred K Warmuth. Predicting {0. 1)-functions randomly drawn points. Information and Computation, 115(2):248 292, 1994.
P. Jacquet, G. I. Shamir, and W. Szpankowski. Precise minimax regret for logistic regression with categorical feature values. In Algorithmic Learning Theory (ALT), volume 132, pp. 755-771, 2021.
Alessandro Lazaric and Rémi Munos. Hybrid stochastic-adversarial on-line learning. Conference on Learning Theory (COLT), 2009.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2): 212-261, 1994.
A. Rakhlin and K. Sridharan. Online nonparametric regression with general los function. In Conference on Learning Theory (COLT), 2014.
Alexander Rakhlin and Karthik Sridharan. Sequential probability assignment with binary alphabets and large classes of experts. arXiv preprint arXiv:/501.073400 2015.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial param- eters, and learnability. In Advances in Neural Information Processing Systems (NeurIPS), 2010.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic and constrained adversaries. arXiv preprint arXiv:1104.5007 2011.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields,
Benjamin Rubinstein, Peter Bartlett, and Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. Advances Neural Information Processing Systems (NeurIPS), 19, 2006.
Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
G. Shamir and W. Szpankowski. general lower bound for regret in logistic regression. In IEEE International Symposium on Information Theory (ISIT), 2021.
Gill I Shamir. Logistic regression regret: What's the catch? In Conference on Learning Theory (COLT), pp 3296-3319. PMLR, 2020.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
Volodimir G. Vovk. Aggregating strategies. Conference on Learning Theory (COLT), pp- 372-383, 1990.
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Sequential vs. fixed design regrets in online learning. IEEE International Symposium on Information Theory (ISIT), pp. 438 443, 2022a.
Changlong WU, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Precise regret bounds for log-loss via a truncated bayesian algorithm. Advances in Neural Information Processing Systems (NeurIPS), 2022b.
19

---

Published in Transactions on Machine Learning Research (08/2023)
A Proof of Lemma
For any [7], denote It ((
((((((((())))))) h(xo(o)) }} where is uniform random permutation
over [7]. For all E [T], we define the reversed sequence of indicators 1 = II -1+1+1 We observe that for all E (T), the indicator 1 only depends on the realizations of (T)) (o(T-)):"" (T- since & is permutation invariant on Xo(1), (T Therefore,
E ".... 1--1== B No(T))"" (o(r-142) & min {
C
(T-1+1
(T() where the last inequality follows from the assumption & and noticing that conditioning on (T(-++42 the per- mutation restricted x²\ (Xo(T),"" (oo(T-442) is also uniform random permutation. For any realization ...... -4-11 we define 1 = 12 E[4 1, 4--1l. We now observe that the indicators 1"" are (Doob) martingale differences, i.e., we have Vt E [7]]
E 11,
1 = O.
By the Bernstein inequality for martingales
& Lugosi 2006
Lemma A.8), we find:
T
Pr
R > k and E² S v S e पनंंगक.
where
We now observe that conditioning I,, I 1. the indicator 1 is a Bernoulli random variable with parameter Pt I min :1. This implies that if 1 1 then Ii 1 and I 0 then [4'| S Pe- Using elementary algebra, we have with probability that
T Σ Pr (1 p:)pi Coo +C. t=1
ENV ...... 1414%111
Plugging it into the Bernstein inequality with 2(C +33)) and v Cllog T T33,, with probability
2 1 8, have:
Σ4=
1
Σ 1 EL
",..,,, 1K-1
T
C
11
< k +
T-1+
S 30 33Clogg T 5C log(1/8).
T T
Here, we used the following elementary inequality:
(2a + b)2
Va, b 20 2(a + (2a + b)/3) 2 b.
The Lemma now follows from the fact that C'log T > 5C when 7 > e and C 2 1.
B Proof of Theorem 5
We will construct a covering set & directly without relying on the error pattern counting as Lemma 2 This is the key removing the extra log T factor. We will introduce a set K index the functions in g. we assume that K is fixed and ||| 2 for some M be chosen later. For any is K, will construct sequential function gk follows:
20

---

Published in Transactions on Machine Learning Research (08/2023)
Let be a realization of the sample from an i.i.d. source. The realization tree T of H on x" is leveled binary tree of depth T + 1, with each node at level t being labeled x, (where level 1 has only the root v1), each left edge being labeled 0 and each right edge being labeled 1, such that any node U/ E T at level t has left (respectively right) child if and only if there exist h E H. such that h(xx) = (respectively (xx) = 1) and h(x,) = L(v; - U;+1) for all S 1 1-1-1 1, where U1 - 12 7 ... + Ve = v the path from root v1 to v and the edge label function. Note that different realizations of x" will result in different realization trees.
We now assign values of the functions 9k with & E K using the following procedure. For any node v in the realization tree T, we will associate set K((u) C K using the following rule (starting from root):
1. If is the root, then (()) K;
2. If has only one child u, then K[(u) K(():
3. If has two children un, u2, we assign the sets un, U2 being an arbitrary partition of K(v) of equal sizes, i... [K[())) = K((u)), ((()) n K(u2) 0 and K(u)) U K((u)) K(v).
Clearly, the value K(()) for any node at level can be determined with only the realization of x' and the values of IC of all nodes at level form a partition of K. The procedure I. fails if there exists some node e with two children such that [K(v)] < 2. Suppose the procedure IC does not fail. We have for any k E K, there exists a unique path ti + 12 - + Dr+1 with 21 being the root, such that for all t < T + we have E K(v)). For any such k, we assign the value of gl on x² as:
(x') = L(u - Mt41),
where is the edge label function as discussed above. If the procedure K. fails at some node us, we assign the value of g& (x') arbitrarily for j 2 t.
By definition of the realization tree, for any E H there must be a unique path 11 - ................................ + UT+1, with 81 being root such that hxx)) L(w,- - vt+1) for all t. Therefore, the procedure I. does not fail, then for k E K((T+1). we have (xx.) g& (x') for all T' by definition of gk- We now show that by setting M
|5Star(H) + log (1/5],, w.p. 2 1 5 over xT. the procedure IC will not fail, thus proving that the class = {9x k E K} is a stochastic sequential covering of H. with confidence 6. To see this, we note that the procedure I. fails at node et at level i if and only if there are 2 M + 1 nodes with two children in the (unique) path 11 - + 1t, where 01 is root, since only rule 3 will reduce the size of value of IC by 1/2. Assume now the procedure K. fails at node u, Let h E H be a function such that (xx,)= = Lo,, + B+41) for all i S t, which must exist by definition of realization tree. Since any node vy in the path 01 - ... + 04 with two children implies x does not certify x, under h, we have that there are least M positions j (with j < 1) such that x/-1 does not certify x, under h. By Lemma 4 and selection of M, this happens
with probability 5. This completes the proof.
C Proof of Theorem 6
The proof will incorporate the SOA argument as in Ben- et al.) (2009) and the result from Theorem 5 For notational convenience, we denote d = Ss)) + 1. For any 1 C [7] with |/| S d, we will construct a set Gr. Let + be the SOA predictor (similar to Bavd et al. 22009, Algorithm 1)) that predicts the label for which the remaining consistent subclass has maximum Star-Littlestone dimension at star scale s, if both subclasses have SL dimension 0 we predict the label for which the remaining consistent subclass has maximum Star number (and break ties arbitrarily). We now construct functions in Gr follows. The predictions of functions in Gr are partitioned into 2 phases (start with phase 1). At phase I, all the functions in Gy use the same prediction rule in Lemma 2 that is, if we at time step E I, we predict using 1 - T. else we use & to predict, where Ob is the SOA prediction rule described above. We enter phase 2 if the remaining consistent class has Star number upper bounded by s; we then construct the prediction functions in Gj as in Theorem 5 with Star(H) s, confidence 8 ddT and |Grl < 55 Tlog /5) The covering class G is defined to be:
g
U
G1.
ICIT), Mssd
By Theorem with Star(H) = and 8 6/rd+1 and computing the number of Is, we have
Td 5. log To +log( (8) < ((max(d.e) log +log((/)))
21

---

Published in Transactions on Machine Learning Research (08/2023)
We now show that G is indeed stochastic sequential covering of H. with confidence 5. Let Hi be the (random) subclass of functions in H that are consistent with & with error pattern 7 before entering phase 2 (it is possible that h remains on phase 1 until time 7)). Note that all functions in H, agree on samples at phase 1. Note also that, with probability we have 7 = UICIT, H-. To see this, we note that if h disagreed with the SOA then the remaining
consistent class has SL(s) decreased by at least (similar to the argument as in Ben- et al. (2009) Lemma 10)) or has Star number S s if the current consistent class has (s(s) = O. This implies that any h E H. can be disagreed with SOA at most d times before entering phase 2, which must be in some Hy with | S d. Now, for any I with [ I d we need show that:
Pr(g, covers H,) 2
Td4I
Note that the main difficulty here that Hy is a random subset. We show that conditioning on any realization of Hr, the above inequality holds (the inequality will then hold by law of total probability. This follows from Theorem by noticing that the samples in phase 2 are still i.i.d. and independent of samples in phase 1, and G7 trivially covers H. in phase 1 by definition of Gj and Hy. The theorem will now follow by union bound on all the /s.
D Example to Corollary 6
We give an example here that demonstrates that there exists H such that "1 (H, I (1 (1-e-1)r² under Log-loss, where P is the class of all i.i.d. distributions over the domain. Let H the class of all the functions map [7] - {0, 1}. Clearly, we have, by computing Shtarkov sum (Wu et al. 2022b), that:
(H() T.
We now provide specific strategy that achieves smaller Pr. The strategy goes as follows, if we haven't seen the w--1/T
sample x, then predict 2. else predict 1+2/T where Yi {0, 1} is the true label observed for previous appearance of Xt (if there are multiple appearance choose arbitrary one). We now observe that the true labels must be consistent with some function in the class. Otherwise the regret will be negative infinite since the functions in H. are {0, 1}- valued. We now observe that for any distribution over [T'] the expected number of distinct elements with T i.i.d. samples is upper bounded by
(1-e
Clearly, this is the bound achieved by uniform distribution over [T]. To see that this hold for arbitrary distribution as well, we observe the expected number of distinct elements equals:
Σ 11
where Pt is the probability mass of the distribution on sample t. We now observe that (1 (1-xx) x²" is convex for all T' and [0, 1]. therefore by Jensen's inequality we have
2 T Te
(1- P.)
Since the regret is upper bounded by the expected number of distinct elements, we have
ir H. () e (1-6 +
E Stochastic sequential cover for finite Pseudo-dimensional classes
Let 76 C [0, 1 be a real valued function class of Pseudo-dimensional P(H). We show in this Appendix that there exists stochastic sequential covering set G of H. w.r.t. i.i.d. processes at scale a and confidence d such that
log G ((P(H) (T + log(T/a))
Here, phase and corresponds that functions consistent with current sample has Star number s and s, respectively.
22

---

Published in Transactions on Machine Learning Research (08/2023)
The proof follows similar path as in the proof of Theorem 4 but replacing the one one-inclusion graph algorithm with the
multi-class one-inclusion graph algorithm as in Rubinstein et al. discretization of [0, 1] with step size 2a, and N := [J] S 2n- Let H' = (x'(x) = arg min.e (()(x) - al} h E H}
(006). To do so, we denote by J C [0. 1| a uniform
be the discretized class of H. Clearly. P(H() < P(H). Let +
(X' x J)" x X - J be the multi-class inc-unclusoon
graph algorithm for H' as in Rubinstein et al. 2006). We have by Rubinstein et al. (2006) Theorem 5.2)
sup sup E, [1(0(x)()) M(x((()1)) # M(FO()))) 1 P(H) x'EX' hEW
where a is uniform random permutation over [t]. Invoking Lemma | for all E H' and x² E X2
PLoT 1(0(x (axxeri,,,((xxx(eee (((x)r(12)))) + 1
h(Xor(o)) 2 4P(H) log log(1/0) s 6.
Corollary 3), for any x" the number of functions of H restricted on x"" is upper bounded by (TN)P(R), Taking 5 == 6/(T (/(N)))(H)) and applying union bound, we have
By generalized Sauer's lemma (Haussler & Long
1995
T sup 1 ((((x=11) , ((xx7((-()) # h(Xo(())) 2 5P(H) log(TN) + log(1/6) S 8. hEH t=1
Prot
By symmetries of i.i.d. process, for any distribution μ over X' we find
PreTo M
sup bEH!
Σ t=1
(J)) + M(x))) 2 (P) + log(1/0) 1og(1/)) 8.
We now use a similar argument as in Lemma 2 to construct the sequential covering set. Let err = 5P(H) (Tg) + log(1/5), I C [T] with |/] I err and K = The)rer E JM4 For any such 1, K, we construct a sequential function 91.K such that for any E I and x' we set 91.x (x') ) = by and set 9t,k (x') ) = (xx,, {gr. (x (}) for & I. It is easy to verify that the class G consisting of all such gr.k is stochastic sequential cover of H' at scale and confidence 8, and
err Σ 1=1
1A'''
log |9| |9|| =
< (TN) (TN))T+ oT < O(P(H) log (TN) + log(TN) log(1/8)).
By the construction of J, G is a stochastic sequential covering set of H. w.n.. i.i.d. processes at scale a and confidence
8. The claimed bound now follows by noticing that N s Za
F An 2(log T) lower bound of realizable cumulative error
We now show that there exist classes H of finite VC-dimension such that for any prediction rule, the expected cumu- lative error with i.i.d. sampling in the realizable case is lower bounded by Q(VC(H) log This result was shown in Haussler et al. (1994] Section 3) and also in Antos & Lugosi (1998), however, we provide an alternative (simpler) proof here for completeness.
Let 7 = (x) = 1fr a} x. a E [0, 1]} be the class of all linear threshold functions [0. {0, 1}. We show that H. is the desired class. To do so, we detine to be the uniform distribution over [0, 1]. Let X,, XT be i.i.d. samples from y We show that for any prediction rule & we have
T Σ
ha(X))) 2 2(log T).
E
W.l.o.g.. we can assume that A, x..... Xy are distinct. By symmetriess of i.i.d., we may assume that A, X,, Xy is uniform random permutation for some fixed set {A, .r). We consider the following process: at the
the extension general VC-dimension d straightforward considering product class 71 = (Ia(x,)) = 12 2 +x): a E J0, 1jd, (x) E [o, 1] x [4] and defining the distribution first sample from uniformly and then sample from This admits lower hound (dd (T/f) since whh.p each [d] appears @ /d) times.
We only prove the when VC(H)
23

---

Published in Transactions on Machine Learning Research (08/2023)
beginning Nature randomly permutes {A, . and maintains set S initially be equal {X1, Xr): At each time step 1, Nature reveals the relative position of X, in S. After the predictor has made the prediction, Nature discards elements in S on the opposite side of X, relative to A (i.c., if A > X, we discard elements - X in S, else we discard elements 2 X₂) and reveals them to the predictor. Clearly, a lower bound for the game described above implies lower bound for the original game, since the predictor gains more information each time step. Denote f(1) to be the expected number of errors the predictor will make if [S] = t. We have the following recursion:
T/2 7
t f(t) T
(T 1) f(T 2)
t T
f +
S(T)
T
T
t=1
conditioned on the event that X2 is at position t, have probability t/T that A is less than X1 and probability (T 1)/T that A is larger than X1. The best strategy for the predictor is to predict A >> X1 if < T/2 and predict A < X1 otherwise. This contributes an expected error at first step to be 7. The recursive formula now follows by the observation that conditioning on the position of X1 and relative position A to X1, the remaining set SU {A} is still a uniform random permutation. We now claim that (the constant 0.01 not optimized):
The reasoning goes follows:
f(t) 2 0.01 logt.
The base case for = 1 can be verified easily. We now prove by induction. We observe that
f x log(z) = 2 n² (g)((()))
x²
4
Therefore, using Macea-Ma formula have:
T f(T) 2
Σ
0.01 llg((t) + 0.01 T log - 0.02 Toog 0.01 / T2/2
/ 0.01 log
The result follows.
24


Reviews:
[{"review_id": "M86lgVQ9Ew", "reviewer": "Reviewer_b28u", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nOverall the results in the paper seem comprehensive, and the authors have tried to interpret their notion of stochastic sequential covering for many of the most common classes contained in the literature including finite VC-dimension, finite Star-dimension, and finite fat-shattering. \n\nHere are some concrete comments/concerns. \n \nDefinition of Expected Worst Case Minimax Regret Equation (1): I’m sure this is extremely naive, but I am confused about what this definition adds. In general, the sup of the expectation over all distributions should occur at a single sequence. Thus I would expect that if $P$ is all distributions over $X^T$, that equations (1) and (3) would be the same.  In fact, (1) and (3) should be the same for any class P which contains all singleton distributions. As the authors remark, (3) is well studied in the literature. Can the authors remark on examples of $P$ that may be interesting that don’t contain the singleton distributions? Are i.i.d processes the natural example?\n\nStylistic Comment: The paper is extremely thorough, but as a result, somewhat challenging to read through. In addition, from a reviewing perspective, it’s hard to tell what the contributions of the authors. Here are some specific comments on this: \n- What is novel in Theorem 1? Presumably existing works have a very similar analysis? \n- Can the authors comment on whether existing results for classical minimax regret (e.g Cesa-Bianchi Lugosi ’06) recover the results of Corollary 1? \n- Maybe some of the technical lemmas and their proofs can be in the appendix? Eg Lemma 2,3,4 and the proof of Theorem 4. I don’t know what the 1-inclusion graph predictor is and so reading the proof was not helpful at all. \n- Along these lines, I felt there were places where things were not defined sufficiently clearly. For example, in Lemma 4 - what is Phi?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers online learning and sequential prediction. The authors introduce a new minimax notion of regret, the expected worst-case minimax regret, which generalizes other existing notions of minimax regret by taking a supremum over all distributions over the sequence of features observed by the algorithms. The authors then establish upper bounds for this minimax regret using stochastic global sequential covers - which generalize the classical sequential cover. To further bound the regret, they bound the stochastic sequential cover for classes with finite VC dimension, finite star number, and finite Star-Littlestone dimension. This last notion is novel, and the authors demonstrate classes where the Star-Littlestone is meaningful even when the star number and littlestone dimension are infinite. The authors finally provide lower bounds on the minimax regret. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think if the authors could more clearly clarify their precise technical contributions it would be easier for a reader to understand the contribution.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OcMPNhnEYd", "reviewer": "Reviewer_tdCv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The most significant weakness in this paper lies in the motivation for the study. As I understand, the minimax regret $r$ does not measure the regret of any particular algorithm — rather, it represents the hypothetical regret of the best possible algorithm. In this regard, $r$ provides a regret lower-bound for any conceivable algorithm. Therefore, studying the upper bound of this quantity appears illogical as it doesn't convey meaningful information about a specific algorithm. Although it might shed some light on the complexity of the hypothesis class under an online decision-making setting, the insights are not particularly significant. Moreover, the lower bound of the quantity, which arguably carries more weight, is not expressed in terms of the VC, SL dimension, etc. — this omission significantly weakens the paper. For example, if the paper demonstrated that both the lower and upper bounds were given by $c*VC * \\log^2(T)$, it would have appeared much stronger.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the worst-case regret bound in a contextual bandit problem with a general prediction class. The primary motivation is to understand the scenario where the contexts are revealed via a fixed distribution, even though the reward can still be adversarial. The minimax regret, $r$, defined in this paper is determined by the \"regular regret\" under the optimal predictor. The paper demonstrates that the regret can be upper-bounded by the stochastic covering number of the hypothesis. The majority of the paper then attempts to upper-bound the covering number using different combinatorial dimensions of the hypothesis class, $H$. The first bound is determined by the VC dimension, such that the log-covering number bounds by VC*$\\log(T)^2$. The quadratic dependence on $\\log T$ is further improved by introducing a dimension known as the star-Littlestone dimension, $SL$. The paper shows that the log-covering number can be upper-bounded by $SL*\\log T$. A lower bound for this quantity is also provided in the pap", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are some minor editorial issues that should be addressed:\n\n- In the introduction, it would be beneficial to provide more motivation for defining and studying the problem, especially when introducing the concept of minimax regret.\n- In the introductory paragraph, the term 'y_t … assume to be convex' is used. Could you please clarify what you mean by 'convex' in this context?\n- In the second paragraph of the introduction, you mention that 'H admits a predictor with cumulative error B'. It's not clear what you mean by 'predictor' and 'cumulative error' here.\n- It would be helpful to include explanations in layman's terms when introducing new concepts. For instance, when defining the 'star' number, could you also provide a simplified explanation of what it means?\n- The definition of the SL dimension should be included in the main body of the paper, rather than being relegated to an appendix or footnote.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4uoE0LbSs2", "reviewer": "Reviewer_pHFt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong aspects of the submission:\n\n- Introducing the notion of expected worst-case minimax regret, generalizing and encompassing prior known minimax regrets.\n- Proposing the novel concept of stochastic global sequential covering to establish tight upper bounds for minimax regrets.\n- Introducing the new complexity measure, the Star-Littlestone dimension, to improve the bound on the cardinality of stochastic global sequential covering.\n- The paper is well-structured, and its claims are supported by convincing mathematical arguments.\n\nWeaknesses of the submission:\n\nThe submission does not seem to have any significant weaknesses. However, it might be beneficial for the authors to:\n\n- Discuss possible limitations of the method and potential avenues for future research to address those limitations.\n- Discuss the gap between the VC dimension and the newly introduced complexity measure (e.g., through concrete examples like Example 6).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors address the problem of sequential prediction and online minimax regret with stochastically generated features under a general loss function. They contribute by:\n\n- Introducing the notion of expected worst-case minimax regret, which generalizes and encompasses prior known minimax regrets.\n- Establishing upper bounds for such minimax regrets using a novel concept called stochastic global sequential covering.\n- Introducing a new complexity measure, the Star-Littlestone dimension, to improve the bound on the cardinality of stochastic global sequential covering.\n- Establishing upper bounds for real-valued classes with finite fat-shattering numbers.\n- Providing lower bounds for expected worst-case minimax regret by applying information-theoretic tools.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Is it possible to argue that the newly introduced complexity measures represent the intrinsic difficulty of the problem?  For example, can you show regret lower bound depending on the complexity measures? Or can you provide examples where the regret upper bound provided in the paper is tight (including factors depending on $\\mathcal{H}$)?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the online minimax regret of sequential prediction with stochastically generated features.  By considering a relaxed adversarial setting and introducing novel theoretical concepts, the authors derive significantly tighter bounds than the known bounds for adversarial settings.

Reviewers originally mentioned the following pros and cons:

Pros:
- The theoretical results are comprehensive with novel concepts introduced.
- Derived significantly tighter bounds than known results (under a different setting).

Cons:
- Weak motivation (deriving upper-bounds of lower-bounds might not be useful)
- Unclear contributions

The authors addressed concerns appropriately and revised the manuscript, which improved the readability.
All reviewers say yes for the two TMLR criteria, and most of them recommend acceptance.

For the camera-ready version, please use the "citet" command (remove parentheses) for references which are parts of sentences.

Decision: Accept (poster)