<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><span class="" style="font-size: 12pt; font-family: Helvetica, sans-serif;"></span> <br class=""><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div class="" style="orphans: 2; widows: 2;"><span class="" style="font-size: 14px;"></span></div><div class="" style="orphans: 2; widows: 2;"></div></div></div></div></div><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div class="" style="orphans: 2; widows: 2;"><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font size="4" class="">Lorenzo Orecchia</font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span class="" style="font-size: 14px;"><i class="">Boston University<br class=""></i></span><div class=""><span class="" style="font-size: 14px;"><i class=""><span class="Apple-tab-span" style="white-space: pre;"> </span></i></span></div></div><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font class="" style="font-size: 14px;"><br class=""></font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span class=""><b class=""><font class="" size="4">Wednesday, April 3, 2019 at 1:00 pm<br class="">Crerar 390</font></b><br class=""></span></div></div><div class="" style="orphans: 2; widows: 2;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class=""><br class=""></div><div class=""><div class=""><font class="" style="font-size: 15px;"><span class=""><b class="" style="color: rgb(33, 33, 33);">Title: </b></span></font><font color="#212121" class=""><span class="" style="font-size: 15px;">First-Order Methods Unleashed: Scalable Optimization in the Age of Big Data</span></font></div><div class="" style="color: rgb(33, 33, 33);"><b class=""><font class="" style="font-size: 15px;"><br class=""></font></b></div><div class="" style="color: rgb(33, 33, 33);"><b class=""><font class="" style="font-size: 15px;">Abstract:</font></b></div><div class=""><font class=""><span class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><div class=""><font class=""><span class=""><span id="docs-internal-guid-bf351367-7fff-5067-8c8e-0130cc54a81c" class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class=""><span class=""><span class="" style="font-size: 15px; white-space: pre-wrap;">First-order methods are a fundamental tool in the design of efficient algorithms for large-scale computational problems. Besides being the optimization workhorse of machine learning, first-order methods have recently served as a springboard for a number of algorithmic advances in discrete optimization, including submodular optimization and maximum flow problems. In this talk, I will showcase a number of results from my research that demonstrate the power of first-order methods as a generic framework for algorithm design.<br class=""> <br class="">In the first part, I will describe my view of first-order methods as discretizations of continuous dynamical systems over curved spaces. For convex optimization, such dynamics conserve a specific quantity -- the product of time and a notion of duality gap -- which immediately guarantees convergence to optimum. This primal-dual view helps us to both design novel algorithms and simplify the analyses of existing ones. In particular, I will discuss how it yields a simple, intuitive analysis of accelerated algorithms and how it allows us to port such algorithms to contexts that do not squarely match standard smoothness assumptions.<br class=""> <br class="">In the second part, we will see how to exploit problem-specific structure by preconditioning, i.e., by endowing the space with a curved geometry that facilitates the convergence of the dynamics above. In particular, I will describe how different random-walk-based algorithms for graph partitioning arise from different preconditionings of the same optimization problem, and how combinatorial preconditioners yield nearly-linear-time algorithms for flow problems over undirected graph.</span><br class=""><br class=""></span></span></div></span></span><b class="" style="font-size: 15px; color: rgb(33, 33, 33);">Bio:</b></font></div></div></span></font></div><div class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class="">Lorenzo Orecchia is an assistant professor in the Department of Computer Science at Boston University. Lorenzo's research focuses on the design of efficient algorithms for fundamental computational challenges in machine learning and combinatorial optimization. His approach is based on combining ideas from continuous and discrete optimization into a single framework for algorithm design. Lorenzo obtained his PhD in computer science at UC Berkeley under the supervision of Satish Rao in 2011, and was an applied mathematics instructor at MIT under the supervision of Jon Kelner until 2014. He was a recipient of the 2014 SODA Best Paper award and a co-organizer of the Simons semester ``Bridging Continuous and Discrete Optimization'' in Fall 2017.</i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><br class=""></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><b class="">Host: Rebecca Willett</b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 14px;"><i class=""><b class=""><br class=""></b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 14px;"><i class=""><b class="">PDF:</b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 14px;"><i class=""><b class=""></b></i></span></font></div></div></div></div></div></div></div></div></div></div></div></body></html>