544 citations · 653 across the 48 of their papers we have counts for
8 papers · 1 filter
On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
Sitan Chen, Xiaoxiao Li, Zhao Song +1
In this work, we examine the security of InstaHide, a scheme recently proposed by [Huang, Song, Li and Arora, ICML'20] for preserving the security of private datasets in the contex…
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
Sitan Chen, Frederic Koehler, Ankur Moitra +1
In this work we revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits, from the perspective of adversarial robustness. Exis…
Learning Deep ReLU Networks Is Fixed-Parameter Tractable
Sitan Chen, Adam R. Klivans, Raghu Meka
We consider the problem of learning an unknown ReLU network with respect to Gaussian inputs and obtain the first nontrivial results for networks of depth more than two. We give an…
Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
Sitan Chen, Frederic Koehler, Ankur Moitra +1
In this paper we revisit some classic problems on classification under misspecification. In particular, we study the problem of learning halfspaces under Massart noise with rate $η…
Learning Polynomials of Few Relevant Dimensions
Sitan Chen, Raghu Meka
Polynomial regression is a basic primitive in learning and statistics. In its most basic form the goal is to fit a degree polynomial to a response variable in terms of an $…
Entanglement is Necessary for Optimal Quantum Property Testing
Sebastien Bubeck, Sitan Chen, Jerry Li
There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity. Unfortunately, they requir…
Algorithmic Foundations for the Diffraction Limit
Sitan Chen, Ankur Moitra
For more than a century and a half it has been widely-believed (but was never rigorously shown) that the physics of diffraction imposes certain fundamental limits on the resolution…
Learning Structured Distributions From Untrusted Batches: Faster and Simpler
Sitan Chen, Jerry Li, Ankur Moitra
We revisit the problem of learning from untrusted batches introduced by Qiao and Valiant [QV17]. Recently, Jain and Orlitsky [JO19] gave a simple semidefinite programming approach…