Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression

Add to your list(s) Download to your calendar using vCal

• Gabriel Arpino, University of Cambridge
• Wednesday 15 November 2023, 14:00-15:00
• MR5, CMS Pavilion A.

If you have a question about this talk, please contact Prof. Ramji Venkataramanan.

Large-scale datasets, other than being high-dimensional, can be highly heterogeneous. Real-world observations, when combined to form large datasets, often incorporate signals from different subpopulations. In this talk we will consider Mixed Sparse Linear Regression, a simple heterogeneous model for high-dimensional inference. This model includes the widely studied linear regression and phase retrieval models as special cases. We provide rigorous evidence for the existence of a fundamental statistical-computational tradeoff in this model, whenever the model parameters are sufficiently symmetric. Outside of this symmetric regime, we prove that an efficient algorithm is sample-optimal. To the best of our knowledge, this is the first thorough study of the interplay between mixture symmetry, signal sparsity, and their joint impact on the computational hardness of mixed sparse linear regression. This is joint work with Ramji Venkataramanan.

This talk is part of the Information Theory Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Information Theory Seminar
• Interested Talks
• MR5, CMS Pavilion A
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.