Stochastic Strongly Convex Optimization via Distributed Epoch Stochastic Gradient Algorithm

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 - delta, the proposed algorithm converges at a rate of O(ln(ln(T)/delta)/T). Finally, we provide numerical experiments to demonstrate the efficacy of the proposed algorithm.