Adaptive Oracle-Efficient Online Learning
Authors: Guanghui Wang
Zihao Hu
Vidya Muthukumar
Jacob Abernethy
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
oracle efficiency
adaptive online learning
small-loss bound

Abstract: The classical algorithms for online learning and decision-making have the benefit of achieving the optimal performance guarantees, but suffer from computational complexity limitations when implemented at scale. More recent sophisticated techniques, which we refer to as $\textit{oracle-efficient}$ methods, address this problem by dispatching to an $\textit{offline optimization oracle}$ that can search through an exponentially-large (or even infinite) space of decisions and select that which performed the best on any dataset. But despite the benefits of computational feasibility, most oracle-efficient algorithms exhibit one major limitation: while performing well in worst-case settings, they do not adapt well to friendly environments. In this paper we consider two such friendly scenarios, (a) "small-loss" problems and (b) IID data. We provide a new framework for designing follow-the-perturbed-leader algorithms that are oracle-efficient and adapt well to the small-loss environment, under a particular condition which we call $\textit{approximability}$ (which is spiritually related to sufficient conditions provided in (Dudík et al., 2020)). We identify a series of real-world settings, including online auctions and transductive online classification, for which approximability holds. We also extend the algorithm to an IID data setting and establish a "best-of-both-worlds" bound in the oracle-efficient setting. 

Adaptive Oracle-Effcieet Online Learning
Guanghui Wang', Zihao Hu', Vidya Muthukumar Jacob Jacob Abernethy?
College Computing
School of Electrical and Computer Engincering
School of Industrial and Systems Engincering"
Georgia Institute of Technology
Atlanta, GA 30339
(gwang369, zihaohu, vmuthukumars, prof) waareffegatthhhe..
Abstract
The classical algorithms for online learning and decision-making have the ben- efit of achieving the optimal performance guarantees, but suffer from computa- tional complexity limitations when implemented at scale. More recent sophisti- cated techniques, which we refer to oracle-efficient methods, address this prob- lem by dispatching to an offtine optimization oracle that can search through an exponentially-large (or even infinite) space decisions and select that which per- formed the best on any dataset. But despite the benefits of computational feasi- bility, oracle-efficient algorithms exhibit one major limitation: while performing well in worst-case settings, they do not adapt well to friendly environments. In this paper we consider two such friendly scenarios, (a) "small-loss" problems and (b) IID data. We provide new framework for designing heflowtthe-erturbedlleee algorithms that are oracle-efficient and adapt well to the small-loss environment, under particular condition which call approximability (which is spiritually lated to sufficient conditions provided in (Dmdik et all 2020). We identify a series of real-world settings, including online auctions and transductive online classifica- tion, for which approximability holds. We also extend the algorithm to an IID data setting and establish "best-of-both sot--off-ohh-wololrc worlds" bound in the oracle-efficint setting.
Introduction
Online learning is fundamental paradigm for modeling sequential decision making problems (Cesa Branchi & Lugosi, MOUG ShavirrS 2m HAZAn LDTG). Online learning is usually formulated as a zero-sum game between a learner and an adversary.
each round t 1..... T, the learner first picks an action x, from (finite) set X' (a(11) ....,, ....,,((K)) (K)) with cardinality equal to K. In E V. As a consequence, the learner observes
the meantime, an adversary reveals its action yt. and suffers loss f(r,, 3t), where f X' y + [0, 1]. The goal is to minimize the regret, which is defined as the difference between the cumulative loss of the learner Σt= f(z,. and the cumulative loss of the best action in hindsight L mingex ΣT, f(x yt).
wide variety of algorithms have been proposed for the goal of minimizing worst-case regret (without any consideration of computational complexity per iteration); see (Cesa-Bianch & Lus gost, 2006; Shalev-Shwarzz ROLT; Hazan, 2016) for representative surveys of this literature. These algorithms all obtain a worst-case regret bound of the order O K), which is known to be minimax-optimal (Cesa-Bianchi & Lugosi, 2008). Over the last two decades, sophisticated adaptive algorithms have been designed that additionally enjoy pepeeenddpenddet performance guarantees, which can automatically lead to better results in friendly environments, One of the most important example for this kind of guarantees is the so-called "small-loss" bound (Hutter & Poland 20TS
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Such bound depends on the best cumula- tive loss in hindsight (i.e. Li) instead of the total number of rounds (T"). Thus, this bound is much tighter than the worst-case bound, especially when the best decision performs well in the sense of incurring a very small loss. Another example is the pest-oo-boothwoorkee bound (Van_Ervee etall emE), which results in an even tighter regret bound for independent and identically distributed (IID) loss functions.
Cesa Bianchi & Lugosi, PIOC Vnn Erven ef all
201E
However, all of these algorithms applied out-of-the-box suffer a linear dependence on the number of decisions K. This prohibitively expensive, especially in problems such as network routing (Awers buch & Klemberg POiS) and combinatorial market design (Cesa-Phanch Rranch et all 20E),, where the cardinality of the decision set grows exponentially with the natural expression of the problem. Sev-
eral efficient algorithms do exist, even for uncountably infinite decision sets, when the loss functions
have certain special structure (such as linearity (Kalai & Vempala, 20TTS or convexity (Zinkevreh.
) )) However, such structure is often absent in the above applications of interests.
Notice that the efficiency of the above specialized methods is usually made possible by assuming that the corresponding offline optimization problem (i.e., minimizing the (averaged) loss) can be solved efficiently. This observation motivates the oracle-effccient online learning problem (Hazan & Koren EOTG). In this setting, the learner has access to a black-box offline oracle, which, given a real-weighted dataset S = ((w(1) (og())yy)))) )
can efficiently return the solution to the following
problem:
argmin xE
Σ
flxf (1).
(1)
The goal is to design oracle-efficient algorithms which can query the offline-oracle ((1) times each round. Concrete examples of such oracle include algorithms for empirical risk minimization
(Brshop 2004), data-driven market design (Nisan & Ronen 21X12), and dynamic programming (Bene
Sekas 1019
As pointed out by Hazan & Koren (20TH), the design of oracle-efficient algorithms extremely challenging and such algorithm does not exist in the worst case. Nevertheless, recent work (Daskalakis & Syrgkamis 2OIG Syrgkamis et all 2UTE; Dudik all 2020) has introduced a scries of algorithms which are oracle-efficient when certain sufficient conditions are met. Among them, the fowrliiied-flloww-tte wwwwtthh-petuureeddeeeee
crall (IZ(), which is variant of the classical thee-perturbed-eeee leader algorithm (GFTPL, Dudis (FTPL) algorithm (Kala & Vempala M0105). Similar to FTPL, GFTPL perturbs the cumulative loss of each decision by adding a random variable, and chooses the decision with the smallest perturbed loss as T2. However, the vanilla FTPL perturbs each decision independently. which requires to generate K independent random variables in total. Moreover, the oracle in (II) can not be applied here since it cannot handle the perturbation term. To address these limitations, GFTPL only generates a noise vector of low dimension (in particular, much smaller dimension than the size of the decision set) in the beginning, and constructs K dependent perturbations based on the multiplication between the noise vector and perturbation translation matrix (PTM). Therefore, the PTM critically ensures that the computational complexity for the noise generation itself is largely reduced. Furthermore, oracle- efficiency can be achieved by setting the elements in the PTM as carefully designed synthetic losses. Dudik et all (212 show that a worst-case optimal regret bound can be obtained when the PTM is admissible, i.e., every two rows are substantially distinct. This serves as a sufficient condition for achieving oracle-efficiency.
state-of-the--at method is the
While these results form solid foundation for general worst-case oracle-efficient online learning, it remains unclear whether problem-dependent or data-adaptive bounds are achievable in conjunction with ofacle-efficiency. In other words, the design of generally applicable oracle-efficient and adaptive online learning algorithm has remained open. In this paper, we provide an affirmative answer to this problem, and make the following contributions.
We propose variant of the GFTPL algorithm (Dudik ata (IZI), and derive a new suf- ficient condition for ensuring oracle-efficiency while achieving the small-loss bound. Our key observation is that while the admissibility condition of the PTM in GFTPL success- fully stabilizes the algorithm (by ensuring that P(z, * x=+1] is small), it does not always enable adaptation. We address this challenge via new condition for PTM, called approx- imability. This condition ensures stronger stability measure, i.c., the ratio of P[z, z(1]

---

and P(z = 2011 is upper-bounded by a universal constant for any i E. [K], which is critical for proving the small-loss bound. In summary, we obtain the small-loss bound by equipping GFTPL. with an approximable PTM, data-dependent step-size and Laplace distribution for the perturbation noise. As a result of these changes, our analysis path dif- fers significantly from that of Dudik at (2022). Our new condition of approximability is simple and interpretable, and can be easily verified for an arbitrary PTM. It shares both sim- ilarities and differences from the admissibility condition proposed in Dudik eLal (2I2)) We demonstrate this through several examples where one the sufficient conditions holds, but not the other.
We identify a series of real-world applications for which PTMs: (a) a series of online auctions problems (Dndiik et all 2020); (b) problems with small adversary action space [ (Daskalakis & Syrgkanis P0TG); and (c) transductive online classification (Svrgkanis et al, 2016 et MMZO) This is the first-time that
construct approximable
the small-loss bound is obtained in all of these applications. To achieve this, we introduce novel PTMs and analysis for showing the approximabilityy condition on these PTMs.
We achieve the "best-of- bottt-orthwwsss bound, which enjoys even tighter results when the data is IID or the number of leader changes is small. The main idea is combine our pro- posed algorithm with vanilla FTL leveraging ideas from a meta-algorithm called FlipFlop introduced in Van Erven al (2013).
2
Related Work
Our work contributes to two bodies of work: oracle-efficiet online learning and adaptive online learning. In this section, we briefly review the related work in these areas.
2.1 Oracle-efficient online learning
For oracle-efficient online learning, the pioneering work of Hazan & Koren (201G) points out that oracle-efficient methods do not exist when dealing with general hostile adversaries, which implies that additional assumptions on the problem structure have to be made. Daskalakis & Syrgkamss (2016) consider the setting in which the cardinality of the adversary's s action set y is finite and small, and propose to add a series of "fake" losses to the learning history based on random samples from y. They prove that for this setting an ((D)VT) regret bound can be obtained. Syrgkams et all (2016) study the contextual combinatorial online learning problem, where each action is associated with a binary vector. They make the assumption that the loss function set contains all linear functions as sub-class. The approach in Syrgkanis all (20G) constructs a set of synthetic losses for perturbation based on randomly-seledd
contexts, and achieves worst-case optimal bounds when all the contextual information can be obtained beforehand, or when there exists small set of contexts that can tell each decision apart. Dudik al (2020) is the first work to focus on the general non- contextual setting, and propose the generalized FTPL algorithm. This algorithm generates a small number of random variables at the beginning, and then perturbs the learning history via the innter product between the PTM matrix and the random variables. The algorithm can be implemented efficiently by setting the entries of the PTM as carefully designed loss values. NEzzdeh et all (2022T) consider a more complicated combinatorial setting where the offline problem is NP-hard, but robust approximation oracle exists. For this case, they propose an online algorithm based on a multiplicative approximation oracle, and prove that it has low approximate regret, which is a measure weaker than regret, since it only compares with a fraction of the cumulative loss of the best decision in hindsight. Note that none of the aforementioned methods can be easily shown to adapt to friendly structure in data. Recently, several concurrent works (Block ctall 0022: Haghtalab et all 20223) investigate how to obtain tighter bounds oracle-effccienlly in the sioothed-annalsee setting where the distribution of data is close to the uniform distribution (Rakhlin el all 201: Haghtaat Small 2)2))). The main focus is to adapt to the VC dimension of the hypothesis class, rather than improve the dependence on the number of rounds T.
In this paper, we mainly focus on the so-called the learning with expert advice setting CesaaMaann
& Lugosi, 2013), where the action set is discrete, and the loss can be highly non-convex. On the other hand, efficient algorithms can be obtained even for continuous action sets when the loss functions
have certain properties, such as lincarity (Kalar & Vempala B0TS. Hutter & Poland, ETTS Awerbuch

---

& Kleinberg P0IS), convexity (Zinkeviei, UCIE Hizan et all
or submodularity (aazan &
Finally, we note that, in this paper we mainly focus on the full-information setting.
where the learner can observe the whole loss function after the action is submitted. Oracle-efficient
online learning has also been widely studied the contextual bandit setting (Langford Zhang.
2010: Dadrk et all 201 Aaarwal et al, 201E: Eoster et al, 20TX Foster & Rakhim, 2020). The
nature the oracle-efficient guarantees for the contextual bandit problem is much weaker compared to full-information online learning: positive results either assume stochastic probability model on
the responses given covariates (e.g. Foster aLal (2018); Foster & Rakhlm (2020) or significantly
stronger oracles than Eq. (II) (e.g. Agarwal et al (2014)
2.2 Adaptive online learning
In this paper, we focus on designing oracle-efficient algorithms with problem-depender regret guar- antees. Note that this kind of bound can be achieved by many inefficient algorithms in general, such
as Hedge and its variants (Cea--Biande & Lugosi, 2006; De Room et al. 201 Luo & Schapire 20TS), follow-the- www-ttetturbed-leadeeeeee
tollow-the- regularized-leader (Drahonal 20T9). Small-loss bounds can also be obtained efficiently when the
(Kala VempaR 2003: Van Erven all MUE
loss functions are simply linear (Entter Poland, 2OTS; Syrgkans an. 2016). On the other hand, in online convex optimization, small-loss bounds can be obtained when the loss functions are ad- ditionally smooth (Srehro all 2010; Drabona all, 20Tz; Wang et all (02(). However, these algorithms heavily rely on the special structure of the loss functions. In this paper, we take the first step extend these methods to support the more complicated (generally non-convex) problems which appear in real-world applications.
Apart from the small-loss, there exist other types of problem-dependent bounds, such second- order bound Cesa--Ranehretan 200S: Galland alll 2014), quantile bound (Chauddun alal 2009
Konlen Frven M0IS), parameter-free bound (Luo Schapire, 2013 Cutkosky Orabona 2018). Moreover, advanced adaptive results can also be obtained by minimizing more advanced performances measures other than regret, such adaptive regret (Hazan & Seshadhri, 2TTι Zhang
all MIT9), or dynamic regret (Zhang et al, 2018; Zhao al M02D). How to obtain these more refined theoretical guarantees in the oralle-efficient setting remains an interesting open problem.
GFTPL with Small-Loss Bound
In this section, ignore computational complexity for the moment and provide FTPL- type algorithm that enjoys the small-loss bound. We then show that the proposed algorithm can be implemented efficiently by the offline oracle in Section H. Before diving into the details, first briefly recall the definition of online learning and regret.
Preliminaries. The online decision problem we consider can be described as follows. In each round f, learner picks action I; E X' [z(1)) ,..., [.3]]. After observing the adversary's decision E y, the learner suffers a loss f'(xe, Me) where the loss function f X x y + [o, 1] is known to the learner and adversary. The regret of online learning algorithm A is defined as
R = E f(re Mi) -
where L min EJ (x( my) is the cumulative loss of the best action in hindsight, and the kE
expectation is taken only with respect to the potentially randomized strategy of the learner.
Our proposed algorithm follows the framework of GFTPL (Ondiket.n all 20za). We first briefty introduce to the intuition behind this method. Specifically, in each round t, GFTPL picks xe by solving the following optimization problem:
It = argmin E/=1 f(x((), + (T((),
kE[K]
where or is N-dimensional noise vector (N & K) generated from uniform distribution, and (k) the k-th row of matrix I' E [0, 1] which referred as the perturbation translation matrix (PTM). Compared to vanilla FTPL, which generates K random variables (one for each expert),

---

GFTPL only generates N random variables, where N is much smaller than K. Each expert is perturbed by a different linear combination of these random variables based on the PTM I. The results of Dudik at (2022) rely on the following assumption on T.
Definition 1. (d-admissibility (Dudik al, (izml) Let [0, [0,1]KXN be a matrix, and denote [(k as the k-th row of T, and I ((k.,) the i-th element of 1 Then, I' is d-admissible (a) Vk, k E [K],
Bi E [N] such that ((k.a) + T(K and (b) vi E [N]. k, k' E [K], such that ((k,5) o D A), then
[[(kk.) 1(k | 8.
The 5-admissibilityy guarantees that every two rows in I' are significantly distinct. As pointed out by Dudik at (202), this is the essential property required by GFTPL, and is used to stabilize the algorithm in the analysis, i.e., ensuring that P(ara & 2 is small. However, the adaptive analysis of inefficient FTPL (Hufter & Poland, 2005)) (i.e. using a noise vector of dimension equal to the size of the decision set) reveals that this type of stability is insufficient. Instead, one needs to control the following 1T. and Vi E [K],
P(z, = [+)
(2)
P P[ = x(]]
the ratio of the probability of picking the i-th decision in two consecutive rounds. We note that 5-admissibility is not sufficient to ensure this quantity is bounded, as we establish in the following
counter-example lemma. (See Appendix A for proof).
Lemma 1. There is an instance of a 8-admissible r, and a sequence {ye : ..2,..... such that if we run GFTPL we can have Pla.=x(0]
0o for some i E [K] and some t >> 0.
P|z-1=2001
To address this problem, we propose new property for r. Define By = E RN: ||s|| S 7) as the bballl of size 7. Definition 2. (>-approximability) Let Tetee E [0, 1|KKN, We say that I is y-approximable if
Ak E [k],ye By E [K]
(r(#) -
p(),ss ( 2 fl f(x .)) f(x(() .))
may not be immediately obvious how we arrived at this condition, so let us provide some intuition. The goal of perturbation methods in sequential decision problems, going back to the early work of Hampan (1157), is to ensure that the algorithm is "hedging" across all available alternative decisions. A newly observed data point y may make expert j suddenly look more attractive than expert lt as we have now introduced new gap f(x(*), -)) y) in their measured loss values. With this in mind, we say that a "good" (i.e. approximable) choice for the PTM, if this gap can be overcome (hedged) by some small (i.e. likely) perturbation s, so that (T()) r()), .) makes up the difference. The inequality makes this property flexible and much easier to satisfy in real- wooldd applications: we only need the gap approximation from above. Later, we will show that a-approximability guarantees the required stability measure in (L), and thus is critical for the small-loss bound.
We want to emphasize two final points. First, the 7-approximability condition purely for analysis purposes and we don't need compute the quantity s in response to y and k. Second, much of the computational and
challenges rest heavily on the careful design of T. The PTM allows the algorithm to perform the appropriate hedging across an exponentially-sizer set of K experts with only N < K dimensions of perturbation. As we demonstrate in the following example, we can always construct a a-approximable I, with N = O K), but at the expense of computational efficiency. The proposed I will not generally be compatible with the given oracle, in the sense that the optimization problem underlying GFTPL cannot be written in the form of Eq. (M). In the next section, we will show how to address this problem via another condition on called implementablity
Simple Example For any online learning problem we may construct as follows. Let N == [loge K7. and define the kith row (*) to be the binary representation of the index k. with +1/ 1 values instead of 0/1. We claim that this I is a-approximable, for [log, K7. We can satisfy the condition of Definition D by setting s ((k) It is easy to see that for any j # k we have (T()) r(), s) = (T()) - -rú), r()) 2 2 2 f(x("),)) y) f(x(1), y). where the last inequality
holds because (f((((), v) < for any i E [K].
5

---

Algorithm Generalized follow-thh-peerttbeeddeee with small-loss bound
1: Init: E [0,1] XN
2: Draw IID vector a = " ~ Lapp(1)); that is, p(a()) = exp((-la
3: for t = ,,..., T, do
4: Set Ore a where 7
parameter computed online
Σ f( .y)) (T(M)
5: Choose 21 c argmin
kE|K] j=1
6: Observe y/
7: end for
Comparison beteeen 7-approximabilty (this paper) and ó-admissibility (Dndikk et all 2020) We note that, although 7-approximability leads to much tighter bound, it is not stronger than 5-admissibility. Instead, they are incomparable conditions. Specifically:
In Section I we demonstrate that when I' is binary, admissibility directly leads to approx- imability, As shown by Dndik et al (2020), a binary and admissible I' exists various online auctions problems, including VCG with bidder-specific reserves (Roughgarden & Wang 20T9),, envy-free item pricing (Guruswami et all (CUS), online welfare maximiza- tion in multi-unit auction (DobzınskL& & Nisan, 201C), and simultancous second-price auc- tions (Daskalakıs & Syrgkanis, 2016). We can directly obtain an approximable I' in such cases.
On the other hand, in problems such as level auction Oudik-ctal 2020), one can construct both admissible and approximable although in completely different ways; we discuss the construction in depth in Section 1
In section
we show that, when the adversary's 's action space is small, we can always construct 7-approximable r, while 6-admissible I'des not exist in general.
In Appendix
A AW we show that in some cases 8-admissible I can be obtained while
7-approximability cannot be achieved.
Equipped with the 7-approximable PTM, we develop generalized followetie-pertuubeedaaddd al- gorithm with the Laplace distribution for the noise a and time-varying step size, which is summa- rized in Algorithm M This choice of Laplace distribution is significantly different from the choice of uniform distribution originally used by GTFPL: it turns out that a continuous distribution is required to satisfy Eq. (L) and thereby the small-loss bound. Note that here we ignored the time complex- ity and only focus on the regret. We will specify how to construct I the next section. For the proposed algorithm, we successfully obtain the following stronger stability property.
Lemma 2. Assume I is 7-approximable. Let x'c argmin Σjn (k) yj) (T(K), aa))
Then in each round t, have Vi E [K],
Pla.
(0) exp (YTH) P(r; -
Note that we replace the term 1 in (L) with 2'z, time-varying step-size is used. Based on Lemma D we obtain the regret bound of Algorithm M as follows.
Theorem 1. Assume I' i appproxximable, and let Lý- = minke(k] ET (x((k), 85). Algorithm
with the min
[i= for any > 0, achieves the following regret bound:
7
4 max2mx(2l K, VNNKK +27 c (ct
!))
Rr <
V L4 +1
(3)
+ +8y 1n
(-V + 27² +4V2 K, 1
Note that the Laplace distribution is not the unique choice to get the small-loss bound. In Appendix we prove that the e, perturbation p(a) x exp (E. ()p) indeed works for any p 2 1.

---

Algorithm 2 Oracle-based GFTPL for the reward feedback
1: Input: Data set 5.. [V], that implement matrix I'E E [0, 1|KXN, 1 = min(, 13.
2: Draw IID vector a [a!1) ,..., [..] Lap(1)^
3: for = 1,...,?' do
(
4: Choose 24 + argmin kE[K] j=1
fa((M) Myy
Σ
w
TJt
(u..))S.
5: Observe Vt
6: Compute T = min E === ((x!1)) U1) by using the oracle kE(K]
7: Set T4+1 min
77' VIŞ+1
8:
end for
The proof of Lemma and Theorem @ can be found in Appendix A By setting c ④(1), Theorem implics that our proposed algorithm achieves (maxx y K, v N In K v LT) regret bound.
Comparison to GFTPL (Dudik et all 2020)) The original GFTPL algorithm has an O VT)
V
regret bound. For the dependence T, (VLLF) bound reduces to O(VT) in the worst-case, and automatically becomes tighter when L7 is small. On the other hand, for the dependence on other terms, note that both NN and max(y, v In K, vNN In K are lower bounded by Slnn K), and their exact relationship depends on the specific problem. In Section E. we show that for many auction applications, the two terms are the same order. Moreover, in cases such as when [}] is small,
Algorithm I with an appropriate c leads to O (V Li max/In K, VD Kn
regret bound, while 2022 can blow up since be infinitely small.
the regret bound of GFTPL Dudik
Oracle-efficiency and Applications
In this section, we discuss how to run Algorithm W in an oracle-efficient way. Following Dudik et (2022), we introduce the following definition.
Definition (Implementability). A matrix I' is implementable with complexity M each [N] there exists dataset Sy. with [Sy| S M, such that Ak: k E [K],
(k.)) - TK
Σ w (f(a (0)))(x(()))) (w.y)SS)
f(x(()
Based on Definition B, easy to get the following theorem, which similar Theorem 2.10 of Dudik at (2020).
Theorem 2. If I is implementable, then Algorithm M is oracle-efficient and has a per-round com- plexity O(T + NM).
In the following sub-sections, we discuss how to construct approximable and implementable I ma- trices in different applications.
4.1 Applications in online auctions
In this part, we apply Algorithm M online auction problems, which is the main focus of Dudi3 srall (2022). To deal with this sort of problems, we first transform Algorithm M to online learning with rewards setting, i.e., in each round after choosing F4, instead of suffering loss, the learner obtains reward r(æ,, yt) E [0. 1]. For this case, it is straightforward to see that running Algorithm on a surrogate loss f(, y) = 1 - r(x, :) directly leads to the small-loss bound. To proceed, we slightly change this procedure and obtain Algorithm A The main difference is that, we implement I with the reward function r(z, y), instead of the surrogate loss f(x, y). This makes the construction of I' much casier. We have the following regret bound for Algorithm A
7

---

Corollary 1. Let f(x, v) 1 r(z, y). Assume I' is "-aaproximable w.t.. f(z, y) and imple- mentable with function r(z, v). regret bound:
Then Algorithm is oracle-efficient and achieves the following
T
RT = G7 -
Σ
rla (( ui) =0 (max finnx(7;,u 17,
VN VNIK) VT
where Ci maX Et= r(x(11 We) is the cumulative reward of the best expert.
Next, we discuss how to construct the PTM in several auction problems.
Auctions with binary and admissible P. As shown by Dndik el all (EIZE), in many online auc- tion problems, such as the Vickrey-Clarkes-Grrvees (VCG) mechanism with bidder-specific reserves (Roughgarden & Wang, 2019), envy-free item pricing (Gurnswam aill RIOS), online welfare max- imization in multi-unit auction (Dobzınski & Nisan, 2OTT) and simultaneous second-price auctions (Daskalakis & Syrgkanis, (0TG), there exists a binary PTM which is 1-admissible and implementable with N rows where N < K. For these cases, we have the following lemma. The proof is deferred to Appendix B
Lemma 3. Ler Tere E [0, [],1]Kxx be binary matrix and 1-admissible, then I' is N approxxiiable.
Note that, I is binary and I-admissible, so every two rows of Gamma differ by at least one element. This means that I must, at the very least, include S2(In K) columns to encode each row. Combining this fact with Lemma B and Corollary M. we can obtain an D(N/T= L,7) bound for all of the above problems, Compared to the original GFTPL algorithm, our condition leads to a similar dependence on N and tighter dependence on T due to the improved small-loss bound. More details about the aforementioned auction problems and corresponding regret bounds can be found in Appendix
Level auction The class of level auctions was first introduced by Morgenstern Roughgarden (2015), and optimizing over this class enables a (1 e) multiplicative approximation with respect Myerson's optimal auction when the distribution of each bidder's valuation independent from others. For this problem, the PTM in Dudik et all (2020) is not easily to be shown approximable. To address this problem, we propose novel way of constructing an approximable and implementable PTM. The key idea is to utilize coordinate-wise threhold function to implement I. Note that this kind of function can not directly obtained. Instead, we create an augmented problem with surrogate loss to deal with this issue. For level auction with single-item, n-bidders, s-level and m- discretization level, our method enjoys an Onsmm / - LT) regret bound, which is tighter than the Onmm² VT) (note that S m) of the original GFTPL both its dependence on the number of rounds T and auction parameters n, m. Due to page limitations, we postpone the detailed problem description and proof to Appendix B.L
4.2 Other applications
Oracle learning and finite parameter space In many real-world applications, such as security game (Balcan.cial 2015) and online bidding with finite threshold vectors (Daskalakıs & Svrekanis 20T6), the decision set X' is extremely large, while the adversary's action set [D] is finite and small. For these problems, we can construct an implementable PTM based the following lemma, whose proof can be found in Appendix BE
Lemma 4. Consider the setting with Y d (d < K), then there exists 1-approximable and implementable I' with columns and complexity 1.
max(In K, Vdlnn K we observe that algorithm achieves small-loss bound the order of O(y max(In K, Vdln K) /T7) On the other hand, because of the continuity of the loss functions in this setting, a 5-admissible PTM in general does not exist (as 8 may approach 0). Therefore, our proposed condition not only leads to a tighter bound, but can also solve problems that the original GFTPL (Dudik all 2020) can not handle.
Combining Lemma B and Theorem M and configuring
8

---

Transductive online classification Finally, we consider the transductive online classification prob- lem (Syrgkanis etl. anl 20TG; Drdi 20ZL). In this setting, the decision set X' consists of K binary classifiers. In each round i, firstly the adversary picks a feature vector wa E W, where [W] = m. Then, the learner chooses classifier (+))) from X. After that, the adversary reveals the label y/ E (0. ,, and the learner suffers loss [Tz, (wt; Me)) (1x) * vel- We assume the problem is transductive, i.e., the learner has access to the adversary's ' set of vectors at the beginning. For this setting, we achieve the following results (the proof is in Appendix B
Lemma 5. Consider transductive online classification with [W] = m. Then there exists a 1- approximable and implementable PTM with m columns and complexity 1. Moreover, Algorithm 0
with such PTM and appropriately chosen parameters achieves Oly max(In K, Vmnk (VT)) regret.
Negative implementability In the this paper we assume that the offline oracle can solve the min- imization problem in (I) given any real-weights. In some cases, the oracle can only accept positive weights. This problem can be solved by constructing negative implementable PTM (Dudik et all 2020). In most of the cases discussed above, negative implementable and approximable PTM exist. This is formally shown in Appendix B.G.
5 Best-of-Roth-Worldd Bound: Adapting to IID data
In this section, we switch our focus adapting between adversarial and stochastic data. While the GFTPL algorithm enjoys an D regret bound on adversarial data, it is possible obtain much better rates on stochastic data. For example, by setting all step sizes n) as co, Algorithm M reduces to the classical FTL algorithm, which suffers linear regret in the adversarial setting but enjoys much tighter bounds when the data is IID or number of leader changes is small. To be more specific, we introduce the following regret bound for FTL.
Lemma 6 (Lemma 9, De Room et all (2111) Let xTTLL argmin Es=1 f(x!(), us)) be the output of the FTL algorithm at round I, CT the set of rounds where the leader changes, and 8 = [ar ((rr",,))) (b)) - (Lg Tūī-1) the "mixability gap" + at round Then for any T 2 1, the regret of FTL.
is bounded by RFT < EiECr 5, S (Crl.
Note that since f E [0, 1] and T, T E [0. [(, 3e)], we know 8, E [0, 1]. For the i.i.d case, if the mean loss of the best expert is smaller than that of other experts by constant, then due to the law of large numbers, the number of leader changes would be small, which results in a constant regret bound (De Rooi et an, 2014).
Our goal is to obtain a ofest-of-bothhwwe worldds bound, which can ensure the small-loss bound in general, while automatically leading to tighter bounds for IID data like FTL. We will now design an algorithm that achieves such a bound by adaptively choosing between GFTPL and FTL depending on which algorithm appears to be achieving lower regret. The essence of this idea was first introduced in the FlipFlop algorithm (De Room et all ZUE)), who showed best-of-both-worlde inefficient case. Our contribution in this section is to adapt this idea to the oracle-efficient setting. Denote Li GFTFLL as the attainable regret bound (as in Theorem M) for running Algorithm alone and
bounds in the
UFTL = Eiecy &, be that of FTL. In the following, we develop a new algorithm and prove that is optimal in both worlds, that is, its regret is on the order of Ommin Omiin(U:FTL (EFTH,
(GFTPL)).
The proposed algorithm, named oracle-efficient flipflop (OFF) algorithm, is summarized in Algo- rithm B The core idea is to switch between FTL and GFTPL (Algorthm M)) based on the compar- ison of the estimated regret. We optimistically start from FTL. In each round L, we firstly pick x, based on the current algorithm Alg,, and then obtain the adversary's 's action ye (line 2). Next, we compute the estimated bounds of regret of both algorithms until round (line 3). Specifically, let IFT {ili E [t], Alg, = F and ZOFTPL {ile E [t] Alg, = GFTPL} be the set of rounds up to t in which we run FTL and GFTPL. Then, the estimated regret of FTL in IFTL is given by
'Here, we use the special definition of the mixability gap for the FTL algorithm. The details can be found in the second paragraph, page 1286 of De Room all (2ITE

---

Algorithm 3 Oracle-efficient Flipflop (OFF)
Initialization: Alg, FTL
for I..... do
2: Get 24 by Alg,, observe
3: Compute ÜFTL and ÜGFTPL
if Alg, == FII. and 0,FL > U/FTPL then
4:
5: Algr+1 GFTPL
6: else if Alg, == GFTPL and OGFTPL > 50,TL then
7: Alg,41 =FTL
8:
end if
9:
Feed Yt to Alg
10:
end for
GFTL EiezFI d;, and the estimated regret of GFTPL in IGFTPL can be bounded via Theorem M+
OOFTPL=
(4v2 (2In K, VN K) + 47) V 7 +1
(4)
+ +y (V + 27² + 4v2 max
max (2In K, VN In K37.
where Σ; min EiEzgrA (ar yi) and set
Note that, the two quantities defined above the exact regret upper bounds of the algorithms their sub-time intervals up to round t, due to the fact that the regret bounds provided in Lemma B and Theorem M are timeless. Moreover, note that the values can be computed by the oracle. We compare the estimated regret of both algorithms, and use the algorithm which performs better for the next round (lines 4-8).
For the proposed algorithm, have the following theoretical guarantee (the proof be found in Appendix D.
Theorem 3. Assume we have a 7-approximable r, then Algorithm is able to achieve the following bound:
GFTPL + +, + + R I min 3UT
where r = 4v ln V In K} + 12 and a =3 1.
The Theorem above shows that the regret of Algorithm B is the minimum of the regret upper bounds of GFTPL and FTL. Thus, ensures the achieves the much better constant regret bound of FTL under iid data without knowing the presence of stochasticity in data beforehand.
bound in the worst case, while automatically
Conclusion
In this paper, establish sufficient condition for the first-order bound in the oracle-efficient setting by investigating a variant the generalized feelowtte-perturbee-eeee show the condition is satisfied in various applications. Finally, we extend the algorithm to adapt to IID losses and achieve a "best-of-bont wow--ooothworldeee bound. In the future, we would like to investigate how to achieve tighter results for oracle-efficient setting, such as the second-order bound (De Rooi Saal 201)) and the quantile bound (Koolen & Erven 2015).
algorithm. We also
Acknowledgments. We gratefully thank the A14OPT Institute for funding, as part of NSF Award 21 2112333. We gratefully acknowledge the NSF for their support through Award IIS-2212182 and Adobe Research for their support through Data Science Research Award. Part of this work was conducted while the authors were visiting the Simons Institute for the Theory of Computing.
References
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algorithm for contextual bandits. Proceedings of the 27th International Conference Machine Learning, pp. 1638-1646, 2014.
10

---

Awerbuch, B. and Kleinberg, R. Online linear optimization and adaptive routing. Journal of Com- puter and System Sciences, 74(1):97-114, 2008.
Balcan, M.-F,, Blum, A., Haghtalab, N., and Procaccia, A. D. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the 16th ACM conference economics and computation, pp. 61-78, 2015.
Bertsekas, D. Reinforcement learning and optimal control. Athena Scientific, 2019.
Bishop, C. M. Pattern Recognition and Machine Learning. Springer, 2007.
Block, A., Dagan, Y., Golowich, N., and Rakhlin, A. Smoothed online learning is as easy as statisti- cal learning. arXiv preprint arXiv:2202.04R 046900 2022.
Cesa-Bianchi, N. and Lugosi, G. Prediction, Learning. and Games. Cambridge University Press, 2006.
Cesa-Bianchi, N., Mansour, Y., and Stoltz,, G. Improved second-order bounds for prediction with expert advice. Proceedings of the 18th Annual Conference on Learning Theory, pp. 217-232, 2005.
Cosa-Bianchi, N., Gentile, C.,, and Mansour, Y. Regret minimization for reserve prices in second- price auctions. IEEE Transactions on Information Theory, 544554549-564 2014.
Chaudhuri, K., Freund, Y., and Hsu, D. A parameter-free hedging algorithm. 22, 2009.
Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. In Proceedings of the 31st Conference On Learning Theory, pp. 1493-1529, 2018
Daskalakis, C. and Syrgkanis, V. Learning in auctions: Regret is hard, envy is easy. In The 57th Annual Symposium on Foundations of Computer Science, pp. 219-228, 2016.
De Rooij, S., Van Erven, T., Grünwald, P. D., and Koolen, W. M. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, 15(1): 1281-1168 2014.
Dobzinski, S. and Nisan, N. Mechanisms for multi-unit auctions. Journal of Artificial Intelligence Research, 37:85 98, 2010.
Dudik, M., Hsu, D., Kale, S., Karampatziakis, N., Langford, J., Reyzin, L.,, and Zhang, T. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pp. 169178, 2011.
Dudík, M., Haghtalab, N., Luo, H., Schapire, R. E., Syrgkanis, V., and Vaughan, J. W. Oracle- efficient online learning and auction design. Journal of the ACM, 67(5):1-57, 2020.
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning, pp. 3199- 3210. PMLR, 2020.
Foster, D., Agarwal, A., Dudik, M., Luo, H., and Schapire, R. Practical contextual bandits with regression oracles. In Proceedings of the 35th International Conference on Machine Learning. pp. 1539-1548, 2018.
Gaillard, P., Stoltz, G., and Van Erven, T. A second-order bound with excess losses. In Proceedings of the 27th Annual Conference on Learning Theory, pp. 176-196, 2014.
Guruswami, V., Hartline, J. D., Karlin, A. R., Kempe, D., Kenyon, C., and McSherry, F. On profit- maximizing envy-free pricing. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 164-1117, 2005.
Haghtalab, N., Han, Y., Shetty, A., and Yang. K. Oracle-efficient online learning for beyond worst- case adversaries. arXiv preprint arXiv: 08549, 2022a.
Haghtalab, N., Roughgarden, T., and Shetty, A. Smoothed analysis with adaptive adversaries. In IEEE 62nd Annual Symposium Foundations of Computer Science, pp. 942-953, 2022b.

---

Hannan. J. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, (2)997-139, 1957.
Hazan, E. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Hazan, and Kale, S. Online submodular minimization. In Journal of Machine Learning Research, volume 13, pp. 2903-2922, 2012.
Hazan, E. and Koren, T. The computational power of optimization in online learning. In Proceedings of the 48th annual ACM symposium on Theory of Computing, pp. 128-141, 2016.
Hazan, E. and Seshadhri, C. Adaptive algorithms for online decision problems. Electronic Collo- quium on Computational Complexity, 88, 2007.
Hazan, E., Agarwal, A.. and Kale, S. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-11133 2007.
Hutter, M. and Poland, J. Adaptive online prediction by following the perturbed leader. Journal of Machine Learning Research, 6(22):639-66) 2005.
Kalai, and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307 2005.
Koolen, W. M. and Erven, T. V. Second-order quantile methods for experts and combinatorial games. In Proceedings of the 28th Conference on Learning Theory, pp. 1155-1175, 2015.
Langford, J. and Zhang, T. The epoch-greedy algorithm for multi-armed bandits with side informa- tion. In Advances Neural Information Processing Systems 20, pp. $17-824, 2008.
Luo, H. and Schapire, R. E. Achieving all with no parameters: Adanormalhedge. In Proceedings of the 28th Conference on Learning Theory, pp.
2015.
Morgenstern, H. and Roughgarden, On the comudddimension nearly optimal auctions. Ad- vances in Neural Information Processing Systems 28, 2015.
Niazadeh, R., Golrezaei, N., Wang. J. R., Susan, F., and Badanidiyuru, A. Online learning via offline greedy algorithms: Applications in market design and optimization. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 737-738, 2021.
Nisan, and Ronen, Computationally feasible veg mechanisms. Journal of Artificial Intelli- gence Research, 29:19-47, 2007.
Orabona, F. A modern introduction online learning. arXiv preprint arXiv: 2019.
Orabona, F., Cesa-Bianchi, N., and Gentile, C. Beyond logarithmic bounds in online learning. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, pp. 823 831, 2012.
Rakhlin, A., Sridharan, K., and Tewari, A. Online learning: Stochastic, constrained, and smoothed adversaries. 24, 2011.
Roughgarden, T. and Wang, J. R. Minimizing regret with multiple reserves. ACM Transactions on Economics and Computation, 183):1-18, 2019.
Shalev-Shwartz, S. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Srebro, N., Sridharan, K., and Tewari, A. Smoothness, low-noise and fast rates. In Advances in Neural Information Processing Systems 23, pp. 2199-2207, 2010.
Syrgkanis, V., Krishnamurthy, A., and Schapire, R. Efficient algorithms for adversarial contextual learning. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2159- 2168, 2016.
12

---

Van Erven, T., Kotlowski, W. and Warmuth, M. K. Follow the leader with dropout perturbations. In Proceedings The 27th Conference on Learning Theory, pp. 949-974, 2014.
Wang, G., Lu, S., Hu, Y., and Zhang, L. Adapting to smoothness: A more universal algorithm for online convex optimization. In Proceedings of the 34th AAAI Conference Artificial Intelligence, 2020.
Zhang, L., Lu, S., and Zhou, Z.-H. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, pp. 1323-13333 2018.
Zhang, L., Liu, T.-Y., and Zhou, Z.-H. Adaptive regret of convex and smooth functions. In Proceed- ings of the 36th International Conference on Machine Learning, pp. 7414-7423, 2019.
Zhao, P., Zhang, Y.-J., Zhang, L.. and Zhou, Z.-H. Dynamic regret of convex and smooth functions.
In Advances Neural Information Processing Systems 33, pp. 12510-12520, 2020.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Pro- ceedings of the 20th International Conference on Machine Learning, pp. 928 988-936,20 2003.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [N/A]
(b) Did you describe the limitations of your work? [Yes] The proposed algorithm can noly
be applied when the 7-approximability condition met.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "pc9G09fczg1", "reviewer": "Reviewer_2kab", "summary": "The paper studies the online learning problem with general (possibly non-convex) losses but a finite number K  of possible actions (i.e., the experts setting). Prior works obtain regret bounds that have the optimal dependence on T. A different line of work, such as that for convex losses, has shown that one can obtain adaptive, problem-dependent,  regret bounds that are much better than the worst-case bounds when the losses are small or iid. The current paper asks whether such adaptive bounds can be obtained in the expert settings using algorithms that are oracle efficient in the sense that the running time has sublinear dependency on the number K of possible actions, with a logarithmic dependency or better being particularly suited for exponentially-sized action spaces.  The paper adapts the algorithm and analysis of Dudik et al., and obtain the first adaptive oracle-efficient algorithms.", "questions": "None", "limitations": "No", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: In order to obtain an oracle-efficient algorithm that adapts to the small losses, the paper adapts the approach of Dudik et al. A key bottleneck is designing a suitable perturbation matrix. The paper shows that the types of perturbation matrices considered by Dudik et al. are not suitable for the adaptive setting. To overcome this, the paper introduces an alternative type of perturbation matrices that are related to but incomparable to those considered by Dudik et al. The paper also shows that several practically relevant applications admit suitable perturbation matrices and thus the framework can be applied to all of these settings. By building on the work of Rooij et al., the paper also gives an algorithm for iid losses. Although the paper builds extensively on prior works, the new components needed to extend those works to the adaptive setting seem to be sufficiently novel.\n\nQuality: The paper seems to be theoretically sound. Both the theoretical and empirical claims seem to be well supported.\n\nClarity: The main body of the paper is sufficiently clear and well written.\n\nSignificance: The paper gives the first adaptive algorithms that are oracle-efficient in the experts settings. The resulting framework has several important applications. Both the theoretical results and the practical applications seems to be good contributions to the online learning literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gVeNN1vmbZx", "reviewer": "Reviewer_c3ru", "summary": "This paper considers online learning problems given offline optimization oracles and provide an algorithm that requires only a small number of oracle calls.\nThe main proposed algorithm has a cumulative-loss dependent regret bound, which implies improved performances for small-loss environments.\nThe algorithm is extended to establish best-of-both-worlds bounds, which means that it works at least as well as the follow-the-leader algorithm.", "questions": "- Is my understanding above correct? For example, if the application of Flipfrop is non-trivial and in need of special consideration, I would appreciate it if you could highlight it.\n\n- Is this the first study dealing with the FTPL approach with time-dependent adaptive parameters $\\eta_t$? If so, that would be strong support for the novelty of this paper.\n", "limitations": "\nThe limitations are adequately addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper provides the first oracle-efficient algorithm with a small-loss regret bound for online learning problem.\n- Assumptions and results are clearly stated\n\nWeaknesses:\n\n- Novelty in algorithms and analysis techniques is somewhat limited. Algorithms 1 and 2 are minor modification of algorithms by (Dud{\\'\\i}k et al., 2020). Algorithm 3 appears to be a direct application of (De Rooij et al., 2014).\n\nComments:\n\nThis study provides the first oracle-efficient algorithm with a small-loss regret bound for online learning problem.\nThe proposed algorithm is based on that by (Dud{\\'\\i}k et al., 2020).\nThe assumption of admissibility and implementablity also follows that by (Dud{\\'\\i}k et al., 2020).\nThe novelty lies in the adaptive updating of the parameter $\\eta_t$ corresponding to the learning rate and in the introduction of the concept of approximability for the analysis.\nA best-of-both-worlds bound is also achieved by a direct application of Flipflop approach by (De Rooij et al., 2014).\n\nWhile there has been steady progress as a result, the impression is that it is merely a combination of existing results.\nUnless this impression is dispelled in future discussions, I cannot strongly support the acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5Cv5TjoSWhx", "reviewer": "Reviewer_z8qi", "summary": "The paper's main contribution is an FTPL-style algorithm that achieves a small-loss bound in the full-information setting, leading to the first Oracle efficient algorithm to achieve such a guarantee. The key insight leading to this result is the observation that ensuring that $P[x_t\\neq x_{t+1}]$ is small (something that can be achieved for the outputs $x_1, x_2, \\dots$ of existing FTPL algorithms) is not enough to achieve a small loss bound. The authors identify a new condition on the perturbation process called approximability that ensures that the ratio $P[x_t \\neq x^i]/P[x_{t+1}\\neq x^i]$ is bounded, which they show is sufficient for achieving a small loss bound. The authors identify many applications where this condition on the noise process is satisfied. ", "questions": "Some questions are included in the limitations section.", "limitations": "See suggestions in the strengths and weaknesses section. Here are some typos:\n- Line 94. condition -> conditions\n- Line 139. The use of \"On the other hand\" does not make sense here. \n- Line 146. You cite Van Erven at. al 2014 when you mention FTPL. I do not think they were the ones to invent it. Perhaps more appropriate to cite Kalai and Vempala 2005 or something earlier.\n- Line 204. It is easy to that for -> It is easy to see that for.\n- Line 225. time-variant -> time-varying\n- Line 244. has a a -> has a\n- In the display within Cor 1, there is an \\epsilon that is not scoped. \n- Line 266. \"Noticing the fact that N= \\Omega (ln K)\". Where are we supposed to notice this from?\n- Line 316. Your notion of mixability gap is different from that of Rooij et al 2014.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The new approximability condition on the noise process of FTPL that the paper presents seems natural and leads to new, non-trivial results in Oracle efficient Online Learning. This is a strong contribution in my opinion. Weaknesses if any would be in the writing; in particular, the order in which some concepts are presented in the paper can be improved in my opinion. \n- First of all, it would be helpful to spell out explicitly early on that the point of using a PTM is to reduce computation as much as possible by only requiring a noise vector of dimension much smaller than the number of experts (you do explain this, but my point is just that it would be better if this point is crystal clear early on---the explanation on line 66 is not clear enough for someone who hasn't read the rest of the paper). \n- On line 200, you say that a PTM is not compatible with the Oracle, which is rather vague. It is not until you see the definition of an implementable PTM that things make sense. I would suggest mentioning something about implementable earlier in the paper. \n- On line 177, you mention \"However, motivated by adaptive FTPL in the inefficient setting\". Here by inefficient, you mean requiring a noise vector of the dimension the same as the number of experts. Spell this out.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-Qh9F33C3C", "reviewer": "Reviewer_dDpe", "summary": "\nSummary: One of the primary contribution of this work was to provide a new framework for designing follow-the-perturbed leader algorithms that are oracle-efficient and adapt well to the small-loss environment, under \"approximability\". Authors also extend their results to an IID data setting and establish a “best-of-both-worlds” bound in the oracle-efficient setting.\n", "questions": "The results for best-of-both setting is not at all clear. Entire Sec. 5 is not elaborated well, what are the two different problem environments (adversarial and stochastic ??), what is the regret benchmarked against in both cases, and how does Thm 3 claims that Alg3 achieves simultaneously achieves best of both both both setups?\n", "limitations": "See Qs above", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n- Strong theoretical results: Oracle efficient algorithms with regret guarantees\n- Applications\n\nWeakness: Scopes of the work appears to be limited since often in the real world problem, coming up with an efficient oracle might not be possible. Papers addresses few applications but for relatively simple/finite/structured settings.\nAlso the best-of both results (Sec 5) are not well defined/explained.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept