University of British Columbia
Communcation-efficient algorithms for decentralized multi-task learning
Abstract
dc:descriptionDistributed optimization requires nodes to coordinate, yet full synchronization scales poorly. When multiple nodes collaborate through pairwise regularizers, standard methods require a number of communications proportional to the total number of regularizers per iteration. We propose randomized local coordination, in which each node independently samples one regularizer uniformly and coordinates only with nodes sharing that term. This approach exploits partial separability, where each regularizer depends on a subset of nodes. For graph-guided regularizers, where each regularizer depends on a pair of nodes, expected communication drops to exactly 2 messages per iteration regardless of the network topology. By replacing the proximal map of the sum with the proximal map of a single randomly selected regularizer, the method preserves convergence while eliminating global coordination. We show that this method achieves a convergence rate comparable to that of centralized stochastic gradient descent in various settings. Experiments validate both convergence rates and communication efficiency across synthetic and real-world datasets.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kuang, Yao
- Contributors dc:contributor
-
- Friedlander, Michael P.
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/92259