research
∙
03/22/2023
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
The notion of replicable algorithms was introduced in Impagliazzo et al....
share
research
∙
02/13/2023
Do PAC-Learners Learn the Marginal Distribution?
We study a foundational variant of Valiant and Vapnik and Chervonenkis' ...
research
∙
05/02/2022
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Fast mixing of random walks on hypergraphs has led to myriad breakthroug...
research
∙
04/25/2022
Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
We construct an explicit family of 3-XOR instances hard for Ω(n)-levels ...
research
∙
01/24/2022
Active Learning Polynomial Threshold Functions
We initiate the study of active learning polynomial threshold functions ...
research
∙
11/17/2021
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Hypercontractivity is one of the most powerful tools in Boolean function...
research
∙
11/08/2021
Realizable Learning is All You Need
The equivalence of realizable and agnostic learnability is a fundamental...
research
∙
02/09/2021
Bounded Memory Active Learning through Enriched Queries
The explosive growth of easily-accessible unlabeled data has lead to gro...
research
∙
11/09/2020
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games
Higher order random walks (HD-walks) on high dimensional expanders have ...
research
∙
04/23/2020
Point Location and Active Learning: Learning Halfspaces Almost Optimally
Given a finite set X ⊂ℝ^d and a binary linear classifier c: ℝ^d →{0,1}, ...
research
∙
01/15/2020
Noise-tolerant, Reliable Active Classification with Comparison Queries
With the explosion of massive, widely available unlabeled data in the pa...
research
∙
10/17/2019
A Novel CMB Component Separation Method: Hierarchical Generalized Morphological Component Analysis
We present a novel technique for Cosmic Microwave Background (CMB) foreg...
research
∙
07/08/2019
The Power of Comparisons for Actively Learning Linear Classifiers
In the world of big data, large but costly to label datasets dominate ma...
research
∙
09/03/2017