2.5k citations · 4.7k across the 60 of their papers we have counts for
7 papers · 1 filter
Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach
Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh +1
The experimental design problem concerns the selection of k points from a potentially large design pool of p-dimensional vectors, so as to maximize the statistical efficiency regre…
Neon2: Finding Local Minima via First-Order Oracles
Zeyuan Allen-Zhu, Yuanzhi Li
We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector pro…
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…
Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
Zeyuan Allen-Zhu, Elad Hazan, Wei Hu +1
We propose a rank- variant of the classical Frank-Wolfe algorithm to solve convex optimization over a trace-norm ball. Our algorithm replaces the top singular-vector computation…
Much Faster Algorithms for Matrix Scaling
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira +1
We develop several efficient algorithms for the classical \emph{Matrix Scaling} problem, which is used in many diverse areas, from preconditioning linear systems to approximation o…
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…
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
Zeyuan Allen-Zhu, Yuanzhi Li
The online problem of computing the top eigenvector is fundamental to machine learning. In both adversarial and stochastic settings, previous results (such as matrix multiplicative…