research
∙
05/30/2023
When Does Optimizing a Proper Loss Yield Calibration?
Optimizing proper loss functions is popularly believed to yield predicto...
share
research
∙
04/19/2023
Loss minimization yields multicalibration for large neural networks
Multicalibration is a notion of fairness that aims to provide accurate p...
research
∙
02/24/2023
Generative Models of Huge Objects
This work initiates the systematic study of explicit distributions that ...
research
∙
11/30/2022
A Unifying Theory of Distance from Calibration
We study the fundamental question of how to define and measure the dista...
research
∙
11/16/2022
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
In many learning theory problems, a central role is played by a hypothes...
research
∙
10/24/2022
Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
Recovering linear subspaces from data is a fundamental and important tas...
research
∙
10/16/2022
Loss Minimization through the Lens of Outcome Indistinguishability
We present a new perspective on loss minimization and the recent notion ...
research
∙
09/15/2022
Omnipredictors for Constrained Optimization
The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wiede...
research
∙
03/09/2022
Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability
We give the first sample complexity characterizations for outcome indist...
research
∙
11/08/2021
An Improved Local Search Algorithm for k-Median
We present a new local-search algorithm for the k-median clustering prob...
research
∙
06/29/2021
Near-Optimal Explainable k-Means for All Dimensions
Many clustering algorithms are guided by certain cost functions such as ...
research
∙
03/02/2021
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization
In the non-negative matrix factorization (NMF) problem, the input is an ...
research
∙
08/18/2020
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
We study the problem of robustly estimating the mean of a d-dimensional ...
research
∙
03/24/2020
Robust and On-the-fly Dataset Denoising for Image Classification
Memorization in over-parameterized neural networks could severely hurt g...
research
∙
02/25/2020
The Power of Many Samples in Query Complexity
The randomized query complexity R(f) of a boolean function f{0,1}^n→{0,1...
research
∙
10/28/2018
Towards Understanding Learning Representations: To What Extent Do Different Neural Networks Learn the Same Representation
It is widely believed that learning good representations is one of the m...
research
∙
11/01/2017
Active Tolerant Testing
In this work, we give the first algorithms for tolerant testing of nontr...
research
∙
02/18/2017