8 papers
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…
Private Geometric Median in Nearly-Linear Time
Syamantak Kumar, Daogao Liu, Kevin Tian +1
Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry. Recently, [HSU24] gave an $(\vareps…
Spike-and-Slab Posterior Sampling in High Dimensions
Syamantak Kumar, Purnamrita Sarkar, Kevin Tian +1
Posterior sampling with the spike-and-slab prior [MB88], a popular multimodal distribution used to model uncertainty in variable selection, is considered the theoretical gold stand…
Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
Hilal Asi, Daogao Liu, Kevin Tian
We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a -moment bound on the Lipschitz…