Wednesday, April 18, 2018 - 12:00pm to 1:00pm
Location:ASA Conference Room 6115 Gates Hillman Centers
Speaker:JONAH SHERMAN, Ph.D. Student https://people.eecs.berkeley.edu/~jsherman/
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.