Abstract
Distributed non-convex optimization is a cornerstone of modern network systems, yet it faces significant challenges regarding communication overhead and mathematical stability. This paper presents a novel framework that "localizes" variables to reduce bandwidth requirements and employs "proximal approximations" to handle functions with unbounded gradients. By leveraging local dependency sets and smoothing techniques like the Lasry-Lions envelope, the proposed Localized Proximal Inexact NEXT algorithm ensures convergence under broader conditions. Numerical simulations in multi-cellular wireless resource allocation demonstrate a four-fold throughput increase compared to traditional methods, highlighting the framework's efficiency and robustness.
Introduction
The rise of 5G, sensor swarms, and large-scale machine learning has made distributed optimization more critical than ever. In these environments, nodes must collaboratively solve complex non-convex problems. However, existing state-of-the-art algorithms often suffer from "communication bloat," requiring every node to track global decision variables. Furthermore, many real-world objective functions, such as logarithmic rates in wireless communications, exhibit unbounded gradients that can lead to numerical instability or failure in standard algorithms. This paper tackles these gaps by allowing nodes to focus only on "local" variables and by "smoothing" difficult functions to ensure mathematical stability.
Methods
The researchers introduce the Localized Proximal Inexact NEXT algorithm, which addresses these issues through two primary innovations: Localization and Proximal Approximations.
Localization and Dependency Sets
Instead of requiring global knowledge, the algorithm exploits the inherent block structure of network problems. Nodes only track and communicate variables within their "local dependency sets." For instance, a base station only needs to consider its own power levels and those of its immediate neighbors that cause interference. This significantly reduces memory and bandwidth consumption.
Proximal Approximations
To stabilize functions with "nasty" gradients, the authors use a sequence of smooth surrogate functions. They employ the Lasry-Lions envelope—a double envelope technique—to smooth the objective while preserving its minimizers. As the algorithm progresses, this approximation is gradually "tightened," ensuring convergence to a stationary point of the original function. The algorithm also incorporates Successive Convex Approximation (SCA) and a "Y-Consensus" trick, where nodes track a "gradient trace" to estimate the aggregate influence of the entire network while only communicating with local neighbors.
Evaluation and Results
The framework was tested using synthetic benchmarks and a 19-cell wrap-around wireless simulation. The synthetic tests confirmed that the proximal approach remains stable where traditional methods oscillate due to unbounded gradients.
In the wireless simulation, the proposed localized methods achieved an average throughput gain of approximately 400% over single-cell (SC) methods. Notably, the fully localized version was not only more scalable but also converged in significantly fewer iterations than globalized versions in certain fairness scenarios. These results demonstrate that sparsity in network dependency is a feature that can be exploited for global optimality without global knowledge.
Conclusion and Future Work
By formalizing local dependency sets and introducing robust smoothing techniques, this work provides a scalable and stable path for distributed non-convex optimization. While significant performance gains were observed in wireless resource allocation, the authors note that future work is needed to develop robust integer rounding schemes for discrete variables and to address unbounded gradients specifically on the boundary of constraint sets. Optimizing the communication graph itself for dynamic networks remains an open and promising next step.
Summary updated