mlsanityData to 7 Oct 2026

On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions

arXiv 2112.09002 ↗First posted 16 Dec 2021math.OCcited by 30

Not on the map. Why?

Abstract (arXiv)

We report a practical finite-time algorithmic scheme to compute approximately stationary points for nonconvex nonsmooth Lipschitz functions. In particular, we are interested in two kinds of approximate stationarity notions for nonconvex nonsmooth problems, i.e., Goldstein approximate stationarity (GAS) and near-approximate stationarity (NAS). For GAS, our scheme removes the unrealistic subgradient selection oracle assumption in (Zhang et al., 2020, Assumption 1) and computes GAS with the same finite-time complexity. For NAS, Davis & Drusvyatskiy (2019) showed that ρ-weakly convex functions admit finite-time computation, while Tian & So (2021) provided the matching impossibility results of dimension-free finite-time complexity for first-order methods. Complement to these developments, in this paper, we isolate a new class of functions that could be Clarke irregular (and thus not weakly convex anymore) and show that our new algorithmic scheme can compute NAS points for functions in that class within finite time. To demonstrate the wide applicability of our new theoretical framework, we show that ρ-margin SVM, 1-layer, and 2-layer ReLU neural networks, all being Clarke irregular, satisfy our new conditions.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Dec 2021.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 6; 2024: 8; 2025: 4; 2026: 9.

30 papers.

Sort:

  1. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  2. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  3. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 25
  4. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 22
  5. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
  6. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
  7. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 14
  8. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 13
  9. 2023Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimizationcited by 11
  10. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  11. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 7
  12. 2025Expected Variational Inequalitiescited by 5
18 more
  1. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  2. 2024Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 3
  3. 2023Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithmscited by 2
  4. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 2
  5. 2022Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizescited by 1
  6. 2026The Convergence Behavior of Adam under Heavy-Tailed Noisecited by 1
  7. 2026Musec: MomentUm SpEctral Clipping for Stable Muon-type Trainingcited by 1
  8. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  9. 2024On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimizationcited by 0
  10. 2024On subdifferential chain rule of matrix factorization and beyondcited by 0
  11. 2024ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary pointscited by 0
  12. 2025The Hidden Power of Normalization Layers in Neural Networks: Exponential Capacity Controlcited by 0
  13. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  14. 2026Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Lossescited by 0
  15. 2026Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noisecited by 0
  16. 2026Adam Converges in Nonsmooth Nonconvex Optimizationcited by 0
  17. 2026Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oraclescited by 0
  18. 2026The Exponential Price of Determinism in Nonsmooth Nonconvex Optimizationcited by 0