Oracle-efficient Hybrid Learning with Constrained Adversaries
Authors: Princewill Okoroafor
Robert Kleinberg
Michael P. Kim
Venue: ICLR 2026 Poster (2026)
Keywords: hybrid online learning
oracle-efficiency
ERM
rademacher complexity
Primary area: learning theory
TL;DR: oracle-efficient hybrid online learning with regret scaling with classical rademacher complexity

Abstract: The Hybrid Online Learning Problem, where features are drawn i.i.d. from an unknown distribution but labels are generated adversarially, is a well-motivated setting positioned between statistical and fully-adversarial online learning. Prior work has presented a dichotomy: algorithms that are statistically-optimal, but computationally intractable \citep{wu2023expected}, and algorithms that are computationally-efficient (given an ERM oracle), but statistically-suboptimal \citep{pmlr-v247-wu24a}.

This paper takes a significant step towards achieving statistical optimality and computational efficiency \emph{simultaneously} in the Hybrid Learning setting. To do so, we consider a structured setting, where the Adversary is constrained to pick labels from an expressive, but fixed, class of functions $\mathcal{R}$. Our main result is a new learning algorithm, which runs efficiently given an ERM oracle and obtains regret scaling with the Rademacher complexity of a class derived from the Learner's hypothesis class $\mathcal{H}$ and the Adversary's label class $\mathcal{R}$. As a key corollary, we give an oracle-efficient algorithm for computing equilibria in stochastic zero-sum games when action sets may be high-dimensional but the payoff function exhibits a type of low-dimensional structure. Technically, we develop a number of novel tools for the design and analysis of our learning algorithm, including a novel Frank-Wolfe reduction with "truncated entropy regularizer" and a new tail bound for sums of "hybrid'' martingale difference sequences.

ORACLE-EFFICIENT HYBRID ONLINE LEARNING WITH CON-
STRAINED ADVERSARIES
Princewill Okoroafor Coreell University
pco9@cornel1.cm edu
Robert Kleinberg
Cornell University rdk@cs. coriics..coeeeleeee
Michael P. Kim
Cornell University mpkêcs. cornell. edu
ABSTRACT
The Hybrid Online Learning Problem, where features are drawn i.i.d. from an un- known distribution but labels are generated adversarially. is well-motivated setting positioned between statistical and fully-adversarial online learning. Prior work has presented a dichotomy: algorithms that are statistically-opiimall but computation- ally intractable (Wu et al., 2023), and algorithms that are computationally-efiin (given an ERM oracle), but
(Wu et al., 2024).
This paper takes a significant step towards achieving statistical optimality and computational efficiency simultaneously in the Hybrid Learning setting. To do so, we consider a structured setting, where the Adversary is constrained to pick labels from an expressive, but fixed. class of functions R. Our main result new learning algorithm, which runs efficiently given an ERM oracle and obtains regret scaling with the Rademacher complexity of a class derived from the Learner's hypothesis class H and the Adversary' label class R. As a key corollary, we give an oracle-efficient algorithm for computing equilibria in stochastic zero-sum games when action sets may be high-dimensional but the payoff function exhibits type tow-dimensional structure. Technically, we develop a number of novel tools for the design and analysis of our learning algorithm, including novel Frank- Wolfe reduction with "truncated entropy regularizer" and a new tail bound for sums "hybrid" martingale difference sequences.
INTRODUCTION
Online learning a fundamental paradigm in machine learning, where an algorithm learns sequen- tially from stream of data, making predictions and updating its model in real-time. Within the broad landscape of online learning, different assumptions can be made about how the data is generated. Two prominent extremes the statistical setting, where data drawn independently and identically distributed (i.i.d.) from a fixed, unknown distribution, and the fully-adversarial setting, where data is chosen by an adaptive adversary aiming to maximize the learner's error. While these are well-studied, the guarantees a learner can obtain can vary starkly between the two extremes. For example, the problem of learning thresholds from a small number of samples is straightforward in the statistical setting, but impossible in the fully-adversarial setting (Littlestone, 1988).
The Hybrid Online Learning Problem (Lazaric & Munos, 2009) has emerged as compelling middle ground, capturing aspects both statistical and adversarial scenarios. In this model, features are assumed to be drawn i.i.d. from an unknown distribution, much like in the statistical setting. The corresponding labels, however, are determined by potentially malicious adversary. On a practical level, this hybrid model captures real-world situations where typical instances follow statistical

---

patterns, but the labels associated with these instances influenced by strategic actors, system dynamics, or other worst-case forces. Theoretically, the model serves as an important frontier for exploring the limits of efficient online learning with provable guarantees.
The current state of research in Hybrid Online Learning hints computational-stati -taatssssistttttiiaalllll divide. Algorithms that achieve statistically optimal performance (Lazaric & Munos, 2009; Wu et al., 2023) are typically computationally intractable with time and space complexity both scaling linearly in the size of the learner's s hypothesis class. On the other hand, algorithms that are computationally efficient typically assume the learner has full knowledge of or unlimited sample access to the underlying feature distribution (Rakhlin et al., 201 I; Haghtalab et al., 2024; Block et al., 2022), or they achieve suboptimal regret (Wu et al., 2024).
This work takes a crucial step towards bridging this gap, aiming to develop learning algorithms that both statistically optimal and computationally efficient in the Hybrid Learning setting. To make progress on this challenging goal, we focus on a structured version of the problem. Specifically, we introduce a constraint on the adversary, assuming that the adversarial labels must be chosen from an expressive, but fixed, class of functions R. This structural assumption allows for a more fine-grained analysis and algorithm design. Our main contribution the development of novel oracle-efficient learning algorithm for this structured setting.
1.1 PROBLEM FORMULATION
We consider the following Hybrid Online Learning Problem: Let X be the feature space and H S [0, 11x and R _ [0, 1] be the learner's hypothesis class and the adversary's constrained label function class, respectively, which are known the learner. We assume the learner's 's loss function e: [0, 1] [0, 1] R is convex and L-Lipschitz with respect to its first argument for some constant L 0 and measurable the second argument. The learning process proceeds over rounds. Nature commits fixed, unknown distribution D over X. In each round I....,T:
1. The learner selects a hypothesis h1-
2. The adversary, with knowledge of the learner's strategy but not the future feature x,, selects function r, from the adversary's 's label function class R.
3. Nature samples feature x, i.i.d. from D. The learner incurs loss (()())))):<xx)))) The pair (X₁, ri) is revealed to the learner.
The learner's goal minimize its cumulative loss. The learner's strategy at time r is function of the history (x1, m.).... .......(ee (z-1), We evaluate the performance of learner by its regret with respect to the best fixed hypothesis H in hindsight. The regret over T rounds defined as:
Σ ((h((x)) min Σ ((0x)):n((x)) WETH
RTg(T) = E Ay
The expectation is taken over the random draws of xI,..., Xy from the distribution D. In ad- dition to this realized regret, it will be convenient consider the in-expectation regret i.e., Ii Ex-D [f(,,(x), (x))] minseh E Br-D [((h(x), r,(x)) Our goal is to design an oracle-efficient learner that minimizes this regret.
1.2 OVERVIEW OF RESULTS
Our main contribution is the development of an oracle-efficient learning algorithm for the Hybrid Online Learning Problem in a structured setting where the adversary's labeling function is constrained to a class R. Our algorithm achieves a statistically near-optimal (up to the dependence on the adversary's constraint set R) regret bound while being computationally efficient given access to linear optimization oracle over the hypothesis class H.
A key quantity characterizing the statistical complexity of function classes is the Rademacher complexity (see Section 1.4 for definition). In statistical learning theory, the Rademacher complexity of hypothesis class H provides tight characterization of the generalization error and hence the statistical error rate (Mohri et al., 2012). Our main result provides a bigh-brroability regret bound for hybrid learner in terms of Rademacher complexity of the function classes.
2

---

Theorem 1.1. Let H [0, 11x be class of hypothesis functions and let R S [0, 1J be class of labeling functions. & [0, 1] [0. 1] - R be a convex, L-Lipschitz loss function in its first argument. There exists online algorithm that outputs sequence of hypothesis functions ....... ft such that with probability at least - ó over the draw of Xy. ~ D, the following bound on the cumulative loss holds:
Σ ((h,(x)),, min NEH
((h(x)) ( (Tradrr H x R) I.Tradr(H) + L /T (og(
min
where o 'H X R denotes the class of functions [x + f(h(x), x(x)) h E H.re E R). The algorithm runs in O(T2) time per round and makes O(72) calls a linear optimization oracle for H throughout T' rounds.
Theorem 1.1 shows that the regret of our algorithm is governed by the statistical complexity of the composite class l a (H x R). Intuitively, this class captures the interaction between the learner's s hypothesis class H and the adversary's labeling class R, since each function in the class maps x to the loss ((h(x), r(x)) induced by pair (h, Consequently, the regret scales with the Rademacher complexity of the family of losses that can arise from this interaction.
The bound is near-optimal up to its dependence on the adversary's ' class R and logarithmic factors in T. In particular, hybrid learning is at least as hard as the corresponding statistical learning problem, which implies a lower bound of order LTrady(HH L VT (6)( on the regret (Mohri et al., 2012). Thus, even in the absence of adversarial structure, the dependence on the complexity of H is unavoidable.
To illustrate the bound in a concrete setting, suppose H is a binary-valued hypothesis class with VC dimension d, and the composite class l o (H x R) is also binary-valued with VC dimension d'. In this case the Rademacher complexity scales as (ady(F) Of vZ/T) for VC classes (see Section 1.4), and the regret bound simplifies to Of VTT + LVTdd /
Finally, the theorem highlights the role of the adversary constraint. If R were unrestricted (for example, R = [0. 11"), then the composite class ( a (H x R) could be arbitrarily rich, and its Rademacher complexity need not vanish with T. In this case, Wu al. (2024) gives sublinear regret bound while our theorem does not. However, in the case where R is constrained to be from H, our theorem matches the lower bound from statistical learning up to log factors.
Our Hybrid Online Learning framework and our hybrid learner can be applied to the area of game theory and optimization, specifically for finding approximate solutions to stochastic saddle-point problems, or equivalently, finding approximate equilibria of stochastic zero-sum games. While is known that oracle-efficient algorithms for finding equilibria of arbitrary zero-sum games do not exist in general (see Theorem 4 of Hazan & Koren (2016)), our results enable designing oracle-efficient algorithms whenever the game's 's payoff function factorizes as the composition of bivariate convex- concave Lipschitz-continuous function with (stochastic) scalar-valued functions of each player's action. Intuitively, any such factorization of the payoff function gives the game a low-dimensional structure that is useful for efficient equilibrium computation. However, since the players' action sets themselves remain (potentially) nigh-dimensional, to take advantage of this low-dimensional structure in an oracle-efficient way one must design algorithms for player to learn an approximate best-response to their opponent's 's adaptively-chosen action sequence in the stochastic zero-sum game, leading naturally to a Hybrid Online Learning problem.
Corollary 1.2.
Let X be domain space and D be a distribution over X. Let H,R c 1] be classes of functions (assumed to closed under convex combinations) and : [0. 1] x [0. 1 be convex-concave payoff function that is L-Lipschitz in its first parameter. Consider the saddle-point optimization problem
min max BB--ol((((x)) beft rek
Given samples from D and access to best-response oracles for H and R. our online learning
algorithm can be used to find an approxxiae saddle point solution (Ii', rr") in polynomial time in m and the complexities of H and R. The approximation guarantee is <(m) radd,. +
As defined in Section 1.4, radr (F) is at most I for any FF and O (d/TT) for binary classes of VC dimension
d
3

---

/logmmmmm O(L /log m/m). where T (f f(x) u(h()), (x)) h H.r R). Note that rad,,. - 0 is necessary for uniform convergence of the payoff matrix.
Finally, along the way to establishing our main result, we prove general uniform convergence bound that may be of independent interest. This bound addresses the challenge concentration for function classes evaluated on i.i.d. data where the functions themselves are chosen adaptively based on the previous data samples:
Proposition 1.3. Let H be class of hypothesis functions and e be a loss function that is L-Lipschitz in the first parameter. Let X1, .7 be a sequence of i.i.d samples from a fixed distribution D. Let PT E [0, 1Jx be sequence of functions where 7, depends only X1, ....... X;-1 (and potentially prior adversarial choices). The following holds with probability at least 1 5 over the draw of Xr, for all h H:
1 ((H(x)) rxx)) T
Σ ((-1((((()) o (ady(1)) + L
log(T (8) T
This result provides uniform convergence bound that effectively handles the data detendeeendent nature of the sequence .y.....r. ry. The sequence ((h(x)) r,(x,)) - -Bn[((((x), r,(x))] is a martingale difference sequence since x, is sampled after the choice of r, is made. Applying Ezuma-HHofffiee a union bound over the class H would only work for finite classes and would lead to a suboptimal bound of log [H] We instead prove this lemma by employing symmetrization technique and the application of a bound based on the distribution-deeendeen sequential Rademacher complexity, a measure introduced by Rakhlin et al. (2011). The L-Lipschitzness of the loss function with respect to its first parameter is key and ensures the bound depends only on the complexity of the hypothesis class H and the Lipschitz constant L, rather than the complexity of the ri sequence itself. We defer the full proof to Appendix A.2. We use Proposition 1.3 to obtain the high probability guarantee in Theorem 1.1 on the sampled sequence.
together with
1.3 TECHNICAL OVERVIEW
Our technical approach begins by considering the in-expectation regret objective: to guarantee a bound on Σ/ Eo( ((()) min Σ/= Eo[((h(x), rxx)), We note that achieving a bound on this quantity is weaker benchmark compared to the standard regret definition (which measured against the sum of losses on observed samples).
key limitation in this setting is that we do not have direct access to the distribution D. To build intuition, suppose for a moment that we had access to m i.i.d. samples, S = [S), Smd. from the distribution D priori. We make the crucial observation that samples are sufficient to guarantee uniform convergence for the combined function class F = (f f(x) E(h(x), r(x)) Vh e H.r R] rate characterized by (F). Therefore, if we had these samples upfront, the problem could be formulated as an online learning over H. In each round given r, the loss a hypothesis h would be the empirical average loss over the sample set S: Es [((((x), r,(x))] >m (r,(ss)),;;))))) Due to the uniform convergence property, for any h E H and adaptive r E R. the empirical average Es [s(((((x), r((x))) would be a good approximation of the true expectation Since the loss function only depends on the samples, this online learning problem is essentially an Online Couvex Optimization problem with action set (((s))/m... h(.m)) e [o, 1/m]" for each h H and where the loss vector in each round corresponds to the empirical losses (((h(s)) r,()))........... E(h(Sm)) r, r,(Sm))) E [0. 1J" Since the action set the projection of H on the samples is subset of [0, 1 1/m]"" which is subset of the m-dimensional simplex, then applying Follow the Regularized Leader (FTRL) achieves regret of vT log m. Unfortunately, a naive application of FTRL will return actions on the m dimensional simplex which may not correspond to any hypothesis in the class H. To solve this problem. we introduce a Frank- Wolfe reduction to the linear optimization oracle in Section 3.
Enle(h(x),
However, in the Hybrid Online Learning problem, we do not have the samples upfront. Instead, observe samples sequentially as part of the online process itself. We thus use the dataset accumulated up to round - 1, S, (x-). to define an empirical loss at round Es, [((h, rx)x) I E (x), rx))). Unfortunately, due the dynamically changing structure of this empirical loss function (as the dataset D, grows with f), this problem cannot be directly modeled as an Online Convex Optimization problem with fixed vector space and sequence of linear loss functions.
4

---

Despite this challenge posed by the adaptive structure of the empirical loss, we are still able make progress by constructing an adaptive sequence of entropy regularizers. In a departure from standard employ are not strongly convex over the entire ambient vector
FTRL analysis, the regularizers space (which is of dimension 7). This is because we never observe the "full vector" of losses or learner's actions all 7' samples any given time < T. Nevertheless, demonstrating that our adaptive entropy regularizers are strongly convex on the relevant coordinates (the first dimensions) at step f. This careful construction allows us to achieve favorable bound of O( / log with respect to our in-expectation regret benchmark (the sum of expected losses).
bypass this difficulty by
Finally, the remaining step is to transition from the weaker benchmark (regret against the sum of expected losses over D) to the stronger benchmark (regret against the sum of actual losses incurred on the observed samples Xy).... This is where uniform convergence arguments shown in Proposition 1.3 come into play, allowing us convert the bound on the weaker benchmark into the desired bound on the standard regret definition.
1.4 TECHNICAL PRELIMINARIES
Complexity Measures For function class S Rx and samples xI...., E X, the empirical Rademacher complexity is radr(!fla....>> if F1) = Ear sup /uup/er JEF Σi= off((x)) where oh...., or
are independent random variables uniformly drawn from [+1]. The Rademacher complexity at horizon with respect to distribution D is rady(F) = E. bit...-p-p//adr(//ll.-... f f FDI. It is well known that for binary classes, the Rademacher complexity is tightly controlled by the VC dimension: it is both upper and lower bounded (up to logarithmic factors) by /VCdim(FF/T (Bartlett & Mendelson, 2003; Mohri et al., 2012). A similar result holds for real-valued classes and the fat-shattering dimension (Mohri et al., 2012).
We additionally define the composite function class: to H x R (x ((((), h H.r E R).
Linear Optimization Oracle Our algorithm's 's computational efficiency is measured in terms of calls to Linear Optimization Oracle for the hypothesis class H. A Linear Optimization Oracle for H is an algorithm that, given a set of points S (sI..... ... Sm] X and set of weights for those points V = ("I...., Vn) C R, returns a hypothesis A H that minimizes Σ v,h(s)) over H. In our context, the set will typically be the set of observed samples x)...., Xy-1 at round f.
1.5 COMPARISON TO PRIOR WORK
The study of hybrid online learning with unknown i.i.d. feature source was initiated by Lazaric & Munos (2009), who obtained O( VdTTlog) Tog regret for binary hypothesis classes with VC dimension d under the absolute loss. More recently, Wu et al. (2023) extended these guarantees to real-valued hypothesis classes and general convex losses, achieving statistically near-optimal expected regret bounds for VC classes. Their algorithms rely on constructing stochastic covers of the hypothesis class, which can be computationally intractable for many natural hypothesis classes.
The first oracle-efficient algorithm for this setting was given by Wu et al. (2024), who obtained 0(33/)73/4) regret for finite VC classes using celaxation-basee
method. While this approach is computationally efficient given an ERM oracle, the resulting regret rate is statistically suboptimal. Our work studies structured variant of the hybrid learning problem in which the adversary is constrained to choose labels from a fixed function class R. Under this assumption, we give an oracle-efficient algorithm whose regret scales with the Rademacher complexity of the composite class l o (H x R), thereby recovering statistical rates whenever this composite complexity small.
Our work is also related to recent results on smoothed and distribuutoon-strucuurdd online learning. In particular, Block et al. (2024) study a smoothed online learning model and show that empirical risk minimization can achieve oracle-efficient error rates governed by the statistical complexity of the hypothesis class even when the base distribution is unknown. Their results imply oracle-efficient algorithm for the realizable case of hybrid learning, in which all labels are generated by a single hypothesis from the class. A key distinction from our setting is that in the hybrid model we study, the adversary may choose a different labeling function r, E R at each round. In particular, even in the special case R H, the labels revealed the learner need not be consistent with any single
5

---

hypothesis h 'H over all rounds. Consequently, the hybrid setting consider strictly generalizes the realizable case while still achieving regret bounds of the same statistical order.
More broadly, smoothed online learning has been studied under various assumptions on the stochastic source (Haghtalab al., 2020; 2024; Block al., 2022). However, many of these works assume either knowledge of the base distribution or sampling access to it. In contrast, the hybrid model considered here assumes only that features are drawn i.i.d. from an unknown distribution. Relatedly, Rakhlin patrrbutioonddeeeddee online learning framework in which Nature adaptively
et al. (201) I) studied selects sampling distributions, but their results primarily apply to settings where the distribution is known to the learner.
Finally, work is conceptually related to the comparative learning framework introduced by Hu & Peale (2023), in which labeling functions are also restricted to lie in a known function class. A key difference is that in comparative learning the labeling function is fixed, whereas in our hybrid setting the adversary may choose a different labeling function r, E R at each round. Understanding whether complexity measures such as the mutual VC dimension introduced by Hu & Peale (2023) can characterize the sample complexity of hybrid learning remains an interesting direction for future work.
2 ORACLE-EFFICIENT HYBRID LEARNING
In Section 2.1, show an oracle-efficient learning algorithm for structured hybrid setting that provides the in-expectation guarantee in Section 1.4. In Section 2.2, we prove our main result (Theorem 1.1).
2.1 IN- IN-EXPECTATION REGRET GUARANTEE USING TRUNCATED ENTROPY REGULARIZATION
This subsection presents and analyzes an algorithm for hybrid learning that makes use of subroutine called an entropy-regulle regguaa--re (-ERM oracle over H, defined as follows.
Definition 2.1. An regulazzeee (-ERM oracle is initialized with a class of functions H. : X [0, 1J. The oracle takes, as input, subset S X of features, a set of triples (11,31, wi)..... (mm Ym: Wm) E S x R x E and parameters 1), It outputs an element h in the convex hull H. such that minimizes (within e) the function Σ w,((h(xx).)) yı) , Eres h(ss) log(h(s)+ I).
We use log(h(x;) + 1) rather than log h(x,) the regularizer to ensure the argument to the log is well-defined on [0. 1] but more importantly, a log(a 1) is uniformly strongly convex the entire interval [0, 1] In Section below, we show how to use the Frank- method to implement an e-approximate regularized (-ERM oracle using polynomial number of calls to linear optimization oracle.
Theorem 2.1. Let H C [0, 1I be a class of hypothesis functions and let R s [0, 1I be a class of labeling functions. Let & be loss function that is convex, L-Lipschitz in the first parameter. Given an engropy-regularized (-ERM oracle for H, Algorithm outputs a sequence of hypothesis functions hl,....hy hy such that with probability at least 6,
Σ r( S min Σ Bl((h(s), + +T ra o Hx O(L (LLVTTIOn log
lilh
The algorithm runs in time O(T²) per timestep and makes T calls the entropy-regullaizee {-ERM oracle for H.
Overview of Algorithm 1 The algorithm implements a hybrid Iearner using the Follow The Regularized Leader (FTRL) approach over the class H. We define surrogate loss for each timestep based on the empirical average of the actual loss with respect to the adversary's 's choice r, on the samples ,,...., X,1 seen so far. Then we choose the approximate minimizer of the cumulative surrogate loss and an entropy regularizer that only depends on A
Concretely, at each timestep the algorithm outputs a predictor h, E conv(H.) After observing the sample x, and receiving the adversary's 's labeling function r; the algorithm prepares the input dataset for the entropy-regularizedd ERM oracle to compute the next predictor h+- The dataset provided to

---

the oracle at step consists of triples (N;, w;) derived from the samples (.,,..., and the past adversarial functions 172.....77l Specifically, for each pair E (2..... and (l...., 1/, the oracle receives triple (x,, r,()), ,T) The oracle finds e-approximate minimizer of this cumulative regularized empirical loss, and this minimizer becomes the predictor 1,1 for the next round.
We introduce the following notation: let r(h) = (h(x))......) M(x)),)....,,)) and V = conv((v(h) h E H)). We define the surrogate loss function time 2 2 as (v()) - E ((vo),,())), and (v()) (where yd refers the s-th coordinate of the vector v). Define the regularizer at time as (1(1)) > yور log()!") 1), and (v)) 0. The algorithm at step outputs h, (corresponding to v2) where v, is an s-approximate minimizer of F,(v) Σ 2,(v) + v,(v) for / 1.
Algorithm Hybrid Learner via FTRL with Truncated- Erutrated-Entropy Regularization
Require: Sequence of ii.d. samples ( D", time horizon T, failure probability 6, approxima-
tion parameter & for the oracle
Ensure: Sequence of predictors [h,) where each h, conv(H)
1: Set < vT/L. log T. & = L. 2/
2: Initialize to some arbitrary hypothesis in H
3: for to T do
4: Output h, Observe x,-
5: Receive adversary function r, E R.
6: Construct the set of triples S = U'=a ((x, (x)),, i 11). (Fort= = L, = 0).
7: Obtain next predictor 4+11 E conv(H) by calling the antropy-regularin ERM oracle (in Algorithm 2) with input dataset S, and feature set xy]:
h+11 < arg min heComv(HH)
Σ we(h(x),y) (KYO))SS
Σ
(xx))og((hhx +D)
7 s=1
8: return: Sequence of predictors (hr
Lemma 2.2 (Approximate FTRL for Hybrid Learning). For 17.8 > O, the empirical regret of Algorithm is bounded by
T Tlog 2
4nd. log
Σ (.,)) min (,(1) wevy
+ 5L VET.
3
To prove this lemma, we first bound the regret of playing the exact minimizers of F,, Then we appeal to the strong convexity of F, and Lipschitzness of & to bound the loss of playing the approximate minimizers. We view this as an OCO problem with ambient vector space V c [0. 1)" and convex loss vectors ?, with adaptive sequence of regularizers v,. We adapt the analysis of FTRL to deal with the fact that the algorithm never observes the full vector E V and the regularizers are not strongly convex with respect to the f--norm of the full ambient space. However, the loss functions ł and the regularizer & only depend on the first / coordinates, which means its gradients are zero for coordinates
As result, the du, is strongly convex w.r.t the i norm of the first coordinates and this suffices for the proof. The full proof can be found in Appendix A.I.
Now we present uniform convergence result necessary for relating the average loss on the sam- ples seen so far to the expected loss under the true distribution. The full proof can found in Appendix A.1.
Lemma 2.3. Let C [O, 1Ix be class of functions. Let Xj. Xy be a sequence samples drawn i..d from a fixed distribution D. With probability at least 6, for all / [ F.
Σ f(x) (x))))))l(()))) 2rad, + log(2T/5) S
Proof of Theorem 2.1. By Lemma 2.2, the empirical regret of the sequence iz...., Vy (using 22.... 2T) with respect to any V is bounded by: EE ((0)) 0 log
7

---

OL VnET) Let E H be arbitrary, and v(h). Since v, v(h,).
Σ ((,, -
1 Σ (((x)) SO(L /ogg + VnST)
Applying Lemma 2.3 to the function class F (x- E(h(x), r(x)) Yh E e R), we have that, with probability least 1 6, for 2 and E H.
Σ (((x))) 2rad;-1(f (xx))
log(2T/0)
B B.-01((0h()
Plugging back in to the regret guarantee, we obtain that with probability at least 6, for E H,
B. (l0 Ex-21(((()))
(1)
log(2T/6)
R)
+ ( (T 0 VnET)
22)
1-1
1=2
0
Σ
rad,- H R))
Ol. T log VnET)
Using Lemma A0 we obtain
Σ
il s O(T rady (lo H x
Including the 1 term, minimizing over h H and setting rj vTLL & Llog 3/2 T/ VT:
B((0h(0). < min B(((h((), radr(( H R)) + 0 ( (T
The runtime of the algorithm dominated by constructing the dataset S, passed the entropy- regularized ERM oracle. Since [S]] Es 1) 0(1²), constructing this dataset requires 0(r) time per round.
2.2 PROOF THEOREM 1.1
Proof. We decompose the quantity to bound: Σn ((h(())), ((()) - min Σn ((h(x), rxx)))
A B + C where
A ((hh(())) EED(C)))))))(
and
B =
Bol((h(x)
min
Bole(h(x)
and
C= min HEHH
Ep(((h(x), r())) min keff
[(h(x)) r,(x))
We bound each term with high probability and allocate a 6/3 failure probability to each.
Term A is sum of martingale differencees, Z, ((h,(x,),,,x)) r(()) satisfies BIZIF,-1] O. Since is L-Lipschitz over the interval [0. 1], IZI s 2L. By the Azuma-Hoefiding
inequality, with probability at least - 8/3: A s 2 L log(1 ((8/3) L log(3/5)
OLL OTL
Term is the in-expectation regret guarantee. By Theorem 2.1, the algorithm guarantees: B T rady(E H R) O(I OQI.TToo (olg with probability at least 5/3.
8

---

Term C the generalization gap for the best hypothesis. By Proposition 1.3, for all E H, the differ- ence between empirical and expected sums bounded uniformly: 3Σ ((h, 12) x;)) Σ Eple(h, ri)ll s L.T . rady + O (VTTogg(T (6)) with probability at least 1 - 6/3. Using this uniform bound, we get C s L.- rH))(H)) + O( /T log(
Summing the bounds for A, B, and C, using a union bound, we obtain that with probability at least
1 1-6:
Σ ((,((s) min 7xx(x) S --rady H + rad, + (LyTToog(T/))
1=1
This proves the regret bound. The computational efficiency follows from Theorem 2.1's use of an entropy-regularize, ERM oracle, which shown in Lemma 3.1 to be implementable efficiently using linear optimization oracle for H.
3 FRANK- WOLFE REDUCTION TO LINEAR OPTIMIZATION ORACLE
In this section we show how implement the entropy-rrgularized ERM oracle of Definition 2.1 using only access to linear optimization oracle over H. Our implementation follows standard projection-free convex optimization approach based on the Frank WWlle method. The resulting procedure, given in Algorithm 2, computes an e-approximate solution to the regularized objective using a polynomial number of calls to the linear optimization oracle for H.
For the analysis of the Frank-Wole procedure we assume that the loss function l is convex and B-smooth in its first argument. This assumption is not restrictive. If ( is convex and I--Lipschitz but not smooth, we can apply the standard OCO-to-OLO reduction and replace f by its linearization the current prediction. Concretely, if the learner predicts a, and observes label b,, we the surrogate loss (())) = Vi b,) a, where v denotes the gradient with respect to the first argument. By convexity of L, we have E(a,, b,) {(a b,) s V, b,) (a, a), so any regret guarantee for the linearized losses Eú implies the same regret guarantee for the original losses f.
Lemma 3.1 (Frank-Wold Wolfe for smooth loss functions). Given a finite set of features ((x,, yi, w/) where X, S for all loss function Ê that is convex and ß-smooth in the first parameter, class of functions H C [0, 1J² linear optimization oracle for H over S, and parameters 77. E > 0, Algorithm returns an e-approximate solution /t to the entropy regularzeeulrizzed (-ERM problem
X, dataset
arg min Rеf
1 wr((h(x))))) + Σ h(s) log(h() + 1)}
after O (SlleeWmmB+))) iterations, where Wmax max Exx-s /w/ is the maximum sum of absolute weights for any feature in S.
Overview of Algorithm 2: The objective requires (approximately) solving constrained smooth minimization problem min(G | E K3) where z e [0. 1)st a vector indexed by elements of S, and the function G [0, lj(t + R. is defined as
G(z) 17 Σ w (il + Σ 2g log(z, + 1),
where z, denotes the component of z corresponding s The set Ks denotes the convex hull of the set of vectors z(h) (h(s)) as h ranges over H. In this section, assume we are given linear optimization oracle for H over the set S, that is, an algorithm for selecting the h E H that minimizes ExEs c.h(s) for given coefficients (cylses- Algorithm 2 below uses such an oracle implement the Trank-Wolf method, also known as conditional gradient descent, for approximately minimizing the convex function G(z) over Ks. each iteration, the algorithm computes the gradient of the objective function G(z) with respect z, maps these components to weights c, for S. and invokes the linear optimization oracle to find an extreme point in the original function class that minimizes the corresponding linear function over S. After O (S (m-) iterations, it returns an e-approximate solution to the original problem.

---

Algorithm 2 Frank-Wolfe for Entropy Regularized (-ERM
1: procedure FRANK MAANEWLLE(((Ar.) yr, wi)) S)
2: Initialize h1 to an arbitrary function 7H
3: for r 1,2, . do
4: Let 2 be the vector (s))
5:
Compute gradient components c,
aGta) for each y E S:
0z,
C₁ 11
Σ Expms
a((h(s))):)
log(h,(s) + 1)+ h,(s) +
h,(s)
Oh
6: Call linear optimization oracle for H over S with weights (cybes to obtain Hi H
minimizing EEs Cyh(s).
7: Set Y/ 2+1
8: Update h+1 (1 - -iih, y,
9: return hr-1
Lemma 3.2 (Conditional Gradient Descent; (Hazan, 2023)). Let K c RR with bounded & diameter R.
Let f be a B-stooth function on K, then the sequence of points X₁ K computed by the conditional gradient descent algorithm satisfies
2BR²
[(x))
I+1
for all 2 where x" arg min xeK f(x).
The proof of Lemma 3.1 uses the formulation of the problem as minimizing a smooth convex function G(z) over bounded set Ks c R We then compute and bound the smoothness constant of G(z) and the diameter of Ks. Finally, we apply the standard convergence guarantce for the Frank-War Wolfe algorithm in Lemma 3.2 to obtain the stated convergence guarantee.
4 APPLICATION TO GAMES
Corollary 4.1. Let X be a domain space and D be a distribution over X. Let H,R c [0, 1] be classes of functions (assumed to be closed under convex combinations) and [0. 1] x [0, 1] - R be a convex-concave payoff function that is L.-Lipschitz its first parameter. Consider the saddle-point optimization problem
min max Bx-Dol(((())) beH reR
Given samples from D and access to best-response oracles for Hf and R. our online learning algorithm can be used to find an (am)-pprrxiimat saddle point solution (h",r") in polynomial time in and the complexities of H and R. The approximation guarantee is e(m) rad,.. ( + OlI Olog m/ /m), where F (f f(x) u(h(x), h H,r R). Note that rad,,.F) necessary for uniform convergence of the payoff matrix.
is
To prove Corollary 4.1, feed the samples from D sequentially into our hybrid learner. For each timestep f, we choose r, to be the best response function to the h, the algorithm outputs. We use the same samples to compute the best response function r, argmax, Σ (x), r(x,)) and this will be close to the true best response due to uniform convergence. Finally, using standard minimax analysis, argue in Appendix C that the process converges an approximate equilibrum.
10

---

REFERENCES
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: risk bounds and
structural results. J. Mach. Learn. Res., 36mull)4463-482, March 2003, ISSN 1532-4435. 5
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pp. 1716-1786. PMLR, 2022. 2,
Adam Block, Alexander Rakhlin, and Abhishek Shetty. On the performance empirical risk minimization with smoothed data. arXiv preprint Skti::2402.14987, 2024. 5
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differen- tially private learning. Advances in Neural Information Processing Systems, 33:9203- 9215, 2020.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver- saries. Journal of the ACM, 71(3):1-34, 2024. 2,
Elad Hazan. Introduction to online convex optimization, 2023. URL U.RL.tttps//arxiv.orr//// 1909. 05207. 10
Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '1. pp. 128-141, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. doi: 10.1145/2895518 28897533. 2897536.
URL https://doi org/10. 10. 1145/2899711.
Lunjia Hu and Charlotte Peale. Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes. In Yael Tauman Kalai (ed.), 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPPcss) pp. 72:1 72:1-72:30, Dagstuhl, Germany, 2023. Schloss Dagstuhl Leibniz-7entrum für Informatik. ISBN 978-3-95977-266-1. doi: 10.4230/LIPIss.ITCS 2023.72 72. URL https::////rte http//dropp..oo/////// dagstuhl. 1011443331/2222 LTI.III..S............. 2023.
de/entities//oooe
Alessandro Lazaric and Rémi Munos. Hybrid stochastic-adversarial on-line learning. In COLT 2009 22nd Conference Learning Theory, Montreal, Canada, jun 2009. (inria-00392524) 2,
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285-318, 1988.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012. ISBN 026201825X. 2, 5,
Francesco Orabona. modern introduction online learning, 2023. URL URL https:/:://r abs/1912. 13213. 13, 15, 17
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011. 2, 4, 19, 20
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1):111-13,, February 2015. ISSN 1432-2064. doi: 10. 10.10077500440:0133005555555 URL https://doi. org/ 10. 10.0000//000400 013 0545-5. 20
Karthik Sridharan. Lecture notes on fat-shattering dimension, supervised learnability, 2010. URL https://www.. wttp:/wwwww......cccco.o
cornell......oooo /ett://corrreee////////////////e pdf. 18
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojeiech Szpankowski. Expected worst regret via stochastic sequential covering. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL /tttp:://ppeereieeee http://paarreeeeeeeeeoooorrrrrta wttpee/e....eeoommiiiiissssssaao 2,
11

---

Changlong Wu, Jin Sima, and Wojeiech Szpankowski. Oracle-efficient hybrid online learning with unknown distribution. In Shipra Agrawal and Aaron Roth (eds.). Proceedings of Thirty Seventh Conference Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 4992-5018. PMLR, 30 Jun-03 Jul 2024. URL attps://proceedings mlr. www.mmrr...sss.. pae...peesss/// wu24a html. 3,55
12


Reviews:
[{"review_id": "F0bZJTIxU2", "reviewer": "Reviewer_rpou", "summary": "The paper studies hybrid online learning which is an intermediate set up between online and statistical learner where the covariates are chosen in an iid manner while the labels are potentially chosen adversarially. In this setting, statistically it is known that a $sqrt{dT}$ regret is achievable where $d$ is the VC dimension of class with respect to which the learner is competing and $T$ is the horizon (the VC dimension dependence is considered \"good\" since it beats the typical \"Littlestone\" dimension dependence when the covariates are also worst case). Unfortunately, this is not achieved just by running empirical risk minimization on the past data. This motivates the question considered in the paper, which asks whether an algorithm that uses empirical risk minimization as an oracle (perhaps motivated by the success of ERM in practice) can achieve the same regret. The paper achieves this goal with the caveat that the VC dimension of the hypothesis class is replaced by the VC dimension of the loss class induced by the actions of the label generating process (referred to as the adversary) and the hypothesis class. The paper achieves this with an interesting Franke-Wolfe style algorithm which should be of general interest beyond hybrid online learning", "questions": "-> As mentioned above the appearence of the complexity measure is a bit arbitrary (and has the flavor of \"what makes the analysis work\"). it would at least help the reader to have a small section discussing the measure and evaluating it in interesting setting e.g. R = H. It helps being honest and saying that in the standard setting where R = {all functions} the bound achieved is trivial. \n\nSimilarly, it would be helpful to discuss why this is essential since previous algorithms don't seem to need uniform convergence on the extended class. For example, this could be by explicitly stating why the present algorithm needs this while the Wu et algorithm does not. I suspect it is due to the passing through FTRL in the analysis but it would be good to be explicit regarding whether this is an artifact of the analysis or inherent in the algorithm. \n\n-> The comparison to previous work mildly misrepresents previous work since smoothed online learning has also been studied without knowing the bases measure and as such strictly generalizes hybrid online learning. BRS24 further study this in the oracle efficient setting (ERM directly even) and show that for realizable case they get a sqrt{Td} bound. When the present resuklt is specialized to the realizable setting, the bound recovered is the same but the covariate distribution is more general there; this is a further reason why an extended discussion of the assumption would help since for me the most interesting/interpretable case of the present bound is when R = H which is already shown in previous work. In particular, it would be interesting to see if similar bound in terms of the complexity in the paper can be shown in teh unknown base measure smoothed setting where too it remain open to get a sqrt{dT} rate in the agnostic case (in fact any sublinear oracle efficient rate is open to the best of my knowledge)\n\n-> Minor: FW type algorithms have been studied before in the oracle efficiency line of work (but with different motivation) start with the work of kakade kalai and ligget and more recently garber. WOuld be interesting to have some discussion on this\n\n-> Minor: Though I am happy to recommend acceptance of this paper to ICLR (whose interest I think of as closer to \"modern machine learning\", I personally do not think it is a good fit and would encourage the authors to (have) consider(ed) a different such as COLT where the community would appreciate the contribution more. That said, ICLR is increasingly being considered as a Neurips-style general ML conference and I understand that the authors have potential \"real world\" constraints beyond the maximization of the  community engagement", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem considered in the paper (hybrid online learning) is a very interesting abstract of \"beyond worst case\" sequential decision making and appears (at least conceptually) as intermediate step in several sequential decision making and game theoretic problems. Further, the study of oracle efficiency is well motivated in these applications (\"best response\" for example) which further justifies the interestingness of the problem. Given that, the paper achieving the strong regret guarantees in this setting should be considered as a strong contribution. Further, though the algorithm presented uses \"standard ideas\" in the community, the application to the present problem overcomes several interesting challenges which should be of broader interest in the community", "weaknesses": "The main issue with the regret bound presented is the dependence on the nonstandard quantity, the rademacher/VC dimension of the composed loss class. This complexity makes it a bit hard to compare the result with previous works directly and (if I understand correctly) should be treated as incomparable (and not an improvement on) to all previous work in the area (see below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sMWhtoFZe2", "reviewer": "Reviewer_JWkH", "summary": "The paper studies hybrid online learning where features are i.i.d. from an unknown distribution $D$ but labels are chosen adversarially from a constrained class $\\mathcal R \\subset [0,1]^X$. Given a linear optimization oracle over the hypothesis class $\\mathcal{H} \\subset [0,1]^X$, the authors design an ERM-oracle-efficient algorithm and prove a high-probability regret bound. The construction includes on (i) an approximate FTRL scheme over the “projection” of $\\mathcal H$ onto seen samples, using a time-varying shifted entropy regularizer (to get strong convexity on the first $t-1$ coordinates), and (ii) a Frank–Wolfe reduction so the regularized ERM calls can be implemented with a linear optimization oracle. A uniform-convergence argument then upgrades in-expectation control to the realized-sample regret bound. The paper also gives an application to approximate equilibria in certain stochastic zero-sum games with separable structure (payoff $u(h(x),r(x))$).", "questions": "See Weakness section.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The considered problem is well-motivated and has real-world applications.\n- The designed algorithms are intuitive and easy to implement. The algorithm is also computationally efficient compared to previous works.", "weaknesses": "- One concern is about the construction of FTRL. Specifically, I am not sure the role of the entropy regularizer is under-motivated. In the main text, the “truncated” entropy $v\\mapsto \\sum_s v(s)\\log(v(s)+1)$ is chosen because $\\log(1+a)$ is uniformly strongly convex on $[0,1]$, giving strong convexity over the first $(t-1)$ coordinates at step $t$. But the paper does not explain why one could not use a simpler $\\ell_2$ regularizer or mirror maps that may yield cleaner constants or better boundedness. Since the algorithm ultimately calls a FW oracle (not projecting onto the simplex), the specific advantage of entropy beyond “we get strong convexity where we need it” is not spelled out. Is that because of the use of $\\ell_\\infty$ in the gradient side?\n- While the analysis looks reasonable in general, there is one place that I do not understand. Specifically, the proof of Lemma A.6 appears flawed. In Lemma A.6 and the following derivation (lines 796–805), this is replaced by $\\psi_t(v_t)-\\psi_{t+1}(v_{t+1})$ with no justification (should be $\\psi_t(v_{t+1})-\\psi_{t+1}(v_{t+1})$). Can the authors explain more about that.\n- The paper does not provide a problem-specific lower bound for its hybrid setting. As a result it is unclear whether the leading terms in the upper bound are minimax tight. Without a matching lower bound that captures the joint stochastic–adversarial nature and the oracle model, it is difficult to assess optimality or to justify the use of the particular regularizer and surrogate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zxeoGDANiJ", "reviewer": "Reviewer_KxDd", "summary": "This paper studies the problem of *hybrid online learning*, where the feature vectors are drawn i.i.d. from an unknown distribution, while the labels are chosen adversarially. It focuses on a structured setting in which the labels are generated by a function belonging to a restricted class. Without restrictions on the labeling functions, Wu et al. (2024) showed that an oracle-efficient online algorithm exists, though its regret bound exhibits a gap compared to the case where the data distribution is known. This paper shows that if the labeling functions are drawn from a class whose complexity is no bigger than that of the hypothesis class, one can achieve the minimax-optimal regret.\n\nThe main proof technique is based on constructing a *surrogate loss* using the previously observed samples and reducing the hybrid online learning problem to an instance of online convex optimization. The paper then introduces a *truncated entropy regularizer* and proves that applying FTRL with this regularizer yields a *pointwise* regret bound of $\\tilde{O}(\\sqrt{T})$. This pointwise guarantee is subsequently converted into a *high-probability* regret bound for the original hybrid learning problem via standard martingale concentration arguments. Finally, since vanilla FTRL requires convexity of the hypothesis class, the authors resolve this issue by employing a Frank–Wolfe–based oracle reduction.", "questions": "Can the OCO problem and its oracle-efficient solution be stated more generally? As far as I can see, the specific form of the loss does not matter, one only needs that each $\\ell_t$ depends only on the first $t-1$ coordinates of $v$ and is convex and Lipschitz with respect to the $\\ell_1$ norm.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I find the idea of reducing the hybrid online learning problem to an OCO problem quite interesting. This could inspire researchers to explore similar reductions for more complex hybrid settings, such as the smoothed adversary model.\n\n2. As far as I understand, the truncated entropy regularizer is novel and may have broader application scenarios beyond this particular setting.\n\n3. The authors demonstrated the usefulness of their constrained labeling-function formulation in the context of finding saddle points in minimax games, which I find convincing.", "weaknesses": "1. Although the paper provides a use case for the constrained labeling-function setting in games, it still feels somewhat restrictive, especially since the prior result by Wu et al. (2024) does not rely on such constraints. It would strengthen the paper if the authors could present additional examples where similar constraints arise naturally from structural properties of the problem.\n\n2. The paper claims that the obtained regret bound is “near-optimal.” I am not entirely sure how this should be interpreted. In particular, if the VC dimension of $R$ is unbounded, the bound becomes vacuous, even though we know that sublinear regret is still achievable in that case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gYH5yhJO6d", "reviewer": "Reviewer_SZPF", "summary": "This paper studies hybrid online learning where features are drawn i.i.d. from an unknown distribution, while labels are chosen by an adversary. Different from the fully adversarial case, the adversary is constrained to pick labels from a fixed function class, and the learner competes with a hypothesis class under a Lipschitz abd convex loss function. The main result of this paper is to propose an oracle-efficient algorithm with a high-probability regret guarantee. The proposed algorithm is built upon FTRL framework with the entropy regularizer, implemented via a Frank–Wolfe reduction that calls a linear‑optimization oracle over hypothesis class.", "questions": "- I am not sure whether imposing the Lipschitz assumption on loss function is common or not. Can authors justify this assumption?\n\n- The algorithm needs to have access of the loss function. I am curious what if the learner does not have the knowledge of the loss function, but only has bandit feedback (i.e., observe the loss of the chosen one).", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Prior work either attains optimal rates but is computationally intractable, or is oracle‑efficient but statistically suboptimal. This paper achieves near‑optimal rates and oracle efficiency by constraining the adversar, which could be an interesting middle ground.\n\n- Authors propose a FTRL-based algorithm with entropy regularizer, and theoratically show that the proposed algorithm achieves a statistically near-optimal up to the dependence on the adversary’s constraint set $\\mathcal{R}$.\n\n- Proposition 1.3 addresses uniform convergence when the functions $r_t$ are chosen adaptively yet independently of $x_t$. This result could be a good contribution of independent interest.\n\n- This paper is easy-to-follow and well-written. Though I am not quite familiar with the context, I appreciate detailed and clear explainations provided by authors.", "weaknesses": "- The tightness of the regret bound remains unclear to me, especially $T* rad_T(\\ell \\circ  \\mathcal{H} \\times \\mathcal{R})$.\n\n- The algorithm runs in $O(T^2)$ time per round and makes $O(T^2)$ calls to a linear optimization oracle, both of which seem to be pretty large.\n\n- In line 265, $\\log(a+1)$ is strongly concave on its domain rather than strongly convex. It should be that $a*log(a+1)$ is strongly convex.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)