b'Nathan Srebro'

research

∙ 07/28/2023

Noisy Interpolation Learning with Shallow Univariate ReLU Networks

We study the asymptotic overfitting behavior of interpolation with minim...

0 Nirmit Joshi, et al. ∙

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),...

0 Lijia Zhou, et al. ∙

research

∙ 06/06/2023

Continual Learning in Linear Classification on Separable Data

We analyze continual learning on a sequence of separable linear classifi...

0 Itay Evron, et al. ∙

research

∙ 05/25/2023

Most Neural Networks Are Almost Learnable

We present a PTAS for learning random constant-depth networks. We show t...

0 Amit Daniely, et al. ∙

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...

0 Spencer Frei, et al. ∙

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...

0 Spencer Frei, et al. ∙

research

∙ 02/15/2023

Efficiently Learning Neural Networks: What Assumptions May Suffice?

Understanding when neural networks can be learned efficiently is a funda...

0 Amit Daniely, et al. ∙

research

∙ 02/14/2023

Interpolation Learning With Minimum Description Length

We prove that the Minimum Description Length learning rule exhibits temp...

0 Naren Sarayu Manoj, et al. ∙

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...

0 Lijia Zhou, et al. ∙

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...

0 Omar Montasser, et al. ∙

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 ...

0 Gene Li, et al. ∙

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...

0 Idan Amir, et al. ∙

research

∙ 02/13/2022

The Sample Complexity of One-Hidden-Layer Neural Networks

We study norm-based uniform convergence bounds for neural networks, aimi...

0 Gal Vardi, et al. ∙

research

∙ 12/28/2021

Exponential Family Model-Based Reinforcement Learning via Score Matching

We propose an optimistic model-based algorithm, dubbed SMRL, for finite-...

12 Gene Li, et al. ∙

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...

0 Lijia Zhou, et al. ∙

research

∙ 10/20/2021

Transductive Robust Learning Guarantees

We study the problem of adversarially robust learning in the transductiv...

0 Omar Montasser, et al. ∙

research

∙ 10/07/2021

A Stochastic Newton Algorithm for Distributed Convex Optimization

We propose and analyze a stochastic Newton algorithm for homogeneous dis...

0 Brian Bullins, et al. ∙

research

∙ 10/06/2021

On Margin Maximization in Linear and ReLU Networks

The implicit bias of neural networks has been extensively studied in rec...

0 Gal Vardi, et al. ∙

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...

0 Emmanuel Abbe, et al. ∙

research

∙ 07/01/2021

Fast Margin Maximization via Dual Acceleration

We present and analyze a momentum-based gradient method for training lin...

0 Ziwei Ji, et al. ∙

research

∙ 06/17/2021

Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting

We consider interpolation learning in high-dimensional linear regression...

0 Frederic Koehler, et al. ∙

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 ...

0 Blake Woodworth, et al. ∙

research

∙ 04/14/2021

Eluder Dimension and Generalized Rank

We study the relationship between the eluder dimension for a function cl...

0 Gene Li, et al. ∙

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...

0 Eran Malach, et al. ∙

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...

0 Shahar Azulay, et al. ∙

research

∙ 02/03/2021

Adversarially Robust Learning with Unknown Perturbation Sets

We study the problem of learning predictors that are robust to adversari...

0 Omar Montasser, et al. ∙

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...

0 Blake Woodworth, et al. ∙

research

∙ 01/04/2021

Does Invariant Risk Minimization Capture Invariance?

We show that the Invariant Risk Minimization (IRM) formulation of Arjovs...

0 Pritish Kamath, et al. ∙

research

∙ 10/22/2020

Reducing Adversarially Robust Learning to Non-Robust PAC Learning

We study the problem of reducing adversarially robust learning to standa...

0 Omar Montasser, et al. ∙

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...

0 Edward Moroshko, et al. ∙

research

∙ 07/09/2020

Predictive Value Generalization Bounds

In this paper, we study a bi-criterion framework for assessing scoring f...

0 Keshav Vemuri, et al. ∙

research

∙ 06/10/2020

On Uniform Convergence and Low-Norm Interpolation Learning

We consider an underdetermined noisy linear regression model where the m...

0 Lijia Zhou, et al. ∙

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...

0 Blake Woodworth, et al. ∙

research

∙ 05/15/2020

Efficiently Learning Adversarially Robust Halfspaces with Noise

We study the problem of learning adversarially robust halfspaces in the ...

0 Omar Montasser, et al. ∙

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...

0 Suriya Gunasekar, et al. ∙

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...

0 Pritish Kamath, et al. ∙

research

∙ 03/06/2020

Dropout: Explicit Forms and Capacity Control

We investigate the capacity control provided by dropout in various machi...

0 Raman Arora, et al. ∙

research

∙ 02/26/2020

Fair Learning with Private Demographic Data

Sensitive attributes such as race are rarely available to learners in re...

0 Hussein Mozannar, et al. ∙

research

∙ 02/20/2020

Kernel and Rich Regimes in Overparametrized Models

A recent line of work studies overparametrized neural networks in the "k...

0 Blake Woodworth, et al. ∙

research

∙ 02/18/2020

Is Local SGD Better than Minibatch SGD?

We study local SGD (also known as parallel SGD and federated averaging),...

5 Blake Woodworth, et al. ∙

research

∙ 12/05/2019

Lower Bounds for Non-Convex Stochastic Optimization

We lower bound the complexity of finding ϵ-stationary points (with gradi...

0 Yossi Arjevani, et al. ∙

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 ...

0 Greg Ongie, et al. ∙

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...

0 Blake Woodworth, et al. ∙

research

∙ 06/21/2019

Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis

We design a general framework for answering adaptive statistical queries...

0 Ryan Rogers, et al. ∙

research

∙ 06/13/2019

Kernel and Deep Regimes in Overparametrized Models

A recent line of work studies overparametrized neural networks in the "k...

0 Blake Woodworth, et al. ∙

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...

0 Mor Shpigel Nacson, et al. ∙

research

∙ 04/23/2019

Semi-Cyclic Stochastic Gradient Descent

We consider convex SGD updates with a block-cyclic structure, i.e. where...

0 Hubert Eichner, et al. ∙

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...

0 Pedro Savarese, et al. ∙

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 ...

0 Dylan Foster, et al. ∙

research

∙ 02/12/2019

VC Classes are Adversarially Robustly Learnable, but Only Improperly

We study the question of learning an adversarially robust predictor. We ...

0 Omar Montasser, et al. ∙

Nathan Srebro

Featured Co-authors