Decentralized Learning for Overparameterized Problems: A Multi-Agent Kernel Approximation Approach

Prashant Khanduri, Haibo Yang, Mingyi Hong, Jia Liu, Hoi To Wai, Sijia LiuICLR 2022 · OpenReview

TL;DR

This paper introduces a communication-efficient framework for decentralized learning in the "overparameterized" regime, where models have far more parameters than there are data points. By shifting the focus from sharing massive model parameters to sharing compact "kernel approximations," the authors enable agents to achieve optimal learning performance with a single round of communication, completely bypassing the need for iterative consensus.

The Bottleneck of Consensus in Overparameterized AI

In traditional decentralized learning, multiple agents (like mobile devices or hospitals) collaborate to train a model without sharing their raw private data. Most existing methods rely on consensus: agents train locally and then repeatedly exchange and average their model parameters.

However, modern AI is in the era of overparameterization. Models like deep neural networks often have millions or billions of parameters ($D$), while the local dataset size ($n$) might be quite small. In this scenario, the "consensus" approach becomes a critical bottleneck—sending high-dimensional parameter vectors back and forth across a network is incredibly slow and expensive.

The fundamental question the authors address is: If the model is huge but the data is small, can we design a decentralized algorithm where the communication cost depends on the amount of data, rather than the size of the model?

Methods: Multi-Agent Kernel Approximation

The authors move away from parameter-sharing and instead leverage Kernel Learning. Specifically, they focus on a broad class of kernels called Generalized Inner-Product (GIP) kernels, which includes the popular Neural Tangent Kernel (NTK) used to analyze deep networks.

Their approach, called Multi-Agent Kernel Approximation, works in two main steps:

Algorithm 1: Local Kernel Estimation
  1. Algorithm 1 (Local Kernel Estimation): Instead of sharing data or parameters, agents share a small, compressed "sketch" of their data. For GIP kernels, this involves sharing a binary matrix that represents the signs of random projections of their data. As shown in the pseudo-code above, this allows every agent to locally estimate the "global" kernel matrix (the relationships between all data points in the network) without ever seeing the actual raw data.
  2. Algorithm 2 (One-Shot Communication): Once the kernel matrix is estimated, agents share their labels (the "answers" for their data points). Because they now have an approximation of the full kernel matrix and all the labels, each agent can solve the optimization problem locally.

What’s new? Unlike standard decentralized SGD or ADMM, this is a one-shot approach. There is no iterative looping or "averaging" step. Agents communicate once, then solve the problem independently.

Key Insights and Results

  • Breaking the Consensus Habit: Most decentralized researchers assume agents must reach a consensus on a single parameter vector. This paper shows that if agents can accurately estimate the global kernel, they can independently arrive at a solution that generalizes just as well as a centralized one.
Comparison of Communication Costs
  • Communication vs. Model Size: As detailed in the comparison table above, the communication cost for the proposed algorithm scales as $\mathcal{O}(N^2/M)$ for GIP kernels and $\mathcal{O}(N\sqrt{N}/M)$ for Random Features (RF) kernels (where $N$ is total samples and $M$ is agents). Crucially, this is independent of the parameter dimension $D$. For massive, overparameterized models, this is a game-changer.
  • The Power of Angles: For GIP kernels, you don't need to know the exact data values; you just need to know the angles between data vectors. The authors use a clever trick from locality-sensitive hashing (LSH) to estimate these angles using very few bits.
  • Optimal Generalization: The authors prove that their decentralized approach achieves "minimax optimal" generalization performance—meaning it’s theoretically as good as the best possible centralized learner.
  • Empirical Superiority: In experiments on UCI Benchmarking Datasets (like the NACA airfoil noise dataset), the proposed method achieved a target Mean Squared Error (MSE) using significantly fewer bits than state-of-the-art iterative methods. When given a fixed communication "budget," the proposed algorithm achieved much lower MSE than competitors, scaling better for complex problems as the number of random features increased.

Limitations and Future Work

  • Loss Function Constraints: The current theoretical analysis and closed-form solutions focus on $\ell_2$ loss (Ridge Regression). Extending this to other loss functions (like cross-entropy for classification) might require iterative solvers, potentially losing the strict "one-shot" benefit.
  • Kernel Dependency: The efficiency relies on the problem being well-modeled by GIP or RF kernels. While this covers many cases (including NTK), it may not capture the "feature learning" dynamics of non-lazy neural network training.
  • Label Privacy: While the method doesn't share raw features, it does require sharing data labels. In some highly sensitive applications (like medical diagnostics), even sharing labels might be a privacy concern, suggesting a need for future integration with Differential Privacy techniques.

Summary updated

Abstract

This work develops a novel framework for communication-efficient distributed learning where the models to be learned are overparameterized. We focus on a class of kernel learning problems (which includes the popular neural tangent kernel (NTK) learning as a special case) and propose a novel {\it multi-agent kernel approximation} technique that allows the agents to distributedly estimate the full kernel function, and subsequently perform decentralized optimization, without directly exchanging any local data or parameters. The proposed framework is a significant departure from the classical consensus-based approaches, because the agents do not exchange problem parameters, and no consensus is required. We analyze the optimization and the generalization performance of the proposed framework for the $\ell_2$ loss. We show that with $M$ agents and $N$ total samples when certain generalized inner-product kernels (resp. the random features kernel) are used, each agent needs to communicate $\mathcal{O}\big({N^2}/{M}\big)$ bits (resp. $\mathcal{O}\big(N \sqrt{N}/M \big)$ real values) to achieve minimax optimal generalization performance. We validate the theoretical results on 90 UCI benchmarking datasets (with average data size $N \approx 1000$) and show that each agent needs to share a total of $200N/M$ bits (resp. $3N/M$ real values) to closely match the performance of the centralized algorithms, and these numbers are independent of parameter and feature dimensions.
BibTeX
@inproceedings{khanduri2022decentralized,
  author = {Prashant Khanduri and Haibo Yang and Mingyi Hong and Jia Liu and Hoi To Wai and Sijia Liu},
  title = {{Decentralized Learning for Overparameterized Problems: A Multi-Agent Kernel Approximation Approach}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=oj2yn1Q4Ett},
}
Figure