Pith. sign in

REVIEW 3 major objections 4 minor 18 references

Nonlinear-Gain Distributed Zeroth-Order Optimization for Networked Black-Box Control

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

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

Pith's one-line read A distributed zeroth-order optimizer with a fractional-power feedback gain reaches the leading nonconvex rate O(sqrt(p/(nT))) while exchanging only primal states.

desk verdict Neat powerball-in-coordinate-ZO idea, but the headline rate is not proven: Lemma 1's variance bound misses the p^2/n_c scaling, so the advertised small-subset speedup collapses. read the letter →

arxiv 2605.25306 v4 pith:TAETDGOW submitted 2026-05-25 eess.SY cs.SY

Shengjun Zhang , Tingyi Liu , Heng Zhang , Dong Xie This is my paper · ORCID
classification eess.SYcs.SY
keywords distributedzeroth-orderoptimizationpowerballmapcoordinatesamplingprimal-onlyconsensusnonconvexstationarityPolyak–Łojasiewiczconditionblack-boxcontrolmulti-agentsystems
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

The paper aims to establish that a coordinate-sampled distributed zeroth-order method can incorporate a fractional-power nonlinear gain—the powerball map—without losing the leading convergence rate. In nonconvex stochastic settings, the network-average squared gradient decays as O(sqrt(p/(nT))), and under the Polyak–Łojasiewicz condition the objective residual decays as O(p/(nT)). The update transmits only primal decision vectors, so the nonlinearity is a local feedback gain rather than a change in communication or oracle schedule. A reader would care because black-box networked control problems, such as multi-vehicle source seeking, often operate in flat regions where the estimated descent signal is weak and the gain accelerates the transient.

What carries the argument

The load-bearing object is the powerball map sigma(g,gamma)=sgn(g)|g|^gamma, applied componentwise to each agent's coordinate-sampled ZO estimate. It amplifies small components, attenuates large ones, and preserves sign; combined with a primal-only consensus step and a Lyapunov function that couples average descent with disagreement, it allows the proof to bound the nonlinear residual directly from the raw oracle assumptions.

What would settle it

Compute the empirical second moment of the one-point coordinate estimator (4) with n_c=1 on a smooth quadratic in p=100 dimensions: if it grows like p^2 rather than p, then Lemma 1's bound (22) fails for small n_c and the theorem rates would need to be re-derived with an explicit n_c dependence.

Watch

Extended reading notes

Core claim

The paper's central claim is that a componentwise fractional-power nonlinearity, sigma(g,gamma)=sgn(g)|g|^gamma for gamma in [1/2,1], can be inserted into a coordinate-sampled distributed zeroth-order recursion without losing the leading convergence order. When each agent builds a coordinate ZO estimate from a small random subset of coordinates, applies the powerball map locally, and exchanges only primal decisions with neighbors, the network-average gradient norm decays as O(sqrt(p/(nT))) in nonconvex settings and the objective residual decays as O(p/(nT)) under the Polyak–Łojasiewicz condition. The nonlinearity is thus a state-dependent feedback gain that reshapes weak versus large local e

Load-bearing premise

The proof relies on each agent's coordinate-sampled ZO estimate having per-agent mean squared error O(p) independent of how few coordinates are sampled; for small subsets the natural variance is larger, roughly p^2/n_c, so the dimension dependence in the stated rates may be optimistic.

Editorial extensions

If this is right

  • Adding the powerball gain costs nothing asymptotically: the same O(sqrt(p/(nT))) stationarity guarantee holds as for the linear endpoint, so practitioners can use it without sacrificing the order of convergence.
  • Under the PL condition, the objective residual O(p/(nT)) gives linear speedup in the number of agents for black-box objectives with a unique global optimum.
  • Because only primal states are exchanged, communication payload per round is one p-vector, independent of gamma and of the number of sampled coordinates.
  • The nonlinear gain is the sole difference from the linear endpoint in the experiments, so observed speed-ups are attributable to gain shaping rather than extra oracle calls.

Reading between the lines

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

  • The per-agent variance bound in Lemma 1 assumes E[||eps||^2] ≤ C p independent of subset size n_c; for the coordinate estimator in (4)-(5) the natural variance scales like p^2/n_c, so the stated p-dependence may only hold when n_c is proportional to p. If small n_c is used, the dimension term in the rates likely becomes worse.
  • If the analysis were reworked with an explicit n_c, one could trade off function-query budget against dimension dependence, which the current theorem statements leave implicit.
  • The powerball map may be interpreted as a per-coordinate adaptive step size; in that view, the paper shows such state-dependent gains can be inserted into distributed consensus without breaking the Lyapunov recursion, which may extend to event-triggered or compressed communication variants.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proposes ZOOM-PB, a distributed stochastic zeroth-order method in which each agent samples n_c coordinates, forms a coordinate-wise finite-difference estimator scaled by p/n_c, applies a componentwise powerball nonlinearity sigma(g,gamma)=sgn(g)|g|^gamma, and runs consensus with only primal states. The central theoretical claim is that, under smoothness, gradient-noise, and bounded-gradient assumptions, the method attains O(sqrt(p/(nT))) stationarity in nonconvex problems and O(p/(nT)) PL objective residual, with an O(n/T) consensus transient. The proof rests on Lemma 1, which asserts a per-agent ZO estimator second moment O(p) and an averaged variance O(p/n). The numerical section isolates the powerball gain from the linear endpoint ZOOM.

Significance. The intended contribution — a primal-only nonlinear-gain ZO method that preserves known distributed ZO rates — is interesting and the problem is well motivated. The ablation against the linear endpoint is a good design, and the communication/query budgets are stated cleanly. If the rate claim held, the method would be a useful addition. However, the proof of the central rate does not withstand scrutiny: the coordinate-subset estimator's variance is Theta(p^2/n_c), so the advertised small-subset regime has a much worse dimension dependence. I do not see a circularity problem; the failure is a concrete moment estimate, not a fitted parameter.

major comments (3)
  1. [Appendix A, Eq. (22); Lemma 1] For the coordinate estimator (4)/(5), conditioning on F_k and writing a_i as the vector of smoothed local coordinate derivatives, uniform sampling of n_c coordinates with scaling p/n_c gives E[||g_tilde_i||^2 | F_k] = (p/n_c) * sum_{j=1}^p E[a_{i,j}^2 | F_k]. Under Assumption 3 each E[a_{i,j}^2 | F_k] can be of order 1 in the worst case, so the second moment is Theta(p^2/n_c), not O(p). Eq. (22) is therefore false when n_c < p; the correct averaged variance in Eq. (24) is at best C p^2/(n_c n). The constants in Lemma 1 are allowed to depend on n_c, but the explicit p-dependence cannot be hidden. This invalidates the Lyapunov recursion (8b) and the convergence theorems that depend on it.
  2. [Theorems 1-2; Proposition 2] With the corrected variance, the stationarity bound degrades to O((p/n_c)*sqrt(p/(nT))) + O(n/T), and only n_c = Theta(p) recovers the advertised O(sqrt(p/(nT))). Similarly, the PL residual in Theorem 2 becomes O(p^2/(n_c n T)) rather than O(p/(nT)). Since the paper motivates 'small coordinate subsets' and assigns different agents to different subspaces, this is a load-bearing change: the central dimension-rate claim fails in the advertised regime. Proposition 2 inherits the same issue, because gamma=1 does not alter the estimator variance.
  3. [Appendix C, Eq. (13) and Theorem 1] There is a second, independent problem with the smoothing schedule. With delta_k^2 <= C/(sqrt(p)*sqrt(n)*sqrt(k+1)), summing (13) gives p^2 * eta * sum delta_k^2 = Theta(p^{3/2} sqrt(T)/sqrt(n)), while the statistical term is p T eta^2 = n. After dividing by n T eta, the bias contribution is (p/n)*sqrt(p/(nT)), not O(sqrt(p/(nT))), unless p = O(n). Theorem 1 is not conditioned on p = O(n), so the stated rate is not established even if the estimator-variance issue is set aside. A different delta schedule or an explicit p/n restriction is needed.
minor comments (4)
  1. [Abstract] The displayed rate appears as 'O(\n p\n p/(nT))' in the full text; this should be O(sqrt(p/(nT))).
  2. [Section IV] The text uses 'UA V' in several places (e.g., 'UA V swarm', 'UA V source seeking'); this should be 'UAV'.
  3. [Eq. (3) and Proposition 1] The ratio |sigma(g,gamma)|/|g| is undefined at g=0; Proposition 1 states g != 0, but Eq. (3) should state this restriction as well.
  4. [Theorem 2 proof] The derivation of the consensus bound E[||x_T||_K^2/n] = O(p/T^2) is sketched as 'applying the disagreement part once more'; this step is not transparent and should be expanded, especially because the driver contains gradient terms that are not obviously bounded.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: convergence rates are derived from explicit assumptions; self-citations are only baselines.

full rationale

The paper's derivation chain is explicit: Algorithm 1 defines the update; Lemma 1 derives a Lyapunov recursion (Eq. (8a)–(8b)) from Assumptions 1–4; Theorem 1 sums that recursion with the chosen stepsize and smoothing schedules; Theorem 2 substitutes the PL condition into the same recursion. The rates O(sqrt(p/(nT))) and O(p/(nT)) appear as the result of substituting eta = sqrt(n/(pT)) and the delta schedule into the summed bound, not as assumptions or fitted targets. No parameter is fitted to reproduce a convergence rate, and no theorem condition is chosen based on the desired conclusion. The powerball map properties (Proposition 1, Eqs. (26)–(27)) are elementary consequences of |g|^gamma and are not imported as an unproved ansatz. Self-citations [14], [15], [18] appear only in the related-work comparison and Table I; they are not used in the proof of Lemma 1 or in the theorems. The numerical section is an ablation of the gamma=1 endpoint under matched budgets, not a claim that a fitted parameter predicts the theoretical rate. There is therefore no step in which a 'prediction' reduces to its input by construction. A separate caveat: Eq. (22) asserts E||epsilon_i,k||^2 <= C p 'after the usual coordinate-sampling scaling' without deriving the n_c-dependence; this may be a soundness gap for small n_c, but it is not circular reasoning — the bound is not defined in terms of the theorem's output, and no quantity is fitted to force the result.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new physical entities are introduced. The central proof leans on standard smoothness, noise, connectivity, and PL assumptions, plus the path-dependent Assumption 4. The decisive unproved ingredient is the O(p) estimator-variance bound; if it is replaced by the standard O(p²/n_c), the advertised √p rate is not obtained.

free parameters (2)
  • γ (powerball exponent) = 0.7 default in simulations; theory allows any γ∈[1/2,1]
    Controls amplification/attenuation shape; not fitted to the convergence theorem but chosen by hand in experiments and central to the claimed empirical speedup.
  • Step-size and smoothing schedule constants (α, κδ, κη, t1) = not fully specified numerically
    Theorem gives ranges/forms (e.g., α < ρ²(L)/(2ρ(L²)), η_k=√n/√(pT), δ_k ≤ κδ/(p^{1/4} n^{1/4} (k+1)^{1/4})) but not the exact values needed to reproduce the figures.
assumptions (4)
  • domain assumption Assumption 4: there exists deterministic G≥1 such that ∥∇f(x̄_k)∥∞≤G along the generated average sequence
    Used in Lemma 1/Appendix B to lower-bound u^Tσ(u,γ)≥G^{γ-1}||u||². It is path-dependent and not known a priori, though it holds under compact level sets.
  • domain assumption Assumptions 2–3: F_i(·,ξ) is L_f-smooth, coordinate gradient noise variance bounded by ζ², and local gradient heterogeneity bounded by σ²₂
    Standard stochastic-smooth oracle model for ZO analysis; without it the finite-difference estimator has no controlled variance.
  • domain assumption Assumption 5: global function f satisfies the PL condition with known constant ν
    Needed only for Theorem 2's objective-residual rate; restricts problem class but is standard in nonconvex optimization.
  • ad hoc to paper Eq. (22): E||ε_{i,k}||²|F_k ≤ Cp for the coordinate-subset estimator
    This is the contested load-bearing step. The standard variance for a uniformly sampled coordinate subset of size n_c is O(p²/n_c)+O((p/n_c)||∇f||²), so the O(p) bound only holds for n_c=Θ(p).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Nonlinear-Gain Distributed Zeroth-Order Optimization for Networked Black-Box Control." pith.science (2026). https://pith.science/paper/TAETDGOW

@misc{pith2026260525306,
  author       = {Pith},
  title        = {Pith review of: Nonlinear-Gain Distributed Zeroth-Order Optimization for Networked Black-Box Control},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TAETDGOW}},
  note         = {Machine review of arXiv:2605.25306}
}
abstract

This letter studies distributed stochastic optimization over a peer-to-peer network when agents can query only zeroth-order function values. We propose ZOOM-PB, a coordinate-sampling method that blends each local ZO estimate with a fractional-power response while maintaining only a primal state. The raw estimate is retained as a linear anchor, and the nonlinear mixing weight is coupled to the optimization stepsize. This design is motivated by a basic obstruction: transforming heterogeneous or noisy local estimates before averaging can reverse the network direction. We bound that nonlinear residual directly from the raw oracle assumptions instead of imposing an aggregate-alignment condition. With a smooth stochastic-function oracle and a connected graph, ZOOM-PB attains the nonconvex stationarity order $\mathcal{O}(\sqrt{p/(nT)})$ and a Polyak--{\L}ojasiewicz statistical term of order $\mathcal{O}(p/(nT))$, after an explicit initialization transient. Numerical examples compare ZOOM-PB with seven distributed ZO baselines under matched query and message budgets.

Figures

Figures reproduced from arXiv: 2605.25306 by the authors.

Figure 1
Figure 1. Training-loss comparison on the black-box binary classification [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Source-estimate trajectories under ZOOM-PB. Agents use only local [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Network-wide average concentration in the UAV source-seeking [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references

  1. [1]

    Cooperative source seeking via networked multi-vehicle systems,

    Z. Li, K. You, and S. Song, “Cooperative source seeking via networked multi-vehicle systems,”Automatica, vol. 115, p. 108853, 2020

    2020

  2. [2]

    J. C. Spall,Introduction to stochastic search and optimization: esti- mation, simulation, and control. John Wiley & Sons, 2005, vol. 65

    2005

  3. [3]

    A. R. Conn, K. Scheinberg, and L. N. Vicente,Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. SIAM Philadelphia, 2009

    2009

  4. [4]

    Audet and W

    C. Audet and W. Hare,Derivative-Free and Blackbox Optimization. Springer, 2017

    2017

  5. [5]

    Derivative-free optimiza- tion methods,

    J. Larson, M. Menickelly, and S. M. Wild, “Derivative-free optimiza- tion methods,”Acta Numerica, vol. 28, pp. 287–404, 2019

    2019

  6. [6]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming,

    S. Ghadimi and G. Lan, “Stochastic first-and zeroth-order methods for nonconvex stochastic programming,”SIAM Journal on Optimization, vol. 23, no. 4, pp. 2341–2368, 2013

    2013

  7. [7]

    A compre- hensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order,

    X. Lian, H. Zhang, C.-J. Hsieh, Y . Huang, and J. Liu, “A compre- hensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order,” inAdvances in Neural Information Processing Systems, 2016, pp. 3054–3062

    2016

  8. [8]

    Random gradient-free minimization of convex functions,

    Y . Nesterov and V . Spokoiny, “Random gradient-free minimization of convex functions,”Foundations of Computational Mathematics, vol. 17, no. 2, pp. 527–566, 2017

    2017

Show all 18 references
  1. [9]

    Zeroth-order stochastic variance reduction for nonconvex optimiza- tion,

    S. Liu, B. Kailkhura, P.-Y . Chen, P. Ting, S. Chang, and L. Amini, “Zeroth-order stochastic variance reduction for nonconvex optimiza- tion,” inAdvances in Neural Information Processing Systems, 2018, pp. 3727–3737

    2018

  2. [10]

    Randomized gradient-free method for multia- gent optimization over time-varying networks,

    D. Yuan and D. W. Ho, “Randomized gradient-free method for multia- gent optimization over time-varying networks,”IEEE Transactions on Neural Networks and Learning Systems, vol. 26, no. 6, pp. 1342–1347, 2014

    2014

  3. [11]

    Gradient-free method for distributed multi- agent optimization via push-sum algorithms,

    D. Yuan, S. Xu, and J. Lu, “Gradient-free method for distributed multi- agent optimization via push-sum algorithms,”International Journal of Robust and Nonlinear Control, vol. 25, no. 10, pp. 1569–1580, 2015

    2015

  4. [12]

    Distributed zero-order algorithms for nonconvex multiagent optimization,

    Y . Tang, J. Zhang, and N. Li, “Distributed zero-order algorithms for nonconvex multiagent optimization,”IEEE Transactions on Control of Network Systems, vol. 8, no. 1, pp. 269–281, 2020

    2020

  5. [13]

    ZONE: Zeroth-order non- convex multiagent optimization over networks,

    D. Hajinezhad, M. Hong, and A. Garcia, “ZONE: Zeroth-order non- convex multiagent optimization over networks,”IEEE Transactions on Automatic Control, vol. 64, no. 10, pp. 3995–4010, 2019

    2019

  6. [14]

    Zeroth-order algo- rithms for stochastic distributed nonconvex optimization,

    X. Yi, S. Zhang, T. Yang, and K. H. Johansson, “Zeroth-order algo- rithms for stochastic distributed nonconvex optimization,”Automatica, vol. 142, p. 110353, 2022

    2022

  7. [15]

    Con- vergence analysis of nonconvex distributed stochastic zeroth-order coordinate method,

    S. Zhang, Y . Dong, D. Xie, L. Yao, C. P. Bailey, and S. Fu, “Con- vergence analysis of nonconvex distributed stochastic zeroth-order coordinate method,” inIEEE Conference on Decision and Control, 2021

    2021

  8. [16]

    Zeroth-order feedback optimization for cooperative multi-agent systems,

    Y . Tang, Z. Ren, and N. Li, “Zeroth-order feedback optimization for cooperative multi-agent systems,”Automatica, vol. 148, p. 110741, 2023

    2023

  9. [17]

    On the powerball method: Variants of descent methods for accelerated optimization,

    Y . Yuan, M. Li, J. Liu, and C. Tomlin, “On the powerball method: Variants of descent methods for accelerated optimization,”IEEE Control Systems Letters, vol. 3, no. 3, pp. 601–606, 2019

    2019

  10. [18]

    Accelerated zeroth-order algorithm for stochastic distributed non-convex optimization,

    S. Zhang and C. P. Bailey, “Accelerated zeroth-order algorithm for stochastic distributed non-convex optimization,” in2022 American Control Conference (ACC). IEEE, 2022, pp. 4274–4279

    2022

Pith tools

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