Localization and Approximations for Distributed Non-convex Optimization

Hsu Kao, Vijay Subramanian

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.

Figure 1: (a) Communication graph; (b) and (c) show different local dependency sets where nodes only interact with a subset of the network.

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

Abstract

We consider the multi-cell joint power control and scheduling problem in cellular wireless networks as a weighted sum-rate maximization problem. This formulation is very general and applies to a wide range of applications and QoS requirements. The problem is inherently hard due to objective's non-convexity and the knapsack-like constraints. Moreover, practical system requires a distributed operation. We applied an existing algorithm proposed by Scutari et al. in distributed optimization literature to our problem. The algorithm performs local optimization followed by consensus update repeatedly. However, it is not fully applicable to our problem, as it requires all decision variables to be maintained at every base station (BS), which is impractical for large-scale networks; also, it relies on the Lipschitz continuity of the objective function's gradient, which does not hold here. We exploited the nature of our objective function, and proposed a localized version of the algorithm. Furthermore, we relaxed the requirements of Lipschitz continuity with the proximal approximation. Convergence to local optimal solutions was proved under some conditions. Future work includes proving the above results from a stochastic approximation perspective, and investigating non-linear consensus schemes to speed up the convergence.
BibTeX
@article{kao2023localization,
  author = {Hsu Kao and Vijay Subramanian},
  title = {{Localization and Approximations for Distributed Non-convex Optimization}},
  journal = {Journal of Optimization Theory and Applications},
  year = {2023},
  doi = {10.1007/s10957-023-02328-8},
}
Figure