Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization
arXiv:1610.04702
Abstract
In this paper we consider convergence rate problems for stochastic strongly-convex optimization in the non-Euclidean sense with a constraint set over a time-varying multi-agent network. We propose two efficient non-Euclidean stochastic subgradient descent algorithms based on the Bregman divergence as distance-measuring function rather than the Euclidean distances that were employed by the standard distributed stochastic projected subgradient algorithms. For distributed optimization of nonsmooth and strongly convex functions whose only stochastic subgradients are available, the first algorithm recovers the best previous known rate of O(ln(T)/T) (where T is the total number of iterations). The second algorithm is an epoch variant of the first algorithm that attains the optimal convergence rate of O(1/T), matching that of the best previously known centralized stochastic subgradient algorithm. Finally, we report some simulation results to illustrate the proposed algorithms.
arXiv comment9 pages, 4 figures; version accepted to Automatica
References in corpus (5)
- Constrained Consensus
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Initialization-free Distributed Algorithms for Optimal Resource Allocation with Feasibility Constraints and its Application to Economic Dispatch of Power Systems
- Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method