Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: For online learning with smoothed adversaries, optimal statistical
regret rates are known, but there are no efficient algorithms. Assuming
access to an offline ERM oracle, the present paper develops new
online algorithms that are computationally efficient (making 1 or 2
calls to the oracle per round, with the input size to the oracle also
under control). These algorithms achieve expected regret rates that are
optimal except for their dependence on the parameter sigma that measures
the smoothness of the adversary. There is also a lower bound that holds
for the expected regret for any algorithm with run-time below a certain
threshold.

strengths_and_weaknesses: Strengths:
* Smoothed adversaries are seeing a lot of recent interest, but to move
  towards practically relevant results it is essential to have efficient
  algorithms, which is what the current paper tries to address.
* The algorithms are elegant reductions to calls to the oracle.
* Their analysis is clean, and clearly explained.

Weaknesses:
* I am not sure that the proposed algorithms will be so efficient that
  they can actually be used in practice, because implementing the oracle
  might still be a bottleneck.
* The lower bound in Thm 5.1 seems rather weak because the run-time
  requirement of omega(sqrt{d/sigma}) does not grow with the total
  number of rounds T.

Remarks:
* Line 125: mathcal{Y} cannot be an arbitrary subset of [-1,+1], because
  the predictions of Algorithm 1 can span the whole range [-1,+1].

Minor comments:
* Line 101: "unaviodable"
* Line 125: mathcal{Y} should not be an element of [-1,1], but a subset
* Line 128: For Y = {-1,+1}, convexity and Lipschitzness make no sense.
  (I assume these requirements do not apply in this case.)
* Paragraph below Definition 2.1: Equivalence between the two versions
  of the protocol is not obvious, because it seems to depend on whether the
  adversary and the learner are allowed to randomize, which is not
  specified explicitly.
* Multiple uses of "arginf" throughout the paper. Use "argmin" instead,
  because it only makes sense if the minimum is achieved.
* Line 179: Please specify distribution of \mathcal{E}^(t)
* Line 181: "labled"
* Multiple places: "\tilde{O} hideS factors"
* Theorem 3.2 and Corollary 3.3: regret -> expected regret.
* Section 4.2: historically, the perturbations for Follow the Perturbed
  Leader were not of the type described here, so perhaps clarify that
  your description is a special case.
* Line 282: please point out that beta is o(1/T). I initially thought it
  was of order T.
* Theorem 5.1: please explain how "total running time" is measured
  (e.g., copy explanation from the appendix)
* Line 522: I think you meant that beta = o(1/T) instead of o(T).
* Line 841, "both lower bounds": there is no lower bound on the regret
  in Theorem 5.1
* Lemma E.2: "supreme" -> "supremum"

questions: * Could you give examples of offline oracles that are sufficiently
  efficient to make your algorithms practically feasible?
* For comparison with the result from Theorem 5.1: what is the running
  time of Algorithms 1 and 2 in your model of "running time"?


limitations: * The efficiency of the algorithms relies on the availability of an
  efficient offline oracle, but the paper does not discuss for which
  hypothesis classes such offline oracles are available. In particular
  for the binary classification case, this might be an issue, since
  computing the ERM is NP-hard for many common classes.

* The algorithms require knowledge of sigma, which would typically not
  be available in practice.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work provides so called oracle efficient algorithms for online learning, in the smoothed adversarial setting. This problem corresponds to: given access to an ERM oracle, to design an algorithm whose regret in the worst-case regret under distributions which are $\sigma$-smooth, is as small at possible. The results of the paper provide $O(\sqrt{T})$ regret algorithms in this setting, where also the noise parameter $\sigma$, as well as the VC dimension $d$, appear in the bounds. The paper focuses in the setting of convex Lipschitz loses and binary cases separately. For the former, a relaxation framework (a technique tracing back to [RSS12]) is proposed, which also leverages a coupling technique that exploits the smoothness of the adversary to establish that any smooth sample will be contained who on a larger sample of iid uniform random variables. For the binary case, tighter bounds are obtained via a follow the perturbed leader (FTPL) approach, which also leverages the aforementioned coupling. Several other ideas, regarding the use of a form of regularized Rademacher complexity, stability analysis, etc.; are used. The paper also provides some computational lower bounds, showing that for small values of $\sigma$, the improved regret bounds of previous work necessarily require polynomial running time in $1/\sigma$.
strengths_and_weaknesses: Strengths: 

1. Strong results, that compare favorably even to concurrent works.
2. Technically solid paper. Many interesting ideas which may be for independent interest.
3. Although the motivating question is more conceptual than practical, I still think it is worth of the attention of the machine learning community.

Weaknesses:

1. I find the idea of an ERM oracle quite unappealing. The optimization problems that ERM entail can be quite difficult to solve (specially for binary classification). So, although I believe that the reduction question is interesting on its own, it is hard to believe this model has any concrete consequences for ML.
2. Bounds depending on combinatorial parameters, such as VC dimension, can be quite pessimistic, and can be majorly improved by distribution dependent quantities, such as margin conditions. Maybe the results of the paper can easily transfer to these more benign characterizations, but it is not evident from the analysis.
questions: 1. Can the authors add some references on transduction learning, just to point interested readers into relevant literature, to better grasp the results?
2. Page 15, equation (5). ${\cal Q}_t$ is used as notation in the equations before it is introduced. I suggest to mention this before the chain of equations, rather than after.
3. Page 17, line 568. What is $I$? Also I am inferring (but it is not clear from the writing) that ${\cal E}=(\epsilon_1,\ldots,\epsilon_I)$?
4. Page 22, Lemma C.6. It was unclear for me (until reading the proof), that $X_I$ is being conditioned on $E,X_{\setminus I}$. I would suggest writing it instead as $X_I | (E,X_{\setminus I})$.
limitations: Yes, I think limitations of the paper are discussed, and it even points out to an interesting open problem. Social impact is out of the scope of the paper.
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: 
This paper considers online learning with smoothed adversaries, which is a special case of online learning. Online learning is a sequential setting in which in round $t = 1, \ldots, T$ a learner issues a prediction, suffers a loss corresponding to that prediction, and subsequently observes some feedback. The goal is to control the regret, which is the difference between the cumulative losses of the learner and the cumulative losses of the best fixed prediction in hindsight. Normally, the losses are chosen by an adversary or sampled from a distribution. However, in this paper the authors consider a setting in which the adversary generates losses from a distribution that is bounded by $1/\sigma$ times the uniform distribution. 

Non-efficient algorithms for this setting obtain regret bounds of order $\sqrt{dT\ln(\sigma^{-1})}$, where $d$ is a problem specific parameter. The authors provide an efficient algorithm with $\sqrt{d T \sigma^{-1}}$ regret for real or binary losses and an algorithm with $\sqrt{dT\sigma^{-1/2}}$ for binary losses. 

Lower bounds for any efficient algorithm are of order $\sqrt{d^{1/2}T\sigma^{-1/2}}$ and for algorithms in the same class of the algorithms that are used to obtain the new upper bounds are of order $\sqrt{dT\sigma^{-1/2}}$. 

strengths_and_weaknesses: Strengths 

The paper is well written.

The techniques to obtain the upper bound are nice and could prove useful beyond this paper. 

There are immediate consequences beyond the setting at hand: the regret bounds imply improvements in worst-case binary classification in terms of the domain size and in transductive binary classification. 

The paper is well contextualised.

The jump in regret bounds from inefficient to efficient algorithms is explained by the lower bounds, although it is not clear whether these lower bounds are tight. 



Weaknesses

The setting seems to be a natural interpolation between adversarially and stochastically generated losses. However, it also seems to be quite a strong assumption to assume knowledge of $\sigma$. Is there a reason why in general one can assume knowledge of $\sigma$?

The algorithm needs knowledge of $\sigma$ to draw samples from $1/\sigma$ times the uniform distribution, which makes me believe that even having a slightly inaccurate $\sigma$ would lead to profound consequences for the regret bound. Naively trying to learn $\sigma$ choosing a grid of possible $\sigma$ and then running an expert algorithm seems quite costly in terms of oracle calls. Is there a more clever approach?

questions: See the weaknesses. 
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work
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: This paper considers the oracle-efficiency of smoothed online learning. In this setting, the output distribution of the nature is constrained to have a constant upper bound. Assuming an offline optimization oracle, they give an $O(\sqrt{T d \sigma^{-1}})$ regret bound for real valued loss and an $O(\sqrt{T d \sigma^{-1/2}})$ regret bound for binary valued loss as their main results. The algorithms achieving these regret bounds are based on FPL. 
strengths_and_weaknesses: The results are sound and solid, and the algorithms and proof ideas are very intuitive. The Poissonization technique is novel and may be of independent interest.

The major concern I have is on the setting of smoothed online learning. There are many ways to characterize online learning beyond worst-case, and smoothed online learning doesn't seem natural to me. I don't see any practical scenario supporting the smoothed setting, and in theory there are other more intuitive ways: for example assuming noise or predictable sequences. The way that smoothed analysis restricts the distribution of the nature's outputs doesn't make much sense and the constant upper bound seems a very strong assumption.

The improvement over regret bounds of classical online learning doesn't seem significant: the dominating term $O(\sqrt{T})$ isn't improved. One may expect a more significant improvement from the strong additional assumption. A (not very relevant) example is that one can improve the regret bound to $O(\log T)$ assuming an abstention option.

The paper is well-written and easy-to-follow. It spells out the assumptions, algorithms and intuitions clearly.

Though the results of this paper are solid, due to the concurrent work of BDGR22 which is already accepted at COLT2022, there doesn't seem to be enough improvement and novelty upon it. For this reason (along with my concern on the smoothed analysis setting), unfortunately I tend to reject this paper. 
questions: Can you give more justification on the smoothed analysis setting? Or any concrete example?
limitations: Yes
review_title: null

Meta-review: metareview: As summarized very well in the reviews, this is a well-written paper that makes a solid and elegant contribution to the recently active line of work on smoothed online learning.  The authors have successfully addressed the main concerns brought up in the discussion.  I genuinely agree the paper should be accepted.

As a side note to the authors: I honestly found your reaction to Reviewer gcMM’s comments rather aggressive and incongruous.  Disagreements naturally arise in a discussion and should not be automatically considered as an attempt to “greatly harm the review process and the community at large”.
confidence: Certain
Decision: Accept