93 citations · 578 across the 83 of their papers we have counts for
44 papers · 1 filter
Faster logconcave sampling from a cold start in high dimension
Yunbum Kook, Santosh S. Vempala
We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algor…
Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
Yunbum Kook, Santosh S. Vempala
We study the complexity of sampling, rounding, and integrating arbitrary logconcave functions. Our new approach provides the first complexity improvements in nearly two decades for…
In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Yunbum Kook, Santosh S. Vempala, Matthew S. Zhang
We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than prev…
Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
Yunbum Kook, Santosh S. Vempala
The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For inst…
Sampling with Barriers: Faster Mixing via Lewis Weights
Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by inequalities in endowed with the metric defined by the Hessian of a convex barrie…
The Bit Complexity of Efficient Continuous Optimization
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
We analyze the bit complexity of efficient algorithms for fundamental optimization problems, such as linear regression, -norm regression, and linear programming (LP). State-of-t…
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
He Jia, Pravesh K . Kothari, Santosh S. Vempala
We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for inde…
Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators
Yunbum Kook, Yin Tat Lee, Ruoqi Shen +1
We study the convergence rate of discretized Riemannian Hamiltonian Monte Carlo on sampling from distributions in the form of on a convex body $\mathcal{M}\subset\mathb…
Constant-Factor Approximation Algorithms for Socially Fair -Clustering
Mehrdad Ghadiri, Mohit Singh, Santosh S. Vempala
We study approximation algorithms for the socially fair -clustering problem with groups, whose special cases include the socially fair -median () and socia…
A Unified Approach to Discrepancy Minimization
Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various…
The Mirror Langevin Algorithm Converges with Vanishing Bias
Ruilin Li, Molei Tao, Santosh S. Vempala +1
The technique of modifying the geometry of a problem from Euclidean to Hessian metric has proved to be quite effective in optimization, and has been the subject of study for sampli…
Faster -Norm Regression Using Sparsity
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
For a matrix with , we consider the dual problems of and $\min_{A^\top x=b} \|x\|_p^p,\, b\in \math…
Tutorial on the Robust Interior Point Method
Yin Tat Lee, Santosh S. Vempala
We give a short, self-contained proof of the interior point method and its robust version.
Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast
Aditi Laddha, Santosh Vempala
The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to Turchin, 1971. In each step of the Gibbs Sampler, we pick a random coordinate and…
Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
He Jia, Aditi Laddha, Yin Tat Lee +1
We show that the volume of a convex body in in the general membership oracle model can be computed to within relative error using $\widetilde{O}(n^{3…
Solving Sparse Linear Systems Faster than Matrix Multiplication
Richard Peng, Santosh Vempala
Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general se…
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…
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
Yin Tat Lee, Zhao Song, Santosh S. Vempala
Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamil…
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
Nima Anari, Constantinos Daskalakis, Wolfgang Maass +3
We analyze linear independence of rank one tensors produced by tensor powers of randomly perturbed vectors. This enables efficient decomposition of sums of high-order tensors. Our…