Reproduce “Privately Learning Subspaces” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Vikrant Singhal, Thomas Steinke
Singhal and Steinke introduce differentially private methods for learning low-dimensional linear subspaces from high-dimensional data, achieving sample complexities that are independent of the ambient dimension. Their algorithms, designed for both exact and approximate subspace recovery, leverage (", ")-differential privacy to circumvent the curse of dimensionality common in previous approaches.
Key insights
- (", ")-differential privacy provides sufficient flexibility to design mechanisms that avoid the "curse of dimensionality" in subspace learning, unlike stronger privacy notions that are prone to packing lower bounds.
- By defining a low-sensitivity score function, the GAP-MAX algorithm can be effectively applied to privately identify the exact underlying subspace with high probability and optimal sample complexity.
- A "subsample and aggregate" approach combined with private histograms over projections of public reference points allows for robust and dimension-independent approximation of a low-rank subspace from noisy, high-dimensional data.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.