[Colloquium] REMINDER: [TTIC Talks] 10/3 Talks at TTIC: Yair Carmon, Stanford University

[Alicia McClarin]

*When:*      Thursday, October 3rd at 11:00 am



*Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who: *       Yair Carmon, Stanford University


*Title:        *The oracle complexity of approximately minimizing
non-convex functions

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

Based on joint work with John Duchi, Oliver Hinder and Aaron Sidford.

*Host: *Nati Srebro <nati at ttic.edu>

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 518*
*Chicago, IL 60637*
*773-834-3321*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191003/aeeb2b3a/attachment.html>