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) @
in Poster Session 6 »
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.
Keywords: Theory

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