{"id":"8e9d1336-3a11-456f-a209-0d566b1cad7a","arxiv_id":"2411.13682","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First sharp asymptotic characterization of differentially private objective perturbation, output perturbation, and DP-SGD in the proportional dimensionality regime, including a privacy-induced double-descent phenomenon.","lead":"This paper derives exact error rates for differentially private regression algorithms when data dimension grows proportionally to sample size, a regime where prior bounds were vacuous. It reveals a privacy-induced double-descent spike and shows that the best algorithm depends on the dimension-to-sample ratio.","discovery_kind":"new_application","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"This paper initiates the study of differentially private learning in the proportional-dimensionality regime where d/n converges to a positive constant δ. For objective perturbation (Algorithm 1), output perturbation (Algorithm 2), and a conditional-expectation version of noisy gradient descent (Algorithm 3), it derives sharp asymptotic characterizations of estimation and prediction errors through low-dimensional fixed-point systems: Eq. (3.8) for Huber regression, Eq. (4.3) for logistic regression, Eqs. (6.2)/(6.4) for output perturbation, and the O(T^2) recursions in Section 7. The proofs combine Legendre transforms, the CGMT, universality results from Han--Shen and Han, and a refined privacy analysis of objective perturbation valid for all positive λ and ν. Numerical simulations are reported for each algorithm and match the formulas. The ν=0 limit recovers known non-private fixed-point equations.","tokens_in":65513,"tokens_out":12182,"duration_ms":123284,"significance":"If the results are fully established, this is a substantial contribution: previous DP analyses of regression are essentially vacuous in the proportional regime, and this paper provides 1+o(1)-factor error estimates that reveal qualitative phenomena such as the privacy-dependent double-descent-like spike in training error and the regime-dependent comparison between objective and output perturbation. Strengths of the manuscript include the parameter-free nature of the derived equations, the sanity check that they reduce to known non-private systems when ν=0, extensive simulation validation, and the new Section 5 privacy analysis extending [RKW23] to arbitrary λ>0. The main theorems are, however, conditional on existence of positive fixed points, and one of the headline claims is obtained in a limiting regime outside the theorem statements; these issues need to be addressed before the claims can be accepted as stated.","major_comments":[{"comment":"The theorems are stated conditionally on the existence of a positive solution (σ*,τ*) or (α*,σ*,γ*) to the fixed-point systems, but no existence or uniqueness result is supplied. If the system has no solution for some parameter values, the theorem is vacuous for those values; if it has multiple solutions, the claim 'let (σ*,τ*) denote the solution' is ambiguous. The ambiguity is visible in the manuscript itself: Theorem 4.2 omits 'unique' while Corollary 6.3 for the same system in the output-perturbation setting explicitly says 'Suppose there are unique σ*,α*,γ*>0'. Numerical validation of the equations is not a substitute for an analytic existence result. Because every utility formula and the comparative conclusions in Section 1.1.4 are expressed through these solutions, this gap is load-bearing. The authors should add a lemma establishing existence and uniqueness on the parameter ranges for which the theorems are claimed, or explicitly restrict the theorems to such ranges.","section":"Theorems 3.7(b), 4.2(b); Eqs. (3.8), (4.3)"},{"comment":"The GFOM universality theorem is stated as a modification of [Han24, Thm 3.2] to vector-valued iterates and per-coordinate test functions, with the assertion that the changes require only 'minimal, syntactic changes in the proof'. No proof of the modified statement is given. This is not merely cosmetic: the modified theorem is used directly in Lemma 4.10, which is the bridge that makes Theorem 4.2(b) hold for non-Gaussian subgaussian designs, and it is also used in Section 7. The authors should either provide a full proof of the adaptation or quote the exact theorem from the source. As written, this is a load-bearing missing proof for the logistic-regression results.","section":"Theorem 2.12 and Lemma 4.10"},{"comment":"The privacy-induced double-descent claim in the training error is derived by taking L→∞ and λ→0 in the fixed-point equations after Theorem 3.7, but Theorem 3.7 is only stated and proved for fixed positive L, λ, ν. No uniform or continuity argument is given to justify interchanging the limit with the asymptotics. Moreover, the zCDP guarantee in Corollary 5.2 has ρ_DP = log(1+s/λ)+L^2/(2ν^2)+O(L/ν), which diverges as λ→0; hence the comparison in Figure 1 at λ=10^{-5} is not at a fixed privacy level. The paper should either prove the limiting statement rigorously or explicitly label the spike as a heuristic prediction from the fixed-point equations, and clarify what privacy level, if any, is being held fixed when the phenomenon occurs.","section":"Section 1.1.1, Figure 1"}],"minor_comments":[{"comment":"The sentence 'The estimation error bβ−β* satisfies ... (β*,ξ,bβ) 99K ...' mixes bβ−β* with bβ: the third coordinate of the displayed convergence is an approximation of bβ, not of bβ−β*. Please align the statement with the proof and with the subsequent computation of the mean squared error.","section":"Theorem 4.2 statement"},{"comment":"In the proof of Lemma 3.13, the choice g=n^{-1/21} is said to give a threshold shift τ ± O(n^{20/21}), whereas Lemma 3.13 states τ+n^{1−Ω(1)}. The scaling by 1/n and the roles of g and ω in Theorem 2.8 should be spelled out so that the stated n^{1−Ω(1)} gap is actually obtained.","section":"Lemma 3.13 proof"},{"comment":"The Rényi divergence formula is written with a misplaced logarithm: the displayed expression should be (α−1)^{-1} log E_Q[(P/Q)^α], or equivalently (α−1)^{-1} log E_P[(P/Q)^{α−1}], not the version with 'log' inside the expectation as currently printed.","section":"Definition 2.2"},{"comment":"Theorem 5.1 contains a duplicated phrase 'any strictly positive λ,ν>0' twice in one sentence, and the proof of Corollary 5.2 asserts without derivation that log(2Φ((L/ν)(α−1)))/(α−1) strictly decreases from sqrt(2/π)L/ν to 0; this monotonicity should be proved or cited.","section":"Theorem 5.1 and Corollary 5.2"},{"comment":"The abstract says the paper determines the error of 'noisy stochastic gradient descent' without qualification, but Section 7 applies only to T=O(1) iterations and to nonstandard conditional-expectation versions of the losses. This caveat should appear in the abstract or the DP-SGD claims should be reworded so as not to overstate the scope.","section":"Abstract and Section 1.1.5"},{"comment":"The caption notation 'n × d = 1000' presumably means n·d=1000, but as written it reads as the Cartesian product of two dimensions. Please clarify the intended relationship between n and d in the simulations.","section":"Figure captions"}],"recommendation":"major_revision","confidential_remarks":"The absent existence/uniqueness proof for the fixed-point systems was also identified in the reader's report, and I agree that it is the main obstruction. The GFOM universality adaptation is a second load-bearing point that needs a proof. The double-descent claim is currently stated in a regime where the privacy parameter diverges, so it should be reframed or proved. These issues are fixable within the manuscript's scope; if addressed, this would be a strong paper for a theory-oriented ML or statistics journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper is the first to get 1+o(1)-precision error formulas for differentially private regression in the d/n -> delta regime, and as far as I can tell the main results are right. The reduction to the known non-private equations when nu=0 is a strong sanity check, and the simulations line up with the formulas. The special-case proof via completing the square is genuinely elegant: it turns objective perturbation into ridge regression with a shifted ground truth, which makes the privacy noise costs transparent.\n\nWhat's genuinely new: the proportional regime, the sharp constants, the use of CGMT and both universality laws on private algorithms, and the privacy-induced double-descent spike in training error. The spike is a real phenomenon in the limiting equations, not something they fitted. They also fix the RKW23 privacy analysis so it works for arbitrarily small lambda, which was a known gap.\n\nThe soft spots are real but manageable. Theorems 3.7 and 4.2 are stated conditionally on existence and uniqueness of the fixed-point systems, and the paper never proves either. If the system has multiple solutions, the asymptotic characterization is ambiguous; if it has none in some regime, the theorem is vacuous there. The numerics probe a few parameter settings, but the phase transition at delta=1, where the formulas blow up, is exactly where existence questions become delicate. This is the clearest gap and the one I'd ask a referee to push on. The paper also doesn't ship code, and the simulation details are terse, so reproducing the plots takes real effort. The DP-SGD section is explicitly a reference point rather than a main contribution, and it comes with heavy caveats: non-standard \"conditional expectation\" losses, constant T, and an O(T^2) system. That's fine, but it should not be sold as more than it is.\n\nWho this is for: anyone working on private high-dimensional estimation, and people using CGMT/universality who want to see those tools pushed into privacy settings. The fixed-point issue is load-bearing, but it is the kind of gap that can often be closed or at least carefully discussed without changing the core message. This deserves a serious referee. I'd send it out.","headline":"First sharp asymptotics for DP regression in the proportional regime; the main claims look right, but the fixed-point existence/uniqueness gap is the one load-bearing soft spot.","tokens_in":65948,"tokens_out":1755,"would_cite":true,"duration_ms":51399,"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":"In the proportional d/n regime, private regression error is fixed by small scalar systems, and privacy noise itself creates a double-descent spike in training error.","keywords":["differential privacy","proportional dimensionality regime","objective perturbation","output perturbation","DP-SGD","double descent","robust linear regression","logistic regression"],"falsifier":"Fix ν>0, small λ and large L, run objective perturbation with Huber loss at d/n=0.9, 1.0, and 1.1 with n large; the paper predicts truncated training error scaling like 1/|δ−1| near δ=1 only when ν>0. A simulation showing no spike with ν>0, or showing the same spike with ν=0, would contradict Theorem 3.7's residual characterization.","tokens_in":65346,"feed_emoji":"📉","tokens_out":7038,"duration_ms":72560,"temperature":0.7,"pith_summary":"This paper studies differentially private regression in the proportional dimensionality regime, where sample size n and dimension d grow together with d/n→δ, and derives exact asymptotic error formulas, correct up to a 1±n^−Ω(1) factor, for objective perturbation, output perturbation, and noisy SGD on robust linear and logistic regression. Prior private-learning theory only covered the classical δ→0 regime and gives vacuous guarantees here; the paper shows that in the proportional regime the error is not a vanishing rate but a constant determined by a small fixed-point system that includes the algorithm's privacy noise. The sharp formulas reveal a previously unseen phenomenon: for Huber objective perturbation, privacy noise creates a double-descent-like spike in training error near d=n that is absent without privacy. The same formulas show that neither objective nor output perturbation dominates the other across all dimensionality ratios, overturning the simpler ranking suggested by earlier analyses.","feed_headline":"Privacy triggers a double-descent spike in training error","feed_subtitle":"Sharp fixed-point equations for private regression show that noise, however small, moves the error spike.","key_machinery":"The load-bearing machinery is the reduction of the private empirical-risk minimizer to a convex-concave saddle-point problem: the Legendre transform of the loss (Huber or logistic) isolates the design matrix in a bilinear term ⟨Xu,v⟩ plus a mean function that absorbs the ground truth, the residual noise, and the privacy perturbation. The Convex Gaussian Minimax Theorem (CGMT)—a Gaussian comparison inequality that replaces the random design matrix by two independent Gaussian vectors—then turns the saddle point into scalar first-order conditions, and two moment-matching universality laws (one for CGMT-type objectives, one for generalized first-order methods) extend the conclusion from Gaussian to subgaussian, bounded designs. The final output is the fixed-point system for (σ,τ) or (α,σ,γ), whose solution encodes estimation error, ℓp distances, correlations, and residual norms of the private estimator.","core_discovery":"The central claim is that in the limit n→∞ with d/n→δ, the normalized estimation error of objective perturbation with Huber loss satisfies (1/d)∥β̂−β*∥²=(σ*)²±n^−Ω(1), where (σ*,τ*) is the positive solution of the two scalar equations σ²=τ²((1/δ)E[((σZ+ε₀*)/(1+τ))_L]²+λ²κ²+ν²) and τ=(1/(λδ))(δ−(τ/(1+τ))Pr(|(σZ+ε₀*)/(1+τ)|<L)), with Z standard normal, κ²=E(β₀*)², ε₀* the limiting regression noise variable, and [·]_L the Huber truncation. Analogous three-equation systems characterize logistic regression, and simple modifications of the same systems give output perturbation and DP-SGD. As corollaries, the paper derives the exact limiting truncated residual error, showing a 1/|δ−1| singularity at d=n only when the privacy perturbation ν>0, and shows that output perturbation can beat objective perturbation for some dimensionality ratios and vice versa.","pith_inferences":["Because the fixed-point systems are stated for any fixed L, λ, ν, they can be used as a numerical phase diagram; a natural testable extension is to other Lipschitz GLM losses, such as quantile or tilted losses, which should yield the same two- or three-equation structure with the loss-specific truncation or proximal operator.","The training-error spike at δ=1 suggests privacy noise changes the interpolation boundary: in the overparameterized region the private estimator no longer interpolates the training labels, so the residual error peaks sharply near n=d, an implicit prediction about where private models are least stable.","An important open question is whether the fixed-point systems always have a unique positive solution; the theorems are conditional on existence, so resolving this determines how universally the formulas apply across the full parameter range."],"forward_implications":["The error of objective perturbation, output perturbation, and DP-SGD in the proportional regime is pinned down by the displayed fixed-point systems, so previous sample-complexity bounds that only give constant error no better than the trivial estimator are superseded by constant-to-constant comparisons.","For robust linear regression with fixed ν>0, the truncated training error of objective perturbation diverges like 1/|δ−1| as d/n→1, whereas with ν=0 the residual error has no such spike—a privacy-induced analogue of double descent.","The relative performance of objective versus output perturbation depends on δ; for many privacy levels neither error curve lies below the other, so the earlier claim that objective perturbation is uniformly better does not hold.","In the δ>1, small-λ, large-L limit, any fixed privacy noise ν>0 forces the estimation error to diverge, while the non-private estimator stays finite—a dramatic privacy cost in the underdetermined regime.","For logistic regression, taking ν→0 and λ→0 recovers the known non-private MLE theory, including the existence phase transition, showing that the private equations are the correct high-dimensional analogue."],"supporting_citations":[{"why":"Supplies the CGMT universality law (Corollary 2.6) that extends sharp Gaussian analyses to the subgaussian, bounded designs required for privacy.","marker":"[HS23]"},{"why":"Supplies GFOM universality (Theorem 3.2) used for logistic regression and DP-SGD, where CGMT universality does not apply directly.","marker":"[Han24]"},{"why":"The Convex Gaussian Minimax Theorem that replaces the Gaussian design matrix by two Gaussian vectors, reducing the saddle point to scalar calculus.","marker":"[Sto13, TOH15]"},{"why":"Establishes the non-private ridge and Huber asymptotics whose ν=0 limit the paper recovers and extends.","marker":"[TAH18]"},{"why":"Provides the six-equation system for regularized logistic regression on which the paper's heuristic derivation and three-equation private system are based.","marker":"[SAH19]"},{"why":"The landmark non-private logistic MLE theory, including the phase transition, recovered in the ν→0, λ→0 limit.","marker":"[SC19]"},{"why":"The objective perturbation privacy analysis that Section 5 refines to allow arbitrarily small λ and ν.","marker":"[RKW23]"},{"why":"The analytic Gaussian mechanism used for the output perturbation privacy guarantee.","marker":"[BW18]"},{"why":"The rigorous dynamical mean-field results for SGD used as a black box for the DP-SGD section.","marker":"[GTM+24]"}],"fun_headline_variants":["Privacy noise creates the double-descent spike","Private regression error spikes sharply at d=n","Tiny privacy perturbation moves the error peak","Sharp error laws for private regression show noise-induced spike","Exact private errors reveal a singularity only with privacy noise"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The formulas for the error are proven only under the assumption that a certain two- or three-equation system has a positive solution, and the paper does not prove that this solution exists or is unique.","fun_headline_variants_meta":{"raw":{"variants":["Privacy noise creates the double-descent spike","Private regression error spikes sharply at d=n","Tiny privacy perturbation moves the error peak","Sharp error laws for private regression show noise-induced spike","Exact private errors reveal a singularity only with privacy noise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000299,"raw_usage":{"total_tokens":1803,"prompt_tokens":1094,"completion_tokens":709,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":710,"completion_tokens_details":{"reasoning_tokens":638}},"tokens_in":710,"tokens_out":709,"duration_ms":8182,"temperature":1.0,"reasoning_tokens":638,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:00:19.487013+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix ν>0, small λ and large L, run objective perturbation with Huber loss at d/n=0.9, 1.0, and 1.1 with n large; the paper predicts truncated training error scaling like 1/|δ−1| near δ=1 only when ν>0. A simulation showing no spike with ν>0, or showing the same spike with ν=0, would contradict Theorem 3.7's residual characterization.","supporting_citations":[],"review_version":1}