Pith. sign in

REVIEW 3 major objections 5 minor 45 references

A Zeroth-Order Extra-Gradient Method for Black-Box Constrained Optimization

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

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

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2506.20546 v2 pith:4WTMFQM6 submitted 2025-06-25 math.OC

Yuke Zhou , Ruiyang Jin , Siyang Gao , Jianxiao Wang , Jie Song This is my paper · ORCID
classification math.OC MSC 90C2590C3090C56
keywords zeroth-orderoptimizationextra-gradientmethodblack-boxconstraintsmin-maxreformulationoraclecomplexitycoordinategradientestimatorderivative-freeloadtracking
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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 / 5 minor

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.

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 (3)
  1. 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.
  2. 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.
  3. 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.
minor comments (5)
  1. 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.
  2. The statement D̃ = max_{z,z'∈Z} ||z−z'|| ≤ +∞ is vacuously true; it should say D̃ < ∞, which follows from compactness.
  3. The loop header 'for k← −0 to K−1' contains a typo with '−0'; it should be 'k←0'.
  4. 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.
  5. 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the O(d/eps) oracle complexity of ZOCEG is derived in-paper via Lemma 2.1 and Lemma 4.1; the sole overlapping-author citation [5] is used for the test problem, motivation, and a literature-placement remark, and is not load-bearing for any bound.

full rationale

The paper's central claims are the oracle complexities O(d/eps^2) (ZOEG), O(d/eps) (ZOCEG), and O(d/eps^2) (ZOBCEG) in Table 1 and Corollaries 3.2 and 4.2. These follow from Theorems 3.1, 4.1, and 4.3, whose proofs are in-paper: Lemma 3.1 (Appendix A.1) and Lemma 4.1 (Appendix B) bound the extra-gradient inner product, Lemma 3.2 turns it into a duality-gap bound via Jensen's inequality, and Lemma 3.3 yields the optimality-gap and constraint-violation bounds. The only imported estimation facts are Lemma 2.2's identities and variance bound, attributed to external references [38] and [20]; Lemma 2.1, the coordinate-estimator bias bound used in every ZOCEG/ZOBCEG proof, is proved in Appendix A. No parameter is fitted to data and later renamed a prediction: step sizes and smoothing radii are set analytically (e.g., eta = D~/(6 sqrt(6 d K G)) in Corollary 3.2) and outputs are averaged iterates. The only overlapping-author citation, [5] (Jin, Tang, Song; Jin and Song are present co-authors), appears in the intro's motivation, as an example of 'common' smoothness assumptions next to external [34], as the Section 5 load-tracking test problem, as a feasibility-perturbation trick in the nonconvex experiments, and in the remark after Corollary 4.2 that separates [5] and [40] from the present problem class because they need decomposable explicit feasible sets. No lemma or proof step cites [5]; the remark's classification of [5] is an externally verifiable literature claim, and the Table 1 baselines [3] and [35] are external. Thus the derivation chain is self-contained and does not reduce to its inputs. Two correctness risks are flagged (neither is circularity): (i) Assumption 2.2 grants G-Lipschitz and L-smoothness only on Z, while estimators (3) and (4) query z + r e_i and z + r v, which can leave Z at boundary iterates, so the segment-wise smoothness in the Appendix A proof of Lemma 2.1 and in Equation (23) of Lemma 4.1 is not guaranteed as stated; repairing this requires smoothness on a neighborhood of Z or a restricted r. (ii) The constant R in Propositions 3.1 and 4.1 (defined via y* + r u in Y) can be 0 when y* lies on the boundary of Y, making the constraint-violation bound vacuous. These are assumption-coverage gaps, not equivalences by construction.

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

The paper introduces no new physical entities or fitted constants. The central claim rests on standard convex optimization assumptions and on algorithm hyperparameters that are explicitly specified in the theorems.

free parameters (3)
  • step size η = set per Corollary 3.2/4.2 (e.g., η = D̃/(6√(6dKG)))
    The convergence bounds depend on η; the theorems prescribe a value that yields the claimed ε complexity.
  • smoothing radii r_k = summable sequences, e.g., r_k = min{5/(k+1)^1.1, 10^-3} in experiments
    The bias and variance bounds depend on r_k; they must satisfy Σ r_k < ∞ and Σ r_k² < ∞ for ZOEG, and Σ r_k ≤ M3/(√dx+√dy) for ZOCEG.
  • block sizes τx, τy (ZOBCEG) = user-chosen integers 1 ≤ τx ≤ dx, 1 ≤ τy ≤ dy
    The ZOBCEG complexity bound depends on τx and τy through dx/τx and dy/τy.
assumptions (5)
  • domain assumption f is convex in x and concave in y (Assumption 2.1)
    Central to the min-max reformulation and duality gap analysis.
  • domain assumption f is G-Lipschitz and L-smooth on Z (Assumption 2.2)
    Provides boundedness and smoothness needed for finite-difference bias and variance bounds.
  • domain assumption Z = X × Y is compact and convex (Assumption 2.3)
    Ensures projections exist and the diameter D̃ is finite.
  • domain assumption A saddle point z* exists and the optimal dual set is bounded under Slater's condition (Section 2.1, citing [37])
    Used to justify constructing a bounded dual set Y containing y*.
  • ad hoc to paper f is smooth on a neighborhood of Z so that finite-difference points z + r e_i are in the domain (implicit)
    The coordinate estimators require evaluating f at points possibly outside Z when z is on the boundary; Assumption 2.2 does not explicitly cover these points.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Zeroth-Order Extra-Gradient Method for Black-Box Constrained Optimization." pith.science (2026). https://pith.science/paper/4WTMFQM6

@misc{pith2026250620546,
  author       = {Pith},
  title        = {Pith review of: A Zeroth-Order Extra-Gradient Method for Black-Box Constrained Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4WTMFQM6}},
  note         = {Machine review of arXiv:2506.20546}
}
abstract

Non-analytical objectives and constraints often arise in control systems, particularly in problems with complex dynamics, which are challenging yet lack efficient solution methods. In this work, we consider general constrained optimization problems involving black-box objectives and constraints. To solve it, we reformulate it as a min-max problem and propose a zeroth-order extra gradient (ZOEG) algorithm that combines the extra gradient method with a feedback-based stochastic zeroth-order gradient estimator. Then, we apply another coordinate gradient estimator to design the zeroth-order coordinate extra gradient algorithm (ZOCEG) to further improve efficiency. The theoretical analysis shows that ZOEG can achieve the best-known oracle complexity of $\mathcal{O}(d\epsilon^{-2})$ to get an $\epsilon$-optimal solution ($d$ is the dimension of decision space), and ZOCEG can improve it to $\mathcal{O}(d\epsilon^{-1})$. Furthermore, we develop a variant of ZOCEG, which applies block coordinate updates to enhance the efficiency of single-step gradient estimation. Finally, numerical experiments on a load tracking problem validate our theoretical results and the effectiveness of the proposed algorithms.

Figures

Figures reproduced from arXiv: 2506.20546 by the authors.

Figure 1
Figure 1. Performance comparison in the convex case: (a) ave [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Performance of ZOBCEG in the convex case: (a) avera [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Performance of algorithms in the nonconvex case: ( [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 44 canonical work pages

  1. [5]

    Zeroth-order feed back-based optimization for distributed de- mand response

    Ruiyang Jin, Y ujie Tang, and Jie Song. Zeroth-order feed back-based optimization for distributed de- mand response. arXiv preprint arXiv:2311.00372, 2023

    arXiv 2023

  2. [1]

    Safe zeroth-order optimization using quadratic local approximations

    Baiwei Guo, Y uning Jiang, Giancarlo Ferrari-Trecate, a nd Maryam Kamgarpour. Safe zeroth-order optimization using quadratic local approximations. Automatica, 174:112141, 2025

    work page 2025

  3. [2]

    Handbook of simulation optimization , volume 216

    Michael C Fu et al. Handbook of simulation optimization , volume 216. Springer, 2015

    work page 2015

  4. [3]

    Stoc hastic zeroth-order functional constrained optimization: Oracle complexity and applications

    Anthony Nguyen and Krishnakumar Balasubramanian. Stoc hastic zeroth-order functional constrained optimization: Oracle complexity and applications. INFORMS Journal on Optimization, 5(3):256–272, 2023

    work page 2023

  5. [4]

    Model-Free Optimal Voltage Control via Continuous-Time Zeroth-Order Methods

    Xin Chen, Jorge I. Poveda, and Na Li. Model-free optimal v oltage control via continuous-time zeroth- order methods, 2021. URL https://arxiv.org/abs/2103.14703

    work page Pith review arXiv 2021

  6. [6]

    direct search

    Robert Hooke and Terry A Jeeves. “direct search”solutio n of numerical and statistical problems. Jour- nal of the ACM (JACM), 8(2):212–229, 1961

    work page 1961

  7. [7]

    A simplex method for functio n minimization

    John A Nelder and Roger Mead. A simplex method for functio n minimization. The Computer Journal, 7(4):308–313, 1965

    work page 1965

  8. [8]

    Numerical solution of a minimum problem

    Enrico Fermi. Numerical solution of a minimum problem. T echnical report, Los Alamos Scientific Lab., Los Alamos, NM, 1952

    work page 1952

Show all 45 references
  1. [9]

    On the convergence of pattern search a lgorithms

    Virginia Torczon. On the convergence of pattern search a lgorithms. SIAM Journal on Optimization , 7 (1):1–25, 1997

    1997

  2. [10]

    Pattern s earch algorithms for bound constrained mini- mization

    Lewis, Robert Michael and Torczon, Virginia. Pattern s earch algorithms for bound constrained mini- mization. SIAM Journal on Optimization, 9(4):1082–1099, 1999

    1999

  3. [11]

    Mesh adaptive direct search algorithms for constrained optimiza- tion

    Charles Audet and John E Dennis Jr. Mesh adaptive direct search algorithms for constrained optimiza- tion. SIAM Journal on Optimization, 17(1):188–217, 2006

    2006

  4. [12]

    A g lobally convergent augmented lagrangian algorithm for optimization with general constraints and si mple bounds

    Andrew R Conn, Nicholas IM Gould, and Philippe Toint. A g lobally convergent augmented lagrangian algorithm for optimization with general constraints and si mple bounds. SIAM Journal on Numerical Analysis, 28(2):545–572, 1991

    1991

  5. [13]

    Bayesian optimisati on for constrained problems

    Juan Ungredda and Juergen Branke. Bayesian optimisati on for constrained problems. ACM Transac- tions on Modeling and Computer Simulation , 34(2):1–26, 2024

    2024

  6. [14]

    Stochastic radial basis function algor ithms for large-scale optimization involving expensive black-box objective and constraint functions

    Rommel G Regis. Stochastic radial basis function algor ithms for large-scale optimization involving expensive black-box objective and constraint functions. Computers & Operations Research , 38(5): 837–853, 2011

    2011

  7. [15]

    A survey of surrogate approaches for exp ensive constrained black-box optimization

    Rommel G Regis. A survey of surrogate approaches for exp ensive constrained black-box optimization. In Optimization of Complex Systems: Theory, Models, Algorith ms and Applications , pages 37–47. Springer, 2020

    2020

  8. [16]

    Constrained stochastic black- box optimization using a progressive barrier and probabili stic estimates

    Kwassi Joseph Dzahini, Michael Kokkolaras, and Sébast ien Le Digabel. Constrained stochastic black- box optimization using a progressive barrier and probabili stic estimates. Mathematical Programming, 198(1):675–732, 2023. 19

    2023

  9. [17]

    Fi lter-based adaptive kriging method for black-box optimization problems with expensive object ive and constraints

    Renhe Shi, Li Liu, Teng Long, Y ufei Wu, and Yifan Tang. Fi lter-based adaptive kriging method for black-box optimization problems with expensive object ive and constraints. Computer Methods in Applied Mechanics and Engineering, 347:782–805, 2019

    2019

  10. [18]

    Conorbit: constrained optimization by radial basis function interpolation in trust regions

    Rommel G Regis and Stefan M Wild. Conorbit: constrained optimization by radial basis function interpolation in trust regions. Optimization Methods and Software, 32(3):552–580, 2017

    2017

  11. [19]

    Stochastic zeroth-order optimiza- tion in high dimensions

    Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aar ti Singh. Stochastic zeroth-order optimiza- tion in high dimensions. In International Conference on Artificial Intelligence and St atistics, pages 1356–1365. PMLR, 2018

    2018

  12. [20]

    A theoretical and em- pirical comparison of gradient approximations in derivative-free optimization

    Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, a nd Katya Scheinberg. A theoretical and em- pirical comparison of gradient approximations in derivative-free optimization. F oundations of Compu- tational Mathematics, 22(2):507–560, 2022

    2022

  13. [21]

    Derivat ive-free alternating projection algorithms for general nonconvex-concave minimax problems

    Zi Xu, Ziqi Wang, Jingjing Shen, and Y uhong Dai. Derivat ive-free alternating projection algorithms for general nonconvex-concave minimax problems. SIAM Journal on Optimization, 34(2):1879–1908, 2024

    1908

  14. [22]

    An i nexact preconditioned zeroth-order proximal method for composite optimization

    Shang-Lin Liu, Lei Wang, Na-Chuan Xiao, and Xin Liu. An i nexact preconditioned zeroth-order proximal method for composite optimization. Journal of the Operations Research Society of China , pages 1–19, 2025

    2025

  15. [23]

    Boosting one-point derivative-free online optimization via residual feedback

    Y an Zhang, Yi Zhou, Kaiyi Ji, Yi Shen, and Michael M Zavla nos. Boosting one-point derivative-free online optimization via residual feedback. IEEE Transactions on Automatic Control, 2024

    2024

  16. [24]

    Online convex optimization in the bandit setting: gradient descent without a gradient

    Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMa han. Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 385–394, 2005

    2005

  17. [25]

    Random gradient-free minimization of convex functions

    Y urii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. F oun- dations of Computational Mathematics , 17(2):527–566, 2017

    2017

  18. [26]

    Zeroth-order feedba ck optimization for cooperative multi-agent systems

    Y ujie Tang, Zhaolin Ren, and Na Li. Zeroth-order feedba ck optimization for cooperative multi-agent systems. Automatica, 148:110741, 2023

    2023

  19. [27]

    Optimal rates for zero- order convex optimization: The power of two function evalua tions

    John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero- order convex optimization: The power of two function evalua tions. IEEE Transactions on Information Theory, 61(5):2788–2806, 2015

    2015

  20. [28]

    A primer on zeroth-order optimization in signal proces sing and machine learning: Principals, recent advances, and applications

    Sijia Liu, Pin-Y u Chen, Bhavya Kailkhura, Gaoyuan Zhan g, Alfred O Hero III, and Pramod K V arsh- ney. A primer on zeroth-order optimization in signal proces sing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43–54, 2020

    2020

  21. [29]

    Mini- batch stochastic approximation methods for nonconvex stochastic composite optimization

    Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini- batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1):267–305, 2016

    2016

  22. [30]

    Distributed rand omized gradient-free mirror descent algorithm for constrained optimization

    Zhan Y u, Daniel WC Ho, and Deming Y uan. Distributed rand omized gradient-free mirror descent algorithm for constrained optimization. IEEE Transactions on Automatic Control , 67(2):957–964, 2021

    2021

  23. [31]

    A frank-wolfe framework for efficient and effective adversarial attacks

    Jinghui Chen, Dongruo Zhou, Jinfeng Yi, and Quanquan Gu . A frank-wolfe framework for efficient and effective adversarial attacks. In Proceedings of the AAAI Conference on Artificial Intelligen ce, volume 34, pages 3486–3494, 2020. 20

    2020

  24. [32]

    An enhanced zeroth-order stochastic frank- wolfe framework for constrained finite-sum optimization

    Haishan Y e, Yinghui Huang, Hao Di, and Xiangyu Chang. An enhanced zeroth-order stochastic frank- wolfe framework for constrained finite-sum optimization. arXiv preprint arXiv:2501.07201, 2025

    2025 arXiv

  25. [33]

    Gradient-free a ccelerated event-triggered scheme for constrained network optimization in smart grids

    Chuanhao Hu, Xuan Zhang, and Qiuwei Wu. Gradient-free a ccelerated event-triggered scheme for constrained network optimization in smart grids. IEEE Transactions on Smart Grid, 15(3):2843–2855, 2023

    2023

  26. [34]

    Min-max optimization without gradients : Convergence and applications to black- box evasion and poisoning attacks

    Sijia Liu, Songtao Lu, Xiangyi Chen, Y ao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Una-May O’Reilly. Min-max optimization without gradients : Convergence and applications to black- box evasion and poisoning attacks. In International Conference on Machine Learning ...

  27. [35]

    Zeroth- order methods for convex-concave min-max problems: Applic ations to decision-dependent risk min- imization

    Chinmay Maheshwari, Chih-Y uan Chiu, Eric Mazumdar, Sh ankar Sastry, and Lillian Ratliff. Zeroth- order methods for convex-concave min-max problems: Applic ations to decision-dependent risk min- imization. In International Conference on Artificial Intelligence and St atistics, ...

    2022

  28. [36]

    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

    Arkadi Nemirovski. 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. SIAM Journal on Optimization, 15(1):229–251, 2004

    2004

  29. [37]

    Subgradient methods for saddle-poin t problems

    Angelia Nedi ´c and Asuman Ozdaglar. Subgradient methods for saddle-poin t problems. Journal of Optimization Theory and Applications , 142:205–228, 2009

    2009

  30. [38]

    Derivative-free methods for policy optimization: Guarantees for linear quadratic systems

    Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Kha maru, Peter L Bartlett, and Martin J Wain- wright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. Journal of Machine Learning Research, 21(21):1–51, 2020

    2020

  31. [39]

    A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Pro ximal point approach

    Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil . A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Pro ximal point approach. In International Conference on Artificial Intelligence and Statistics , pages 1497–1507. PMLR, 2020

    2020

  32. [40]

    A zeroth-order block coordi- nate gradient descent method for cellular network optimiza tion

    Pengcheng He, Siyuan Lu, Xin Guan, Yibin Kang, and Qingj iang Shi. A zeroth-order block coordi- nate gradient descent method for cellular network optimiza tion. In 2022 International Symposium on Wireless Communication Systems (ISWCS), pages 1–6. IEEE, 2022

    2022

  33. [41]

    Stochastic fir st-order methods for convex and nonconvex functional constrained optimization

    Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic fir st-order methods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215–279, 2023

    2023

  34. [42]

    Robust stochastic ap- proximation approach to stochastic programming

    Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, an d Alexander Shapiro. Robust stochastic ap- proximation approach to stochastic programming. SIAM Journal on Optimization , 19(4):1574–1609, 2009. 21 Appendices A Proof of Lemma 2.1 By definition, we have |Gh,i(z; r)−∇ ih(z)| ...

    2009

  35. [43]

    Taking expectation over vk gives: E [⟨ ηF (z+ k ), z+ k− z ⟩ |F k ] ≤ E [⟨ ηg+ k , z+ k− z ⟩ |F k ] + ηL ˜Drk

    and the last inequality follows from ( 7). Taking expectation over vk gives: E [⟨ ηF (z+ k ), z+ k− z ⟩ |F k ] ≤ E [⟨ ηg+ k , z+ k− z ⟩ |F k ] + ηL ˜Drk. (16) Then, we focus on the bound for the first term: ⟨ ηg+ k , z+ k− z ⟩ = ⟨ ηg+ k , z+ k− zk+1 ⟩ + ⟨ ηg+ k , zk+1− z ⟩ ≤ ⟨ ...

  36. [44]

    Then, E [ ‖gk− g+ k‖2|F k ] is bounded as follows: E [ ‖gk− g+ k‖2|F k ] ≤ ˆ∆k, (19) where ˆ∆k = 108d2G2 d+2 + 9d2L2r2 k + 12L2r2 k + 12G2

    with (8) yields the following bound: E [ ‖gk− F (zk)‖2|F k ] ≤2· E [ ‖gk− F rk (zk)‖2 +‖F rk (zk)− F (zk)‖2|F k ] ≤ 18d2G2 d + 2 + 3d2L2r2 k 2 + 2L2r2 k, and the bound on E [ ‖g+ k− F (z+ k )‖2|F k ] can be derived similarly. Then, E [ ‖gk− g+ k‖2|F k ] is bounded as follows: ...

  37. [45]

    24 C Proof of Theorem 4.3 Similarly, We start by defining a filtration F b k := σ (z0,I x 0 ,I y 0 ,J x 0 ,J y 0 , z1, ..., zk)

    and (25) gives: ⟨ ηF (z+ k ), z+ k− z ⟩ ≤ Hk(z)− Hk+1(z) + 3 2 ηLrk( √ dx + √ dy) ˜D. 24 C Proof of Theorem 4.3 Similarly, We start by defining a filtration F b k := σ (z0,I x 0 ,I y 0 ,J x 0 ,J y 0 , z1, ..., zk). Given zk, z+ k , ⟨∇xf (z+ k ), x+ k− x⟩ is bounded as follows: ⟨...

Pith tools

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