research
∙
05/24/2023
Lexinvariant Language Models
Token embeddings, a mapping from discrete lexical symbols to continuous ...
share
research
∙
10/03/2022
Online Pen Testing
We study a "pen testing" problem, in which we are given n pens with unkn...
research
∙
08/01/2022
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
In-context learning refers to the ability of a model to condition on a p...
research
∙
04/26/2022
From Sand to Flour: The Next Leap in Granular Computing with NanoSort
The granularity of distributed computing is limited by communication tim...
research
∙
03/29/2022
Efficient Convex Optimization Requires Superlinear Memory
We show that any memory-constrained, first-order algorithm which minimiz...
research
∙
01/12/2022
On the Statistical Complexity of Sample Amplification
Given n i.i.d. samples drawn from an unknown distribution P, when is it ...
research
∙
06/29/2021
Exponential Weights Algorithms for Selective Learning
We study the selective learning problem introduced by Qiao and Valiant (...
research
∙
02/17/2021
Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training
Self-training is a standard approach to semi-supervised learning where t...
research
∙
01/13/2021
On Misspecification in Prediction Problems and Robustness via Improper Learning
We study probabilistic prediction games when the underlying model is mis...
research
∙
12/07/2020
Stronger Calibration Lower Bounds via Sidestepping
We consider an online binary prediction setting where a forecaster obser...
research
∙
05/02/2020
On the Generalization Effects of Linear Transformations in Data Augmentation
Data augmentation is a powerful technique to improve performance in appl...
research
∙
12/12/2019
Sublinear Optimal Policy Value Estimation in Contextual Bandits
We study the problem of estimating the expected reward of the optimal po...
research
∙
11/09/2019
How bad is worst-case data if you know where it comes from?
We introduce a framework for studying how distributional assumptions on ...
research
∙
07/18/2019
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
We consider the problem of computing the maximum likelihood multivariate...
research
∙
07/11/2019
Making AI Forget You: Data Deletion in Machine Learning
Intense recent discussions have focused on how to provide individuals wi...
research
∙
06/03/2019
A Surprising Density of Illusionable Natural Speech
Recent work on adversarial examples has demonstrated that most natural i...
research
∙
04/26/2019
Sample Amplification: Increasing Dataset Size even when Learning is Impossible
Given data drawn from an unknown distribution, D, to what extent is it p...
research
∙
04/19/2019
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
We consider deep networks, trained via stochastic gradient descent to mi...
research
∙
04/18/2019
Memory-Sample Tradeoffs for Linear Regression with Small Error
We consider the problem of performing linear regression over a stream of...
research
∙
02/12/2019
Maximum Likelihood Estimation for Learning Populations of Parameters
Consider a setting with N independent individuals, each with an unknown ...
research
∙
02/12/2019
A Theory of Selective Prediction
We consider a model of selective prediction, where the prediction algori...
research
∙
01/25/2019
Equivariant Transformer Networks
How can prior knowledge on the transformation invariances of a domain be...
research
∙
11/15/2018
A Spectral View of Adversarially Robust Features
Given the apparent difficulty of learning models that are robust to adve...
research
∙
11/08/2018
An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
The log-concave maximum likelihood estimator (MLE) problem answers: for ...
research
∙
05/04/2018
Estimating Learnability in the Sublinear Data Regime
We consider the problem of estimating how well a model class is capable ...
research
∙
12/05/2017
Approximating the Spectrum of a Graph
The spectrum of a network or graph G=(V,E) with adjacency matrix A, cons...
research
∙
11/07/2017
Learning Overcomplete HMMs
We study the problem of learning overcomplete HMMs---those that have man...
research
∙
11/07/2017
Finding Heavily-Weighted Features in Data Streams
We introduce a new sub-linear space data structure---the Weight-Median S...
research
∙
06/25/2017
There and Back Again: A General Approach to Learning Sparse Models
We propose a simple and efficient approach to learning sparse models. Ou...
research
∙
03/15/2017
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
We introduce a criterion, resilience, which allows properties of a datas...
research
∙
03/06/2017
Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
The popular Alternating Least Squares (ALS) algorithm for tensor decompo...
research
∙
12/08/2016
Prediction with a Short Memory
We consider the problem of predicting the next observation given a seque...
research
∙
11/07/2016
Learning from Untrusted Data
The vast majority of theoretical results in machine learning and statist...
research
∙
01/30/2016
Spectrum Estimation from Samples
We consider the problem of approximating the set of eigenvalues of the c...
research
∙
04/17/2015
Testing Closeness With Unequal Sized Samples
We consider the problem of closeness testing for two discrete distributi...
research
∙
10/07/2013