93 citations · 578 across the 83 of their papers we have counts for
6 papers · 2 filters
A Unified View of Graph Regularity via Matrix Decompositions
Greg Bodwin, Santosh Vempala
We prove algorithmic weak and \Szemeredi{} regularity lemmas for several classes of sparse graphs in the literature, for which only weak regularity lemmas were previously known. Th…
Robustly Clustering a Mixture of Gaussians
He Jia, Santosh Vempala
We give an efficient algorithm for robustly clustering of a mixture of two arbitrary Gaussians, a central open problem in the theory of computationally efficient robust estimation,…
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, Santosh Vempala
Motivated by the Dikin walk, we develop aspects of an interior-point theory for sampling in high dimension. Specifically, we introduce a symmetric parameter and the notion of stron…
The Communication Complexity of Optimization
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator toge…
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Zongchen Chen, Santosh S. Vempala
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to where is -strongly convex and …
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
Santosh S. Vempala, Andre Wibisono
We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution on . We prove a convergence guarantee in Kullback-Leibler (K…