CaltechAUTHORS
  A Caltech Library Service

Distributed Optimization via Local Computation Algorithms

London, Palma and Chen, Niangjun and Vardi, Shai and Wierman, Adam (2017) Distributed Optimization via Local Computation Algorithms. Performance Evaluation Review , 45 (2). pp. 30-32. ISSN 0163-5999. https://resolver.caltech.edu/CaltechAUTHORS:20180409-162519917

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180409-162519917

Abstract

We propose a new approach for distributed optimization based on an emerging area of theoretical computer science -- local computation algorithms. The approach is fundamentally different from existing methodologies and provides a number of benefits, such as robustness to link failure and adaptivity in dynamic settings. Specifically, we develop an algorithm, LOCO, that given a convex optimization problem P with n variables and a "sparse" linear constraint matrix with m constraints, provably finds a solution as good as that of the best online algorithm for P using only O(log(n+m)) messages with high probability. The approach is not iterative and communication is restricted to a localized neighborhood. In addition to analytic results, we show numerically that the performance improvements over classical approaches for distributed optimization are significant, e.g., it uses orders of magnitude less communication than ADMM.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3152042.3152053DOIArticle
https://dl.acm.org/citation.cfm?id=3152053PublisherArticle
ORCID:
AuthorORCID
Chen, Niangjun0000-0002-2289-9737
Additional Information:Copyright is held by author/owner(s).
Issue or Number:2
Record Number:CaltechAUTHORS:20180409-162519917
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180409-162519917
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:85706
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:10 Apr 2018 14:43
Last Modified:03 Oct 2019 19:34

Repository Staff Only: item control page