Stochastic Strongly Convex Optimization via Distributed Epoch Stochastic Gradient Algorithm
Deming Yuan, Daniel W. C. Ho, Shengyuan Xu
Abstract
This article considers the problem of stochastic strongly convex optimization over a network of multiple interacting nodes. The optimization is under a global inequality constraint and the restriction that nodes have only access to the stochastic gradients of their objective functions. We propose an efficient distributed non-primal-dual algorithm, by incorporating the inequality constraint into the objective via a smoothing technique. We show that the proposed algorithm achieves an optimal O((1)/(T)) ( T is the total number of iterations) convergence rate in the mean square distance from the optimal solution. In particular, we establish a high probability bound for the proposed algorithm, by showing that with a probability at least 1-δ , the proposed algorithm converges at a rate of O(ln(ln(T)/δ)/ T) . Finally, we provide numerical experiments to demonstrate the efficacy of the proposed algorithm.