Research map / Learning theory and algorithms / Sample complexity
On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the Clarke subgradient oracle (Zhang et al. 2020, Assumption 1a) with a gradient oracle evaluated only at differentiable points (Assumption 3.1a) in the GAS algorithm (Perturbed INGD) | Perturbed INGD for Goldstein approximate stationarity · deterministic nonsmooth Lipschitz minimization | oracle calls to find (ϵ,δ)-GAS point | No clear effect |
| use a random conic perturbation of the sampling direction (Algorithm 1) instead of uniform sampling as in Zhang et al. 2020 | Perturbed INGD · deterministic GAS | finite-time oracle complexity | No clear effect |
| use a constant perturbation radius ζ instead of a gradient-norm-adaptive one in the stochastic setting | Perturbed stochastic INGD · stochastic GAS | convergence guarantee | No clear effect |
| introduce the (δ,η,κ)-outer Lipschitz continuity class of subdifferentials and compute NAS via GAS (Theorem 4.4) | Lipschitz functions with OLC subdifferential (e.g., ρ-margin SVM, 1- and 2-layer ReLU networks) · NAS computation | finite-time computability of (ϵ,δ)-NAS points | Helped |
Closest papers by meaning
- Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses (NeurIPS 2026 · similarity 0.89)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · similarity 0.87)
- First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.87)
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.86)
- On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.86)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.