Efficient List-Decodable Regression using Batches
Abstract
We begin the study of list-decodable linear regression using batches.
In this setting only an $\alpha \in (0,1]$ fraction of the batches are genuine, each providing a batch of $\ge n$ i.i.d. samples from a common unknown distribution. The remaining batches may contain arbitrary or even adversarial samples.
We derive a polynomial time algorithm that for any $n\ge \tilde \Omega(1/\alpha)$ returns a list of size $\mathcal O(1/\alpha)$ such that one of the item in the list is close to the true regression parameter. The algorithm requires only $\tilde\cO(d)$ genuine batches, and works under fairly general assumptions on the distribution.
The results demonstrate the utility of batch structure, which allows for the first polynomial time algorithm for list-decodable regression, which may be impossible for non-batch setting, as suggested by a recent SQ lower bound~\cite{diakonikolas2021statistical} for the non-batch setting.
In this setting only an $\alpha \in (0,1]$ fraction of the batches are genuine, each providing a batch of $\ge n$ i.i.d. samples from a common unknown distribution. The remaining batches may contain arbitrary or even adversarial samples.
We derive a polynomial time algorithm that for any $n\ge \tilde \Omega(1/\alpha)$ returns a list of size $\mathcal O(1/\alpha)$ such that one of the item in the list is close to the true regression parameter. The algorithm requires only $\tilde\cO(d)$ genuine batches, and works under fairly general assumptions on the distribution.
The results demonstrate the utility of batch structure, which allows for the first polynomial time algorithm for list-decodable regression, which may be impossible for non-batch setting, as suggested by a recent SQ lower bound~\cite{diakonikolas2021statistical} for the non-batch setting.
Research Areas
