24 citations · 108 across the 21 of their papers we have counts for
5 papers · 1 filter
Short-step Methods Are Not Strongly Polynomial-Time
Manru Zong, Yin Tat Lee, Man-Chung Yue
Short-step methods are an important class of algorithms for solving convex constrained optimization problems. In this short paper, we show that under very mild assumptions on the s…
Acceleration with a Ball Optimization Oracle
Yair Carmon, Arun Jambulapati, Qijia Jiang +4
Consider an oracle which takes a point and returns the minimizer of a convex function in an ball of radius around . It is straightforward to show that rough…
Complexity of Highly Parallel Non-Smooth Convex Optimization
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee +2
A landmark result of non-smooth convex optimization is that gradient descent is an optimal algorithm whenever the number of computed gradients is smaller than the dimension . In…
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…
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
Kevin Scaman, Francis Bach, Sébastien Bubeck +2
In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptio…