research
∙
11/22/2022
Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
Despite the widespread success of Transformers on NLP tasks, recent work...
share
research
∙
10/12/2022
When are Local Queries Useful for Robust Learning?
Distributional assumptions have been shown to be necessary for the robus...
research
∙
08/25/2022
Partial Matrix Completion
In the matrix completion problem, one wishes to reconstruct a low-rank m...
research
∙
05/24/2022
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy
Among the various aspects of algorithmic fairness studied in recent year...
research
∙
05/12/2022
Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks
A fundamental problem in adversarial machine learning is to quantify how...
research
∙
02/23/2022
Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition
The local Rademacher complexity framework is one of the most successful ...
research
∙
05/28/2021
Towards optimally abstaining from prediction
A common challenge across all areas of machine learning is that training...
research
∙
02/15/2021
Efficient Learning with Arbitrary Covariate Shift
We give an efficient algorithm for learning a binary function in a given...
research
∙
07/16/2020
Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning
We analyse the pruning procedure behind the lottery ticket hypothesis ar...
research
∙
07/08/2020
How benign is benign overfitting?
We investigate two causes for adversarial vulnerability in deep neural n...
research
∙
03/03/2020
Differentiable Causal Backdoor Discovery
Discovering the causal effect of a decision is critical to nearly all fo...
research
∙
02/01/2020
The Statistical Complexity of Early Stopped Mirror Descent
Recently there has been a surge of interest in understanding implicit re...
research
∙
09/15/2019
Online k-means Clustering
We study the problem of online clustering where a clustering algorithm h...
research
∙
09/12/2019
On the Hardness of Robust Classification
It is becoming increasingly important to understand the vulnerability of...
research
∙
09/11/2019
Implicit Regularization for Optimal Sparse Recovery
We investigate implicit regularization schemes for gradient descent meth...
research
∙
05/28/2019
Adaptive Reduced Rank Regression
Low rank regression has proven to be useful in a wide range of forecasti...
research
∙
10/10/2018
Decentralized Cooperative Stochastic Multi-armed Bandits
We study a decentralized cooperative stochastic multi-armed bandit probl...
research
∙
08/06/2018
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain
We study the problem of hypothesis testing between two discrete distribu...
research
∙
06/09/2018
TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service
Machine learning methods are widely used for a variety of prediction pro...
research
∙
04/19/2018
Low Rank Structure of Learned Representations
A key feature of neural networks, particularly deep convolutional neural...
research
∙
02/15/2018
Learning DNFs under product distributions via μ-biased quantum Fourier sampling
We show that DNF formulae can be quantum PAC-learned in polynomial time ...
research
∙
11/03/2017
From which world is your graph?
Discovering statistical structure from links is a fundamental problem in...
research
∙
04/07/2016
Online Optimization of Smoothed Piecewise Constant Functions
We study online optimization of smoothed piecewise constant functions ov...
research
∙
07/13/2013
MCMC Learning
The theory of learning under the uniform distribution is rich and deep, ...
research
∙
11/14/2012
Distributed Non-Stochastic Experts
We consider the online distributed non-stochastic experts problem, where...
research
∙
11/05/2012
Learning using Local Membership Queries
We introduce a new model of membership query (MQ) learning, where the le...
research
∙
04/11/2011