2.5k citations · 4.7k across the 60 of their papers we have counts for
9 papers · 1 filter
The Lingering of Gradients: Theory and Applications
Zeyuan Allen-Zhu, David Simchi-Levi, Xinshang Wang
Classically, the time complexity of a first-order method is estimated by its number of gradient computations. In this paper, we study a more refined complexity by taking into accou…
Natasha 2: Faster Non-Convex Optimization Than SGD
Zeyuan Allen-Zhu
We design a stochastic algorithm to train any smooth neural network to -approximate local minima, using backpropagations. The best result was…
Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
Zeyuan Allen-Zhu
Given a nonconvex function that is an average of smooth functions, we design stochastic first-order methods to find its approximate stationary points. The convergence of our ne…
First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
Zeyuan Allen-Zhu, Yuanzhi Li
We study streaming principal component analysis (PCA), that is to find, in space, the top eigenvectors of a hidden matrix with online vectors drawn…
Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
Zeyuan Allen-Zhu, Yuanzhi Li
We study -GenEV, the problem of finding the top generalized eigenvectors, and -CCA, the problem of finding the top vectors in canonical-correlation analysis. We propo…
Katyusha: The First Direct Acceleration of Stochastic Gradient Methods
Zeyuan Allen-Zhu
Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting,…
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…
Optimal Black-Box Reductions Between Optimization Objectives
Zeyuan Allen-Zhu, Elad Hazan
The diverse world of machine learning applications has given rise to a plethora of algorithms and optimization methods, finely tuned to the specific regression or classification ta…
Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik +1
Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is…