Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents high probability bounds of O(1/n) for uniformly stable algorithms. The authors assume the generalized Bernstein condition due to Koltchinskii [26] as an additional assumption compared to related works in the literature. Under this assumption, they show that uniformly stable algorithms can achieve [optimization_error + O(1/n)] excess risk bound with a high probability. The authors show that optimization of stronlgy convex Lipschitz continuous objective functions satisfies the generalized Bernstein condition. This allows them to provide the first high probability O(log(n)/ n) risk bound for uniformly stable algorithms on a strongly convex Lipschitz continuous optimization problem.
main_review: The paper uses tools developed by Bousquet et al. [8] heavily to prove their results. It is rather difficult to find a strongly convex function that is Lipschitz continuous and bounded. An easy way to justify these conditions together is to assume that \mathcal{X} is a compact set. The contribution is of good value from a theoretical point of view. As the authors pointed out, the generalized Bernstein assumption might be useful when considering optimization under PL-condition which is widely studied in recent years due to its usefulness for modern ML applications. Overall, the paper makes a good contribution and might serve as a first step to thoroughly explore the new assumption in different settings.
limitations_and_societal_impact: One potential improvement is to consider the running time of the algorithm when trying to achieve high probability O(1/n) excess risk bounds. Currently, the algorithm requires n^2 iterations of full-batch which results in O(n^3) gradient-complexity which is significant.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The article exhibit a way to bound the excess risk in a general risk minimization framework when the loss function is with bounded difference (or stable as they call it). They show that the rates $O(1/n)$ can be attained under some Bernstein condition. This is  often called "fast rates" of convergence in the literature and this article exhibit the first general inequality to get fast rates of convergence for stable loss function.
main_review: To my knowledge, this type of result was only proved in particular cases and this is the first general result on fast rates of convergence obtained via stability. The article is clear and well written and I think this is significant for the Neurips community. This article may generalize to a lot of learning problems and may become a tool to prove fast rates in  a lot of different settings, this may be an important step to assess the rate of convergence of algorithms and to have theoretical rates that match the rates that we witness in practice. The authors also illustrate this generalization capacity on the problem of stochastic convex optimization with strongly convex losses.
limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary:  The authors presented an improved variance-type excess risk analysis for uniformly stable learning algorithms. Particularly, it was proved that if the population risk satisfies the Bernstein condition, then a $\gamma$-stable algorithm with optimization error $\Delta_{opt}$ over a set of $n$ observations can achieve excess risk of order $\gamma \log(n) + \frac{1}{n} + \Delta_{opt}$ with high probability. This result implies $O(\frac{\log(n)}{\lambda n})$ risk bounds for empirical risk minimization (ERM) and projected gradient descent (PGD) with $\lambda$-strongly convex and Lipschitz loss functions. Also, a high-probability $\eta$-approximated generalization error bound is provided which improves the $O(\sqrt{\frac{\log(1/\delta)}{n}})$ tail term in the best known generalization bounds to $O(\frac{\log(1/\delta)}{\eta n})$.


main_review: Strengths: 
+ The deviation analysis of uniformly stable algorithms as focused in this paper is an important and timely topic in learning theory.
  
+ I am particularly impressed with the strength and originality of the results obtained in this paper for strongly convex optimization problems. The main idea of proof is to make a smart use of an extended bounded difference inequality from Bousquet, et al. (2020) to separate the sampling term from the generalization error, so that the randomness of model and data sample can be decoupled in a way that the Bernstain inequality is applicable to get tighter bounds. While built largely upon the previous results, IMO the technical part still appears novel enough in the considered problem regime.  
 
+ The paper is generally well organized and clearly presented, with all steps in the proofs very carefully explained. 

Weakness: 
  
   My main concern is about the benefit of main results in Theorem 1.1 when substantialized to ERM and PGD with arbitrary convex losses. Basically, the improved $O(\frac{\log(n)}{n})$ rate of convergence seems only possible for strongly convex loss functions with zero optimization error achievable over training data. For generic convex losses which are of more interest in practice, we usually need to deal with regularized ERM of which the empirical risk error $\Delta_{opt}$ is typically $O(\frac{1}{\sqrt{n}})$ due to a trade-off between optimization and generalization. In this case, while the population risk can still be assumed strongly convex so that Theorem 1.1 is applicable, the $O(\frac{1}{\sqrt{n}})$ optimization error term will dominate the risk bound which makes the  $O(\frac{1}{n})$ term much less interesting. The authors have partially  addressed such a limitation for Theorem 1.2 with respect to the empirical risk. However, it looks like that similar or even more severe limitations exist for Theorem 1.1 as well in terms of optimization error.  


=== Post rebuttal update ===

The major concern  on the limitation of results raised in my initial review has been properly addressed in author response. I would like to maintain my rating.   
limitations_and_societal_impact: Yes,  the authors have partially addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work provides improved generalization bounds for uniformly stable algorithms under the Bernstein condition. This condition bounds the variance of the loss with respect to a risk minimizer by the excess risk, and it has been widely used to derive faster rates in statistical learning. However, their use for high probability bounds in stochastic optimization was limited by the fact that all known high probability generalization bounds for stable algorithms incurred terms $\Omega(1/\sqrt{n})$. The main consequence of this result is a high probability excess risk bound for the Empirical Risk Minimizer in strongly convex stochastic optimization, resolving an open question by Shalev-Shwartz et al. (COLT 2009). Another consequence is an (optimal) high probability excess risk bound for (full-batch) gradient descent with O(n^2) iterations. 

Uniform stability is a central tool for machine learning theory, and the results of this paper provide a clear contribution here. Technically, the paper does not include much innovation, but the methods used, particularly referring to the excess risk decomposition, are quite interesting, and may encounter further use. Finally, I am not sure about the "deviation optimal" part in the title: Is it clear that the bounds derived are sharp? No matching lower bounds are provided for Lemma 3.1 or Theorem 1.1. I believe existing results (like lower bounds in Bousquet, Klochkov & Zhivotovskiy (BKZ)) may already explain this to some extent, but I would suggest including a more detailed discussion on sharpness.

main_review: 
1. To achieve the main result, a useful Lemma 3.1 is shown (this is a minor variation of a Lemma from BKZ): this result avoids the sampling error term $O(1/\sqrt{n})$ by showing a moment bound of a "shifted" generalization error. This shifting includes the risk of the algorithm output and an average conditional loss. It would be interesting if the authors would elaborate further about the intuition on this refinement, and what are its consequences for the excess risk bounds (the technical proofs are clear, but 
nevertheless it might be useful a brief discussion).

2. The proof of the main result (Thm 1.1) is obtained nontrivially from Lemma 3.1. This involves a (seemingly novel) decomposition of the excess risk and the (shifted) generalization error, along with various estimates based on concentration by the Bernstein condition.

3. Theorem 1.2 provides what they call a variance-type bound (not sure why is it called like this), which bounds the risk in terms of the empirical risk and a deviation bound which leverages faster rates by uniform stability. This bound seems useful in realizable settings, where the empirical risk can be made arbitrarily small.

4. The consequences for strongly convex stochastic optimization appear in Proposition 2.1 and its following discussion. As mentioned above, this general bound for stable algorithms answers a question raised in Shalev-Shwartz et al (2009) which is quite interesting on its own. In this result, the most problematic term is $\sqrt{L^2\overline{\Delta}/\lambda}$, where $\overline{\Delta}$ is a bound on the empirical error: this leads to optimal excess risk in this case for GD with O(n^2) iterations. It is worth pointing out here that a similar iteration requirement appears in the nonsmooth case, as shown in Bassily, Feldman Guzman and Talwar (2020). That paper also includes a lower bound on stability, showing that for GD $\Omega(n^2)$ steps needed to obtain optimal rates with uniform stability. It is reasonable to conjecture that a similar lower bound may hold in the strongly convex setting, and in fact some limitations of GD in terms of excess risk have already been shown in recent work by Amir, Koren and Livni (https://arxiv.org/pdf/2102.01117.pdf). The latter result is shown for GD on the regularized ERM, but I suspect ideas there might be useful for the strongly convex setting as well.

Finally, I would suggest the authors to include a more detailed statement of the last paragraph before section 3 (lines 204-206 in page 6). Here it is claimed a new high-probability excess risk bound for GD on smooth and strongly convex losses. For future use of this result, it might be a good idea to have a proper statement.

limitations_and_societal_impact: This work is theoretical, so I agree with the authors there are no societal consequences of it.
review_title: null

Meta-review: The reviewers are unanimous that this work provides a significant contribution in the area of uniform stability, which should interest the learning theory community as well as the wider NeurIPS community. A key consequence of the authors' results is the positive resolution of a long-standing open question of Shalev-Shwartz et al.'s COLT 2009 paper: this question is about whether ERM can obtain fast rates of convergence for Lipschitz, stochastic strongly convex optimization with high probability, where the dependence on the failure probability $\delta$ is logarithmic. While the authors do heavily draw from previous work, certain technical components like the novel excess risk decomposition are highly original, provide an important technical contribution, and might lead to progress in future works. In addition, the work is very well written and clear. This work would be a welcome contribution to NeurIPS.
Decision: Accept (Oral)