Swarming for Faster Convergence in Stochastic Optimization

We study a distributed framework for stochastic optimizati on which is inspired by models of collective motion found in nature (e.g., swarming) with mild communication requirements. Specifically, we analyze a scheme in which each one of N 1 independent threads, implements in a distributed and unsynchronized fashion, a stochastic grad ient-descent algorithm which is perturbed by a swarming potential. Assuming the overhead caused by syn chronization is not negligible, we show the swarming-based approach exhibits better performance t han a centralized algorithm (based upon the average of N observations) in terms of (real-time) convergence speed. W e also derive an error bound that is monotone decreasing in network size and connec tivity. We characterize the scheme's finite-time performances for both convex and non-convex obj ective functions.