12 citations · 25 across the 7 of their papers we have counts for
9 papers
ReSQueing Parallel and Private Stochastic Convex Optimization
Yair Carmon, Arun Jambulapati, Yujia Jin +4
We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probab…
Weil-Poincaré series and topology of collections of valuations on rational double points
A. Campillo, F. Delgado, S. M. Gusein-Zade
Earlier it was described to which extent the Alexander polynomial in several variables of an algebraic link in the Poincaré sphere determines the topology of the link. It was shown…
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford +1
In this paper we provide an time randomized algorithm for solving linear programs with variables and constraints with high probability. To obtain this…
Chasing Nested Convex Bodies Nearly Optimally
Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee +2
The convex body chasing problem, introduced by Friedman and Linial, is a competitive analysis problem on any normed vector space. In convex body chasing, for each timestep $t\in\ma…
An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
Yin Tat Lee, He Sun
For any undirected and weighted graph with vertices and edges, we call a sparse subgraph of , with proper reweighting of the edges, a -s…
Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing
Yin Tat Lee, Santosh S. Vempala
We show that the Cheeger constant for -dimensional isotropic logconcave measures is , improving on the previous best bound of As corollari…
Kernel-based methods for bandit convex optimization
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee
We consider the adversarial convex bandit problem and we build the first -time algorithm with -regret for this problem. To do so we int…
Geodesic Walks in Polytopes
Yin Tat Lee, Santosh S. Vempala
We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities.…
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia +1
In this paper, we introduce a new framework for approximately solving flow problems in capacitated, undirected graphs and apply it to provide asymptotically faster algorithms for t…