research
∙
07/28/2023
Noisy Interpolation Learning with Shallow Univariate ReLU Networks
We study the asymptotic overfitting behavior of interpolation with minim...
share
research
∙
06/22/2023
An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression
We study the cost of overfitting in noisy kernel ridge regression (KRR),...
research
∙
06/06/2023
Continual Learning in Linear Classification on Separable Data
We analyze continual learning on a sequence of separable linear classifi...
research
∙
05/25/2023
Most Neural Networks Are Almost Learnable
We present a PTAS for learning random constant-depth networks. We show t...
research
∙
03/02/2023
Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization
Linear classifiers and leaky ReLU networks trained by gradient flow on t...
research
∙
03/02/2023
The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks
In this work, we study the implications of the implicit bias of gradient...
research
∙
02/15/2023
Efficiently Learning Neural Networks: What Assumptions May Suffice?
Understanding when neural networks can be learned efficiently is a funda...
research
∙
02/14/2023
Interpolation Learning With Minimum Description Length
We prove that the Minimum Description Length learning rule exhibits temp...
research
∙
10/21/2022
A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models
We prove a new generalization bound that shows for any class of linear p...
research
∙
09/15/2022
Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization
We present a minimax optimal learner for the problem of learning predict...
research
∙
05/21/2022
Pessimism for Offline Linear Contextual Bandits using ℓ_p Confidence Sets
We present a family {π̂}_p≥ 1 of pessimistic learning rules for offline ...
research
∙
02/27/2022
Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization
We consider linear prediction with a convex Lipschitz loss, or more gene...
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
∙
12/28/2021
Exponential Family Model-Based Reinforcement Learning via Score Matching
We propose an optimistic model-based algorithm, dubbed SMRL, for finite-...
research
∙
12/08/2021
Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression
We study a localized notion of uniform convergence known as an "optimist...
research
∙
10/20/2021
Transductive Robust Learning Guarantees
We study the problem of adversarially robust learning in the transductiv...
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/06/2021
On Margin Maximization in Linear and ReLU Networks
The implicit bias of neural networks has been extensively studied in rec...
research
∙
08/09/2021
On the Power of Differentiable Learning versus PAC and SQ Learning
We study the power of learning via mini-batch stochastic gradient descen...
research
∙
07/01/2021
Fast Margin Maximization via Dual Acceleration
We present and analyze a momentum-based gradient method for training lin...
research
∙
06/17/2021
Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
We consider interpolation learning in high-dimensional linear regression...
research
∙
06/04/2021
An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
We present and analyze an algorithm for optimizing smooth and convex or ...
research
∙
04/14/2021
Eluder Dimension and Generalized Rank
We study the relationship between the eluder dimension for a function cl...
research
∙
03/01/2021
Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
We study the relative power of learning with gradient descent on differe...
research
∙
02/19/2021
On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
Recent work has highlighted the role of initialization scale in determin...
research
∙
02/03/2021
Adversarially Robust Learning with Unknown Perturbation Sets
We study the problem of learning predictors that are robust to adversari...
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/04/2021
Does Invariant Risk Minimization Capture Invariance?
We show that the Invariant Risk Minimization (IRM) formulation of Arjovs...
research
∙
10/22/2020
Reducing Adversarially Robust Learning to Non-Robust PAC Learning
We study the problem of reducing adversarially robust learning to standa...
research
∙
07/13/2020
Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
We provide a detailed asymptotic study of gradient flow trajectories and...
research
∙
07/09/2020
Predictive Value Generalization Bounds
In this paper, we study a bi-criterion framework for assessing scoring f...
research
∙
06/10/2020
On Uniform Convergence and Low-Norm Interpolation Learning
We consider an underdetermined noisy linear regression model where the m...
research
∙
06/08/2020
Minibatch vs Local SGD for Heterogeneous Distributed Learning
We analyze Local SGD (aka parallel or federated SGD) and Minibatch SGD i...
research
∙
05/15/2020
Efficiently Learning Adversarially Robust Halfspaces with Noise
We study the problem of learning adversarially robust halfspaces in the ...
research
∙
04/02/2020
Mirrorless Mirror Descent: A More Natural Discretization of Riemannian Gradient Flow
We present a direct (primal only) derivation of Mirror Descent as a "par...
research
∙
03/09/2020
Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
We present and study approximate notions of dimensional and margin compl...
research
∙
03/06/2020
Dropout: Explicit Forms and Capacity Control
We investigate the capacity control provided by dropout in various machi...
research
∙
02/26/2020
Fair Learning with Private Demographic Data
Sensitive attributes such as race are rarely available to learners in re...
research
∙
02/20/2020
Kernel and Rich Regimes in Overparametrized Models
A recent line of work studies overparametrized neural networks in the "k...
research
∙
02/18/2020
Is Local SGD Better than Minibatch SGD?
We study local SGD (also known as parallel SGD and federated averaging),...
research
∙
12/05/2019
Lower Bounds for Non-Convex Stochastic Optimization
We lower bound the complexity of finding ϵ-stationary points (with gradi...
research
∙
10/03/2019
A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
A key element of understanding the efficacy of overparameterized neural ...
research
∙
07/01/2019
Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
We note that known methods achieving the optimal oracle complexity for f...
research
∙
06/21/2019
Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis
We design a general framework for answering adaptive statistical queries...
research
∙
06/13/2019
Kernel and Deep Regimes in Overparametrized Models
A recent line of work studies overparametrized neural networks in the "k...
research
∙
05/17/2019
Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
With an eye toward understanding complexity control in deep learning, we...
research
∙
04/23/2019
Semi-Cyclic Stochastic Gradient Descent
We consider convex SGD updates with a block-cyclic structure, i.e. where...
research
∙
02/13/2019
How do infinite width bounded norm networks look in function space?
We consider the question of what functions can be captured by ReLU netwo...
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/12/2019