Thank you for your review. Here are the replies for your questions.

Question 1: As mentioned in Weaknesses, 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.

Answer: Regarding the example you mentioned, it is true that, our result in Theorem 3 improves upon the conclusion of (Fan and Lei, 2024, Theorem 3) by showing that the absolute constant $M$ can be replaced with the variance of the gradients of the loss. However, achieving this improvement is not straightforward. Inspired by (Klochkov & Zhivotovskiy, 2021), but it is essential to note that prior work predominantly focuses on one-dimensional random variables. Our approach, however, confronted additional complexities due to the involvement of random vectors and their norms. In one-dimensional cases, the condition of a variable value being $0$ is equivalent to its absolute value being $0$. However, the Euclidean norm of a vector being $0$ does not imply that the vector itself is the $0$ vector, adding significant complexity to our proof. This distinction necessitated a more nuanced analysis during the proofs.

Beside, for Theorem 1, in our writing, we discovered that the constant in Marcinkiewicz-Zygmund's inequality for random variables taking values in a Hilbert space could be further improved. Consequently, we included this part in the paper. Considering that Theorem 1 has other broad applications, we report this result as well. Although it is the constant-level improvement. The proof was challenging, as it involved establishing the best constant in Marcinkiewicz-Zygmund's inequality for random variables taking values in a Hilbert space, which has its foundations in Khintchine-Kahane's inequality. To prove the best constant, we utilized Stirling's formula for the Gamma function to construct appropriate functions, establishing both upper and lower bounds. Then using Mean Value Theorem, this approach ultimately led to the convergence of the constant as $p$ approaches infinity.

For Theorem 4, the proof for this theorem primarily exploits the self-bounded properties of functions, facing challenges akin to those highlighted in Theorem 3, related to the interaction between the norms $|| \cdot ||$ and the expectation symbol $\mathbb{E}$. While we can sometimes apply the Jensen's inequality, there are instances where we must innovatively navigate around such relationships within the function construction. This complexity does not arise for scalar variables, and we think that this provide a pathway for future inquiries into the stability of algorithms involving vector norm considerations.

In addition to the technical novelty mentioned above, as Reviewer 9oQf noted in 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 terms of problem well-behavedness constraints) and more general (in terms of studying the 'oracle' $A$) setup. This might potentially bar the paper from entering the conference highlight.

The novelty of our results are also important. We also highlight the novelty of our work for the results in public response. Notably, our results are asymptotically optimal, which align with existing theories. We not only provide a more precise stability analysis tool under PL conditions, but we also offer new and improved insights into the relationship between algorithm stability and generalization in non-convex settings (Theorem 3). This has potential applications in non-convex scenarios as well.

Dear Reviewer RDFx,

We hope this message finds you well. We are writing to follow up on the rebuttal we submitted several days ago. We wanted to check in to see whether it has addressed your concerns.

If there are any remaining questions or if there are new issues you would like to discuss, please feel free to reach out. We appreciate your feedback and am eager to ensure that all aspects of the paper meet your expectations. Thank you for your time and consideration.

Best regards,

Authors

Thank you for your review. We want to emphasize that the advancements in the relationship between stability and generalization are limited recent years. Most papers focus on utilizing stability tools to address application problems or to explore the stability of specific algorithms. In contrast, our analysis of stability bounds dependent on optimal parameters is an improvement in this area. We also highlight the novelty of our results and the technical innovations in public response. Here are the replies for your questions.

Question 1: As mentioned in 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.

Answer: Our Theorem 4 only requires that the population risk $F$ satisfies the PL condition with parameter $\mu$, which is relatively weak. In fact, $\mu$ can be viewed as a constant in some cases within classical learning theory. For instance, consider the classical linear regression setup: $f(w; (x,y)) = || y - \langle w, x \rangle ||^2$, where $y = \langle w^*, x \rangle + v$, with $v \sim N(0, 1)$ and $x \sim N(0, \sigma I_{d \times d})$. In this case, we have $\mu = 2$.

Dear Reviewer XMnk,

We hope this message finds you well. We are writing to follow up on the rebuttal we submitted several days ago. We wanted to check in to see whether it has addressed your concerns.

If there are any remaining questions or if there are new issues you would like to discuss, please feel free to reach out. We appreciate your feedback and am eager to ensure that all aspects of the paper meet your expectations. Thank you for your time and consideration.

Best regards,

Authors

3. Regarding general machine learning setting, as you pointed out, regularization is often necessary. We provide a discussion concerning the hyperparameters of the regularizer. As detailed in the first point, the essence of the strong-convexity assumption is that $F_S$ must satisfy a PL condition (or satisfy that PL condition with high probability). Considering the empirical risk with a regularizer, $F_S(w) = \frac{1}{n} \sum_{i=1}^n f(w;z_i) + \frac{\mu}{2} ||w||_2^2$, suppose $\mu \asymp n^{-\alpha}$ with $\alpha \in [0, \frac{1}{2})$. Using PGD as an example, we substitute into the proof in Section 4 and derive the following result:

This indicates that the sample complexity requirement becomes $n^{1-2\alpha} = \Omega \left(16 \gamma^2 \log \left(\frac{6}{\delta}\right) \right)$, while our results can achieve $O(1/n^{2 - \alpha})$ when $F(w^*) = O(1/n)$. Furthermore, when $\alpha = 0$, that is, when $\mu$ is independent of $n$, our results can tightly reach $O(1/n^2)$. When $\alpha \in (0, \frac{1}{2})$, our results are also the best currently available. For comparison, the existing stability generalization error bounds $R_S(A(S)) - R(A(S))$ given by [Agarwal and Niyogi, 2009; Jin et al., 2009; Wang et al., 2019] are of the order $O( 1/n^{\frac{1}{2} - \alpha} )$, while the excess risk bound $R(A(S)) - R(w^*)$ given by [Klochkov and Zhivotovskiy, 2021] is of the order $O(M/n^{1 - \alpha})$ under strongly convexity.

4. Finally, we want to emphasize that the core idea of this paper is to provide finer analytical tools for stability and generalization. As we discussed in the rebuttal and paper, our results perform better than existing ones under the same assumptions. We have also discussed the optimality of our results in the latest version. Our method can achieve rates as high as $O(1/n^2)$ depending on the optimal parameters. As the saying goes, "no free lunch"; attaining such a fast rate is not simple and often necessitates some assumptions. Compared to other papers that achieve fast rates, our approach delivers tighter bounds without introducing more stringent assumptions. % We think it somewhat unreasonable to overly emphasize scenarios where our assumptions may not hold.

We hope this clarifies our reasoning and addresses your concerns adequately. Thank you once again for your insights. If we haven't explained things clearly or if you have any questions, please feel free to reach out to us.

Reference

Marchenko, V. A.; Pastur, L. A. Distribution of eigenvalues for some sets of random matrices. in Mat. Sb. N.S. (in Russian) 1967.

S. Agarwal and P. Niyogi. Generalization bounds for ranking algorithms via algorithmic stability. JMLR 2009.

R. Jin, S. Wang, and Y. Zhou. Regularized distance metric learning: Theory and algorithm. NeurIPS, 2009.

B. Wang, H. Zhang, P. Liu, Z. Shen, and J. Pineau. Multitask metric learning: Theory and algorithm. AISTATS, 2019.

Y. Klochkov, and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate $O(1/n)$. NeurIPS 2021.

Thank you for your review. Here are the replies for your questions.

Question 1: As mentioned in 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.

Answer: Thank you for recognizing our work. In public response, we highlight the novelty of our work, particularly focusing on both the novelty of the results and the techniques employed. Notably, our results are asymptotically optimal, which align with existing theories. We not only provide a more precise stability analysis tool under PL conditions, but we also offer new and improved insights into the relationship between algorithm stability and generalization in non-convex settings (Theorem 3). This has potential applications in non-convex scenarios as well.

Question 2: As mentioned in 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.

Answer: In our first application, Empirical Risk Minimization (ERM) can be regarded as a specific type of M-estimation (Sen, 2018), where the objective function is defined based on the empirical risk derived from the training data. In this sense, ERM represents a particular case of M-estimation that focuses specifically on minimizing the empirical average of a loss function. When our objective function satisfies the assumptions outlined in Theorem 5 (namely, being Lipschitz continuous, strongly convexity and smoothness), we can substitute the corresponding parameters into Theorem 5 to arrive at our conclusion.

Reference

Bodhisattva Sen. A gentle introduction to empirical process theory and applications. Lecture Notes Section 1.2, Columbia University 11 (2018): 28-29.

Thank you for your review. Here are the replies for your questions.

Question 1: As mentioned in 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].

Answer: We appreciate your feedback regarding the perceived novelty of our proofs and results. In public response, we have provided a detailed explanation of the novelty of our results, as well as the innovative aspects of our proof techniques. Notably, our results are asymptotically optimal, which align with existing theories. We not only provide a more precise stability analysis tool under PL conditions, but we also offer new and improved insights into the relationship between algorithm stability and generalization in non-convex settings (Theorem 3). This has potential applications in non-convex scenarios as well. We believe these innovations warrant consideration and appreciate your understanding.

Question 2: As mentioned in Weaknesses, moreover, the excess risk of order $O(1/n^2)$ can be obtained only in the setting $F(w^*) = O(1/n)$, that is, provided that the noise-at-the-optimum is rather small.

Answer: Thank you for your valuable feedback. We appreciate your insights regarding the bounds we presented in our work. It is important to clarify that our upper bound of $O(1/n^2)$ is dependent on optimal parameters, but this does not imply poorer performance under alternative conditions. For instance, using PGD algorithm, the result in (Klochkov & Zhivotovskiy, 2021) is

As a comparison, under the same assumptions (including the same iteration step $T = O(\log n)$), our result in Theorem 6 is

As long as $F(w^*)$ converges as $n$ increases, our result outperforms better. Even when $F(w^*) = O(1)$, our PGD result remains comparable to those presented by (Klochkov & Zhivotovskiy, 2021). Similarly, in the case of SGD, (Li & Liu, 2021) demonstrated an upper bound of $O(1/n)$ using stability methods when $T = n^2$. In contrast, our Theorem 8 yields an optimal upper bound

Dear Reviewer KqxP,

We hope this message finds you well. We are writing to follow up on the rebuttal we submitted several days ago. We wanted to check in to see whether it has addressed your concerns.

If there are any remaining questions or if there are new issues you would like to discuss, please feel free to reach out. We appreciate your feedback and am eager to ensure that all aspects of the paper meet your expectations. Thank you for your time and consideration.

Best regards,

Authors

Thank you for your constructive feedback. We greatly appreciate your time and effort in reviewing our work. Your comments have been invaluable in helping us refine our manuscript.

2. Currently, advancements in the relationship between stability and generalization are limited; most papers focus on utilizing stability tools to address application problems or to explore the stability of specific algorithms. In contrast, our analysis of stability bounds dependent on optimal parameters is an improvement in this area. Best result given by (Klochkov & Zhivotovskiy, 2021, Theorem 1.1) is

In constrast, our result in Theorem 4 is

We can see that when the algorithm optimization is sufficiently effective (i.e., $F_S(A(S)) - F_S(w^*(S)) = 0, \nabla F_S(A(S)) = 0$), our conclusions, despite requiring additional smoothness and PL conditions, provide a more granular analysis dependent on optimal parameters.

For instance, when the algorithm's stability $\beta = O(1/\sqrt{n})$ the upper bound, according to (Klochkov & Zhivotovskiy, 2021), can at most reach the order of $1/\sqrt{n}$ due to the algorithm's stability constraints. In contrast, our result shows that even under the assumption that $F(w^*) = O(1)$, treating $F(w^*)$ as a constant, we can achieve an order of $1/n$.

Next, we discuss the fast rates of stability methods by considering a specific, more stable algorithm, denoted as $\beta = O(1/n)$, our results simplify to $\frac{F(w^*)}{n} + \frac{1}{n^2}$. In contrast, the results from (Klochkov & Zhivotovskiy, 2021) yield $\frac{1}{n}$ (omitting logarithmic terms). This indicates that existing results cannot surpass the $\frac{1}{n}$ barrier, while our conclusions can tighten as the condition on $F(w^*)$ becomes stronger. For example, when $F(w^*) = O(\frac{1}{\sqrt{n}})$, our results can achieve a rate of $O(\frac{1}{n^{3/2}})$. In other words, as long as $F(w^*)$ converges as $n$ increases, our results outperform existing ones. Even in cases where $F(w^*) = O(1)$, which is a constant independent of $n$, our results are comparable to those presented by (Klochkov & Zhivotovskiy, 2021).

On the other hand, while it may seem that we have introduced additional smoothness and PL conditions, extensive research on specific algorithms shows that, to maintain good stability with high probability, smoothness and strong convexity conditions are almost essential—for instance, (Klochkov & Zhivotovskiy, 2021) for PGD. Essentially, we are effectively utilizing the smoothness and PL conditions to explore the relationship between stability and generalization error. Thus, when addressing the ultimate problem, we achieve better results without adding extra conditions.

Finally, this approach can be seamlessly extended to various areas, such as differentially private models, pairwise learning, minimax problems et al., leading to more refined, parameter-dependent stability bounds across a wider array of algorithms.

3. Our methodology has the potential for extensive applications. For application, we have achieved the best current results for empirical risk minimization (ERM), projected gradient descent (PGD), and stochastic gradient descent (SGD). It is important to clarify that our upper bound of $O(1/n^2)$ is based on optimal parameters; however, this does not imply poorer performance under alternative conditions. As discussed in the second point, the original method requires the algorithm's stability to be on the order of $1/n$ in order to achieve an upper bound of $1/n$. In contrast, our approach only necessitates that the specific algorithm's stability is at the order of $1/\sqrt{n}$ to reach the same $1/n$ upper bound. This means our method is less dependent on assumptions in practical applications.

4. We also see potential applications of our approach in non-convex settings. While we focused primarily on maintaining the readability of our manuscript, which limits the discussion about non-convex settings in Remark 4. We admit that exploring high-probability stability for specific algorithms in non-convex setting is indeed challenging. However, our core result (Theorem 3) does not rely on convexity assumptions, making it an invaluable tool for discussing algorithm stability and generalization error bounds in non-convex settings.

Novelty in Proof Techniques

1. For Theorem 1, in our writing, we discovered that the constant in Marcinkiewicz-Zygmund's inequality for random variables taking values in a Hilbert space could be further improved. Consequently, we included this part in the paper. Considering that Theorem 1 has other broad applications, we report this result as well. Although it is the constant-level improvement. The proof was challenging, as it involved establishing the best constant in Marcinkiewicz-Zygmund's inequality for random variables taking values in a Hilbert space, which has its foundations in Khintchine-Kahane's inequality. To prove the best constant, we utilized Stirling's formula for the Gamma function to construct appropriate functions, establishing both upper and lower bounds. Then using Mean Value Theorem, this approach ultimately led to the convergence of the constant as $p$ approaches infinity.

2. For Theorem 3, although this theorem is inspired by (Klochkov & Zhivotovskiy, 2021), it is essential to note that prior work predominantly focuses on one-dimensional random variables. Our approach, however, confronted additional complexities due to the involvement of random vectors and their norms. In one-dimensional cases, the condition of a variable value being $0$ is equivalent to its absolute value being $0$. However, the Euclidean norm of a vector being $0$ does not imply that the vector itself is the $0$ vector, adding significant complexity to our proof. This distinction necessitated a more nuanced analysis during the proofs.

3. For Theorem 4, the proof for this theorem primarily exploits the self-bounded properties of functions, facing challenges akin to those highlighted in Theorem 3, related to the interaction between norms $|| \cdot ||$ and expectation symbols $\mathbb{E}$. While we can sometimes apply the Jensen's inequality, there are instances where we must innovatively navigate around such relationships within the function construction. This complexity does not arise for scalar variables, and we think that this provide a pathway for future inquiries into the stability of algorithms involving vector norm considerations.

We hope that our detailed response helps clarify the novelty and significance of our manuscript. We are grateful for your insights and look forward to your feedback.

Authors

Reference

Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.

And W Van der Vaart. On the asymptotic information bound, The Annals of Statistics (1989) 1487-1500.

Jaroslav Hajek. Local asymptotic minimax and admissibility in estimation. Berkeley symposium on mathematical statistics and probability, Volume 1: Theory of Statistics. 1972.

L Le Cam et al. Limits of experiments. Berkeley symposium on mathematical statistics and probability, Volume 1: Theory of Statistics. 1972.

Yunbei Xu and Assaf Zeevi. Towards optimal problem dependent generalization error bounds in statastical learning theory. Mathematics of Operations Research 2024.

Yegor Klochkov, and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with convergence Rate $O(1/n)$. NeurIPS 2021.