{"id":"559eedfc-36d5-4e86-8a70-df3280b26505","arxiv_id":"2506.20546","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A coordinate extra-gradient method for black-box constrained convex optimization attains O(d/ε) oracle complexity, the best known in this setting.","lead":"The paper proposes two zeroth-order extra-gradient algorithms for constrained optimization when objective and constraints are black boxes, achieving oracle complexities O(d/ε²) and O(d/ε). The improved complexity could cut the number of simulations or function evaluations needed for systems like power grids and simulation-based design.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Finite-difference estimators at boundary points leave the assumed smoothness region; Lemma 2.1, and hence the O(d/ε) claim, is not justified as stated.","rationale":"The central claim — O(d/ε) oracle complexity for ZOCEG — rests on Lemmas 2.1 and 4.1. Those lemmas use finite-difference estimators at points z + r e_i, where z is an iterate in the compact set Z. Because Z is compact, iterates can sit on the boundary, so the queried point leaves Z. Assumption 2.2 bounds smoothness only on Z, making the mean-value integral in the proof of Lemma 2.1 invalid. This is an internal inconsistency between the algorithm's queries and the theorem's hypotheses, not a disagreement with community consensus. A concrete 1D oracle satisfying all stated assumptions makes the estimator error at x = 1 as large as A√r, violating the claimed ½Lr bound. The same defect appears in Lemma 3.1 and Theorem 4.3, so the proofs are not sound as written. The repair is small — assume L-smoothness on a fixed neighborhood of Z — and with that repair the convergence algebra appears to work, so the result is plausibly correct. The reader's secondary concern about R = 0 in the constraint-violation bound is also real and patchable, but it touches the primal feasibility translation rather than the core duality-gap complexity. Overall, the conditional verdict is appropriate: the paper needs a revision to close the domain-of-smoothness gap, not rejection.","tokens_in":22382,"tokens_out":20556,"duration_ms":227284,"concrete_test":"Analytical counterexample: take X = [0,1], φ0(x) = x^2 on X, and define φ0(x) = x^2 + A(x-1)^{3/2} sin(1/(x-1)) for x > 1. This satisfies Assumptions 2.1–2.3 with L = 2 and G = 2 on Z, and φ0 is differentiable at x = 1 with derivative 2. At z = 1, estimator (3) gives (φ0(1+r)-φ0(1))/r = 2 + r + A√r sin(1/r), so |G - φ0'(1)| ≈ A√r, which is not bounded by (1/2)Lr = r for any A > 0 and sufficiently small r. If this oracle is admissible under the stated assumptions, Lemma 2.1 is false; if not, the missing neighborhood-smoothness hypothesis must be added explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 2.2 grants G-Lipschitz and L-smoothness only on Z = X × Y, but the coordinate estimator (3) and the UniGE estimator (4) evaluate f at z + r e_i or z + r v with z an iterate in Z. For z on the boundary of Z, the queried point leaves Z, so the mean-value proof of Lemma 2.1 integrates ∇h along a segment that is not covered by the assumed smoothness. The same defect enters Lemma 3.1's variance argument and Lemma 4.1's Eq. (23), so Theorems 3.1 and 4.1, and therefore Corollary 4.2, do not follow from the stated assumptions. This is not merely stylistic: one can define f to equal x^2 on [0,1] but have unbounded gradient on (1,∞); at x=1 the estimator error is unbounded as r→0 while all stated assumptions hold. The natural fix is to assume smoothness on an open neighborhood of Z, or to restrict r so that all queried segments lie in Z; with either repair the proof algebra appears to go through. A secondary, also patchable gap is that R in Proposition 3.1/4.1 can be zero when y* lies on the boundary of Y, making the constraint-violation bound vacuous.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies constrained optimization with black-box objective and constraint functions by reformulating problem (1) as a convex-concave min-max problem (2) over X × Y. It proposes ZOEG, which combines extra-gradient updates with a 2-point uniform sphere gradient estimator, and ZOCEG, which uses a 2d-point coordinate gradient estimator, together with a block-coordinate variant ZOBCEG. Convergence and oracle-complexity bounds are given: O(d ε^{-2}) for ZOEG and O(d ε^{-1}) for ZOCEG, with experimental validation on a load-tracking problem in power systems. The technical narrative is self-contained: the proofs are detailed, the algorithms are clearly specified, and no parameters are fitted to justify the claimed rates.","tokens_in":22599,"tokens_out":14142,"duration_ms":149794,"significance":"If the proofs are repaired along the lines below, the paper makes a solid contribution: ZOCEG's O(d ε^{-1}) oracle complexity is a substantial improvement over the O(d^2 ε^{-2}) and O(d^4 ε^{-2}) bounds cited for earlier black-box constrained methods, and the block-coordinate extension addresses a practical concern about per-iteration evaluation cost. The convergence analysis is not circular and does not tune assumptions to match experiments; the numerical study on a realistic load-tracking problem supports the qualitative behavior of the algorithms. The main caveats are technical: the smoothness domain for finite-difference estimators, the boundary-degenerate constraint-violation constant R, and an algebraic error in Corollary 3.2. These are fixable within the manuscript's scope, but they currently affect load-bearing statements.","major_comments":[{"comment":"Assumption 2.2 grants G-Lipschitzness and L-smoothness only for pairs of points in Z, but the estimators (3) and (4) evaluate f at z+r e_i or z+r v. For z on the boundary of Z these evaluation points lie outside Z, so the segment-integration argument in the proof of Lemma 2.1 is not covered by the stated assumption. One can construct a function that is smooth on Z with the stated constants but has arbitrarily large gradients just outside Z, making the finite-difference bias at boundary points unbounded as r→0. The same defect enters the variance argument in Lemma 3.1 and the term (23) in Lemma 4.1, and hence propagates to Theorems 3.1, 4.1, and 4.3. Please assume smoothness on an open neighborhood of Z, or restrict the smoothing radii so that all queried segments remain in Z, or use a projected estimator that stays inside Z. With any of these repairs the subsequent proof algebra appears to go through.","section":""},{"comment":"The constant R is defined in Lemma 3.3 as the inradius of Y centered at y*, i.e., the largest r such that the whole ball y* + rB^{dy} lies in Y. If y* lies on the boundary of Y, then R=0 and the displayed constraint-violation bounds become vacuous; moreover, the point ȳ = y* + R [s]_+/||[s]_+|| used in the proof of Lemma 3.3 degenerates to y* and gives no control on the violation. This is not an exceptional case, since dual multipliers for inactive constraints naturally sit at zero. Please add an explicit interiority assumption with a positive margin, or replace the uniform R by a direction-dependent distance to the boundary of Y and adapt the argument, or reformulate the violation bound so that it does not involve 1/R.","section":""},{"comment":"Substituting η = D̃/(6√(6dKG)) into Theorem 3.1 gives terms D̃²/(2ηK) and 108ηdG² that decay as K^{-1/2}, not as K^{-1}; the displayed equality in the proof, which has denominators K and √(K³), is inconsistent with the substitution. Consequently the second entry in the maximum for K, whose exponent is 1/3, does not control the term (9d²+12)L²M₂η, which is O(K^{-1/2}) and requires a lower bound of the form K ≥ const/ε². Please correct the algebra and the stated lower bounds. The overall O(d/ε²) oracle-complexity claim may survive the correction, but the corollary as printed is not implied by Theorem 3.1.","section":""}],"minor_comments":[{"comment":"In the sampling line, I^x_k is written twice where the second occurrence should be I^y_k; the same duplication occurs for J^x_k and J^y_k.","section":""},{"comment":"The statement D̃ = max_{z,z'∈Z} ||z−z'|| ≤ +∞ is vacuously true; it should say D̃ < ∞, which follows from compactness.","section":""},{"comment":"The loop header 'for k← −0 to K−1' contains a typo with '−0'; it should be 'k←0'.","section":""},{"comment":"The remark claims that the deterministic results extend to the stochastic setting 'as discussed in [3]', but no stochastic analysis is given in this paper; either add the proof or soften the claim.","section":""},{"comment":"The table lists O(d ε^{-1}) for ZOCEG and O(d ε^{-2}) for ZOBCEG, but for ZOBCEG the displayed bound in Theorem 4.3 only yields that rate after choosing η of order √(d̃/K); please state this parameter choice in the table or its caption. Also, the claim that this is the best-known complexity for problem (1) would be easier to verify if the precise settings and rates of references [40] and [5] were summarized alongside the comparison.","section":""}],"recommendation":"major_revision","confidential_remarks":"The manuscript cites reference [5], co-authored by two of the present authors, as a baseline and as the source of the experimental setup. The convergence analysis does not rely on [5], so I do not see a circularity problem, but the 'best-known complexity' claim would benefit from a precise statement of what [5] and [40] actually prove. The main technical gaps—domain of smoothness, the boundary-degenerate R, and the Corollary 3.2 algebra—are all locally fixable and do not, in my view, invalidate the core algorithmic ideas."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The central result is a genuine improvement in oracle complexity: ZOCEG gets O(d/ε) for convex problems with black-box constraints, which is a factor d/ε better than the cited O(d²/ε²) and O(d⁴/ε²) bounds. The proof strategy is transparent: combine extra-gradient with coordinate finite differences, control the estimator bias linearly in r, and telescope. If the assumptions are read as intended, the complexity table follows from the theorems.\n\nWhat the paper does well: it identifies the right estimator for this setting. CooGE has lower variance than UniGE, so the O(d) oracle per step actually pays off. The analysis is self-contained, the step-size conditions are explicit, and the comparison with [5] is fine as a baseline even though two authors overlap. The experiments on load tracking are reasonable and support the claims, though no code or data are provided.\n\nSoft spots, in order of importance. First, Assumption 2.2 only grants G-Lipschitz and L-smoothness on Z = X×Y, but the coordinate estimator queries f at z + r e_i, which leaves Z when z is on the boundary. Lemma 2.1's proof integrates ∇h along that segment, so it is not covered by the assumption. This is not just a formal quibble: one can satisfy the assumptions on Z and have unbounded gradient just outside Z, making the forward-difference error at the boundary unbounded as r→0. Theorems 4.1 and 3.1, and hence the O(d/ε) claim, do not follow as stated. The fix is easy—assume smoothness on an open neighborhood of Z, or restrict the smoothing radii so every queried segment lies in Z—and with either repair the algebra appears to go through. Second, the constraint-violation bounds in Propositions 3.1 and 4.1 use R, the radius of the largest ball centered at y* inside Y. If y* lies on the boundary of Y, R=0 and the bound is vacuous. This can happen with active constraints and a bounded dual set, so the paper's stated guarantee of ε-optimality for problem (1) is not justified without an additional assumption (e.g., y* interior, or a different measure of violation). This is also patchable.\n\nWho this is for: researchers in zeroth-order and simulation optimization. The complexity improvement is real enough to deserve scrutiny. My recommendation: yes, send it to peer review, but the authors should be asked to fix the smoothness-domain assumption before acceptance; as written, the headline theorem is conditional.","headline":"A clean O(d/ε) oracle complexity claim for constrained black-box optimization that is probably right, but the stated smoothness assumptions don't cover the points the algorithm queries; both gaps are patchable.","tokens_in":23177,"tokens_out":5359,"would_cite":false,"duration_ms":61959,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes zeroth-order extra-gradient algorithms for black-box constrained optimization and proves that a coordinate-estimator variant reaches an $\\epsilon$-optimal solution with $O(d/\\epsilon)$ function evaluations, the…","keywords":["zeroth-order optimization","extra-gradient method","black-box constraints","min-max reformulation","oracle complexity","coordinate gradient estimator","derivative-free optimization","load tracking"],"falsifier":"Take $Z=[0,1]$ and let $f(x)=x^2$ for $x\\le 1$ but $f(x)=x^2+C(x-1)$ for $x>1$ with $C$ large. On $Z$ this satisfies the stated smoothness assumptions with small $L$, yet the coordinate estimator at $x=1$ has bias roughly $C+r$, far exceeding $\\tfrac12 Lr$; this directly contradicts Lemma 2.1 and would invalidate the ZOCEG convergence proof, showing the stated assumptions are insufficient as written.","tokens_in":22117,"feed_emoji":"⚡","tokens_out":9941,"duration_ms":98606,"temperature":0.7,"pith_summary":"Constrained optimization problems whose objective and constraint functions can only be evaluated, not differentiated, arise in control and power systems. This paper reformulates the problem as a convex-concave saddle-point problem and appends extra-gradient updates with two zeroth-order gradient estimators: ZOEG uses a two-point spherical estimator, and ZOCEG uses a $2d$-point coordinate-wise finite-difference estimator. The paper proves that ZOCEG finds an $\\epsilon$-optimal solution with $O(d/\\epsilon)$ function evaluations, improving on the previous best $O(d^2/\\epsilon^2)$ for black-box constraints and matching the first-order extra-gradient rate up to one factor of $d$. A block-coordinate extension, ZOBCEG, trades some of that guarantee for lower per-iteration cost. Numerical experiments on a demand-side load-tracking problem in power systems validate the convergence behavior.","feed_headline":"Coordinate extra-gradient hits O(d/ε) for black-box constraints","feed_subtitle":"Pairing a coordinate-wise estimator with extra-gradient updates cuts required function queries by a factor of 1/ε.","key_machinery":"The mechanism is the extra-gradient pair of projected updates, $z_k^+=\\mathcal{P}_Z[z_k-\\eta g_k]$ and $z_{k+1}=\\mathcal{P}_Z[z_k-\\eta g_k^+]$, applied to the convex-concave Lagrangian $f(x,y)=\\phi_0(x)+\\sum_{j} y_j\\phi_j(x)$ on $Z=X\\times Y$, with operator $F=(\\nabla_x f; -\\nabla_y f)$. Because $F$ is unavailable, the updates use zeroth-order estimators: the $2d$-point coordinate finite-difference estimator $\\hat g_i=(h(z+re_i)-h(z))/r$ and the two-point uniform spherical estimator. The coordinate estimator has bias $O(Lr)$ and variance $O(L^2r^2)$, so for small smoothing radius it behaves like a first-order gradient and preserves the telescoping-sum argument that gives the $O(1/K)$ duality-gap bound. This variance reduction is what converts the $O(d/\\epsilon^2)$ oracle complexity of ZOEG into the $O(d/\\epsilon)$ oracle complexity of ZOCEG.","core_discovery":"On the paper's own account, the central discovery is that the extra-gradient update can be made zeroth-order without losing its $O(1/K)$ duality-gap rate, provided gradients are estimated coordinate-by-coordinate instead of with a two-point spherical estimator. For ZOCEG, the authors prove that after $K \\ge \\max\\{\\tilde{D}^2/(\\eta\\epsilon),\\, 3LM_3\\tilde{D}/\\epsilon\\}$ iterations, the averaged output satisfies duality gap $\\Delta(\\hat z_K)\\le\\epsilon$, constraint violation $\\|[\\varphi(\\hat x_K)]_+\\|\\le\\epsilon/R$, and objective suboptimality $\\phi_0(\\hat x_K)-\\phi_0^*\\le\\epsilon$. Since each iteration costs $2d$ function evaluations, ZOCEG has oracle complexity $O(d/\\epsilon)$ for problem (1), which the paper reports as the best known for black-box constraints under its assumptions. The two-point-estimator algorithm ZOEG is shown to reach $O(d/\\epsilon^2)$ with an improved dimension factor relative to prior work.","pith_inferences":["If the $O(d/\\epsilon)$ oracle complexity holds, the remaining bottleneck is the factor $d$ from estimating each coordinate separately; variance-reduced or importance-sampled estimators might shrink that factor while keeping zeroth-order access.","The proof gap at boundary points suggests a mild repair: assume smoothness on an $r$-neighborhood of $Z$, which differentiable simulators typically satisfy; the complexity conclusions would likely survive unchanged.","ZOCEG's estimator is deterministic, so the method is tailored to noiseless observations; inserting repeated evaluations or smoothing could test whether the $O(d/\\epsilon)$ rate survives small stochastic noise.","The contrast between the spherical and coordinate estimators suggests a design principle: with a deterministic oracle, pay more evaluations per iteration to lower estimator variance, since that variance is what forces the $\\epsilon^{-2}$ term."],"forward_implications":["ZOCEG reaches an $\\epsilon$-saddle point of the min-max reformulation and an $\\epsilon$-optimal solution of the original constrained problem with oracle complexity $O(d/\\epsilon)$.","ZOEG reaches the same targets with oracle complexity $O(d/\\epsilon^2)$, improving the dimension dependence over earlier black-box constrained methods.","With diminishing smoothing radii and a step size tuned to $K$, the fixed error terms in the ZOEG bound vanish, so both constraint violation and optimality gap converge at rate $O(1/K)$.","ZOBCEG uses only $2(\\tau_x+\\tau_y)$ evaluations per iteration, recovers ZOCEG when $\\tau_x=d_x$ and $\\tau_y=d_y$, and keeps oracle complexity $O(d/\\epsilon^2)$ for intermediate block sizes.","For nonconvex problems, the paper notes that wrapping the algorithms in a proximal-point meta-algorithm would give oracle complexity $O(d/\\epsilon^3)$ for ZOEG and $O(d/\\epsilon^2)$ for ZOCEG to reach an $\\epsilon$-critical KKT point."],"supporting_citations":[{"why":"Establishes the previous oracle complexity $O(d^2/\\epsilon^2)$ for black-box constrained problems and supplies the stochastic and proximal-point settings referenced in the paper.","marker":"[3]"},{"why":"Provides the $O(d^4/\\epsilon^2)$ zeroth-order optimistic GDA baseline that the new dimension dependence improves on.","marker":"[35]"},{"why":"Supplies the extra-gradient / prox-method machinery whose $O(1/T)$ rate and updates the algorithms build on.","marker":"[36]"},{"why":"Gives the two-point uniform spherical estimator and the bias and variance bounds used in the ZOEG analysis.","marker":"[38]"},{"why":"Supplies the coordinate gradient estimator analysis and the variance bound used by ZOCEG.","marker":"[20]"},{"why":"Defines the load-tracking test problem and the feasibility-preserving perturbation technique used in the numerical experiments.","marker":"[5]"}],"fun_headline_variants":["Zeroth-order extra-gradient: O(d/ε) for black-box constraints","Coordinate estimator pushes extra-gradient to O(d/ε) queries","Black-box constrained opt: zeroth-order extra-gradient at O(d/ε)","Extra-gradient without gradients: best-known O(d/ε) for black-box"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the black-box function is smooth at the offset query points $z+r e_i$ used by the finite-difference estimator, whereas the stated assumptions only guarantee smoothness on the feasible set $Z$ itself; a boundary point whose offset sample lands outside $Z$ is therefore not covered by the proof.","fun_headline_variants_meta":{"raw":{"variants":["Zeroth-order extra-gradient: O(d/ε) for black-box constraints","Coordinate estimator pushes extra-gradient to O(d/ε) queries","Black-box constrained opt: zeroth-order extra-gradient at O(d/ε)","Extra-gradient without gradients: best-known O(d/ε) for black-box"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000351,"raw_usage":{"total_tokens":1923,"prompt_tokens":966,"completion_tokens":957,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":876}},"tokens_in":582,"tokens_out":957,"duration_ms":9321,"temperature":1.0,"reasoning_tokens":876,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:47:42.728913+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $Z=[0,1]$ and let $f(x)=x^2$ for $x\\le 1$ but $f(x)=x^2+C(x-1)$ for $x>1$ with $C$ large. On $Z$ this satisfies the stated smoothness assumptions with small $L$, yet the coordinate estimator at $x=1$ has bias roughly $C+r$, far exceeding $\\tfrac12 Lr$; this directly contradicts Lemma 2.1 and would invalidate the ZOCEG convergence proof, showing the stated assumptions are insufficient as written.","supporting_citations":[{"cited_title":"Stoc hastic zeroth-order functional constrained optimization: Oracle complexity and applications","cited_arxiv_id":null,"evidence_quote":"Establishes the previous oracle complexity $O(d^2/\\epsilon^2)$ for black-box constrained problems and supplies the stochastic and proximal-point settings referenced in the paper."},{"cited_title":"Zeroth- order methods for convex-concave min-max problems: Applic ations to decision-dependent risk min- imization","cited_arxiv_id":null,"evidence_quote":"Provides the $O(d^4/\\epsilon^2)$ zeroth-order optimistic GDA baseline that the new dimension dependence improves on."},{"cited_title":"Prox-method with rate of convergen ce o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex -concave saddle point problems","cited_arxiv_id":null,"evidence_quote":"Supplies the extra-gradient / prox-method machinery whose $O(1/T)$ rate and updates the algorithms build on."},{"cited_title":"Derivative-free methods for policy optimization: Guarantees for linear quadratic systems","cited_arxiv_id":null,"evidence_quote":"Gives the two-point uniform spherical estimator and the bias and variance bounds used in the ZOEG analysis."},{"cited_title":"A theoretical and em- pirical comparison of gradient approximations in derivative-free optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the coordinate gradient estimator analysis and the variance bound used by ZOCEG."}],"review_version":1}