research
∙
05/24/2023
Can Copyright be Reduced to Privacy?
There is an increasing concern that generative AI models may produce out...
share
research
∙
02/09/2023
Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
We examine the relationship between the mutual information between the o...
research
∙
06/07/2022
Better Best of Both Worlds Bounds for Bandits with Switching Costs
We study best-of-both-worlds algorithms for bandits with switching cost,...
research
∙
04/19/2022
Making Progress Based on False Discoveries
We consider the question of adaptive data analysis within the framework ...
research
∙
02/27/2022
Benign Underfitting of Stochastic Gradient Descent
We study to what extent may stochastic gradient descent (SGD) be underst...
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
∙
06/29/2021
Never Go Full Batch (in Stochastic Convex Optimization)
We study the generalization performance of full-batch optimization algor...
research
∙
06/25/2021
Littlestone Classes are Privately Online Learnable
We consider the problem of online classification under a privacy constra...
research
∙
02/02/2021
Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
Which classes can be learned properly in the online model? – that is, by...
research
∙
02/01/2021
SGD Generalizes Better Than GD (And Regularization Doesn't Help)
We give a new separation result between the generalization performance o...
research
∙
06/24/2020
A Limitation of the PAC-Bayes Framework
PAC-Bayes is a useful framework for deriving generalization bounds which...
research
∙
03/13/2020
Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study
The notion of implicit bias, or implicit regularization, has been sugges...
research
∙
03/01/2020
An Equivalence Between Private Classification and Online Prediction
We prove that every concept class with finite Littlestone dimension can ...
research
∙
02/24/2020
Prediction with Corrupted Expert Advice
We revisit the fundamental problem of prediction with expert advice, in ...
research
∙
06/01/2019
Graph-based Discriminators: Sample Complexity and Expressiveness
A basic question in learning theory is to identify if two distributions ...
research
∙
02/13/2019
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
We study the expressive power of kernel methods and the algorithmic feas...
research
∙
02/09/2019
Passing Tests without Memorizing: Two Models for Fooling Discriminators
We introduce two mathematical frameworks for foolability in the context ...
research
∙
06/04/2018
Private PAC learning implies finite Littlestone dimension
We show that every approximately differentially private learning algorit...
research
∙
11/16/2017
On Communication Complexity of Classification Problems
This work introduces a model of distributed learning in the spirit of Ya...
research
∙
10/05/2014
On the Computational Efficiency of Training Neural Networks
It is well-known that neural networks are computationally hard to train....
research
∙
04/26/2013