124 citations · 1.6k across the 112 of their papers we have counts for
9 papers · 1 filter
Finding Approximate Local Minima Faster than Gradient Descent
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins +2
We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and t…
A Non-generative Framework and Convex Relaxations for Unsupervised Learning
Elad Hazan, Tengyu Ma
We give a novel formal theoretical framework for unsupervised learning with two distinctive characteristics. First, it does not assume any generative model and based on a worst-cas…
Faster Eigenvector Computation via Shift-and-Invert Preconditioning
Dan Garber, Elad Hazan, Chi Jin +4
We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix -- i.e. computing a unit vector such that …
An optimal algorithm for bandit convex optimization
Elad Hazan, Yuanzhi Li
We consider the problem of online convex optimization against an arbitrary adversary with bandit feedback, known as bandit convex optimization. We give the first $\tilde{O}(\sqrt{T…
Online Learning with Low Rank Experts
Elad Hazan, Tomer Koren, Roi Livni +1
We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown -dimensional subspace.…
Variance Reduction for Faster Non-Convex Optimization
Zeyuan Allen-Zhu, Elad Hazan
We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem…