BEGIN:VCALENDAR
VERSION:2.0
PRODID:talks.ox.ac.uk
BEGIN:VEVENT
SUMMARY:Algorithms and Algorithmic Obstacles in High-Dimensional Regressio
n - David Gamarnik (MIT Sloan School of Management\, USA)
DTSTART;VALUE=DATE-TIME:20180427T143000Z
DTEND;VALUE=DATE-TIME:20180427T153000Z
UID:https://talks.ox.ac.uk/talks/id/cf2bfe86-9395-49d1-a6bc-e8ee10e644be/
DESCRIPTION:Many optimization problems arising in studying of random struc
tures exhibit an apparent gap between the optimal values which can be esti
mated by non-constructive means\, and the best values achievable by fast (
polynomial time) algorithms. Through a combined effort of mathematicians\,
computer scientists and statistical physicists\, it became apparent that
a potential and in some cases a provable obstruction for designing algorit
hms bridging this gap is a phase transition in the geometry of nearly opti
mal solutions\, in particular the presence of a certain Overlap Gap Proper
ty (OGP).\n\nIn this talk we discuss this property in the context of spars
e high dimensional linear regression problem with Gaussian design. We show
that\, on the one hand\, in the sampling regime where the known fast meth
ods for this problem are effective\, the space of solutions exhibits a mon
otonicity with respect to the proximity to the ground truth regression vec
tor and no local optimums exist apart from the ground truth. On the other
hand\, once the sampling number is asymptotically in the regime where the
known methods fail\, we show that the monotonicity is lost\, and the model
exhibits an OGP. In the context of the regression problem this means ever
y solution exhibiting a small mean squared error is either fairly close to
the ground truth or is very far from it\, with no middle ground.\nSpeaker
s:\nDavid Gamarnik (MIT Sloan School of Management\, USA)
LOCATION:Large Lecture Theatre
URL:https://talks.ox.ac.uk/talks/id/cf2bfe86-9395-49d1-a6bc-e8ee10e644be/
BEGIN:VALARM
ACTION:display
DESCRIPTION:Talk:Algorithms and Algorithmic Obstacles in High-Dimensional
Regression - David Gamarnik (MIT Sloan School of Management\, USA)
TRIGGER:-PT1H
END:VALARM
END:VEVENT
END:VCALENDAR