Smoothed Analysis of Sequential Probability Assignment
Authors: Alankrita Bhatt
Nika Haghtalab
Abhishek Shetty
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Online learning
Log loss
Information theory
Smoothed Analysis
Beyond worst case analysis
Oracle Efficient Online Learning
TL;DR: We study sequential probability assignment in the smoothed adversary model, presenting both statistically and computationally efficient algorithms that achieve the rates depending on offline complexity measures.

Abstract: We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning. This leads to optimal (logarithmic) fast rates for parametric classes and classes with finite VC dimension. On the algorithmic front, we develop an algorithm that efficiently taps into the MLE oracle, for general classes of functions. We show that under general conditions this algorithmic approach yields sublinear regret.

Smoothed Analysis of Sequential Probability Assignment
Alankrita Bhatt California Institute of Technology abhatt@caltech. edu
Nika Haghtalab
University of California, Berkeley
nika@berkeley. edu
Abhishek Shetty
University of California, Berkeley shetty@berkeley.com
Abstract
We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information coommation-thooettcaalll theoretically optimal minmax rates as well as framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning. This leads to optimal (logarithmic) fast rates for parametric classes and classes with finite VC dimension. On the algorithmic front, we develop algorithm that efficiently taps into the MLE oracle, for general classes of functions. show that under general conditions this algorithmic approach yields sublinear regret.
Introduction
Sequential probability assignment - also known online learning under the logarithmic loss - is fundamental problem with far-reaching impact on information theory, statistics, finance, optimization, and sequential decision making [Rissanen, 1983, 1984, Cover, 1991, Feder et al., 1992, Xie and Barron, 1997, Merhay and Feder, 1998, Xie and Barron, 2000, Yang and Barron, 1999, Jiao et al., 2013, Orabona and Pál, 2016, Foster al., 2018). In recent years, methods for incorporating contexts or side information into sequential probability assignment have gained much attention [Rakhlin and Sridharan, 2015, Fogel and Feder, 2017, 2018, Foster al., 2018, Bhatt and Kim, 2021, Bilodeau et al., 2021, Wu et al., 2022a], in part due to their newly forged connection to sequential decision making applications, the contextual bandit problem, and learning in Markov Decision Processes (MDPs) (see e.g. [Foster and Krishnamurthy. 2021] and [Foster et al., 2021a])- In this setting, a forecaster who has access to historical data T1a-11 /1:1-1 consisting of contexts x,, (e.g., day T's meteorological information) and the outcomes yr E {0, 1} (e.g.. whether T was a rainy day) wishes to predict Yr given
context Z₁, The forecaster uses probabiliry assignment Pt to estimate the probability of yt = 1 outcome and incurs the logarithmic loss, i.e., log Pt (ye),, which rewards the forecasters for having assigned high probability the realized outcome. The goal of the forecaster is to suffer low regref against a chosen reference class of predictors.
A large body of prior work sequential probability assignment with contexts has focused settings where contexts are presented i.i.d. from an unknown distribution (see [Fogel and Feder, 2017, Bhatt and Kim, 2021, Bilodeau et al., 2021, Wu et al., 2022a] and the references within); this problem is also referred to as conditional density estimation. In these cases, sequential probability assignment is known to enjoy small regret for several reference classes such as Vapnik-Chervonee Chervonenkis (VC) classes. On the other hand, attempts to consider context distributions that evolve unpredictably and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

adversarially have faced strong impossibility results even for simple reference classes of predictors. For example, for the reference class of simple one-dimensional thresholds assigning Pt (, I [0, 1], regret is bounded by O(log T') in the i.i.d. case [Fogel and
a} + 01 I (xxa > a} for Feder, 2017] but is lower bounded by S2(T) when the sequence of contexts is chosen adversarially (folkiore e.g. Littlestone [1988].. In the face of the increasing need to adapt to evolving contexts in modern applications, these impossibility results indicate that new models adversarial behavior must be considered for obtaining rigorous guarantees that guide the design of sequential probability assignment in practical applications.
In recent years, smoothed analysis of adaptive adversaries [Haghtalab et al., 2021, Rakhlin et al., 2011] has emerged as a framework for going beyond the worst-case adversaries while making minimal assumptions about the adaptive process that generates a sequence. In this setting, contexts are chosen from an evolving sequence of so-called o-smooth distributions, whose density is bounded above by 1/a times that of a base measure (such as the uniform distribution). Remarkably, these methods, established by Haghtalab et al. [2021] for (-1 loss and extended to regression by Haghtalab et al. [2022], Block et al. [2022], have established performance guarantees for the sequential prediction problem that matches the optimal performance in the i.i.d setting. This raises the question as to whether the sequential probability assignment problem may similarly enjoy improved minmax regret bounds for smoothed adaptive sequences.
Beyond minmax rates, an important feature of probability assignment and, its analogue, density estimation is the availability of fundamental and natural estimation techniques such as maximum likelihood estimation (MIE).. For i.i.d. sequences, under general conditions, MLE is known to be optimal asymptotically and often serves as a starting point for designing more sophisticated estimators. Going beyond i.i.d. sequences, we ask whether MLE can be made to achieve good statistical behavior on adaptive sequences. More generally, algorithmic perspective is increasingly important for the sequential probability assignment problem and its applications to contextual bandits and reinforcement learning (where algorithm design is as fundamental a consideration as minmax rates [Agarwal et al., 2014, Simchi-Levi and Xu, 2022, Foster and Rakhlin, 2020, Langford et al., 2007, Foster et al., 2021b]). In this space, oracle-effciennt sequential decision making algorithms that repurpose existing offline algorithmic routines have received special interest [Kalai and Vempala, 2005, Dudik et al., 2020, Wang et al., 2022, Kakade et al., 2007, Simchi-Levi and Xu, 2022]. Here again, recent progress smoothed analysis for sequential prediction with 0-1 loss and regression loss [Haghtalab et al., 2021, Block et al., 2022] has shown promise in bridging the computational and iooomatioontheoreticc gaps between what is obtainable in the i.i.d. case and for smoothed adaptive sequences.
In this paper, we initiate the study of smoothed analysis for sequential probability assignment and seek to understand fundamental information-theoreti limits on the minmax regret as well as design natural and oracle-efficient algorithms for this problem. Additionally, the smoothed analysis setting, maximum likelihood estimation can efficiently address sequential probability assignment while achieving small regret. To the best of our knowledge, our work is the first to consider oracle-efficient algorithms (and particularly the MLE) for the sequential probability assignment problem.
investigate whether in
1.1 Main results
Reduction to transductive learning, Our first main result is a reduction from regret bounds against a smoothed adversary to regret bounds against (a generalized version of) transductive adversary. That is, we show that the minimax regret in the smoothed analysis setting is upper bounded by the minimax regret in the setting where a set of contexts is provided to the learner and the adversary is constrained to picking the contexts from this set. For F, a class of hypotheses mapping contexts to [0, 1]. let us define the minmax regret in the transductive case over times steps when a context set of size M is provided to the learner to be RA (F). We establish in Theorem 3.1 that for all -msoohh sequences the minmax regret
satisfies, for any k >> 1,
RT(F, F)
(F) + T2 -).
Furthermore, in Theorem 3.4 we upper bound RAT (F) by connecting the worst case adversarial regret in this setting to the scale-sensitive VC dimension of F which is a prototypical off complexity of the class. Our results obtain logarithmic dependence on 1/o. In particular, in
2

---

Corollary 3.4.1, we show that for VC classes (and parametric classes) the regret is bounded by Rr)F,o) 0
dllog (
)
where is the VC dimension class F.
Efficient Reduction from Sequential Probability Assignment to MLE. Our second contribution initiating the study of oracle-efficient algorithm design for sequential probability assignment. In particular, for small alphabet size, we design a natural algorithm (Algorithm 1) that efficiently uses an MLE oracle and achieves sublinear regret in the smoothed setting. Our Theorem 4.1 gives general regret bound in terms of the statistical complexity of the class F and the smoothness parameter
For VC classes, this achieves regret rate of T L. To the best of our knowledge, this is the first orucle-efficient algorithm and analysis of the setoowtth--eeturbe--leeddd style algorithms for the logarithmic loss.
assignment for VC classes, For VC classes we explicitly construct sequential probability assignments and establish their regret guarantees in the smoothed setting. That is, we construct a probability assignment based on Bayesian mixture over J that satisfies Rr a) s
Probability
Cdlog : where d is the VC dimension of class F. While this approach is not oracle-efficient, it
indeed achieves regret bound with optimal dependence on T and Ø. This motivates a natural direction for future work as whether such mixture- -based methods can be implemented oracle efficiently or if there is a tradcoff between the regret and the computational complexity of sequential probability assignment.
2 Preliminaries
Let X' be set of contexts and y {0, 1}. Then, the problem being studied entails sequential game where at each timestep f. based on the history of contexts T1:t := (#1...... .......... .r)) where x; E X and associated bits V1-1-1 E {0, 10,1 the player must assign probability ((11=144 (1a-11))) to what the upcoming bit yt will be. Once the bit y/2 is revealed (possibly in an adversarial fashion) the player incurs loss log g(v ( (1 and the game proceeds to the next step. For a hypothesis class C {X + [o, 1]]. the associated regret for a probability assignment strategy 2 = {g( (rit V1a-1) for fixed Fi.r, Vi.r is
T
DIFF =
log
inf fET
log
Pf (3cl
1=1
where p)(1 = (xx);; i.e. the function assigns probability Bern(J(az)) to the upcoming bit given the context Tiz-
Our statistical results apply to general loss function l and general actions of the learner a,. For set of inputs (x,, w))) specified by the adversary and set of actions {ar)/=s of the learner, regret defined by
T
RF N1 Bi:r, (1:))
llas (11,80)
Σ (((x)), (x,, FEF
inf
where for log-loss a, = g( Fi:e, 11:-11:; the action is probability mass function (pmf) over {0, 1}.
The regret in 1) is often studied under various adversary models; i.e. various different probabilistic assumptions (or lack thereof) on the model generating sr and ye. In this work, we consider worst-case Ve (in contrast to the realizuble setting where Y, ~ [ern( for fixed unknown f E F)) and X, ~ D, where D,s form an adaptive sequence of smooth distributions.
Definition 2.1 (Smooth distribution and adversary [Haghtalab et al., 2020J). Consider a fixed and known base distribution j on X' (such the uniform distribution if X' supports it). A distribution
D on X' said to o-smooth for all measurable sets C X ((A) S ((A) We denote the set of all a-smooth distributions by A, (μ).. An adversary, characterized by a joint distribution D with X, ~ DD (where D, may possibly depend on the history) is said to be a-smooth adaptive adversary if D, E Ao (1) for all t (1.....7) T).
3

---

In order to bound this, we consider generalization the notion of online learning that is referred to as transductive learning. In this setting, at the start of the interaction the adversary chooses set of contexts X MM for some M > T and provides this the player. The game proceeds as The minmax regret for o-smooth adaptive adversaries is then given by
(r = inf
Ex
max Rr X1r, 91.7
smaothed
9
where 2 is the set of all probability assignment strategies.
We particularly interested in how geometric properties of the function class F affect R₂ (F, o.). There are several notions of covering numbers and combinatorial dimensions that quantify the "richness" and complexity of a class, but the scale-sensitive VC dimension will be of particular interest to us and is invoked in our results.
Definition 2.2 (Scale-sensitive VC dimension). Let be a function class. For any a > and points Fi...... Zm X, say that FF shatters the set Ti.... Zm scale if there exist ......... Sm E R such that for each E 1 there exists function f E F such that E; (f(z;) 8;) 2 2 The scale sensitive VC dimension at scale a of F, denoted by (C a is defined as the largest m such that there is set of y points I1, ..... Im E X such that F shatters the set at scale The (traditional) VC dimension of a binary class F is defined as (C = lima-su VC (F,,))
Throughout,
the following result of Haghtalab al. [2021] about a-smooth distributions. This results aids us reduction from smoothed learning to transductive learning.
Theorem 2.1 (Coupling Lemma of Haghtalab et al. [2021]). Let Da an adaptive sequence of a-smooth distributions on X. There is coupling Il such that
Z.,,. Xx. 7........ 7. ~ II
1. Xi..... Xt is distributed according 2o.
2. For every S (2.,,)2 are uniformly and independently distributed on X, condi- tioned Xı,..., Xj-1-
3. For any t. with probability at least 1 - 1-(1111 o1 Xx f f
3 General reduction to transductive learning
In this section, we will consider the minimax regret for the smoothed online learning game with respect to the loss function' against general class of functions F. In Section 3.1, we will show that the minimax regret can be reduced to the minimax regret for a version of transductive learning with respect to the same loss function and class of functions. In Section 3.2, give general upper bounds for the transductive setting. There is a subtle but important difference between reduction that directly involve regret compared recent efforts (such Haghtalab al. [2021], Block et al. [2022], Haghtalab et al. [2022]) using reductions between proxies of regret, such as covering numbers and sequential complexities. This is particularly important for log loss since its complexity is not captured by covering numbers. We discuss this point further in Section 3.2.2.
3.1 Regret-to-regrel Reduction
We work with general loss function and general actions of the learner ag. We note that, we can write the minmax value of the smoothed setting in extensive form as
Rr(F.o)= = sup ExieD, inf sup sup DiEdo(a)
ExgxD, inf sup- az 82
(2)
sup EX,~D, inf sup R(F,X1xx Vher orr)) DrEA.(w)
ay
'The reduction works for general loss functions with the property that the worst-case regret for horizon T is bounded T', but think about l being the loss throughout this section for concreteness.

---

before with the adversary picking (Zt, y1) at time and the learner picking an action and suffering loss E(a,, (It, ye)). However, the adversary is now constrained pick 2, E at all times t. We can then define the minmax regret indexed by X as
R (F, = max inf sup.... max inf sup R(F, Tu. Mirry (1:r; mieX an in ayeX ar yr
Furthermore, define the worst-case transductive learning regret for sets of size as R (F) x (F, (F, In the following theorem, we show that the regret against o-smoothed adversaries is bounded by the regret in the transductive learning setting when the set contexts is drawn from the base distribution μ.
Theorem 3.1. Let FF be any class of functions from X to lK and les (0,1) Then, for any T and k. we have
RT KI
Theorem 3.1 shows that reduce the problem of evaluating the minimax regret for smoothed adversaries to evaluating the minimax regret for transductive learning. Note that the second term
(1 - o)* I e- -eo and thus, in order to get bounds that are sublinear one needs to consider k clog T/or for an appropriate absolute constant As we will see in the next section, this leads (x <
to logarithmic dependence on o=!. Moreover, by Theorem 3.1 and since Ex~μ²² (r, Rr(F, o), we can see that the transductive learning regret exactly captures the smoothed regret up to polylog factors.
3.2 Bounds for Transductive Learning
In this section, we discuss ways to upper bound transductive learning regret Ry (F) so to achieve bounds on (FF,o)) via Theorem 3.1.
3.2.1 Using Covering Numbers
One of the approaches common in online learning is to characterize the regret in terms of geometric properties (such as covering numbers) of the function class F. The notion of covering required varies depending the loss function and the stochastic properties of the data-lypically completely adversarial problems require stronger notions sequential coverings [Rakhlin al., 2015a, 20]5a.b] while for stochastic problems usually weaker offline coverings suffice. In our smoothed case, we show that the offline complexity notion of scale-sensitive VC dimension as defined in Definition 2.2 is adequate. Similar ideas were considered for the case of regression and convex Lipshitz losses in Haghtalab et al. [2022], Block et al. [2022].
Let us first define the notion of approximation according to which cover will be constructed; we will consider a pointwise approximation. This notion is similar to the notion of global sequential covering in Wu et al. [2022b].
Definition 3.1. Let be a function class. set of functions f said to be a e-covering F if for any f f F there exists g E f such that supzex [x() - g(x)] S c. We will use A (F, c) to denote the size of the minimal c-covering of F.
Note that while the metric in Definition 3. is quite stringent, using this cover in the transductive learning case requires us to only consider function classes with bounded domain size. We capture this using the following theorem.
Theorem 3.2 (Upper bound on transductive learning). Let F be functiionn class and e > 0. Then,
T
(
inf
inf
sup =KX
log (Flz, 2cT
where Flz is the projection of hypothesis class F on the set Z.
5

---

The proof of this theorem follows from relating transductive learning to the worst sequential prediction on finite set of points using formalism presented in Wu et al. [2022b]. The proof of this theorem is deferred to the Appendix C.
Next, we recall that the covering number (FF is bounded as function of the scale sensitive VC dimension of the class F and the number of points in the domain.
Theorem 3.3 (Rudelson and Vershynin [2006]). There exist universal constants e, such that for all 0, any function class F defined on finite set X, and > 0, we have
log.N((,c) & C- CCCC, cac) ( log +o ( (VC(F, cE)E
C|21
Finally, putting together Theorem 3.1, Theorem 3.2 and Theorem 3.3 we get the following.
Theorem 3.4 (Minimax smoothed regret and scale-sensitive VC dimension).
RT(F,o) S inf (C.VC(F cave) log ++a k,a,s50
CKT
+ 2:7 + + (72 (1
VC(FF
We can instantiate the bound in Theorem 3.4 in terms of and for two particularly interesting cases: when VC(F, .) scales as dl log (1/e) (often referred to as parametric classes) and when VC(F, e) scales as = (often referred to nonparametrie classes). A canonical example of the former are VC classes; for a class with VC dimension d, VC(JVC, e)) = Cd log (+) (see for example [Vershynin, 2018, Theorem 8.3.18).. A canonical example of the latter are functions of bounded variation, FBV which have VC(FBV c) (see for example [Musayeva, 2020, Bartlett et al., 1997]). This class is known to have unbounded sequential covering numbers [Rakhlin et al., 2010] and therefore is not learnable with a worst-case adversary-this can be seen simple consequence of the fact that JBV contains all one-dimensional thresholds.
Corollary 3.4.1 (Rates for parametric and nonparametric classes). ICCC(F,e) = dllog (1/e), then for large enough? T
RT(F,o)50 so(a poly log
-
IFCC(F,)) = then
T (0
poly log
In particular, note that Corollary 3.4.1 shows that for VC classes RT .00) = do (a)
(tight, see also concurrent work [Wu al., 2023] for similar bound) and for functions of bounded variation RFBF o) = Ô VT
log log (t) note that the minmax rates for the worst-case adversary scale as S2(T) for both these cases. We note that the above bound may be loose for general nonpara- metric classes, but should be improvable using a multiscale (chaining) version of Theorem 3.4 but we do not focus on this here.
Though the above results give satisfactory bounds in the minimax for many classes J of interest, is useful to consider explicit constructions of probability assignment rules. For the case finite VC dimension, give explicit probability assignment rule by considering diseretization of the class and using mixture probability assignment rule. In particular, this strategy (denoted by 2CC)
yields optimal regret (FVF .., VV) < dd )z)) For the formal statements, proofs and detailed discussion see Appendix D.
3.2.2 Examples without Covering numbers
This reduction approach to characterizing minmax regret the log-loss is interesting since all previous approaches have used covering numbers of some kind-either sequential covering numbers

---

or stronger notions of global covering. However, in stark contrast to the 0/1 loss and several other loss functions [Rakhlin et al., 2015b]. covering numbers cannot capture the minmax regret for the log-loss, at least in the adversarial case. Consider the following class of functions context set
X = B2 (where B2 denotes the unit & Euclidean ball) FLin
(2,00)+11
w E
1B2
For
leader (FTRL) based algorithm achieving regret O(vT) However, Bilodeau et al. [2020] show upper bound on the regret in terms of sequential covering numbers which is not improvable general this shows that sequential covering numbers not adequate to capture the minmax regret rates for the log-loss, Wu et al. [2022b] further consolidate this by considering the following class, closely resembling Fllin,
this class, Rakhlin and Sridharan [2015] construct sellow-the-reguaane
FAbsLin
x x (xz, w)|
132
[Wu et al., 2022b, Example 2, Theorem 6] establish that the
minmax regret for J-AbsLin is @(T2/3). demonstrating the surprising fact that by simple linear transformation of the hypothesis class (which does not change covering number) one can obtain minmax rates that differ by polynomial factor! On the other hand, our reduction-based approach bypasses the need for using any covering based arguments and therefore would lead tight (at least up to poly log(T/a)) rates.
We remark that exact characterizations of the minmax regret with log-loss (often referred as the minmax redundancy in the information theory literature) in the no-context (adversarial) case is most often calculated by studying the so-called stochastic complexity of the class F [Rissa- nen, 1996]. This can be extended to (worst-case) transductive learning with contexts Z...... 27; in this case the minmax optimal regret for a fixed horizon achieved by the normalized max- imum likelihood (NML) probability assignment (Shta 1987], and can be expressed as (F) = maX2,.7 log (E, m II Py (3e Pr(uel=))) This expression has been eval- uated previously for online logistic regression [Jacquet et al., 2021] and more general hypothesis classes [Wu et al., 2022b]. is an intriguing question to understand what properties of F the stochastic complexity depends on, given that the above examples illustrates that covering numbers do not capture it. Our reduction provides a technique to use such fine-grained understanding of the regret to directly lift the bounds the more general smoothed adversary setting.
4 Oracie-Efficient Smoothed Sequential Probability Assignment
In the previous section, we consider a purely statistical perspective on the minimax value of the sequential probability assignment problem for smoothed adversaries. In this section, we will focus on an algorithmic perspective and design an algorithm that is efficiently implemented using calls to an MLE oracle. We will focus on the setting when the base measure the uniform measure on the input space X' and the label space y = {0, 1]. In this setting, we are given access to an oracle OPT which given data set S {z,, 31 )= outputs hypothesis that minimizes the loss S. That is,
m
OPT (S) = argmin heT
Σ (h, (zr,
In the context of the logarithmic loss, this corresponds to maximum likelihood estimation. Most of the analysis holds for a general loss function É (with regret scaling appropriate bounds on the values and derivatives), but for clarity one can think of é as the log-loss. In particular, Algorithm I is written for the log-loss.
The main framework we work in is the follow-the hite--erturbed-leadeeee (FTPL) framework. Here, our algorithm uses the oracle on data set consisting of the historical samples and a hallucinated samples. The hallucinated samples are intended to "stabilize" the predictions of the algorithm. This gives us probability assignment FTPLL [g FTPL (-/a1.t -1=-1)
In order to state the regret bound, we need the following notions. For any class F, define the truncated class F. as Fa { { [a() = 1+2a where f /EF}. We will also need the notion of
f(x)+a
Rademacher complexity Rad (F,T) supxcxix E, [sup $ EvEx t (r)
7

---

Algorithm 1: Probability assignment 2FTPL
Input: time horizon 7, smoothness parameter o, VC dimension d, Samples per step Parameter n, Truncation parameter
for / + to I"" do
Generate N(O Poi(n) fresh hallucinated samples (51 ", ( -
). which are i...d. conditioned on N with xf" ~ ((x) and ((t) ~ ((0,, 1}) Call the oracle to compute (1 (((4 OPT
(()) hEENo U {Ir, Ur brl(e(t-11)
Observe It
Assign probability o FTPL Uia V14-1) h.z20 Receive
1+20
end
Theorem 4.1 (Main Regret Bound). For any hypothesis class F and parameters n, o, we have that the regret of Algorithm for o-smoothed adversaries bounded as
Rr 2,,,,,22TPL & noo 2
+ aT + T log 1 1
Rad (//m + n2 n (111o) o)mh log (1/a) e e-/8 a
I
T inf men
m
We will instantiate this bound for case when the class F has bounded VC dimension. For such classes, it is known that the Rademacher complexity is bounded. We state this in the following corollary.
Corollary 4.1.1. Let FF be a hypothesis class such that the Rademacher complexity bounded as
Rad (F.. T) cT- then we have RT(F, 2UTPL S TTaw V
poly log
Id
Note that, in particular, for VC classes we have Rr (FVC, scales as T4/5, Improving this to achieve the minimax rate discussed in Corollary 3.4.1 is an interesting open question.
Remark. slightly improved regret scaling as 3 be achieved by assuming access to oracle that can optimize mixed objective function involving the log-loss and signed sum of the functions in class. However, these oracles do not have the natural interpretation in terms maximum likliehood estimation.
4.1 Analysis
The main challenge in designing algorithms in the follow-the- the distribution the hallucinated samples so as to balance the tradeoff between the "stability" of the algorithm i.e. how little the algorithm changes its prediction from time step to time step. and the "perturbation" ie. how much the addition of the hallucinated samples changes the prediction of the algorithm from the outputting the best hypothesis the historical samples. This captured by the following lemma.
follow-the-pertureed perturbed-leader framework is designing
Lemma 4.2 (Follow the Perturbed Leader bound). Let l be convex loss function, and let F be a hypothesis class. Let 'D denote the distribution of the adversary at time I and let Or denote the distribution of the hypothesis hy outpul by Algorithm 1. Then, we have that the regret of Algorithm I (where we use (I,, We) to denote a hallucinated data point) is bounded by
N
Σ
E 16(1, 8c] Br (ewe
B
E Best De+1
[[(be+1,8:)]
+E
sup bEF.
e(h, 3r) e(1",10)
taT.
i=1
Sunblity
Perturbation
where h argmin ΣT e(h, St).
With some abuse of notation, consider D, to be over X (0. 1).

---

We provide proof in Appendix E for completeness. Given this decomposition of the regret, we need to handle both terms carefully. Just appreciate the tradeoff, note that as we increase the number of hallucinated examples, the perturbation term generally increases, but the stability term generally decreases. First, let us focus on the stability term which is harder to deal with. The main approach we will use is a generalization of the decomposition of the stability term introduced in Haghtalab et al. [2022] even when the losses are unbounded, as is the case with the log-loss. The main idea is to decompose the stability term in terms of the distance between the distribution of the average prediction at the next time step and the distribution of the current time step, as captured by the x" distance and term that captures how different the predictions of the algorithm are when the sample is resampled from the same distribution. The proof can be found in Appendix F.
Lemma 4.3 X² + Generalization Stability). Let Qs denote learner's distribution over F in at round t, De be adversary's 's distribution at time (given the history $1," ,8--1), ) St ~ DD be the realized adversarial instance at time t, and sy be an independent copy s ~ Dr. Let R(t+1) refers to the randomness used by the algorithm in round + 1. Then,
E ( E [e(he st)]
E
[((b+2,
BenDD Re
1++1
x E 1Q.11) 2+) log (2) sOND,
$ V 2
E "1.S(~D(RRHL) [e(he+1, s() - E(he+1.
Given this lemma, move on bounding the x² divergence between the distribution of the average prediction at the next time step and the distribution of the current time step. This is done using the Ingster method to bound the divergence of mixtures. We include a proof in Appendix G for completeness.
Lemma 4.4 (Bound on x²). x2 (Es,-D, (Q 2x) S
2 dm
Next, we move on second term in Lemma 4.3. Note that this term involves the difference between the loss of the hypothesis output at time + 1 evaluated on two independent points 8; and s drawn from D. The main idea to bound the term is to use a stronger version of the coupling lemma Theorem 2.1 which allows us extract subsequences of points sampled according smooth distributions from iid samples from the base measure. This allows us to relate the required generalization bound to the Rademacher complexity of the class composed with the loss. Using the truncation and the contraction principle, we get the desired bound. The proof can be found in Appendix H.
Lemma 4.5 (Generalization). Let h441 denote the hypothesis output by the Algorithmm I time 1. Then, for any m S n, we have
[e(be41, (() 9t)] s RADD (Fa, n/m) + n (1 -0 log (1/a) + -n/8
E $1,5| (D.
a
m
The final term that we want bound the perturbation term. In order to bound this note that we set our truncation parameter such that the loss our the prediction made by our algorithm is bounded and consequently the perturbation term is bounded by n log ! see Appendix I. Theorem 4.1 follows by combining the above results.
5 Conclusions and Open Problems
In this paper, we initiated the study of sequential probability assignment with smoothed adversaries. We characterize the minimax regret in terms of the minimax regret for transductive learning and use this to provide tight regret bounds, c.g., for VC classes. Furthermore, we initiate the study of oracle efficiency in this setting and show that sublinear regret can be achieve for general classes.
Our work motivates several directions for future work. An interesting direction is whether the optimal Olog(T)) regret is achievable for some classes, such as VC classes, using oracle-efficient algorithms. More generally, are there computational barriers obtaining fast rates in prediction with log-loss in this setting?
'For the particular use in our analysis a simpler version of the lemma similar to Haghtalab et al. [2022] suffices but we prove general version since we believe such version is useful in providing improved regret bounds for the problem.

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Science Foundation under grant CCF-2145898, C3.AI Digital Transformation Institute grant, and Berkeley Al Research Commons grants. This work was partially done while authors were visitors the Simons Institute for the Theory of Computing.
References
Jorma Rissanen. universal data compression system. IEEE Transactions on information theory, 29 (5):556664, 1983.
Jorma Rissanen. Universal coding, information, prediction, and estimation. IEEE Transactions Information theory, 30(4):629-636, 1984.
Thomas M Cover. Universal portfolios. Mathematical finance, 1(1):1-29, 1991.
Meir Feder, Neri Merhav, and Michael Gutman. Universal prediction of individual sequences. IEEE Iransactions on Information Theory, 38(4))) 1992.
Qun Xie and Andrew R Barron. Minimax redundancy for the class of memoryless sources. IEEE Transactions on Information Theory, 4362):646-657, 1997.
Neri Merhav and Meir Feder. Universal prediction. IEEE Transactions on Information Theory, 44(6): 2124-2147, 1998.
Qun Xie and Andrew Barron. Asymptotic minimax regret for data compression, gambling, and prediction. IEEE Transactions Information Theory, 46(2):431-445, 2000.
Yuhong Yang and Andrew Barron. Information-theoreti determination of minimax rates of conver- gence. Annals of Statistics, pages 1564-1599, 1999.
Jiantao Jiao, Haim H Permuter, Lei Zhao, Young- Han Kim, and Tsachy Weissman. Universal estimation of directed information. IEEE Transactions on Information Theory, 59(10):620-6242. 2013.
Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, 29, 2016.
Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. Conference On Learning Theory, pages 167-208. PMLR, 2018.
Alexander Rakhlin and Karthik Sridharan. Sequential probability assignment with binary alphabets and large classes of experts. arXiv preprint arXiv: 2015.
Yaniv Fogel and Meir Feder. On the problem of on-line learning with log-loss. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1995-2999 IEEE, 2017.
Yaniv Fogel and Meir Feder. Universal batch learning with log-loss. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 21-25, IEEE, 2018.
Alankrita Bhatt and Young-Han Kim. Sequential prediction under log-loss with side information. In Algorithmic Learning Theory, pages 340.344. PMLR, 2021.
Blair Bilodeau, Dylan Foster, and Daniel M Roy. Minimax rates for conditional density estimation via empirical entropy. arXiv preprint arXiv:2 109. 10461, 2021.
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Expected worst regret via stochastic sequential covering. arXiv preprint arXiv:2209.04441,, 2022a.
Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction,
allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34: 18907-18919, 2021.
10

---

Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021a.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285-318, 1988.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver- saries. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 942-953. IEEE, 2021.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. In Advances in neural information processing systems, pages 1764- 1772, 2011.
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. Advances in Neural Information Processing Systems, 2022.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. Conference on Learning Theory, pages 1716-1786. PMLR, 2022.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904-1933 2022.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles, In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
John Langford, Lihong Li, and Alexander Strehl. Vowpal wabbit open source project. 2007.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. gestace-deepndens complexity of contextual bandits and reinforcement learning: A disagreement-basse perspective. 2021b.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):91-307, 2005.
Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkamis, and Jen- nifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 6755) 2020.
Guanghui Wang, Zihao Hu, Vidya Muthukumar, and Jacob Abernethy. Adaptive oracle-efficient online learning. Advances in Neural Information Processing Systems, 2022.
Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pages 546-555, 2007.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differ- entially private learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, Aditors.Advancer. Advances in Neural Information Processing Systems, volume 33, pages 9203-9215. Curran Associates, Inc., 2020.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1-2):111--) 2015a.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexi- ties. J. Mach. Learn. Res., 16(1):155-18))) 2015b.

---

Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Precise regret bounds for log-loss via a truncated bayesian algorithm. Advances Neural Information Processing Systems, 2022b.
Mark Rudelson and Roman Vershynin. Combinatories of random processes and sections of convex bodies. Annals of Mathematics, pages 603-648, 2006.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018.
Khadija Musayeva. Sample complexity result for multi-category classifiers of bounded variation. arXiv preprint arXiv22033.09776, 2020.
Peter I. Bartlett, Sanjeev R Kulkarni, and S Eli Posner, Covering numbers for real-valued function classes. IEEE transactions information theory, 43(5):1721-1724, 1997.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances in Neural Information Processing Systems, 23, 2010.
Changlong Wu, Ananth Grama, and Wojeiech Szpankowski. Online learning dynamically changing environments. arXiv preprint arXiv:2302.00/033 2023.
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.
Jorma J Rissanen. Fisher information and stochastic complexity. IEEE transactions information theory, 42(1):40-47, 1996.
Yurii Mikhailovich Shtar' kov. Universal sequential coding of single messages. Problemy Peredachi Informatsi, -3 1987.
Philippe Jacquet, Gil Shamir, and Wojeiech Szpankowski. Precise minimax regret for logistic regression with categorical feature values. In Algorithmic Learning Theory, pages 755-771. PMLR, 2021.
Raphail Krichevsky and Victor Trofimov. The performance of universal encoding. IEEE Transactions on Information Theory, 27(2):199-20) 207, 1981.
Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. On learning distributions from their samples. Conference on Learning Theory, pages 1066-1100, PMLR, 2015.
Daniel A Spielman and Shang-Hur Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385 463, 2004.
Adam Block and Max Simchowitz. Efficient and near-optimal smoothed online learning for general- ized linear functions. Advances in neural information processing systems, 2022.
Adam Tauman Kalai and Santosh Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research, pages 423-440, 2002.
Haipeng Luo, Chen-Ye Yu Wei, and Kai Zheng. Efficient online portfolio with logarithmic regret. Advances in neural information processing systems, 31, 2018
Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the efficiency- regret pareto frontier for online learning of portfolios and quantum states. In Conference on Learning Theory, pages 182-226. PMIR, 2022.
Rémi Jézéquel, Dmitrii M Ostrovskii, and Pierre Gaillard. Efficient and near-optimal online portfolio selection. arXiv preprint arXiv:2209. 2022.
12

---

Tim Van Erven, Dirk Van der Hoeven, Wojciech Kotlowski, and Wouter M Koolen. Open problem: Fast and optimal online portfolio selection. In Conference on Learning Theory, pages 3864-3869. PMLR, 2020.
Thomas M Cover and Erik Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory, 42(2):348-33) 363, 1996.
Jason E Cross and Andrew R Barron. Efficient universal portfolios for past-dependent target classes. Mathematical Finance: An International Journal of Mathematics, Statistics and Financial Economics, 13(2):245-276, 2003.
László Györfi, Gábor Lugosi, and Frederic Udina. Nonparametric kernel-based sequential investment strategies. Mathematical Finance: An International Journal of Mathematics, Statistics and Financial Economics, 16(2):337-357, 2006.
Alankrita Bhatt, Jon Ryu, and Young-Har Han Kim. On universal portfolios with continuous side information. In International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
13

---

A Related work
Sequential probability assignment is classic topic in information theory with extensive literature, see the survey by Merhav and Feder [1998] and the references within. In particular, the idea of probability assignments that are Bayesian mixtures over the reference class of distributions [Krichevsky and Trofimov, 1981] is of central importance- -uch mixture probability assignments arise as the optimal solution to several operational information theoretic and statistical problems [Kamath et al., 2015]. It is also known that the Bayesian mixture approach often outperforms the "plug-in" approach of estimating a predictor from the reference class and then playing it [Merhav and Feder, 1998]. A similar Bayesian mixture probability assignment in the contextual probability assignment problem was used by Bhatt and Kim [2021]. where the covering over the VC function class was obtained in data- deteddeenddntt manner. This idea of using a mixture over an empirical covering along with a so-called "aad-33" probability assignment was then used by Bilodeau et al. [2021]. Combining this with the key idea of discretizing the class of functions as per the Hellinger divergence induced metric, they obtained matching rates for several interesting classes in the realizable case (i.e. y/ 24 generated according to a fixed unknown distribution in the reference class); see also Yang and Barron [1999] for more intuition behind usage of Hellinger coverings for stochastic data. Recent work of Wu et al. [2022a,b] has also employed an empirical covering with an add-3 probability assignment for both stochastic and adversarial adversaries.
A complementary approach, more common in the online learning literature is to study fundamental limits of sequential decision making problems non-constructively (i.e. providing bounds on the minmax regret without providing probability assignment that achieves said regret). This sequen- tial complexities based approach of Rakhlin et al. [2015b,a] has been employed for the log-loss by Rakhlin and Sridharan [2015] and Bilodeau et al. [2020]; however the latter suggests that sequential complexities might not fully capture the log-loss problem.
Smoothed analysis, initiated by Spielman and Teng [2004] for the study of efficiency of algorithms such as the simplex method, has recently shown to be effective in circumventing both statistical and computatonal lower bounds in online learning for classification and regression Haghtalab et al. [2021], Rakhlin et al. [2011], Block et al. [2022], Haghtalab et al. [2020]. Block and Simchowitz [2022]. This line of work establishes that smoothed analysis is viable line of attack to construct statistically and computationally efficient algorithms for sequential decision making problems and has developed tools such as the coupling lemma to understand smoothed sequential decision decision-making. But handling the unbounded and non-Lipschitz log-loss and MLE oracle the main conceptual novelty introduced in this work.
Due to the fundamental nature of the problem, the notion of computational efficiency for sequential probability assignment and the closely related problem of portfolio selection has been considered in the literature. Kalai and Vempala [2002] presents an efficient implementation of Cover's universal portfolio algorithm using techniques from Markov chain Monte Carlo. Recently, there has been a flurry of interest in using follow the regularized leader (FTRL) type techniques to achieve low regret and low complexity simultaneously [Luo et al., 2018, Zimmert et al., 2022, Jézéquel et al., 2022], see also Van Erven et al. [2020] and the references within. However, none of these methods consider the contextual version of the problem and are considerably different from the oracle-efficiee approach. On the other hand, work studying portfolio selection with contexts [Cover and Ordentlich, 1996, Cross and Barron, 2003, Györfi et al., 2006, Bhatt et al., 2023] does not take oracle-effiieency into account.
Concurrent Work: Wu et al. [2023] also study the problem of sequential probability assignment (and general mixable losses) and for VC classes achieve the optimal regret of Od /o). In addition to the smooth adversaries, they also studied general models capturing the setting where the base measures are not known. They work primarily in the information theoretical setting and do not present any results regarding efficient algorithms. A major contribution of our work is the study of oracle-efficient online learning for the log-loss, which has not been considered by Wu et al. [2023] Indeed, to the best of knowledge, oracle efficiency has not been considered at all for losses such as the log loss even for worst-case settings. Considering oracle-efficiency for log-loss an important and natural line of research as the ERM oracle corresponds to the maximum likelihood estimator (MLE) that is commonly used in practice. Our paper presents sublinear regret oracle efficient algorithms for the log loss (which does not have analog in Wu et al. [2023]).
14

---

B Deferred Proof from Section 3
In order obtain upper bound on (F o) in terms of KT (F) for some k. we will consider (2) and proceed inductively. The main idea is to note that since D2 is a-smoothed, conditioned on the history thus far, can invoke the coupling lemma given in Theorem 2.1.
For the sake of illustration, first consider the simple case of T 1. Let X1, Zi... Zg denote the coupling alluded to in Theorem 2.1. Recall that Xi D1 and Zi ~ n². Defining the event Ei = (X1 E Zi:h.. we have
R1 (F,, Φ) = Ex inf sup (F, 31, a1)
91
inf sup R1 (F, X1, y1, 0n)
@1
1{ } inf sup R1 (F, X1. v1,
Ziik
+ Zua
1 inf sup (F X1,
< Zxi
1 [[Fi] inf sup R1 (F,, X1 v1, a1) 21
+ +P(EF)
(3)
< Bz
max sup RS (F, X1 81, 01) XiE
X1,
+ (11
(4)
y1
= R (F)
(5)
where (3) uses that infa, sup,, R₂ (1 X1, V1. an) S 14, (4) follows by the coupling lemma and (5) follows from the definition of transductive learning regret. The next step is to generalize this to arbitrary T. The key aspect that makes this possible is that for all t S T, have D, A, (μ). even conditioned on the past, allowing us to apply the coupling lemma. Furthermore, we need that RT < T for arbitrary sequences which indeed guaranteed for reasonable losses such the log-loss as noted above.
We now move to general case. We will prove this inductively. Assume that we have used the coupling lemma till time - and replaced the samples from the smooth distributions with samples from the uniform. That is assume the induction hypothesis, for time t as RI S
E max inf sup... sup inf sup...... ( 01 21
X.~D, a: St
... E inf sup R(F, X1.1, VI.r, a1r) + T(t - 1)( o)* Dr Xr~Dr aT yr
Using the coupling lemma, we have that there exists coupling II, such that X,, Zt,1... Zt, ~ II, and an event E, = {xx E Z,,r }
that occurs with probability - (1 - -)) a)*h Using
Z, = [Z...... } we have
E max inf sup....uuu sup Zi X1E21 a 91 D.
E inf sup.. sup E sup R(F, XI.T MI.T (1:7) X. in Dr Xr or yr
< E max inf sup sup Zi XIEZi in
inf sup... sup E D. X. Ze B Dr Xy gr
E
inp R(F, X B1r,,
]
max inf sup sup Zinuat XiEZi 0n
E
E D. X,
1 I[E.] ae y
inf sup
sup E sup R(F X MIT, X Dr Dr or
+
max inf sup... ... sup Ziopk X,EZ,
E
E D. XII
1 [E
inf sup M1
sup E inf sup R(F, X1 Bver (1r,))r)) Dr Xr ar gr
'This holds for the loss by using the trivial strategy of using a uniform probability assignment at each step.
15

---

E max inf sup sup E D. Xelemlll
1 [Br]]
inf sup ... sup at
sup R(F, X XIx,, BI:T, XIsT, (1r))
2, Zinuh XIEZi #1
yt
Dy Dr or
+ +
- (1
S max inf sup........ sup max
inp
.uspp..uupp
sup
E inf sup R(F, Xi., Virr, 01:)) Dr Xr ar
Zinuk XIEZ1 21
D. br11l, X.Eli
de
vr
T 0)
E max Zi X1EZ1 as Zenpt XieZi
E max inf sup...
inf sup ... sup E inf sup sup R(F, XIr, (1:)) de
Dr Xr or
+ (1 -
Combining with the induction hypothesis, gives us the induction hypothesis for the next t required. The desired result follows by upper bounding the average with the supremum over all subsets of size KT.
C Proof of Theorem 3.2
First, recall the notion of the global sequential covering for a class Wu et al. [2022b].
Definition C.1 (Global Sequential Covering Wu et al. [2022b]). For any class F, we say that F. C X + [0, 1] is global sequential a-covering of F at scale T if for any sequence Fu. and he F, there is h F such that for all i,
hh(x)) h'(11s)l Sa.
Theorem C.1 (Wu al. [2022b]). F is a global sequential a-covering of F scale then
Rr (F) < inf 22T + log] Fog]F%]]
as0
To finish the proof note that e-cover in the sense of Definition 3.1 gives global sequential cover in sense Definition C.I.
D VC Classes
In this section, we construct probability assignment for the case when F C {X' + [0. 1]} is VC class. To motivate this probability assigmment, consider the no-context case, which a classic problem in information theory, where the (asymptotically) optimal probability assignment is known be the Krichevsky and Trofimov [1981] (KT) probability assignment which is Bayesian mixture of the form
S (e()):))w(0)d0
qKT (VI.T)
for particular prior wf). This be written sequentially qer (1/11=111) 1
leading
1-1+1
sometimes being called the add- 1/2 probability assignment; by choosing w(O) be Beta 3) prior one can achieve corresponding add-ß probability assignment. We extend the mixture idea to the contextual case. In particular, for functions f1,... fi...., m E one can choose mixture probability assignment as
Ps. (Milzz) +
II [9 11:-1) 9o 1111:) imi
EI
1+ 23
'Note that once mixture d(yu. [mι)) has been defined for arbitrary Iist Fia the probability assign-
ment time t (or equivalently, the predicted probability with which the upcoming bit is 1) can be defined givia l[lrat) in particular, this prediction depends only the observed history g(1 (11/ V1--1) o(vi:t-1 a = Wist, Mitt-1 and not the future yt.
16

---

This is the approach employed presently with carefully chosen fi..... fm- We remark that for VC classes this mixture approach may be extended to any mixable [Cesa- Bass-Biancci and Lugosi, 2006, Chapter 3] loss.
First consider VC classes A S X, where A E A C 2x with the VC dimension of the collection A being d < 3o; as well as lwo numbers do 01 [0, 1]. Then, have
carefully: i.e. each f E FVC is characterized by three things:
fA,0.,, 0, (z)
A} 011 A
The following equivalent representation of this hypothesis class is more convenient to use. We consider each f to be characterized by tuple f = (g, 0g 01) where
1. 0o, 01 [0, 1]
2. g E 9 c {X + {0,
In other words. belongs to a class G of binary functions- this is simply the class of functions {a 1 A} A A} in the original notation; that clearly VCdim(G) d. Then, have Pf(-1x) = Pg.0o.0 0, (-1z) = Bernoulli(oo) if ( = O: and Ps. (-12r) = Bernoulli(e1) otherwise. (g, 0o 01) for a sequential probability
Recalling the definition of regret against a particular assignment strategy 2 (11l
T
T
Rr 2)
Σ log q I1 v1a-1)
log p
(6)
log p (urrlan
(32: ((rr))
where ((v:7||<117) == II (Vv (11, 11
In the smoothed analysis case, have X, Dr where D, for all / is o-smoothed. Recall that in this case, we are concerned with the regret
Ps (1.r)
Rr(F,o,
max
ExpT
max sup Mir fer U(viTT|X1:1)
a sanoobee
0g.00.01 (31.1) (1:)
max P:o-smoothed
Exir
max sup max yor geß 0..0,
D.1 Proposed probability assignment
Let μ be the dominating measure for the a-smoothed distribution of XI.T. Let gr..... 1m. E g be an c-cover of the function class G under the metric (11(1 92) = Prx~ * 9x())). The following lemma bounds m.-
Lemma D.1 (Covering number of VC classes under the metric 6, Vershynin [2018]).
m. (
for an absolute constant
Following the idea of using a mixture probability assignment, we take a uniform mixture over .1..... Im. Imm
and 0g 0, so that
1
1 m.
[=1 2/- Po..o.., (11=
m.
and consequently the sequential probability assignment (or equivalently, the probability assigned to
is
q(1/r12 11--1) = ((11=~1||===)
One can observe that g(0 11= (1=-,) ((1 [rra,, 11- so that legitimate probability assignment. Let the strategy induced by this uniform mixture be called vC
0 and g(0 v
17

---

D.2 Analysis of 2VC for smoothed adversaries
We note from (6) that for the 2VC as defined in the last section, have
Py M7 (V1.r F1.r)
2r((",00 f,,, FIT VI VC) = log me + log
D ===1 So So Po. 0r (herlaarr))000ddd
Po .95 or (11.T (1:T)
I log me + log
So So Ps.- 0o.0; (urr/e1rr)dt d00,00
where gs E {gi.... ,.. 9m. is the function i* E [m] that minimizes the Hamming distance between the binary strings (g-- (z1),... 9:- (FT)) and (9" (r (xrr))
We now take closer look the second term of (7). Firstly, note that for any (g. fg 01) have 00 (MIT)(11e))
09.00.0 (ye xx) = II s(xe) (1 (o(oo)) 1-
II
0g 00)
0 (1 02) 1-
(=)(=))=
(=g(w))=1
(1 0,) 0000
8t ( (1 ,1 1
where for E 1)
k |[t: yt 1, g 531 no(g; = |||: g(ar) = j}}
Next, we note that for any E
L. L 0s.00.0 0, (y1-T Fir 11.r) dd0gd0;
%.- 00 (o (1 00)
(o - d0o
Jo ol (1 02) te d01
(8)
(a(gari)) (ol (n + 1)
n² no(g Kalg: ) (e na (gtaee))
(g
where (8) follows from properties of the Laplace probability assignment (or that of the Beta/Gamma functions), captured by Lemma D.2. Lemma D.2. For ls S n E, N,
S. (1- T(k: + 1)T(n - -k
+ 2)
(n + 1)
where I'(-) represents the Gamma function.
Putting this back into (7) (and rearranging), we have
Rr(lg" "alll",,00 06 07), FI., Vver, , VC) - llog m. 2
ny (1((0)141)))
Σ log
(arl:::arrr..: (07) (500 ( (n 00' (n))) (0 (o sonr
JE(0.1)
ny (g (11))
ny(9") (11)
= Σ log
(0 Fee. (
)
JE(0.1)
18

---

ny(0"
(077) ( -0 (or))///omm/rr/_ar)))) (m
(1
(( (y(o: (1 (
nyl0" ny(o" (g a1.r,y :
Σ log
jE(0.1)
where (9) follows since for any natural numbers k S and 0 [0, 1] we have (1) 11-0011-0000 0))- 1. Now, note that
n!. nz!
k!!
(n' K')
log
log
+ log
+ log
k!
(n k)!
(n' + In - n'
(k + 1k: WD)!
((n - k) + In - n + 1k: K'D)
S log
+ log
log
n'!
k!
(n k))
I: fak--ka In I 8, and max(n, S then by for example [Bhatt and Kim, 2021, Proposition
6] we have that
log S 28 log(n' + 26) + 26 log(k: + 26) + 40 log((n k) + 46)
166 16olog N.
(10)
We now wish to use this bound (9). For this, we will recall the definitions (g; Fir)) (1r)) and ku(g; #1.7, 31.r) for particular function and observe that for functions g.g have that both (o(g::1::) - nolg': æ1rr). ko Ji.r, 91:r) ho Fi-r, yirr) S (g(rer))) ). g (x1:)) where de(::)) denotes the Hamming distance and ( == (g(z)),.... (......99(777) (xT)) E (0, 1) Thus, by using (10) in (9) with du (g (II:T) (),T)), N = =,, we get
Rgg(g" , 0), TIT VIT, 2C & logm, m. + log T + 32d (g" (IIT), (urr),e 9:- (IITT) log (11)
Note that (11) has effectively removed any dependence on y, 6 07- We then have for some absolute constant C, (recalling the definition i* and from earlier)
(T 2) & C'log m. + Clog T
max 2.0 -smoohhd
E
sup min du d 9 66 iE(m.]
(12)
Finally, control the last term in (12) by the following result, which follows from the coupling lemma and variance sensitive upper bounds on suprema over VC classes. Lemma D.3 (Lemma 3.3 of Haghtalab al. [2021]).
E
sup min dgr (Xir), ( (I
e Tlog Td
(
T log T
ge eg iE(m)
Plugging the above into (12) and taking = gives us
o, so dlog (1))
E
Proof of Lemma 4.2
Proof. Note that this proof holds for general loss functions. Let Ry denote the regret.
T
T
Rr < E
E(he,
9t)
inf
Σ
E(h,
st)
heF 1=1
T
T E(he, st) Σ E(het1
T Σ
T' e(h, st)
E
Σ
8t) +
((1411)))
inf KEF i=1
Σ
1=1
19

---

E
elbss 8t)
Σ 80
+ IE
Σ
E(he+1, 81)
inf NEF
e(h, 8t)
Let us focus on the second term.
T E
(h(+11
inf NEF
st)
< E
Σ ((18+1881)
inf heTa
Σ (1)
+ inf
Σ
((),
inf hEy
Σ
e(h, s1)
befa
$ 2aT +
((1441, St)
inf NEJa
e(h, st))
(13)
20T
Σ E(b,, 8z) -((rr,
(14)
$ 2oT +
sup hEF. 1=1
e(h, 86) - - -hh" (t)
where 10* ===-innez Σ' E(h, 8:) (13) follows by comparing the optimal of the truncated class with the whole class, see Bianchi and Lugosi, 2006, Lemma 9.5]. (14) follows from the Be-the-leader lemma Cesa- Bianchi and Lugosi [2006].
F Proof of Lemma 4.3
Denote by R (Nv(), (5e]venc)) the fresh randomness generated at the beginning of time t, which independent of {sy}rce generated by the adversary. Let Q the distribution of the leamer''s action h4 E H in Algorithm 1, Formally,
1)
((x)=
Σ
91 (11)
1 (1+1) = =x)+ + Σ yr 1(x, = x).
Let pt be the distribution of rd The reason why we introduce this notion is that he in Algorithm only depends on the vector p
The main step in the proof is to introduce independent sample from the distribution D, in order to decouple the dependence of the distribution 2.+1 on the test point St-
E
E
[e( st)
E
E
[6(he41,
R,-D,
he Q.
si-D, b 1111
E e
E
[e( 3()]
E
E
[e(he+1.
hem@.
het1
E
E
(((he+1,8))
E
E
[((he+1,
(15)
1
SeWD, 1
E
1e [1)]
E AAND,
E
(((het1,5))]
(16)
DD h.
E
[e(he+1, s())
[((he41, st)]
W, 1
BrwDD he-1
where we get (15) by adding and subtracting the middle term corresponding to evaluating the loss on an independent sample s and (16) by observing that 8; and 8f are equally distributed. Since the second term is the same in the required equation, we can focus the first term.
E
[E(he, ([)
E
[6(he41, s111
(17)
by D
26 D.D
hest 1.+1
D.
20

---

Here we use the notation 24+1 BR,,D [Q++1] for the mixture distribution. In order to bound this, we look a variational interpretation of the x" distance between two distributions and Q.
Lemma F.1 Hhammensley-Chappan--- -happaaa-apaabbiinn bound). For any pair of measures P and Q and any measurable function X + R, we have
Ex [x~p(x(X)] Ex &
X2 (P.Q) Varx~Q (x
v | v) (P.Q) Ex,x'mQ (x))-(xx)))
Applying this to (17), we get
E Q
E AD
[e(her s/)]
E
[e(he+2, s{)]
R
Q111
sinDD
$ 2
E (Qi-1). Qi) EB..M- (BEIND, [e(he s1) E(h/ [t)] aanDD
as required. As noted before, for the particular use in our analysis simpler version of the lemma similar to Haghtalab et al. [2022] suffices but we include the general version since we believe such a version is useful in providing improved regret bounds for the problem.
G Upper Bounding x2 Distance: Proof of Lemma 4.4
In this section, we will focus on bounding the x² distance between the distribution of actions at time steps. The reasoning in this section closely follows Haghtalab et al. [2022]. We reproduce it here for completeness.
We assume that X' is discrete. Define
N
N
no(x)= 10; = 0) and n1(x)
Σ 1 1 =I 1).
As each T; is uniformly distributed on X and ãJ ~ u({0, 1J), by the subsampling property of the Poisson distribution, the 2| random variables (no(z), n (1(x) are i.i.d. distributed as Poi(n/2|A1))
Since the historic data is only translation, it suffices to consider the distributions time 0 and t == 1. Let nz(x)) = no(x) + 1(x1 = xr = 0) with n definied similarly. Let P and Q be the probability distributions of (2)) nı (x=) and (x)) (x)))=xx respectively. Note that the output of the oracle depends only on this vector and thus by the data processing inequality it suffices bound x (P, Q).
Note that the distribution P is product Poisson distribution:
(((no(z),m1z))) = II II xEX yE(0,1}
P(Poi(n/2) = (z))
As for the distribution Q, it could be obtained from P in the following way: the smooth adversary draws x² ~ DD independent of (mo(x), nı (x())) (x)] ~ P, for some a-smooth distribution E A, (2)). He then chooses label y y(x*) E (0, 1) function of a= and sets
1 (x"=) ")(==)( 1, and n ny (x), V(z, v) (x", ((()))))).
Consequently, given o-smooth distribution D and labeling function y X {0, used by the adversary, the distribution Q is a mixture distribution Q = Ex x [Q with
Qu (()b((())) P((ooi(n/2)22 ")y(wr) (x*) 1)
II
P(Poi(n/2) ny (x)).)
(#.))((** wv**))
We will use the Ingster method control the x2 between the mixture distribution Q and the base distribution P.
21

---

Lemma G.1 (Ingster's x2 method). For mixture distribution Eg [Qol and generic distribution P. the following identity holds:
[0(2))
)
x²
Qol.
E
E
- 1,
0,8%Na
P(z)²
where 0' an independent copy of 0.
Let vi. be arbitrary pair of instance. Using the closed-form expressions of distributions P and
Que, holds that
Quy
2/ 21((m)()))(11)) 2| (n (y (x2)
p2
n
Using the fact that (no(z), n2 (x)) are i..d distributed as (2)())2( under P, we have
Qa: (1nb(<)) mt (M)))
= =1+ 2| [ = x.2)
E
(x)))
P((no(r), (z)))²
We will use the fact that the probability of collision between two independent draws 15. D is small. That is using the Lemma G.I, we have
X x)
22 P.E..DDO Deo
X
V
E
[(x]
= =2²)
2
2
n
X
Σ
D(x)25
X
D(x)
1
x
V
yan
DEA
FEX
where the last inequality follows from the definition of a a-smooth distribution.
H Upper Bounding Generalization Error: Proof of Lemma 4.5
The proof of the theorem is similar the [Haghtalab et al., 2022, Section 4.2.2). In our setting, need to deal with general losses. We shall need the following property of smooth distributions which slightly strengthened version of the coupling lemma in Theorem 2.1 shown Haghtalab al. [2022].
Lemma H.1. Let XI,.... ".....",,,,,,
X ~ Q and be another distribution with a bounded likelihood ratio: dP/dQ 1/o. Then using external randonness R, there exists index I I(X1, .mm R) [m] and a success event E'.,.... .Xms R) such that Pr[E9] S - orm, and
(X, E, x,) ~ P.
Fix any realization the Poissonized sample size Poi(n). Choose m in Lemma H.I. Since for any o-smooth D., it holds that
D,(s)
D1(2) Dely x)
S
u(X x t0, 1)){))()) ((x)(x) U({0, 13)(z)
the premise of Lemma H. holds with parameter a //2 for P P Dr, u(X {0, 13). Consequently. dividing the self- eeffrgenerated samples .,.... .5 into N/m groups each of size m, and running the procedure in Lemma H.1, we arrive N/m independent events F EN/m= each with probability T Moreover, conditioned each Ej, can pick element
least (1 - 0 2)
Ug E { 11m++1)
fim such that
(u,) Ej, (30-1m+11.- ... ,,m ~ D..
For notational simplicity denote the set of unpicked samples (11j-1)m+1"" 3 Mu, by uy As result, thanks to the mutual independence of different groups and s, D, conditioned on $14-1 (note that we draw fresh randomness at every round), for E' 2 DjelN/mi Es we have
(u ....... UN/m; 8t) (E, $14-1, V1, .N/m)) ~ Dr-
22

---

Let us denote h++1 O1+1 81 the output of the algorithm at time when $1.-.. NN denotes the hallucinated data points and $1=-1. 8, denotes the observed data points. We will use the fact that Oc+1 is permutation invariant function. Consequently, for each j E [N/m] we have
[e(he+1, st) |
E
[5(0 ,3,, St), E]
NN
(000+1 ,N/m: st), 1 E, (1t-1.1
E
0,81--1
E
[(00+1(010011100 u1, ,, ' uN uN/mm Uz) u,) EX 1((8))-1
0,61. i
E MM/m
(1 ; E, 814-1,
(19)
-
B
((h441:2))) Fz.
where (18) follows from the conditional iid (and thus exchangeable) property (ui,-.. uN/m= 8t) after the conditioning, and (19) is due to the invariance of the O.+1 after any permutation of the inputs. On the other hand, if s/ ul, :. 2'x//m are independent copies st ~ Dr, by independence
is clear that
E D. [ at) El D.s(~ [e [E]
Vj E [N/m].
Consequently, using the shorthand un = 8t, u1g = 8/ we have
E
E(he+1, sc) E]
81 Ric
Ric
N/m
E
Σ 1=0
(E(hu+1, v/y) E(he41. E
N/m + S ni++)
N/m
E
sup heFa j=0
Σ
(E(h, u() - uz))
N/m +
u0.
M4/ Mor
N/m"
Dr
N/m sup Σ egh(u,)
2a
E
N/m + ug. MN D, Enmm
hEFa
j=0
1
Rad (Fa;N/m).
a
The last inequality uses the fact that the algorithm always outputs a function in Fa. Further, we have used the Ledoux- Ledoux-Talagrand contraction inequality. Theorem H.2 Ledoux-Talagree function class F. denote by g F the compositions function in F with g. Then, for all
Contraction). Let g R - R. be T.-Lipschitz function. For
Rad (g F, n) < L Rad (F,n). .)).
Last inequality follows from the fact that the derivative of the log loss is bounded by 1/a when truncated at level a. Note that the union bound gives
N/m
N 0)T Σ Pr[E
Pr[E S
S
m
1=1
Thus,the law of total expectation gives
E
(((he+1,8)) e(he41, 8c)
23

---

E
[e(he+1, st)) {(1++1, st) E] + Pr[E*] log(1/a)
Rad (Fa, N/m) + N (1 6m" log (1/a)
a
The last equation follows from the fact that the output of the algorithm has loss always bounded by log (1/a).
We get the desired result by taking the expectation of N ~ Poi(n), and using Pr(N > n/2] 2
1 - e n/8 in the above inequality completes the proof.
Bound on the Perturbation Term
Lemma I.1 (Perturbation).
E
Σ
L(h, I(h", 82) S 1ogg
Proof. Note from the truncation step in Algorithm 1, we have that L(h, 3,) S (a). We get the desired bound by taking expectations.
24


Reviews:
[{"review_id": "hlEhmV5TCD", "reviewer": "Reviewer_w3DK", "summary": "This paper studies the problem of sequential probability assignment in the smoothed setting. In particular, a learner receives labelled examples sequentially, where the contexts are drawn from some smooth distribution which can otherwise be chosen adversarially (in each step) and the labels can be chosen adversarially. The goal of the learner is to minimize the regret (minimax rate of excess error with respect to the optimum hypothesis on the subsequence seen so far). \n\nThe first main result provided is that the optimum regret for the problem is characterized by the optimum regret of a different problem where the adversary chooses a priori the set of contexts that they will have to choose from throughout the interaction with the learner. Using the demonstrated relationship between the two problems, the authors provide an upper bound on the regret in the smoothed setting, which involves the scale sensitive VC-dimension of the hypothesis class and a number of free parameters that can be chosen accordingly to adapt the bound to different regimes for the VC-dimension. For VC-classes the provided adapted bound is essentially tight.\n\nThe second main result provided is an oracle-efficient algorithm achieving sublinear regret on VC-classes (and more generally on classes with polynomially decaying Rademacher complexity), provided access to an ERM oracle for the hypothesis class considered. The algorithm follows the approach of Follow-the-Perturbed-Leader, which takes advantage of the trade-off between the stability of the algorithm's intermediate states and the excess error due to perturbing the current set of samples (by adding a number of hallucinated uniformly random data points). ", "questions": "My main questions are related to the two main points raised in the weaknesses section. Given the concreteness of the provided results, I would be happy to increase my score if the issues I pointed to are sufficiently addressed by the authors' answer.\n\n1. Are there some simple function classes for which the ERM oracle can be efficiently implemented under the marginal assumptions that correspond to the considered setting? Alternatively, is there a(n empirical, conceptual or theoretical) reason for which one might expect to heuristically obtain an approximate ERM oracle?\n\n2. What are the main technical hurdles arising when one tries to instantiate prior techniques in the considered setting? In which ways does the technical work differ from prior work?\n\nI have also found a small number of typos:\n- line 294: likliehood $\\to$ likelihood\n- lines 306-307: i=1 $\\to$ t=1 (3 times, one for each summation)\n- line 318: at in $\\to$ in\n- line 321: refers $\\to$ refer\n- line 344: achieve $\\to$ achieved", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper demonstrates that the smoothed analysis framework is relevant to providing provable guarantees for the problem of sequential probability assignment, hence initiating (and motivating) the (further) study of the problem through the lens of smoothed analysis. The results provided include essentially tight bounds on the (smoothed) regret for VC-classes and two main conceptual contributions: First, characterizing the minimax regret for the problem considered in terms of the minimax regret of another relevant problem (rather than some combinatorial notion of dimension, which might even be hopeless in general). Second, repurposing ERM as an oracle to be exploited by algorithms with sublinear regret.\n\nOverall, the results are presented with clarity and sufficient detail, and provide bounds for the considered problem that are fairly general and adaptable to hypothesis classes with different properties.", "weaknesses": "The first weakness of the paper is that the oracle-efficient algorithm proposed is not necessarily efficient, due to the potentially high complexity of the ERM oracle, especially since the labels are chosen adversarially. In other words, it is not clear whether assuming oracle access to an ERM is reasonable. A discussion on existing or simple positive results regarding the oracle's implementation or even a pointer to empirical results that demonstrate its success on a relevant setting would be appreciated.\n\nFurthermore, many of the technical contributions of the paper are not discussed in the main text. For example, the only hint provided for the proof of Theorem 3.1 in the main text is that it uses Theorem 2.1. In particular, it is not clear what (if any) technical obstacles arise when one tries to apply Thm 2.1 to this setting, or if adapting some approach from prior work is sufficient. Similarly, a proof sketch for Theorem 3.2 would be helpful for the reader.\n\nOverall, while the problem considered is well-motivated and the results are concrete, it is not clear whether there are strong conceptual and technical contributions relatively to prior work (smoothed analysis has already been applied to online learning and most of the tools used to demonstrate the results existed in the literature, at least in some less general form -- e.g., Theorem 2.1 and the idea of decomposing the stability term in Haghtalab et al. [2022]).\n\n-- Most of my main concerns where addressed in the rebuttal and for this reason I increased my score from 6 to 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thoughtful review. We will incorporate the suggested typographical and expository corrections.  \n\n**Applicability of oracle-efficiency**: The oracle-efficient framework is important because it allows us to directly tap into existing deployed algorithms, without having to design and implement an algorithm from scratch. These sub-routine algorithms can be heuristics and do not have to be provably efficient. Modern computer science is full of such heuristics that perform exceedingly well in practice even when hardness barriers exist in theory; a great example of this is deep learning. The oracle-efficient method for designing online algorithms has been extremely popular recently and has seen a lot of use in varied contexts such as contextual bandits and reinforcement learning (see https://vowpalwabbit.org/) and is even used in production. We see our work as following this line of work to design online algorithms. In particular, our paper elucidates the relative complexity of maximum likelihood estimation and sequential conditional density estimation. \n\nNote that the oracle in our algorithm is called on either “smoothed” instances given by the adversary, or random instances sampled from the uniform distribution. In such settings,  hardness results usually do not hold since they are proven mostly for worst case instances. Therefore, when implementing our algorithms in practice, instead of using an oracle that is provably efficient for all worst-case inputs, it suffices to have a weaker oracle that performs reasonably well on “average” case instances. \n\nFurther, for many practical classes of conditional probability densities, heuristic algorithms (for example bases on deep learning) are often used in practice. One perspective on this line of work is developing machinery to convert algorithms for heuristic optimization into provable algorithms for sequential decision making\n\n\n**On technical hurdles of our work and contributions relative to prior work**:\nPrior work focused on the case of the binary loss and VC classes and presented a statistical rate for the smoothed setting matching the rates for the iid case. In our work, we focus on the log loss which does not fall into their framework because of the poor Lipschitz constant and unboundedness. Furthermore, their original result can be seen as a covering based argument while our general result is a direct reduction from the smoothed setting to the transductive setting. Our work goes beyond finite covering numbers. This allows our work to extend to non-parametric settings and others where the covering numbers do not capture the regret in the  log-loss setting. To get these stronger results, our approach differs entirely from Haghtalab et al. ‘22. Rather than looking at coverings, our main statistical result establishes a reduction from the smoothed online setting to a version of transductive setting. In particular, we show that the regret is small as long as the notion of transductive regret is small without the need to restrict to settings with small covering numbers. Interesting consequences of this covering-number free approach are discussed in Section 3.2.2. \n\n\nThe algorithmic questions in our paper require new technical innovations. To the best of knowledge, oracle efficiency has not been considered at all for losses such as the log loss even though we believe this is a natural setting for oracle efficiency since the ERM oracle corresponds to the maximum likelihood estimator (MLE). Technical challenges arise from the fact that the log loss is unbounded and non-Lipschitz which was a necessary requirement from previous work. Furthermore, a main technical contribution is techniques to handle the MLE oracle (which differs from the previous work which uses a more general regression oracle). Technically, this corresponds to a different way of controlling the perturbation term in the regret."}, {"review_id": "039lbnvaJF", "reviewer": "Reviewer_oQa8", "summary": "The paper discusses smoothed analysis of probability assignments in an online setting. The paper shows how the problem can be reduced to a transductive setting and obtains an upper bound on the regret using covering numbers which is further bounded by the scale sensitive VC dimension. The results are instantiated for various classes of functions, including VC function class and the non-parametric class where the scale sensitive VC dimension grows as \\epsilon^{-p} at scale \\epsilon. \n\nOn the algorithmic side, the authors propose an oracle efficient FTPL style algorithm to predict the probability assignments and show weaker regret bounds for the same (by bounding the Rademacher complexity)", "questions": "- The authors can elaborate the results of Wu.et al [2023] and highlight the differences and similarities (both in terms of results and techniques). \n-  Is Algorithm 1 actually implementable in practice - especially without the knowledge of \\sigma, the smoothness parameter? \n- How do the results change in case the adversary is realizable w.r.t to the class F that the regret is measured against?\n- How critical is the assumption on uniform distribution over X. For instance if X does not support a uniform distribution, how does Algorithm 1 and it's guarantees change?\n\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and is very clear and easy to follow.\n- The paper is the first to consider Oracle efficient algorithms for the sequential prob. assignment problem\n- The paper creatively combines earlier ideas (Coupling Lemma) to reduce the smoothed adversary setting to a transductive setting.\n", "weaknesses": "Please see questions below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments.\n\n**Regarding the concurrent work by Wu et al**: As the reviewer pointed out that both the papers were concurrent and independent works. We agree that the ideas in the statistical aspect of our paper are related to the ones in Wu et al 2023 and are both inspired by the coupling lemma from Haghtalab et al 2021. \n\nThe small overlap between the results of these two papers is only limited to the statistical rates for the case of VC classes (the statement of Corollary 3.4.1). Even in the statistical case, our work goes beyond VC classes as opposed to Wu et al, who only considered the case of finite covering numbers. This allows our work to extend to non-parametric settings and others where the covering numbers do not capture the regret in the  log-loss setting. To get these stronger results, our approach differs entirely from Wu et al. Rather than looking at coverings, our main statistical result establishes a reduction from the smoothed online setting to a version of transductive setting. In particular, we show that the regret is small as long as the notion of transductive regret is small without the need to restrict to settings with small covering numbers. Interesting consequences of this covering-number free approach are discussed in Section 3.2.2. \n\n\nA major contribution of our work is the study of oracle-efficient online learning for the log-loss, which has not been considered by Wu et al. Indeed, to the best of knowledge, oracle efficiency has not been considered at all for losses such as the log loss even for worst-case settings. Considering oracle-efficiency for log-loss is an important and natural line of research as the ERM oracle corresponds to the maximum likelihood estimator (MLE) that is commonly used in practice.  Our paper presents sublinear regret oracle efficient algorithms for the log loss (which does not have an analog in Wu et al 2023).  ​​In our opinion, the algorithmic questions in our paper are a significant contribution. \n\n**Implementation in practice and Smoothness parameter**:\nWe believe that the algorithm is very reasonable to implement in practice when given access to a class of models that one can optimize over. Note that the algorithm just choses some samples from the base distribution and adds it to the training set and uses the optimization oracle. For many classes of interest such as neural networks one can implement optimization oracles using (stochastic) gradient descent (in practice).\n\nFurther, we clarify that the exact knowledge of $\\sigma$  is not needed by our approach. Our algorithms and regret bounds can work with any approximation of sigma value that is a lower bound of the real up to constant multiplicative factors. This corresponds to settings where the world is more smooth than we give it credit. Even when we have extremely poor upper and lower bounds, we can use hedging to still get non-trivial regret with only a minor blow up in computation. We will provide more details next as to how we work with knowledge of approximate sigma.\n\nIn general, given (loose) upper and lower bounds on the exact value, we can use a geometric doubling approach to deal with the unknown $\\sigma$. To be specific, one could construct experts, where each expert runs a local version of our algorithm with parameters $ \\sigma_i = \\sigma_{low} 2^i$. Here $\\sigma_{low}$ is a loose lower bound on $\\sigma$. We maintain experts till $\\sigma_i = \\sigma_{high}$ which is a loose upper bound on $\\sigma$. We then run Hedge on these experts. Note that the parameter of the best expert satisfies $\\sigma/2 \\leq   \\sigma_i \\leq 2 \\sigma$ , so its regret matches the regret of the same algorithm that runs on true $\\sigma$ up to a constant factor. Therefore, the expected regret of this meta algorithm is comparable to the bound in with known $\\sigma$, with an additive term of order at most $\\sqrt{T \\log \\log (\\sigma_{high} / \\sigma_{low} )}$. This could potentially be improved using a more aggressive step size for the Hedge meta algorithm.\n\n**Realizability**: For the statistical rates, realizability (appropriately defined) does not affect the rates significantly.But for the oracle efficient case this is an interesting question. Even for the binary loss case, this is not fully understood in the sense that we don't know an algorithm that achieves oracle efficient fast rates in the realizable case. Understanding this in the log loss case is an excellent avenue for improving the rates.\n\n**Uniformity on $\\mathcal{X}$**: The notion of smoothness with respect to an arbitrary measure in general without the domain to have a uniform distribution. The algorithm 1 generalizes in a natural way to this setting by sampling from the base measure $\\mu$ instead of the uniform distribution. The analysis also remains the same (by and large) but some care needs to taken in order to define appropriate notions (such as Poisson processes) that we use in the analysis to the arbitrary domain. \n"}, {"review_id": "M9EGqzS2E1", "reviewer": "Reviewer_X6XT", "summary": "The paper considers the sequential probability assignment problem, which is the following:\n\nThe algorithm (forecaster), based on past context and outcomes, must assign probabilities to 0-1 values for the next outcome given the latest context. The forecaster competes against a reference class of predictor functions (experts) and aims to suffer low regret compared to the best of these functions. For a logarithmic loss incurred for incorrect predictions, regret is defined as the difference in the total log-loss of the forecaster and the best of the experts.\n\nWhen the contexts are drawn independently from an unknown distribution, and the class of predictor functions is special (say, has a bounded VC dimension), the sequential probability assignment has low (i.e. sublinear) regret. However, if the contexts are adversarial, there are impossibility results even for simple classes of predictors.\n\nTherefore, following Haghtalab et al. (2021), the authors study a smoothed version of the problem where contexts can only be chosen adaptively from the set of sigma-smoothed distributions. They study how the properties of the class of the predictor functions like bounded “scale-sensitive” VC dimensions affect the regret. \n\nThe main tool used is a powerful coupling lemma from Haghtalab et al. (2021) that converts the problem with an adaptive sequence of t contexts to a problem with t*K uniformly and independently distributed contexts (the length of the sequence increases but they are no more adaptive). Thus, results for i.i.d. samples may be applied where the regret is essentially logarithmic in T (number of time steps), which is the first result of the paper.\n\nThe second question studied is an algorithmic approach to solving the problem using calls to MLE. A follow the perturbed leader type algorithm using ideas generalized from Haghtalab et al. (2022) is used. Here, however, the regret is not logarithmic but T^0.8. This is the second main result in this paper.", "questions": "--", "limitations": "n.a.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and the considered problem is natural. The results are interesting.", "weaknesses": "It seems the first main result of this paper is already presented in a paper that has been accepted at COLT 2023 (Wu et al.) Even though this seems to be independent work of a different group of authors, I would still find it strange if the same result was now also accepted at NeurIPS, in particular because the proofs are quite similar. Both rely essentially on the coupling arguments from the work of Haghtalab et al. I also have to say that my impression is that the known coupling argument is really the key ingredient and the proof in this submission is \"only\" an adaption of the arguments by Haghtalab to the log-loss setting. Maybe the authors could point out more clearly if there were significant challenges in this adaption. \n\nThe second main result is not contained in the COLT paper. However, it unfortunately only shows a regret of T^0.8 and no logarithmic one and it also follows known algorithmic approaches from the literature like follow the perturbed leader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. \n\n**Regarding the concurrent work by Wu et al**: As the reviewer pointed out that both papers are concurrent and independent works. We agree that at first sight the ideas in the statistical aspect of our paper are related to the ones in Wu et al 23 and are both inspired by the coupling lemma from Haghtalab et al 21. As we explain below, the overlap between the results are minor and limited to one of our statistical rates, our statistical rates are stronger than Wu et al in general, and one of our primary contributions (computational perspective) forms a very novel setting that has not been studied before. In short, our work has independent insights, results, contributions, and open directions than Wu et al. 23 and will draw independent readership and interest from the field.\n\nThe small overlap between the results is only limited to the rates for the case of VC classes (Corollary 3.4.1). Even in the statistical case more broadly, our work goes beyond VC classes as opposed to Wu et al, who only considered the case of finite covering numbers. This allows our work to extend to non-parametric settings where the covering numbers do not capture the regret. To get these stronger results, our approach differs entirely from Wu et al. Our main statistical result establishes a reduction from the smoothed setting to a transductive setting. Interesting consequences of this approach are discussed in Section 3.2.2. \n\n**Algorithmic Challenges**: A major contribution of our work is the study of oracle-efficient online learning for the log-loss, which has not been considered by Wu et al. Indeed, oracle efficiency has not been considered at all for the log loss even for worst-case settings. Considering oracle-efficiency for log-loss is an important line of research as the ERM oracle corresponds to the maximum likelihood estimator (MLE) that is commonly used in practice.  Our paper presents sublinear regret oracle efficient algorithms (which does not have an analog in Wu et al 2023). ​​In our opinion, this is a significant contribution.\n\nWe acknowledge the reviewer’s concern regarding regret rates. As we state in our section 5, we believe that obtaining subpolynomial bounds is an interesting direction for future work. We also provide discussions and some evidence that highlights why any MLE oracle (and FTPL analysis) will face significant technical challenges in obtaining subpolynomial regret bounds, due to these methods’ reliance on $\\sqrt{T}$ “out of sample generalization'' variance term.  We believe that this discussion and our proof approach will be insightful more broadly for online algorithm design. Proving lower bounds is also challenging, as log-loss necessitates considering improper algorithms which are historically challenging for obtaining lower bounds. This puts the problem in an intriguing situation that warrants further investigation. We believe that significant progress requires perspectives and the publication of our work will bring this to the attention of the community.\n\n**On the algorithmic framework of FTPL**:  One of our main technical contributions is an oracle-efficient algorithm that taps into the MLE oracle to achieve sublinear regret for the log-loss. We emphasize that most work on oracle efficiency considers a “mixed loss” oracle that minimizes a signed combination of the historical losses. This is unnatural in the log loss setting and a major technical consideration that sets our work apart from other work on oracle-efficient online learning is to work just with MLE oracles due to the natural connection to statistical estimation.\n\nFurther we believe \"known algorithmic approaches from the literature like follow-the-perturbed leader\" again minimizes our contributions. In particular, algorithms in the oracle efficient setting are forced be similar to FTPL, since the algorithm is only promised a \"leader\" oracle. The fact that all oracle-efficient algorithms utilize the FTPL framework is a testament to its fundamental nature. The main challenge in designing oracle efficient algorithms is getting regret and running times roughly logarithmic in the number of experts (note that the basic FTPL analysis gives polynomial dependence on the number of experts). Since this (provably) cannot be done in generality each paper adapts the FTPL framework to the particular setting.\n\n**On the use of coupling lemma**: Indeed, the coupling lemma of Haghtalab et al ‘21 was a fundamental tool in the analysis of smoothed online learning. Since then, every work in this space published at top tier conferences such as NeurIPS, and COLT (which constitutes 10s of papers) has relied on that coupling lemma. This should be taken as the evidence of the unusual versatility of the coupling lemma, but not to underestimate contributions of a long line of work on smoothed analysis. Additionally, see the comments above regarding the reduction between smoothed analysis and transductive learning for further differences between our work and prior work. \n\n**On treatment of concurrent literature**: As demonstrated above, our results are novel and have only minor overlap with Wu et al. Indeed, the work of Wu et al did not consider  computational aspects to smoothed analysis. Even for statistical analysis, our approach presents a more general approach that extends to general losses. In short, our work has independent insights, results, contributions, and open directions than Wu et al. 2023 and will draw independent readership and interest from the field.\n\nThe publication of the concurrent works (with a minor overlap) in other conferences is only evidence that the community is very interested in this line of work. The first versions of our work were made public within days of each other. We believe that rejecting a work for a minor overlap with concurrent work is a deviation from standard practice in the review process and would be counterproductive for the research community.\n"}, {"review_id": "kPFKDe2SCc", "reviewer": "Reviewer_9j8s", "summary": "The paper studies the sequential probability assignment problem with a smoothed adversary. The learner sequentially assigns a probability given contexts, which the adversary generates from a distribution that can be far from a known base distribution by a factor of $1/\\sigma$. For the problem with the i.i.d. setting, there is an $O(\\log T)$ regret method, while we must incur $\\Omega(T)$ regret in the pure adversarial setting. Thus, it is well motivated to study what regret is possible in the smoothed setting with respect to $T$ and $1/\\sigma$. \n\nThe authors provide a general regret bound via reduction to transductive learning. E.g., if the class of functions that map contexts to a probability has the VC dimension of $d$, the regret is $O(d \\log (T/\\sigma))$, achieving the logarithmic dependence on $T$ and $1/\\sigma$. The authors also present an FTPL-style algorithm that is efficient in terms of calls to MLE oracles. It is shown that the algorithm attains $T^{4/5}\\sqrt{d/\\sigma}$ regret for the VC class. ", "questions": "1. I would appreciate it if the authors could describe intuitive technical differences from Haghtalab et al. [2021, 2022]. \n2. The scale-sensitive VC dimension appears to be related to the fat-shattering dimension. Is there some connection between them?\n\n#### Minor comments\n- In Algorithm 1's input, capitalization is inconsistent. \n- In Algorithm 1, line 2, a period or a line break is missing before \"Call the oracle...\"\n- I prefer references arranged in alphabetical order. \n- Hyperlinks do not work. ", "limitations": "Although limitations are not explicitly discussed, the range to which their results apply seems clear from the description. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies an interesting online learning problem under the smoothed setting, which is well motivated by the known results in stochastic and adversarial settings. \n2. The results imply some interesting consequences. Although I'm not an expert, I found Section 3.2.2 to be interesting, where the authors discuss the benefit of their covering-argument-free idea. ", "weaknesses": "1. Theorem 3.1, the reduction to transductive learning, seems to be relying heavily on the coupling lemma by Haghtalab et al. [2021]. \n2. The analysis of the oracle-efficient algorithm in Section 4.1 also appears to be relying on Haghtalab et al. [2022].  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We will incorporate corrections to the typographical errors in a revision.\n\n**Differences between Haghtalab et al 21,22 and our work**: The main focus of the work by Haghtalab et al 21, 22 was on the case of the binary loss. Haghtalab et al 21 focused on the case of the binary loss and VC classes and presented a statistical rate for the smoothed setting matching the rates for the iid case. In our work, we focus on the log loss which does not fall into their framework because of the poor Lipschitz constant and unboundedness. Furthermore, their original result can be seen as a covering based argument while our general result is a direct reduction from the smoothed setting to the transductive setting. Our work goes beyond finite covering numbers. This allows our work to extend to non-parametric settings and others where the covering numbers do not capture the regret in the  log-loss setting. To get these stronger results, our approach differs entirely from Haghtalab et al. Rather than looking at coverings, our main statistical result establishes a reduction from the smoothed online setting to a version of transductive setting. In particular, we show that the regret is small as long as the notion of transductive regret is small without the need to restrict to settings with small covering numbers.\n\nHaghtalab et al 22 focuses on the oracle efficiency (also for the binary loss or finite regression loss). The main algorithmic difference between our result and theirs is the choice of the oracle. In our paper, we focus on the MLE oracle which just outputs the best model in the class on the data while their paper uses a stronger notion of what is commonly referred to as a mixed binary-regression oracle. The difference is important in the case of the log loss because the MLE oracle can be seen as a natural subroutine in statistical analysis while the general mixed binary-regression oracle is unnatural in most settings including the log loss setting. Technical challenges arise from the fact that the log loss is unbounded and non-Lipschitz which was a necessary requirement from previous work. Furthermore, a technical challenge in handling the MLE oracle corresponds to a different way of controlling the perturbation term in the regret.\n\n**On the use of coupling lemma**: Indeed, the coupling lemma of Haghtalab et al ‘21 was a fundamental tool in the analysis of smoothed online learning. Since then, every work in this space published at top tier conferences such as NeurIPS, STOC/FOCS, and COLT (which constitutes 10s of papers) has relied on that coupling lemma. This should be taken as the evidence of the unusual versatility of the coupling lemma of Haghtalab et al ’21, but not to underestimate contributions of a long line of work on smoothed analysis since Haghtalab et al ’21. \n\nFurthermore, the original result of Haghtalab et al  ‘21 can be seen as a covering based argument while our general result is a direct reduction from the smoothed setting to the transductive setting. Our work goes beyond finite covering numbers. This allows our work to extend to non-parametric settings and others where the covering numbers do not capture the regret in the  log-loss setting. To get these stronger results, our approach differs entirely from previous work. Rather than looking at coverings, our main statistical result establishes a reduction from the smoothed online setting to a version of transductive setting. In particular, we show that the regret is small as long as the notion of transductive regret is small without the need to restrict to settings with small covering numbers. Our reduction to the transductive setting is a novel and promising approach that we expect will have an equally versatile role to play (compared to the coupling lemma of Haghtalab et al ‘21) for the study of statistical and computational perspective of unbounded losses and losses with curvature.\n\n\n**Scale-sensitive Dimension and Fat shattering dimension**: The notions of complexity are different terminology arising from different communities. For example, compare definition 3.2 in https://home.ttic.edu/~tewari/lectures/lecture15.pdf  and section 2.4 in https://arxiv.org/pdf/2202.04690.pdf\n"}, {"review_id": "skQH8XF8Ib", "reviewer": "Reviewer_4UMy", "summary": "This paper focuses on the contextual sequential probability assignments, and specifically examines cases where the contexts $x_{1:T}$ are generated by $\\sigma$-smooth adversaries as introduced in [Haghtalab et al. 2021], and where the labels $y_{1:T}$ are adversarially generated. The primary findings pertain to the minimax regrets under the logarithmic loss, as compared to a generic set of experts $\\mathcal{F}$. More specifically, the paper demonstrates the following:\n\n1. If the class $\\mathcal{F}$ possesses a scale-sensitive VC-dimension of order $\\epsilon^{-p}$, then the information-theoretical minimax regret grows as $T^{p/(p+1)}\\cdot \\text{poly}\\log(T/\\sigma)$, which is tight up to polylogarithmic factors.\n\n2. An efficient algorithm exists, given an MLE oracle, that attains regret of order $T^{2/(2+w)}\\sqrt{1/\\sigma}$, provided the Rademacher complexity of $\\mathcal{F}$ is of order $T^{-w}$. For the VC-class, specifically where $w=1/2$, this algorithm yields a regret bound of order $T^{4/5}$.\n\n3. For the VC-class, it demonstrates that the information-theoretical regret is of the order $d\\log(T/\\sigma)$ up to a constant factor (the same result was also found in concurrent work [Wu et al. 2023]).\n\nThe principal contribution of this paper that distinguishes it from previous work on contextual sequential probability assignments is the introduction of an oracle-efficient algorithm that achieves sublinear regret. Although the primary techniques are rooted in the FTPL (Follow The Perturbed Leader) framework as outlined in [Haghtalab et al. 2022], this unique contribution sets a new precedent in this line of research.", "questions": "I have the following questions for the authors:\n\n1. It seems that your FTPL algorithm relies on an exact ERM oracle. I'm curious, how would the performance or operation of the algorithm change if the oracle was only approximately optimal?\n2. Is there any computational lower bounds as in [Haghtalab et al. 2022] that can be proved for the log-loss?\n3. Your bound in Theorem 4.1 seems to rely solely on the Rademacher complexity. Does this suggest that your analysis isn't capable of achieving a $\\log(T)$ dependency for the VC-class? For instance, consider the linear function $|\\langle w,x\\rangle|$ with $w,x$ in a unit ball (of a Hilbert space). This class admits a $1/\\sqrt{T}$ Rademacher complexity, but it's known that the information theoretical lower bound is $T^{2/3}$.\n4. Is it possible to achieve better dependency on $T$ with your FTPL algorithm if the contexts are generated from an i.i.d. process (i.e., with $\\sigma=1$)?", "limitations": "No issue with negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The primary strength of this work lies in the oracle-efficient algorithm, which presents the first known instance of computationally efficient sublinear regrets under log-loss for general non-parametric classes, albeit using an MLE oracle. This is likely to inspire further research in this field.", "weaknesses": "The main weakness is the novelty of the techniques used in this paper. From a purely technical standpoint, Algorithm 1 and its analysis seem to merely mimic those used in [Haghtalab et al. 2022]. In fact, there are many places in the proof that appear to be verbatim copied!\n\nThere are also some presentation and technical issues, which I outline below:\n- There are many places where the index of summation is $i$ but the summand is written as $s_t$, for instance, in Lemma 4.2. I suggest the authors conduct a thorough proofreading, including the appendix, to correct issues like this;\n- I recommend that the authors include a proof for Corollary 4.1.1. It's unclear to me how Theorem 4.1 implies this bound for certain values of $n$, $\\alpha$, and $m$;\n- The authors claim that a $T^{3/4}$ bound could be achieved for an alternative oracle. This is not clear to me at all. Are you refering to the Theorem 7 of [Block et al., 2022]? If so, it should be properly cited and clearly explained by what you mean \"mixed objective function\";\n-  In line 636 (appendix), it appears that Lemma 3.3 from [Haghtalab et al., 2021] requires $\\epsilon> \\frac{\\sigma}{T\\log T}$? The choice of $\\epsilon=\\frac{\\sigma}{T^2}$ does not align with the condition stated in that Lemma. I believe a stronger concentration result, such as Lemma 21 from [Wu et al., 2023], would be required in this context;\n- In the proof of Lemma 4.4, presented in Appendix G, you assert that the distributions $P, Q$ are solely dependent on the ensembles $\\\\{n_0(x),n_1(x)\\\\}$. However, I contend that this is not a self-evident fact. It is essential, at the very least, to posit that your OPT oracle is permutation invariant with respect to the input sample sequence. This assumption, it should be noted, does not necessarily hold for all optimization methods; stochastic gradient descent, for example, may not exhibit this property.\n\nThese are the primary reasons I give a \"weak accept\".\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review and the careful reading of our paper. We will fix the typographical errors and omissions. \n\n**Choice of parameters**: Thanks a lot for noticing this. Upon further inspection our proof gives the desired bound with the choice $\\epsilon = \\sigma / T \\log T$ as would work with the original lemma in Haghtalab et al. We will fix this in the revision. \n\n**Permutation Invariance**: We agree that the claim made in the paper would need permutation invariance of the oracle. But in our notation we consider the input to the oracle as the unordered set of historical point and the objective (the average loss) is permutation invariant. In particular, we can achieve the desired permutation invariance by randomly shuffling the data. But we agree that explicitly mentioning this would be helpful and we will elaborate on this in a revision. \n\n**Approximate ERM**: The question regarding the approximate oracle is a good one. Previous works on oracle efficiency have studied the effect of approximation on FTPL type algorithms (See section 6 https://arxiv.org/pdf/1611.01688.pdf). Incorporating (additive) approximations is usually simple but multiplicative approximations are considered challenging and have received study even in the binary case. Even there we don’t have a fully satisfactory solution beyond the linear case. (See for example https://arxiv.org/abs/1804.07837, https://arxiv.org/abs/2102.11050). Studying the appropriate notion of approximate regret in this setting is an interesting avenue for further research. \n\n**Dependence on Rademacher Complexity**: As the reviewer notes the dependence on the Rademacher complexity is a reason for a lack of sharpness in the oracle efficient setting. Unfortunately, this dependence (or on a similar quantity) seems fundamental to FTPL/stability type analysis due to the requirement to analyze the “out of sample generalization” (in our setting, this comes up in analyzing the error between the hallucinated sample and hypothetical coupled random variables). We believe circumventing would require novel ideas and is an exciting avenue of research. \n\n**Computational Lower Bounds**: The main challenge in proving computational lower bounds in the log-loss setting is that most natural algorithms here are fundamentally improper. In general, we do not have good tools to prove lower bounds for improper algorithms (even in the worst-case binary setting). Since the lower bounds in Haghtalab et al are primarily for proper algorithms, they do not port naturally to this setting. Either proving improper algorithm lower bounds or improving oracle efficient regret for improper algorithms is an excellent area for research, whose relevance is further accentuated by oracle efficiency for the log loss introduced in our work. \n\n**IID contexts**: When both the contexts and labels are generated in an iid fashion, the analysis of our regret of our algorithm reduces to the classical analysis of the error of MLE. When the contexts are iid and labels are adversarial, the bound is not immediately clear. Similar setups are studied in online learning (for example in contextual bandits https://arxiv.org/pdf/1606.00313.pdf, https://arxiv.org/pdf/2003.12699.pdf). But usually even in this setting, the analysis is fairly involved. But, the iid context setting is a natural first place towards improved regret bounds.  "}]

Author rebuttal:

Meta-review: This paper analyses the regret of sequential probability assignment problems with binary labels, when the labels are adversarial but feature distributions are smoothed. Reviewers agree that this is a strong contribution to the recent literature on characterizing such problems by weakening the strong adversarial setting. The most important aspect to address is to explain the significance of the theorems in plain language, to improve their appreciation by the readership. The authors are also advised to more carefully compare with the Haghtalab et al 2022 and the concurrent  Wu et al 2023 papers, particularly in terms of the technical tools used. Discussions with reviewers, e.g., on the practical usefulness of oracle access to ERM and where changing the uniformity assumption would affect the results, should also ideally find their way to the paper. Lastly, the paper's mathematical notation could benefit from a thorough proofreading pass, e.g., to make sure the summation indices are correct.
Decision: Accept (spotlight)