Research map / Optimization / Nonconvex and smooth optimization
Zeroth-Order Methods for Nonconvex Stochastic 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 two zeroth-order methods for nonconvex stochastic problems with decision-dependent distributions: a one-point estimator with an adaptively updated variance-reduction baseline c_k, and a two-point Gaussian-smoothed estimator, both with Gaussian homotopy, evaluated on a multiproduct pricing task with real retail data.
Problem
Minimizing an expected objective whose sampling distribution depends on the decision variable, when the distribution is unknown so gradients cannot be computed directly, under mild assumptions and non-convexity.
Approach
A one-point Gaussian-smoothed gradient estimator with a variance-reduction baseline c_k built from past iterations' samples (weighted by closed-form optimal weights), plus a two-point estimator that avoids strong convexity and bounded-objective assumptions; both are combined with Gaussian homotopy.
Key results
- Proposed-1 (mini-batch) reaches average obj of -7.39 on week 02/21--02/27 versus 2.83 for CZO-1 (mini-batch), and all proposed methods beat CZO-1 across the eight weeks.
- Proposed-2 (mini-batch) achieves the best average objective in 4 of 8 weeks, e.g. -7.78 in week 03/21--03/27 versus 4.08 for CZO-1 (batch size 1).
- Theoretical sample complexity is O(d^{9/2} eps^{-6}) for both methods, versus O(G^6 d^2 eps^{-6}) for the existing one-point method.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed one-point estimator with variance-reduction parameter c instead of conventional one-point CZO-1 | Zeroth-order pricing optimization · Multiproduct pricing, all reported weeks | obj: -7.39 vs 1.83; -7.61 vs 2.41 | Helped |
| use the proposed two-point estimator instead of conventional one-point CZO-1 | Zeroth-order pricing optimization · Multiproduct pricing, all reported weeks | obj: -7.26 vs 1.83; -7.78 vs 2.41 | Helped |
| use the two-point estimator instead of the one-point estimator with variance reduction | Proposed zeroth-order method · Multiproduct pricing, different weeks | obj: -7.39 vs -7.26; -7.61 vs -7.78 | Mixed |
| use batch size 1 instead of mini-batch (ablation) | Proposed-1 · Multiproduct pricing, different weeks | obj: -7.39 -> -2.62; -5.28 -> -1.89 | Hurt |
| use batch size 1 instead of mini-batch (ablation) | Proposed-2 · Multiproduct pricing, different weeks | obj: -7.26 -> -6.62; -6.38 -> -5.35 | Hurt |
Surprising findings
- The two-point estimator performs better than the one-point variant in experiments even though both have the same worst-case sample complexity.
- The proposed one-point method with batch size 1 performs worse than CZO-1 on several weeks, indicating the benefit depends on mini-batching.
Limitations
- Only stationary-point convergence is guaranteed, since the problem is non-convex under the looser assumptions.
- Requires knowing smoothness/Wasserstein constants sigma and alpha to set parameters, which may be unknown in practice.
- Experiments are limited to a single simulated pricing application with a synthetic buyer choice model.
Experimental setup
Datasets: New Product Sales Ranking (KSP-SP Co., Ltd) retail data
Benchmarks: multiproduct pricing simulation with real retail data
Metrics: objective value (revenue-based cost) standard deviation over 20 random instances
Baselines: CZO-1 (conventional one-point zeroth-order method)
Builds on: zeroth-order gradient estimation via Gaussian smoothing Gaussian homotopy conventional one-point zeroth-order method for performative prediction
Closest papers by meaning
- Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions (ICML 2025 · similarity 0.91)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.86)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.85)
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.85)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.84)
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.