261 citations · 1.4k across the 45 of their papers we have counts for
4 papers · 1 filter
Learning threshold neurons via the "edge of stability"
Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi +3
Existing analyses of neural network training often operate under the unrealistic assumption of an extremely small learning rate. This lies in stark contrast to practical wisdom and…
The Randomized -Server Conjecture is False!
Sébastien Bubeck, Christian Coester, Yuval Rabani
We prove a few new lower bounds on the randomized competitive ratio for the -server problem and other related problems, resolving some long-standing conjectures. In particular,…
On the complexity of finding stationary points of smooth functions in one dimension
Sinho Chewi, Sébastien Bubeck, Adil Salim
We characterize the query complexity of finding stationary points of one-dimensional non-convex but smooth functions. We consider four settings, based on whether the algorithms und…
Shortest Paths without a Map, but with an Entropic Regularizer
Sébastien Bubeck, Christian Coester, Yuval Rabani
In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while att…