TITLE: A Flocking-based Approach for Distributed Stochastic Optimization

ABSTRACT:

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 single-thread 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 single-thread 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 single-thread stochastic gradient algorithm based upon the average of N gradient samples at each step.

Bio:

Alfredo Garcia is Professor with the Department of Industrial and Systems Engineering at the University of Florida. He received an undergraduate degree in Electrical Engineering from the Universidad de los Andes, Colombia, in 1991, the Diplome d'Etudes Approfondies D.E.A. in Control Systems from the Université Paul Sabatier, Toulouse, France, in 1992, and the Ph.D. degree in Operations Research from the University of Michigan, Ann Arbor, in 1997. During 1998-2000 he served as Commissioner in the Colombian Energy Regulatory Commission. From 2001-2015 he was a member of the faculty at the University of Virginia. His research interests include game theory and dynamic optimization with applications in power and communication networks. He currently manages the program in "Control of Networked Multi-agent Systems" for ARO.