Timezone: »

 
Poster
Statistical Query Lower Bounds for List-Decodable Linear Regression
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
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 $T$ of labeled examples $(x, y) \in \mathbb{R}^d \times \mathbb{R}$ and a parameter $0< \alpha <1/2$ such that an $\alpha$-fraction of the points in $T$ are i.i.d. samples from a linear regression model with Gaussian covariates, and the remaining $(1-\alpha)$-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of $d^{\mathrm{poly}(1/\alpha)}$ for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.

Author Information

Ilias Diakonikolas (UW Madison)
Daniel Kane (University of California, San Diego)
Ankit Pensia (University of Wisconsin-Madison)
Thanasis Pittas (University of Wisconsin, Madison)
Alistair Stewart (University of Southern California)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors