1 citations · 1 across the 10 of their papers we have counts for
13 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^…
Walk fast but be careful: Understanding Parallel Sampling in Masked Diffusion
Vansh Bansal, Cho Cholyeon, Cholyeon Cho +3
In this paper, we use random walks on graphs as a verifiable sandbox for studying parallel sampling strategies in masked diffusion models (MDMs). We train an MDM on random walk sam…
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…
Low-Precision Streaming PCA
Sanjoy Dasgupta, Syamantak Kumar, Shourya Pandey +1
Low-precision streaming PCA estimates the top principal component in a streaming setting under limited precision. We establish an information-theoretic lower bound on the quantizat…
Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA
Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar
We propose a novel statistical inference framework for streaming principal component analysis (PCA) using Oja's algorithm, enabling the construction of confidence intervals for ind…
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…
Dimension-free Score Matching and Time Bootstrapping for Diffusion Models
Syamantak Kumar, Dheeraj Nagaraj, Purnamrita Sarkar
Diffusion models generate samples by estimating the score function of the target distribution at various noise levels. The model is trained using samples drawn from the target dist…
Black-Box -to--PCA Reductions: Theory and Applications
Arun Jambulapati, Syamantak Kumar, Jerry Li +3
The -principal component analysis (-PCA) problem is a fundamental algorithmic primitive that is widely-used in data analysis and dimensionality reduction applications. In sta…
Oja's Algorithm for Streaming Sparse PCA
Syamantak Kumar, Purnamrita Sarkar
Oja's algorithm for Streaming Principal Component Analysis (PCA) for data-points in a dimensional space achieves the same sin-squared error as the o…
Nonparametric Evaluation of Noisy ICA Solutions
Syamantak Kumar, Purnamrita Sarkar, Peter Bickel +1
Independent Component Analysis (ICA) was introduced in the 1980's as a model for Blind Source Separation (BSS), which refers to the process of recovering the sources underlying a m…