BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Quest for a unified theory of efficient optimizati
 on
DTSTART:20170227T101500
DTEND:20170227T113000
DTSTAMP:20260916T044019Z
UID:986389b53838214f793f465d184dc62cbae28d8e832aad0306210663
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : David Steurer - Cornell University\nIC Faculty candidate\
 n\nAbstract :\nNon-convex and discrete optimization problems are at the he
 art of many algorithmic tasks that arise in machine learning and other com
 puting applications.\nA promising approach to solve such problems is the s
 um-of-squares (SOS) meta-algorithm\, which has been discovered multiple ti
 mes across different disciplines including control theory\, proof complexi
 ty\, and quantum information.\n\nWe show in a sequence of recent works tha
 t for a wide range of optimization problems this meta-algorithm achieves t
 he best known provable guarantees\, often improving significantly over all
  previous methods.\nFor example\, we obtain the first polynomial-time algo
 rithm for learning sparse dictionaries in the case of non-independent coor
 dinates beyond the square-root of dimension sparsity threshold that has be
 en a inherent barrier for previous provable methods.\nRemarkably\, SOS ach
 ieves these guarantees without being tailored to specific problems.\n\nMor
 eover\, we prove that for a rich class of problems\, the guarantees that S
 OS achieves are optimal with respect to a restricted but very powerful mod
 el of computation.\nThis result leads to the strongest known unconditional
  lower bounds for NP-complete problems.\n\nTaken together these results po
 int toward a unified theory for efficient optimization centered around SOS
  that could change how we think about efficient computation and bring a ki
 nd of conceptual clarity to the design of algorithms we had never anticipa
 ted.\n\nBio :\nDavid Steurer is an Assistant Professor in the department o
 f computer science at Cornell University and a Visiting Assistant Professo
 r at the Institute for Advanced Study in Princeton.\nHis research interest
 s are in the theory of algorithms\, complexity\, and machine learning.\nHi
 s goal is to identify the underlying principles that distinguish tractable
  problems from intractable ones.\nSteurer received his PhD from Princeton 
 University advised by Sanjeev Arora and was a postdoctoral researcher at M
 icrosoft Research for two years before joining Cornell University.\nFor hi
 s work\, he received best paper awards at STOC and FOCS\, a Microsoft Rese
 arch Faculty Fellowship\, an ACM Doctoral Dissertation Award Honorable Men
 tion\, an NSF CAREER Award\, and an Alfred P. Sloan Research Fellowship.\n
 \nMore information \n 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR