<div dir="ltr"><div class="gmail_default"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Thursday, October 3rd at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font></font>Yair Carmon, Stanford University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p></div><div class="gmail_default"><div><b>Title:        </b>The oracle complexity of approximately minimizing non-convex functions</div><div><br></div><div><b>Abstract: </b>We establish algorithmic upper bounds and algorithm-independent lower bounds for finding approximate stationary points of smooth, high-dimensional, potentially non-convex functions. To establish our upper bounds, we introduce "convex until proven guilty," an algorithm that leverages Nesterov's acceleration of gradient descent to guarantee faster convergence to stationarity when both the function and its gradient are smooth. To establish our lower bounds, we combine classical ideas from large-scale convex optimization with novel non-convex constructions. The main consequence of our results is that gradient descent is minimax  optimal for smooth functions; when derivatives are also smooth, our lower bounds nearly match the "convex until proven guilty" rates.</div><br>Based on joint work with John Duchi, Oliver Hinder and Aaron Sidford.<div><b><br></b></div><div><b>Host: </b><a href="mailto:nati@ttic.edu" target="_blank">Nati Srebro</a></div></div><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 518</i></div><div><i style="color:rgb(11,83,148)">Chicago, IL 60637</i><br></div></div><div><i style="color:rgb(11,83,148)">773-834-3321</i><i style="color:rgb(11,83,148)"><br></i></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div></div>