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

1. Problem Statement

The paper addresses the problem of distributed stochastic optimization over a peer-to-peer network of $n$ agents. The agents cooperatively solve the global minimization problem:
$$\min_{x \in \mathbb{R}^p} f(x) \triangleq \frac{1}{n} \sum_{i=1}^n f_i(x), \quad f_i(x) = \mathbb{E}_{\xi_i}[F_i(x, \xi_i)]$$
The core constraint is that agents operate in a black-box setting where they cannot compute or directly estimate gradients $\nabla f_i(x)$. Instead, they can only query noisy zeroth-order function values $F_i(x, \xi_i)$. This scenario is prevalent in networked control, robotic swarms, and sensor networks where agents rely on local sensor readings (e.g., concentration levels) or simulator outputs that are noisy and lack analytical derivatives.

Existing distributed zeroth-order (ZO) methods often rely on spherical perturbations, primal-dual tracking variables, or asymptotic analysis that fails to address practical "stalling" in flat, non-convex regions where finite-difference signals are weak and dominated by noise.

2. Methodology: ZOOM-PB

The authors propose ZOOM-PB, a coordinate-sampling distributed ZO algorithm equipped with a fractional-power powerball map. The method operates under a primal-only communication primitive, meaning agents exchange only their current decision variables $x_{i,k}$ without transmitting dual variables, gradient trackers, or raw data.

Key Algorithmic Components:

1. Coordinate Sampling: Instead of perturbing all $p$ dimensions simultaneously (spherical smoothing), each agent $i$ samples a small subset of coordinates $S_{i,k}$ at each iteration. This distributes the sampling burden and allows agents to explore different subspaces in parallel.
2. Zeroth-Order Estimation: Agents construct a coordinate-wise gradient estimate $\hat{g}_{i,k}$ using either one-point or two-point finite differences based on the sampled coordinates.
3. Nonlinear Feedback Gain (Powerball Map): The core innovation is the application of a componentwise nonlinear map $\sigma(\cdot, \gamma)$ to the estimated gradient before the update step:
   $$\sigma(g, \gamma) = \text{sgn}(g)|g|^\gamma, \quad \gamma \in [1/2, 1]$$
   • Weak Signal Amplification: When $|g| < 1$ (flat regions), the map amplifies the signal ($|g|^\gamma > |g|$), increasing the actuation magnitude without changing the descent direction.
   • Large Signal Attenuation: When $|g| > 1$, the map attenuates large stochastic estimates, preventing aggressive jumps.
   • Control Interpretation: This acts as a state-dependent nonlinear feedback gain rather than a change in the estimator itself.

Update Rule:

The update for agent $i$ at iteration $k$ is:
$$x_{i,k+1} = x_{i,k} - \alpha \sum_{j=1}^n L_{ij} x_{j,k} - \eta_k \sigma(\hat{g}_{i,k}, \gamma)$$
where $L$ is the graph Laplacian, $\alpha$ is a consensus weight, and $\eta_k$ is the step size. When $\gamma = 1$, ZOOM-PB reduces to the baseline linear-gain algorithm (ZOOM).

3. Key Contributions

The paper makes three primary contributions:

1. Algorithm Design: A fully distributed stochastic ZO algorithm that uses coordinate sampling and primal-only communication. It avoids the overhead of auxiliary tracking states or dual variables found in other methods (e.g., ZOD-PDA, ZODIAC).
2. Theoretical Guarantees:
   • Non-Convex Stationarity: Under standard smoothness, oracle-variance, and connectivity assumptions, ZOOM-PB achieves a leading convergence rate of $O(\sqrt{p/(nT)})$ for the expected squared gradient norm, where $p$ is the dimension and $T$ is the horizon.
   • PL Condition: Under the Polyak–Łojasiewicz (PL) condition, it attains a leading objective residual rate of $O(p/(nT))$.
   • Preservation of Order: The analysis proves that the nonlinear gain mechanism does not degrade the standard stochastic ZO convergence order, despite altering the local descent dynamics.
3. Finite-Time Effect Isolation: The paper isolates the finite-time benefits of the nonlinear gain by comparing $\gamma < 1$ against the linear endpoint $\gamma = 1$. The theoretical contribution is not an improvement in the asymptotic big-O exponent, but a modification of the local descent response in weak-signal regimes.

4. Results and Simulations

The paper validates the method through two numerical experiments:

• Black-Box Binary Classification: Using a non-linear least-squares benchmark with $p=100$ and $n=10$ agents.

  • Result: ZOOM-PB demonstrated faster empirical convergence in training loss compared to the linear-gain ZOOM and other state-of-the-art methods (ZO-GDA, ZONE-M, ZODIAC).
  • Accuracy: Final test accuracies were comparable (ZOOM-PB: 97.0%, ZOOM: 96.5%, ZODIAC: 97.0%), indicating the speedup did not compromise solution quality.

• UAV Source Seeking: A multi-agent control task where UAVs search for a hazardous emission source using only local noisy concentration measurements.

  • Result: In the "weak-signal" regime (far from the source where gradients are small and flat), ZOOM-PB showed significantly faster convergence in network-wide average concentration compared to the linear endpoint.
  • Significance: The nonlinear gain effectively amplified weak search directions without requiring additional communication states or centralized coordination.

5. Significance and Claims

The authors position ZOOM-PB as a complementary rather than a replacement for existing distributed ZO estimators.

• Modest Theoretical Claim: The paper explicitly states it does not claim to improve the minimax ZO exponent (the big-O rate). The theoretical contribution is demonstrating that a nonlinear feedback gain can be integrated into a distributed stochastic coordinate-ZO scheme without losing the best-known convergence order.
• Practical Impact: The significance lies in the finite-time behavior. By reshaping the local descent vector through a componentwise nonlinear gain, the method accelerates convergence in practical scenarios characterized by flat landscapes and weak signals, which are common in black-box networked control.
• Engineering Profile: The method offers a simpler communication profile (primal-only, no tracking variables) while achieving performance gains in weak-signal regimes, making it suitable for resource-constrained networked systems.

The paper concludes that future work will explore how this nonlinear gain interacts with quantized communication, event-triggering, and packet drops.