{"id":"1687d689-9c72-4f96-895b-e3c256a6764c","arxiv_id":"2509.09485","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":6,"one_line_summary":"D2P2-SGD combines time-decreasing privacy noise with random projection to improve the accuracy of differentially private SGD, with convergence rates matching ordinary SGD.","lead":"Researchers built an optimizer named D2P2-SGD that adds less and less noise during training while compressing gradients into a lower-dimensional space, aiming to keep models both useful and private. The paper gives mathematical convergence guarantees and tests the method on image classification tasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Privacy proof's 'sensitivity Δ=1' ignores the projection: the noise-perturbed query is (1/√p)A^T g, whose sensitivity is ||A||_2/√p ~ √(d/p), not 1; Theorem 1's d-independent σ_ε is therefore unsupported.","rationale":"The reader's weakest assumption—that the projection multiplies the sensitivity instead of preserving it—is exactly the load-bearing gap I find. Theorem 1 is the foundation of both the paper's privacy claims and the subsequent utility/privacy tradeoff statements. If the noise is calibrated to sensitivity 1 but the actual projected query has sensitivity scaling with ||A||_2, the privacy guarantee is unsupported. This is not a disagreement with a community consensus; it is an internal inconsistency in the proof. Lemma 5 explicitly says 'this ensures the sensitivity Δ=1 for the mini-batch sum' while the mechanism in Algorithm 1 perturbs (1/√p)A_k^T g_k, not g_k. The missing factor ||A_k||_2/√p is large for Gaussian projections and depends on d. I also note secondary algebraic errors in the utility proofs (e.g., E[A_k^T A_k] is d σ_A^2 I_p, not p σ_A^2 I_p, so the perturbation-term bound changes), but the privacy flaw alone is sufficient to reject the paper as written. The approach may be salvageable by normalizing the projection or scaling noise by the spectral norm, but that would change the stated rates and privacy parametrization. I therefore recommend keeping the reader's REJECT verdict.","tokens_in":25903,"tokens_out":14842,"duration_ms":189844,"concrete_test":"Re-derive Lemma 5 with the correct query. Let q(D) = (1/√p)A^T g(D). Its sensitivity is S(A) = (2/(B√p))||A||_2. Substitute S(A) for Δ=1 into the per-step Rényi bound used for Eq. (12), i.e. replace σ_ε^2 by σ_ε^2 / S(A)^2 in the denominator. If the resulting condition forces σ_ε^2 = Ω( d log(1/δ) / (n^2 ε^2) ) rather than the stated C2 B^2 K^2 log(1/δ)/(n^2 ε^2), Theorem 1's independence from d is disproved. For a quick numerical confirmation, set d=1000, p=100, draw A~N(0,I_{d×p}) once, and compute ||A||_2/√p; the median over many draws is approximately (√d+√p)/√p ≈ 4.16, directly contradicting the 'sensitivity 1' premise. Also check whether any part of Appendix A.3 bounds S(A) or accounts for the probability of large ||A||_2; it does not.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central privacy claim (Theorem 1) rests on Lemma 5 (Appendix A.3), which asserts that per-sample clipping to ℓ2 norm 1 gives sensitivity Δ=1 for the mini-batch query. But Algorithm 1 (Line 6) does not add Gaussian noise to g_k; it adds noise to the projected query q_k = (1/√p) A_k^T g_k, then post-processes by multiplying with A_k. For a neighboring dataset differing in one sample, ||Δg_k|| ≤ 2/B, so the ℓ2 sensitivity of q_k is S_k = (1/√p) sup_{||v||≤1} ||A_k^T v|| = ||A_k||_2/√p (up to the 2/B factor). For A_k with iid N(0,1) entries, ||A_k||_2 = Θ(√d + √p) with high probability, so S_k grows like √(d/p), not 1. Lemma 5 never accounts for this; the moments bound (Eq. 12) is only valid for sensitivity 1. The post-processing argument in the main text does not rescue this: post-processing preserves DP only if q_k + ε_k is already a DP mechanism, and that is precisely what fails. A JL-style high-probability argument would still need to bound the sup over all neighboring gradients (a continuum) and to fold the probability of large ||A_k||_2 into δ; the paper provides neither. Consequently, the stated σ_ε, independent of d and p, is not sufficient for the claimed (ε,δ)-DP guarantee as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces D2P2-SGD, a differentially private SGD variant that combines (i) a dynamic (time-varying) Gaussian noise schedule for DP, (ii) per-sample gradient normalization as automatic clipping, and (iii) random projection of the mini-batch gradient into a lower-dimensional space. The main theoretical claims are an (ε,δ)-DP guarantee (Theorem 1), sub-linear convergence rates for convex objectives (Theorem 2, Corollary 1) and non-convex objectives (Theorem 3, Corollary 2), and a formal trade-off among utility, privacy, and projection dimension. Experiments on FashionMNIST, SVHN, CIFAR-10, and other datasets are reported to support the claims.","tokens_in":26373,"tokens_out":15147,"duration_ms":174133,"significance":"If the results were correct, the paper would offer a useful combination of dynamic privacy budgeting and random projection, with a potentially practical reduction in the dimension of injected noise. The paper is clearly written, includes code, and reports experiments across a wide set of datasets and baselines. The automatic-clipping mechanism from Bu et al. is competently integrated into the algorithm. However, the central theoretical results are not established: the privacy proof ignores the effect of the random projection on sensitivity, the convergence theorems contain an incorrect linear-algebra identity, and the stated convergence rates do not withstand substitution of the privacy-required noise magnitude. These are load-bearing issues that affect the main contributions of the paper.","major_comments":[{"comment":"The privacy proof assumes the sensitivity of the noisy query is 1, but that is false for the actual mechanism. Line 6 of Algorithm 1 adds Gaussian noise to q_k = (1/√p) A_k^T g_k, not to g_k. For two neighboring datasets differing in one sample, the ℓ2 sensitivity of q_k is (1/(B√p)) ||A_k^T (ĝ_s − ĝ_s')||, which scales with the spectral norm of A_k. For A_k with iid N(0,1) entries, ||A_k||_2 = Θ(√d + √p) with high probability, so the sensitivity is Θ(√(d/p)), not 1. Lemma 5's bound in Eq. (11) and the resulting σ_ε^2 bound in Theorem 1 are therefore unsupported. The post-processing argument in §3.2 does not apply, because the noise is added after projection; post-processing preserves DP only if q_k + ε_k is already a DP release, which is exactly what is in question. A valid analysis would need to condition on the realized A_k, set the noise variance proportional to ||A_k||^2/p, and fold","section":"Appendix A.3, Lemma 5; Theorem 1 (Section 3.2)"},{"comment":"The stated convergence rates are inconsistent with the privacy requirement. The noise term in Theorem 2 (Eq. (2)) is O(α p^{1.5} lnK σ_ε^2 / K). Theorem 1 requires σ_ε^2 = Ω(B^2 K^2 ln(1/δ)/(n^2 ε^2)). Substituting this into Eq. (2) with α = O(1/√K) gives a noise term Ω(B^2 p^{1.5} √K lnK ln(1/δ)/(n^2 ε^2)), which diverges as K grows. The same issue appears in Theorem 3 (Eq. (3)). Thus Corollaries 1 and 2 do not follow from the privacy theorem; they treat σ_ε as a constant independent of K, which is incompatible with Theorem 1. The claim of 'matching the best available rate' is therefore not supported for the privacy-compliant algorithm.","section":"Theorems 2 and 3, Corollaries 1 and 2"},{"comment":"The proof incorrectly computes E[‖A_k ε_k‖²]. For a d×p matrix A_k with iid N(0, σ_A²) entries, E[A_k^T A_k] = d σ_A² I_p, not p σ_A² I_p. Therefore E[‖A_k ε_k‖²] = d p σ_A² σ_ε,k², not p² σ_A² σ_ε,k². This error propagates into Eq. (2) and Eq. (3): the additive-noise term should scale as d√p rather than p^{3/2}. Since the paper's motivation is that random projection reduces the influence of the ambient dimension d on the injected noise, this is not a cosmetic typo; it changes the central dimension-privacy-utility trade-off claimed in Section 3.2.","section":"Appendix A.4, proof of Theorem 2; also used in Theorem 3"},{"comment":"The dimension-privacy-utility comparison is not a valid implication of Theorem 1. Theorem 1 states that σ_ε^2 = C₂ B² K² ln(1/δ)/(n² ε²) for universal constants C₁, C₂. In Appendix A.5, however, C₂ is set to nε/(p^{5/2} K lnK √ln(1/δ)), which depends on ε, K, p, and n and is therefore not a constant. The subsequent 'privacy error' terms in Eqs. (23)–(24) and (35)–(36) are constructed by this choice and do not follow from the theorem. This undermines the quantitative conclusions about how projection reshapes the privacy-utility trade-off.","section":"Appendix A.5 and A.8"}],"minor_comments":[{"comment":"The theorem statement says 'for any ε ≤ C₁B²K/n²', but the proof concludes using ε = C₁B²K²/n². The exponent of K is inconsistent and should be corrected.","section":"Theorem 1 statement and proof"},{"comment":"The condition reads 'If the step size α ≤ 1/(2L), and, then ...'; there is a stray 'and'.","section":"Theorem 3 statement"},{"comment":"Lemma 5 refers to the 'mini-batch sum' and sets sensitivity Δ=1, while Algorithm 1 uses the mini-batch average g_k = (1/B)∑ ĝ_s. The factor of B (and the factor 2 arising from sample replacement) should be made explicit so that the privacy accountant's normalization is clear.","section":"Algorithm 1 and Lemma 5"},{"comment":"The non-convex section writes E[f(¯x_K) − f*] even though Theorem 3 bounds the expected gradient norm; this is a confusing reuse of the convex notation.","section":"Appendix A.8, Eq. (35)"}],"recommendation":"reject","confidential_remarks":"The load-bearing issues are severe: the privacy guarantee as stated is not proven and the convergence rates do not hold when the privacy-required noise magnitude is inserted. These are not local presentation errors; a correct treatment would require redesigning the privacy analysis (and likely the algorithm) and re-deriving the utility bounds. I therefore cannot recommend acceptance in either its current or a lightly revised form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the central privacy claim doesn't hold as written. Lemma 5 asserts per-sample clipping gives sensitivity Δ=1 for the mini-batch sum, but the mechanism's actual query before noise is (1/√p) A_k^T g_k. For neighboring datasets, the ℓ2 sensitivity of that query is roughly (2/B)·∥A_k∥_2/√p, and ∥A_k∥_2 ≈ √d+√p. So the Gaussian noise variance in Theorem 1, independent of d and p, cannot deliver the stated (ε,δ) guarantee. Post-processing doesn't rescue it, because the noisy projected query must itself be DP, and that is precisely what fails. A JL-style argument would need to bound the sup over all neighboring gradients and fold the probability of large ∥A_k∥_2 into δ; neither is present. The utility proofs are in better shape but have a real slip: E[A_k^T A_k] = d σ_A^2 I_p, not p σ_A^2 I_p, so the noise-term constants in Theorems 2–3 are off (probably not the rates).\n\nWhat the paper does well: the combination of dynamic DP, automatic clipping, and random projection is genuinely new as a package; the convex analysis is explicit; and the experiments are extensive and fairly reported. The authors don't oversell — they note D2P2-SGD is for moderate privacy regimes, that high privacy remains hard, and that choosing p is not yet principled. The accuracy gains over DPSGD on FashionMNIST/SVHN at ε around 2.5 are visible, and the intuition that projection shrinks the noise dimension while preserving the dominant gradient directions is worth taking seriously.\n\nHonest bottom line: this is a salvageable paper with a serious, identified flaw. If the sensitivity of the projected query is bounded properly — for example, by choosing A with bounded spectral norm, or by folding ∥A∥_2 into the noise scale and the analysis — the rest of the framework and experiments would likely survive. As written, the privacy guarantee is unproven.\n\nFor your question: I would send it to a serious referee, but with the expectation that the referee would ask for the sensitivity analysis to be redone, not for the idea to be abandoned. I wouldn't cite it in the current form; I'd cite the components (Du et al. 2021, Kasiviswanathan 2021, Bu et al. 2024) instead. Worth a reading group if you want to think through the projection-sensitivity pitfall.","headline":"The random-projection DP idea is worth engaging, but the privacy proof's sensitivity calculation ignores the projection and the theorem as written does not go through.","tokens_in":26832,"tokens_out":3551,"would_cite":false,"duration_ms":42638,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","90C15","90C25","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"D2P2-SGD: private training at non-private SGD speed","keywords":["differential privacy","stochastic gradient descent","random projection","dynamic privacy noise","gradient clipping","convex optimization","non-convex optimization","sub-linear convergence"],"falsifier":"Calculate the l2 sensitivity of the released quantity (1/√p)A^T g for a Gaussian matrix A with d=1000, p=100 and two neighboring datasets whose clipped gradients differ by a unit vector; the sensitivity concentrates around (√d+√p)/√p ≈ 4.16, not 1. If this exceeds the value used in the privacy accountant, Theorem 1's (ε,δ) bound cannot hold as stated.","tokens_in":25846,"feed_emoji":"🔒","tokens_out":10040,"duration_ms":100382,"temperature":0.7,"pith_summary":"The paper introduces D2P2-SGD, a stochastic optimizer that trains models under differential privacy by combining three mechanisms: per-sample gradient clipping that needs no threshold tuning, a Gaussian noise scale that decreases over the course of training, and random projection of gradients into a low-dimensional space before noise is added. The authors claim this design preserves the (ε,δ)-differential privacy guarantee while achieving sub-linear convergence rates of O(1/√K + lnK/K^{1.5}) for both convex and non-convex objectives, matching the best available rate of standard SGD. If correct, the method would let practitioners train private models with less accuracy loss than static-noise differentially private SGD, and with noise cost tied to the projected dimension rather than the full parameter dimension. The paper also reports experiments on several image datasets suggesting the optimizer outperforms static and dynamic baselines.","feed_headline":"D2P2-SGD: private training at non-private SGD speed","feed_subtitle":"Less noise late in training plus low-dimensional gradients means private models with less accuracy loss.","key_machinery":"The update rule is x_{k+1} = x_k − α A_k( (1/√p) A_k^T g_k + ε_k ), where g_k is the mini-batch gradient after per-sample clipping, A_k is a d×p Gaussian random matrix, and ε_k ~ N(0, σ²_{ε,k} I_p) with σ²_{ε,k} = σ²_ε/k. The privacy argument treats the sequence of projected noisy gradients as a composition of subsampled Gaussian mechanisms and relies on the unit l2 sensitivity of the clipped per-sample gradients. The convergence analysis controls the distortion introduced by the random projection through its sampling variance σ_A², yielding error terms that scale with p^{3/2} and p d² σ_A² and vanish at the claimed rates.","core_discovery":"The central claim is that dynamic privacy noise and random projection can be combined without sacrificing the convergence rate of SGD. Theorem 1 states that D2P2-SGD is (ε,δ)-differentially private whenever the base noise variance satisfies σ²_ε ≥ C₂ B² K² ln(1/δ)/(n² ε²), with B the mini-batch size, n the dataset size, and K the number of iterations. Theorems 2 and 3 respectively give expected suboptimality bounds for convex and non-convex objectives; with step size α = O(1/√K), these become O(1/√K + lnK/K^{1.5}) for convex functions, and the same rate plus a clipping-bias term for non-convex functions. The mechanism works by projecting the clipped mini-batch gradient onto a random low-dime","pith_inferences":["A cautionary extension: the stated privacy guarantee assumes the projected gradient keeps unit l2 sensitivity, but for a Gaussian projection the sensitivity scales with the spectral norm of A_k/√p; unless the projection is normalized or the sensitivity is recomputed, the (ε,δ) bound in Theorem 1 may not hold as written.","A practical variant the paper does not explore is fixing the random projection matrix across iterations, which would cut the per-iteration cost from O(dp) to an amortized O(dp/K) and might admit a different privacy analysis.","The same dynamic-noise scheduler could replace random projection with other dimensionality reducers, such as quantization or sketching, yielding a family of private optimizers whose noise cost tracks the compressed dimension rather than the parameter count."],"forward_implications":["Differentially private training can asymptotically match the convergence rate of ordinary SGD, up to logarithmic factors, for both convex and non-convex objectives.","The injected noise variance depends on the projection dimension p rather than the parameter dimension d, so private training of very large models becomes less expensive.","The decreasing noise schedule lets practitioners shift more privacy cost to early iterations, effectively spending the privacy budget where it matters least for final utility.","The static-noise and non-projected versions of private SGD appear as special cases, so the analysis provides a unified convergence and privacy treatment of these variants."],"fun_headline_variants":["Dynamic privacy plus random projection: SGD speed stays","Private SGD without rate loss: dynamic noise and random projections","D2P2 matches SGD rates while keeping data private","Less noise later, random projections: private learning stays fast"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The privacy proof assumes that random projection leaves the l2 sensitivity of the mini-batch gradient at 1; for a Gaussian projection matrix, the sensitivity of (1/√p)A^T g actually scales with the spectral norm of A/√p, which typically exceeds 1, so the stated (ε,δ) guarantee depends on an assumption that is likely false.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic privacy plus random projection: SGD speed stays","Private SGD without rate loss: dynamic noise and random projections","D2P2 matches SGD rates while keeping data private","Less noise later, random projections: private learning stays fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000738,"raw_usage":{"total_tokens":3147,"prompt_tokens":775,"completion_tokens":2372,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":2319}},"tokens_in":519,"tokens_out":2372,"duration_ms":18526,"temperature":1.0,"reasoning_tokens":2319,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T19:01:39.046752+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Calculate the l2 sensitivity of the released quantity (1/√p)A^T g for a Gaussian matrix A with d=1000, p=100 and two neighboring datasets whose clipped gradients differ by a unit vector; the sensitivity concentrates around (√d+√p)/√p ≈ 4.16, not 1. If this exceeds the value used in the privacy accountant, Theorem 1's (ε,δ) bound cannot hold as stated.","supporting_citations":[],"review_version":1}