Pith. sign in

REVIEW 3 major objections 6 minor 104 references

Differentially Private Learning Beyond the Classical Dimensionality Regime

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2411.13682 v2 pith:KNIDWNCN submitted 2024-11-20 cs.LG cs.CRcs.DS

Cynthia Dwork , Pranay Tankala , Linjun Zhang This is my paper · ORCID
classification cs.LGcs.CRcs.DS
keywords differentialprivacyproportionaldimensionalityregimeobjectiveperturbationoutputDP-SGDdoubledescentrobustlinearregressionlogistic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Theorems 3.7(b), 4.2(b); Eqs. (3.8), (4.3)] 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.
  2. [Theorem 2.12 and Lemma 4.10] 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.
  3. [Section 1.1.1, Figure 1] 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.
minor comments (6)
  1. [Theorem 4.2 statement] 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.
  2. [Lemma 3.13 proof] 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.
  3. [Definition 2.2] 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.
  4. [Theorem 5.1 and Corollary 5.2] 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.
  5. [Abstract and Section 1.1.5] 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.
  6. [Figure captions] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the error formulas are derived through CGMT/universality reductions to external fixed-point systems, with self-citations only in background and motivation.

full rationale

The main utility claims are obtained by a genuine derivation chain. The objective-perturbation estimator is rewritten via Legendre transform as a min-max problem (Lemmas 3.11 and 4.11); universality theorems from [HS23, Han24] transfer the analysis from bounded or subgaussian designs to Gaussian designs; and CGMT reduces the Gaussian min-max problem to a scalar fixed-point system, whose solution (sigma*, tau*) or (alpha*, sigma*, gamma*) is then shown to govern the pseudo-Lipschitz limit of the estimator. The systems (3.8) and (4.3) are not fitted: they emerge from first-order optimality conditions of the auxiliary CGMT problem, simplified using Stein's lemma and proximal identities. Their nu=0 limits reduce to the known non-private equations of [TAH18, HS23, SAH19, SC19], which confirms rather than fabricates the connection to prior theory. The output-perturbation corollaries follow from the same saddle-point analysis with an additive Gaussian term, not from fitting a free constant. The DP-SGD section explicitly imports external GFOM/DMFT results [GTM+24, Han24] and is labeled by the authors as a point of reference rather than a main technical contribution. The paper's self-citations ([CWZ21], [CWZ23], [AKT+23]) appear only in background or motivation passages and are not load-bearing for any theorem. Finally, the theorems are conditional on existence of a positive solution to the fixed-point systems without a proof of existence or uniqueness; this is an unproved mathematical gap, not a circular reduction, because the claimed asymptotic value is not defined in terms of the algorithm's own output and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper derives, rather than fits, all formulas. The only assumptions are standard probabilistic tools from prior literature, the average-case data model, and the explicit but unproved existence condition for the fixed-point systems.

assumptions (6)
  • standard math Convex Gaussian Minimax Theorem (CGMT) as stated in Theorem 2.7
    Used to relate the primary min-max problem to a simpler auxiliary problem; central to the utility proofs.
  • standard math CGMT universality, Corollary 2.6 of Han and Shen (2023)
    Used to extend Gaussian-design analysis to subgaussian designs with bounded entries, as required by DP data bounds.
  • standard math GFOM universality, Theorem 3.2 of Han (2024)
    Used for logistic regression and DP-SGD where the objective is not directly in CGMT form.
  • domain assumption Subgaussian design with independent entries, zero mean, variance 1/d (Definition 3.2)
    Defines the average-case data model for the utility guarantees; privacy holds for worst-case data.
  • domain assumption Data bounded in B_R(0), meaning the norm of each x_i is at most R
    Required to apply the privacy analysis; the utility analysis reconciles this with universality.
  • ad hoc to paper Existence of a positive solution (sigma_star, tau_star) and (alpha_star, sigma_star, gamma_star) to the fixed-point systems (3.8) and (4.3)
    Assumed without proof in Theorems 3.7 and 4.2; no uniqueness argument is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Differentially Private Learning Beyond the Classical Dimensionality Regime." pith.science (2026). https://pith.science/paper/KNIDWNCN

@misc{pith2026241113682,
  author       = {Pith},
  title        = {Pith review of: Differentially Private Learning Beyond the Classical Dimensionality Regime},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KNIDWNCN}},
  note         = {Machine review of arXiv:2411.13682}
}
abstract

We initiate the study of differentially private learning in the proportional dimensionality regime, in which the number of data samples $n$ and problem dimension $d$ approach infinity at rates proportional to one another, meaning that $d/n\to\delta$ as $n\to\infty$ for an arbitrary, given constant $\delta\in(0,\infty)$. This setting is significantly more challenging than that of all prior theoretical work in high-dimensional differentially private learning, which, despite the name, has assumed that $\delta = 0$ or is sufficiently small for problems of sample complexity $O(d)$, a regime typically considered "low-dimensional" or "classical" by modern standards in high-dimensional statistics. We provide sharp theoretical estimates of the error of several well-studied differentially private algorithms for robust linear regression and logistic regression, including output perturbation, objective perturbation, and noisy stochastic gradient descent, in the proportional dimensionality regime. The $1+o(1)$ factor precision of our error estimates enables a far more nuanced understanding of the price of privacy of these algorithms than that afforded by existing, coarser analyses, which are essentially vacuous in the regime we consider. Using our estimates, we discover a previously unobserved "double descent"-like phenomenon in the training error of objective perturbation for robust linear regression. We also identify settings in which output perturbation outperforms objective perturbation on average, and vice versa, demonstrating that the relative performance of these algorithms is less clear-cut than suggested by prior work. To prove our main theorems, we introduce several probabilistic tools that have not previously been used to analyze differentially private learning algorithms, such as a modern Gaussian comparison inequality and recent universality laws with origins in statistical physics.

Figures

Figures reproduced from arXiv: 2411.13682 by the authors.

Figure 1
Figure 1. Theorem 1.1’s predictions of the estimation error and truncated residuals of objective perturbation with Huber loss. Larger δ ∈ (0, ∞) corresponds to smaller n/(n + d) ∈ (0, 1). Curves indicate theoretical predictions, and dots indicate the mean over 100 simulations of the algorithm on synthetic data with n × d = 1000. In the left plots, the perturbation magnitude is ν = 0, corresponding to the non-private case, but… view at source ↗
Figure 2
Figure 2. Left: Comparison of error estimates for output perturbation (Corollary [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. The functions HL, H′ L , and H′′ L with L = 1. Assumptions. The main assumption for our utility analysis will be that the matrix X, which we call the design matrix or feature matrix, is subgaussian in the sense defined below. Definition 3.2 (Subgaussian Design). We say a random matrix X ∈ BR(0) n with d = Θ(n) follows a subgaussian design if its entries xij are independent and satisfy the following conditions. (a) F… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The functions ρ, ρ ′ , ρ ′′, and proxγρ with γ = 3. 4 Utility of Objective Perturbation for Logistic Regression In this section, we study the privacy-utility tradeoff for objective perturbation, applied to the prob￾lem of logistic regression. The version of the algorit…
Figure 5
Figure 5. Figure 5: Theorem 4.2’s predictions of the error of Algorithm 1 with logistic loss. Estimation error refers to 1 d ∥βb − β ⋆∥ 2 . Difference of ρ ′ refers to 1 n ∥ρ ′ (Xβ⋆ ) − ρ ′ (Xβb)∥ 2 , which is related to the residual vector y − ρ ′ (Xβb) since y ∼ Bernoulli(ρ ′ (Xβ⋆ )). C…
Figure 6
Figure 6. Figure 6: Predictions of Corollaries 6.1 and 6.3 on the estimation error of Algorithm 2. In all plots, curves correspond to theoretical predictions, and dots correspond to the mean over 100 simulations of the algorithm on synthetic data with n×d = 1000. In the left plots, the pe…
Figure 7
Figure 7. Figure 7: Predictions of Theorems 7.1 and 7.2 on the estimation error of Algorithm 3. In all plots, curves correspond to theoretical predictions, and dots correspond to the mean over 104 simulations of the algorithm on synthetic data with n × d = 1000. In the left plots, the noi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

104 extracted references · 74 canonical work pages

  1. [1]

    Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang

    Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM Conference on Computer and Communications Security (CCS) , 2016

    2016

  2. [2]

    Easy differentially private linear regression

    Kareem Amin, Matthew Joseph, M \' o nica Ribero, and Sergei Vassilvitskii. Easy differentially private linear regression. In International Conference on Learning Representations (ICLR) , 2023

    2023

  3. [3]

    Private mean estimation with person-level differential privacy

    Sushant Agarwal, Gautam Kamath, Mahbod Majid, Argyris Mouzakis, Rose Silver, and Jonathan Ullman. Private mean estimation with person-level differential privacy. In ACM - SIAM Symposium on Discrete Algorithms (SODA) , 2024

    2024

  4. [4]

    Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang

    Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating a gaussian: Efficient, robust, and optimal. In ACM Symposium on Theory of Computing (STOC) , 2023

    2023

  5. [5]

    Private and polynomial time algorithms for learning gaussians and beyond

    Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory (COLT) , 2022

    2022

  6. [6]

    McCoy, and Joel A

    Dennis Amelunxen, Martin Lotz, Michael B. McCoy, and Joel A. Tropp. Living on the edge: phase transitions in convex programs with random data . Information and Inference: A Journal of the IMA , 3(3):224--294, 06 2014

    2014

  7. [7]

    Universality in learning from linear measurements

    Ehsan Abbasi, Fariborz Salehi, and Babak Hassibi. Universality in learning from linear measurements. In Conference on Neural Information Processing Systems (NeurIPS) , 2019

    2019

  8. [8]

    Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation

    Gavin R Brown, Krishnamurthy Dj Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Guha Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation. In International Conference on Machine Learning (ICML) , 2024

    2024

Show all 104 references
  1. [9]

    Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C

    Gavin Brown, Jonathan Hayase, Samuel B. Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, and Adam Smith. Insufficient statistics perturbation: Stable estimators for private least squares. In Conference on Learning Theory (COLT) , 2024

    2024

  2. [10]

    Reconciling modern machine-learning practice and the classical bias–variance trade-off

    Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences , 116(32):15849--15854, 2019

    2019

  3. [11]

    Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions

    Gavin Brown, Samuel Hopkins, and Adam Smith. Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions. In Conference on Learning Theory (COLT) , 2023

    2023

  4. [12]

    Two models of double descent for weak features

    Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science , 2(4):1167--1180, 2020

    2020

  5. [13]

    A leave-one-out approach to approximate message passing, 2023

    Zhigang Bao, Qiyang Han, and Xiaocong Xu. A leave-one-out approach to approximate message passing, 2023

    2023

  6. [14]

    Private hypothesis selection

    Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. In Conference on Neural Information Processing Systems (NeurIPS) , 2019

    2019

  7. [15]

    Universality in polytope phase transitions and message passing algorithms

    Mohsen Bayati, Marc Lelarge, and Andrea Montanari. Universality in polytope phase transitions and message passing algorithms . The Annals of Applied Probability , 25(2):753 -- 822, 2015

    2015

  8. [16]

    The dynamics of message passing on dense graphs, with applications to compressed sensing

    Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory , 57(2):764--785, 2011

    2011

  9. [17]

    The lasso risk for gaussian matrices

    Mohsen Bayati and Andrea Montanari. The lasso risk for gaussian matrices. IEEE Transactions on Information Theory , 58(4):1997--2017, 2011

    1997

  10. [18]

    Concentrated differential privacy: Simplifications, extensions, and lower bounds

    Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography Conference (TCC) , 2016

    2016

  11. [19]

    Smith, and Abhradeep Thakurta

    Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In IEEE Symposium on Foundations of Computer Science (FOCS) , 2014

    2014

  12. [20]

    Convex optimization: Algorithms and complexity

    S \' e bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8(3-4):231--357, 2015

    2015

  13. [21]

    Improving the gaussian mechanism for differential privacy: A nalytical calibration and optimal denoising

    Borja Balle and Yu - Xiang Wang. Improving the gaussian mechanism for differential privacy: A nalytical calibration and optimal denoising. In International Conference on Machine Learning (ICML) , 2018

    2018

  14. [22]

    Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman

    Cl\' e ment L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman. The structure of optimal private tests for simple hypotheses. In ACM Symposium on Theory of Computing (STOC) , 2019

    2019

  15. [23]

    Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research , 12(29):1069--1109, 2011

    2011

  16. [24]

    The estimation error of general first order methods

    Michael Celentano, Andrea Montanari, and Yuchen Wu. The estimation error of general first order methods. In Conference on Learning Theory (COLT) , 2020

    2020

  17. [25]

    The Lasso with general Gaussian designs with applications to hypothesis testing

    Michael Celentano, Andrea Montanari, and Yuting Wei. The Lasso with general Gaussian designs with applications to hypothesis testing . The Annals of Statistics , 51(5):2194 -- 2220, 2023

    2023

  18. [26]

    Cand \`e s and Pragya Sur

    Emmanuel J. Cand \`e s and Pragya Sur. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression . The Annals of Statistics , 48(1):27 -- 42, 2020

    2020

  19. [27]

    Tony Cai, Yichen Wang, and Linjun Zhang

    T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy . The Annals of Statistics , 49(5):2825 -- 2850, 2021

    2021

  20. [28]

    Tony Cai, Yichen Wang, and Linjun Zhang

    T. Tony Cai, Yichen Wang, and Linjun Zhang. Score attack: A lower bound technique for optimal differentially private learning, 2023

    2023

  21. [29]

    Our data, ourselves: Privacy via distributed noise generation

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) , 2006

    2006

  22. [30]

    A model of double descent for high-dimensional binary linear classification

    Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification . Information and Inference: A Journal of the IMA , 11(2):435--495, 04 2021

    2021

  23. [31]

    Differential privacy and robust statistics

    Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In ACM Symposium on Theory of Computing (STOC) , 2009

    2009

  24. [32]

    Oussama Dhifallah and Yue M. Lu. A precise performance analysis of learning with random features, 2020

    2020

  25. [33]

    Lu, and Subhabrata Sen

    Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen. Universality of approximate message passing with semirandom matrices . The Annals of Probability , 51(5):1616 -- 1683, 2023

    2023

  26. [34]

    Message-passing algorithms for compressed sensing

    David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences , 106(45):18914--18919, 2009

    2009

  27. [35]

    The noise-sensitivity phase transition in compressed sensing

    David L Donoho, Arian Maleki, and Andrea Montanari. The noise-sensitivity phase transition in compressed sensing. IEEE Transactions on Information Theory , 57(10):6920--6941, 2011

    2011

  28. [36]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC) , 2006

    2006

  29. [37]

    The algorithmic foundations of differential privacy

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9(3-4):211--407, 2014

    2014

  30. [38]

    Rothblum

    Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy, 2016

    2016

  31. [39]

    Rishabh Dudeja, Subhabrata Sen, and Yue M. Lu. Spectral universality in regularized linear regression with nearly deterministic sensing matrices. IEEE Transactions on Information Theory , 70(11):7923--7951, 2024

    2024

  32. [40]

    Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results, 2013

    Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results, 2013

    2013

  33. [41]

    On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators

    Noureddine El Karoui. On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. Probability Theory and Related Fields , 170(1):95--175, Feb 2018

    2018

  34. [42]

    On robust regression with high-dimensional predictors

    Noureddine El Karoui, Derek Bean, Peter J Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimensional predictors. Proceedings of the National Academy of Sciences , 110(36):14557--14562, 2013

    2013

  35. [43]

    Approximate Message Passing algorithms for rotationally invariant matrices

    Zhou Fan. Approximate Message Passing algorithms for rotationally invariant matrices . The Annals of Statistics , 50(1):197 -- 224, 2022

    2022

  36. [44]

    Kristian Georgiev and Samuel B. Hopkins. Privacy induces robustness: information-computation gaps and sparse mean estimation. In Conference on Neural Information Processing Systems (NeurIPS) , 2024

    2024

  37. [45]

    Locally private hypothesis selection

    Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Conference on Learning Theory (COLT) , 2020

    2020

  38. [46]

    Some inequalities for gaussian processes and applications

    Yehoram Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathematics , 50(4):265--289, Dec 1985

    1985

  39. [47]

    Rigorous dynamical mean-field theory for stochastic gradient descent methods

    C\' e dric Gerbelot, Emanuele Troiani, Francesca Mignacco, Florent Krzakala, and Lenka Zdeborov\' a . Rigorous dynamical mean-field theory for stochastic gradient descent methods. SIAM Journal on Mathematics of Data Science , 6(2):400--427, 2024

    2024

  40. [48]

    Entrywise dynamics and universality of general first order methods, 2024

    Qiyang Han. Entrywise dynamics and universality of general first order methods, 2024

    2024

  41. [49]

    Hopkins, Gautam Kamath, and Mahbod Majid

    Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. In ACM Symposium on Theory of Computing (STOC) , 2022

    2022

  42. [50]

    Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan

    Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. In ACM Symposium on Theory of Computing (STOC) , 2023

    2023

  43. [51]

    Hong Hu and Yue M. Lu. Slope for sparse linear regression: Asymptotics and optimal regularization. IEEE Transactions on Information Theory , 68(11):7627--7664, 2022

    2022

  44. [52]

    Universality of regularized regression estimators in high dimensions

    Qiyang Han and Yandi Shen. Universality of regularized regression estimators in high dimensions. The Annals of Statistics , 51(4):1799 -- 1823, 2023

    2023

  45. [53]

    Peter J. Huber. Robust Estimation of a Location Parameter . The Annals of Mathematical Statistics , 35(1):73 -- 101, 1964

    1964

  46. [54]

    Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang

    Roger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In IEEE Symposium on Security and Privacy , 2019

    2019

  47. [55]

    (near) dimension independent risk bounds for differentially private learning

    Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differentially private learning. In International Conference on Machine Learning (ICML) , 2014

    2014

  48. [56]

    Berrett, and Yi Yu

    Alexander Kent, Thomas B. Berrett, and Yi Yu. Rate optimality and phase transition for user-level local differential privacy, 2024

    2024

  49. [57]

    A pretty fast algorithm for adaptive private mean estimation

    Rohith Kuditipudi, John Duchi, and Saminul Haque. A pretty fast algorithm for adaptive private mean estimation. In Conference on Learning Theory (COLT) , 2023

    2023

  50. [58]

    Privately learning high-dimensional distributions

    Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory (COLT) , 2019

    2019

  51. [59]

    Applications of the lindeberg principle in communications and statistical learning

    Satish Babu Korada and Andrea Montanari. Applications of the lindeberg principle in communications and statistical learning. IEEE Transactions on Information Theory , 57(4):2440--2450, 2011

    2011

  52. [60]

    A private and computationally-efficient estimator for unbounded gaussians

    Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationally-efficient estimator for unbounded gaussians. In Proceedings of Thirty Fifth Conference on Learning Theory (COLT) , 2022

    2022

  53. [61]

    Private robust estimation by stabilizing convex relaxations

    Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Conference on Learning Theory (COLT) , 2022

    2022

  54. [62]

    Private convex empirical risk minimization and high-dimensional regression

    Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory (COLT) , 2012

    2012

  55. [63]

    Private mean estimation of heavy-tailed distributions

    Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory (COLT) , 2020

    2020

  56. [64]

    Learning curves of generic features maps for realistic datasets with a teacher-student model

    Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. Learning curves of generic features maps for realistic datasets with a teacher-student model. In Conference on Neural Information Processing Systems (NeurIPS) , 2021

    2021

  57. [65]

    Kakade, and Sewoong Oh

    Xiyang Liu, Weihao Kong, Sham M. Kakade, and Sewoong Oh. Robust and differentially private mean estimation. In Conference on Neural Information Processing Systems (NeurIPS) , 2021

    2021

  58. [66]

    Differential privacy and robust statistics in high dimensions

    Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory (COLT) , 2022

    2022

  59. [67]

    A precise high-dimensional asymptotic theory for boosting and minimum- _ 1 -norm interpolated classifiers

    Tengyuan Liang and Pragya Sur. A precise high-dimensional asymptotic theory for boosting and minimum- _ 1 -norm interpolated classifiers . The Annals of Statistics , 50(3):1669 -- 1695, 2022

    2022

  60. [68]

    Darakhshan J. Mir. Differential privacy: An exploration of the privacy-utility landscape . PhD thesis, Rutgers University, 2013

    2013

  61. [69]

    R \' e nyi differential privacy

    Ilya Mironov. R \' e nyi differential privacy. In IEEE Computer Security Foundations Symposium (CSF) , 2017

    2017

  62. [70]

    Better locally private sparse estimation given multiple samples per user

    Yuheng Ma, Ke Jia, and Hanfang Yang. Better locally private sparse estimation given multiple samples per user. In International Conference on Machine Learning (ICML) , 2024

    2024

  63. [71]

    The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning

    L \'e o Miolane and Andrea Montanari. The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning . The Annals of Statistics , 49(4):2313 -- 2335, 2021

    2021

  64. [72]

    The generalization error of random features regression: Precise asymptotics and the double descent curve

    Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics , 75(4):667--766, 2022

    2022

  65. [73]

    Universality of the elastic net error

    Andrea Montanari and Phan-Minh Nguyen. Universality of the elastic net error. In 2017 IEEE International Symposium on Information Theory (ISIT) , pages 2338--2342, 2017

    2017

  66. [74]

    The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime, 2023

    Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime, 2023

    2023

  67. [75]

    Private high-dimensional hypothesis testing

    Shyam Narayanan. Private high-dimensional hypothesis testing. In Conference on Learning Theory (COLT) , 2022

    2022

  68. [76]

    Oracle efficient private non-convex optimization

    Seth Neel, Aaron Roth, Giuseppe Vietri, and Zhiwei Steven Wu. Oracle efficient private non-convex optimization. In International Conference on Machine Learning (ICML) , 2020

    2020

  69. [77]

    Universality laws for randomized dimension reduction, with applications

    Samet Oymak and Joel A Tropp. Universality laws for randomized dimension reduction, with applications . Information and Inference: A Journal of the IMA , 7(3):337--446, 11 2017

    2017

  70. [78]

    Pour, Hassan Ashtiani, and Shahab Asoodeh

    Alireza F. Pour, Hassan Ashtiani, and Shahab Asoodeh. Sample-optimal locally private hypothesis selection and the provable benefits of interactivity. In Conference on Learning Theory (COLT) , 2024

    2024

  71. [79]

    Neal Parikh and Stephen P. Boyd. Proximal algorithms. Foundations and Trends in Optimization , 1(3):127--239, 2014

    2014

  72. [80]

    A universal analysis of large-scale regularized least squares solutions

    Ashkan Panahi and Babak Hassibi. A universal analysis of large-scale regularized least squares solutions. In Conference on Neural Information Processing Systems (NeurIPS) , 2017

    2017

  73. [81]

    Improving the privacy and practicality of objective perturbation for differentially private linear learners

    Rachel Redberg, Antti Koskela, and Yu - Xiang Wang. Improving the privacy and practicality of objective perturbation for differentially private linear learners. In Conference on Neural Information Processing Systems (NeurIPS) , 2023

    2023

  74. [82]

    Privately publishable per-instance privacy

    Rachel Redberg and Yu - Xiang Wang. Privately publishable per-instance privacy. In Conference on Neural Information Processing Systems (NeurIPS) , 2021

    2021

  75. [83]

    The impact of regularization on high-dimensional logistic regression

    Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high-dimensional logistic regression. In Conference on Neural Information Processing Systems (NeurIPS) , 2019

    2019

  76. [84]

    Pragya Sur and Emmanuel J. Candès. A modern maximum-likelihood theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences , 116(29):14516--14525, 2019

    2019

  77. [85]

    Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In IEEE Global Conference on Signal and Information Processing (GlobalSIP) , 2013

    2013

  78. [86]

    Differentially private ordinary least squares

    Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning ( ICML ) , 2017

    2017

  79. [87]

    Old techniques in differentially private linear regression

    Or Sheffet. Old techniques in differentially private linear regression. In International Conference on Algorithmic Learning Theory , 2019

    2019

  80. [88]

    On general minimax theorems

    Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics , 8(1):171 -- 176, 1958

    1958

  81. [89]

    The one-sided barrier problem for gaussian noise

    David Slepian. The one-sided barrier problem for gaussian noise. The Bell System Technical Journal , 41(2):463--501, 1962

    1962

  82. [90]

    A framework to characterize performance of lasso algorithms, 2013

    Mihailo Stojnic. A framework to characterize performance of lasso algorithms, 2013

    2013

  83. [91]

    Thomas Steinke and Jonathan R. Ullman. Tight lower bounds for differentially private selection. In IEEE Symposium on Foundations of Computer Science (FOCS) , 2017

    2017

  84. [92]

    Precise error analysis of regularized m-estimators in high dimensions

    Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory , 64(8):5592--5628, 2018

    2018

  85. [93]

    Regularized linear regression: A precise analysis of the estimation error

    Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory (COLT) , 2015

    2015

  86. [94]

    Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography , pages 347--450. Springer International Publishing, 2017

    2017

  87. [95]

    High-Dimensional Probability: An Introduction with Applications in Data Science

    Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018

    2018

  88. [96]

    (nearly) optimal private linear regression for sub-gaussian data via adaptive clipping

    Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression for sub-gaussian data via adaptive clipping. In Conference on Learning Theory (COLT) , 2022

    2022

  89. [97]

    Wainwright

    Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019

    2019

  90. [98]

    Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain

    Yu - Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI) , 2018

    2018

  91. [99]

    Privacy for free: Posterior sampling and stochastic gradient monte carlo

    Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning (ICML) , 2015

    2015

  92. [100]

    Does SLOPE outperform bridge regression? Information and Inference: A Journal of the IMA , 11(1):1--54, 11 2021

    Shuaiwen Wang, Haolei Weng, and Arian Maleki. Does SLOPE outperform bridge regression? Information and Inference: A Journal of the IMA , 11(1):1--54, 11 2021

    2021

  93. [101]

    Universality of approximate message passing algorithms and tensor networks

    Tianhao Wang, Xinyi Zhong, and Zhou Fan. Universality of approximate message passing algorithms and tensor networks. The Annals of Applied Probability , 34(4):3943--3994, 2024

    2024

  94. [102]

    Cand \`e s

    Qian Zhao, Pragya Sur, and Emmanuel J. Cand \`e s. The asymptotic distribution of the MLE in high-dimensional logistic models: Arbitrary covariance . Bernoulli , 28(3):1835 -- 1861, 2022

    2022

  95. [103]

    Hubert Chan, Giulia Fanti, and Elaine Shi

    Mingxun Zhou, Tianhao Wang, T-H. Hubert Chan, Giulia Fanti, and Elaine Shi. Locally differentially private sparse vector aggregation. In IEEE Symposium on Security and Privacy , 2022

    2022

  96. [104]

    A modern theory for high-dimensional cox regression models, 2022

    Xianyang Zhang, Huijuan Zhou, and Hanxuan Ye. A modern theory for high-dimensional cox regression models, 2022

    2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.