Generalization Bounds for Uniformly Stable Algorithms
Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss function with range bounded in [0, 1], the generalization error of a γ-uniformly stable learning algorithm on n samples is known to be within O((γ + 1/n) n log(1/δ)) of the empirical error with probability at least 1 − δ. Unfortunately, this bound does not lead to meaningful generalization bounds in many common settings where γ ≥ 1/ √ n. At the same time the bound is known to be tight only when γ = O(1/n). We substantially improve generalization bounds for uniformly stable algorithms without making any additional assumptions. First, we show that the bound in this setting is O( (γ + 1/n) log(1/δ)) with probability at least 1 − δ. In addition, we prove a tight bound of O(γ 2 + 1/n) on the second moment of the estimation error. The best previous bound on the second moment is O(γ + 1/n). Our proofs are based on new analysis techniques and our results imply substantially stronger generalization guarantees for several well-studied algorithms.
This paper develops new generalization bounds for algorithms that are uniformly stable. Specifically, the main results are an improved high probability bound on generalization error and an improved bound on the second moment on the generalization error. Both bounds to appear to be real improvements over past results and advance what is known about the generalization error of uniformly stable algorithms. The key tools used to prove the new results are from recent developments in differential privacy and adaptive data analysis. While many of the core techniques were established in previous works, the authors do go further to combine these techniques with a more learning-specific analysis to get their results, and I believe their supporting lemmas and proofs of their theorems represent non-trivial contributions.  An unfortunate weakness of this paper is that it provides only a blurry coverage of applications near the end of the Introduction, but all new results related to applications are hidden away in the appendix. New results do not belong in the appendix, and to expect reviewers to take them into account is to implicitly try to overcome the page limit. Therefore, with regards to applications, my review only considers whatever I could learn from the very high-level Applications section on page 4. I recommend the authors remove Appendix A from the paper, and that they try to develop at least one of the applications properly in the main text.   DETAILED REVIEW   In comparing the results of Theorem 1.2 to what was previously known from equations (2) and (3), I found this paper's results to be significant improvements. These results are foundational and I expect can be further built upon to get new results in specific (still theoretical) applications. On the whole, the paper is clear, but I recommend rewriting the Applications subsection as it was hard to get a clear view into the authors' results here as so much is packed in within a small space. A good tradeoff would be to move some of the proofs appearing in the main text into the appendix, allowing more space in the main text for formal statements of (some of the) Applications-related results. This will no doubt improve the impact of the paper as more people will see what the Theorem 1.2 can buy us in ``practice''. Also, the citations for Theorem 3.3 were not very clear. Some more guidance as to what parts of these papers have the stated result would help (I found them finally but after a lot of extra effort on my part).   Regarding the technical quality of the authors' results: The new technical results of the authors are Theorem 1.2 (consisting of inequalities (5) and (6)) and its supporting lemmas: Lemma 3.4, 3.5 ,and 4.1, and 4.2. I looked through the proofs of all these results. I believe the proofs of the lemmas and also inequaity (5) of Theorem 1.2 are all correct. The proof of inequality (6) of Theorem 1.2 also is generally fine, modulo some small typos / missing details that I ask the authors to include. Specifically:    1. On the 4th line of page 7, when you say ``By Lemma 3.5 we have that'' I think you should also mention that you are using the part of Theorem 3.3 that says that the exponential mechanism in this case is differentially private, as this is needed to apply Lemma 3.5.    2. When you say ``To bound this expression we choose $\epsilon =$ ...'', the second equality is only an inequality (it should be $\leq$), and only if you set $\epsilon$ to the RHS (the term with the $\ln(e \ln(2)/\delta)$) does the rest of the proof work. I suggest making this fix so that the proof is correct. In the second to last math display (in Proof of eq. (6) in Theorem 1.2), I wasn't able to see immediately how the inequality follows (even after using $\gamma \leq \sqrt{\gamma}$). Saying a little extra here could help.    3. I was able to myself construct the argument for why you need only consider the regime of $(e^\epsilon - 1) \leq 2 \epsilon$, but as stated, your explanation of ``Our bound is at least $2 \epsilon$ and hence...'' is not very clear and should be rephrased/expanded.   Last, while many of the core original tools were developed in previous works, I believe that some amount of ingenuity was needed on the parts of the authors to apply these tools in the right way to get their new results for uniformly stable algorithms. As these techniques are still relatively new to the learning theory community, I believe mixing them into this space provides significant value.     Minor corrections/points:  In Definition 2.2, I believe $S^{(i \leftarrow z_i)}$ should be replaced by $S^{(i \leftarrow z)}$  There are suspicious issues with missing line numbers thorughout the paper, but especially on page 7.     EXPERTISE OF REVIEWER  I am familiar with the fundamental developments related to algorithmic stability (and more generally, learning theory), although I am less aware of new contributions within the last year or so. Likewise, I am familiar with many of the techniques used in differential privacy and adaptive data analysis.   UPDATE AFTER READING THE REBUTTAL  You should reconsider leaving the current Applications section as is. I think it really is not useful and will hurt the impact of your paper. It is sad that you would leave a discussion of core selling points of your paper to the appendix. While a learning theorist may get excited, a large number of other readers will not. Also, things that "follow easily" to the authors may not follow so easily to a reader that is not an author of the work; please consider the perspective the reader.