Stability and Performance Limits of Adaptive Primal-Dual Networks

Abstract

This work 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 have 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.

arXiv comment16 pages, 9 figures

References in corpus (7)

• Gossip Algorithms for Distributed Signal Processing
• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks
• Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
• Performance Limits for Distributed Estimation Over LMS Adaptive Networks
• Distributed Recursive Least-Squares: Stability and Performance Analysis
• Convergence and Applications of a Gossip-based Gauss-Newton Algorithm

Cited by in corpus (19)

• Proximity Without Consensus in Online Multi-Agent Optimization
• Diffusion LMS for Multitask Problems with Local Linear Equality Constraints
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• Diffusion LMS with Communication Delays: Stability and Performance Analysis
• Networked Signal and Information Processing
• Distributed Adaptive Learning Under Communication Constraints
• Almost surely constrained convex optimization
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems
• Decentralized Consensus Optimization with Asynchrony and Delays
• A Class of Randomized Primal-Dual Algorithms for Distributed Optimization
• Compressed Regression over Adaptive Networks
• Linearly Convergent Algorithm with Variance Reduction for Distributed Stochastic Optimization
• Performance Limits of Stochastic Sub-Gradient Learning, Part II: Multi-Agent Case
• Asynchronous Decentralized Stochastic Optimization in Heterogeneous Networks
• Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks
• Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization Over Random Networks
• Asymptotic Properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ Method with Diminishing Stepsize