Stability and Sharper Risk Bounds with Convergence Rate $O(1/n^2)$

Authors: Bowei Zhu, Shaojie Li, Yong Liu
Primary area: learning theory
Keywords: algorithmic stability, generalization bounds, excess risk bounds, stochastic gradiet descent

Abstract:
The sharpest known high probability excess risk bounds are up to $O\left( 1/n \right)$ for empirical risk minimization and projected gradient descent via algorithmic stability (Klochkov \& Zhivotovskiy, 2021). In this paper, we show that high probability excess risk bounds of order up to $O(1/n^2)$ are possible. We discuss how high probability excess risk bounds reach $O(1/n^2)$ under strong convexity, smoothness and Lipschitz continuity assumptions for empirical risk minimization, projected gradient descent and stochastic gradient descent. Besides, to the best of our knowledge, our high probability results on the generalization gap measured by gradients for nonconvex problems are also the sharpest.

Decision: reject
Reviewer scores: 6, 8, 5, 5

Reviews and discussion:
<thread>
creation date:
1730088600872

thread_type:
official_review

<thread_object>
creator: reviewer_rdfx

<content>
summary:
The paper studied the algorithmic stability of the empirical risk minimization,  projected gradient descent, and SGD in the high probability form.
In particular, the authors show that  the rate $1/n^2$ can be achieved when the objective function is smooth and satisfied the PL condition (strongly convexity). The obtained results seems to the first of its kind in the literature.

strengths:
1. The paper seems to be the first-ever-known fast rate in high probability in the framework of algorithmic stability.

2.  The paper is generally well written with good organization.

weaknesses:
1.  While the results obtained are new and interesting, the proof techniques heavily reply on the existing literature (Klochkov & Zhivotovskiy, 2021) and specially Fan and Lei (2024). For instance, Theorem 1 is a refined version of Theorem 3 in Fan and lei (2024) by observing that the absolute constant  $M$ there can be replaced by the variance of the gradients of the loss.  The authors may need to further highlight  other technical novelty in the proof. 

2.  The existing literature on the fast rates for SGD using stability approach often focused on the one-pass SGD, i.e., $T=n$. Although the fast rate was obtained in this paper for SGD with PL and smooth condition here,  the paper needs high gradient complexity, i.e. $T=n^2$.  In this case, there is a compromise here to achieve fast rate $1/n^2$ there.

questions:
NA
</content>
</thread_object>

</thread>
<thread>
creation date:
1730097513286

thread_type:
official_review

<thread_object>
creator: reviewer_xmnk

<content>
summary:
The paper presents high-probability generalization bounds based on stability analysis. To this aim, the paper first presents a moment bound for sums of vector-valued functions of independent variables. Based on this, the paper gives a high-probability bound on the difference between the gradients of population risks and the gradients of empirical risks. This further implies excess risk bounds under a PL condition. The paper shows that this risk bound can be of order of $O(1/n^2)$ under some conditions. Further applications to empirical risk minimization, gradient descent and stochastic gradient descent are also given.

strengths:
- The paper shows improved generalization bounds based on stability analysis. The paper gives clear comparison with existing results. For example, Remark 4 and Remark 7 show the advantage of the derived generalization bounds over the existing results in Fan & Lei 2024 and Xu & Zeevi (2024).
- The paper also shows improved excess risk bounds over the existing results. For example, in Remark 9, the paper shows that the results outperform those in Zhang & Zhou by removing the dependency on the dimensionality. In Remark 11, the paper shows that it is better than Klochkov & Zhivotovskiy (2021) by allowing for rates of order $O(1/n^2)$.

weaknesses:
- While the rates of order $O(1/n^2)$ are interesting, it seems that the bounds have another linear dependency on $1/\mu^2$. For example, according to proof of Theorem 4, there is a missing factor of $1/\mu^2$ in each term on the right-hand side of the bound. Note $\mu$ is the PL parameter and can be very small in practice. This can make the derived bound less interesting in practice. 
- For applications in Section 4, the paper considers strongly convex problems. There is an assumption that $n\geq 16\gamma^2\log(6/\delta)/\mu^2$, which amounts to saying that $\mu \geq 4\gamma\log^{1/2}(6/\delta)/\sqrt{n}$. Note that typically one needs to introduce a strongly convex regularizer to get strong convexity. However, one is mostly interested in the original loss function without the regularizer. While the paper shows improved rates for the loss with the regularizer, the requirement $\mu \geq 4\gamma\log^{1/2}(6/\delta)/\sqrt{n}$ makes the rate for the loss without the regularizer still not fast. 
- For SGD, in Remark 13 the paper requires $T=n^4$ to get good bounds. This requirement on the number of iterations is a bit large. Then, the computational cost may be huge in this case.

questions:
- Can the results in Section 4 guarantee fast rates for the original loss without the regularizer? That is, whether we can transform the generalization bounds in Section 4 to get fast rates on the decay of the population risk without the regularizer?
- Lemma 3 is a bit strange. The left hand side involves w_t^i and w_t. However, the right-hand side only involves $\epsilon(w_t)$. The authors should check it.

Minor comments:
- "under strongly convexity" in Abstract
- $w^*$ is not defined in the introduction
- "inequality which provide" in Section 3
</content>
</thread_object>

</thread>
<thread>
creation date:
1730432618195

thread_type:
official_review

<thread_object>
creator: reviewer_9oqf

<content>
summary:
The authors provide dimension-free, $O(1/n^2)$-rate generalization bounds for learning algorithms with uniformly stable gradients. This is applicable to the ERMs of sufficiently well-behaved risk functions, as well as the gradient descent iterates of sufficiently well-behaved objective functions.

strengths:
- As summarized in Table 1 (which is very informative), the bounds for ERM, PGD, and SGD are indeed the sharpest in the literature, in particular in terms of the sample complexity.

- Overall the paper is very clearly written, including proof sketch, comparison etc.

weaknesses:
- Given the impressive results I do think this is a very minor weakness, but the technical novelty is indeed not *that* compelling. The main result is mostly derived from applying Klochkov and Zhivotovskiy's techniques to a more restrictive (in the sense of problem well-behavedness constraints) and more general (in the sense of studying the "oracle" $A$) set-up. This might potentially bar the paper from entering the conference highlight.

questions:
- Can the authors briefly comment on the implications for 1-dimensional mean estimation (w/ empirical mean, M-estimators, etc.)? This might be a good illustrative example.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730654721741

thread_type:
official_review

<thread_object>
creator: reviewer_kqxp

<content>
summary:
Th authors of the paper obtain high probability excess risk bounds of order up to $\mathcal{O}(1/n^2)$ (up multiplicative logarithmic factors) for both empirical risk minimization problems and gradient descent algorithms. Towards this aim, the authors consider uniform stability in gradients instead of uniform stability of the loss function itself.

strengths:
The paper is well-written and main contributions are clearly articulated. The fact that the bounds for ERM and SGD setting do not require lower bounding the sample size $n$ in terms of the problem dimension $d$ is also a significant improvement, for example, over, [Xu & Zeevi, 2024].

weaknesses:
The technical novelty of the results is limited. Essentially the proof is based on an appropriate combination of [Zhang & Zhou, 2019] and [Klochkov & Zhivotovskiy, 2021]. Moreover, the excess risk of order $\mathcal{O}(1/n^2)$ can be obtained only in the setting $F(w*) = \mathcal{O}(1/n)$, that is, provided that the noise-at-the-optimum is rather small. The tail bound of order $\log^2(1/\delta)$ in Theorems $4$ - $6$ (in front of $1/n^2$ terms) also seems to be not optimal. For example, this $\log^2(1/\delta)$ regime does not appear in [Klochkov & Zhivotovskiy, 2021].

questions:
Is it possible to improve scaling of the right-hand side in Theorems $4-6$ with $\log(1/\delta)$?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732184697091

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Public Response (Part I)

comment:
Dear Reviewers,

Thank you very much for your thoughtful and thorough review of our manuscript. We sincerely appreciate the time you have dedicated to providing constructive feedback, which has been invaluable in refining our work.

In this response, we would like to emphasize our contributions and engage with the concerns raised regarding the novelty of both our results and our proof techniques.


# Novelty of Our Results


1. Our results are asymptotically optimal, which aligns with existing theories. For instance, in the case of ERM, according to the classical asymptotic theory, under some local regularity assumptions, when $ n \rightarrow \infty $, it is shown in the asymptotic statistics monographs (Vaart, 2000) that 
$$
    \sqrt{n} (\hat{w}^*(S) - w^*) \stackrel{\rho}\longrightarrow N(0, H^{-1}Q H^{-1}),
$$
where $ \hat{w}^*(S) $ denotes the ERM algorithm, $ H = \nabla^2 F(w^*) $, $Q$ is the covariance matrix of the loss gradient at $w^*$ (also called Fisher's information matrix): $ Q = \mathbb{E} [\nabla f(w^*; z) \nabla f(w^*; z)^T ] $
($A^T$ denotes the transpose of a matrix $A$), and $\stackrel{\rho}\longrightarrow$ means convergence in distribution. The second-order Taylor expansion of the population risk around $w^*$ then allows to derive the same asymptotic law for the scaled excess risk $ 2n (F(\hat{w}^*(S)) - F(w^*)) $. Under suitable conditions, this asymptotic rate is usually theoretically optimal (Vaart, 1989). For example, when $f(w;z)$ is a negative log-likelihood, this asymptotic rate matches the Hajek-LeCam asymptotic minimax lower bound (Hajek, 1972; LeCam, 1972).
We then analysis the result in Theorem 5. In the proof of Theorem 4, before we use the self-bounded smoothness property $ || \nabla f(w^*;z) ||^2 \leq 4 \gamma f(w^*;z) $, we get the following result for Theorem 5
$$
    F(\hat{w}^*(S)) - F(w^*) \lesssim \frac{ \mathbb{E}[ ||\nabla f(w^*;z)||^2 ] \log(1/\delta)}{\mu n} + \frac{\log^2 (1/\delta)}{n^2}.
    $$
Our result is the finite sample version of the asymptotic rate given above, which characterizes the critical sample size sufficient to enter this ``asymptotic regime''. This is because the excess risk error $F(\hat{w}^*(S)) - F(w^*)$ can be approximated by the quadratic form $ (\hat{w}^*(S) - w^*)^T H (\hat{w}^*(S) - w^*) $. $ 1/\mu $ is a natural proxy for the inverse Hessian $H^{-1}$, and $\mathbb{E}[ ||\nabla f(w^*;z)||^2 ]$ is a natural proxy for Fisher's information matrix $Q$.
Furthermore, when discussing sample complexity, (Xu \& Zeevi, 2024) constructed a simple linear model to demonstrate the constant-level optimality of the sample complexity lower bound $\Omega(d \beta^2/\mu^2)$ under such conditions. Our theorem further reveals, through the use of stability methods, that this complexity lower bound can be independent of the dimensionality $d$.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper derives high-probability generalization bounds based on stability. The main contribution of this work is a risk bound of order O(1/n^2) under certain conditions. Further, authors discuss implications to ERM problems, gradient descent and SGD.

This paper was reviewed by four reviewers and received the following Scores/Confidence: 5/5, 5/3, 6/3, 8/3. I think paper is studying an interesting topic, and the results are intriguing but authors are not able to convince half the reviewers sufficiently well about the technical novelty. The following concerns were brought up by the reviewers:

- Results in this paper can be derived by a straightforward combination of existing work. This limits the technical contribution/novelty significantly given that this is the main contribution.
- Dependence on the PL constant is not good. The overall rate depends quadratically on this parameter, which can be extremely small in practice.
- Conditions and their practical implications are not sufficiently discussed in the paper.

  
Three reviewers are not particularly excited about the paper. As such, based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend not including this paper to the ICLR 2025 program.