1.6k citations · 1.7k across the 22 of their papers we have counts for
8 papers · 1 filter
Near-optimal method for highly smooth convex optimization
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee +2
We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the order Taylor expansion of a function at t…
Adversarial Examples from Cryptographic Pseudo-Random Generators
Sébastien Bubeck, Yin Tat Lee, Eric Price +1
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the…
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li +1
Let be a family of sets in some metric space. In the -chasing problem, an online algorithm observes a request sequence of sets in and respo…
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
This paper shows how to solve linear programs of the form with variables in time where is the e…
The Kannan-Lovász-Simonovits Conjecture
Yin Tat Lee, Santosh S. Vempala
The Kannan-Lovász-Simonovits conjecture says that the Cheeger constant of any logconcave density is achieved to within a universal, dimension-independent constant factor by a hyper…
Metrical task systems on trees via mirror descent and unfair gluing
Sébastien Bubeck, Michael B. Cohen, James R. Lee +1
We consider metrical task systems on tree metrics, and present an -competitive randomized algorithm based on the mirror descent framework introduce…