acceptodds
Under review as a conference paper at ICLR 2027

Improving the Empirical Risk Bound for Private Learning under Interpolation

Abstract

Differentially Private Gradient Descent (DP-GD) provides a principled approach to training machine learning models while preserving data privacy by injecting Gaussian noise into model updates and clipping sample-wise gradients. Existing literature has established joint theoretical guarantees for differential privacy and excess empirical risk under classical assumptions such as (strong) convexity and the Polyak-Łojasiewicz (PL) condition, with excess empirical risk bounded by or worse. In this paper, we study DP-GD in the *interpolation regime*, a key setting in modern machine learning where the training data can be fit exactly. We show that interpolation enables substantially stronger optimization guarantees, transforming polynomial-type empirical-risk bounds into exponential-type bounds in and , while still preserving differential privacy. Specifically, leveraging a property of interpolation — *automatic gradients reduction*, we propose to synchronously decay the standard deviation of the injected Gaussian noise and the gradient clipping threshold, at an appropriate exponential rate. First, in the classical settings considered in prior work, we show that interpolation improves the empirical risk to . We further extend our analysis to non-convex neural networks and establish the same exponential empirical risk bound, which is also preserved under stochastic training. Finally, empirical evaluations verify the effectiveness of the proposed hyperparameter decay mechanism and demonstrate improved convergence compared with standard DP-GD.

Primary area:
optimization
Keywords:
Differential Privacy, Empirical Risk Minimization, Interpolation, Over-parameterization, Optimization Theory

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_BXBoOpenReview ↗
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

L(wT)−L∗≤exp⁡(−Ω~(n2ε2/p))(L(w0)−L∗).L(w_T)-L^* \leq \exp\left(-\widetilde\Omega(n^2\varepsilon^2/p)\right)(L(w_0)-L^*).

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
  1. 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.

  1. 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.

  1. 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.

  1. 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.

  1. 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

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 C0C_0 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 C0C_0 was computed directly from L(w0)\mathcal{L}(\mathbf{w}_0). In Algorithm 1, C0>0C_0 > 0 is a pre-fixed, data-independent hyperparameter specified prior to training, like the learning rate η\eta and decay rate qq. Because Ct=C0qtt=0T−1\\{C_t = C_0 q^t\\}_{t=0}^{T-1} and Ctσt=0T−1\\{C_t \sigma\\}_{t=0}^{T-1} are pre-scheduled without depending on the private dataset D\mathcal{D}, the (ϵ,δ)(\epsilon, \delta)-DP guarantees in Theorems 3.8 (formerly Theorem 3.7) and 5.1 hold unconditionally for all datasets. The reviewer's counterexample assumes C0C_0 is computed from the dataset; in Algorithm 1, C0C_0 is pre-fixed prior to observing any data, so both neighboring datasets use the identical schedule.

In fact, C0C_0 does not need to depend on L(w0)\mathcal{L}(\mathbf{w}_0) 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 C0C_0 satisfies β2L(w0)μ≤C0≤c0β2L(w0)μ\beta \sqrt{\frac{2\mathcal{L}(\mathbf{w}_0)}{\mu}} \le C_0 \le c_0\beta \sqrt{\frac{2\mathcal{L}(\mathbf{w}_0)}{\mu}} in Theorem 3.6 (and similarly in Theorems 4.4 and 5.3) for a constant c0≥1c_0 \ge 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, C0C_0 can be set using a public upper bound Lmax⁡≥L(w0)L_{\max} \ge \mathcal{L}(\mathbf{w}_0) 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\mathcal{X} \subset \mathbb{R}^p with diameter DD, with several practical limitations:

  • Global convexity on bounded X\mathcal{X} excludes unconstrained non-convex neural networks.
  • Lipschitzian extensions via infimal convolutions FL(x;si)=inf⁡yF(y;si)+L∣x−y∣F_{L}(x; s_i) = \inf_{y}\\{F(y; s_i) + L\\|x - y\\|\\} require solving an inner continuous problem over Rp\mathbb{R}^p per sample per step, with no closed form.
  • Algorithm 1 relies on black-box DP-SCO oracles solving inner regularized ERM problems (Algorithm 4) rather than explicit gradient updates.
  • Localization solves constrained ERM over shrinking balls X∩B(xk−1,Dk)\mathcal{X} \cap \mathcal{B}(x_{k-1}, D_k) per epoch, requiring repeated high-dimensional projections incompatible with unconstrained deep learning.

Thus, their algorithm is difficult to implement in practice. In contrast, we study unconstrained DP-ERM on Rp\mathbb{R}^p: 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 κ=β/μ\kappa = \beta/\mu (H/λH/\lambda in Asi et al.), their (ϵ,δ)(\epsilon, \delta)-DP excess risk bound (Theorems 2 and 9) scales as O(n−c+exp⁡(−Θ~(ncκ2))+exp⁡(−Θ~(nϵcκp)))\mathcal{O}\big(n^{-c} + \exp(-\tilde{\Theta}(\frac{n}{c\kappa^2})) + \exp(-\tilde{\Theta}(\frac{n\epsilon}{c\kappa \sqrt{p}}))\big), where c>0c > 0 trades off the polynomial tail n−cn^{-c} against the exponential rates. Our bound gives L(wT)≤O(exp⁡(−Θ~(n2ϵ2κ3p))L(w0))\mathcal{L}(\mathbf{w}_T) \le \mathcal{O}\big(\exp(-\tilde{\Theta}(\frac{n^2\epsilon^2}{\kappa^3 p}))\mathcal{L}(\mathbf{w}_0)\big). For κ=O(1)\kappa = \mathcal{O}(1), we improve the exponent from nϵ/pn\epsilon/\sqrt{p} to (nϵ/p)2(n\epsilon/\sqrt{p})^2 without any additive polynomial term.

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 BR(w0)\mathcal{B}_R(\mathbf{w}_0), 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 (κ−3\kappa^{-3})... Can the authors explicitly state the dependence on (β,μ)(\beta, \mu) and κ\kappa?"

A: We thank the reviewer for this observation and agree with the condition-number dependence (κ=β/μ\kappa = \beta/\mu). In Theorem 3.6, this yields L(wT)≤O(exp⁡(−Θ~(n2ϵ2κ3p))L(w0))\mathcal{L}(\mathbf{w}_T) \le \mathcal{O}\big(\exp(-\tilde{\Theta}(\frac{n^2\epsilon^2}{\kappa^3 p}))\mathcal{L}(\mathbf{w}_0)\big) (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 O(1)\mathcal{O}(1) to focus on asymptotic rates in nn, pp, and ϵ\epsilon. 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 κ\kappa: under β=Θ(1)\beta = \Theta(1) (so 1/μ=Θ(κ)1/\mu = \Theta(\kappa)), Bassily et al. (2014) give O~(κpn2ϵ2)\tilde{\mathcal{O}}(\frac{\kappa p}{n^2\epsilon^2}) and Wang et al. (2017) give O~(κ2pn2ϵ2)\tilde{\mathcal{O}}(\frac{\kappa^2 p}{n^2\epsilon^2}). When p≫np \gg n forces κ≥n\kappa \ge n, these classical bounds diverge (→∞\to \infty), whereas ours stays bounded (L(wT)≤O(L(w0))=O(1)\mathcal{L}(\mathbf{w}_T) \le \mathcal{O}(\mathcal{L}(\mathbf{w}_0)) = \mathcal{O}(1)). When κ=O(1)\kappa = \mathcal{O}(1) (as in our synthetic experiment in Appendix I.3), our rate improves exponentially over prior polynomial bounds and improves the exponent from nϵ/pn\epsilon/\sqrt{p} in Asi et al. (2022) to (nϵ/p)2(n\epsilon/\sqrt{p})^2.

W4b & Q5: "No lower bounds... Are there lower bounds suggesting n2ϵ2/pn^2\epsilon^2/p is optimal?"

A: Our paper focuses on upper bounds. While Asi et al. (2022) proved pure-DP lower bounds under interpolation, tight (ϵ,δ)(\epsilon, \delta)-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 (C0C_0, σ\sigma, and η\eta) 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 n2n^2 (R2=0.9993R^2 = 0.9993), 1/p1/p (R2=0.9999R^2 = 0.9999), ϵ2\epsilon^2 (R2=0.9981R^2 = 0.9981), and n2/pn^2/p (R2=0.9924R^2 = 0.9924), directly confirming the −n2ϵ2/p-n^2\epsilon^2/p 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."

Reviewer_L4TaOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies differentially private gradient descent (DP-GD) in the interpolation regime, where all training losses share a common minimizer at which they vanish. The authors propose ND-DP-GD, which decreases the gradient clipping threshold and Gaussian noise scale together at a geometric rate, Ct=C0qtC_t=C_0q^t. Since the noise-to-clipping ratio remains constant, the privacy cost of each iteration is the same as in standard DP-GD.

The main claim is that this approach achieves an exponentially small empirical-risk bound of the form exp⁡(−Θ~(n2ϵ2/p))L(w0)\exp(-\widetilde{\Theta}(n^2\epsilon^2/p))L(w_0), improving upon the polynomial rate O~(p/(n2ϵ2))\widetilde{O}(p/(n^2\epsilon^2)) obtained in previous work. The authors extend the analysis from strongly convex objectives to functions satisfying the Polyak–Łojasiewicz (PL) condition, wide neural networks under PL* and "Aiming" assumptions, and minibatch DP-SGD. Experiments on MNIST 0-vs-1 and CIFAR-2 are included in the appendix.

Critical strengths
  1. The proposed modification to DP-GD is simple and easy to implement. By decreasing the clipping threshold and noise scale at the same rate, the algorithm preserves the usual privacy accounting of DP-GD. For a fixed, data-independent schedule, this privacy guarantee holds for all neighboring datasets.

  2. I find the idea of using interpolation to justify a decreasing clipping threshold interesting. In particular, the authors use the bound ∥∇ℓi(w)∥≤βdist⁡(w,S)\|\nabla\ell_i(w)\|\leq\beta\operatorname{dist}(w,\mathcal{S}) to show that clipping can remain inactive as the iterates approach the solution set. The induction argument in the strongly convex setting appears mathematically sound. In sufficiently low-dimensional problems, the analysis does yield an empirical-risk bound that decreases exponentially with n2ϵ2n^2\epsilon^2.

  3. Understanding whether interpolation can improve the privacy–utility trade-off is an important problem, especially given the widespread use of overparameterized models in modern machine learning.

Critical weaknesses
  1. The paper overlooks closely related prior work, and the novelty claims are not convincing. My first concern is that the paper does not discuss what appears to be its closest predecessor:

    • Asi, Chadha, Cheng, and Duchi, "Private Optimization in the Interpolation Regime: Faster Rates and Hardness Results" (ICML 2022).

    This paper studies essentially the same setting: private optimization under interpolation, smooth per-sample losses, and a growth condition on the gradients. It also uses the observation that individual gradients become smaller near the solution, through a bound of the form ∥∇f(x;s)∥≤H∥x−x∗∥\|\nabla f(x;s)\|\leq H\|x-x^*\|, to justify geometrically decreasing clipping thresholds. Importantly, it already establishes near-exponential convergence rates with explicit dependence on the condition number, together with lower bounds and hardness results.

    This directly challenges the claims that theoretical risk guarantees for such clipping schedules have not previously been established. I think this work needs to be discussed prominently, with a careful comparison of the assumptions, algorithms, convergence rates, and lower bounds.

    Several other components are also closely related to existing results:

    • The inequality in Lemma 3.2 is the classical self-bounding property of nonnegative smooth losses. See Srebro, Sridharan, and Tewari, "Smoothness, Low Noise and Fast Rates" (NeurIPS 2010).
    • Iteration-dependent privacy budgets and noise schedules have been explored in Lee and Kifer, "Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget" (KDD 2018).

    These connections do not necessarily invalidate the proposed approach, but they substantially weaken the novelty claims in the current manuscript.

  2. The main convergence rates hide a potentially large condition-number dependence, which makes the guarantees uninformative in the overparameterized regime emphasized by the paper. This is my most serious technical concern. The headline rate is stated as exp⁡(−Θ~(n2ϵ2/p))\exp(-\widetilde{\Theta}(n^2\epsilon^2/p)), but the proof contains a dependence on the condition number κ=β/μ\kappa=\beta/\mu that is absorbed into the asymptotic notation. For the squared-loss problems considered in the paper, this condition number can grow at least linearly with min⁡(n,p)\min(n,p). Once this dependence is made explicit, the claimed improvement becomes much weaker and can be vacuous when p≥np\geq n.

    Specifically, in the proof of Theorem 3.6 (Appendix C.2), the authors maintain the invariant

    L(wt)≤μ2β2Ct2.L(w_t)\leq \frac{\mu}{2\beta^2}C_t^2.

    This is necessary to ensure that the per-sample gradients stay below the clipping threshold. Indeed, strong convexity gives

    \leq \sqrt{\frac{2L(w_t)}{\mu}} \leq \frac{C_t}{\beta},$$ and interpolation together with per-sample smoothness then implies $$\\|\nabla\ell_i(w_t)\\| \leq \beta\operatorname{dist}(w_t,\mathcal{S}) \leq C_t.$$ Since $C_t$ decreases geometrically, the loss must decrease at a comparable rate to maintain this invariant. However, strong convexity only guarantees a contraction factor of $1-\mu\eta$, while the injected Gaussian noise adds an error term of order $\beta^3\eta^2K^2/(\mu n^2)$. To keep the noise contribution sufficiently small and obtain $q^2=1-\mu\eta/2$, the proof requires $$\eta\leq\frac{\mu^2n^2}{4\beta^3K^2}.$$ The distinction between $\beta$ and $\mu$ matters here. The clipping threshold must accommodate the largest individual gradient, which is controlled by $\beta$, while optimization progress depends on the curvature of the averaged loss, measured by $\mu$. After $T$ iterations, the proof gives $$L(w_T)\leq q^{2T}L(w_0) \leq \exp\left(-\frac{\mu\eta T}{2}\right)L(w_0).$$ Substituting the step-size restriction, $K\geq\sigma\sqrt{p}$, and the privacy calibration $\sigma^2=32T\ln(1/\delta)/\epsilon^2$, we obtain $$\frac{\mu\eta T}{2}\leq\frac{\mu^3n^2\epsilon^2}{256\beta^3p\ln(1/\delta)}=\frac{n^2\epsilon^2}{256\kappa^3p\ln(1/\delta)}.$$ Notice that $T$ cancels. Increasing the number of iterations does not improve this exponent because the noise required by privacy accounting grows with $T$. In the final step of Appendix C.2 (lines 909–917), the authors write $\eta=\widetilde{\Theta}(n^2\epsilon^2/(pT))$, effectively hiding the factor $\kappa^{-3}=\mu^3/\beta^3$. However, $\widetilde{\Theta}$ is defined to suppress only constants and logarithmic factors (lines 117–118). Unless $\kappa$ is assumed to be bounded independently of $n$ and $p$, the stated rate does not follow in the claimed form. **Why this matters for squared losses.** Consider a squared-type loss $\ell_i(w)=(f_i(w)-y_i)^2$. At an interpolating solution, the residual vanishes, so the per-sample Hessian becomes $$\nabla^2\ell_i(w)=2\nabla f_i(w)\nabla f_i(w)^\top.$$ This is a rank-one matrix whose nonzero eigenvalue is $2\\|\nabla f_i(w)\\|^2$. Consequently, the per-sample smoothness constant must satisfy $$\beta\geq 2\max_i\\|\nabla f_i(w)\\|^2.$$ Meanwhile, the Hessian of the averaged loss is $$\nabla^2L(w)=\frac{2}{n}\sum_{i=1}^{n} \nabla f_i(w)\nabla f_i(w)^\top.$$ When $p\leq n$, the smallest eigenvalue is at most the trace divided by $p$, giving $\mu\leq\beta/p$. When $p\geq n$, the relevant nonzero curvature is restricted to the span of the sample gradients, and the corresponding Gram-matrix argument gives $\mu\leq\beta/n$. Thus, in the relevant nondegenerate directions, $$\kappa=\frac{\beta}{\mu}\geq\min(n,p).$$ This dependence comes from the structure of interpolating squared losses rather than an avoidable looseness in the proof. **Therefore, in the low-dimensional case $p\ll n$, substituting $\kappa\geq p$ gives an exponent no larger than \$\\frac{n^2\\epsilon^2} {256p^4\\ln(1/\\delta)}.\$** For fixed $p$, this is still exponential in $n^2\epsilon^2$, so the classical strongly convex result remains meaningful. However, the dimension dependence is effectively $p^4$ rather than $p$, and the bound requires approximately $n\gtrsim p^2$ to become informative. For example, with $\epsilon=1$, $\delta=10^{-6}$, and $n=10^5$, taking $p=10$ gives an exponent of about 280. However, increasing the dimension to $p=100$ reduces the exponent to approximately $0.03$, corresponding to a bound around $L(w_T)\leq0.97L(w_0)$. This is barely an improvement even though $p/n=0.001$. **The problem is more serious when $p\geq n$, which is precisely the regime emphasized throughout the paper.** It appears in the motivation (line 074), the generalized strong-convexity extension (lines 342–353), Sections 4–5, and both experiments, where $(p,n)=(108866,12665)$ and $(267618,10000)$. In this regime, $\kappa\geq n$, so the exponent is at most $$\frac{\epsilon^2} {256np\ln(1/\delta)}.$$ This approaches zero as the problem size grows, making the resulting guarantee essentially vacuous. Overall, I believe the dependence on the condition number and the scaling of the curvature constants need to be revisited carefully. As currently stated, the main theoretical guarantees do not appear to justify the claimed exponential improvement in the overparameterized setting that motivates the paper.

Minor Weaknesses

  1. There are additional concerns with the privacy analysis. In Theorem 5.1 (Appendix G, lines 1291–1299), the paper appears to use the asymptotic central-limit approximation of Bu et al. (2020) as though it were a finite-TT privacy upper bound. An asymptotic approximation alone is not sufficient to establish the claimed finite-iteration privacy guarantee. I would recommend using a rigorous privacy accountant, such as Mironov, Talwar, and Zhang, "Rényi Differential Privacy of the Sampled Gaussian Mechanism" (2019).

  2. The experimental evaluation is limited and does not adequately support the theoretical claims. The experiments appear only in the appendix and focus on two relatively small binary classification tasks with full-batch training. There is no experimental evaluation of the proposed ND-DP-SGD extension. The main baseline is standard DP-GD with fixed clipping thresholds (C=50C=50 or 150150), which does not appear to be carefully tuned. On CIFAR-2, this baseline remains close to chance at ϵ=1\epsilon=1, so outperforming it does not necessarily demonstrate a meaningful advantage.

    There is also a mismatch between the theoretical assumptions and the experimental settings. On CIFAR-2, the training error remains around 16%–31%, so the models do not actually interpolate the training data. The CNN also uses ReLU activations and MaxPool operations, which do not satisfy the global smoothness assumptions used in the theory. In addition, the paper does not investigate how performance scales with nn, pp, or ϵ\epsilon, even though these are central to the claimed improvement.

Questions for authors
  1. Could the authors restate Theorems 3.6, 4.4, and 5.3 with the dependence on all relevant constants made explicit? In particular, do the authors agree that the exponent in the strongly convex result is bounded by n2ϵ2/(256κ3pln⁡(1/δ))n^2\epsilon^2/(256\kappa^3p\ln(1/\delta)), where κ=β/μ\kappa=\beta/\mu? For squared losses, the analysis above suggests κ≥min⁡(n,p)\kappa\geq\min(n,p). How do the authors reconcile the claimed exponential convergence with this condition-number dependence and the random-label lower-bound example?

  2. How does the proposed method differ from Asi, Chadha, Cheng, and Duchi, "Private Optimization in the Interpolation Regime: Faster Rates and Hardness Results" (ICML 2022)? I would appreciate a detailed comparison of the algorithmic ideas, assumptions, convergence rates, condition-number dependence, and lower bounds, since this appears to be the closest related work.

  3. Could the authors provide a rigorous finite-TT privacy accountant for the minibatch algorithm in Theorem 5.1? Also, how is the end-to-end differential privacy guarantee maintained when C0C_0, qq, and η\eta depend on quantities computed from the private dataset? Would the claimed results still hold with a fully data-independent parameter schedule?

  4. Could the authors strengthen the experimental evaluation with the following comparisons and analyses?

    • Compare against properly tuned DP-GD with learning-rate decay, as well as adaptive and automatic clipping methods.
    • Study the dependence on nn, pp, and ϵ\epsilon using a problem that genuinely satisfies the interpolation and smoothness assumptions.
4 comments

We thank the reviewer for confirming the soundness of our induction and for the condition-number derivation. Major revisions are highlighted in cyan in the revised PDF. We address the questions below.

Part I

W1a & Q2: "The paper does not discuss... Asi et al. (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\mathcal{X} \subset \mathbb{R}^p with diameter DD, with several practical limitations:

  • Global convexity on bounded X\mathcal{X} excludes unconstrained non-convex neural networks.
  • Lipschitzian extensions via infimal convolutions FL(x;si)=inf⁡yF(y;si)+L∣x−y∣F_{L}(x; s_i) = \inf_{y}\\{F(y; s_i) + L\\|x - y\\|\\} require solving an inner continuous problem over Rp\mathbb{R}^p per sample per step, with no closed form.
  • Algorithm 1 relies on black-box DP-SCO oracles solving inner regularized ERM problems (Algorithm 4) rather than explicit gradient updates.
  • Localization solves constrained ERM over shrinking balls X∩B(xk−1,Dk)\mathcal{X} \cap \mathcal{B}(x_{k-1}, D_k) per epoch, requiring repeated high-dimensional projections incompatible with unconstrained deep learning.

Thus, their algorithm is difficult to implement in practice. In contrast, we study unconstrained DP-ERM on Rp\mathbb{R}^p: 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 κ=β/μ\kappa = \beta/\mu (H/λH/\lambda in Asi et al.), their (ϵ,δ)(\epsilon, \delta)-DP excess risk bound (Theorems 2 and 9) scales as O(n−c+exp⁡(−Θ~(ncκ2))+exp⁡(−Θ~(nϵcκp)))\mathcal{O}\big(n^{-c} + \exp(-\tilde{\Theta}(\frac{n}{c\kappa^2})) + \exp(-\tilde{\Theta}(\frac{n\epsilon}{c\kappa \sqrt{p}}))\big), where c>0c > 0 trades off the polynomial tail n−cn^{-c} against the exponential rates. Our bound gives L(wT)≤O(exp⁡(−Θ~(n2ϵ2κ3p))L(w0))\mathcal{L}(\mathbf{w}_T) \le \mathcal{O}\big(\exp(-\tilde{\Theta}(\frac{n^2\epsilon^2}{\kappa^3 p}))\mathcal{L}(\mathbf{w}_0)\big). For κ=O(1)\kappa = \mathcal{O}(1), we improve the exponent from nϵ/pn\epsilon/\sqrt{p} to (nϵ/p)2(n\epsilon/\sqrt{p})^2 without any additive polynomial term.

W1b: "Lemma 3.2 is the classical self-bounding property (Srebro et al., 2010)... adaptive privacy budgets (Lee and Kifer, 2018)."

A: Thank you for pointing out these two references, which we have added to the revised PDF:

  • Srebro et al. (2010): Cited in Remark 3.3 for the classical smoothness-based gradient bound.
  • Lee and Kifer (2018): Cited in Section 1.1 (Related Work) on adaptive per-iteration privacy budgets.

These works do not conflict with our core contribution, which lies in establishing exponential empirical risk bounds under interpolation for both classical settings and non-convex neural networks.

W2 & Q1: "The main convergence rates hide a potentially large condition-number dependence... κ≥min⁡(n,p)\kappa \ge \min(n, p)... make guarantees uninformative when p≥np \ge n..."

A: We agree with the reviewer's derivation of the condition-number dependence (κ=β/μ\kappa = \beta/\mu). In Theorem 3.6, this yields L(wT)≤O(exp⁡(−Θ~(n2ϵ2κ3p))L(w0))\mathcal{L}(\mathbf{w}_T) \le \mathcal{O}\big(\exp(-\tilde{\Theta}(\frac{n^2\epsilon^2}{\kappa^3 p}))\mathcal{L}(\mathbf{w}_0)\big) (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 O(1)\mathcal{O}(1) to focus on asymptotic rates in nn, pp, and ϵ\epsilon. 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 κ\kappa: under β=Θ(1)\beta = \Theta(1) (so 1/μ=Θ(κ)1/\mu = \Theta(\kappa)), Bassily et al. (2014) give O~(κpn2ϵ2)\tilde{\mathcal{O}}(\frac{\kappa p}{n^2\epsilon^2}) and Wang et al. (2017) give O~(κ2pn2ϵ2)\tilde{\mathcal{O}}(\frac{\kappa^2 p}{n^2\epsilon^2}). When p≫np \gg n forces κ≥n\kappa \ge n, these classical bounds diverge (→∞\to \infty), whereas ours stays bounded (L(wT)≤O(L(w0))=O(1)\mathcal{L}(\mathbf{w}_T) \le \mathcal{O}(\mathcal{L}(\mathbf{w}_0)) = \mathcal{O}(1)). When κ=O(1)\kappa = \mathcal{O}(1) (as in our synthetic experiment in Appendix I.3), our rate improves exponentially over prior polynomial bounds and improves the exponent from nϵ/pn\epsilon/\sqrt{p} in Asi et al. (2022) to (nϵ/p)2(n\epsilon/\sqrt{p})^2.

Part II

Minor W1 & Q3a: "There are additional concerns with the privacy analysis... Could the authors provide a rigorous finite-TT privacy accountant for the minibatch algorithm in Theorem 5.1?"

A: Thank you for this helpful observation. We agree that a finite-step privacy accountant should be used for Theorem 5.1. Note that this asymptotic issue is specific to the stochastic variant ND-DP-SGD with Poisson subsampling (Theorem 5.1); for full-batch ND-DP-GD, both Theorem 3.8 (Moments Accountant) and the GDP composition in Appendix E hold for every finite TT without asymptotic approximations. In the revised PDF, we have updated Theorem 5.1 and Appendix G.1 using the finite-step Moments Accountant of Abadi et al. (2016, Theorem 1), ensuring (ϵ,δ)(\epsilon, \delta)-DP for σ≥c2qsTln⁡(1/δ)ϵ\sigma \ge c_2 \frac{q_s \sqrt{T\ln(1/\delta)}}{\epsilon} with a constant c2>0c_2 > 0. With this noise scaling, the convergence and empirical risk bounds (Theorem 5.3 and Corollary 5.4) remain unchanged.

Q3b: "How is the end-to-end differential privacy guarantee maintained when C0C_0, qq, and η\eta depend on quantities computed from the private dataset? Would the claimed results still hold with a fully data-independent parameter schedule?"

A: Yes. In Algorithm 1, the privacy mechanism is independent of the convergence conditions, and C0>0C_0 > 0 is a pre-fixed, data-independent hyperparameter specified prior to training, like η\eta and qq. Because Ct=C0qtt=0T−1\\{C_t = C_0 q^t\\}_{t=0}^{T-1} and Ctσt=0T−1\\{C_t \sigma\\}_{t=0}^{T-1} remain identical across neighboring datasets, the (ϵ,δ)(\epsilon, \delta)-DP guarantees in Theorems 3.8 and 5.1 hold unconditionally for all datasets. We have revised Theorems 3.6, 4.4, and 5.3 into an explicit if-then form: for example, if the pre-fixed C0C_0 satisfies β2L(w0)μ≤C0≤c0β2L(w0)μ\beta \sqrt{\frac{2\mathcal{L}(\mathbf{w}_0)}{\mu}} \le C_0 \le c_0\beta \sqrt{\frac{2\mathcal{L}(\mathbf{w}_0)}{\mu}} in Theorem 3.6 (and similarly in Theorems 4.4 and 5.3) for a constant c0≥1c_0 \ge 1, then the exponential convergence guarantee holds. In practice, C0C_0 can be set using a public upper bound Lmax⁡≥L(w0)L_{\max} \ge \mathcal{L}(\mathbf{w}_0) without accessing private data (Remark 3.7).

Minor W2 & Q4: "The experimental evaluation is limited... models do not actually interpolate on CIFAR-2... CNN uses ReLU and MaxPool... does not investigate how performance scales with nn, pp, or ϵ\epsilon..."

A: Our paper is primarily a theoretical work improving empirical risk bounds under interpolation, where ND-DP-GD serves as a simple algorithmic prototype rather than an empirically tuned method; as noted above, closely related theoretical works such as Bassily et al. (2014) and Asi et al. (2022) include little to no numerical experiments. In the revised PDF (Appendix I), we clarify that the MNIST and CIFAR-2 neural network evaluations serve as a proof of concept and a stress test on realistic architectures (including non-smooth components such as ReLU and max pooling), using the same initial hyperparameters (C0C_0, σ\sigma, η\eta) as standard DP-GD for a fair comparison to show that synchronized decay removes the static noise floor.

Following the reviewer's suggestion in Q4, we have added a synthetic multi-output linear regression experiment under exact interpolation and smoothness in Appendix I.3 (Figure 3) of the revised PDF, systematically varying nn, pp, and ϵ\epsilon. The empirical log-risk ratio ln⁡(LT/L0)\ln(\mathcal{L}_T/\mathcal{L}_0) scales linearly with n2n^2 (R2=0.9993R^2 = 0.9993), 1/p1/p (R2=0.9999R^2 = 0.9999), ϵ2\epsilon^2 (R2=0.9981R^2 = 0.9981), and n2/pn^2/p across 15 joint configurations (R2=0.9924R^2 = 0.9924), confirming the theoretical −n2ϵ2/p-n^2\epsilon^2/p rate.

References:

Abadi et al. (2016). "Deep learning with differential privacy."

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."

Lee and Kifer (2018). "Concentrated differentially private gradient descent with adaptive per-iteration privacy budget."

Srebro et al. (2010). "Smoothness, low noise and fast rates."

Wang et al. (2017). "Differentially private empirical risk minimization revisited: Faster and more general."

Thank you for the detailed response and the revised manuscript. My concerns are partially resolved, and the remaining one is the dependence on the condition number κ=β/μ\kappa = \beta/\mu.

  • As shown in Appendix C (l.911–912), the exponent is of order n2ϵ2/(κ3p)n^2\epsilon^2/(\kappa^3 p), but κ\kappa is still absorbed into Θ~(⋅)\tilde{\Theta}(\cdot) in the main theorems, the corollaries and Table 1.
  • This matters most in the over-parameterized regime that the paper emphasizes. For linear regression, κ≥min⁡(n,p)\kappa \ge \min(n, p). For the averaged loss used in Theorem 4.1, μ=O(λ0/n)\mu = O(\lambda_0/n), so again κ≳n\kappa \gtrsim n. When p≥np \ge n, the exponent is therefore at most O(ϵ2/(np))O(\epsilon^2/(np)), and the bound reduces to O(L(w0))O(L(w_0)), which holds trivially.
  • The new synthetic experiment (Appendix I.3) uses din=2d_{\text{in}} = 2 with many outputs. Each output is a 2-dimensional regression with nn samples, so the Hessian has full rank and κ=O(1)\kappa = O(1). The experiment therefore does not test the over-parameterized regime in this sense.

I suggest stating the κ\kappa dependence explicitly in the theorems and Table 1, and restricting the over-parameterized claims, including the neural-network results, to settings where κ\kappa remains bounded. In addition, the experiments still compare only against DP-GD with a fixed clipping threshold. A tuned or adaptive clipping baseline, e.g., Andrew et al., "Differentially Private Learning with Adaptive Clipping" (NeurIPS 2021), would make the empirical comparison more convincing.

Given the corrected privacy analysis and the improved positioning, I raise my score to 2. The κ\kappa issue keeps the paper below the acceptance threshold.

Thank you for raising the score and for the constructive suggestions on the condition-number dependence and the scope of our claims. In the revised PDF (highlighted in cyan), we have updated the text and tables as follows:

1. Explicit Parameter Dependence in Theorems and Table 1

  • Theorems and Corollaries: Theorems 3.6, 4.4, 5.3 and Corollaries 4.5, 5.4 now display curvature and smoothness parameters directly in their displayed bounds, rather than absorbing them into asymptotic notation.
  • Table 1: We have explicitly displayed the condition number κ\kappa for both interpolation works: κ=H/λ\kappa = H/\lambda for Asi et al. (2022), and O(exp⁡(−Θ~(n2ϵ2/(κ3p))))\mathcal{O}(\exp(-\tilde{\Theta}(n^2\epsilon^2/(\kappa^3 p)))) (SC/PL) and O(exp⁡(−Θ~(n2ϵ2/(κ2p))))\mathcal{O}(\exp(-\tilde{\Theta}(n^2\epsilon^2/(\kappa^2 p)))) (NNs) for our method. Footnote 4 also clarifies that classical DP-ERM bounds hide similar or worse condition numbers.

2. Scope of Claims: Interpolation and Comparison with Asi et al. (2022)

  • Interpolation vs. Over-parameterization: We appreciate the reviewer highlighting the scaling of κ\kappa when p≥np \ge n. Our core contribution is driven by interpolation (exact data fitting) rather than over-parameterization (p≫np \gg n). In classical regimes with p≤np \le n, the condition number κ=O(1)\kappa = \mathcal{O}(1) naturally holds. There, prior private ERM bounds remain polynomial (O~(p/(n2ϵ2))\tilde{\mathcal{O}}(p/(n^2\epsilon^2))), whereas our synchronized decay achieves exponential empirical risk even without over-parameterization.
  • Comparison with Asi et al. (2022): The degeneration when worst-case interpolation forces κ≥n\kappa \ge n is intrinsic to private interpolation rather than unique to our analysis. In fact, the foundational work on private interpolation, Asi et al. (2022), carries an explicit condition number in its exponent: exp⁡(−Θ~(nϵcκp))\exp(-\tilde{\Theta}(\frac{n\epsilon}{c\kappa\sqrt{p}})). When worst-case interpolation scales κ≥n\kappa \ge n, their bound degenerates as well. Under standard bounded conditioning (κ=O(1)\kappa = \mathcal{O}(1)), our bound improves the exponent from nϵ/pn\epsilon/\sqrt{p} to (nϵ/p)2(n\epsilon/\sqrt{p})^2. Furthermore, our algorithm uses standard DP-GD updates with closed-form decay (avoiding continuous infimal convolutions), eliminates their polynomial tail, and extends to non-convex neural networks.
  • Scope Clarification: In response to your suggestion, we have explicitly qualified our claims in the Abstract, the Introduction (Section 1), and Section 3.2 (below Theorem 3.6). We clarify that our exponential empirical risk bound applies when the condition number remains bounded (κ=O(1)\kappa = \mathcal{O}(1)). In Section 3.2, we also discuss that when κ\kappa scales with nn, the bound degenerates, consistent with prior interpolation literature.

3. Connection to Adaptive Clipping (Andrew et al., 2021)

Thank you for this constructive suggestion. Adaptive clipping methods such as Andrew et al. (2021) focus on practical empirical performance, using data-driven quantile estimation to dynamically tune clipping thresholds for general DP-SGD. However, they lack theoretical convergence guarantees under interpolation and do not prevent static noise accumulation. In contrast, our work focuses on the theoretical foundation, establishing that synchronously decaying the clipping threshold and noise variance achieves provable exponential empirical risk.

These two approaches are inherently complementary. While adaptive clipping provides practical heuristics for empirical tuning, integrating our provable synchronized decay mechanism into data-driven adaptive clipping frameworks could potentially unlock even superior empirical performance and tighter practical risk bounds. We have expanded this discussion in Section 1.1 (Related Work).

We hope these explicit parameter dependencies, clarified scopes, and updated comparisons address your remaining concerns.

Reviewer_enR4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

本文研究插值条件下差分隐私学习的经验风险界,重点关注固定噪声与裁剪阈值的局限:随着训练过程中逐样本梯度逐渐减小,固定尺度的隐私噪声可能主导模型更新,阻碍进一步收敛。 This paper studies empirical risk bounds for differentially private learning under interpolation, focusing on the limitations of fixed noise scales and clipping thresholds, where privacy noise may dominate model updates as per-sample gradients diminish during training, hindering further convergence.

Critical strengths

研究动机清晰,针对插值条件下逐样本梯度不断减小、固定尺度隐私噪声逐渐阻碍优化的问题,为同步衰减裁剪阈值与噪声尺度提供了合理依据。 方法简洁,仅需对标准 DP-GD 的裁剪阈值和噪声尺度进行同步调度;MNIST 和 CIFAR-2 实验展示了其相较于所选固定配置更好的收敛表现。 1.The motivation is clear and addresses an important limitation of private learning under interpolation: fixed-scale privacy noise can increasingly hinder optimization as per-sample gradients diminish, motivating synchronized decay of the clipping threshold and noise scale. 2.The method is simple, requiring only synchronized scheduling of the clipping threshold and noise scale in standard DP-GD. Experiments on MNIST and CIFAR-2 demonstrate improved convergence over the evaluated fixed configurations.

Critical weaknesses

数据依赖的参数选择与隐私保证之间的兼容性需要澄清。定理 3.6 和 4.4 根据初始训练损失 L(w0)L(w_0) 设置裁剪阈值 C0C_0,但附录 D.2–D.3 的隐私分析在相邻数据集之间使用相同的阈值和噪声方差。作者应说明如何在不引入额外隐私泄露的情况下确定这些参数,例如使用公开的数据无关上界,或计入相应的隐私估计开销。 随机训练的有限步数隐私分析需要补充论证。附录 G 将 μtotal≤qsT(e4/σ2−1)\mu_{\mathrm{total}}\le q_s\sqrt{T(e^{4/\sigma^2}-1)} 直接用于定理 5.1 的隐私保证,但所引文献中的对应表达式来自渐近组合分析。作者应提供该不等式在有限 TT 下成立的依据,或采用具有严格有限步数保证的隐私会计方法。 实验对照和理论验证仍不充分。附录 I 主要比较固定配置的标准 DP-GD 与不同衰减率的 ND-DP-GD,未报告基线裁剪阈值的系统调优,也未与已有动态裁剪或噪声调度方法比较。此外,缺少系统改变样本量 nn 和参数量 pp 的实验,因而尚未直接验证所提出风险界的尺度依赖关系。 1.The compatibility between data-dependent parameter choices and the privacy guarantee requires clarification. Theorems 3.6 and 4.4 set the initial clipping threshold C0C_0 using the initial training loss L(w0)L(w_0), whereas the privacy analysis in Appendices D.2–D.3 uses identical thresholds and noise variances across neighboring datasets. The authors should explain how these parameters can be determined without additional privacy leakage, for example through public, data-independent bounds or explicit accounting for private estimation. 2.The finite-step privacy analysis for stochastic training requires further justification. Appendix G directly uses μtotal≤qsT(e4/σ2−1)\mu_{\mathrm{total}}\le q_s\sqrt{T(e^{4/\sigma^2}-1)} to establish the privacy guarantee in Theorem 5.1, although the corresponding expression in the cited work arises from asymptotic composition analysis. The authors should justify this inequality for finite TT or use a privacy accountant with rigorous finite-step guarantees. 3.The experimental comparisons and validation of the theoretical scaling remain limited. Appendix I primarily compares standard DP-GD with fixed configurations against ND-DP-GD with different decay rates, without reporting systematic tuning of the baseline clipping threshold or comparisons with existing dynamic clipping and noise scheduling methods. Moreover, no systematic variation of sample size nn and parameter dimension pp is provided, leaving the claimed scaling of the risk bound without direct empirical validation.

Questions for authors

See Weaknesses

1 comment

We thank the reviewer for the careful review, and for acknowledging the motivation, simplicity, and convergence of ND-DP-GD. Major revisions are highlighted in cyan in the revised PDF. We address your concerns below:

W1: "The compatibility between data-dependent parameter choices and the privacy guarantee requires clarification. Theorems 3.6 and 4.4 set the initial clipping threshold C0C_0 using the initial training loss L(w0)\mathcal{L}(\mathbf{w}_0) ..."

A: Thank you for pointing this out, and we apologize for the confusion. We agree with the reviewer that the phrasing in the original version of the theorems could give the impression that C0C_0 was set directly using L(w0)\mathcal{L}(\mathbf{w}_0). In fact, C0C_0 does not need to depend on L(w0)\mathcal{L}(\mathbf{w}_0) in either the privacy or the convergence analysis. We have revised the theorem statements and proofs to clarify this (see Theorems 3.6, 4.4, 5.3, and Remark 3.7 in the revised PDF). Specifically, the convergence theorems hold for any pre-fixed, data-independent constant C0C_0 that falls within a valid range, e.g., β2L(w0)μ≤C0≤c0β2L(w0)μ\beta \sqrt{\frac{2\mathcal{L}(\mathbf{w}_0)}{\mu}} \le C_0 \le c_0\beta \sqrt{\frac{2\mathcal{L}(\mathbf{w}_0)}{\mu}} in Theorem 3.6 (and similarly in Theorems 4.4 and 5.3), where c0≥1c_0 \ge 1 is a constant. In practice, as noted by the reviewer, C0C_0 can be set using a public upper bound Lmax⁡≥L(w0)L_{\max} \ge \mathcal{L}(\mathbf{w}_0) without accessing private data (Remark 3.7).

The privacy mechanism itself is independent of these convergence conditions. In Algorithm 1, the initial clipping threshold C0>0C_0 > 0 is a pre-fixed, data-independent hyperparameter specified prior to training, like the learning rate η\eta and decay rate qq. Because the schedules Ct=C0qtt=0T−1\\{C_t = C_0 q^t\\}_{t=0}^{T-1} and Ctσt=0T−1\\{C_t \sigma\\}_{t=0}^{T-1} remain identical across any two adjacent datasets, the (ϵ,δ)(\epsilon, \delta)-DP guarantees in Theorems 3.8 and 5.1 hold unconditionally for all datasets, regardless of L(w0)\mathcal{L}(\mathbf{w}_0) or whether clipping occurs.

W2: "The finite-step privacy analysis for stochastic training requires further justification... justify this inequality for finite TT or use a privacy accountant with rigorous finite-step guarantees."

A: Thank you for this helpful observation. We agree that a finite-step privacy accountant should be used for Theorem 5.1. Note that this asymptotic issue is specific to the stochastic variant ND-DP-SGD with Poisson subsampling (Theorem 5.1); for full-batch ND-DP-GD, both Theorem 3.8 (based on the Moments Accountant) and the GDP composition in Appendix E hold for every finite TT without asymptotic approximations.

In the revised PDF, we have updated Theorem 5.1 and its proof (Appendix G.1) using the finite-step Moments Accountant framework of Abadi et al. (2016, Theorem 1). Under Poisson subsampling with rate qsq_s, the Moments Accountant guarantees (ϵ,δ)(\epsilon, \delta)-DP for σ≥c2qsTln⁡(1/δ)ϵ\sigma \ge c_2 \frac{q_s \sqrt{T \ln(1/\delta)}}{\epsilon} with a constant c2>0c_2 > 0. With this noise scaling σ=O(qsTln⁡(1/δ)ϵ)\sigma = \mathcal{O}\left(\frac{q_s \sqrt{T \ln(1/\delta)}}{\epsilon}\right), the convergence and empirical risk bounds (Theorem 5.3 and Corollary 5.4) remain unchanged.

W3a: "Appendix I primarily compares standard DP-GD with fixed configurations..., without reporting systematic tuning of the baseline clipping threshold or comparisons with existing dynamic clipping and noise scheduling methods."

A: For standard DP-GD with fixed configurations, we use the same initial hyperparameters (C0C_0, σ\sigma, and η\eta) 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. 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).

W3b: "Moreover, no systematic variation of sample size nn and parameter dimension pp is provided, leaving the claimed scaling of the risk bound without direct empirical validation."

A: Thank you for this suggestion. We have added synthetic linear regression experiments under interpolation varying sample size nn, parameter dimension pp, and privacy budget ϵ\epsilon (see Appendix I.3 and Figure 3 in the revised PDF). The empirical log-risk ratio ln⁡(LT/L0)\ln(\mathcal{L}_T/\mathcal{L}_0) scales linearly with n2n^2 (R2=0.9993R^2 = 0.9993), 1/p1/p (R2=0.9999R^2 = 0.9999), ϵ2\epsilon^2 (R2=0.9981R^2 = 0.9981), and n2/pn^2/p (R2=0.9924R^2 = 0.9924), confirming the −n2ϵ2/p-n^2\epsilon^2/p rate.

References:

Abadi et al. (2016). "Deep learning with differential privacy."

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."

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.