BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20170326T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20161030T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260429T024210Z
UID:585bcc8a77ece863551534@ist.ac.at
DTSTART:20170130T084500
DTEND:20170130T094500
DESCRIPTION:Speaker: David Steurer\nAbstract: Non-convex and discrete optim
 ization problems are at the heart of many algorithmic tasks that arise in 
 machine learning and other computing applications\, for example\, learning
  mixtures of Gaussians and sparse dictionaries.\n\nIn a sequence of recent
  works\, we show that a concrete polynomial-time meta-algorithm called sum
 -of-squares (SOS) achieves for a wide range of these problems the stronges
 t known provable guarantees. \nRemarkably\, SOS achieves these guarantees 
 without being tailored to problem specifics.\n\nWe also show that for a ri
 ch class of problems\, the guarantees that SOS achieves are optimal for a 
 restricted but very powerful model of computation. \nThis result leads to 
 the strongest known unconditional lower bounds for NP-complete problems.\n
 \nTaken together these results point to a unified theory for efficient opt
 imization centered around SOS that could change how we think about efficie
 nt computation in general and bring a kind of conceptual clarity to the de
 sign of efficient algorithms we had never anticipated.
LOCATION:Mondi Seminar Room 3\, Central Building\, ISTA
ORGANIZER:pdelreal@ist.ac.at
SUMMARY:David Steurer: Quest for a unified theory of efficient optimization
URL:https://talks-calendar.ista.ac.at/events/268
END:VEVENT
END:VCALENDAR