{
  "id": "1806.04207",
  "version": "v1",
  "published": "2018-06-11T19:24:59.000Z",
  "updated": "2018-06-11T19:24:59.000Z",
  "title": "Swarming for Faster Convergence in Stochastic Optimization",
  "authors": [
    "Shi Pu",
    "Alfredo Garcia"
  ],
  "comment": "Accepted in SIAM Journal on Control and Optimization",
  "categories": [
    "math.OC",
    "cs.DC",
    "cs.MA",
    "cs.SI",
    "stat.ML"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-11T19:24:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stochastic optimization",
      "faster convergence",
      "schemes finite-time performances",
      "mild communication requirements",
      "stochastic gradient-descent algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}