Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions

Abstract

We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonconvex functions. In particular, we study the class of Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions for which the chain rule of calculus holds. This class contains examples such as ReLU neural networks and others with non-differentiable activation functions. We first show that finding an $\epsilon$-stationary point with first-order methods is impossible in finite time. We then introduce the notion of $(\delta ,\epsilon )$-stationarity, which allows for an $\epsilon$-approximate gradient to be the convex combination of generalized gradients evaluated at points within distance $\delta$ to the solution. We propose a series of randomized first-order methods and analyze their complexity of finding a $(\delta ,\epsilon )$-stationary point. Furthermore, we provide a lower bound and show that our stochastic algorithm has min-max optimal dependence on $\delta$. Empirically, our methods perform well for training ReLU neural networks.

References in corpus (11)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Escaping Saddles with Stochastic Gradients
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Analysis of nonsmooth stochastic approximation: the differential inclusion approach
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
• Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning

Cited by in corpus (9)

• A mathematical model for automatic differentiation in machine learning
• Adam${}^{+}$: A Stochastic Method with Adaptive Variance Reduction
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• Support Vector Machine Classifier via $L_{0/1}$ Soft-Margin Loss
• Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• Incremental Without Replacement Sampling in Nonconvex Optimization
• On The Convergence of First Order Methods for Quasar-Convex Optimization