Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition

Xinlei Yi, Shengjun Zhang, Tao Yang, Karl Henrik Johansson, Tianyou Chai

Abstract

This paper considers the distributed smooth optimization problem in which the objective is to minimize a global cost function formed by a sum of local smooth cost functions, by using local information exchange. The standard assumption for proving exponential/linear convergence of first-order methods is the strong convexity of the cost functions, which does not hold for many practical applications. In this paper, we first show that the continuous-time distributed primal-dual gradient algorithm converges to one global minimizer exponentially under the assumption that the global cost function satisfies the restricted secant inequality condition. This condition is weaker than the strong convexity condition since it does not require convexity and the global minimizers are not necessary to be unique. We then show that the discrete-time distributed primal-dual algorithm constructed by using the Euler's approximation method converges to one global minimizer linearly under the same condition. The theoretical results are illustrated by numerical simulations.

Introduction

In distributed optimization, a network of agents (such as robots, sensors, or power grid nodes) collaborates to minimize a global cost function. Each agent possesses only its local cost function and communicates solely with its immediate neighbors. To ensure these algorithms converge rapidly—exponentially in continuous-time or linearly in discrete-time—researchers typically assume strong convexity. This assumption implies the cost function landscape is a steep, single-bottomed bowl.

However, many practical problems, including least squares and logistic regression, do not satisfy strong convexity. They may feature flat regions or multiple global minimizers. This research bridges the gap between theory and practice by demonstrating that high-speed convergence is achievable under the more relaxed Restricted Secant Inequality (RSI) condition.

The Restricted Secant Inequality (RSI)

The RSI condition serves as a "Goldilocks" assumption: it is weaker than strong convexity because it does not require the function to be convex everywhere and allows for non-unique global minimizers. Crucially, it remains strong enough to ensure that every stationary point is a global minimum.

A key insight of this work is that while individual local cost functions must be smooth, only the global sum needs to satisfy the RSI condition to guarantee fast network-wide convergence.

Distributed Primal-Dual Algorithms

The authors analyze a distributed primal-dual gradient algorithm where primal variables represent local estimates of the optimal solution, and dual variables facilitate consensus, forcing agents to agree on a common value.

Figure 2: Evolution of local estimates $x_i(k)$ for 10 agents, showing rapid consensus and convergence to the global minimizer.

The study covers two implementations:

  1. Continuous-time: Modeled via ordinary differential equations (ODEs), ideal for physical control systems.
  2. Discrete-time: Derived using Euler’s approximation, this version is equivalent to the well-known EXTRA algorithm and is suited for digital implementation.

Convergence Results and Validation

Using Lyapunov stability theory, the paper proves that the distance to the set of global minimizers shrinks at a constant rate under the RSI condition. Specifically, continuous-time models achieve exponential convergence, while discrete-time models achieve linear convergence.

Numerical simulations with a non-convex cost function and a 10-agent ring network validate these findings. As shown in the residual plot, the error decreases linearly on a logarithmic scale, reaching a precision of $10^{-8}$ within a few hundred iterations.

Figure 3: The residual error plotted on a logarithmic scale, demonstrating the linear convergence rate predicted by the theory.

Conclusion and Future Directions

This work provides a unified framework for fast distributed optimization without the strict requirement of strong convexity. Future research may address the conservative nature of current theoretical step-size bounds and explore "fully" distributed parameters that do not require global network knowledge (like Laplacian eigenvalues). Additionally, extending these results to asynchronous networks or even more general conditions, such as the Polyak-Łojasiewicz (PL) condition, remains an active area of interest.

Summary updated

Abstract

This paper considers the distributed smooth optimization problem in which the objective is to minimize a global cost function formed by a sum of local smooth cost functions, by using local information exchange. The standard assumption for proving exponential/linear convergence of first-order methods is the strong convexity of the cost functions, which does not hold for many practical applications. In this paper, we first show that the continuous-time distributed primal-dual gradient algorithm converges to one global minimizer exponentially under the assumption that the global cost function satisfies the restricted secant inequality condition. This condition is weaker than the strong convexity condition since it does not require convexity and the global minimizers are not necessary to be unique. We then show that the discrete-time distributed primal-dual algorithm constructed by using the Euler's approximation method converges to one global minimizer linearly under the same condition. The theoretical results are illustrated by numerical simulations.
BibTeX
@inproceedings{yi2020exponential,
  author = {Xinlei Yi and Shengjun Zhang and Tao Yang and Karl Henrik Johansson and Tianyou Chai},
  title = {{Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition}},
  booktitle = {IFAC-PapersOnLine},
  year = {2020},
  doi = {10.1016/j.ifacol.2020.12.383},
}
Figure