2.5k citations · 4.7k across the 60 of their papers we have counts for
22 papers · 1 filter
Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic
Eshika Saxena, Alberto Alfarano, François Charton +3
Recent work showed that ML-based attacks on Learning with Errors (LWE), a hard problem used in post-quantum cryptography, outperform classical algebraic attacks in certain settings…
Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
Zeyuan Allen-Zhu, Yuanzhi Li
Generative adversarial networks (GANs) are among the most successful models for learning high-complexity, real-world distributions. However, in theory, due to the highly non-convex…
Byzantine-Resilient Non-Convex Stochastic Gradient Descent
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li +1
We study adversary-resilient stochastic distributed optimization, in which machines can independently compute stochastic gradients, and cooperate to jointly optimize over their…
Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
Zeyuan Allen-Zhu, Yuanzhi Li
We formally study how ensemble of deep learning models can improve test accuracy, and how the superior performance of ensemble can be distilled into a single model using knowledge…
Feature Purification: How Adversarial Training Performs Robust Deep Learning
Zeyuan Allen-Zhu, Yuanzhi Li
Despite the empirical success of using Adversarial Training to defend deep learning models against adversarial perturbations, so far, it still remains rather unclear what the princ…
Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning
Zeyuan Allen-Zhu, Yuanzhi Li
Deep learning is also known as hierarchical learning, where the learner _learns_ to represent a complicated target function by decomposing it into a sequence of simpler functions t…
What Can ResNet Learn Efficiently, Going Beyond Kernels?
Zeyuan Allen-Zhu, Yuanzhi Li
How can neural networks such as ResNet efficiently learn CIFAR-10 with test accuracy more than 96%, while other methods, especially kernel methods, fall relatively behind? Can we m…
Can SGD Learn Recurrent Neural Networks with Provable Generalization?
Zeyuan Allen-Zhu, Yuanzhi Li
Recurrent Neural Networks (RNNs) are among the most popular models in sequential data analysis. Yet, in the foundational PAC learning language, what concept class can it learn? Mor…
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang
The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit w…
A Convergence Theory for Deep Learning via Over-Parameterization
Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a…
On the Convergence Rate of Training Recurrent Neural Networks
Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
How can local-search methods such as stochastic gradient descent (SGD) avoid bad local minima in training multi-layer neural networks? Why can they fit random labels even given non…
Is Q-learning Provably Efficient?
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck +1
Model-free reinforcement learning (RL) algorithms, such as Q-learning, directly parameterize and update value functions or policies without explicitly modeling the environment. The…
Byzantine Stochastic Gradient Descent
Dan Alistarh, Zeyuan Allen-Zhu, Jerry Li
This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the machines which allegedly compute stochastic gradients every it…
Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
Zeyuan Allen-Zhu
The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasingly important in machine learning, and is the…
Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
Zeyuan Allen-Zhu, Sébastien Bubeck, Yuanzhi Li
Regret bounds in online learning compare the player's performance to , the optimal performance in hindsight with a fixed strategy. Typically such bounds scale with the square…
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
Zeyuan Allen-Zhu
Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives . However, in terms of making the gradients small, the origin…
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…
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…
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…
Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters
Zeyuan Allen-Zhu, Yang Yuan, Karthik Sridharan
The amount of data available in the world is growing faster than our ability to deal with it. However, if we take advantage of the internal \emph{structure}, data may become much s…
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia
In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required r…
Survey & Experiment: Towards the Learning Accuracy
Zeyuan Allen Zhu
To attain the best learning accuracy, people move on with difficulties and frustrations. Though one can optimize the empirical objective using a given set of samples, its generaliz…