Research map / Optimization / Nonconvex and smooth optimization
Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional 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 zeroth-order (gradient-free) stochastic methods GFCOM and GFCOM+ for nonconvex nonsmooth stochastic compositional optimization, reaching (δ,ϵ)-Goldstein stationarity, plus a warm-started variant for convex nonsmooth SCO.
Problem
Stochastic compositional optimization where both outer and inner functions are Lipschitz but possibly nonconvex and nonsmooth, so gradient-based methods and Clarke stationarity criteria do not apply.
Approach
Combine randomized smoothing with two-point zeroth-order gradient estimators built from mini-batch estimates of the inner function at perturbed points, with optional variance reduction (recursive estimator) applied only to the outer function; a warm-start phase extends the method to convex nonsmooth SCO.
Key results
- GFCOM achieves O(d^3.5 δ^-3 ϵ^-6) zeroth-order oracle complexity and GFCOM+ improves this to O(d^3.5 δ^-3 ϵ^-5) for (δ,ϵ)-Goldstein stationarity in nonconvex nonsmooth SCO.
- WS-GFCOM+ achieves O(d^3 δ^-2.4 ϵ^-4 + d^3.5 δ^-2 ϵ^-5) for convex nonsmooth SCO.
- In experiments, GFCOM+ converges much faster than GFCOM and the Kiefer-Wolfowitz baseline on portfolio management and RL tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use variance reduction in the outer-function gradient estimator (GFCOM+ instead of GFCOM) | GFCOM · Nonconvex nonsmooth SCO | stochastic zeroth-order oracle complexity: O(d3.5δ−3ϵ−6) -> O(d3.5δ−3ϵ−5) | Helped |
| Add a warm-start phase before GFCOM+ | GFCOM+ · Convex nonsmooth SCO | stochastic zeroth-order oracle complexity: O(d3δ−2.4ϵ−4.8 + d3.5δ−2ϵ−6) -> O(d3δ−2.4ϵ−4 + d3.5δ−2ϵ−5) | Helped |
| Use GFCOM+ rather than GFCOM in the second phase of the warm-start method | WS-GFCOM · Convex nonsmooth SCO | stochastic zeroth-order oracle complexity: O(d3δ−2.4ϵ−4.8 + d3.5δ−2ϵ−6) -> O(d3δ−2.4ϵ−4 + d3.5δ−2ϵ−5) | Helped |
Surprising findings
- Variance reduction is applied only to the outer function; applying it to the inner function estimator does not vanish asymptotically in the zeroth-order setting.
Limitations
- Complexity bounds are polynomial with high exponents (d^3.5, ϵ^-5/ϵ^-6), and the authors leave lower bounds open.
- Convex extension requires convex and non-decreasing outer function and convex inner functions (Assumption 5.1).
- Code is not released at submission time.
Experimental setup
Datasets: 6 Fama-French portfolio datasets (Size and Operating Profitability) synthetic Markov decision processes with n in {400, 600, 800} states
Benchmarks: nonconvex penalized portfolio management (capped-l1) Bellman residual RL value evaluation
Metrics: loss vs. stochastic function calls
Baselines: Kiefer-Wolfowitz zeroth-order baseline
Builds on: Lin et al. randomized smoothing for nonsmooth zeroth-order optimization SCGD (Wang et al.) recursive variance reduction (SPIDER/SARAH-style) Zhang et al. interpolated normalized gradient descent
Closest papers by meaning
- Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization (NeurIPS 2025 · similarity 0.91)
- Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms (ICML 2024 · similarity 0.89)
- How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization? (NeurIPS 2024 · similarity 0.88)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.88)
- Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization (AAAI 2024 · similarity 0.87)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · 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.