Swarming for Faster Convergence in Stochastic Optimization

DOI10.1137/17M1111085zbMATH Open1401.90138arXiv1806.04207OpenAlexW2964263318MaRDI QIDQ4582016FDOQ4582016

Alfredo García, Shi Pu

Publication date: 22 August 2018

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: We study a distributed framework for stochastic optimization 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 gradient-descent algorithm which is perturbed by a swarming potential. Assuming the overhead caused by synchronization is not negligible, we show the swarming-based approach exhibits better performance than a centralized algorithm (based upon the average of $N$ observations) in terms of (real-time) convergence speed. We also derive an error bound that is monotone decreasing in network size and connectivity. We characterize the scheme's finite-time performances for both convex and non-convex objective functions.

Full work available at URL: https://arxiv.org/abs/1806.04207

zbMATH Keywords

stochastic optimizationdistributed optimizationswarming-based framework

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15)

Cites Work

• Title not available (Why is that?)
• A Stochastic Approximation Method
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Distributed Subgradient Methods for Convex Optimization Over Random Networks
• A Model Reference Adaptive Search Method for Global Optimization
• Stochastic Estimation of the Maximum of a Regression Function
• A class of attractions/repulsion functions for stable swarm aggregations
• Design and analysis of simulation experiments
• Swarm Stability and Optimization
• Adaptive Penalty-Based Distributed Stochastic Convex Optimization
• Noise Reduction by Swarming in Social Foraging
• A Flocking-Based Approach for Distributed Stochastic Optimization

Cited In (6)

• Erratum: Swarming for Faster Convergence in Stochastic Optimization
• Title not available (Why is that?)
• Fast Decentralized Nonconvex Finite-Sum Optimization with Recursive Variance Reduction
• Distributed stochastic gradient tracking methods
• A swarm-inspired projection algorithm
• Safe Metropolis-Hastings algorithm and its application to swarm control

Uses Software

• Boids

This page was built for publication: Swarming for Faster Convergence in Stochastic Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4582016)