ADD-OPT: Accelerated Distributed Directed Optimization

MaRDI QIDQ5375217zbMATH OpenFDO

Authors Chenguang Xi, Ran Xin, Usman A. Khan

Publication date 14 September 2018

Full work available at URL https://arxiv.org/abs/1607.04757

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Convex programming (90C25)

Abstract: In this paper, we consider distributed optimization problems where the goal is to minimize a sum of objective functions over a multi-agent network. We focus on the case when the inter-agent communication is described by a strongly-connected, emph{directed} graph. The proposed algorithm, ADD-OPT (Accelerated Distributed Directed Optimization), achieves the best known convergence rate for this class of problems,~$O(m{u}^k),0<mu<1$, given strongly-convex, objective functions with globally Lipschitz-continuous gradients, where~$k$ is the number of iterations. Moreover, ADD-OPT supports a wider and more realistic range of step-sizes in contrast to existing work. In particular, we show that ADD-OPT converges for arbitrarily small (positive) step-sizes. Simulations further illustrate our results.

Recommendations

• An augmented Lagrangian method for distributed optimization
• An accelerated exact distributed first-order algorithm for optimization over directed networks
• Distributed optimization over networks
• Approximations in Distributed Optimization
• Distributed optimization with arbitrary local solvers
• Revisiting EXTRA for Smooth Distributed Optimization
• Decentralized Dynamic Optimization Through the Alternating Direction Method of Multipliers
• D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization
• Distributed optimization: advances in theories, methods, and applications
• Harnessing Smoothness to Accelerate Distributed Optimization

Cited in

(31)

• Distributed decision-coupled constrained optimization via proximal-tracking
• Surplus-based accelerated algorithms for distributed optimization over directed networks
• Triggered gradient tracking for asynchronous distributed optimization
• Tracking-ADMM for distributed constraint-coupled optimization
• A distributed algorithm for solving mixed equilibrium problems
• Distributed nonconvex constrained optimization over time-varying digraphs
• A distributed methodology for approximate uniform global minimum sharing
• ADD-OPT
• Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
• On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• scientific article; zbMATH DE number 7307473 (Why is no real title available?)
• An event-triggering algorithm for decentralized stochastic optimization over networks
• An accelerated exact distributed first-order algorithm for optimization over directed networks
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
• Resilient consensus‐based distributed optimization under deception attacks
• Distributed online convex optimization with multiple coupled constraints: a double accelerated push-pull algorithm
• Linear convergence of distributed estimation with constraints and communication delays
• Dynamics based privacy preservation in decentralized optimization
• A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks
• Optimal gradient tracking for decentralized optimization
• A distributed accelerated algorithm based on a unified momentum method
• Balancing communication and computation in gradient tracking algorithms for decentralized optimization
• AB /Push-Pull method for distributed optimization in time-varying directed networks
• Delay-tolerant augmented-consensus-based distributed directed optimization
• Momentum-based accelerated algorithm for distributed optimization under sector-bound nonlinearity
• On the convergence result of the gradient-push algorithm on directed graphs with constant stepsize
• Distributed aggregative optimization over directed networks with column-stochasticity
• Convergence of an accelerated distributed optimisation algorithm over time-varying directed networks
• Performing linear convergence for distributed constrained optimisation over time-varying directed unbalanced networks

This page was built for publication: ADD-OPT: Accelerated Distributed Directed Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375217)