Pith. sign in

REVIEW 3 major objections 3 minor 30 references

Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions

T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that two zeroth-order methods—one with a variance-reduced one-point gradient estimator and one with a two-point gradient estimator—converge to stationary points of decision-dependent stochastic optimization problems, with…

desk verdict Clever variance-reduced one-point estimator for decision-dependent problems, but the main convergence theorem rests on a lemma that misapplies Assumption 1, so the claimed complexities are not established as written. read the letter →

arxiv 2412.20330 v1 pith:CQRFAYCZ submitted 2024-12-29 math.OC cs.LG

Yuya Hikima , Akiko Takeda This is my paper · ORCID
classification math.OCcs.LG MSC 90C1590C2690C56
keywords zeroth-orderoptimizationdecision-dependentdistributionsnonconvexGaussiansmoothingvariancereductionsamplecomplexitystationarypointsperformativeprediction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies minimizing $F(x)=\mathbb{E}_{\xi\sim D(x)}[f(x,\xi)]$ over $x\in\mathbb{R}^d$, where the distribution $D(x)$ itself depends on the decision variable, so the gradient of $F$ cannot be computed or estimated directly. It proposes two zeroth-order methods—meaning methods that use only noisy function values—and claims both converge to stationary points under mild Lipschitz, smoothness, and conditional-variance assumptions. The first method uses a one-point gradient estimator with an adaptively chosen shift parameter $c_k$ that reduces estimator variance, and the second uses a two-point estimator. Under the paper's assumptions, after $O(d^{5/2}\varepsilon^{-4})$ iterations and $O(d^{9/2}\varepsilon^{-6})$ samples the output satisfies $\mathbb{E}[\|\nabla F(\hat{x})\|^2]\le \varepsilon^2$. The key advantage over earlier one-point methods is that this sample complexity does not involve $G=\sup_{x,\xi}|f(x,\xi)|$, which is often large or unbounded.

What carries the argument

The central objects are the Gaussian smoothed function $F_\mu(x)=\mathbb{E}_{u\sim \mathcal{N}(0,I_d)}[F(x+\mu u)]$ and two gradient estimators built from noisy function values: $g_1=\frac{1}{\mu}(f(x+\mu u,\xi)-c)u$ with $\xi\sim D(x+\mu u)$, and $g_2=\frac{1}{2\mu}(f(x+\mu u,\xi_1)-f(x-\mu u,\xi_2))u$ with $\xi_1,\xi_2$ drawn from the two shifted distributions. Lemmas 2 and 7 establish that both estimators are unbiased for $\nabla F_\mu(x)$, and Lemmas 3 and 8 bound the estimator variance in terms of $d$, $\mu$, $\sigma^2$, and, for $g_1$, the gap $(F(x)-c)^2$. That gap is controlled by updating $c_k$ as a weighted average of past samples whose weights are the solution of a small convex problem (Lemma 5), so the variance reduction does not require extra samples. The annealing schedule $\mu_{k+1}=\max(\gamma\mu_k,\mu_{\min})$ connects the smoothed problem to the original one, and Lemma 6 keeps the estimation error $\delta_k=F(x_k)-c_k$ uniformly bounded.

What would settle it

Compute the quantity in Lemma 4 for $f(x,\xi)=\langle x,\xi\rangle$ and $D(x)$ a Gaussian centered at $x$, taking $x_k$ far from $x_i+\mu_i u_i$: the gap between $F(x_k)$ and the average of $f(x_k,\xi)$ over past samples is of order $L_x\|x_k-(x_i+\mu_i u_i)\|$, so inequality (6) fails unless the missing $L_x^2$ term is added.

Watch

Extended reading notes

Core claim

The paper's central claim, stated in Theorems 1 and 2, is that Algorithms 1 and 2 achieve $\mathbb{E}[\|\nabla F(\hat{x})\|^2]\le \varepsilon^2$ for the nonconvex objective $F(x)=\mathbb{E}_{\xi\sim D(x)}[f(x,\xi)]$ under Assumptions 1–4: a uniform bound on the variance of $f(x,\xi)$ around $F(x)$, a Wasserstein-1 Lipschitz condition on $D(x)$, Lipschitz continuity of $f$ in both arguments, and smoothness of $F$. The estimators are unbiased for the gradient of the Gaussian smoothed function $F_\mu(x)$, and the variance-reduction parameter $c_k$ is set by averaging past samples with weights chosen to balance distribution shift against sampling noise. Both methods anneal the smoothing radius $\mu_k$ from large to small, a Gaussian-homotopy technique intended to reach better stationary points. The resulting iteration complexity $O(d^{5/2}\varepsilon^{-4})$ and sample complexity $O(d^{9/2}\varepsilon^{-6})$ are independent of $G=\sup|f|$, improving on the existing one-point zeroth-order bound $O(G^6 d^2\varepsilon^{-6})$ when $G$ is large.

Load-bearing premise

The proof of Lemma 4 in Appendix B.4 assumes that the variance bound $\sigma^2$ holding for samples from $D(x_k)$ also applies to samples drawn earlier from $D(x_i+\mu_i u_i)$ and evaluated at $f(x_k,\cdot)$; without an added $L_x^2\|x_k-(x_i+\mu_i u_i)\|^2$ term, this estimate can fail.

Editorial extensions

If this is right

  • If Theorems 1 and 2 are correct, zeroth-order methods can find stationary points of decision-dependent stochastic problems using only noisy function evaluations, with no need to know or estimate the gradient of the unknown distribution $D(x)$.
  • The sample complexity does not depend on $G=\sup_{x,\xi}|f(x,\xi)|$, so the methods remain usable when the objective is unbounded, where existing one-point zeroth-order methods with $O(G^6 d^2\varepsilon^{-6})$ complexity lose their guarantee.
  • The two-point method works under the same mild assumptions, without the exponential-family restriction and auxiliary inequality required by the earlier two-point approach.
  • The one-point method is available in settings where sampling from the same environment twice is impossible, such as time-varying distributions, and still benefits from variance reduction.
  • On a multiproduct pricing task with real retail data, both proposed methods produce lower objective values than the conventional zeroth-order baselines within the tested sample budget.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The strategy of reusing past samples to estimate the current function value could extend to time-varying or slowly drifting distributions, provided the weighting scheme accounts for the drift rate.
  • The $d$-dependence $O(d^{9/2})$ suggests high-dimensional problems remain expensive, so combining the estimators with coordinate-wise or sparse-update schemes is a natural next step.
  • The two-point estimator's variance bound halves the sampling-noise term relative to the one-point estimator, which may explain the better practical performance observed in the pricing experiments.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the nonconvex stochastic optimization problem min_x F(x)=E_{\xi\sim D(x)}[f(x,\xi)] where the sampling distribution depends on the decision variable and is unknown. It proposes two zeroth-order methods: Algorithm 1, which uses a one-point gradient estimator with a variance-reduction parameter c_k estimated from past samples, and Algorithm 2, which uses a two-point estimator. Under Assumptions 1--4 (bounded conditional variance, Wasserstein-Lipschitz distribution map, Lipschitz f, and smooth F), Theorems 1 and 2 claim convergence to a stationary point with iteration complexity O(d^{5/2}\varepsilon^{-4}) and sample complexity O(d^{9/2}\varepsilon^{-6}), with no dependence on G=\sup_{x,\xi}|f(x,\xi)|. Experiments on a synthetic retail-pricing problem with real supermarket data report lower objective values than the conventional one-point zeroth-order baseline.

Significance. If correct, the paper would remove the boundedness/G assumption that limits existing one-point zeroth-order analyses for decision-dependent distributions, and it would extend two-point zeroth-order methods beyond the special distribution families assumed by Chen et al. The variance-reduction idea of reweighting past samples is sensible, and the two-point method's proof appears to be independent of the flawed lemma discussed below. The paper also provides a public code link and a reproducible experimental setup, which are commendable. However, the central convergence theorem for the one-point method rests on Lemma 4, whose proof is invalid as written; consequently the claimed Theorem 1 is not established in the submitted manuscript.

major comments (3)
  1. [Appendix B.4, Lemma 4 (Eq. (6))] Lemma 4's proof bounds the second term by \sigma^2/m_i using Assumption 1 and Lemma B.6. Those results control the variance of f(y,\xi) when \xi\sim D(y), but the term in question is the variance of f(x_k,\xi) when \xi\sim D(x_i+\mu_i u_i), with x_k generally different from x_i+\mu_i u_i. Because f is only L_x-Lipschitz in its first argument, the correct bound contains an additional O(L_x^2\|x_k-(x_i+\mu_i u_i)\|^2) term, up to absolute constants and possibly a cross term. Thus inequality (6) is not a consequence of Assumptions 1--3, and Lemma 4 is false as stated.
  2. [Appendix B.6, Lemma 6] Lemma 6 is the direct downstream consequence of Lemma 4. After choosing \theta_{k-1}=1 in Lemma 6's proof, the recursion for E[\delta_k^2] has coefficient 12L_\xi^2\alpha^2\beta^2 d/\mu_{\min}^2 multiplying E[\delta_{k-1}^2]. With the missing L_x^2 term from Lemma 4, the coefficient becomes 12(L_\xi^2\alpha^2+L_x^2)\beta^2 d/\mu_{\min}^2. The stated condition \beta\le\mu_{\min}/(2L_\xi\alpha\sqrt{6d}) is insufficient to keep this coefficient at most 1/2 when L_x is comparable to or larger than L_\xi\alpha. Therefore the contraction estimate in Lemma 6, and with it the step-size and parameter choices used in Theorem 1, are not established.
  3. [Section 4.3, Theorem 1 and Algorithm 1 line 7] A repair of the proof would require modifying Lemma 4 and Lemma 5 so that the optimal weights include the L_x^2 term, changing line 7 of Algorithm 1 from M=L_\xi^2\alpha^2/\sigma^2 to a value involving L_\xi^2\alpha^2+L_x^2, and replacing the step-size bound in Theorem 1 by a condition involving \sqrt{L_\xi^2\alpha^2+L_x^2}. As written, Algorithm 1 and Theorem 1 use M and \beta that depend only on L_\xi\alpha, so the claimed convergence of the one-point method is not supported by the proof. The two-point method in Theorem 2 does not rely on Lemma 4 and appears unaffected by this issue.
minor comments (3)
  1. [Sections 1 and 4, notation] The introduction writes the random direction as a uniform unit vector v_k, while the main body and Algorithm 1 use u_k\sim N(0,I_d); the two conventions should be reconciled to avoid a hidden factor of d in the estimators.
  2. [Equations (5) and Algorithm 1 line 8] The definition of c_k in (5) uses iterations k-s,\ldots,k-1, while Algorithm 1 computes c_{k+1} from iterations k-s+1,\ldots,k; the index shift is correct but should be stated explicitly for readability.
  3. [Lemma 5] Lemma 5 silently drops the constant factor 2 appearing in Lemma 4; this is harmless for the minimizer, but a one-sentence remark would help the reader connect the optimal weights to line 7 of Algorithm 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence and complexity claims are derived self-contained from Assumptions 1–4 using standard smoothing lemmas; self-citations are not load-bearing.

full rationale

The paper's central claims (Theorems 1 and 2) are derived from Assumptions 1–4 through a self-contained chain: Lemmas 2–3 bound the one-point and two-point estimator moments under these assumptions; Lemma 4 bounds the variance-reduction error using Assumptions 1–3 and standard concentration inequalities; Lemma 5 gives closed-form optimal weights; Lemma 6 combines these with a step-size condition to obtain a contraction for the estimation error; Theorem 1 then combines the smoothing descent inequality with Lemmas 3, 6, and standard Gaussian smoothing lemmas. The variance reduction parameter c_k is estimated from past samples using the algorithm's own f-queries, but it is not fitted to the target convergence quantity: Lemma 6 explicitly bounds the estimation error δ_k = F(x_k) - c_k in terms of step size, smoothing parameters, and sample sizes, and this bound is then used in the final complexity calculation. No prediction in the paper is statistically forced by a fitted parameter renamed as a result, and no central premise reduces to an equation of the paper's own making. The self-citations (Iwakiri et al. 2022 for Gaussian homotopy and Lemmas B.4–B.5; Hikima and Takeda 2023 for an alternative stochastic-gradient setting) are not load-bearing: the Gaussian smoothing lemmas are standard and stated with explicit assumptions not including the target result, and the cited prior work is not used to exclude alternative derivations or to justify uniqueness. The reader-identified issue in Lemma 4 (the variance term for past samples drawn from D(x_i + μ_i u_i) but evaluated at f(x_k,·) may require an additional L_x^2 term) is a possible mathematical correctness gap in the proof, not a circularity: it concerns whether Assumption 1 is applied outside its domain, not whether an output is equivalent to an input. Therefore the circularity score is 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The theoretical claim rests on four domain assumptions about the objective and distribution, plus standard smoothing inequalities. The critical weakness is that Lemma 4's proof relies on Assumption 1 beyond its stated scope, introducing an unaccounted dependence on L_x and the distribution shift. No new entities are postulated.

free parameters (1)
  • Hyperparameters of Algorithms 1 and 2 (mu0, mumin, beta, gamma, m_k, M, smax, c0) = Tuned in experiments; in theory set via Theta notation from sigma, alpha, H_F, etc.
    These numbers are chosen by the user or tuned on the same problem instances in the experiments (Appendix A.3). They do not affect the theoretical result if set according to known constants, but in practice they are free.
assumptions (5)
  • domain assumption Assumption 1: E_{xi~D(x)}[(F(x)-f(x,xi))^2] <= sigma^2 for all x.
    Used in Lemma 3 to bound the sampling noise in the gradient estimator; also implicitly in Lemma 4, where it is misapplied to shifted distributions.
  • domain assumption Assumption 2: W(D(x),D(x')) <= alpha ||x-x'|| for all x,x'.
    Controls distribution shift under decision changes; used in Lemma 4 and Lemma B.2.
  • domain assumption Assumption 3: f(x,xi) is L_xi-Lipschitz in xi and L_x-Lipschitz in x.
    Needed for Lipschitz properties of F and for bounding variance of f under distribution shift; L_x is conspicuously absent from Lemma 4's bound.
  • domain assumption Assumption 4: F(x) is H_F-smooth.
    Standard smoothness for convergence to stationary points; also used in Gaussian smoothing bounds.
  • standard math Lemma B.8 (Nesterov-Spokoiny inequality for one-point smoothing).
    Cited from prior literature and used to bound the deterministic part of the gradient estimator variance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions." pith.science (2026). https://pith.science/paper/CQRFAYCZ

@misc{pith2026241220330,
  author       = {Pith},
  title        = {Pith review of: Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQRFAYCZ}},
  note         = {Machine review of arXiv:2412.20330}
}
read the original abstract

In this study, we consider an optimization problem with uncertainty dependent on decision variables, which has recently attracted attention due to its importance in machine learning and pricing applications. In this problem, the gradient of the objective function cannot be obtained explicitly because the decision-dependent distribution is unknown. Therefore, several zeroth-order methods have been proposed, which obtain noisy objective values by sampling and update the iterates. Although these existing methods have theoretical convergence for optimization problems with decision-dependent uncertainty, they require strong assumptions about the function and distribution or exhibit large variances in their gradient estimators. To overcome these issues, we propose two zeroth-order methods under mild assumptions. First, we develop a zeroth-order method with a new one-point gradient estimator including a variance reduction parameter. The proposed method updates the decision variables while adjusting the variance reduction parameter. Second, we develop a zeroth-order method with a two-point gradient estimator. There are situations where only one-point estimators can be used, but if both one-point and two-point estimators are available, it is more practical to use the two-point estimator. As theoretical results, we show the convergence of our methods to stationary points and provide the worst-case iteration and sample complexity analysis. Our simulation experiments with real data on a retail service application show that our methods output solutions with lower objective values than the conventional zeroth-order methods.

Figures

Figures reproduced from arXiv: 2412.20330 by the authors.

Figure 1
Figure 1. Change in obj in the first 3000 samples in the simulation experiment with real data. Each graph shows the result in one problem instance for each week. The horizontal axis indicates the number of samples, and the vertical axis indicates obj. provided the worst-case iteration and sample complexity analysis. Our simulation experiments with real data on a retail service application showed good performance of our method… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 24 canonical work pages

  1. [1]

    Basciftci, S

    B. Basciftci, S. Ahmed, and S. Shen. Distributionally robust facility location problem under decision-dependent stochastic demand. European Journal of Operational Research, 292 0 (2): 0 548--561, 2021

    work page 2021

  2. [2]

    Brochu, V

    E. Brochu, V. M. Cora, and N. De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv:1012.2599., 2010

    arXiv 2010

  3. [3]

    H. Cai, D. McKenzie, W. Yin, and Z. Zhang. Zeroth-order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Optimization, 32 0 (2): 0 687--714, 2022

    work page 2022

  4. [4]

    Y. Chen, W. Tang, C.-J. Ho, and Y. Liu. Performative prediction with bandit feedback: Learning through reparameterization. arXiv preprint arXiv:2305.01094, 2023

    arXiv 2023

  5. [5]

    P. I. Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811., 2018

    arXiv 2018

  6. [6]

    J. E. Freund and R. E. Walpole. Mathematical statistics. Prentice-Hall, Inc., 1986

    work page 1986

  7. [7]

    Gallego and R

    G. Gallego and R. Wang. Multiproduct price optimization and competition under the nested logit model with product-differentiated price sensitivities. Operations Research, 62 0 (2): 0 450--461, 2014

    work page 2014

  8. [8]

    Ghadimi and G

    S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23 0 (4): 0 2341--2368, 2013

    2013

Show all 30 references
  1. [9]

    Hazan, K

    E. Hazan, K. Y. Levy, and S. Shalev-Shwartz. On graduated optimization for stochastic non-convex problems. In International Conference on Machine Learning, pages 1833--1841, 2016

    2016

  2. [10]

    Hikima and A

    Y. Hikima and A. Takeda. Stochastic approach for price optimization problems with decision-dependent uncertainty. arXiv preprint arXiv:2307.00492 (to appear in European Journal of Operational Research), 2023

    2023 arXiv

  3. [11]

    Ito and R

    S. Ito and R. Fujimaki. Large-scale price optimization via network flow. Advances in Neural Information Processing Systems, 29: 0 3862--3870, 2016

    2016

  4. [12]

    Iwakiri, Y

    H. Iwakiri, Y. Wang, S. Ito, and A. Takeda. Single loop gaussian homotopy method for non-convex optimization. Advances in Neural Information Processing Systems, 35: 0 7065--7076, 2022

    2022

  5. [13]

    Jagadeesan, T

    M. Jagadeesan, T. Zrnic, and C. Mendler-D \"u nner. Regret minimization with performative feedback. In International Conference on Machine Learning, pages 9760--9785, 2022

    2022

  6. [14]

    K. Ji, Z. Wang, Y. Zhou, and Y. Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International Conference on Machine Learning, pages 3100--3109, 2019

    2019

  7. [15]

    Johnson and T

    R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26: 0 315–323, 2013

    2013

  8. [16]

    H. Liu, Q. Li, and H. T. Wai. Two-timescale derivative free optimization for performative prediction with M arkovian data. In International Conference on Machine Learning, pages 31425--31450, 2024

    2024

  9. [17]

    S. Liu, B. Kailkhura, P.-Y. Chen, P. Ting, S. Chang, and L. Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31: 0 3731–3741, 2018

    2018

  10. [18]

    Luo and S

    F. Luo and S. Mehrotra. Distributionally robust optimization with decision dependent ambiguity sets. Optimization Letters, 14: 0 2565--2594, 2020

    2020

  11. [19]

    Mendler-D \"u nner, J

    C. Mendler-D \"u nner, J. Perdomo, T. Zrnic, and M. Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33: 0 4929--4939, 2020

    2020

  12. [20]

    J. P. Miller, J. C. Perdomo, and T. Zrnic. Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning, pages 7710--7720, 2021

    2021

  13. [21]

    Mobahi and J

    H. Mobahi and J. W. Fisher. On the link between gaussian homotopy continuation and convex envelopes. In Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 43--56, 2015

    2015

  14. [22]

    Mobahi and J

    H. Mobahi and J. Fisher III. A theoretical analysis of optimization by gaussian continuation. In AAAI Conference on Artificial Intelligence, pages 1205--1211, 2015

    2015

  15. [23]

    Nesterov and V

    Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17 0 (2): 0 527--566, 2017

    2017

  16. [24]

    J. Ou. Improved exact algorithms to economic lot-sizing with piecewise linear production costs. European Journal of Operational Research, 256 0 (3): 0 777--784, 2017

    2017

  17. [25]

    Perdomo, T

    J. Perdomo, T. Zrnic, C. Mendler-D \"u nner, and M. Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599--7609, 2020

    2020

  18. [26]

    M. Ray, L. J. Ratliff, D. Drusvyatskiy, and M. Fazel. Decision-dependent risk minimization in geometrically decaying dynamic environments. In AAAI Conference on Artificial Intelligence, pages 8081--8088, 2022

    2022

  19. [27]

    D. X. Shaw and A. P. Wagelmans. An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs. Management Science, 44 0 (6): 0 831--838, 1998

    1998

  20. [28]

    R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018

    2018

  21. [29]

    H. Tunc, O. A. Kilic, S. A. Tarim, and B. Eksioglu. The stochastic lot sizing problem with piecewise linear concave ordering costs. Computers & Operations Research, 65: 0 104--110, 2016

    2016

  22. [30]

    Y. Wang, S. Du, S. Balakrishnan, and A. Singh. Stochastic zeroth-order optimization in high dimensions. In International Conference on Artificial Intelligence and Statistics, pages 1356--1365, 2018

    2018

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.