4 papers · 1 filter
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Guy Kornowski, Ohad Shamir
We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate conv…
Are Convex Optimization Curves Convex?
Guy Barzilai, Ohad Shamir, Moslem Zamani
In this paper, we study when we might expect the optimization curve induced by gradient descent to be \emph{convex} -- precluding, for example, an initial plateau followed by a sha…
On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
Guy Kornowski, Swati Padmanabhan, Ohad Shamir
We study the oracle complexity of nonsmooth nonconvex optimization, with the algorithm assumed to have access only to local function information. It has been shown by Davis, Drusvy…
Open Problem: Anytime Convergence Rate of Gradient Descent
Guy Kornowski, Ohad Shamir
Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives, merely by changing the stepsize sequence. We show that this can lead to surprisin…