# Deterministic Nonsmooth Nonconvex Optimization

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 63 references that are in the map.
- First posted on arXiv 16 Feb 2023.

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

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [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)
- [Optimizing Mode Connectivity via Neuron Alignment](https://mlsanity.com/paper/2009.02439/) (2020)
- [Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning](https://mlsanity.com/paper/1909.10300/) (2019)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions](https://mlsanity.com/paper/2112.09002/) (2021)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Gradient Sampling Methods for Nonsmooth Optimization](https://mlsanity.com/paper/1804.11003/) (2018)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Smooth activations and reproducibility in deep networks](https://mlsanity.com/paper/2010.09931/) (2020)
- [No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzians](https://mlsanity.com/paper/2210.06907/) (2022)
- [Pathological subgradient dynamics](https://mlsanity.com/paper/1910.13604/) (2019)
- [Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization](https://mlsanity.com/paper/1709.07180/) (2017)

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

- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Adam with model exponential moving average is effective for nonconvex optimization](https://mlsanity.com/paper/2405.18199/) (2024)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization](https://mlsanity.com/paper/2411.07061/) (2024)
- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Optimization on Pareto sets: On a theory of multi-objective optimization](https://mlsanity.com/paper/2308.02145/) (2023)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2406.01484/) (2024)
- [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [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)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024)
- [On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2409.10323/) (2024)
- [HOME-3: High-Order Momentum Estimator with Third-Power Gradient for Convex and Smooth Nonconvex Optimization](https://mlsanity.com/paper/2505.11748/) (2025)
- [Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Study](https://mlsanity.com/paper/2505.11752/) (2025)
- [Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses](https://mlsanity.com/paper/2605.10219/) (2026)
- [Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2605.24513/) (2026)
- [Adam Converges in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2606.22326/) (2026)
- [Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles](https://mlsanity.com/paper/2607.17607/) (2026)
- [Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2610.05789/) (2026)

## Abstract (arXiv)

We study the complexity of optimizing nonsmooth nonconvex Lipschitz functions by producing (δ,ε)-stationary points. Several recent works have presented randomized algorithms that produce such points using tilde O(δ-1ε-3) first-order oracle calls, independent of the dimension d. It has been an open problem as to whether a similar result can be obtained via a deterministic algorithm. We resolve this open problem, showing that randomization is necessary to obtain a dimension-free rate. In particular, we prove a lower bound of Omega(d) for any deterministic algorithm. Moreover, we show that unlike smooth or convex optimization, access to function values is required for any deterministic algorithm to halt within any finite time. On the other hand, we prove that if the function is even slightly smooth, then the dimension-free rate of tilde O(δ-1ε-3) can be obtained by a deterministic algorithm with merely a logarithmic dependence on the smoothness parameter. Motivated by these findings, we turn to study the complexity of deterministically smoothing Lipschitz functions. Though there are efficient black-box randomized smoothings, we start by showing that no such deterministic procedure can smooth functions in a meaningful manner, resolving an open question. We then bypass this impossibility result for the structured case of ReLU neural networks. To that end, in a practical white-box setting in which the optimizer is granted access to the network's architecture, we propose a simple, dimension-free, deterministic smoothing that provably preserves (δ,ε)-stationary points. Our method applies to a variety of architectures of arbitrary depth, including ResNets and ConvNets. Combined with our algorithm, this yields the first deterministic dimension-free algorithm for optimizing ReLU networks, circumventing our lower bound.