Lorenzo Orrechia and Zeyuan Allen Zhu: A Survey of First-Order Iterative Methods in the Design of Fast Graph Algorithms

Friday, April 11, 2014 - 12:45pm to 3:45pm
Refreshments: 
Pizza at 12:30pm
Location: 
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Speaker: 
Lorenzo Orrechia and Zeyuan Allen Zhu

Full title: A Survey of First-Order Iterative Methods in the Design of Fast Graph Algorithms: from Multiplicative Weight Updates to Nesterov’s Algorithm via Regularization.

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.