Research map / Optimization / Nonconvex and smooth optimization
Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes generalized Goldstein stationarity notions (generalized gradient mapping and δ-Frank–Wolfe gap) and four zeroth-order stochastic methods (projected and projection-free, minibatch and variance-reduced) with non-asymptotic guarantees for constrained nonconvex nonsmooth optimization.
Problem
Non-asymptotic convergence for stochastic nonconvex nonsmooth optimization over a closed convex compact set using only zeroth-order (function value) oracles; classical gradient mapping and Frank–Wolfe gap are ill-suited because they require gradients everywhere and Clarke-based criteria admit no fin
Approach
Generalize gradient mapping and the Frank–Wolfe gap using Goldstein δ-subdifferentials to define (γ,δ,ϵ)-generalized Goldstein stationarity and (δ,ϵ)-Goldstein Frank–Wolfe stationarity, then obtain finite-time rates for zeroth-order projected SGD and Frank–Wolfe with two-point randomized-smoothing gradient estimators (minibatch and variance-reduced).
Key results
- MB-ZOSPGD attains a (γ,δ,ϵ)-generalized Goldstein stationary point with O(d^{3/2} δ^{-1} ϵ^{-4}) function queries; VR-ZOSPGD improves this to O(d^{3/2} δ^{-1} ϵ^{-3}).
- MB-ZOSFW and VR-ZOSFW reach (δ,ϵ)-Goldstein Frank–Wolfe stationarity with O(d^{3/2} δ^{-1} ϵ^{-4}) and O(d^{3/2} δ^{-1} ϵ^{-3}) function queries respectively.
- In experiments on robust low-rank matrix recovery, both Frank–Wolfe variants converge faster than projection-based variants in processed time on synthetic and MovieLens 1M data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use variance reduction instead of a minibatch estimator | ZOSPGD · Constrained nonconvex nonsmooth stochastic optimization | FQO complexity: O(d^{3/2} δ^{-1} ϵ^{-4}) -> O(d^{3/2} δ^{-1} ϵ^{-3}) | Helped |
| Use variance reduction instead of a minibatch estimator | ZOSFW · Constrained nonconvex nonsmooth stochastic optimization | FQO complexity: O(d^{3/2} δ^{-1} ϵ^{-4}) -> O(d^{3/2} δ^{-1} ϵ^{-3}) | Helped |
| Use projection-free Frank–Wolfe updates instead of projected updates | ZOSFW · Synthetic robust low-rank matrix recovery | loss convergence speed | Helped |
| Use variance reduction instead of a minibatch estimator | ZOSPGD · Synthetic robust low-rank matrix recovery | loss convergence speed | Hurt |
| Use projection-free Frank–Wolfe updates instead of projected updates | ZOSFW · MovieLens 1M | loss convergence speed | Helped |
| Use variance reduction instead of a minibatch estimator | ZOSPGD · MovieLens 1M | loss convergence speed | Hurt |
Surprising findings
- VR-ZOSPGD converges slower than MB-ZOSPGD in experiments despite its better theoretical rate, attributed to expensive projections.
- Clarke-based approximate stationarity (generalized Clarke stationary points and ϵ-Clarke Frank–Wolfe points) admits no finite-time analysis for any algorithm.
Limitations
- Clarke-based stationarity criteria cannot be analyzed in finite time, so guarantees rely on δ>0 Goldstein relaxations.
- Oracle complexity O(d^{3/2} δ^{-1} ϵ^{-3}) for variance-reduced methods is left open for improvement.
- Experiments are limited to one robust low-rank matrix recovery problem and a single smoothing setup.
Experimental setup
Datasets: synthetic low-rank matrix MovieLens 1M
Benchmarks: synthetic low-rank matrix recovery (d=3000,4000,5000) MovieLens 1M
Metrics: loss vs processed time oracle complexity (FQO and LMO calls)
Baselines: MB-ZOSPGD VR-ZOSPGD MB-ZOSFW VR-ZOSFW
Builds on: Zhang et al. 2020 (Goldstein stationarity) Lin et al. 2022 (zeroth-order nonsmooth) Chen et al. 2023 (variance-reduced zeroth-order) Frank-Wolfe Projected gradient descent
Closest papers by meaning
- Zeroth-order (Non)-Convex Stochastic Optimization via Conditional Gradient and Gradient Updates (NeurIPS 2018 · similarity 0.91)
- Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.88)
- Barrier Algorithms for Constrained Non-Convex Optimization (ICML 2024 · similarity 0.87)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.87)
- First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.87)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 2025 · similarity 0.87)
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.