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: The authors study the problem of the gap that exists between the bounds for computationally feasible bounds for online learning poly(T/sigma) and exponential-complexity algorithms with a log(T/sigma). The consider a subset of this problem where the adversary or nature is allowed to select contexts with density bounded w.r.t. a known measure mu. They also provide theorems that characterize the determinant of matrix averages.
strengths_and_weaknesses: The paper gives a computationally efficient algorithm that closes the computational gap for a more restricted problem in online learning: where nature is restricted to select from a distribution bounded by 1/sigma from a know measure mu. This is a novel result that is interesting.

The bigger strengths of the paper are the interesting use of the John ellipsoid in their base algorithm and their use of Ville's inequality to analyze and bound the stopping time. Their theoretical results and techniques are of independent interest in addition to the their computationally efficient algorithm.
questions: None
limitations: None
review_title: null

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: This paper considers the problem of smooth online learning in the realizable setting. In the smooth online learning problem, the adversary is limited to choosing a distribution over contexts at each round which is “smooth” wrt to a dominating measure. The player knows the dominating measure. 
 
For smooth online learning algorithms, there exists a statistical computational gap, and the main goal of this paper is to close the gap for the special case of the linear function classes in high dimensions. The main contribution of the paper is designing novel algorithms for this problem which attain the optimal statistical guarantees on the regret while computationally-efficient. 

The main idea behind the proof is presented in Section 3. The authors show that if, with respect to the dominating measure, the error probability of the player decays, then with respect to any other measure that is smooth wrt to the dominating measure , we have a control over the regret. Then, as usual, to control the probability of error, the authors use the fact that a control over the size of the disagreement region can control the probability of error. They have a very nice result which provides a bound on the size of the disagreement region based on the volume of the version space in Lemma 4.

In the rest of the paper, they use their techniques to obtain optimal regret bounds for Linear Classification, Perceptron algorithm, Linear Classification Under a Feature map, and Multi-Class Classification.

strengths_and_weaknesses: Overall, I think this paper is really strong. Also, the paper is very well-written, and the proof sketches are helpful in understanding the gist of the techniques. Moreover, the techniques used by the authors are also very interesting and novel.
My main concern about this paper is the “robustness” of the results and the techniques to the dominating measures. It seems in most of the results in the paper, it is assumed that the dominating measure is uniform on the unit ball of radius one in dimension d. 

I have a few questions which I will discuss in the next part. 

questions: 1- What is the definition of overly strong measures in Remark 2?

2- Are your results robust to the change of the dominating measure? How can we design algorithms that are agnostic to the dominating measure?

3- It seems that the algorithms designed in the paper are agnostic to the value of sigma. Is there any improvement if we assume the player knows the value of sigma? 

5- As mentioned in some cases, the sigma may depend on the dimension. Do we have a general approach to make sure sigma is O(1) in dimension?

6- Your results strongly rely on the fact that the linear function class has a natural parameterization as vectors in dimension d. How can the results be extended to the classes without natural parametrization. 


limitations: yes.
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 focuses on the statistical analysis of smoothed online learning for generalized linear functions. It provides the statistical \log(T/sigma) regret for K-wise linear classification and extends the results to settings where the true classifier is linear in an over-parameterized polynomial featurization of the contexts, as well as to a realizable piecewise-regression setting assuming access to an appropriate ERM oracle. This work develops a characterization of the geometry of the disagreement region induced by generalized linear classifiers and a general anti-concentration bound for the determinant of certain matrix averages.
strengths_and_weaknesses: This paper has the following contributions: This paper studies the statistical property of certain classes of realizable smoothed online classification problems, for example affine thresholds, affine thresholds in nonlinear features, K-class affine classification, and piecewise affine regression, which have the statistically optimal regret bound. Then, this paper obtains a fast algorithm that achieves optimal regret dependence on the horizon, up to logarithmic factors, by applying the obtained results to noiseless contextual bandits. Finally, a complementary approach based on the perceptron algorithm is provided, which has a polynomial regret in a “directional smoothness” parameter. This paper adopts the smoothed online learning setting of Rakhlin et al. [2011], Haghtalab et al. [2021], Block et al. [2022]. The related work can be elaborated in more detail. It would be better to provide related experimental results to prove the rationality of the theoretical analysis.
The research field of this paper is significant. The organization and presentation of this paper can be further improved. There is no conclusion section.
questions: This paper investigates the statistical analysis of smoothed online learning for generalized linear functions. The paper can be improved from multiple points of view.
1)Presentation. The presentation could be improved. The logic of this paper is hard to follow. 
2)Quality. The introduction of related work can be further specified, and the comparison work can be further refined and improved. This paper adopts the smoothed online learning setting of Rakhlin et al. [2011], Haghtalab et al. [2021], Block et al. [2022]. It would be better if there is an improvement of the algorithms.
3)Experiments. This paper mainly provides new theoretical analysis on the existing algorithms. It would be better if there are experiments to verify the results of theoretical analysis. 
4)Grammar, typos, and writing. It is suggested to further polish the writing.
References are generally not used as the beginning of a sentence, such as: Rakhlin et al. [2011] proposed smoothed adversaries and proved regret bounds for linear thresholds in ...
Tenses in this paper are inconsistent. For example: 
In line 73, Smoothed analysis was first proposed in Spielman and Teng [2004] as a way to explain the success of the simplex algorithm...
In line 101, Hanneke [2007] controls the label complexity of active learning...
The equation at the end of the sentence should be punctuated. For example, equation (2.2).
limitations: This paper describes the scope of application of the proposed methods in detail, and does not involve negative social impact.
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 studies the smoothed online learning setting, where the adversary's action at each step must be drawn from a distribution with density bounded by $1/\sigma$. This model bridges the offline/batch setting and the usual online setting. Previous upper bounds for this smoothed setting, however, have an exponential gap in the dependence on $T/\sigma$ between computationally bounded and unbounded learners.

This work gives efficient algorithms that achieve $\log(T/\sigma)$-type regret, which nearly matches the optimal regret when computation is unbounded. All the following results hold under the realizable case: For linear classification, Theorem 5 gives a high-probability regret bound of $O(d\log d + \log(T/\sigma))$, nearly matching an $\Omega(d + \log(T/\sigma))$ lower bound in Proposition 6. This is further generalized to affine classification (Corollary 8), linear classification under a feature map (Theorems 9 and 10), and multi-class classification (Theorems 11 and 12).

For linear classification, the algorithm (Algorithm 1) is quite intuitive: maintain the (convex) set of hypotheses that are consistent with all previous examples, and predict with the center of its John ellipsoid. (The authors show that for other natural choices like the Chebyshev center or centroid, the analysis would not work.)

The analysis builds on the following two technical tools:
- A decay analysis (Lemma 3), showing that it suffices to argue that whenever a mistake is made, the probability of making a mistake (at the next step) shrinks by a factor.
- A geometric result (Lemma 4) that proves such a decay. While its statement is intuitive, the proof of Lemma 4 is quite technical and nontrivial.
strengths_and_weaknesses: The paper studies a sequential learning setting that receives much attention recently, and makes good progress in closing the computation-information gap in the optimal regret. While the proposed algorithm is simple, its analysis seems highly nontrivial even in the linear classification setting. I found the paper enjoyable to read, and thought that the authors did a good job in including both intuition and technical details of their proofs in the main paper, despite the technical difficulty in them.

One weakness is that the results are specific to the realizable setting, and it is unlikely that the current apporach/techniques could be easily extended to agnostic case. Nevertheless, given that previously no efficient algorithms are known to achieve the $\log(T/\sigma)$-type regret, I found the current results sufficiently significant.
questions: 1. The paragraph on Lines 248-255 says that other choices of $w_t$ cannot guarantee the decay in both volume and surface area. Are there hard instances on which these choices provably incur a large regret? In other words, to what extent is the surface area decay necessary?

2. What is the main difficulty in extending the results to the agnostic setting?
limitations: The main limitation is the results only hold for certain hypothesis classes and only under the realizable setting. This is made clear by the authors when summarizing the contribution.
review_title: null

Meta-review: metareview: The reviewers agree that this is a solid contribution. Please do revise the paper according to the reviewers comments and the discussion.
confidence: Certain
Decision: Accept