You are here

A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions

Swati Padmanabhan, UW
Thursday, February 9, 2023 - 1:00pm to 2:00pm
Zoom - https://washington.zoom.us/j/99239593243

Gradient descent --- one of the simplest optimization algorithms --- has been a workhorse of large-scale machine learning for decades. In particular, the finite-time (i.e., "nonasymptotic") theoretical guarantees on its rates of convergence have been extensively studied on broad families of functions including convex and smooth functions. However, modern machine learning has witnessed the emergence of problems far beyond the aforementioned problem classes. Indeed, tremendous empirical success (such as that of deep learning) has recently been powered by tools like Google's TensorFlow and Facebook's PyTorch that use non-smooth non-convex optimization under the hood. A fundamental theoretical question, therefore, is to obtain nonasymptotic theoretical guarantees for non-smooth non-convex optimization. In this talk, I will present our result for this problem, giving the first non-asymptotic convergence guarantee for non-smooth non-convex optimization under the ``standard first-order oracle model''. This is joint work with Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, and Guanghao Ye and appeared as an Oral Presentation in NeurIPS 2022. 

Share