Breaking the l_infinity Regularization Barrier: Approximating Undirected Multicommodity Flow in Nearly-Linear Time

April 18, 2018 (GHC 6115
)

Regularization is one of the most powerful tools in continuous optimization, yet existing approaches using strong-convexity fail for several important problems due to the infamous "l_infinity barrier". In this talk, we show strong-convexity may be relaxed to a weaker notion of "area-convexity", for which those barriers do not apply. Using area-convex regularization, we obtain a fast algorithm for approximately solving matrix inequality systems AX <= B over right-stochastic matrices X. By combining that algorithm with recent work on maximum-flow, we obtain a nearly-linear time approximation algorithm for maximum concurrent flow in undirected graphs.