Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

DOI10.1109/TAC.2016.2529285MaRDI QIDQ2979341zbMATH OpenOpenAlexFDO

Authors Angelia Nedić, Alex Olshevsky

Publication date 3 May 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Distributed algorithms (68W15) Convex programming (90C25) Programming involving graphs or networks (90C35)

Abstract: We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying directed graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of $Oleft((lnt)/tight)$ for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the $Oleft((lnt)/sqrttight)$ rate previously known for (general) convex functions.

Cited in

(44)

• Optimal distributed stochastic mirror descent for strongly convex optimization
• Convergence rate analysis of distributed optimization with projected subgradient algorithm
• Distributed constrained stochastic subgradient algorithms based on random projection and asynchronous broadcast over networks
• Distributed stochastic gradient tracking methods
• On the linear convergence of two decentralized algorithms
• On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
• Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
• Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs
• Cooperative convex optimization with subgradient delays using push-sum distributed dual averaging
• An improved distributed gradient-push algorithm for bandwidth resource allocation over wireless local area network
• An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs
• Distributed stochastic subgradient projection algorithms based on weight-balancing over time-varying directed graphs
• Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
• Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
• On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Decentralized consensus algorithm with delayed and stochastic gradients
• Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
• Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate.
• A distributed ADMM-like method for resource sharing over time-varying networks
• Optimal convergence rates for convex distributed optimization in networks
• Snake: A Stochastic Proximal Gradient Algorithm for Regularized Problems Over Large Graphs
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• Multi-agent based optimal equilibrium selection with resilience constraints for traffic flow
• A differentially private distributed optimization method for constrained optimization
• A Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks
• Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method
• Distributed constrained optimization for multi-agent networks with communication delays under time-varying topologies
• An accelerated distributed online gradient push-sum algorithm on time-varying directed networks
• Gradient-free algorithms for distributed online convex optimization
• Distributed heterogeneous multi-agent optimization with stochastic sub-gradient
• Distributed stochastic optimization algorithm with non-consistent constraints in time-varying unbalanced networks
• Multi-agent flocking control with complex obstacles and adaptive distributed convex optimization
• Distributed stochastic constrained optimization with constant step-sizes via saddle-point dynamics
• Delay-tolerant augmented-consensus-based distributed directed optimization
• Momentum-based accelerated algorithm for distributed optimization under sector-bound nonlinearity
• On the convergence analysis of the decentralized projected gradient descent method
• Gradient-free distributed online optimization in networks
• On the convergence result of the gradient-push algorithm on directed graphs with constant stepsize
• Performing linear convergence for distributed constrained optimisation over time-varying directed unbalanced networks
• Linear convergence for distributed stochastic optimization with coupled inequality constraints
• An improved convergence guarantee for the gradient-push algorithm with a constant stepsize
• Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes

This page was built for publication: Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

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