A computation-efficient distributed algorithm for convex constrained optimization problem

摘要

#$%^&*AU2020101237A420200806.pdf#####Abstract A computation-efficient distributed algorithm based on the stochastic gradient projection method for solving the problem of convex constrained optimization with a sum of smooth convex functions and non-smooth regularization terms subject to locally general constraints is proposed over an undirected network. The algorithm mainly includes five parts: Variable initialization, parameter definition and selection, information exchange, stochastic gradient computation, and variable update. By adopting the variance reduction technique, the proposed algorithm which is set forth in the present invention reduces the amount of computation in comparison with related works. Presuming the smoothness and strong convexity cost functions, the proposed algorithm can find the exact optimal solution in expectation in the event that the constant step-size is less than an explicitly estimated upper bound. With respect to the existing distributed schemes, the proposed algorithm is more convenient for general constrained optimization problems and possesses low computation complexity in terms of the total number of local gradient evaluations. The present invention has broad application in the modern large-scale information processing problems in machine learning (The samples of a training dataset are randomly distributed across multiple computing nodes and each of the smooth objective functions is further considered as the average of several constituent functions).1/2 Start Each node sets k=O and maximum number of iteration, kmax Each node initializes local variables and selects fixed step-size as well as fixed tunable parameter according to the network and the problem Each node computes the stochastic gradient according to the variance reduction technique Each node updates the main variable according to the stochastic gradient projection method Each node updates the Lagrangian multipliers according to the main variable and the projection operator Each node sets k=k+l No k Akax Yes End Figure 1