Adaptive Penalty-Based Distributed Stochastic Convex Optimization

Abstract

In this work, we study the task of distributed optimization over a network of learners in which each learner possesses a convex cost function, a set of affine equality constraints, and a set of convex inequality constraints. We propose a fully-distributed adaptive diffusion algorithm based on penalty methods that allows the network to cooperatively optimize the global cost function, which is defined as the sum of the individual costs over the network, subject to all constraints. We show that when small constant step-sizes are employed, the expected distance between the optimal solution vector and that obtained at each node in the network can be made arbitrarily small. Two distinguishing features of the proposed solution relative to other related approaches is that the developed strategy does not require the use of projections and is able to adapt to and track drifts in the location of the minimizer due to changes in the constraints or in the aggregate cost itself. The proposed strategy is also able to cope with changing network topology, is robust to network disruptions, and does not require global information or rely on central processors.

13 pages, 1 figure

References in corpus (7)

• Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks
• Estimation Diversity and Energy Efficiency in Distributed Sensing
• Distributed Random Projection Algorithm for Convex Optimization
• Distributed Pareto Optimization via Diffusion Strategies
• Performance Limits for Distributed Estimation Over LMS Adaptive Networks
• On Distributed Online Classification in the Midst of Concept Drifts
• On the Learning Behavior of Adaptive Networks - Part I: Transient Analysis

Cited by in corpus (21)

• Multitask Diffusion Adaptation over Networks
• Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
• Dictionary Learning over Distributed Models
• Proximity Without Consensus in Online Multi-Agent Optimization
• Diffusion LMS for Multitask Problems with Local Linear Equality Constraints
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Networked Signal and Information Processing
• Distributed Constrained Online Learning
• Multi-hop Diffusion LMS for Energy-constrained Distributed Estimation
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• Distributed Stochastic Gradient Tracking Methods
• A Multitask Diffusion Strategy with Optimized Inter-Cluster Cooperation
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• A Distributed Stochastic Gradient Tracking Method
• Asynchronous adaptive networks
• A Flocking-based Approach for Distributed Stochastic Optimization
• Decentralized Dynamic Optimization for Power Network Voltage Control
• Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks
• Nested Distributed Gradient Methods with Stochastic Computation Errors
• On the Asymptotic Bias of the Diffusion-Based Distributed Pareto Optimization
• Swarming for Faster Convergence in Stochastic Optimization