Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
Summary: 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.

strengths_and_weaknesses: 
- Strong theoretical results: Oracle efficient algorithms with regret guarantees
- Applications

Weakness: 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.
Also the best-of both results (Sec 5) are not well defined/explained.
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?

limitations: See Qs above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

Quality: The paper seems to be theoretically sound. Both the theoretical and empirical claims seem to be well supported.

Clarity: The main body of the paper is sufficiently clear and well written.

Significance: 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.
questions: None
limitations: No
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers online learning problems given offline optimization oracles and provide an algorithm that requires only a small number of oracle calls.
The main proposed algorithm has a cumulative-loss dependent regret bound, which implies improved performances for small-loss environments.
The 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.
strengths_and_weaknesses: Strengths:

- The paper provides the first oracle-efficient algorithm with a small-loss regret bound for online learning problem.
- Assumptions and results are clearly stated

Weaknesses:

- 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).

Comments:

This study provides the first oracle-efficient algorithm with a small-loss regret bound for online learning problem.
The proposed algorithm is based on that by (Dud{\'\i}k et al., 2020).
The assumption of admissibility and implementablity also follows that by (Dud{\'\i}k et al., 2020).
The 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.
A best-of-both-worlds bound is also achieved by a direct application of Flipflop approach by (De Rooij et al., 2014).

While there has been steady progress as a result, the impression is that it is merely a combination of existing results.
Unless this impression is dispelled in future discussions, I cannot strongly support the acceptance.
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.

- 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.

limitations: 
The limitations are adequately addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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. 
- 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). 
- 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. 
- 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.

questions: Some questions are included in the limitations section.
limitations: See suggestions in the strengths and weaknesses section. Here are some typos:
- Line 94. condition -> conditions
- Line 139. The use of "On the other hand" does not make sense here. 
- 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.
- Line 204. It is easy to that for -> It is easy to see that for.
- Line 225. time-variant -> time-varying
- Line 244. has a a -> has a
- In the display within Cor 1, there is an \epsilon that is not scoped. 
- Line 266. "Noticing the fact that N= \Omega (ln K)". Where are we supposed to notice this from?
- Line 316. Your notion of mixability gap is different from that of Rooij et al 2014.
review_title: null

Meta-review: metareview: The paper received reviews from experts in online learning, who all support acceptance following some clarifications provided by the authors.  From my own look into the paper, I also firmly support acceptance: the paper makes a clear, solid and elegant contribution to a long line of research in online learning, and it is also very well written.  I do however strongly encourage the authors to pay close attention to the suggestions in the reviews as to how to improve their presentation for the final version.
confidence: Certain
Decision: Accept