16 citations · 79 across the 28 of their papers we have counts for
11 papers · 1 filter
First Order Stochastic Optimization with Oblivious Noise
Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park +1
We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup. In our setting, in addition to random observation…
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions
Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park +1
We demonstrate the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We assume we have sample access…
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…
The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
Aravind Gollakota, Sushrut Karmalkar, Adam Klivans
We consider the problem of distribution-free learning for Boolean function classes in the PAC and agnostic models. Generalizing a beautiful work of Malach and Shalev-Shwartz (2022)…
Robustly Learning any Clusterable Mixture of Gaussians
Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane +1
We study the efficient learnability of high-dimensional Gaussian mixtures in the outlier-robust setting, where a small constant fraction of the data is adversarially corrupted. We…
Lower Bounds for Compressed Sensing with Generative Models
Akshay Kamath, Sushrut Karmalkar, Eric Price
The goal of compressed sensing is to learn a structured signal from a limited number of noisy linear measurements . In traditional compressed sensing, "structure"…
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane +2
We study high-dimensional sparse estimation tasks in a robust setting where a constant fraction of the dataset is adversarially corrupted. Specifically, we focus on the fundamental…
List-Decodable Linear Regression
Sushrut Karmalkar, Adam R. Klivans, Pravesh K. Kothari
We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than fraction of examples. For any $α…
Compressed Sensing with Adversarial Sparse Noise via L1 Regression
Sushrut Karmalkar, Eric Price
We present a simple and effective algorithm for the problem of \emph{sparse robust linear regression}. In this problem, one would like to estimate a sparse vector $w^* \in \mathbb{…
Robust polynomial regression up to the information theoretic limit
Daniel Kane, Sushrut Karmalkar, Eric Price
We consider the problem of robust polynomial regression, where one receives samples that are usually within of a polynomial , but have a chance of be…