{"id":"1b6aea22-387a-4e0e-acd5-6c735cd19130","arxiv_id":"1908.07643","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Coordinate-wise adaptive clipping in DP-SGD, with per-coordinate scales derived from a noise-minimization problem, yields higher MNIST accuracy than standard L2 clipping at the same privacy budget.","lead":"AdaCliP is a differentially private version of SGD that clips each gradient coordinate with its own adaptive scale, chosen to minimize the total added noise. A smart generalist might read it because it offers a principled way to recover model accuracy that privacy noise normally destroys.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5's per-example/mean-noise equivalence is off by a factor √B in the noise scale, so the moments-accountant input does not match the mechanism that is actually run; the stated ε is not derived from the algorithm as written.","rationale":"The reader identifies the most attackable point: the relationship between per-example noise addition and noise added to the mean. Working through the algorithm's averaging, the released update has noise scale σ/√B in the transformed space, while the sensitivity of the mean of unit-ball vectors is O(1/B), giving an effective per-step Gaussian noise scale z = σ√B/2 rather than σ. The paper's sentence asserting equivalence is false, so the moments-accountant input is not derived from the mechanism actually run. However, for the experimental batch size B=600, the corrected z is larger than the value fed to the accountant, meaning the reported ε is conservative and the empirical privacy claim would survive a corrected analysis; the defect is a missing proof, not an observed privacy violation. The additional concern about variance debiasing under clipping is real but secondary: it undermines the optimality of the estimated b_t, not the privacy accounting itself. The convergence analysis also assumes oracle statistics, but that is a standard gap for adaptive methods and is less central than the privacy accounting. I therefore keep the reader's CONDITIONAL verdict unchanged, while agreeing partially with the stated weakest assumption.","tokens_in":14728,"tokens_out":30296,"duration_ms":306289,"concrete_test":"Run the moments accountant (or RDP accountant) on the actual per-step mechanism: release (1/B)Σ clip((g_k−m_t)/b_t) plus N(0, σ²/B I) in transformed coordinates, with m_t and b_t fixed from the history, sensitivity 2/B, sampling probability q=B/N, and the same T and δ as in Tables 1 and 2. Use the effective noise scale z = σ√B/2 and compare the resulting ε_corrected with the reported ε. If ε_corrected ≤ ε_reported for all configurations, the privacy claim can be restored by correcting the accountant input; if ε_corrected > ε_reported for any configuration (including small B), the reported privacy is invalid and the experiments would need to be rerun with corrected accounting.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 asserts that adding N(0,σ²I) to each per-user transformed gradient and then averaging is 'essentially equivalent' to adding the same noise to the mean. For a batch of size B, the released average has noise covariance (b_t b_tᵀ)σ²/B, not (b_t b_tᵀ)σ². Conditioned on the history (including the data-dependent m_t and b_t), the step is a Gaussian mechanism with sensitivity bounded by 2‖b_t‖/B and noise std ‖b_t‖σ/√B, so the effective per-step noise scale is z = σ√B/2 (up to the usual factor of 2 in the sensitivity). The paper supplies no conditional-privacy derivation for the adaptive, data-dependent clipping vectors; it feeds σ into an accountant calibrated for a different mechanism. For the experiments with B=600 the corrected z is larger than σ, so the reported ε is conservative and the central privacy claim is likely salvageable; but for B<4 the discrepancy goes the other way, and in any case 'essentially equivalent' is not a proof. The claim 'provably adds less noise under (ε,δ)-DP' is therefore not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AdaCliP, a differentially private SGD method with coordinate-wise adaptive clipping. In the proposed framework, a stochastic gradient is transformed by subtracting a vector a_t and dividing by a vector b_t, clipped to unit L2 norm, and perturbed with Gaussian noise; Theorem 1 states that under a constraint E||w_t||^2 <= gamma, the optimal choices are a_t equal to the true gradient mean and b_t proportional to coordinate standard deviations, yielding noise whose squared norm scales as the square of the sum of standard deviations rather than d times the L2-clipping noise. Algorithm 1 estimates these quantities from noisy gradients and averages per-user noisy gradients over a minibatch. Experiments on a synthetic regression and on MNIST for logistic regression and a neural network report that AdaCliP achieves better accuracy than L2 clipping and noise proportional to the gradient norm bound for the same reported (epsilon,delta).","tokens_in":14897,"tokens_out":9063,"duration_ms":95862,"significance":"The core optimization idea is attractive and the derivation in Theorem 1 is transparent: if the privacy mechanism is genuinely the one analyzed in Section 4.1, coordinate-wise adaptive clipping provably reduces added noise relative to uniform clipping, and the empirical gains on MNIST would be valuable. The paper also gives a concrete algorithm and an explicit experimental protocol, which are assets. However, the advertised privacy guarantee is not established as written, because the noise accounting in Section 5 does not match the mechanism actually run in Algorithm 1, and because the convergence theorem is proved for an idealized variant with batch size 1 and a_t equal to the true gradient mean. The central claim is therefore currently conditional on a repair of the privacy analysis.","major_comments":[{"comment":"The sentence 'adding Gaussian noise to the individual user processed gradient and to the mean processed gradient is essentially equivalent' is not correct as stated. If each per-user transformed gradient receives N(0,sigma^2 I), the averaged noisy gradient has noise covariance (b_t b_t^T) sigma^2 / B, whereas the framework of Section 4.1 assumes the mean receives N(0,sigma^2 I). Conditioned on the history, so that b_t is fixed, the per-step mechanism has L2 sensitivity 2||b_t||/B and noise standard deviation ||b_t|| sigma / sqrt(B), giving an effective Gaussian-mechanism noise scale z = sigma sqrt(B)/2 (up to the usual factor of 2 in the sensitivity convention) rather than sigma. The moments accountant is therefore invoked with the wrong per-step privacy parameter, so the reported (epsilon,delta) is not derived from the algorithm as written and the claimed 'provably adds less noise under (epsilon,delta)-DP' is not established. For the experimental batch size B=600 the corrected z is larger and the reported epsilon would be conservative, but for B<4 the opposite holds. Please either modify Algorithm 1 to scale the per-user noise by sqrt(B), or add the noise directly to the mean with scale sigma, and in either case provide a conditional-privacy analysis that accounts for the data-dependent b_t.","section":"Section 5, Algorithm 1"},{"comment":"The debiasing identity used for the variance estimate, deriving E[(g_t^i - m_t^i)^2] from E[(~g_t^i - m_t^i)^2] - (b_t^i)^2 sigma^2, is derived under the assumption that clipping does not take place, i.e., ~g_t = g_t + b_t N_t. This directly conflicts with the design premise of the paper, which states that E||w_t||^2 <= gamma ensures that w_t is clipped with constant probability. Consequently the variance estimate is biased precisely in the operating regime the algorithm targets. In addition, if per-user noise is averaged over a batch, the correction should involve sigma^2 / B rather than sigma^2. This should be acknowledged as a heuristic, or the estimator should be analyzed in the presence of clipping.","section":"Section 5, variance estimator"},{"comment":"Theorem 2 is stated for batch size 1 and for a_t equal to the true expectation E[g_t], while Algorithm 1 uses a minibatch of size B and replaces a_t by the exponential moving average m_t of noisy gradients defined in Eq. (4). The convergence bound therefore does not apply to the algorithm whose accuracy is reported in Section 6. Since the theoretical motivation for AdaCliP rests on this bound, the paper should either extend the analysis to the estimated a_t and b_t (with batch size B), or explicitly state Theorem 2 as an ideal-population analysis and provide a separate, weaker guarantee for the implemented variant.","section":"Section 4.2, Theorem 2"}],"minor_comments":[{"comment":"The notation s_t^i = Σ E[(g_t^i - E g_t^i)^2] appears to be a typo; it should denote the coordinate variance E[(g_t^i - E g_t^i)^2] or its square root, since the proof uses (s_t^i)^2 in the numerator. Please make the definition of s_t^i unambiguous.","section":"Section 4, Theorem 1 and Theorem 2"},{"comment":"The expression for b_t^i in Algorithm 1 is rendered ambiguously in the text; the intended formula b_t^i = sqrt(s_t^i / gamma) * sqrt(sum_j s_t^j) should be written explicitly with parentheses so that the derivation in Theorem 1 is reproducible.","section":"Section 5, Eq. (5)"},{"comment":"The text contains 'deferentially private momentum optimization'; this should be 'differentially private'.","section":"Appendix B"},{"comment":"Figure 3 reports an average noise ratio around 0.8, but no error bars or number of independent runs are given; since this figure directly supports the claim of reduced added noise, some measure of variability would be helpful.","section":"Section 6, Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The core noise-minimization derivation is sound and the empirical direction is promising, so I would not reject on novelty or correctness-of-Theorem-1 grounds. The blocking issue is the mismatch between the mechanism analyzed and the mechanism implemented in Algorithm 1; this is fixable by rescaling per-user noise and redoing the accounting, and for B=600 the reported numbers would likely be conservative rather than invalid. The self-citation for Lemma 2 is not a concern in my view, as the lemma is a standard SGD bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know about this paper is that the core optimization is genuinely new and clean: instead of clipping the whole gradient or adapting a single L2 threshold, AdaCliP chooses per-coordinate scales by minimizing the expected squared noise subject to a variance budget. Theorem 1 is a neat Holder-inequality argument, and the regression example makes the factor-d improvement vivid. The MNIST results are consistent and modest (0.2-1.6% accuracy gains), and the measured noise ratio backs the theory. I was not expecting to like it as much as I did.\n\nThe soft spots are real but not fatal. Section 5 says adding Gaussian noise to each per-user gradient and adding it to the mean is 'essentially equivalent.' That is not a proof. As the stress-test note says, for batch size B the averaged per-user noise has covariance b b^T sigma^2 / B, while the accountant is fed sigma for a sensitivity-1 mechanism. So the accountant input does not match the mechanism. However, the direction of the discrepancy is in the authors' favor: with B=600, the effective per-step noise-to-sensitivity ratio is sigma sqrt(B)/2, which is much larger than sigma, so the reported epsilon is conservative. The privacy claim is likely salvageable, but only after the authors actually write down the per-step conditional sensitivity and the resulting z, rather than hand-waving equivalence.\n\nThe second gap is theory-to-algorithm transfer. Theorem 2 assumes a_t equals the true gradient mean; the algorithm estimates it from noisy gradients, and the variance estimator subtracts b_i^2 sigma^2 under an assumption that clipping does not happen. That conflicts with the analysis, which relies on clipping occurring with constant probability. This is worth a proper derivation or at least an explicit statement of what is heuristic.\n\nAlso minor: h2 is tuned but never reported, no code is released, and the experiments omit the adaptive L2 clipping baselines the authors themselves cite (van der Veen et al., Thakkar et al.). For a paper whose claim is 'adds less noise than previous methods,' those comparisons matter.\n\nThe citation pattern is fine; Lemma 2 is self-cited but standard.\n\nBottom line: this is a serious piece of work, the central idea is sound, but the privacy accounting needs to be rewritten before the headline claim is established. I would send it to a good referee and ask for a revision.","headline":"A clean per-coordinate clipping idea with a real privacy-accounting gap; the sqrt(B) issue is genuine but runs in the authors' favor here, so the paper deserves a careful revision rather than rejection.","tokens_in":15499,"tokens_out":4528,"would_cite":true,"duration_ms":604958,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive per-coordinate clipping gives the same differential-privacy guarantee with substantially less added noise than standard L2 clipping.","keywords":["differential privacy","stochastic gradient descent","adaptive clipping","coordinate-wise clipping","Gaussian mechanism","moments accountant","gradient noise","MNIST"],"falsifier":"Run Algorithm 1 exactly as written and feed its per-step noisy gradients to a moments accountant, comparing the resulting $\\epsilon$ with the values in Tables 1 and 2; a discrepancy would show the per-example-versus-mean noise equivalence fails at the implemented scale. Separately, on the paper's regression example with $d=1000$ and one informative coordinate, measure the empirical average of $\\|b_t\\|^2\\sigma^2$; if the injected noise grows with $d$, the predicted factor-$d$ reduction is absent.","tokens_in":14459,"feed_emoji":"🔒","tokens_out":15455,"duration_ms":152127,"temperature":0.7,"pith_summary":"AdaCliP is a differentially private SGD algorithm whose central claim is that the usual way of bounding gradient sensitivity—clipping the whole gradient vector's norm—adds more noise than necessary. The paper derives the optimal coordinate-wise scaling: after centering each gradient by its estimated mean, each coordinate is scaled in proportion to the square root of that coordinate's standard deviation, so coordinates with little signal receive very little noise. Under this scaling the expected squared added noise becomes proportional to $(\\sum_i s_i^t)^2/\\gamma$ rather than the $d\\sum_i (s_i^t)^2/\\gamma$ of L2 clipping, a factor of $d$ smaller when only a few coordinates are informative. On MNIST logistic regression and a one-hidden-layer network, AdaCliP reports higher accuracy than L2 clipping at the same $(\\epsilon,\\delta)$ budgets, with gains from about 0.2 to 1.6 percentage points.","feed_headline":"Per-coordinate clipping cuts noise in private SGD","feed_subtitle":"AdaCliP scales each gradient coordinate by its own variation, saving up to a factor of d in added noise.","key_machinery":"The load-bearing object is the per-coordinate transformation $w^t = (g^t - a^t)/b^t$ with clipping $\\hat{w}^t = w^t/\\max(1,\\|w^t\\|)$ before adding Gaussian noise $N(0,\\sigma^2 I)$. The optimal scale comes from the constrained program $\\min_{a,b}\\sum_i b_i^2$ subject to $\\sum_i (s_i^2 + (m_i-a_i)^2)/b_i^2 \\le \\gamma$; Cauchy's inequality gives equality when $a_i = m_i$ and $b_i^2 = s_i S_t/\\gamma$. Here $\\gamma$ is a parameter bounding the expected squared norm of the transformed gradient, which controls how often clipping occurs. The algorithm estimates the mean $m$ and standard deviation $s$ by exponential moving averages of private noisy gradients, with a debiasing correction that subtracts the known noise variance $(b_i^t)^2\\sigma^2$ from each squared deviation.","core_discovery":"The paper's central claim is that in the family of element-wise linear gradient transformations—subtract a vector, divide coordinate-wise, clip to unit norm, add Gaussian noise, then rescale—the choice that minimizes injected noise is not the usual L2-norm clipping and not classical whitening. Writing $s_i^t$ for the standard deviation of coordinate $i$ of the stochastic gradient at iteration $t$, the optimal shift is $a_i^t = \\mathbb{E}g_i^t$ and the optimal scale is $b_i^t = \\sqrt{s_i^t S_t/\\gamma}$, where $S_t = \\sum_j s_j^t$ and $\\gamma$ bounds the expected squared norm of the transformed gradient. The expected squared added noise then equals $\\sigma^2 S_t^2/\\gamma$, compared with $\\sigma^2 d\\sum_i (s_i^t)^2/\\gamma$ for L2 clipping, so the advantage grows with the number of coordinates that carry no signal. On MNIST, AdaCliP reports accuracy improvements of 0.2 to 1.6 percentage points over L2 clipping at the same $(\\epsilon,\\delta)$ budgets, consistent with the smaller injected noise.","pith_inferences":["A direct consequence the paper leaves implicit: if the per-user noise in Algorithm 1 is not scaled by $1/\\sqrt{B}$ before averaging, the effective noise-to-sensitivity ratio on the batch mean is not the $\\sigma$ used in the moments accountant, so the reported $\\epsilon$ values should be rechecked against the exact per-user algorithm.","The debiased variance estimator subtracts $(b_i^t)^2\\sigma^2$ under the assumption that clipping did not occur, while the analysis assumes clipping happens with constant probability; an unbiased variance estimator robust to clipping would make the theory and implementation consistent.","The same per-coordinate scaling idea could be tested in federated learning settings, where client gradient variances are naturally heterogeneous; one could check whether AdaCliP's advantage over L2 clipping grows with the degree of heterogeneity across clients."],"forward_implications":["At a fixed $(\\epsilon,\\delta)$ budget, AdaCliP's coordinate-adaptive clipping yields lower expected injected noise than L2 norm clipping whenever coordinate standard deviations are unequal, because $(\\sum_i s_i)^2 \\le d\\sum_i s_i^2$.","On sparse-gradient problems such as the paper's regression example, the noise saving is a factor of the dimension $d$, and the optimization error no longer grows with the number of uninformative coordinates.","AdaCliP needs no public data or precomputed Lipschitz bounds; it estimates the per-coordinate mean and standard deviation from the same private noisy gradients used for updates.","The privacy-utility tradeoff in deep models improves consistently on MNIST: with $(\\epsilon,10^{-5})$-differential privacy, accuracy rises by 0.2 to 1.6 percentage points at matched $\\epsilon$ compared with L2 clipping.","The same moments accountant used for standard private SGD applies, so AdaCliP can be inserted into existing private-training pipelines without changing the privacy accounting method."],"supporting_citations":[{"why":"Supplies the baseline private SGD that clips the full gradient norm and provides the moments accountant used for all reported privacy budgets.","marker":"[14]"},{"why":"Source of the Gaussian mechanism and Lemma 1, the link between noise scale $\\sigma$ and the $(\\epsilon,\\delta)$ privacy guarantee.","marker":"[9]"},{"why":"Nonconvex SGD convergence bound adapted as Lemma 2, which motivates minimizing bias and variance of the modified gradients.","marker":"[42]"},{"why":"Earlier private ERM method whose Lipschitz-based sensitivity bound serves as one of the baselines AdaCliP improves on.","marker":"[16]"},{"why":"Coordinate-wise clipping baseline that motivates why per-coordinate thresholds can beat a single global norm threshold.","marker":"[13]"},{"why":"Recent adaptive clipping method for the L2 threshold, which AdaCliP generalizes from one threshold to coordinate-wise thresholds.","marker":"[41]"}],"fun_headline_variants":["AdaCliP: per-coordinate clipping reduces private SGD noise","Adaptive clipping saves up to factor d in private SGD","AdaCliP outperforms L2 clipping for private model accuracy","Coordinate-wise adaptive clipping trims noise in private SGD"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"If adding Gaussian noise to each per-example gradient and then averaging is not the same as adding one Gaussian perturbation to the averaged gradient at the scale the moments accountant assumes, then the reported $\\epsilon$ does not describe the algorithm actually executed.","fun_headline_variants_meta":{"raw":{"variants":["AdaCliP: per-coordinate clipping reduces private SGD noise","Adaptive clipping saves up to factor d in private SGD","AdaCliP outperforms L2 clipping for private model accuracy","Coordinate-wise adaptive clipping trims noise in private SGD"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000899,"raw_usage":{"total_tokens":3838,"prompt_tokens":880,"completion_tokens":2958,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":496,"completion_tokens_details":{"reasoning_tokens":2890}},"tokens_in":496,"tokens_out":2958,"duration_ms":22455,"temperature":1.0,"reasoning_tokens":2890,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:01:43.981846+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 exactly as written and feed its per-step noisy gradients to a moments accountant, comparing the resulting $\\epsilon$ with the values in Tables 1 and 2; a discrepancy would show the per-example-versus-mean noise equivalence fails at the implemented scale. Separately, on the paper's regression example with $d=1000$ and one informative coordinate, measure the empirical average of $\\|b_t\\|^2\\sigma^2$; if the injected noise grows with $d$, the predicted factor-$d$ reduction is absent.","supporting_citations":[{"cited_title":"Deep learning with differential privacy","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline private SGD that clips the full gradient norm and provides the moments accountant used for all reported privacy budgets."},{"cited_title":"The algorithmic foundations of differential privacy.Foun- dations and TrendsR©in Theoretical Computer Science, 9(3–4):211–407, 2014","cited_arxiv_id":null,"evidence_quote":"Source of the Gaussian mechanism and Lemma 1, the link between noise scale $\\sigma$ and the $(\\epsilon,\\delta)$ privacy guarantee."},{"cited_title":"Stochastic variance reduction for nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"Nonconvex SGD convergence bound adapted as Lemma 2, which motivates minimizing bias and variance of the modified gradients."},{"cited_title":"Privacy-preserving deep learning","cited_arxiv_id":null,"evidence_quote":"Coordinate-wise clipping baseline that motivates why per-coordinate thresholds can beat a single global norm threshold."}],"review_version":1}