Research map / Optimization / Nonconvex and smooth optimization
Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
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 guided zeroth-order methods for performative prediction that shape Gaussian perturbation covariance using the known gradient term of f, with new or historical samples, achieving O(σ³d⁴ε⁻⁶) sample complexity.
Problem
Stochastic non-convex optimization where the data distribution D(x) depends on the decision x and is unknown (performative prediction), so gradients must be estimated by zeroth-order methods that ignore the known structure of f.
Approach
Set the Gaussian sampling covariance as a mix of isotropic and the outer product of a partial gradient estimate ∇xf averaged over samples, so zeroth-order update directions tend to decrease the objective; a schedule increases the isotropic weight over time. A variant reuses historical samples to avoid extra sampling.
Key results
- On multiproduct pricing across five weeks of data, GZO-NS and GZO-HS reach objective values around -12.5 to -15.7 versus about -10.3 to -10.9 for ZO-TG in several weeks, with significant differences (p<0.05) in most settings.
- On strategic classification, GZO-NS achieves training loss 0.83-0.88 versus 1.21-1.35 for ZO-TG across tau values.
- Theoretical worst-case sample complexity is O(σ³d⁴ε⁻⁶), improving on O(σ³d^{9/2}ε⁻⁶) of Hikima & Takeda 2025b and O(G⁶d²ε⁻⁶) of Liu et al. 2024a when G is large.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use function-gradient information to guide two-point zeroth-order update directions (GZO-NS) | Two-point zeroth-order optimization · Multiproduct pricing | obj: -10.92 -> -12.53 | Helped |
| Use historical samples to guide two-point zeroth-order update directions (GZO-HS) | Two-point zeroth-order optimization · Multiproduct pricing | obj: -10.92 -> -12.85 | Helped |
| Use function-gradient information to guide update directions (GZO-NS) | Two-point zeroth-order optimization · Strategic classification, τ=0.5 | train loss: 1.21 -> 0.87 | Helped |
| Use historical samples to guide update directions (GZO-HS) | Two-point zeroth-order optimization · Strategic classification, τ=0.5 | train loss: 1.21 -> 0.83 | Helped |
| Use historical samples rather than new samples for partial-gradient information | Guided zeroth-order method · Multiproduct pricing | obj: -12.53 -> -12.85; -9.06 -> -9.52 | Mixed |
Surprising findings
- On the pricing task, GZO-HS was not significantly better than ZO-TG for the 7/18-7/24 week, while GZO-NS remained significantly better.
Limitations
- Strategic classification setting violates the smoothness (Assumption 4.3) required by the theory, per the authors' remark.
- Requires knowledge of smoothness constant H_F for parameter setting, which may be unknown in practice.
- Balance parameter alpha and historical window p are set heuristically; no principled tuning method is provided.
Experimental setup
Datasets: New Product Sales Ranking (KSP-SP, Japan supermarket retail data) Taiwan credit card default dataset (Yeh & hui Lien, 2009)
Benchmarks: multiproduct pricing simulation (20 instances) strategic classification on credit-card default data
Metrics: objective value training loss test loss test AUC test accuracy
Baselines: ZO-TG ZO-OG ZO-OGVR Ray et al. 2022 one-point method Liu et al. 2024a DFO
Builds on: Gaussian smoothing zeroth-order methods (Nesterov & Spokoiny) Maheswaranathan et al. 2019 guided evolution strategies zeroth-order methods for decision-dependent distributions (Hikima & Takeda 2025b Ray et al. 2022 Liu et al. 2024a
Closest papers by meaning
- Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions (AAAI 2025 · similarity 0.91)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.88)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.87)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.87)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 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.