Oracle Complexity in Nonsmooth Nonconvex Optimization
Dec 6, 2021
Speakers
Guy Kornowski
Speaker · 0 followers
Ohad Shamir
Speaker · 1 follower
About
It is well-known that given a smooth, bounded-from-below, and possibly nonconvex function, standard gradient-based methods can find ϵ-stationary points (with gradient norm less than ϵ) in 𝒪(1/ϵ^2) iterations. However, many important nonconvex optimization problems, such as those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. In this paper, we study nonsmooth nonconvex optimization from an oracle complexity viewpoint, where the algorithm is assumed to be given access only to local information about the function at various points. We provide two main results (under mild assumptions): First, we consider the problem of getting near ϵ-stationary points. This is perhaps the most natural relaxation of finding ϵ-stationary points, which is impossible in the nonsmooth nonconvex case. We prove that this relaxed goal cannot be achieved efficiently, for any distance and ϵ smaller than some constants. Our second result deals with the possibility of tackling nonsmooth nonconvex optimization by reduction to smooth optimization: Namely, applying smooth optimization methods on a smooth approximation of the objective function. For this approach, we prove an inherent trade-off between oracle complexity and smoothness: On the one hand, smoothing a nonsmooth nonconvex function can be done very efficiently (e.g., by randomized smoothing), but with dimension-dependent factors in the smoothness parameter, which can strongly affect iteration complexity when plugging into standard smooth optimization methods. On the other hand, these dimension factors can be eliminated with suitable smoothing methods, but only by making the oracle complexity of the smoothing process exponentially large.It is well-known that given a smooth, bounded-from-below, and possibly nonconvex function, standard gradient-based methods can find ϵ-stationary points (with gradient norm less than ϵ) in 𝒪(1/ϵ^2) iterations. However, many important nonconvex optimization problems, such as those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. In this paper, we study nonsmooth nonconvex optimization from an oracle complexity viewpoint, where the algo…
Organizer
NeurIPS 2021
Account · 1.9k followers
Categories
Mathematics
Category · 2.4k presentations
AI & Data Science
Category · 10.8k presentations
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Deep learning for biological sequences
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Quantitative Epistemology - Empowering Human Meta-learning using Machine Learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Keynote speakers Q&A
Watch later
Sarit Kraus, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Similarity and Matching of Neural Network Representations
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Long-Term Credit Assignment via Model-based Temporal Shortcuts
Watch later
Michel Ma, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Pay Attention to What You Need: Do Structural Priors Still Matter in the Age of Billion Parameter Models?
Watch later
Total of 1 viewers voted for saving the presentation to eternal vault which is 0.1%