UC Irvine

This dissertation studies collaborative learning when communication is limited. The challenge is: data are spread across many devices, but the model should improve as if the network were working together. Moreover, the devices may be connected by a network with limited bandwidth, and links may be delayed or unavailable. The algorithms in this dissertation are designed to address these issues.The first part considers online kernel learning over a graph. We extend distributed online multi-kernel learning beyond complete graphs by combining gossip with a hidden-state quantization scheme, and we prove sublinear regret with finite-bit messages.We then study asynchronous federated learning with bidirectional quantization. The resulting algorithm uses a shared hidden state to prevent quantization errors from accumulating between the server and clients, and it retains the standard ergodic convergence rate for non-convex stochastic optimization.The next part focuses on compression in distributed learning. Previous literature has shown that error-feedback can be used to correct for compression errors, but it requires clients to store local hidden states. We propose two methods that remove this requirement and allow clients to be stateless while still using error-feedback.The final part moves to decentralized online learning. We show that we can use a coin-betting framework, previously proposed for the single-agent case, to remove learning-rate tuning from decentralized online convex optimization, and we give comparator-adaptive network-regret guarantees. We also extend this framework to compressed gossip, giving parameter-free network-regret bounds under compressed communication.Together, these results improve our understanding of how compression, hidden states, gossip, and parameter-free online learning can affect collaborative learning in communication-constrained networks, and how we can co-design algorithms to work around communication bottlenecks.