A Flocking-Based Approach for Distributed Stochastic Optimization

• 成果类型: Article
• 署名作者: Pu, Shi; Garcia, Alfredo
• 署名单位: Arizona State University; Arizona State University-Tempe; Texas A&M University System; Texas A&M University College Station
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1666
• 发表日期: 2018
• 页码: 267-281
• 关键词: convex-optimization

摘要

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 among processors and most importantly, does not require synchronization. Specifically, we analyze a scheme with N > 1 independent threads each implementing 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 that 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.