27 citations · 61 across the 27 of their papers we have counts for
28 papers
Fast Algorithms for Sparse PCA and Robust Sparse Estimation
Giannis Iakovidis, Ankit Pensia
We study fast algorithms for sparse-PCA certification. Given a positive semidefinite matrix , the problem asks either to rule out a large -sparse quadratic form or to return…
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…
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…
SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia +1
We prove that there is a universal constant so that for every , every centered subgaussian distribution on , and every even $p \in…
Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
Thanasis Pittas, Ankit Pensia
Algorithmic robust statistics has traditionally focused on the contamination model where a small fraction of the samples are arbitrarily corrupted. We consider a recent contaminati…
Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study Gaussian sparse estimation tasks in Huber's contamination model with a focus on mean estimation, PCA, and linear regression. For each of these tasks, we give the first sam…
A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
Ankit Pensia
We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Specifically, the algorithm observes a \emph{corrupted} set of samples from $\ma…
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…
Black-Box -to--PCA Reductions: Theory and Applications
Arun Jambulapati, Syamantak Kumar, Jerry Li +3
The -principal component analysis (-PCA) problem is a fundamental algorithmic primitive that is widely-used in data analysis and dimensionality reduction applications. In sta…
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +1
We study the fundamental problems of Gaussian mean estimation and linear regression with Gaussian covariates in the presence of Huber contamination. Our main contribution is the de…
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +1
We study principal component analysis (PCA), where given a dataset in from a distribution, the task is to find a unit vector that approximately maximizes the var…
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +2
We study the problem of list-decodable Gaussian covariance estimation. Given a multiset of points in such that an unknown fraction of points in ar…
Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints
Ankit Pensia, Amir R. Asadi, Varun Jog +1
We study simple binary hypothesis testing under both local differential privacy (LDP) and communication constraints. We qualify our results as either minimax optimal or instance op…
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +1
We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples…
Gaussian Mean Testing Made Simple
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
We study the following fundamental hypothesis testing problem, which we term Gaussian mean testing. Given i.i.d. samples from a distribution on , the task is to d…
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the problem of list-decodable sparse mean estimation. Specifically, for a parameter , we are given points in , of whi…
Robust Sparse Mean Estimation via Sum of Squares
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the problem of high-dimensional sparse mean estimation in the presence of an -fraction of adversarial outliers. Prior work obtained sample and computationally efficient…
Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities
Ankit Pensia, Varun Jog, Po-Ling Loh
We study hypothesis testing under communication constraints, where each sample is quantized before being revealed to a statistician. Without communication constraints, it is well k…
Streaming Algorithms for High-Dimensional Robust Statistics
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +1
We study high-dimensional robust statistics tasks in the streaming model. A recent line of work obtained computationally efficient algorithms for a range of high-dimensional robust…
Sharp Concentration Inequalities for the Centered Relative Entropy
Alankrita Bhatt, Ankit Pensia
We study the relative entropy between the empirical estimate of a discrete distribution and the true underlying distribution. If the minimum value of the probability mass function…
Statistical Query Lower Bounds for List-Decodable Linear Regression
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +2
We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set of labeled examples $(x, y…
Robust regression with covariate filtering: Heavy tails and adversarial contamination
Ankit Pensia, Varun Jog, Po-Ling Loh
We study the problem of linear regression where both covariates and responses are potentially (i) heavy-tailed and (ii) adversarially contaminated. Several computationally efficien…