BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Information Theory Seminar
SUMMARY:Statistical-Computational Tradeoffs in Mixed Spars
e Linear Regression - Gabriel Arpino\, University
of Cambridge
DTSTART;TZID=Europe/London:20231115T140000
DTEND;TZID=Europe/London:20231115T150000
UID:TALK207589AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/207589
DESCRIPTION: Large-scale datasets\, other than being high-dime
nsional\, can be highly heterogeneous. Real-world
observations\, when combined to form large dataset
s\, often incorporate signals from different subpo
pulations. In this talk we will consider _Mixed Sp
arse Linear Regression_\, a simple heterogeneous m
odel for high-dimensional inference. This model in
cludes the widely studied linear regression and
phase retrieval models as special cases. We provid
e rigorous evidence for the existence of a fundame
ntal statistical-computational tradeoff in this mo
del\, whenever the model parameters are sufficient
ly symmetric. Outside of this symmetric regime\, w
e prove that an efficient algorithm is sample-opti
mal. To the best of our knowledge\, this is the fi
rst thorough study of the interplay between mixtur
e symmetry\, signal sparsity\, and their joint imp
act on the computational hardness of mixed sparse
linear regression. This is joint work with Ramji V
enkataramanan.
LOCATION:MR5\, CMS Pavilion A
CONTACT:Prof. Ramji Venkataramanan
END:VEVENT
END:VCALENDAR