COKE: Communication-Censored Decentralized Kernel Learning

Abstract

This paper studies the decentralized optimization and learning problem where multiple interconnected agents aim to learn an optimal decision function defined over a reproducing kernel Hilbert space by jointly minimizing a global objective function, with access to their own locally observed dataset. As a non-parametric approach, kernel learning faces a major challenge in distributed implementation: the decision variables of local objective functions are data-dependent and thus cannot be optimized under the decentralized consensus framework without any raw data exchange among agents. To circumvent this major challenge, we leverage the random feature (RF) approximation approach to enable consensus on the function modeled in the RF space by data-independent parameters across different agents. We then design an iterative algorithm, termed DKLA, for fast-convergent implementation via ADMM. Based on DKLA, we further develop a communication-censored kernel learning (COKE) algorithm that reduces the communication load of DKLA by preventing an agent from transmitting at every iteration unless its local updates are deemed informative. Theoretical results in terms of linear convergence guarantee and generalization performance analysis of DKLA and COKE are provided. Comprehensive tests on both synthetic and real datasets are conducted to verify the communication efficiency and learning effectiveness of COKE.

References in corpus (26)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
• Sparsified SGD with Memory
• Generalization Properties of Learning with Random Features
• Parallel Selective Algorithms for Big Data Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• AIDE: Fast and Communication Efficient Distributed Optimization
• Orthogonal Random Features
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Online Distributed Learning Over Networks in RKH Spaces Using Random Fourier Features
• Decentralized Online Learning with Kernels
• Quantized Consensus ADMM for Multi-Agent Distributed Optimization
• Optimal Rates for Random Fourier Features
• Analyzing sparse dictionaries for online learning with kernels
• On reducing the communication cost of the diffusion LMS algorithm
• Distributed Kernel Regression: An Algorithm for Training Collaboratively
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Double Quantization for Communication-Efficient Distributed Optimization
• Distributed Adaptive Learning with Multiple Kernels in Diffusion Networks
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
• Towards A Unified Analysis of Random Fourier Features

Cited by in corpus (2)

• Joint Optimization of Communications and Federated Learning Over the Air
• 1-Bit Compressive Sensing for Efficient Federated Learning Over the Air