5 papers · 1 filter
Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
Anming Gu, Syamantak Kumar, Kevin Tian +1
Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream. We give a new analysis of the ubiquitous Oja's algori…
High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression
Syamantak Kumar, Purnamrita Sarkar, Kevin Tian +1
Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice $\mathcal{X}_k^…
Revisiting the Provable-Auditable Privacy Gap of DP-SGD
Saloni Modi, Srivi Balaji, Yusong Zhu +2
Differential privacy (DP) has traditionally been used to provide theoretical upper bounds on an algorithm's stability to changing its training data. In modern private machine learn…
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar +1
We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under -row-column sparsity (-RCS) of…
Combinatorial Sparse PCA Beyond the Spiked Identity Model
Syamantak Kumar, Purnamrita Sarkar, Kevin Tian +1
Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance , whose top eigenve…