# Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions

arXiv: https://arxiv.org/abs/2002.04130 · HTML: https://mlsanity.com/paper/2002.04130/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2020.

## Built on by (most cited first, 13 of 13)

- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2302.03407/) (2023)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes](https://mlsanity.com/paper/2301.06806/) (2023)
- [Private Zeroth-Order Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2406.19579/) (2024)
- [Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning](https://mlsanity.com/paper/2407.01825/) (2024)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization](https://mlsanity.com/paper/2206.06531/) (2022)

## Abstract (arXiv)

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 ε-stationary point with first-order methods is impossible in finite time. We then introduce the notion of (δ, ε)-stationarity, which allows for an ε-approximate gradient to be the convex combination of generalized gradients evaluated at points within distance δ to the solution. We propose a series of randomized first-order methods and analyze their complexity of finding a (δ, ε)-stationary point. Furthermore, we provide a lower bound and show that our stochastic algorithm has min-max optimal dependence on δ. Empirically, our methods perform well for training ReLU neural networks.