On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
arXiv:1903.09844
Abstract
We introduce a primal-dual stochastic gradient oracle method for distributed convex optimization problems over networks. We show that the proposed method is optimal in terms of communication steps. Additionally, we propose a new analysis method for the rate of convergence in terms of duality gap and probability of large deviations. This analysis is based on a new technique that allows to bound the distance between the iteration sequence and the optimal point. By the proper choice of batch size, we can guarantee that this distance equals (up to a constant) to the distance between the starting point and the solution.
References in corpus (9)
- TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
- A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
- Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces
- On the Complexity of Approximating Wasserstein Barycenter
- Distributed Learning for Cooperative Inference
- Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters