Efficient List-Decodable Regression using Batches

Abstract

We begin the study of list-decodable linear regression using batches. In this setting only an (0,1] fraction of the batches are genuine. Each genuine batch contains n i.i.d. samples from a common unknown distribution and the remaining batches may contain arbitrary or even adversarial samples. We derive a polynomial time algorithm that for any n (1/) returns a list of size O(1/^2) such that one of the items in the list is close to the true regression parameter. The algorithm requires only O(d/^2) 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 the non-batch setting, as suggested by a recent SQ lower bound diakonikolas2021statistical for the non-batch setting.

Tasks

Reproductions