We give the first polynomial-time algorithm for robust regression in the listdecodable setting where an adversary can corrupt a greater than1/2 fraction ofexamples.

Inevitably these systems need to deal with the plethora of practical issues that arise from automation. One important aspect is being able to deal with corrupted or irregular data, either due to poor data collection, the presence of outliers, or adversarial attacks by malicious agents.

We consider the problem of hypothesis testing for discrete distributions.

In this paper, we find an appealing way to synthesize [JO19] and [CLM19] to give the best of both worlds: an algorithm which runs in polynomial time and can exploit structure in the underlying distribution to achieve sublinear sample complexity.

Commonly used classification algorithms in machine learning, such as support vector machines, minimize a convex surrogate loss on training examples. In practice, these algorithms are surprisingly robusttoerrors inthe training data.

Each participating individual should be able tocontribute without the fearofleaking one'ssensitiveinformation. At the same time, thesystem should berobustinthepresence ofmalicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable to the other.

The statistical-query model is a well-studied framework for analyzing the sample complexity of learning problems andcaptures mostknownlearning algorithms.

Under label corruptions, we prove that this simple estimator achieves minimax near-optimal riskonawiderange ofgeneralized linear models, including Gaussian regression, Poisson regression and Binomial regression.