Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2017 | Published
Journal Article Open

Distributed Optimization via Local Computation Algorithms

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.

Additional Information

Copyright is held by author/owner(s).

Attached Files

Published - p30-london.pdf

Files

p30-london.pdf
Files (883.1 kB)
Name Size Download all
md5:80466a4d0156d065d3860e3f86fca542
883.1 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023