research
∙
07/24/2023
Efficiently Sampling the PSD Cone with the Metric Dikin Walk
Semi-definite programs represent a frontier of efficient computation. Wh...
share
research
∙
06/06/2023
Computation with Sequences in the Brain
Even as machine learning exceeds human-level performance on many applica...
research
∙
04/04/2023
The Bit Complexity of Efficient Continuous Optimization
We analyze the bit complexity of efficient algorithms for fundamental op...
research
∙
03/01/2023
Sampling with Barriers: Faster Mixing via Lewis Weights
We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a poly...
research
∙
03/01/2023
Is Planted Coloring Easier than Planted Clique?
We study the computational complexity of two related problems: recoverin...
research
∙
02/23/2023
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
We present a polynomial-time algorithm for robustly learning an unknown ...
research
∙
10/13/2022
Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators
We study the convergence rate of discretized Riemannian Hamiltonian Mont...
research
∙
08/24/2022
A Slightly Improved Bound for the KLS Constant
We refine the recent breakthrough technique of Klartag and Lehec to obta...
research
∙
06/22/2022
Constant-Factor Approximation Algorithms for Socially Fair k-Clustering
We study approximation algorithms for the socially fair (ℓ_p, k)-cluster...
research
∙
05/02/2022
A Unified Approach to Discrepancy Minimization
We study a unified approach and algorithm for constructive discrepancy m...
research
∙
04/22/2022
Convergence of the Riemannian Langevin Algorithm
We study the Riemannian Langevin Algorithm for the problem of sampling f...
research
∙
03/23/2022
The k-Cap Process on Geometric Random Graphs
The k-cap (or k-winners-take-all) process on a graph works as follows: i...
research
∙
02/03/2022
Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space
We demonstrate for the first time that ill-conditioned, non-smooth, cons...
research
∙
11/17/2021
How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization
The success of gradient descent in ML and especially for learning neural...
research
∙
10/27/2021
Provable Lifelong Learning of Representations
In lifelong learning, the tasks (or classes) to be learned arrive sequen...
research
∙
10/07/2021
Assemblies of neurons can learn to classify well-separated distributions
Assemblies are patterns of coordinated firing across large populations o...
research
∙
09/24/2021
The Mirror Langevin Algorithm Converges with Vanishing Bias
The technique of modifying the geometry of a problem from Euclidean to H...
research
∙
09/23/2021
Sparse Regression Faster than d^ω
The current complexity of regression is nearly linear in the complexity ...
research
∙
08/10/2021
Tutorial on the Robust Interior Point Method
We give a short, self-contained proof of the interior point method and i...
research
∙
12/03/2020
Robustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomial-time algorithm for the problem of robustly estimati...
research
∙
08/05/2020
Reducing Isotropy and Volume to KLS: An O(n^3ψ^2) Volume Algorithm
We show that the the volume of a convex body in ℝ^n in the general membe...
research
∙
06/13/2019
The Communication Complexity of Optimization
We consider the communication complexity of a number of distributed opti...
research
∙
05/07/2019
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logc...
research
∙
03/20/2019
Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices
We prove a convergence guarantee on the unadjusted Langevin algorithm fo...
research
∙
12/15/2018
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
Sampling logconcave functions arising in statistics and machine learning...
research
∙
07/10/2018
The Kannan-Lovász-Simonovits Conjecture
The Kannan-Lovász-Simonovits conjecture says that the Cheeger constant o...
research
∙
02/10/2018
Approximating Sparse Graphs: The Random Overlapping Communities Model
How can we approximate sparse graphs and sequences of sparse graphs (wit...
research
∙
10/17/2017
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
We give the first rigorous proof of the convergence of Riemannian Hamilt...
research
∙
06/22/2017
Efficient Convex Optimization with Membership Oracles
We consider the problem of minimizing a convex function over a convex se...
research
∙
12/26/2014
Unsupervised Learning through Prediction in a Model of Cortex
We propose a primitive called PJOIN, for "predictive join," which combin...
research
∙
12/09/2014
