In this work, we revisit a discrete implementation of the primal-descent dual-ascent gradient method applied to saddle-point optimization problems. Through a short proof, we establish linear (exponential) convergence of the algorithm for strongly-convex cost functions with Lipschitz continuous gradients. Unlike previous studies, we provide explicit upper bounds on the step-size parameters for stable behavior and on the resulting convergence rate and highlight the importance of having two different primal and dual step-sizes. We also explain the effect of the augmented Lagrangian penalty term on the algorithm stability and performance for the distributed minimization of aggregate cost functions over multi-agent networks.
Recently many first-order primal-dual gradient algorithms have been used to solve distributed optimization problems -- see @cite_27 @cite_28 @cite_1 @cite_20 @cite_3 and references therein, which are based on augmented Lagrangian (AL) formulations and incremental updates. They have been shown to achieve linear convergence under strong-convexity even though the consensus constraint matrix is not full rank. However, the analysis techniques used to establish the convergence of these methods depend on the particular consensus constraint matrix. Moreover, unlike these works, due to our unified Lagrangian and AL framework, we clarify the effect of the AL penalty term on the performance of these types of distributed algorithms. The work @cite_17 focuses on distributed optimization problems for mean-square-error costs and studies non-incremental primal-dual methods with identical step-sizes. It was found in @cite_17 that unlike AL methods, Lagrangian methods suffer from stability issues when the individual costs are not strongly-convex. This work generalize this result to general costs; moreover, we show that Lagrangian methods can use larger step-sizes compared to AL methods and, more importantly, we show how the AL penalty term affects the convergence rate.
@cite_28 @cite_1 @cite_3 @cite_27 @cite_20 @cite_17
2963649943 2782375002 1553365534 2075677880
This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit est... Recently, there has been significant progress in the development of distributed first-order methods. In particular, (2015) on the one hand and Qu and Li (2017) and (2016) on the other hand propose two different types of methods that are designed from very different perspectives. They achieve both exact and linear convergence when a constant step size is used—a favorable feature that was not achievable by most prior methods. In this paper, we unify, generalize, and improve convergence speed of the methods by (2015), Qu and Li (2017), and (2016), when the underlying network is static and undirected. We first carry out a unifying primal-dual analysis that sheds light on how these methods compare. The analysis reveals that a major difference between the methods is on how the primal error affects the dual error along iterations. We, then, capitalize on the insights from the analysis to derive a novel method that can reduce the negative effect of the primal error on the dual error. We establish for the proposed generalized method global R-linear convergence rate under strongly convex costs with Lipschitz continuous gradients. This paper develops the Decentralized Linearized Alternating Direction Method of Multipliers (DLM) that minimizes a sum of local cost functions in a multiagent network. The algorithm mimics operation of the decentralized alternating direction method of multipliers (DADMM) except that it linearizes the optimization objective at each iteration. This results in iterations that, instead of successive minimizations, implement steps whose cost is akin to the much lower cost of the gradient descent step used in the distributed gradient method (DGM). The algorithm is proven to converge to the optimal solution when the local cost functions have Lipschitz continuous gradients. Its rate of convergence is shown to be linear if the local cost functions are further assumed to be strongly convex. Numerical experiments in least squares and logistic regression problems show that the number of iterations to achieve equivalent optimality gaps are similar for DLM and ADMM and both much smaller than those of DGM. In that sense, DLM combines the rapid convergence of ADMM with the low computational burden of DGM. This paper studies distributed primal-dual strategies for adaptation and learning over networks from streaming data. Two first-order methods are considered based on the Arrow-Hurwicz (AH) and augmented Lagrangian (AL) techniques. Several revealing results are discovered in relation to the performance and stability of these strategies when employed over adaptive networks. The conclusions establish that the advantages that these methods exhibit for deterministic optimization problems do not necessarily carry over to stochastic optimization problems. It is found that they have narrower stability ranges and worse steady-state mean-square-error performance than primal methods of the consensus and diffusion type. It is also found that the AH technique can become unstable under a partial observation model, while the other techniques are able to recover the unknown under this scenario. A method to enhance the performance of AL strategies is proposed by tying the selection of the step-size to their regularization parameter. It is shown that this method allows the AL algorithm to approach the performance of consensus and diffusion strategies but that it remains less stable than these other strategies.