A Survey of First-Order Iterative Methods in the Design of Fast Graph Algorithms: from Multiplicative Weight Updates to Nesterov’s Algorithm
Event details
| Date | 24.07.2014 |
| Hour | 11:00 › 12:00 |
| Speaker | Lorenzo Orechhia, MIT |
| Location | |
| Category | Conferences - Seminars |
Abstract: Fast iterative methods from Convex Optimization play a crucial role in a number of recent breakthroughs in the design of nearly-linear-time algorithms for fundamental graph problems, 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 algorithms.
However, 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 achieves 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.
In this survey, we will provide answers by presenting a unified 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 dual iterative method, known as Mirror Descent, and how Nesterov’s algorithm can be naturally derived as a combination of Mirror and Gradient Descent.
Bio: Lorenzo Orecchia is a Postdoctoral Associate at the Massachusetts Institute of Technology. Starting January 2015, Lorenzo will be an Assistant Professor in Computer Science at Boston University. Orecchia obtained his PhD in Theoretical Computer Science at UC Berkeley under the supervision of Satish Rao in 2011 and has been an Applied Mathematics Instructor at MIT under the supervision of Jon Kelner until May 2014. Orecchia is interested in the interplay of Convex and Combinatorial Optimization. In particular, he is currently focusing on the design of fast algorithms for fundamental combinatorial problems that rely on ideas from continuous optimization.
However, 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 achieves 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.
In this survey, we will provide answers by presenting a unified 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 dual iterative method, known as Mirror Descent, and how Nesterov’s algorithm can be naturally derived as a combination of Mirror and Gradient Descent.
Bio: Lorenzo Orecchia is a Postdoctoral Associate at the Massachusetts Institute of Technology. Starting January 2015, Lorenzo will be an Assistant Professor in Computer Science at Boston University. Orecchia obtained his PhD in Theoretical Computer Science at UC Berkeley under the supervision of Satish Rao in 2011 and has been an Applied Mathematics Instructor at MIT under the supervision of Jon Kelner until May 2014. Orecchia is interested in the interplay of Convex and Combinatorial Optimization. In particular, he is currently focusing on the design of fast algorithms for fundamental combinatorial problems that rely on ideas from continuous optimization.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi