Fixed-time Distributed Optimization under Time-Varying Communication Topology

Kunal Garg, Mayank Baranwal, Alfred O. Hero, Dimitra PanagouarXiv 2019 · arXiv

Abstract

This paper presents a novel method for solving distributed optimization problems within a fixed time over time-varying communication topologies. By investigating the first nonlinear protocol for achieving fixed-time convergence independent of initial conditions, the study addresses critical gaps in convergence speed and restrictive local assumptions. For global objective functions that are strictly convex or satisfy the Polyak-Łojasiewicz (PL) inequality, the authors develop a first-order, Hessian-free approach that ensures rapid convergence to the global optimum. The results demonstrate that the proposed algorithm maintains fixed-time stability even after discretization, making it highly effective for practical applications like training neural networks.

Introduction

In distributed optimization, a network of agents (sensors, robots, or servers) collaborates to minimize a global cost function. Each agent possesses only a "private" portion of the data and must communicate with neighbors to reach a consensus on the optimal solution. Traditional methods often suffer from asymptotic convergence—where the solution is approached but never reached in a set timeframe—and require every agent's local function to be strongly convex. This paper introduces the FxTS-DOA (Fixed-time stable Distributed Optimization Algorithm) to overcome these hurdles.

Methodology

The FxTS-DOA architecture relies on two primary components:

  1. Fixed-time Parameter Estimation: Agents use a consensus protocol to estimate global quantities, such as the sum of all gradients, within a fixed temporal window.
  2. Fixed-time Consensus: A second layer ensures that all agents' internal states synchronize rapidly to the same value.

Key Innovations

  • PL Inequality Extension: The math is extended to functions satisfying the Polyak-Łojasiewicz (PL) inequality. This significant relaxation of convexity allows the algorithm to handle non-convex problems, such as deep learning.
  • Consistent Discretization: The authors provide a rigorous proof that using standard Euler discretization preserves fixed-time convergence behavior, ensuring the theoretical speed translates to real-world code.
  • Hessian-Free Protocol: Unlike second-order methods that require exchanging complex Hessian matrices, this method is first-order, requiring only gradient information, which reduces communication overhead.

Experimental Evaluation

The researchers evaluated FxTS-DOA on two primary tasks: distributed linear regression and MNIST handwritten digit classification.

Distributed Linear Regression

Using a synthetic dataset of 15,000 points across five agents, the goal was to find a linear relationship for 3D inputs. As shown in the Mean-squared-error (MSE) analysis, all agents converged to the optimal solution in very few epochs, demonstrating the algorithm's independence from initial error magnitudes.

Mean-squared-errors (MSE) vs Epochs for distributed linear regression across five agents.

MNIST Classification

The algorithm was used to train a convolutional neural network (CNN) with 2.8 million parameters across three servers. FxTS-DOA achieved approximately 94% test accuracy in less than 10 epochs, significantly outperforming Decentralized Stochastic Gradient Descent (DSGD) in both accuracy and consensus speed.

Performance on MNIST: Test accuracy (top) and consensus errors (bottom) comparing FxTS-DOA and DSGD.

Key Insights and Results

  • Global over Local: The study proves that only the collective team goal needs to be well-behaved (strongly convex or PL), not every individual agent's function.
  • Fixed-time Stability: Convergence time has a hard upper bound that does not increase even if the starting point is far from the optimum.
  • Robustness: The algorithm successfully handled the non-convex nature of neural network training, confirming the practical utility of the PL-inequality extension.

Conclusion and Future Work

The FxTS-DOA provides a robust framework for fast, distributed optimization over dynamic networks. While the current focus is on unconstrained optimization, future work will explore adapting the framework for private convex constraints and further refining step-size sensitivity to balance speed with final precision.

Summary updated

Abstract

This paper presents a method to solve distributed optimization problem within a fixed time over a time-varying communication topology. Each agent in the network can access its private objective function, while exchange of local information is permitted between the neighbors. This study investigates first nonlinear protocol for achieving distributed optimization for time-varying communication topology within a fixed time independent of the initial conditions. For the case when the global objective function is strictly convex, a second-order Hessian based approach is developed for achieving fixed-time convergence. In the special case of strongly convex global objective function, it is shown that the requirement to transmit Hessians can be relaxed and an equivalent first-order method is developed for achieving fixed-time convergence to global optimum. Results are further extended to the case where the underlying team objective function, possibly non-convex, satisfies only the Polyak-Łojasiewicz (PL) inequality, which is a relaxation of strong convexity.
BibTeX
@misc{garg2019fixed,
  author = {Kunal Garg and Mayank Baranwal and Alfred O. Hero and Dimitra Panagou},
  title = {{Fixed-time Distributed Optimization under Time-Varying Communication Topology}},
  year = {2019},
  eprint = {1905.10472},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.10472},
}
Figure