261 citations · 1.4k across the 45 of their papers we have counts for
9 papers · 1 filter
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…
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…
Is Q-learning Provably Efficient?
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck +1
Model-free reinforcement learning (RL) algorithms, such as Q-learning, directly parameterize and update value functions or policies without explicitly modeling the environment. The…
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…
A Nearly-Linear Bound for Chasing Nested Convex Bodies
C. J. Argue, Sébastien Bubeck, Michael B. Cohen +2
Friedman and Linial introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems. In convex body chasing, at…