{"id":"47496c66-5099-40a7-b3d8-ddc97a777358","arxiv_id":"2412.20330","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"Two zeroth-order methods, including a variance-reduced one-point estimator, are shown to converge to stationary points with sample complexity O(d^9/2 epsilon^-6) for nonconvex decision-dependent stochastic problems.","lead":"This paper proposes two optimization algorithms that work without gradient information when the randomness in a problem depends on the decision itself, as in pricing. The algorithms converge to stationary points under mild assumptions and perform well in retail pricing simulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4 misapplies Assumption 1 to past samples drawn from a different distribution; the missing L_x^2 term breaks Lemma 6 and hence Theorem 1's claimed sample complexity.","rationale":"Read in good faith: the paper addresses a meaningful problem and proposes a reasonable algorithmic framework; the Gaussian-homotopy schedule and reweighting of past samples are plausible. I verified the proof chain from Lemma 2 through Theorem 1. Lemma 2 and Lemma 3 are correct: the gradient estimator is unbiased, and the variance bound is valid because the sampling distribution and evaluation point coincide. The gap is in Lemma 4: the samples ξ_j^i were drawn from D(x_i+μ_i u_i), but are used to estimate F(x_k) via f(x_k,·). Assumption 1 bounds the variance of f(y,ξ) around F(y) when ξ~D(y); it says nothing about the variance of f(x,ξ) under D(y) for x≠y. By the L_x-Lipschitz property, that variance can be as large as (σ + 2L_x||x_k-y||)^2, so the bound in (6) is missing a term proportional to L_x^2||x_k-(x_i+μ_i u_i)||^2/m_i. Lemma 5's weights and Lemma 6's contraction rely on the exact form of (6); with the missing term, the coefficient of E[δ_{k-1}^2] in Lemma 6 is no longer guaranteed to be ≤1/2, e.g., when L_x > L_ξα and m_k is small. Theorem 1's proof immediately fails at this point. Theorem 2 does not use c_k and its proof appears unaffected, so the two-point method may stand independently; however, the paper's advertised improvement over G-dependent bounds for the one-point method is not established. The empirical section is secondary; the core issue is the proof error. The proposed concrete test (re-deriving the variance term and checking the recursion coefficient) would settle whether the paper can be patched by absorbing L_x into M or whether the complexity claim is wrong.","tokens_in":28005,"tokens_out":14308,"duration_ms":131302,"concrete_test":"Re-derive the variance term in Lemma 4 with y = x_i + μ_i u_i: compute Var_{ξ~D(y)}[f(x_k,ξ)] under Assumptions 1-3 and show it contains an additive L_x^2||x_k-y||^2 term rather than just σ^2. Substitute the corrected bound into the proof of Lemma 6 and recompute the coefficient multiplying E[δ_{k-1}^2] at β = μ_min/(2L_ξα√6d) with m_k=1. If the coefficient is not ≤1/2, the Lemma 6 claim fails. As a numerical check, run Algorithm 1 on d=1, D(x)=N(αx,1), f(x,ξ)=sin(x-ξ) with L_x > L_ξα and measure E[δ_k^2] over iterations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central convergence proof rests on Lemma 4 (Appendix B.4), which bounds (F(x_k)-c_k)^2 by (6). In the variance term, the proof bounds E[(E_{D(x_i+μ_i u_i)}[f(x_k,ξ)] - (1/m_i)Σ_j f(x_k,ξ_j^i))^2] by σ^2/m_i using Assumption 1 and Lemma B.6. But Assumption 1 only controls Var_{ξ~D(y)}[f(y,ξ)]; it does not control Var_{ξ~D(y)}[f(x,ξ)] when x≠y. The correct variance contains an additive L_x^2||x_k-(x_i+μ_i u_i)||^2 term (plus a cross term), because f is L_x-Lipschitz in its first argument. Lemma 5's optimal weights and Lemma 6's contraction factor 1/2 depend on the exact form (6). Inserting the missing L_x^2 term changes the coefficient multiplying δ_{k-1}^2 in Lemma 6; under the stated step-size condition β ≤ μ_min/(2L_ξα√6d), this coefficient can exceed 1/2 (e.g., when L_x > L_ξα and m_k=1). Without a corrected Lemma 4, the iteration/sample complexity O(d^{5/2}ε^{-4}) / O(d^{9/2}ε^{-6}) in Theorem 1 is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28302,"tokens_out":20601,"duration_ms":207965,"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":[{"comment":"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.","section":"Appendix B.4, Lemma 4 (Eq. (6))"},{"comment":"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.","section":"Appendix B.6, Lemma 6"},{"comment":"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.","section":"Section 4.3, Theorem 1 and Algorithm 1 line 7"}],"minor_comments":[{"comment":"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.","section":"Sections 1 and 4, notation"},{"comment":"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.","section":"Equations (5) and Algorithm 1 line 8"},{"comment":"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.","section":"Lemma 5"}],"recommendation":"major_revision","confidential_remarks":"The Lemma 4 issue is real and load-bearing: Theorem 1 is unproven as submitted. I nevertheless recommend major revision rather than rejection because the gap appears repairable within the paper's scope: adding an L_x^2 distance term to Lemma 4 and adjusting M and \\beta accordingly should preserve the stated complexity exponents. Please ask the authors to supply a corrected Lemma 4, a corrected Lemma 6, and a revised Algorithm 1/Theorem 1 parameter specification. The two-point method and the experimental section are less affected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has a genuinely new idea: a one-point zeroth-order estimator with an online control variate c_k, updated from past samples, that avoids the G-dependence in earlier one-point methods (Ray, Liu). That is worth something. The two-point estimator is a more direct extension of existing analysis, but putting it under milder assumptions than Chen et al. is also useful. The experiments on retail pricing are sane, though limited.\n\nThe problem is Lemma 4. It bounds (F(x_k)-c_k)^2 by a sum of a^2_i (L_xi^2 alpha^2 ||x_k - x_i - mu_i u_i||^2 + sigma^2/m_i). The sigma^2/m_i term comes from applying Assumption 1 and Lemma B.6 to samples xi_j^i ~ D(x_i + mu_i u_i) evaluated at f(x_k, ·). But Assumption 1 only controls the variance of f(y, ξ) when ξ ~ D(y). For x_k ≠ y, you get an extra L_x^2 ||x_k - y||^2 term (plus cross terms) because f is L_x-Lipschitz in x. That missing term changes the optimal weights in Lemma 5 and the contraction factor in Lemma 6. The stress-test note is right: under the stated step-size condition, the coefficient on E[delta_{k-1}^2] can exceed 1/2, so the recursion and the O(d^{9/2} epsilon^{-6}) sample complexity in Theorem 1 are not established.\n\nThis is load-bearing, not a minor typo. The central claim of the paper depends on it. The two-point algorithm (Theorem 2) does not use c_k and may be salvageable more easily—its proof is standard—but the paper's headline contribution is the one-point method.\n\nThe experiments also have a soft spot: no two-point baseline (CZO-2) is compared, and hyperparameters were tuned on the same test setting, which inflates the apparent advantage. That said, the empirical gap over CZO-1 is large enough that something real is happening, likely due to variance reduction.\n\nThe paper is clearly written, the related work is fair, and the authors ship code. The flaw is an honest technical mistake, not hand-waving. I would not accept the current proofs, but I would send this to peer review: the variance-reduction mechanism is novel enough that a serious referee should engage, and a correction of Lemma 4 might lead to slightly worse constants or an extra term that still yields the same complexity—or it might reveal a genuine obstacle. In either case, the paper deserves a careful look and a revision path.","headline":"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.","tokens_in":28826,"tokens_out":2137,"would_cite":false,"duration_ms":23118,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C26","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["zeroth-order optimization","decision-dependent distributions","nonconvex optimization","Gaussian smoothing","variance reduction","sample complexity","stationary points","performative prediction"],"falsifier":"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.","tokens_in":27783,"feed_emoji":"🎯","tokens_out":9701,"duration_ms":88780,"temperature":0.7,"pith_summary":"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.","feed_headline":"Derivative-free methods reach stationary points without bounding f","feed_subtitle":"Variance-reduced one-point and two-point estimators reach stationary points with O(d^{4.5} ε^{-6}) samples.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the one-point zeroth-order estimator and assumptions that the paper's Assumptions 1–4 generalize; its Lemma 1 gives a smoothness sufficient condition and it serves as a baseline.","marker":"[Ray et al., 2022]"},{"why":"Analyzes zeroth-order methods with the one-point estimator for nonconvex decision-dependent problems; its $O(G^6 d^2\\varepsilon^{-6})$ sample complexity is the bound the paper improves to be $G$-independent.","marker":"[Liu et al., 2024]"},{"why":"Prior two-point zeroth-order method restricted to an exponential-family distribution and an auxiliary inequality; the paper's Theorem 2 removes those restrictions.","marker":"[Chen et al., 2023]"},{"why":"Supplies the Gaussian smoothing identities and variance estimates for randomized gradient estimators used in Lemmas 2, 3, 7, and 8.","marker":"[Nesterov and Spokoiny, 2017]"},{"why":"Source of the Gaussian homotopy technique and of the smoothing properties (Lemmas B.4 and B.5) that control the annealing schedule.","marker":"[Iwakiri et al., 2022]"},{"why":"Provides the distribution-shift bounds and the idea of estimating $F(x)$ from past samples, used in Lemma 4 and in the construction of $c_k$.","marker":"[Jagadeesan et al., 2022]"},{"why":"Gives the sample-mean variance inequality (Lemma B.6) used in the variance bounds.","marker":"[Freund and Walpole, 1986]"}],"fun_headline_variants":["Variance-reduced derivative-free methods for nonconvex decision-dependent problems","One-point and two-point estimators tame stochastic nonconvex optimization","Derivative-free algorithms reach stationary points without gradient information","Variance-reduced zeroth-order methods for nonconvex stochastic problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Variance-reduced derivative-free methods for nonconvex decision-dependent problems","One-point and two-point estimators tame stochastic nonconvex optimization","Derivative-free algorithms reach stationary points without gradient information","Variance-reduced zeroth-order methods for nonconvex stochastic problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001962,"raw_usage":{"total_tokens":7726,"prompt_tokens":1064,"completion_tokens":6662,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":6589}},"tokens_in":680,"tokens_out":6662,"duration_ms":47498,"temperature":1.0,"reasoning_tokens":6589,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:24:09.465113+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}