Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm
Authors: Changlong Wu
Mohsen Heidari
Ananth Grama
Wojciech Szpankowski
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sequential probability assignment
Online Regression
Logarithmic Loss
Bayesian Algorithm
Shtarkov Sum

Abstract: We study sequential general online regression, known also as sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We obtain tight, often matching, lower and upper bounds for sequential minimax regret, which is defined as the excess loss incurred by the predictor over the best expert in the class. After proving a general upper bound we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values of the data dimension and the number of rounds. To derive lower bounds, we use tools from information theory (e.g., Shtarkov sum) and for upper bounds, we resort to new "smooth truncated covering" of the class of experts. This allows us to find constructive proofs by applying a simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.

Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm
Changlong Wu²
Mohsen Heidari
Ananth Grama? Wojeiech Szpankowski*
CSol. Purdue University 2 Indiana University
wuchangl @arraangg@hwawaar @hawa ii ledu, (mheidari, ayg, szpar @purdue.
Abstract
We study sequential general online regression, known also sequential probability assignments, under logarithmic loss when compared against broad class experts. We obtain tight, often matching, lower and upper bounds for sequential minimax regret, which is defined as the excess loss incurred by the predictor over the best expert in the class. After proving general upper bound we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values the data dimension and the number rounds. To derive lower bounds, and for upper bounds we resort to new "smooth truncated covering" the class of experts. This allows us to find constructive proofs by applying simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.
tools from information theory (e.g.. Shtarkov sum),
1 Introduction
online learning and sequential probability assignments arising in information theory, portfolio optimization, and machine learning, the training algorithm consumes d dimensional data in rounds I E (1, T} and predicts the label fr. based on data received and labels observed so far. After prediction, the true label yı is revealed and the loss E(y, ût) is incurred. The (pointwise) regret is defined as the (excess) loss incurred by the algorithm over a class of experts, also called the hypothesis class.
More precisely, in each round 2 the learner obtains a dimensional input/ feature vector x, Rdd. In addition to x;, the learner may use the past observations (xr; Vr), < & to make a prediction ÿ of true label. Therefore, the prediction can be written as ÿ. d (y x²), where y represents the labels in the past / rounds, xf represents the input vectors in rounds, and Φi represents the strategy of the learner to obtain its prediction based on the past and current observations. Once prediction is made, nature reveals the true label yt and the learner incurs loss 5 x y + R. where ) and y are the prediction and true label domains respectively. Hereafter, we assume throughout 5 = [0, 13. y= = (0, 1} with logarithmic loss
E(gt. v/) yu log(ū:) (1 ye) log(1 (((1--))) (t).
In regret analysis, we are interested in comparing the accumulated loss of the learner with that of the best strategy within predefined class of predictors (experts) denoted by H. More precisely, H is a collection of predicting functions IR + with input being x; at time t. Therefore, given learner Φr, t > 0 and (Vt. x after I' rounds the pointwise regret is defined as
RIOT ... Hlxx)
Σ Elir v.) inf NEW
((h(x.).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where 인t = = Observe that the first term above represents the accumulated loss incurred by the learning algorithm, while the second summation deals with the best prediction within H. We highlight two useful perspectives on analyzing the regret next.
Fixed Design: This point of view studies the minimal regret for the worst realization of the label with the feature vector x" known in advance. Suppose that the learner has a fixed strategy Φi, t > 0. Then, the fixed design minimax regret for a given x" is defined
7 inf sup R(Ø", yy Hlx²)) o² y²
(2)
Further, the fixed design maximal minimax regret is given by:
r (H) = sup inf sup R(o", s² H|x").
(3)
o" g"
Sequential Design: In this paper we mostly focus on the sequential or agnostic regret in which the optimization regret is performed each time without knowing in advance x" y". Then the sequential (maximal) minimax regret is given by [24]:
(H)- = sup inf sup .. sup inp sup R(O".'' ; x1
(4)
91 y1
Xr 97 vr
In [37] it is shown that (H) 2 r (H) for all H. We will use (?H as our tool to derive lower bounds for (H).
Our main goal is to gain insights into the growth of sequential regret r (H) for various classes H and to show how the structure of H. as well as the relationship between d and T impact the precise growth of the regret. To see this more clearly, we briefly review regret in universal source coding.
Regrets in Information Theory. In universal compression, the dependence between regret and the reference class was intensively studied [10, 21, 27, 28, 32, 38, 39]. Here, there is no feature vector x", and the dimension d = 1. A sequence y² is generated by source P that belongs to class of sources S, which can be viewed as the reference class H in online learning. The minimax regret for the logarithmic loss is given by [9, 31, 10]:
r min max(- log Q(v") log sup P(y )), PES
Q v²
where Q is the universal probability assignment approximating the unknown P. The main question is how the structure of S impacts the growth of the minimax regret. Let m denote the alphabet size (in online learning, we only consider sources of order r, regret grows as m" (m - 1)/2 2 log T for fixed m [27, 21, 28, 33), while in [33] minimax regret was analyzed for all ranges of m and T. For non-Markovian sources, the growth is super logarithmic. For example, for renewal sources of order the regret is (TT//r++1) [7] and the precise constant in front of the leading term is know for = [11]. However, should be pointed out that [6. I] studied the general classes of densities smoothly parameterized by a d-dimensional data to obtain general results for minimax regret that can be phrased as an online regret.
2). It is known [10, 21, 27, 28, 32, 38, 39] that for Markov
Main Contributions. Our main results are summarized in Table 1. One of the main contributions of this paper is the concept of a global sequential covering used to prove constructively general upper bounds regret (Theorem 1). We establish Theorem 1 via novel smooth truncation approach enabling us to find tight upper bounds that subsume the state-of-the -fhth--rrt results (e.g., [23, 3]) obtained non-algorihmmicaly. In fact, Algorithm 2 developed in this paper achieves these bounds. Moreover, Theorem 1 provides optimal constants that are crucial to derive the best bounds in special cases discussed next. For general I. Lipschitz parametric class H. in Theorem 2, we derive the upper bound d log(T/a (d) + ((d) for T > d. In Theorem 3, we show that the leading constant (in front of d (og( is optimal for T' > d log())). Furthermore, we obtain the best constant for the leading term & log(T/d) when the Hessian of log f is bounded for any function Then, we show in Theorem 5 that the constant 1 in our bound optimal for functions of the form f(w, x)), where w IRd is the parameter of the function, (w, x) is the inner product in Rd, w and x are in a generaal &g norm unite ball, and T > d(*+2)/s, This result recovers all the lower bounds in [29] obtained for logistic regression (however, the technique of [29] works for other functions with
H (see Theorem 4).

---

bounded second derivatives, like the probit function). Lastly, when d 2 T, for a linear function of the form (w, x)] we show that the growth is at least ((T=<((++)) under lg ball and at most ((22/3) for lg ball (see Theorem and Example 2).
The main technique used in our paper (smooth truncation) is novel with other potential applications (e.g., average minimax regret). Instead of the conventional approach for truncating only the values close to {0, J. we truncate all values in [0, 1] in a smooth way (see Lemma 4). This allows us to obtain upper bound via a simple truncated Bayesian algorithm. Our proofs are substantially simpler (cf. (3]) yet provide tighter and often optimal bounds.
In summary, main contributions are: (i) constructive proofs through new smooth truncated Bayesian algorithm: (ii) the novel application of global sequential covering in the context of logarith- mic loss; (iii) lower and upper bounds with optimal leading constants; and (iv) novel information- theoretic techniques for the lower bounds.
Table 1: Summary of results
Constrains
d v.s T
Bounds
Comment
General a cover 9a
N.A.
(9(H) S inf {2aT + log (ga]) (.ac)
Theorem
General Lipschitz /
Any
(9((H)) S d log (z + +1 + O(d)
Theorem
under Eg ball Bounded Hessian
T >> dlogT
r4HH) dlog (5) O(dlog log T*)
Theorem 3
d log m9(H)) - 2 d +11 + +
Any
Theorem 4
of log f under & ball
f(w,x) x)) with f0( #
T > d(s+2)/=
(HHH) 2 a log (g.4))7)) ((d)
Theorem
under l, ball
(w, x) under& f, ball
T
(+H)) > *e
#11+//++11
Theorem 6
(w, x) under & ball
d T
2(T2(3) o (Hl) S ((T2/3)
Example
Related Work In this paper we study sequential minimax regret for general online regression with logarithmic loss using tools of information theory, in particular universal source coding (lower bounds) [1, 10, 18, 21, 26, 27, 28, 38] and sequential covering (upper bounds).
Most of the existing works in online regression deals with logistic regression. We first mention the work of [13], who studied pointwise regret of logistic regression for the proper setting. Unlike improper learning, studied in this paper, where feature
at time is also available to the learner, [13] showed that pointwise regret is (3 for d = 1 and ((VT) for d > 1. Furthermore, [17] demonstrates that regret for logistic regression grows as (d log T/d). This was further generalized in [12]. These results were strengthened in [29]. which also provides matching lower bounds. Precise asymptotics for the fixed design minimax regret were recently presented [14, 15].
Regret bounds under logarithmic loss for general expert class H was first investigated by Vovk under the framework of mixable losses [16, 34). In particular, Vovk showed that for finite class H. the regret growth is log [H| via the aggregating algoritiu (i.c., the Bayesian algorithm that we will discuss below). We refer the reader to [5. Chapter 3.5, 3.6] and the references therein for more results on this topic. Cesa- Bianchi and Lugosi [5] were the first to investigate log-loss under general (infinite) expert class H [5, Chapter 9.10, 9.11]. where they derived a general upper bound using the concept of covering number and two-stage prediction scheme. In particular, Cesa Bianchi and Lugosi showed that for Lipschitz parametric classes with values bounded away from {0. 1}. one can achieve regret bound of the form 2/2 log(T/d). When the values are close to {0, 1). they used hard truncation approach, which gives a sub-optimal bound of the form 3/2d log(T/d) (i.e., this bound is not explicitly shown in [5] but can be derived using their approach). Moreover, the approach of [5] only works for fixed design regret (or simulatable in their context). In [23], the authors extended the result of [5, Chapter 9. 9.10] to the sequential case via the machinery of sequential covering that was
3

---

established in [22]. However, [23] also used the same hard truncation as in [5] resulting in suboptimal upper bounds. In [3]. the authors obtained an upper bound similar the upper bound presented in Theorem via the observation that the log function is ceff-concordant. In particular, this allows them to resolve the tight bounds for non-pannan con-paametrri Lipschitz. functions that map [0, 1] - [0, 1]. However, their bounds are proved non-constructively. i.e., the proof does not provide an algorithm that achieves such bounds. [4], the authors used similar idea of smoothing for controlling the unboundedness of log-loss. however, they are assumed that the features x² are presented i.i.d.. More importantly, the results in [4] only holds for the average case regret.
2 Problem Formulation and Preliminaries
We denote X' as the input feature space and H. as the concept class, which is a set of functions mapping
X + +00, 1]. We use an auxiliary set W to index H. We say that function g is sequential if it maps X + [0, where X is set of all finite sequences with elements in X. We denote 9 as a class of sequential functions. T is a time horizon, then for any t E [T]. we write x' = {x1, ... x,} } and
y' {y1. 3e). We use standard asymptotic notation ftt) (g((t) if there exists a constant
C such that f(t)= I Cg(() for sufficient large t 2 0, and f(t) < g(t) if lim sup, ft)//g(t) = O.
We assume the log function log(ar) is the nature logarithm to the base of e.
The main objective of this paper is to study the growth of the sequential minimax regret (H)) for a large class of experts H. We accomplish this goal using two different techniques. For the lower bound, we precisely estimate the fixed design minimax regret (H|x² using the Shtarkov sum [31], discussed next. For the upper bound, we construct global cover set G of H and design new (truncated) Bayesian algorithm to find precise bounds with constants that are provably optimal.
Lower Bounds. We investigate the lower bound of adversarial regret r r4H(H) by considering its corresponding fixed design minimax regret r (H(xT)) and r+( = maxx? r (H(x") We are able do this due to the recent result [37], which we quote next.
Lemma (Wu et al., 2022). Let H. be any general hypothesis class and E be any loss function. Then (H( 2 r (H),
and the inequality is strict for certain H. and loss function f.
We establish precise growth of (?() by estimating the Shtarkov sum that was intensively analyzed in information theory [31, 10] and recently applied in online learning [30, 14]. For the logarithmic loss, the Shtarkov sum (conditioned on x²) is defined as follows!
(x((x def Σ sup Pr x²),
V'E(O,ITT
hEH
where (y |x*)= IT_ Mxx) ndh (1 h(x,)) v and we interpret h(x,) = P(y: 1[x,). The regret can expressed in terms of the Shtarkov sum (see [14, Equation (6) or [5, Theorem 9.1)) as
(H) sup (TH)'))
(5)
x²
It is known that the leading term in the Shtarkov sum for parametric classes H' is often independent of x [29, 12, 14, 15). Therefore, the Shtarkov sum often gives the leading growth of r (H|p?
independent of x which also suggests the leading growth of the agnostic regret (HL)..
Upper Bounds. We now discuss our constructive approach to upper bounds. In the next section, we present our Smooth truncated Bayesian Algorithm (Algorithm 2) that provides a constructive and often achievable upper bound. Here we focus on some, mostly known, preliminaries.
Let G C [0, 1 be any reference class. Let W be an index set of G and μ be an arbitrary finite measure over W. The standard Bayesian predictor with prior is presented in Algorithm 1. Based on this algorithm, we have the following two lemmas that are used to establish most of the upper bounds in this paper. See e.g., [19, Lemma 3] or [5, Chapter 3.3] for proofs.
"Note that the Starkov sum can be detined for any class of measures, however, here we only use the form for product measures.

---

Algorithm 1 Bayesian predictor
Input: Reference class G (ow W) with index W and prior μ over W
1: Set Pw x²) = for all w E W.
2: for 1= 1....., do
3: Receive feature vector X
4: Make prediction using the following equation:
De Sw
Iw Iw
(p |x "e'-")dp
Sw Pwo Pw) x 11
5: Receive label y/+
6: For w W, update: pa (1/ x²) = -- Per ( (v 1 x(-1)..
7: end for
Lemma 2. Let G be collection of functions 9w X - [0, [0, E W. Let yt be the Bayesian prediction rule as Step of Algorithm I with prior μs. Then, for any x" and y we have
Σ ((De Me) S -log Sw Puoll xFddd
Swidp ldp
where Pw (y² x=)= = = Eis (ow(()) and E is the log-loss in equation (1).
The following lemma bounds the regret under log-loss of finite classes, which well known.
Lemma 3. For any finite class of experts G, we have r (9) llog [9].
3
Main Results
We start with a concept of covering set called the global sequential cover that was used implicitly in [24, Section 6.1] for the Lipschitz losses and dated back to the ideas in [2].
Definition 1 (Global sequential covering). For any H. C [0, 1]x we say that class of sequential functions G C [0, 1]x* is global sequential a-covering of H at scale T if for any x3 e XT and h H, there exists
such that Vt E [T).
[h(x,) g(x')l S a.
Throughout we assume that Sasi.
Note that the global sequential covering is different from the (local) sequential covering used in [3] (originally from [24]), since our covering function does not depend on the underlying trees as in [24] This is crucial to apply our covering set directly in algorithmic way (see Algorithm 2). Particularly, enables us to establish our lower and upper bounds for Lipschitz classes of functions with the optimal constants the leading term. We further improve these results for Lipschitz class with bounded Hessian. Finally, we study cases when the data dimension d grows faster than by bounding the covering size through the sequential fat-shattering number. In particular, we prove matching (up to poly log T factor) upper and lower bounds for the generalized linear functions.
We are now in the position to state our first main general finding. Theorem 1. for any > there exists a global sequential a-covering set Gn of H, then
General Results.
(HH) S inf (2aT log (9. 05a51
and this bound achievable by Algorithm 2.
We should point out that Theorem also improves the results of [3] by obtaining better constants in front of both of and log Ga,l (i.e., from (4, 4) to (2, 1)). The proof is based on the following key lemma that is established in Appendix A.
Note that the covering functions in Definition can be viewed as the experts constructed in [24, Section 6.1]

---

Algorithm 2 Smooth truncated Bayesian predictor
Input: Reference class & with index set W and prior over W, and truncation parameter
I: Let (v. x9) for all w E W
2: for 1= 1,... do
3: Receive feature X,
4: For all w E W, set
(x')x 9w:
+ 20
5: Make prediction
91 Sw Iu (x*) (x' (no("" -2- x² x(11)d
Sw Per (y xt- xd/p
6: Receive label Vr:
7: For all w E W, update:
(v/ x²) f(0 Per (v | 1x(=1).
8: end for
Lemma 4. Suppose has a global sequential o-covering set 9 for some a E [0, 1]. Then, there exists a truncated set of G with |6 = [ such that for all xf 22 and H there exists a 9 ğ satisfying
Ph (y
x2
S (1 51++20 20x)
(7)
Pg(U
x²)
where
pM(y") xx))==
II (1x) and P5(v" T xx²)
II (1-
Proof of Theorem 1. We show that for any S a I an a-covering set Ga exists, then one can achieve the claimed bound for such a. To do so, run the Smooth truncated Bayesian Algorithm (Algorithm 2) Ga with uniform prior and truncation parameter We denote by G.. the truncated class of Ga as in Lemma (same as the step 4 of Algorithm 2). We now fix xT" ,y" By Lemma (with G being Ga), we have
T
T
T
Σ e(U Mc) S inf Σ E(g((')), + log Gaal = inf Σ ((g(x'), )1 + log Gal GEG.
GEGa
the last equality follows from |9.| = 1. Since Ein {([(xx)) v()) logpy x² for any function f. then by Lemma we conclude that
inf MEW
((h(x)). > inf BEG.
Σ e(((x'), vc) - T looo (1 + 2a:)
The result follows by combining the inequalities and noticing that log [1 +x) & x for all x 2 11
We further note that for any constant c C2 c for which the bound r (H) S CT + C2 log [aa holds universally we must have è 2 2 and C2 2 1. Therefore, our bounds are optimal with respect to the constants To see this, we let X' [T] and define g be the function that maps every E [T] to } Let H be the class of functions that maps to [1/2 a, 1/2 + a]. Clearly, H is a-covered by By noting that the maximum probability (1/2 aF (1 20 (1/2)* we compute the Shtarkov sum (5) to get:
(H) 2 (H) > log(1 + 20x ~ 2n,
where holds when sufficiently small. This implies that we must have e₁ 2 The fact that C2 > is due to the fact that mixability constant of log-loss is 1, which also follows from Theorem 3 below.
NNte that the optimally only shows that the constants in the form 2xT + log | cannot be improved. However, it is quite possible that one can obtain better bounds with different form.

---

Lipschitz Parametric Class. We now consider Lipschitz parametric function class, Given function f W x - [0, 1], define the following class
H (f(w,)) [0, 1] WEW).
where w E Wis often a vector in R
We will assume that [(w, x) is L-LLipschitz for every x, where L E RR. More formally, VW1, W2 E W and x E X' we have
If(w1, f(w2,x)) S L|[ -w2ll-
where | is some norm on W. For example, if we take W C R then the norm can be E,, l2 or loo norm. For any specific norm || ||. write (R) for the ball under such with radius in W.
In particular, denote by B (R) the ball in Fd of radius R under & norm centered at the origin.
Theorem 2. Let B (R) R + [0, 1]
be L-Lipschitz function under lg norm. Then
- (Hg) & min doo
(RRT d
+1) + 2d,
(8)
Proof. By L-Lipschitz condition, find a-covering in the sense of Definition 1, we only need to find a covering of B (R) with radius a/ L. By standard result (see c.g. Lemma 5.7 and Example 5.8 of [35]) we know that the covering size is upper bounded by
2RL a +1
By Theorem 1, we find
(2RL. a +1
r9HH)))) S inf 0ca<l
2all' dlog
Taking a d/T, we conclude
1RRT
(9 S d log
+ + 2d.
This completes the proof for 2 d. The upper bound T is achieved by predicting every time.
For logistic function f(w, x) (1 + - and E ( with E (1) our result recovers those of [12], but with better leading constant (the bound in [12] has constant 5). Note that, the result in [3] also provides a sub-optimal constant ~ 4. Moreover, our bounds have logarithmic dependency on Lipschitz constant L.
Example 1.
The question arises whether the factor in front of log T can be improved to d/2 instead of d as discussed some recent papers [29, 14, 15]. Theorem below, we show that, general, cannot unless we further strengthen our assumption (see Theorem 4). For the ease of presentation, we only consider the parameters restricted to Ea norm. The proof can found Appendix B.
Theorem 3. For any d, T, R, L such that T > dlog(RLT)) there exists L-Lipschitz function
f: B Rt) x Rd + [0, such that
RLT
r (HL) 2 dllog
d log 64 - d log log (RLT).
Lipschitz Class with Bounded Hessian. As we have demonstrated in Theorem 3 the leading constant of the regret for Lipschitz parametric classes can not be improved in general. We now show that for some special function f one can improve the constant to 3. as already noticed in [29, 14, 15]. For any function f R x d + Jo, 1], we say the Hessian of log f is uniformly bounded on X' c Rd
there exists constant C' such that for any w E Rd and x E X and E {0, 1} we have
u log f(w, x1 f(w,x)) x < C,
sup 1
where 22 is the Hessian at The proof of the next theorem can be found in Appendix C.
7

---

Theorem 4. Let f : IR x R + [0,1] be function such that the Hessian of log f is uniformly bounded by on X. Let
H = {f(w, x). E W.XEX)
be such a class of f restricted to some compact set W C R Then
Vol(W*)
(HH)) S log Vol(B3 (VI/CT) + d log
(10)
where W {ww - W, E ( (dd/C))) Vol(-) is volume under Lebesgue measure. In particular, for W (R), we have
2CR
r (HL)) - log
d +2 + d//22 + log log2.
Note that, Theorem 4 subsumes the results of [17, 29] where the authors considered functions of form f((w,x) x)) and requires that the second derivative log is bounded, see also [5, Chapter 11.10]. However, the KL-divergence-basee argument of [17] can not be used directly in the setup of Theorem 4 since we do not assume the function I has a linear structure. Our main proof technique of Theorem 4 is direct application of Lemma 2 and estimation of the integrals via Taylor expansion; see Appendix C for more details on the proof.
Finally, complete this part with the following lower bound for generalized linear functions under unit lg balls. See Appendix D for proof.
Theorem 5. Let f R-- - [0, 1] be arbitrary function such that there exists cı, C2 E (0, 1) and for all r > O we have [c1 - c2d a + c2d f(I-d" ") for sufficiently large d. Let
H (f((w,
(1), ()())
where 0. Then
T
( log d(s+2)/s
O(d)
(11)
where O hides some absolute constant that is independent of d, T.
Note that for the logistic function f(x) (1+ Theorem 5 holds with e₁ Therefore,
and C2 -5
1. If s then
d
T
(HH)) 2 2
log
- (d).
d3
2. If 2, then
d
T
(H()
log
Od))
2
d2
3. If s 0o, then
(H, 2 log
O(d).
Od).
This recovers all the lower bounds from [29]. We note that a simple sufficient condition for Theorem hold is require f0) Of f(z) is differentiable.
Large Growth. We now present some results for large d growing even faster than T. We will show that the size of global sequential covering (Definition 1) of class H. can be bounded by the sequential aat-shattering number of HL in similar fashion as [24]. We first introduce the notion of sequential fat-shattering number as [24].
denote {0, 1 be the set of all binary sequences of length less than or equal to A binary tree of depth d with labels in X' defined be map 7 1] X. For any function class H [0, 1 we say H a-fat shatters tree 7 if there exists [0, 1]-value tree s: {0, 1] + [0, I] such that for any binary sequence ef {0, 1). there exist h H. such that for all E [d]:
1. If e O, then h((((f-1) 5(6)
at 2. If e 1, then h(((()) 2-1 s(e +
'To get the upper bounds in [29] one only needs estimate the volume of E, balls, which is well known [36].

---

Definition 2.
The sequential a-fat shattering number of H. is defined to be the maximum number d(()) such that H. a-fat shatters tree T of depth d d(a.).
In the lemma below, we present an upper bound for the cardinality of the global covering with algorithmically constructed cover set Ga. see e.g., [24, Section 6.1]. We provide proof in Appendix E for completeness.
Lemma 5. Let H C [0, 1a be any class and d(a) be the sequential a-fatt shattering number of H. Then there exists global sequential a-covering set Ga of in Definition such that
dia/3)
3
3T
da/33)+1
Gal S
(12)
2
2a
2=0
Example 2. By [24] we know that the sequential o-fat shattering number of linear functions f(w, = kw, x)] with w,x E (1) of order 0(a= where in we hide a polylog factor. Lemma 5 implies that the global sequential a-covering number is upper bounded by
(37)
d(a/3)+1
(2a)
By Theorem 1, we have
(HH))
inf 0<a<1
2nT + δ
a² S Ö(12/)))
by taking = T/3/3 This bound is independent of the data dimension d.
Remark 1. Observe that for any class with sequential fat-shattering number of order a= one can achieve regret upper bound of order ((T//*+1) by Theorem 1. We refer to (24, 25 for the estimations of sequential fat-shattering number of a variety of classes.
Finally, we present the following general lower bound. See Appendix F for proof.
Theorem 6. For any 2 1, we define
Σ PS < }
D. p E 10
$1
We can view the vectors in D, as functions mapping [T] [0, 1}. Then
(D.) 2 (D.) 2 D(T=/s11).
(13)
To see why Theorem 6 implies lower bound for /'w,, x) 1(w, x) with d 2 T, as in Example 2, we take w,x x By (1) (i.e., with = T) and define x, e, with e, being the standard base of IR that takes value at position t and zeros otherwise. Note that the functions of Hy with f(w, = (w, x)| restricted on x" is exactly D2. Then
(H,) (H,) 2 (D2) S(T2/33
and this is matching lower bound of Example 2. Note that, it is proved in [23] that for function [w, x) (w,x)+1 one achieve the regret of form Ö(vT)s. Example implies that the generalized linear functions form f'(ww x)) can have different regrets with polynomial gap even with a simple shift on the value (though they have the same covering number). It therefore an interesting open problem to investigate a tighter complexity measure (instead of a covering number in Definition that captures this phenomenon.
4 Conclusion
In this paper, we presented best known lower and upper bounds on sequential online regret for a large class of experts. We accomplish this by designing new smooth truncated Bayesian algorithm, together with the concept of global sequential covering, that achieves these upper bounds. For the lower bound, that these techniques can be generalized to broader set problems, e.g., when the features x" present stochastically. We leave these the future investigations.
novel informationnthhoreee
approach based the Shtarkov sum. We expect
SA E2( ( lower bound for 2 VT be derived from Theorem recovering [23, Lemma 8J.

---

Acknowledgments
This work was partially supported by the NSF Center for Science of Information (CSol) Grant CCF-0939370, by NSF Grants CCF-2006440, CCF-2007238, and CCF- 2211423, and in addition by Google Research Grant and by Rolls Royce.
References
[1] A. Barron, J. Rissanen, and B. Yu. The minimum description length principle in coding and modeling. IEEE Trans. Information Theory, 44(6):2743-2760, Oct. 1998.
[2] Shai Ben-David, Dávid Pál, and Shai -Swartz... Agnostic online learning. In Conference on Learning Theory (COLT), volume 3, 2009.
[3] Blair Bilodeau, Dylan Foster, and Daniel Roy. Tight bounds on minimax regret under logarithmic loss via concordcccee.... In International Conference on Machine Learning (ICML), pages 919-929. PMLR, 2020.
[4] Blair Bilodeau, Dylan Foster, and Daniel M Roy. Minimax rates for conditional density estimation via empirical entropy. arXiv preprint arXiv:2 (et.1199.0000 10461, 2021.
[5] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning and Games. Cambridge University Press, 2006.
[6] B. Clarke and A. Barron. Jeffreys' prior is asymptotically least favorable under entropy of risk. Statistical Planning and Inference, pages 453 471, 1994.
[7] I. Csiszar and P. Shields. Redundancy rates for renewal and other processes. IEEE Trans. Information Theory, 42:2065-2072, 1995.
[8] Amit Daniely, Sivan Sabato, Shai Ben-David and Shai Shalev-Shwariz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
[9] L. D. Davisson. Universal noiseless coding. IEEE Trans. Information Theory, 11-1966:78337795 Nov. 1973.
[10] M. Drmota and W. Szpankowski. Precise minimax redundancy and regrets. IEEE Trans. Information Theory, IT-50:2686-2707, 2004.
[11] P. Flajolet and W. Szpankowski. Analytic variations on redundancy rates of renewal processes. IEEE Trans. Information Theory, 48:2911-299 2002.
[12] Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. In Conference on Learning Theory (COLT), 2018.
[13] E. Hazan, T. Koren, and K. Y. Levy. Logistic regression: Tight bounds for stochastic and online optimization. In Conference Learning Theory (COLT), pages 197-209. MIT press, 2014.
[14] 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, pages 755-771, 2021.
[15] Philippe Jacquet, Gil Shamir, and Wojeiech Szpankowski. Precise minimax regret for logistic regression. In IEEE International Symposium on Information Theory (ISIT), pages 444 449, IEFE, 2022.
[16) Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Mixability made efficient: Fast online multiclass logistic regression. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
10

---

[17] Sham M Kakade and Andrew Y. Ng. Online bounds for bayesian algorithms. In L. K. Saul, Weiss, and L. Bottou, editors. Advances Neural Information Processing Systems (NeurIPS), pages 641-648. MIT Press, 2005.
[18] R. E. Krichevsky and V. K. Trofimov. The performance of universal encoding. IEEE Trans. Information Theory, I1-27(2):199-007,, Mar. 1981.
[19] Jack Mayo, Hédi Hadiji, and Tim van Erven. Scale-free unconstrained online learning for curved losses. arXiv preprint arXiv:2202.056300 2022.
[20] Edward James McShane. Extension of range of functions. Bulletin of the American Mathemati- cal Sociery, 40(12):837-842, 1934.
[21] A. Orlitsky and N. P. Santhanam. Speaking of infinity. IEEE Trans. Information Theory, 50(10):2215-22330 Oct. 2004.
[22] A. Rakhlin and Sridharan. Online nonparametric regression with general loss function. In Conference on Learning Theory (COLT), 2014.
[23] Alexander Rakhlin and Karthik Sridharan. Sequential probability assignment with binary alphabets and large classes of experts. arXiv preprint arXiv: 501.07340, 2015.
[24] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances in Neural Information Processing Systems (NeurIPS), 23, 2010.
[25] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1)1111-55) 2015.
[26] J. Rissanen. Universal coding, information, prediction, and estimation. IEEE Trans. Information Theory, IT-30(4)6629-6366 Jul. 1984.
[27] Rissanen. Fisher information and stochastic complexity. IEEE Trans. Information Theory, 42:40-47, 1996.
[28] G. I. Shamir. On the MDL principle for i.i.d. sources with large alphabets. IEEE Trans. Information Theory, 1235) May 2006.
[29] Gil Shamir. Logistic regression regret: What's the catch? In Conference on Learning Theory (COLT)) pages 3296-3319, 3319. PMLR, 2020.
[30] Gil Shamir and Wojciech Szpankowski. Low complexity approximate bayesian logistic regression for sparse online learning. arXiv preprint arXiv:2101.12113 2021.
[31] Y. M. Shtarkov. Universal sequential coding of single messages. Problems of Information Transmission, 23(3):3-11 Jul.-Sep. 1987.
[32] W. Szpankowski. On asymptotics of certain recurrences arising in universal coding. Problems of Information Transmission, 34:55-61, 1998.
[33] W. Szpankowski and M. Weinberger. Minimax pointwise redundancy for memoryless models over large alphabets. IEEE Trans. Information Theory, 58:4094 2012.
[34] Volodya Vovk. Competitive on-line statistics. International Statistical Review, 69(2):213-248, 2001.
[35] Martin J Wainwright. Hligh-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[36] Xianfu Wang. Volumes of generalized unit balls. Mathematics Magazine, 78(5):390-33) -90-9999999,900 2005.
[37] Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Sequential vs. fixed design regrets in online learning. In IEEE International Symposium on Information Theory (ISIT), pages 438 438-443, 2022.

---

[38] Q. Xie and A. Barron. Minimax redundancy for the class of memoryless sources. IEEE Trans. Information Theory, pages 647-657, 1997.
[39] Q. Xie and A. Barron. Asymptotic minimax regret for data compression, gambling, and prediction. IEEE Trans. Information Theory, 46:431-445, 2000.
[40] Kenji Yamanishi. Minimax relative loss analysis for sequential prediction algorithms using parametric hypotheses. In Conference on Learning Theory (COLT), pages 32-43, 1998.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "bK_t8ccFlOR", "reviewer": "Reviewer_75nX", "summary": "The authors consider the problem of sequential prediction of binary data scored with log loss against potentially large classes of reference predictors. Using the method of [RST10] to sequentially construct covers, they algorithmically recover minimax rates that previously were only achieved non-constructively. They also improve constants of (4,4) to (2,1), which they prove are sharp for some classes that have uniform (non-sequential) covers.", "questions": "I raised all my questions in the body of the review.", "limitations": "I see no negative societal impacts of this theoretical work.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Review Summary\n\nThe main contribution of the work, which is algorithmically achieving the best-known minimax rates for this problem, is a significant contribution to the literature. I have minor comments regarding (a) the authors framing of novelty, as all of the algorithm components exist in the literature already (this is not a bad thing, but warrants stronger citations); and (b) the authors claims of generically tight constants, since it is not clear that the results are even tight in terms of log factors for classes that cannot be uniformly bounded over the covariate space (such as the high-dimensional linear functions example, in contrast with Lipschitz functions on bounded sets). I am confident these concerns can be addressed in the revision period.\n\n## Concerns to be addressed\n\nMy first concern is regarding the claims of novelty in this work. The notion of global sequential covering, while concisely defined in Lemma 1, is not novel in my opinion. As the authors cite (unfortunately, only in parentheses and on page 9), this notion was exactly considered by [RST10] in their Section 6.1, who also already proved Lemma 5 (their Lemma 15), albeit with slightly worse constants inside (eventual) log factors. Similarly, the distinction between this notion of sequential covering and the one used for nonconstructive minimax rates (by, e.g., [BFR20]) is only consequential for the algorithmic aspects (which, as noted, is significant and the main contribution of this work is to provide an “implementable” algorithm). This means that Eq. (6) (up to an improvement of constants 4,4 to 2,1) is exactly the same as the main result of [BFR20], since we currently only know how to use this regret bound by further upper bounding it by either the uniform metric entropy (for classes that can be covered without knowledge of covariates) or by the fat-shattering number (for classes that cannot), and both notions of entropy are bounded in the exact same way.\n\nThe idea of Bayesian averaging a cover with smoothing has also already been used in the literature to obtain tight rates for log loss regret [see BFR21], and is implicit at least as far back as [YB99] (see the discussion after their Lemma 2); notably, these works are only in the i.i.d. setting, although the smoothing is purely used in the present work to deal with the unboundedness of log loss (the adversarial sequential aspect is handled by the existing cover notion). The truly novel result in the present work is Lemma 4, which allowed the authors to apply these existing notions to the present problem specifically for binary responses. I believe the rhetoric and citations can be updated to reflect this history.\n\nMy second concern is regarding the claims of general optimality for the constants. The authors have multiple results of classes for which they prove sharp leading constants. However, for each of these, the class is already uniformly bounded in sup norm over the covariate space, and hence standard notions of covering could be used to control the size, with no need to consider sequential covers (of either kind). For classes that actually require the sequential covering notion, such as the linear classes that require an empirical covering (i.e., it depends on the observed covariates), it is unclear whether even the log factors are tight, let alone the constants. Further, as shown by [BFR20, Corollary 4] (and repeated after Theorem 6 in the present work), sequential fat-shattering (which both [BFR20] and the present work have to use to control their respective covering notions) is insufficient to fully characterize minimax regret. In summary, I think the claim that “our bounds are optimal on the constants” after line 167 is unsubstantiated.\n\n[RST10] - Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances in Neural Information Processing Systems, 23, 2010.\n\n[BFR20] - Blair Bilodeau, Dylan Foster, and Daniel Roy. Tight bounds on minimax regret under logarithmic loss via self-concordance. In International Conference on Machine Learning, pages 919–929. PMLR, 2020.\n\n[BFR21] – Bilodeau, Foster, and Roy (2021). Minimax Rates for Conditional Density Estimation via Empirical Entropy, arXiv:2109.10461\n\n[YB99] – Yang and Barron (1999). Information-theoretic determination of minimax rates of convergence, Annals of Statistics.\n\n## Typos\n\n- The definition of regret after line 32 is slightly inconsistent with the usage that follows it, and should be better defined as $R(\\phi^T, y^T, \\mathcal{H} | x^T)$.\n- line 139, “reference class map” is undefined, although reasonably clear; I hope the authors can just be a bit more precise with the wording\n- Set notation for sets of functions is somewhat inconsistent, eg write $\\mathcal{G} \\subseteq [0,1]^{\\mathcal{X}^*}$ in Definition 1 to match $\\mathcal{H}$\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5VCm_vJd7m", "reviewer": "Reviewer_K3Wr", "summary": "In this work the authors study bounds on the sequential minimax regret of sequential probability assignment against a set of expert predictors. They provide both lower- and upper-bound on the adversarial regret that either match or improve on previous bounds. For the upper-bounds, their main technique relies on the idea of \"sequential $\\alpha$-covering\" of a experts' class, which builds upon on similar idea from previous work, and using these covers in the classical Bayesian predictor algorithm. They further sharpen such bound when the experts' class is parameterized and Lipschitz over these parameters, and also give sequential covering for experts classes with low fat shattering number. Finally, they also provide interesting lower-bounds on the adversarial regret, which they lower-bound by lower-bounding the maximal minimax regret.", "questions": "Unfortunately I do not have interesting technical questions for the authors. However, I'd like to know whether and how the authors plan to improve the presentation of the paper based on what I've discussed. Also, if you could give some intuition on how Shtarkov sums are used to prove lower-bounds, I'd be very interested to hear. However, I know the authors will be time-constrained during the rebuttal and I don't think my review will be a problem for the acceptance of the paper, so feel free to not give a thorough rebuttal to my review.", "limitations": "Although the discussion of related work is hard to parse and sometimes limited, the authors do discuss some limitations of their results and future directions of research.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Although I am not very acquainted with the latest results in regret analysis of sequential probability assignment, this paper seems to have strong theoretical results: better bounds on the minimax sequential regret obtained by interesting ideas combining global sequential coverings (which expands on def of previous work) with Bayesian update rule;\n- They also prove lower-bounds that match many of their rates, but I can't say much about the techniques since they do not discuss it at length in the main body of the paper (and I didn't have the time to look into the appendix);\n\n### Weaknesses\n- Although I'm making a list, all weaknesses lie under the umbrella of **presentation**. I had a hard time going through this paper due to a collection of reasons (some of which I'll list). In general, the discussion of related work and of the techniques used is sub-optimal and very hard to go through if one doesn't have the other papers fresh in one's mind. A clear example is that only after reading the first couple of pages of [3] (Bilodeau, Foster, Roy 2020) and skimming their results I could digest the paper properly;\n- About high-level presentation problems, nowhere in the main body of the paper the authors discuss how they use Shtarkov sums to give lower-bounds. They go through the trouble of even defining it, but only use it on Theorem 1 to prove an upper-bound. Since I do not have time to look through the appendix I'm left wondering why Shtarkov sums are helpful in the l\n- For an example of parts where I had trouble reading, I'll walk through my experience in the introduction. The first paragraph of the introduction introduces the problem in a very general (player predicts \"labels\" instead of probabilities). The second paragraph makes the definition precise and general, and right after already specializes to probability prediction, so it makes one wonder if the generality of labels was even necessary (even more so in the introduction!). Yet, until this point I was still following. When the authors introduce fixed and sequential design, I had to spend quite some time parsing the notation and understanding the differences since the text does not seem to try to guide our understanding. At this point I had to spend more effort than usual just to understand *the introduction* of the paper. But then the \"regrets in information theory\" section was very dense and even after reading the paper I don't think it helps me place the contribution of the authors in the literature nor does it help me understand the motivation/\"hardness\" of bounding the regret. In fact, the related work subsection that comes later does a better job (but I'll comment on this later), and I don't know what is the purpose of the section of regret in info theory. Yet, by the end of the introduction I was not sure if I had understood the problem very well, and I definitely could not quite put my finger on what were the bounds that the community had worked on before. That is when I went through [3], whose introduction and defs I could read without much effort, and it helped me understand the motivation and setting much better;\n- When comparing your results and techniques with other works, the authors seems to write as if we had these other work fresh in our minds. Even though I do not expect you to explain all the previous work in your paper, more formally stating their bounds or techniques so that I do not need to open their papers to understand what you mean in some passages of your paper would be very helpful. A couple of examples: (1) Before Thm 1 you mention something about trees in [23], but without opening the paper a reader cannot even understand why it is a problem or what it means. After Thm 1 you also say that you obtain better constants if compared to [3], but without opening their paper I do not know how much better theses constants are and whether they analyze a more general case. At least stating the constants [3] gets should not take much space; (2) In example 1 it is not immediately clear what constants are being discussed (although one can infer which constants after reading the rest of the paper) and the authors also mention  logarithmic dependency on $L$, but they never mention what were the dependency on $L$ on previous work (was it better? worse?)\n\n\nSome briefer comments on presentation:\n- The discussion between lines 167 and 170 should be a proposition, and the authors could be more explicit on what \"universally\" means;\n- The definition of Big-Oh notation in lines 120 and 121 is a bit wrong (it is not for all $t \\geq 0$, only for sufficiently big $t$);\n- \"function is self-concordance\" -> \"function is self-concordant\"\n- Lines 205-210 are extremely hard to parse (and formatted weirdly);\n- Line 213: cardinally -> cardinality\n- In line 214 you cite [23] but it only made me confused: is it that the next lemma is due to them, or they do something related?\n\n### Summary\nI think this is a technically strong paper which is very hard to parse for readers not well-acquainted with the latest work on this topic. I'm favorable towards acceptance. For now I only have my score in \"weak accept\" because I have a hard time assessing impact (even after skimming a bit of related work), but I might increase my assessment during the rebuttal phase.\n\n\n### Post-rebuttal\nIncrease my score from 6 to 7 based on other reviews and authors responses. This is definitely a strong paper and my initial problems with presentation will be addressed as much as possible. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2XkS45eWoNn", "reviewer": "Reviewer_Gq3y", "summary": "The paper presents new tight lower and upper bounds for online regression with the log loss, with new and simple proofs. For the upper bounds, the authors prove their result using a new and simple truncated Bayesian algorithm. This analysis of this algorithm involves a new complexity measure---the Global sequential covering number---which the author show is upper bounded by the sequential fat-shattering number. For the lower bound, the author use the fact that the sequential minmax regret is lower bounded by the regret in the fixed design setting (known covariates), which they further lower bound using concepts from information theory such as the Shtarkov sum.", "questions": "How do your results compare to e.g. \"An improper estimator with optimal excess risk in misspecified density estimation and logistic regression\"?", "limitations": "The presentation can be improved in places. Here I give a couple of suggestions (some minor):\n- Line 141: [4, Chapter 3.3] are you referring to Eq 4?\n- Lemma 4 should refer to the specific truncation mechanism in Algorithm 2 (not just there exists). This is required in the proof of Theorem 1.\n- To be consistent with the notation I would use $(${$0,1$}${}^d)^*$ instead of {$0,1$}${}^d_*$. \n- The fact that the global sequential covering number can be bounded by the fat-shattering number should be mentioned earlier in the presentation (perhaps around the definition of the global sequential covering number).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents improved upper and lower bounds for the problem of online regression with the log-loss. The approaches used to achieve these results are new and simple, which constitute a solid contribution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept