[AI Seminar] Theory Lunch: Jonah Sherman on Breaking the l_infinity Regularization Barrier

[Anupam Gupta]

Hi all: talk of potential interest by Jonah Sherman, starting in 5 minutes.

---------- Forwarded message ----------
From: Roie Levin <roiel at andrew.cmu.edu>
Date: Wed, Apr 18, 2018 at 10:15 AM
Subject: Today at Theory Lunch: Jonah Sherman
To: theory-announce at cs.cmu.edu

Hello all,

Please join us Today at noon in GHC 6115 where lunch will be provided. A
video recording of the talk will be available on the

*CMU Youtube Theory channel
<https://www.youtube.com/channel/UCWFp4UWNiOv71j0sPbdNiqw>. *
*Location/Time:* GHC 6115/Today, April 18, 12-1pm

*Speaker:** Jonah Sherman*
*Title**:* Breaking the l_infinity Regularization Barrier: Approximating
Undirected Multicommodity Flow in Nearly-Linear Time

*Abstract: *
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.

See you there!
Ellis + Roie
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/ai-seminar-announce/attachments/20180418/d09df1bb/attachment.html>