Efficient List-Decodable Regression using Batches
Jul 24, 2023
Speakers
Ayush Jain
Speaker · 0 followers
Abhimanyu Das
Speaker · 0 followers
Weihao Kong
Speaker · 0 followers
About
We demonstrate the use of batches in studying list-decodable linear regression, in which only α∈ (0,1] fraction of batches contain genuine samples from a common distribution and the rest can contain arbitrary or even adversarial samples. When genuine batches have >Ω̃(1/α) samples each, our algorithm can efficiently find a small list of potential regression parameters, with a high probability that one of them is close to the true parameter. This is the first polynomial time algorithm for list-decodable linear regression, and its sample complexity scales nearly linearly with the dimension of the covariates. The polynomial time algorithm is made possible by the batch structure and may not be feasible without it, as suggested by a recent Statistical Query lower bound <cit.>.We demonstrate the use of batches in studying list-decodable linear regression, in which only α∈ (0,1] fraction of batches contain genuine samples from a common distribution and the rest can contain arbitrary or even adversarial samples. When genuine batches have >Ω̃(1/α) samples each, our algorithm can efficiently find a small list of potential regression parameters, with a high probability that one of them is close to the true parameter. This is the first polynomial time algorithm for list…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Slot-VAE: Slot Attention Enables Object-Centric Scene Generation
Watch later
Yanbo Wang, …
Towards Stable and Efficient Adversarial Training against l_1 Bounded Adversarial Attacks
Watch later
Yulun Jiang, …
spred: Solving L1 Penalty with SGD
Watch later
Liu Ziyin, …
Neural Distributed Compressor Does 'Binning'
Watch later
