5 papers
Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers
Ilias Diakonikolas, Chao Gao, Daniel M. Kane +2
We study robust regression under a contamination model in which covariates are clean while the responses may be corrupted in an adaptive manner. Unlike the classical Huber's contam…
High-dimensional estimation with missing data: Statistical and computational limits
Kabir Aladin Verchand, Ankit Pensia, Saminul Haque +1
We consider computationally-efficient estimation of population parameters when observations are subject to missing data. In particular, we consider estimation under the realizable…
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Ilias Diakonikolas, Chao Gao, Daniel M. Kane +2
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a di…
The Sample Complexity of Simple Binary Hypothesis Testing
Ankit Pensia, Varun Jog, Po-Ling Loh
The sample complexity of simple binary hypothesis testing is the smallest number of i.i.d.\ samples required to distinguish between two distributions and in either: (i) the…
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia +1
We study for random rectangular matrices. If is an matrix with independent Gaussian entries, we give a new family of…