research
∙
07/10/2023
An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization
We study the complexity of producing (δ,ϵ)-stationary points of Lipschit...
share
research
∙
05/25/2023
Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks
We provide several new results on the sample complexity of vector-valued...
research
∙
05/24/2023
From Tempered to Benign Overfitting in ReLU Neural Networks
Overparameterized neural networks (NNs) are observed to generalize well ...
research
∙
02/16/2023
Deterministic Nonsmooth Nonconvex Optimization
We study the complexity of optimizing nonsmooth nonconvex Lipschitz func...
research
∙
09/21/2022
On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
We study the oracle complexity of producing (δ,ϵ)-stationary points of L...
research
∙
06/15/2022
Reconstructing Training Data from Trained Neural Networks
Understanding to what extent neural networks memorize training data is a...
research
∙
02/13/2022
The Sample Complexity of One-Hidden-Layer Neural Networks
We study norm-based uniform convergence bounds for neural networks, aimi...
research
∙
02/09/2022
Gradient Methods Provably Converge to Non-Robust Networks
Despite a great deal of research, it is still unclear why neural network...
research
∙
02/08/2022
Width is Less Important than Depth in ReLU Neural Networks
We solve an open question from Lu et al. (2017), by showing that any tar...
research
∙
01/30/2022
Implicit Regularization Towards Rank Minimization in ReLU Networks
We study the conjectured relationship between the implicit regularizatio...
research
∙
01/27/2022
The Implicit Bias of Benign Overfitting
The phenomenon of benign overfitting, where a predictor perfectly fits n...
research
∙
12/08/2021
Replay For Safety
Experience replay <cit.> is a widely used technique to achieve efficient...
research
∙
12/08/2021
Convergence Results For Q-Learning With Experience Replay
A commonly used heuristic in RL is experience replay (e.g. <cit.>), in w...
research
∙
10/07/2021
A Stochastic Newton Algorithm for Distributed Convex Optimization
We propose and analyze a stochastic Newton algorithm for homogeneous dis...
research
∙
10/07/2021
On the Optimal Memorization Power of ReLU Neural Networks
We study the memorization power of feedforward ReLU neural networks. We ...
research
∙
10/06/2021
On Margin Maximization in Linear and ReLU Networks
The implicit bias of neural networks has been extensively studied in rec...
research
∙
06/12/2021
Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
Recently, there has been much interest in studying the convergence rates...
research
∙
06/02/2021
Learning a Single Neuron with Bias Using Gradient Descent
We theoretically study the fundamental problem of learning a single neur...
research
∙
04/14/2021
Oracle Complexity in Nonsmooth Nonconvex Optimization
It is well-known that given a smooth, bounded-from-below, and possibly n...
research
∙
02/02/2021
The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
We resolve the min-max complexity of distributed stochastic convex optim...
research
∙
01/31/2021
The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
Several recent works have shown separation results between deep neural n...
research
∙
01/30/2021
Size and Depth Separation in Approximating Natural Functions with Neural Networks
When studying the expressive power of neural networks, a main challenge ...
research
∙
12/09/2020
Implicit Regularization in ReLU Networks with the Square Loss
Understanding the implicit regularization (or implicit bias) of gradient...
research
∙
10/13/2020
High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
In this note, we consider the complexity of optimizing a highly smooth (...
research
∙
06/30/2020
Gradient Methods Never Overfit On Separable Data
A line of recent works established that when training linear predictors ...
research
∙
06/01/2020
The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
We study the effects of mild over-parameterization on the optimization l...
research
∙
05/31/2020
Neural Networks with Small Weights and Depth-Separation Barriers
In studying the expressiveness of neural networks, an important question...
research
∙
02/27/2020
Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
It is well-known that given a bounded, smooth nonconvex function, standa...
research
∙
02/18/2020
Is Local SGD Better than Minibatch SGD?
We study local SGD (also known as parallel SGD and federated averaging),...
research
∙
02/03/2020
Proving the Lottery Ticket Hypothesis: Pruning is All You Need
The lottery ticket hypothesis (Frankle and Carbin, 2018), states that a ...
research
∙
01/15/2020
Learning a Single Neuron with Gradient Methods
We consider the fundamental problem of learning a single neuron x σ(w^ x...
research
∙
10/04/2019
The Complexity of Finding Stationary Points with Stochastic Gradient Descent
We study the iteration complexity of stochastic gradient descent (SGD) f...
research
∙
07/31/2019
How Good is SGD with Random Shuffling?
We study the performance of stochastic gradient descent (SGD) on smooth ...
research
∙
04/15/2019
Depth Separations in Neural Networks: What is Actually Being Separated?
Existing depth separation results for constant-depth networks essentiall...
research
∙
04/01/2019
On the Power and Limitations of Random Features for Understanding Neural Networks
Recently, a spate of papers have provided positive theoretical results f...
research
∙
02/13/2019
The Complexity of Making the Gradient Small in Stochastic Convex Optimization
We give nearly matching upper and lower bounds on the oracle complexity ...
research
∙
02/09/2019
Space lower bounds for linear prediction
We show that fundamental learning tasks, such as finding an approximate ...
research
∙
10/29/2018
Global Non-convex Optimization with Discretized Diffusions
An Euler discretization of the Langevin diffusion is known to converge t...
research
∙
09/23/2018
Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks
In this note, we study the dynamics of gradient descent on objective fun...
research
∙
06/26/2018
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
We provide tight finite-time convergence bounds for gradient descent and...
research
∙
04/18/2018
Are ResNets Provably Better than Linear Predictors?
A residual network (or ResNet) is a standard deep neural net architectur...
research
∙
03/04/2018
Detecting Correlations with Little Memory and Communication
We study the problem of identifying correlations in multivariate data, u...
research
∙
12/24/2017
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
We consider the optimization problem associated with training simple ReL...
research
∙
12/18/2017
Size-Independent Sample Complexity of Neural Networks
We study the sample complexity of learning neural networks, by providing...
research
∙
05/15/2017
Bandit Regret Scaling with the Effective Loss Range
We study how the regret guarantees of nonstochastic multi-armed bandits ...
research
∙
03/23/2017
Failures of Gradient-Based Deep Learning
In recent years, Deep Learning has become the go-to solution for a broad...
research
∙
11/15/2016
Oracle Complexity of Second-Order Methods for Finite-Sum Problems
Finite-sum optimization problems are ubiquitous in machine learning, and...
research
∙
10/31/2016
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
We provide several new depth-based separation results for feed-forward n...
research
∙
09/05/2016
Distribution-Specific Hardness of Learning Neural Networks
Although neural networks are routinely and successfully trained in pract...
research
∙
03/02/2016