On Differentially Private Subspace Estimation in a Distribution-Free Setting
Not on the map. Why?
Abstract (arXiv)
Private data analysis faces a significant challenge known as the curse of dimensionality, leading to increased costs. However, many datasets possess an inherent low-dimensional structure. For instance, during optimization via gradient descent, the gradients frequently reside near a low-dimensional subspace. If the low-dimensional structure could be privately identified using a small amount of points, we could avoid paying for the high ambient dimension. On the negative side, Dwork, Talwar, Thakurta, and Zhang (STOC 2014) proved that privately estimating subspaces, in general, requires an amount of points that has a polynomial dependency on the dimension. However, their bounds do not rule out the possibility to reduce the number of points for "easy" instances. Yet, providing a measure that captures how much a given dataset is "easy" for this task turns out to be challenging, and was not properly addressed in prior works. Inspired by the work of Singhal and Steinke (NeurIPS 2021), we provide the first measures that quantify "easiness" as a function of multiplicative singular-value gaps in the input dataset, and support them with new upper and lower bounds. In particular, our results determine the first types of gaps that are sufficient and necessary for estimating a subspace with an amount of points that is independent of the dimension. Furthermore, we realize our upper bounds using a practical algorithm and demonstrate its advantage in high-dimensional regimes compared to prior approaches.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 23 of its 52 references that are in the map. First posted on arXiv 9 Feb 2024.
Builds on
23 of 52 references.
References · 23
- 2016Deep Learning with Differential Privacycited by 2,682
- 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
- 2018Measuring the Intrinsic Dimension of Objective Landscapescited by 364
- 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
- 2018Gradient Descent Happens in a Tiny Subspacecited by 208
- 2017Finite Sample Differentially Private Confidence Intervalscited by 103
- 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 88
- 2021Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learningcited by 86
- 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
- 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
- 2022Mixed Differential Privacy in Computer Visioncited by 53
- 2022When Does Differentially Private Learning Not Suffer in High Dimensions?cited by 48
11 more
- 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
- 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2019Hessian based analysis of SGD for Deep Nets: Dynamics and Generalizationcited by 37
- 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
- 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
- 2021Privately Learning Subspacescited by 16
- 2020Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspacescited by 10
- 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
- 2020How neural networks find generalizable solutions: Self-tuned annealing in deep learningcited by 5
- 2017Subgaussian Tail Bounds via Stability Argumentscited by 1
Built on by
Citing papers per year: 2025: 1.
1 paper.