# A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2021.

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

- [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)
- [Adam with model exponential moving average is effective for nonconvex optimization](https://mlsanity.com/paper/2405.18199/) (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)
- [General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization](https://mlsanity.com/paper/2411.07061/) (2024)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [On the Complexity of Finding Small Subgradients in Nonsmooth Optimization](https://mlsanity.com/paper/2209.10346/) (2022)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [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)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [Stein Boltzmann Sampling: A Variational Approach for Global Optimization](https://mlsanity.com/paper/2402.04689/) (2024)
- [Adaptive Batch Size for Privately Finding Second-Order Stationary Points](https://mlsanity.com/paper/2410.07502/) (2024)
- [Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scale](https://mlsanity.com/paper/2501.19099/) (2025)
- [Revisiting Frank-Wolfe for Structured Nonconvex Optimization](https://mlsanity.com/paper/2503.08921/) (2025)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [Musec: MomentUm SpEctral Clipping for Stable Muon-type Training](https://mlsanity.com/paper/2609.11655/) (2026)
- [Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes](https://mlsanity.com/paper/2211.04655/) (2022)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Sliced Inner Product Gromov-Wasserstein Distances](https://mlsanity.com/paper/2605.08546/) (2026)
- [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024)
- [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)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)

## Abstract (arXiv)

Zhang et al. introduced a novel modification of Goldstein's classical subgradient method, with an efficiency guarantee of O(varepsilon-4) for minimizing Lipschitz functions. Their work, however, makes use of a nonstandard subgradient oracle model and requires the function to be directionally differentiable. In this paper, we show that both of these assumptions can be dropped by simply adding a small random perturbation in each step of their algorithm. The resulting method works on any Lipschitz function whose value and gradient can be evaluated at points of differentiability. We additionally present a new cutting plane algorithm that achieves better efficiency in low dimensions: O(dvarepsilon-3) for Lipschitz functions and O(dvarepsilon-2) for those that are weakly convex.