# Oracle Complexity in Nonsmooth Nonconvex Optimization

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 14 Apr 2021.

## Builds on (most cited first, 18 of 18)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems](https://mlsanity.com/paper/1706.06461/) (2017)
- [On Graduated Optimization for Stochastic Non-Convex Problems](https://mlsanity.com/paper/1503.03712/) (2015)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Analysis of nonsmooth stochastic approximation: the differential inclusion approach](https://mlsanity.com/paper/1805.01916/) (2018)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions](https://mlsanity.com/paper/2002.04130/) (2020)
- [Lower Bound for Randomized First Order Convex Optimization](https://mlsanity.com/paper/1709.03594/) (2017)
- [On the Randomized Complexity of Minimizing a Convex Quadratic Function](https://mlsanity.com/paper/1807.09386/) (2018)

## Built on by (most cited first, 30 of 39)

- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (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)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [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)
- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [On the Complexity of Finding Small Subgradients in Nonsmooth Optimization](https://mlsanity.com/paper/2209.10346/) (2022)
- [Private Zeroth-Order Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2406.19579/) (2024)
- [Optimization on Pareto sets: On a theory of multi-objective optimization](https://mlsanity.com/paper/2308.02145/) (2023)
- [Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Framework](https://mlsanity.com/paper/2309.13278/) (2023)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Low-rank bias, weight decay, and model merging in neural networks](https://mlsanity.com/paper/2502.17340/) (2025)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2608.26288/) (2026)
- [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [Adaptive Batch Size for Privately Finding Second-Order Stationary Points](https://mlsanity.com/paper/2410.07502/) (2024)
- [Musec: MomentUm SpEctral Clipping for Stable Muon-type Training](https://mlsanity.com/paper/2609.11655/) (2026)
- [RedEx: Beyond Fixed Representation Methods via Convex Optimization](https://mlsanity.com/paper/2401.07606/) (2024)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)
- [An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization](https://mlsanity.com/paper/2210.16099/) (2022)
- [Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization](https://mlsanity.com/paper/2406.19475/) (2024)
- [On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2409.10323/) (2024)

## Abstract (arXiv)

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 O(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: 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 under a mild assumption 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.