An optimal decentralized optimization algorithm for dynamic networks has been developed.

The research findings have been published in the proceedings of the NeurIPS 2024 conference. In today's world, many computational tasks require processing large volumes of data distributed across numerous computers or devices forming a network.

The traditional approach of processing data on a central server becomes inefficient when dealing with a high number of nodes and large data volumes. Decentralized optimization offers an alternative solution where each node in the network performs computations using only its local data and shares information solely with its neighbors. This significantly enhances the reliability, scalability, and security of the system.

This challenge is further complicated by the fact that the connections between nodes in the network can change over time. The dynamic nature of networks is characteristic of many real-world systems, such as wireless sensor networks, distributed machine learning systems, and future generations of federated learning. In such conditions, developing effective optimization algorithms poses a significant computational challenge. Until now, the scientific literature has lacked optimal algorithms, as well as theoretical estimates of the minimum number of communications and computations required to solve the decentralized optimization problem for non-smooth functions in dynamic networks.

A research group of Russian scientists has successfully overcome this barrier. “For the first time, we have established lower bounds on the complexity of communication and computation for solving non-smooth convex decentralized optimization problems in dynamically changing networks,” said Alexander Gasnikov, head of the Mathematical Methods of Optimization Laboratory at MIPT. “Moreover, we developed the first optimal algorithm that achieves these lower bounds and demonstrates significantly improved theoretical performance compared to existing methods.”

The developed algorithm is based on a special method for solving optimization problems—reducing it to solving a specifically saddle-point problem. This methodology allows reformulating the original problem into a more convenient equation for resolution. Unlike previous approaches, the new algorithm takes into account the non-smoothness of the functions stored at the nodes of the network. A key aspect is the application of an accelerated “forward-backward” method, modified to operate in a dynamic environment. The algorithm employs a feedback mechanism based on errors for effective information exchange in a network with variable topology.

The scientists proved the optimality of their algorithm by establishing strict lower bounds on the complexity of computations and communications. These bounds indicate that the developed algorithm not only operates efficiently but also achieves the theoretically best possible result for this class of problems. The theoretical results obtained are supported by preliminary numerical experiments demonstrating the superiority of the new algorithm in terms of convergence speed and scalability compared to existing methods.

To validate the algorithm, the researchers used a regression problem model with quadratic regularization on synthetic data. Experiments were conducted on various types of networks with different degrees of node connectivity, simulating different real-world system scenarios. The results showed a significant advantage of the new algorithm over known analogs, particularly as the number of nodes in the network and the complexity of the optimized function increased.

For comparison, the authors utilized a standard decentralized subgradient descent algorithm, which diverged and failed to solve the problem, a more advanced subgradient descent algorithm with Push-sum, and the ZO-SADOM algorithm, which employs randomized smoothing.

The improved subgradient descent algorithm uses the Push-Sum protocol for information aggregation, allowing it to handle a potentially asymmetric weight matrix of the network and ensuring proper convergence. However, the convergence speed of Subgradient-Push turned out to be low.

Although the ZO-SADOM algorithm can operate effectively in a changing network environment and with non-smooth functions, it has a worse complexity estimate compared to the newly developed algorithm by the authors. This is due to the additional computational costs associated with randomized smoothing and the non-optimal use of the ADMM method in the context of the problem. The authors successfully demonstrated that their new method circumvents these drawbacks.

Interestingly, even in scenarios where each node exchanges information only with its immediate neighbors (local minimum search), the new algorithm significantly outperforms existing analogs that require data exchange across the entire network.

The developed algorithm enables training large models on distributed computing resources while considering the unreliability of connections between nodes, optimizing resource distribution in wireless networks and energy systems, facilitating collective control of groups of robots and swarms of drones in dynamically changing environments, and creating effective and resilient federated learning systems that account for the dynamics of mobile networks.

The results obtained open new avenues for further research in decentralized optimization. In particular, the authors plan to explore the possibility of applying the developed algorithm to solving problems with non-convex functions and adapting the algorithm to more complex and realistic models of dynamic networks.

The development of an optimal algorithm for decentralized optimization in dynamic networks represents a significant breakthrough in computational mathematics and machine learning. The new algorithm exhibits high efficiency, scalability, and resilience to changes in network topology, opening new opportunities for addressing a wide range of practical problems.