- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper studies differentially private empirical risk minimization in the interpolation regime. The authors propose Noise-Decay DP-GD, which geometrically decreases both the per-sample gradient clipping threshold and the magnitude of the injected Gaussian noise. Under individual smoothness, interpolation, and strong convexity or PL-type geometric assumptions, they establish a high-probability empirical-risk bound of the form
They extend their analysis to overparameterized neural networks satisfying local PL* and Aiming conditions, as well as stochastic mini-batch training. Experiments on binary MNIST and CIFAR classification suggest improved convergence relative to standard DP-GD with fixed clipping and noise.
Critical strengths
The proposed synchronized decay schedule is simple and potentially useful in practice.
The analysis covers both classical optimization geometries and nonconvex neural networks under suitable assumptions.
The exponential empirical-risk guarantee is substantially stronger than the classical polynomial rates for general strongly convex private ERM, if the claimed privacy and utility guarantees hold.
Critical weaknesses
- Potentially incorrect differential privacy guarantee due to data-dependent hyperparameter initialization.
Theorems 3.6 and 4.4 prescribe an initial clipping threshold (C_0) that depends on the private empirical loss (L_D(w_0)). However, the privacy analysis in Appendix D treats the clipping schedule as fixed when comparing adjacent datasets, and does not account for the data dependence of (C_0).
This appears to invalidate the claimed privacy guarantee. For example, consider one-dimensional squared losses (\ell(w;z)=(w-z)^2/2) with initialization (w_0=0). If all training records equal zero, the prescribed initialization gives (C_0=0), and the algorithm returns zero deterministically. Replacing one record with a nonzero value yields (C_0>0), and the algorithm injects nondegenerate Gaussian noise. These neighboring datasets induce output distributions that violate ((\varepsilon,\delta))-DP for any (\delta<1).
A publicly specified upper bound or a private initialization procedure might repair this problem, but neither appears to be included in the proposed algorithm or its analysis.
- Major missing related work and questionable novelty.
The paper does not cite or compare against:
Asi, Chadha, Cheng, and Duchi (ICML 2022), Private Optimization in the Interpolation Regime: Faster Rates and Hardness Results.
This is a highly relevant omission. Asi et al. previously showed that interpolation combined with quadratic growth enables near-exponential improvements in private optimization. More specifically, their Domain and Lipschitz Localization algorithm progressively shrinks both the optimization domain and the effective Lipschitz constant, using smoothness and interpolation to establish that individual gradient norms decrease near the optimum.
This is essentially the same conceptual observation motivating the submitted paper's decaying clipping thresholds and Gaussian noise. The implementations differ, but the claimed algorithmic insight is not new.
Asi et al. study excess population risk rather than empirical risk, so their results do not directly subsume the submitted theorems. Nevertheless, a careful comparison is essential to establish the novelty and significance of the contribution. The present paper does not provide one.
- Restrictive geometric assumptions and limited generality.
The theoretical guarantees require strong convexity, global PL, or local PL* together with Aiming conditions. In contrast, Asi et al. obtain improved rates under the weaker quadratic-growth assumption for convex objectives, and also investigate more general growth conditions.
The paper does not clarify whether its approach can be extended beyond PL-type assumptions, or whether there are inherent obstacles to doing so. As a result, it is unclear how much additional insight the analysis provides into private optimization under interpolation beyond settings with strong optimization geometry.
- Hidden conditioning dependence and lack of optimality results.
The headline bound suppresses potentially important dependencies on problem parameters. In particular, substituting the step-size choice in Theorem 3.6 into its convergence analysis reveals a condition-number dependence of order ((\mu/\beta)^3=\kappa^{-3}) in the exponential rate.
The paper should present this dependence explicitly and compare it with prior work. It also provides no lower bounds establishing whether its dependence on sample size, dimension, privacy parameters, or condition number is optimal.
- Experimental comparisons are limited.
The experiments principally compare against standard DP-GD with fixed clipping and noise. They do not establish whether the proposed method improves over stronger dynamic-clipping or localization-based methods. Comparisons with relevant adaptive clipping baselines would help isolate the value of the proposed schedule.
Questions for authors
How is the privacy guarantee preserved when (C_0) depends on the private dataset through (L_D(w_0))? Does the counterexample above invalidate Theorem 3.7 when combined with the hyperparameter choices of Theorem 3.6?
How does the algorithm and its theoretical guarantee compare with Asi et al. (ICML 2022), particularly their domain and Lipschitz localization algorithm? What is the precise novel contribution relative to that work?
Can the results be extended to objectives satisfying quadratic growth without PL, or to weaker growth conditions?
Can the authors explicitly state the dependence on (\beta,\mu), and the associated condition number in their main theorem statements?
Are there lower bounds suggesting that the exponential dependence (n^2\varepsilon^2/p) is optimal?
2 comments
Part II
W3 & Q3: "Restrictive geometric assumptions... quadratic-growth for convex objectives... Can the results be extended beyond PL-type assumptions?"
A: Thank you for raising this point, which gives us the opportunity to highlight the advantages of our theoretical framework. Asi et al. (2022) rely on global convexity, which excludes neural networks. In contrast, our analysis moves beyond convex settings to deep learning:
- In classical settings (Section 3), our proof requires only the PL condition (Appendix C.1), accommodating non-convex objectives.
- For neural networks (Section 4), wide architectures satisfy local PL$^\ast$ and Aiming in the NTK regime (Liu et al., 2022; 2023), and empirical evidence shows these properties also hold along optimization trajectories of practical finite-width networks. Here, our theoretical analysis establishes the Non-Escape property (Proposition F.3), keeping the private trajectory confined within the local ball , which closely aligns with deep learning theory.
By analyzing non-convex neural network geometry rather than remaining restricted to global convexity, our work moves beyond the convex framework of Asi et al. (2022). Extending the analysis to non-convex objectives satisfying quadratic growth without PL is an interesting direction for future work.
W4a & Q4: "Hidden conditioning dependence ()... Can the authors explicitly state the dependence on and ?"
A: We thank the reviewer for this observation and agree with the condition-number dependence (). In Theorem 3.6, this yields (and similarly in Theorems 4.4 and 5.3). In the main theorems, we follow a common convention in DP-ERM and treat problem-dependent constants as to focus on asymptotic rates in , , and . The exact dependence on these constants is tracked explicitly in the proofs (Appendices C.2, F.3–F.4, and H.3–H.4).
Classical DP-ERM bounds also depend on : under (so ), Bassily et al. (2014) give and Wang et al. (2017) give . When forces , these classical bounds diverge (), whereas ours stays bounded (). When (as in our synthetic experiment in Appendix I.3), our rate improves exponentially over prior polynomial bounds and improves the exponent from in Asi et al. (2022) to .
W4b & Q5: "No lower bounds... Are there lower bounds suggesting is optimal?"
A: Our paper focuses on upper bounds. While Asi et al. (2022) proved pure-DP lower bounds under interpolation, tight -DP lower bounds remain an open question.
W5: "Experimental comparisons are limited... standard DP-GD with fixed clipping and noise..."
A: For standard DP-GD with fixed configurations, we use the same initial hyperparameters (, , and ) as ND-DP-GD for a fair comparison. Our paper is primarily a theoretical work improving empirical risk bounds under interpolation, where ND-DP-GD serves as a simple prototype rather than an empirically tuned method. Therefore, empirical comparisons with other dynamic scheduling methods are outside our focus, and many related theoretical works include little to no numerical experiments, such as Bassily et al. (2014) and Asi et al. (2022). In the revised PDF (Appendix I), we clarify that the MNIST and CIFAR-2 evaluations serve as a proof of concept and stress test showing that ND-DP-GD removes the static noise floor of standard DP-GD, and we have added a synthetic linear regression experiment under exact interpolation (Appendix I.3, Figure 3) whose empirical log-risk ratio scales linearly with (), (), (), and (), directly confirming the rate.
References:
Asi et al. (2022). "Private optimization in the interpolation regime: Faster rates and hardness results."
Bassily et al. (2014). "Private empirical risk minimization: Efficient algorithms and tight error bounds."
Liu et al. (2022). "Loss landscapes and optimization in over-parameterized non-linear systems and neural networks."
Liu et al. (2023). "Aiming towards the minimizers: Fast convergence of SGD for overparametrized problems."
Wang et al. (2017). "Differentially private empirical risk minimization revisited: Faster and more general."
We thank the reviewer for the constructive feedback and for recognizing the practical utility and simplicity of our algorithm. Major revisions are highlighted in cyan in the revised PDF. We address the comments below.
Part I
W1 & Q1: "Potentially incorrect differential privacy guarantee due to data-dependent hyperparameter initialization... Theorems 3.6 and 4.4 prescribe an initial clipping threshold C0 that depends on the private empirical loss..."
A: Thank you for pointing this out, and we apologize for the confusion. We agree that the phrasing in the original version of the theorems could give the impression that C0 was computed directly from L(w0). In Algorithm 1, C0>0 is a pre-fixed, data-independent hyperparameter specified prior to training, like the learning rate η and decay rate q. Because Ct=C0qtt=0T−1 and Ctσt=0T−1 are pre-scheduled without depending on the private dataset D, the (ϵ,δ)-DP guarantees in Theorems 3.8 (formerly Theorem 3.7) and 5.1 hold unconditionally for all datasets. The reviewer's counterexample assumes C0 is computed from the dataset; in Algorithm 1, C0 is pre-fixed prior to observing any data, so both neighboring datasets use the identical schedule.
In fact, C0 does not need to depend on L(w0) in either the privacy or the convergence analysis. In the revised PDF, we have restated Theorems 3.6, 4.4, and 5.3 in an explicit if-then form: for example, if the pre-fixed hyperparameter C0 satisfies βμ2L(w0)≤C0≤c0βμ2L(w0) in Theorem 3.6 (and similarly in Theorems 4.4 and 5.3) for a constant c0≥1, then clipping does not occur along the trajectory with high probability, and the asymptotic order and exponential rate of the empirical risk bound remain unchanged. In practice, as noted by the reviewer, C0 can be set using a public upper bound Lmax≥L(w0) without accessing private data (Remark 3.7).
W2 & Q2: "Major missing related work... Asi, Chadha, Cheng, and Duchi (ICML 2022)..."
A: Thank you for pointing out this paper. We have cited Asi et al. (2022) and added a comparison in Appendix J. While both works study private learning under interpolation and use gradient reduction, they differ in setting, algorithm, and rates:
1. Setting and Algorithm. Asi et al. (2022) study DP-SCO on a bounded convex domain X⊂Rp with diameter D, with several practical limitations:
Thus, their algorithm is difficult to implement in practice. In contrast, we study unconstrained DP-ERM on Rp: ND-DP-GD uses standard gradient updates with closed-form per-sample clipping and Gaussian noise, establishing exponential empirical risk bounds for PL objectives and non-convex neural networks.
2. Convergence Rates. With κ=β/μ (H/λ in Asi et al.), their (ϵ,δ)-DP excess risk bound (Theorems 2 and 9) scales as O(n−c+exp(−Θ~(cκ2n))+exp(−Θ~(cκpnϵ))), where c>0 trades off the polynomial tail n−c against the exponential rates. Our bound gives L(wT)≤O(exp(−Θ~(κ3pn2ϵ2))L(w0)). For κ=O(1), we improve the exponent from nϵ/p to (nϵ/p)2 without any additive polynomial term.