Abstract
In this paper, we consider distributed optimization problems over a multi-agent network, where each agent can only partially evaluate the objective function, and it is allowed to exchange messages with its immediate neighbors. Differently from all existing works on distributed optimization, our focus is given to optimizing a class of non-convex problems, and under the challenging setting where each agent can only access the zeroth-order information (i.e., the functional values) of its local functions. For different types of network topologies such as undirected connected networks or star networks, we develop efficient distributed algorithms and rigorously analyze their convergence and rate of convergence (to the set of stationary solutions). Numerical results are provided to demonstrate the efficiency of the proposed algorithms.
Introduction
Distributed optimization has traditionally relied on two major assumptions: the convexity of objective functions and the availability of gradient information. However, real-world applications in machine learning and engineering often involve non-convex landscapes with multiple local minima. Furthermore, in scenarios like simulation-based optimization, calculating gradients may be computationally prohibitive or mathematically impossible. In such "black-box" settings, agents only have access to zeroth-order information—the function values themselves.
This paper introduces two novel algorithms, ZONE-M and ZONE-S, to address these challenges. These methods combine primal-dual optimization techniques with zeroth-order gradient estimation, providing the first distributed framework for non-convex optimization with rigorous global convergence guarantees.
Proposed Algorithms: ZONE-M and ZONE-S
The researchers tailor their approach to two distinct network architectures, as illustrated in Figure 1.
ZONE-M (Mesh Networks)
ZONE-M is designed for decentralized mesh networks where agents are connected in an arbitrary, undirected graph. The algorithm operates within a primal-dual framework based on the Augmented Lagrangian. To circumvent the lack of explicit gradients, it employs Gaussian smoothing. Agents estimate local slopes by sampling function values at random points around their current position. This allows the network to reach a consensus on the solution even without direct derivative information.
ZONE-S (Star Networks)
For networks featuring a central controller (master-worker setup), the authors propose ZONE-S. This architecture allows for more sophisticated operations. Specifically, the central controller can handle non-smooth terms, such as $L_1$ regularization for sparsity, which are difficult to manage in a fully decentralized mesh. ZONE-S also utilizes a non-uniform sampling strategy, where the controller prioritizes updates from agents with higher local function complexity, thereby accelerating convergence.
The core innovation in both algorithms is the integration of zeroth-order gradient estimators into a Method of Multipliers framework. This ensures stability and consensus across the network despite the inherent noise in gradient estimation and the complexity of non-convex objectives.
Experimental Evaluation
The algorithms were evaluated using synthetic non-convex functions (combinations of sigmoid and logarithmic functions) and high-dimensional regression problems with $L_1$-norm constraints. Key findings include:
- Efficiency: ZONE-M demonstrated significantly faster convergence and higher precision compared to the Randomized Gradient Free (RGF) algorithm.
- Centralized Comparison: ZONE-S outperformed standard centralized zeroth-order methods like ZO-GD and ZO-SGD, highlighting the benefits of leveraging distributed problem structures.
- Scalability: Both algorithms remained stable as network sizes increased from 10 to 80 nodes, maintaining low consensus error.
Discussion and Conclusion
The research proves that global convergence to a stationary point is achievable in distributed, non-convex settings using only function evaluations. While there is a trade-off in speed—convergence is sublinear compared to first-order methods—the approach is mathematically robust.
A key insight is that network topology dictates capability: the star network (ZONE-S) is fundamentally better at handling non-smooth constraints because the central hub can perform complex proximal operations. However, because zeroth-order estimation is noisy, the algorithms converge to a neighborhood of a stationary point rather than an exact point, with the neighborhood size determined by the smoothing parameter $\mu$. Future work may focus on extending these frameworks to fully asynchronous networks.
Summary updated