Timezone: »
Motivated by federated learning, we consider the hub-and-spoke model of distributed optimization in which a central authority coordinates the computation of a solution among many agents while limiting communication. We first study some past procedures for federated optimization, and show that their fixed points need not correspond to stationary points of the original optimization problem, even in simple convex settings with deterministic updates. In order to remedy these issues, we introduce FedSplit, a class of algorithms based on operator splitting procedures for solving distributed convex minimization with additive structure. We prove that these procedures have the correct fixed points, corresponding to optima of the original optimization problem, and we characterize their convergence rates under different settings. Our theory shows that these methods are provably robust to inexact computation of intermediate local quantities. We complement our theory with some experiments that demonstrate the benefits of our methods in practice.
Author Information
Reese Pathak (University of California, Berkeley)
Martin Wainwright (UC Berkeley)
More from the Same Authors
-
2020 Poster: Preference learning along multiple criteria: A game-theoretic perspective »
Kush Bhatia · Ashwin Pananjady · Peter Bartlett · Anca Dragan · Martin Wainwright -
2018 Poster: Theoretical guarantees for EM under misspecified Gaussian mixture models »
Raaz Dwivedi · nhật Hồ · Koulik Khamaru · Martin Wainwright · Michael Jordan -
2017 Poster: Online control of the false discovery rate with decaying memory »
Aaditya Ramdas · Fanny Yang · Martin Wainwright · Michael Jordan -
2017 Poster: Early stopping for kernel boosting algorithms: A general analysis with localized complexities »
Yuting Wei · Fanny Yang · Martin Wainwright -
2017 Spotlight: Early stopping for kernel boosting algorithms: A general analysis with localized complexities »
Yuting Wei · Fanny Yang · Martin Wainwright -
2017 Oral: Online control of the false discovery rate with decaying memory »
Aaditya Ramdas · Fanny Yang · Martin Wainwright · Michael Jordan -
2017 Poster: A framework for Multi-A(rmed)/B(andit) Testing with Online FDR Control »
Fanny Yang · Aaditya Ramdas · Kevin Jamieson · Martin Wainwright -
2017 Spotlight: A framework for Multi-A(rmed)/B(andit) Testing with Online FDR Control »
Fanny Yang · Aaditya Ramdas · Kevin Jamieson · Martin Wainwright