BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:A Survey of First-Order Iterative Methods in the Design of Fast Gr
 aph Algorithms: from Multiplicative Weight Updates to Nesterov’s Algorit
 hm
DTSTART:20140724T110000
DTEND:20140724T120000
DTSTAMP:20260915T235055Z
UID:c5311448a9b6ab782b13a264239532ae1c6dd46d7c87880366eb5f44
CATEGORIES:Conferences - Seminars
DESCRIPTION:Lorenzo Orechhia\, MIT\nAbstract: Fast iterative methods from 
 Convex Optimization play a crucial role in a number of recent breakthrough
 s in the design of nearly-linear-time algorithms for fundamental graph pro
 blems\, such as maximum flow and graph partitioning. Multiplicative Weight
  Updates\, Euclidean and Non-Euclidean Gradient Descent\, and Nesterov’s
  Method have become a mainstay in the construction and analysis of fast al
 gorithms.\nHowever\, until recently\, the relation between these different
  methods and the reason for their success have been somewhat murky.  What
  is the exact relation between Multiplicative Weight Updates and Gradient 
 Descent? Why do Multiplicative Weight Updates show up in so many settings?
  What is the intuition behind Nesterov’s iterative algorithm that achiev
 es the asymptotically optimal iteration count for smooth convex functions 
 (hint: it isn’t just an algebraic trick)? The answer to these questions 
 was not clear.\nIn this survey\, we will provide answers by presenting a u
 nified framework that reveals the power and limitations of each method and
  provides much needed geometric intuition. Among other insights\, we will 
 explain how Multiplicative Weight Updates are a particular instance of a d
 ual iterative method\, known as Mirror Descent\, and how Nesterov’s algo
 rithm can be naturally derived as a combination of Mirror and Gradient Des
 cent.\nBio: Lorenzo Orecchia is a Postdoctoral Associate at the Massachuse
 tts Institute of Technology. Starting January 2015\, Lorenzo will be an As
 sistant Professor in Computer Science at Boston University. Orecchia obtai
 ned his PhD in Theoretical Computer Science at UC Berkeley under the super
 vision of Satish Rao in 2011 and has been an Applied Mathematics Instructo
 r at MIT under the supervision of Jon Kelner until May 2014. Orecchia is i
 nterested in the interplay of Convex and Combinatorial Optimization. In pa
 rticular\, he is currently focusing on the design of fast algorithms for f
 undamental combinatorial problems that rely on ideas from continuous optim
 ization.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR