We propose a change-of-measure framework based on the data-processing inequality (DPI) for deriving novel high-probability generalization bounds for general learning algorithms. Compared to classical bounds based on Rademacher complexity or covering numbers, which often require sophisticated task-specific bounding techniques, our bounds are easy to evaluate and effective. Furthermore, our framework allows one to produce a family of generalization bounds by adopting different DPI-based change of measure inequalities and different assumptions on the loss function. We evaluate our bounds for examples of Gaussian mean estimation, linear regression, and multiclass classification with deep neural networks. Compared to state-of-the-art bounds from prior literature, our bounds provide significantly tighter guarantees at practically relevant sizes of the training dataset.
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.Reviewer_v8Y8OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary
This paper proposes a data-processing inequality framework for high-probability uniform generalization bounds under Lipschitz continuity and uniformly sub-Gaussian or sub-exponential losses. An auxiliary distributions around worst-case hypotheses yield explicit bounds depending on parameter dimension, norm, and loss constants. A peeling argument extends the results to unbounded parameter spaces. Experiments compare the resulting bounds with existing guarantees on Gaussian mean estimation, linear regression, and CNN classification.
Critical strengths
These bounds have explicit constants and are straightforward to evaluate once valid loss parameters are available.
I find the auxiliary-distribution construction provides a coherent proof strategy that separates the analyzed learning algorithm from the distributions introduced for the analysis.
The sub-exponential extension and detailed appendices broaden the treatment beyond bounded losses.
Critical weaknesses
To the best of my knowledge, the theoretical contribution is insufficiently distinguished from existing PAC-Bayes smoothing arguments. Under the same global assumptions, take
\rho_w=\operatorname{Unif}(B_p(w,\beta)).$$
For $w\in B_{W_*,p}$, the KL divergence is $d\log(1+W_*/\beta)$. An exponential-moment bound, Markov’s inequality, the KL variational inequality, and Lipschitz control of the smoothing error give
$$L(w)-\widehat L(S,w)
\le
2C_{\ell,p}\beta+
\sqrt{\frac{2\sigma_\ell^2}{n}
\left[d\log(1+W_*/\beta)+\log(1/\delta')\right]}$$
simultaneously over the ball, with probability at least $1-\delta'$. Applying the paper's radius-peeling argument recovers Theorem 1 with a slightly smaller confidence constant.
The paper therefore needs to identify what substantive result the DPI formulation adds beyond this construction. The Gaussian auxiliary-distribution branch is looser. The discussion of deterministic algorithms also understates existing PAC-Bayes approaches: auxiliary perturbations have already been used to bound the risk of the original deterministic predictor, including in Neyshabur et al. (ICLR 2018).
2. I find the neural network experiments provide limited evidence of practical usefulness. All reported DNN bounds are vacuous. For CNN-3-100, the stated parameter count is $d=129400$; at $n=60000$, the complexity term in Corollary 1 is already at least
$$\sqrt{\frac{129400\log(1+\sqrt{60000})}{120000}}
\approx2.44,$$
using only $W(w)\ge1$ and $\gamma\ge1$. Thus, this configuration cannot provide a nonvacuous classification-risk guarantee. The sample threshold obtained by fixing model parameters and empirical statistics is an algebraic extrapolation, not an established learning sample complexity. It limits the practical significance claimed here.
Questions for authors
Does the KL smoothing construction above recover Theorem 1? What substantive theoretical contribution remains beyond this construction and existing perturbation-based PAC-Bayesian analyses? Please also clarify whether the sub-exponential extension offers a distinction beyond applying the corresponding exponential-moment bound in the same KL argument.
Appendix D establishes the CNN Lipschitz constant on the spectrally constrained parameter set, whereas Proposition 1 uses auxiliary distributions supported on full parameter balls. How are parameters outside the constrained set handled? Would a projection-based extension justify the stated bound for spectrally constrained networks?
We thank the reviewer for their comments. We addressed them below and revised the paper with changes highlighted in blue.
Weakness 1 and Question 1
Answer: Thanks for the interesting suggestions, we plan to look into that and compare to our results. Additionally, just plugging in the expectation will result in a bound of a different form. And we still think our framework is useful due to its potential of yielding more bounds (we have specified them in Future Work section).
Weakness 2
Answer: Our bound is significantly tighter than other bounds from previous literature under practical DNNs examples. The threshold sample size calculation is just want to show that our bound need significantly less number of training sample to become non-vacuous compared with other bounds if we fixed other quantities. But we agree there is a more reasonable way to present. Therefore, based on your suggestion we evaluate further our bounds and other comparable bounds on a synthetic binary classification task (see Appendix F for more details) using CNN. As shown in Figure 5, our bound requires much fewer training samples than existing bounds to become non-vacuous.
Questions 2: Appendix D establishes the CNN Lipschitz constant ....
Answer: Selecting PW∣S and QW as two uniform balls in Proposition 1 is our proof technique, which has nothing to do with imposing restrictions on the hypotheses or hypothesis space used in practice. Additionally, by applying Lemma 5, we can remove the restriction on the radius of the hypothesis space and then make our bounds hold for all $ w\in\mathcal W$.
Critical Weakness 1: The discussion of deterministic algorithms also understates existing PAC-Bayes approaches.....
Answer: Thank you for highlighting this reference. So we added Table 6 in Appendix E, which compares our bound with [1]. Although both bounds have the same convergence rate with respect to n, our bound has a more favorable dependence on the product of layer-wise spectral norms. In particular, the dependence on this product is O(∏i=1L∥A(i)∥2) in [1], compared with O(log(∏i=1L∥A(i)∥2)) in our bound. Additionally, their bound is formulated for fully connected neural networks (FNNs), whereas our bound applies to both FNNs and convolutional neural networks (CNNs). The numerical example in Section~4.3 demonstrates its application to CNNs. Additionally, we also added a sentence discussing it at our related work section.
Reference:
[1] Neyshabur, B., Bhojanapalli, S., & Srebro, N. (2018). A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks. International Conference on Learning Representations.
The paper proposes a data-processing-inequality framework for deriving high-probability uniform generalization bounds over continuous hypothesis spaces. Under parameter-Lipschitz continuity and sub-Gaussian or sub-exponential assumptions on the loss, the authors obtain generalization bounds and evaluate them on Gaussian mean estimation, linear regression, and convolutional neural networks.
Critical strengths
The goals of the paper are clear, and the proof strategy is interesting. Despite the use of DPI for generalization error analysis in countable hypothesis spaces, the author adopts the same approach to derive high-probability uniform generalization bounds for continuous hypothesis classes. I find the proof techniques nice; however, I am not convinced by the obtained results. Please see the section below for the reasons why.
Critical weaknesses
I list below what I have identified as critical weaknesses.
The proposed bound retains an explicit dependence on the parameter dimension d, more precisely, the generalization error bounds go approximately as d/n, multiplied by logarithmic factors. This remains a substantial obstacle in overparameterized settings. Indeed, the reported DNN bounds are vacuous, as the authors acknowledge. Numerically improving a vacuous bound does not by itself establish that the result provides useful guarantees or new insight into generalization. Therefore, the paper should clarify what substantive insight the proposed bound provides beyond these existing approaches, and identify regimes where its improvement yields an informative guarantee.
As part of the contributions (line 064), the authors claim that their bound can be evaluated directly. However, the evaluation of the bound involves the computation of a Lipschitz constant. A tight estimation of this constant is known to be a very hard problem, and general upper bounds are very loose. Therefore, the sentence "our bounds can be evaluated directly" is a bit strong. Also, the one proposed in the deep convolutional network is, in general, loose since it depends exponentially on the depth L.
Assumption 2 requires the loss to be Sub-Gaussian. If the loss is bounded, this assumption is automatically satisfied, but if the loss is not bounded, such as MSE, this assumption is quite strong. For instance, consider the case when the inputs are iid subgaussian and the model is Lipschitz, this kind of concentration is not guaranteed without additional assumptions, such as each coordinate satisfying a log-Sobolev inequality.
The proof sketch and appendix need a clearer explanation of the argument. The proof sketch of Theorem 1 is difficult to follow without consulting the appendix. In particular, the events A, DS, and E, and the choices of auxiliary distributions, are not specified explicitly enough in the main text. A proof sketch should provide the key intuition behind the proof in a more understandable way. The appendix should be more structured, and the explanation of the proof strategy should be improved; it is very hard to follow, and the exposition is not linear in the steps (recall partial objects appearing in the results above). So far, the preliminary results look like a sequence of results without explanation or comments.
The section from lines 257 to line 281, should go in a future work section after discussion.
The experiments illustrate the framework but do not establish its practical advantage: the DNN bounds remain vacuous, while the Gaussian mean-estimation experiment uses only d=2, hiding the bad scaling in the dimension d. The baseline selection also needs clarification. Section 4.3 evaluates the third inequality of Theorem 3.1 in [1]; the authors should also evaluate the second, which has milder dependence, wherever its applicability condition holds, or explain its exclusion. Finally, the regression input mean of 1000 worsen the selected norm-based baselines, but it is unclear if there is any advantage of their bound for smaller input means.
References: [1] Long, P. M., & Sedghi, H. (2019). Generalization bounds for deep convolutional neural networks. arXiv preprint arXiv:1905.12600.
Questions for authors
Below are my questions.
Given the explicit dependence on the dimension d, the generalization error is vacuous in the overparametrized settings, and the presence of the Lipschitz constant Cℓ,p, which is hard to estimate tightly. What is the message here? What is the advantage of this approach over covering numbers? Why would you say that the proposed bound is interesting for the machine learning community if it fails for deep overparametrized neural networks due to the dependence on d and it does not provide any additional insight than classical covering arguments?
The logarithmic dependence on the Lipschitz constant is potentially beneficial: an estimate growing exponentially with depth contributes only linearly in depth inside the logarithm, which subsequently appears under a square root. However, this mechanism is not unique to the proposed framework. Can you compare your generalization bound with the one presented in Theorem 3.1 in [1], which exhibits the same dependence on L,d and n but is based on a covering argument?
Can you comment a bit the points in weaknesses?
References: [1] Long, P. M., & Sedghi, H. (2019). Generalization bounds for deep convolutional neural networks. arXiv preprint arXiv:1905.12600.
We thank the reviewer for their comments. We addressed them below and revised the paper with changes highlighted in blue.
Weakness 1.The proposed bound retains an explicit dependence on the parameter dimension...
Answer: We have added Table 6 to Appendix E to compare our bound with existing bounds in terms of their convergence rates with respect to the sample size n and their leading dependence on network quantities that evolve during training. Apart from the tightest guarantee demonstrated in numerical experiments,
as shown in the table, our bound offers two
advantages.
First, compared with [2] and [3] it depends logarithmically on the product of
layer-wise spectral norms, whereas this product appears as a
multiplicative factor in several existing bounds. These products are always substantially larger than the parameter dimension d, which explicitly explain the reason why our bound is tighter than the bounds of [2] and [3].
Second, our bound is straightforward
to evaluate.
Compared with [1], all numerical constants are explicit, and its evaluation does not require the constraints on the initialization.
Regarding d: d dependence also shows up in the bound in 4th row of the bound [1]. Indeed, there are no extra d terms in [2] and [3], but the reason that our bound is still much tighter than them is the logarithmic dependence on the product of layer-wise spectral norms.
Reference:
[1] Long, P. M., & Sedghi, H. (2019). Generalization bounds for deep convolutional neural networks. arXiv preprint arXiv:1905.12600.
[2] Graf, F., Zeng, S., Rieck, B., Niethammer, M., & Kwitt, R. (2022). On measuring excess capacity in neural networks. Advances in Neural Information Processing Systems, 35, 10164-10178.
[3] Galanti, T., Xu, M., Galanti, L., & Poggio, T. (2023). Norm-based generalization bounds for sparse neural networks. Advances in Neural Information Processing Systems.
Weakness 2. As part of the contributions (line 064)...
Answer: We agree with your point, and we have now change the way for presentation.
In the summary of our contribution we have added: 'our bounds can be evaluated directly without introducing extra complexity measures given the specified Lipschitz constant and MGF parameters.'
Agree with the reviewer, point out that the Lipschitz constant is a standard assumption, and acknowledge it can be hard to estimate. Additionally, even though all of the bounds we compared in DNNs examples (including our bound) depend exponentially on the depth L, ours shows a much slower growth rate compared with other bounds (See Figure 4 in our paper). Additionally, as we state in Q1, our bound depends logarithmically on the product of
layer-wise spectral norms, whereas this product appears as a
multiplicative factor in several existing bounds.
Weakness 3. Assumption 2 requires the loss to be Sub-Gaussian...
Answer: We thank the reviewer for highlighting this limitation. We have expanded the future-work discussion to emphasize weakening the Lipschitz and concentration assumptions.
But we clarify that many loss functions satisfy the Sub-Gaussian assumption, including bounded losses (hinge loss, ramp loss, and 0-1
loss) and unbounded losses (e.g., absolute-error loss and Euclidean loss used in our Gaussian mean estimation example). Additionally, Theorem 2 can also work with losses that satisfy the sub-exponential assumption (huber loss), broadening the applicability of our framework.
Concretely, Example 1 at Section 4.1 provides an example where the input is Gaussian, and the loss is sub-Gaussian. Our Theorem 2 can also handle non sub-Gaussian (but sub-exponential) assumption.
Weakness 4. The proof sketch and appendix need a clearer explanation...
Answer: Thanks for your suggestions. To improve the readability of the paper, we
introduced the definitions of the three sets at the beginning of Section 3.1 in the revised version. Additionally, we present a more detailed proof roadmap at the beginning of Appendix A to illustrate the logical dependencies among our results and how the lemmas are used to derive the propositions and theorems.
Weakness 5. The section from lines 257 to line 281, should go in a future work section after discussion...
Answer: Thanks for your suggestion. We have moved them to future work section.
Weakness 6. The experiments illustrate the framework but do not establish its practical advantage....
Answer:
Currently, we have shown that under DNN example (i.e., when d is large) our bound yields the tightest guarantee compared with other bounds. Additionally, based on your suggestion we evaluate further our bounds and other comparable bounds on a synthetic binary classification task using CNN (see the new figure (Figure 5) and also Appendix F for more details). As shown in Figure 5 in Section 4.3, our bound requires significantly fewer training samples than existing bounds to become non-vacuous. We have also added the second bound of Thm 3.1 in [1] (Long et al (2020) (2) in Figure 5) to both synthetic experiment with DNN and convergence rate analysis. We are currently evaluating the second bound in Theorem 3.1 of [1] using DNNs on MNIST and CIFAR-10. The experiments have been delayed by the job queue at our computing center. We will share the results before the rebuttal period ends and include them in the final version.
Question 1. Given the explicit dependence on the dimension d...
Answer: We agree that a comparative discussion with covering number based bounds is essential to put our work in proper context. For that reason, we compare the numerical bounds obtained from our approach with covering number based approaches such as [1] and [2]. It can be seen for instance in our plots in Section 4.3 that covering number based approaches currently do not yield non-vacuous bounds for standard learning scenarios such as MNIST, which to us suggests that novel techniques may be needed. While we acknowledge that our bounds also require significant additional research to become usefulk in this sense, we do think that the comparison in Figure 4 suggests that our bounds constitute a significant step towards such more practically useful bounds. To make this more explicit, we have also added a comparison for a synthetic scenario in Figure 5 where the number of training samples is large enough to also see the non-vacuous regime. While the number of training samples needed to reach the non-vacuous regime in our approach is quite high at around 2 million, it is still a significant improvement over the best comparable bound (the second bound in [1]) which needs around 8 million.
So in summary, we acknowledge that there is additional research needed to develop our technique in such a way that it yields useful bounds in standard learning scenarios such as MNIST, we believe that we are making a significant step towards this goal and have shown that our novel technique has strong potential to eventually reach it.
Question 2. The logarithmic dependence on the Lipschitz constant is potentially beneficial...
Thank you for pointing this out. We have incorporated this observation into the remark (The second inequality in Theorem~3.1 of [1] also exhibits a similarly favorable dependence on the Lipschitz constant.)
and included a comparison with this bound in our experiments.
References:
[1] Long, P. M., & Sedghi, H. (2019). Generalization bounds for deep convolutional neural networks. arXiv preprint arXiv:1905.12600.
[2] Ledent A, Alves R, Lei Y. Generalization bounds for rank-sparse neural networks[J]. Advances in Neural Information Processing Systems, 2026, 38: 147927-147996.
Update on the CNNs numerical comparison with the second bound in Long, P. M., & Sedghi, H. (2019)
Thank you for suggesting a numerical comparison with the second bound of Long and Sedghi (2019). We have included this bound in our numerical comparison for CNNs (see Figure 4). Our bound remains the tightest among the bounds evaluated.
I thank the authors for their reply. I still think that the obtained generalization bound is way too weak, as acknowledged by the authors, to explain generalization. To me, also, the comparison with Long et al. (2020) (2), doesn't show a particularly stong improvent upon their bound. Therefore, I am not sure what insights the paper provides, since the linear dependence in the depth of the bound is not unique to this work. I appreciate that the authors intend to improve the presentation, but I don't feel the contribution is enough to justify acceptance.
For the problem of addressing the limitations of generalization analysis, a framework based on the data processing inequality (DPI) and change of measure with Rényi divergence is proposed to derive generalization bounds. The central idea is to introduce a conditional distribution and a prior distribution over the hypothesis space, both of which can be chosen freely. The DPI is then used to decompose the failure probability associated with the worst-case generalization gap into a moment-generating function (MGF) concentration term and a divergence term. Specific uniform and Gaussian choices of these auxiliary distributions induce directly evaluable generalization bounds. The paper presents main theoretical results for both sub-Gaussian and sub-exponential losses and evaluates the resulting bounds on Gaussian mean estimation, linear regression, and multi-class classification with deep neural networks.
Critical strengths
The paper attempts to provide worst-case, high-probability generalization bounds over continuous hypothesis spaces while avoiding the Dirac posterior and infinite KL divergence issues that deterministic learning algorithms encounter in the classical PAC-Bayes setting. This is a valuable research objective.
The framework allows different choices of DPI-based change of measure inequalities, auxiliary distributions and distributional assumptions on the loss function. These choices lead to different families of generalization bounds. The uniform and Gaussian constructions illustrate this flexibility.
Theorems 1 and 2 depend on quantities such as norms, dimension, Lipschitz constants, and concentration parameters, rather than requiring explicit evaluation of Rademacher complexity or covering numbers. Although estimating these parameters may itself be nontrivial, the resulting expressions are potentially easier to evaluate directly.
Critical weaknesses
To instantiate the bounds of Kakade et al. and Awasthi et al., the authors restrict the baseline hypothesis space to W=w∈R2:∣w∣1≤3σ. However, the paper does not adequately explain why the baseline radius must grow linearly with the noise standard deviation σ. In the high-variance setting σ=100, the baseline radius becomes W1=300. Since the main terms in the Kakade bound scale linearly with W1, this choice can substantially increase the baseline bound and lead to extremely large crossover sample sizes. This choice is not innocuous. Without a sensitivity analysis, it is difficult to determine whether the advantages shown in Figure 2 and Table 1 arise from the DPI framework itself or from the particular enlargement of the baseline hypothesis space. It is recommended that the authors explain why W1=3σ is necessary or natural choice, rather than merely a feasible one, and report, where possible, the radius choice that is most favorable to the baseline while satisfying the baseline assumptions, or provide explicit criteria for radius choice. The Gaussian mean estimation experiment does not adequately support the strong claim that the proposed bounds are significantly tighter at practically relevant sample sizes.
Appendix B states that the two coordinates are viewed as two independent intercept-only linear prediction tasks. It then directly presents the final inequalities associated with Kakade et al. and Awasthi et al. However, the mapping from the original problem to these inequalities is unclear. Specifically, the loss considered in this paper is the two-dimensional Euclidean loss. This is not the usual scalar loss in a single-output linear prediction problem. The authors should clarify which function class, input matrix, and loss are used when applying Corollary 5 of Kakade et al. and Theorem 1 of Awasthi et al., and how the required concentration conditions are satisfied when the Gaussian data are unbounded. In addition, the second term of the specialized Awasthi bound in Appendix B is written as 32nlog(2/δ), whereas the corresponding term in the Kakade bound contains a factor of σ. The authors should explain why this term in the Awasthi bound is independent of the noise scale, or check whether a factor of σ or another problem-dependent parameter has been omitted.
The authors explicitly acknowledge that all bounds, including the proposed one, are vacuous in the DNN regimes considered. For classification error, an upper bound greater than 1 provides no nontrivial information about the risk. Comparing the numerical values of different vacuous upper bounds may be mathematically informative as a comparison of scaling behavior, but its practical significance is limited. The paper further claims that the proposed bound requires fewer training samples to become non-vacuous. For example, it reports that CNN-3-100 requires 1.5×106 samples, whereas the other bounds require more. However, this calculation is performed by holding the network parameters and empirical data statistics fixed while varying n. This does not correspond to an actual learning process. If the training sample size increases from 60000 to 1.5×106, retraining may change the network parameters, spectral norms, parameter norms, empirical ramp loss, and statistics appearing in the other bounds. Hence, these sample sizes should be interpreted only as formal thresholds under fixed statistics, not as sample sizes at which actual trained networks would obtain non-vacuous guarantees.
The proposed results are indeed independent of the specific learning algorithm. However, this does not imply that they are broadly applicable to general learning problems without further qualification. The theoretical results require global Lipschitz continuity of the loss with respect to the model parameters, a sub-Gaussian or sub-exponential condition for every candidate hypothesis, and common parameters Cℓ,p, σℓ, νℓ, and αℓ that can be obtained in a sufficiently tight and computable form. These conditions are nontrivial in many common learning problems. For example, squared loss over an unbounded hypothesis space is generally not globally Lipschitz, and unbounded cross-entropy loss does not naturally satisfy a uniform sub-Gaussian condition. The DNN result can apply Theorem 1 because it uses the bounded ramp loss, rather than directly addressing the cross-entropy loss used during training. Moreover, avoiding additional complexity measures does not eliminate task-specific bounding work. The framework shifts most of the difficulty to estimating global or layer-wise Lipschitz constants, obtaining tight concentration parameters for the loss, and controlling how these quantities grow with depth, dimension, and parameter norms.
Theorem 1 requires γ≥1, whereas Remark 1 directly chooses γ=Cℓ,p2. When 0<Cℓ,p<1, this choice is invalid. Assumptions 1 and 2 are stated for w∈W, whereas Theorems 1 and 2 conclude that the bounds hold simultaneously for all w∈Rd. If W is a proper subset, then L(w), the Lipschitz condition, and the concentration condition need not be defined or valid outside W. Moreover, Definition 1 introduces μp(s)∈argmaxw∈BW∗,p∥L(w)−L^(s,w)∥. The subsequent proofs construct conditional distributions centered at μp(S) and integrate with respect to these distributions. The authors should discuss the existence of the maximum, the existence of a measurable selection, and any necessary measurability assumptions. In addition, μp also depends on W∗, but this dependence is suppressed in the current notation, which may cause ambiguity.
We thank the reviewer for their comments. We addressed them below and revised the paper with changes highlighted in blue.
Q1. To instantiate the bounds of Kakade et al. and Awasthi et al.....
Answer: Thank you for the suggestion. In the revised version we included the sensitivity analysis in Appendix B (Tables 2, 3, and 4.), shown in blue text.
To clarify the effect of the hypothesis-class constraint, we calculate
the crossover hypothesis constraint for the Gaussian mean estimation example at sample
sizes n∈{300,600,900}. It is clear that we do not have to set hypothesis radius W w.r.t σ, our bound is always tighter then the existing bounds once the hypothesis radius is set to be larger than the threshold (WA× or WK×) shown in the tables. These results provide an explicit criterion for identifying the case where our bound is tighter at a given sample size and hypothesis space constraint.
Q2. Appendix B states that the two coordinates are viewed...
Answer: Thanks for your suggestion, we give a clearer description about the mapping (i.e., function class, input matrix and loss) at Appendix B {in the revised version}.
Our example uses the unsquared Euclidean loss ℓ(w,z)=∥w−z∥2. Euclidean loss ℓ(w,z)=∥w−z∥2 is a standard location-estimation loss whose empirical risk is the geometric-median objective, studied extensively in robust estimation and optimization. Here are some works that use Euclidean loss:
[1] Wei, X., Yu, H., Ling, Q., & Neely, M. J. (2018). Solving non-smooth constrained programs with lower complexity than O(1/ϵ): A primal-dual homotopy smoothing approach. Advances in Neural Information Processing Systems, 31. (Equation (5))
[2] Haghifam, M., Steinke, T., & Ullman, J. (2024). Private geometric median. Advances in Neural Information Processing Systems, 37. (Equation (1))
To make a clearer description, here we restate the specialized version of Corollary 5 of Kakade et al.
PS(∀w∈W,L(w)−L^(S,w)≤2W2n1+W22nlog(1/δ))≥1−δ.
and specialized version of Theorem 1 of Awasthi et al.
\forall w\in \mathcal W,
L(w)-\hat L(S,w)
\le
2W_2\sqrt{\frac{1}{n}}
+
3\sqrt{\frac{\log(2/\delta)}{2n}}
\right)
\ge 1-\delta.$$
As you can see the second term of the Awasthi bound does not contain $W_2$, while the second term of the bound in Corollary 5 of Kakade et al. contains hypothesis constraint $W_2$. Because we set the hypothesis space as $\mathcal W:=\{w\in\mathbb R^d, \|w\|_2\le 6\sigma\}$ (i.e., $W_2=6\sigma$), you can see that $\sigma$ shows up at the second term of Corollary 5 of Kakade et al.
**Q3. The authors explicitly acknowledge that all bounds, including the proposed one.**
Answer: The sample-size calculation is intended to illustrate numerically that, with all other quantities held fixed, our bound requires substantially fewer training samples than the competing bounds to become non-vacuous. But we agree there is a more reasonable way to present. Specifically, we further added Figure 5 in Section 4.3, a synthetic binary classification task (see Appendix F for more details) using CNN. As shown in Figure 5, our bound requires around 2 million training samples to become non-vacuous. Although the number is quite large, it is still a significant improvement over the best comparable bound Long et al. (2020) which needs around 8 million.
Q4. The proposed results are indeed independent of.....
Answer: We thank the reviewer for highlighting this limitation. We would like to highlight the point that our bound does not need any additional assumptions, compared to the bounds we compared in the numerical section. In fact, compared to the bounds in [1] and [2], our bounds actually need fewer assumptions (bounded hypothesis space and bounded data assumption).
Also notice that for bounded loss functions, the Lipschitz constant is the only parameter that needs to be estimated, which is sufficient for most ML applications. In this case, when the loss function is unbounded, the bounds on sub-Gaussian and sub-exponential loss functions, although needing additional parameters, provide the opportunity for the bounds to be evaluated practically. We want to stress that such restrictions are also common in comparable generalization analysis. To the best of our knowledge, all the the existing generalization bounds for deterministic DNNs (i.e., ∀w∈W) do not hold for cross-entropy loss. Additionally, all of the existing norm-based bounds impose network-level or layer-wise Lipschitz constraints, often together with bounded-loss assumptions (e.g., all of the bounds we compared in Section 4.3).
However, we agree that our results rely on Lipschitz continuity together with a uniform sub-Gaussian or sub-exponential MGF condition on the centered loss. Therefore, we have expanded the Future Work section to emphasize weakening the Lipschitz and concentration assumptions.
Reference:
[1] Awasthi, P., Frank, N., & Mohri, M. (2020). On the Rademacher complexity of linear hypothesis sets. arXiv preprint arXiv:2007.11045.
[2] Kakade, S. M., Sridharan, K., & Tewari, A. (2008). On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in Neural Information Processing Systems.
Q5. Theorem 1 requires γ≥1...
Answer: Thanks for pointing out these minor issues. We have corrected all of them. In particular, for the existence of measurable argmax, we have added a detailed argument in Appendix A.1, which establishes the existence of a measurable worst-case hypothesis μp(S) under mild technical assumptions on the loss function.
From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.
We thank the reviewer for their comments. We addressed them below and revised the paper with changes highlighted in blue.
Weakness 1 and Question 1
Answer: Thanks for the interesting suggestions, we plan to look into that and compare to our results. Additionally, just plugging in the expectation will result in a bound of a different form. And we still think our framework is useful due to its potential of yielding more bounds (we have specified them in Future Work section).
Weakness 2
Answer: Our bound is significantly tighter than other bounds from previous literature under practical DNNs examples. The threshold sample size calculation is just want to show that our bound need significantly less number of training sample to become non-vacuous compared with other bounds if we fixed other quantities. But we agree there is a more reasonable way to present. Therefore, based on your suggestion we evaluate further our bounds and other comparable bounds on a synthetic binary classification task (see Appendix F for more details) using CNN. As shown in Figure 5, our bound requires much fewer training samples than existing bounds to become non-vacuous.
Questions 2: Appendix D establishes the CNN Lipschitz constant ....
Answer: Selecting PW∣S and QW as two uniform balls in Proposition 1 is our proof technique, which has nothing to do with imposing restrictions on the hypotheses or hypothesis space used in practice. Additionally, by applying Lemma 5, we can remove the restriction on the radius of the hypothesis space and then make our bounds hold for all $ w\in\mathcal W$.