research
∙
09/14/2023
Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
Can we accelerate convergence of gradient descent without changing the a...
share
research
∙
02/20/2023
Faster high-accuracy log-concave sampling via algorithmic warm starts
Understanding the complexity of sampling from a strongly log-concave and...
research
∙
12/24/2022
Concentration of the Langevin Algorithm's Stationary Distribution
A canonical algorithm for log-concave sampling is the Langevin Algorithm...
research
∙
10/29/2022
Flows, Scaling, and Entropy Revisited: a Unified Perspective via Optimizing Joint Distributions
In this short expository note, we describe a unified algorithmic perspec...
research
∙
10/16/2022
Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling
Sampling from a high-dimensional distribution is a fundamental task in s...
research
∙
05/27/2022
Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
A central issue in machine learning is how to train models on sensitive ...
research
∙
06/22/2021
Asymptotics for semi-discrete entropic optimal transport
We compute exact second-order asymptotics for the cost of an optimal sol...
research
∙
06/16/2021
Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent
We study first-order optimization algorithms for computing the barycente...
research
∙
06/04/2021
Kernel approximation on algebraic varieties
Low-rank approximation of kernels is a fundamental mathematical problem ...
research
∙
01/04/2021
Wasserstein barycenters are NP-hard to compute
The problem of computing Wasserstein barycenters (a.k.a. Optimal Transpo...
research
∙
12/10/2020
Hardness results for Multimarginal Optimal Transport problems
Multimarginal Optimal Transport (MOT) is the problem of linear programmi...
research
∙
08/07/2020
Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure
Multimarginal Optimal Transport (MOT) has recently attracted significant...
research
∙
06/14/2020
High-precision Wasserstein barycenters in polynomial time
Computing Wasserstein barycenters is a fundamental geometric problem wit...
research
∙
04/07/2020
Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a...
research
∙
04/06/2020