March 10, 2017, Webb 1100

In recent years, the paradigm of cloud computing has emerged as an architecture for computing that makes use of distributed (networked) computing resources. In this paper, we consider a distributed computing algorithmic scheme for stochastic optimization which relies on modest communication requirements amongst processors and most importantly, does not require synchronization. Specifically, we analyze a scheme with N > 1 independent threads implementing each a stochastic gradient algorithm. The threads are coupled via a perturbation of the gradient (with attractive and repulsive forces) in a similar manner to mathematical models of flocking, swarming and other group formations found in nature with mild communication requirements. When the objective function is convex, we show that a flocking-like approach for distributed stochastic optimization provides a noise reduction effect similar to that of a centralized stochastic gradient algorithm based upon the average of N gradient samples at each step. The distributed nature of flocking makes it an appealing computational alternative. We show that when the overhead related to the time needed to gather N samples and synchronization is not negligible, the flocking implementation outperforms a centralized stochastic gradient algorithm based upon the average of N gradient samples at each step. When the objective function is not convex, the flocking-based approach seems better suited to escape locally optimal solutions due to the repulsive force which enforces a certain level of diversity in the set of candidate solutions. Here again, we show that the noise reduction effect is similar to that associated to the centralized stochastic gradient algorithm based upon the average of N gradient samples at each step.

Shi Pu is a postdoctoral associate in the Department of Industrial and Systems Engineering at the University of Florida. He received a B.S. Degree in Engineering Mechanics from Peking University in 2012, and a Ph.D. Degree in Systems and Information Engineering from the University of Virginia in 2016. His research interests lie in the broad area of multi-agent control and optimization, network science, and game theory.