Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper considers the problem of showing tight generalization bounds for randomized uniformly stable algorithms. The key contributions are the following:

1. The paper uses the framework of confidence-boosting to develop a generic procedure for amplifying the success probability in the generalization bound for a uniformly stable algorithm.

2. The paper then instantiates this bound for the important case of SGD, obtaining generalization bounds that hold in step sizes regime not covered by previous work.

3. Finally, the paper shows that though the framework is developed for randomized algorithms it obtains tighter bounds for deterministic algorithms as well.
main_review: Strengths:

1. The problem of showing tighter generalization bounds for uniformly stable algorithms has seen exciting work recently, and the paper makes solid contributions to this directions.

2. The paper is quite well-written. It discusses the prior work properly in context, provides sufficient intuition for their results and is generally quite easy to read.

3. It's nice that even thought the framework is developed for randomized algorithms, it yields some tighter bounds for previous deterministic settings as well. This makes it seem a bit less specialized.

Weaknesses:

1. Continuing from the previous point, one could argue that the results in the paper are a little bit specialized. They hold for a specific regime of SGD, and though the authors do provide context about the importance of the results, perhaps a bit more discussion, discussion of the open problem from previous work and how the paper is concretely making substantial progress on it would be helpful.

2. It's a bit unsatisfying that the bounds don't hold for SGD itself, but instead for the confidence boosted procedure which Alg. 1 develops. Do the authors believe that this is necessary? Is it possible to show the high-probability results for SGD itself?
summary_of_the_review: Overall, this is a well-written paper which uses interesting techniques and makes decent progress on an interesting problem, and hence I am in favor of acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper first establishes an in-expectation first moment generalization error bound for
randomized learning algorithm with on-average uniform stability, based on which
it then shows that a properly designed subbagging process leads to near-tight high
probability generalization bounds over the randomness of data and algorithm. It
further substantializes these generic results to SGD to derive improved high probability generalization bounds for convex or non-convex optimization with natural
time decaying learning rates, which have not been possible to prove with the existing uniform stability results.
main_review: The paper makes progress towards answering, for randomized
algorithms with on-average uniform stability, such as stochastic gradient descent
(SGD) with time decaying learning rates, wheter
these deviation bounds still hold with high confidence over the internal randomness of algorithm.

However clarity can be improved in showing how far paper's results are from lower bounds.
summary_of_the_review: The paper makes progress towards answering, for randomized
algorithms with on-average uniform stability, such as stochastic gradient descent
(SGD) with time decaying learning rates, wheter
these deviation bounds still hold with high confidence over the internal randomness of algorithm.

However clarity can be improved in showing how far paper's results are from lower bounds.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper establishes near-optimal high probability bound for randomized algorithms with on-average uniform stability. To this end, the authors use a confidence-boosting technique via a subbaging process. The authors then apply the derived generalization bound to SGD and the deterministic uniformly stable algorithm. The results reveal that their bounds improve the results of SGD in (Hardt et al., 2016) and the results in (Bousquet et al,. 2020) up to a $\log (N)$ term.
main_review: strengths :
(1.) This paper has nice writing and a clear organization.

(2.) Existing generalization bounds of randomized algorithms are often derived in expectation. Although some work uses the Chernoff bound of Bernoulli random variables to derive the high probability bound, the authors provide improved ones in this paper. 

(3.) I checked the proof, which seems to be solid.

Concerns:
(1.) The subbaging process requires an enormous computational complexity. When the authors apply it to SGD, it occurs to me that the high probability generalization bounds are derived for a variant of SGD, not the vanilla SGD. 

(2.) Some proof steps in Page 15 between $\mathbb{P}_{S,A_k}(\bar{(\mathcal{E}_1^k)})$ and $\frac{\delta}{2K}$ are confused. The authors can make a detailed explanation to improve their paper’s impact.

(3.) The authors discussed that Lemma 1 is inspired by (Bousquet et al,. 2020). In the proof of Lemma 1, Lemma 4, a basic lemma, is a first moment bound for a summation of random functions, while Theorem 4 in (Bousquet et al,. 2020) are derived for $p$-th moment bound with $p \geq 2$. I do hope the authors can explain why they derive the first moment bound. Is it an essential step to the proof? In my opinion, the $p$-th moment bound can be employed to derive $1/n$-type bound (Klochkov and Zhivotovskiy, 2021). The first moment bound may limit its application to derive sharper bounds.

summary_of_the_review: Overall, the authors proposed an interesting idea to improve the stability-based generalization bound for randomized algorithms. I thus tend to comment for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper:  This paper derives near-optimal high probability generalization bounds for randomized learning algorithms. To be specific, the authors establish an improved high probability generalization error bounds over the randomness of data and algorithm via confidence boosting method. The main novelty is they establish the in-expectation first moment generalization bound with mean (square) uniform stability for the randomized algorithm and then use subbagging technique to obtain the high-confidence bounds. In particular, their results can handle time-varying stepsize cases when applied to SGD.  The ideas are motivated by the confidence-boosting/bagging ideas in the literature. 
main_review: Comments:  

1. In Corollary 1 2 and 3, Consider Algorithm 1 specified to $A_{\text{SGD-w}}$ is unclear to me, and $\{A_{\text{SGD-w},k}\}$ is not defined. In my understanding, $A_{\text{SGD-w}, k^*} (S_{ k^* } )$ is the output of SGD with subbagging process in Algorithm 1, and Algorithm 2 is seems to redundant here. Did I imiss something ?

2.  In the proof of Corollary 1 2 and 3, the authors should clearly state that they put $\gamma_{m,N/K}$ and $\gamma_{m^2,N/K}$ instead of $\gamma_{m,N}$ and $\gamma_{m^2,N}$ back into Theorem 1, and the bounds are related to $K$ which cannot be ignored. In addition, in the statements of corollaries, setting $\alpha=1/2$â should be added. 

3. In Remark 6, choosing $K\asymp\log{(1/\delta)}$ and $\eta_t=1/\sqrt t$, the high probability generalization bound should be dominated by $O\left(\sqrt{\frac{\log{(T)}}{N}}+\frac{\sqrt T+\sqrt{N\log{(1/\delta)}}}{N}\right)$. 

4. In Remark 8, the stepsize is chosen to be $\eta_t = O({1\over t^{1+\nu}})$ which seems not right, since the stepsize should satisfy $\sum_{t=1}^\infty \eta_t =\infty$. Is this the artifact of the proof in the nonconvex case? 


Mirror comments: Page 4 paragraph 3, $\gamma_{m,N/K}$ and $\gamma_{m^2,N/K}$ have not been defined before. Page 12, in Lemma 4, $h_i$ should be $g_i$.
 

summary_of_the_review:  The paper proposed to use the confidence-boosting/bagging techniques to boost the dependence of learning algorithm from $1/\delta$ to $\log (1/\delta)$.  Specific applications to SGD are derived.   Overall, the paper is well written and the results are new and interesting.
review_title: null

Meta-review: Confidence boosting via aggregating multiple run of algorithms has been used before. The main result of the paper relies on a generic confidence boosting trick. The authors for instance cite Shalev-Schwartz et al 2010 theorem 26 in remark 4 of their paper and correctly point out that for deterministic algorithms like ERM one can use that for confidence boosting. While that theorem there is proved for excess risk and for deterministic algorithms, the main idea there to me seems like what is used in the authors paper as well. 

The basic idea: 
Property A holds in expectation, Hence use Markov inequality to get a low grade probability version of it in each of the K pieces
Now probability that at least one of the pieces is good is high since each piece is independent of the other
Finally aggregate with simple concentration with union bound.

In Shalev-Schwartz et al 2010 this is done with property being excess risk, here it is done with generalization error.

(Oh and I should add, the fact that the algorithm is randomized does not affect this line of reasoning as long as we use fresh randomness for each of the K blocks).

Now the missing piece covered is that on-average stability implies generalization in expectation. But isn’t this already known to be true in the stability literature? 

To me it seems like the main technical contribution of the paper is not as novel. Further, as one of the reviewers points out, the main goal should be to prove high probability guarantee for the algorithm popularly used like SGD not the confidence boosted version of it.

None the less, it seems like the application of the result to SGD seems interesting and somewhat new. 

I am reluctant to propose an accept here.
Decision: Reject