Fundamental Limits of Personalized Federated Linear Regression with Data Heterogeneity
Journal
IEEE International Symposium on Information Theory - Proceedings
Journal Volume
2022-June
ISBN
9781665421591
Date Issued
2022-01-01
Author(s)
Hou, Chun Ying
Abstract
Federated learning is a nascent framework for collaborative machine learning over networks of devices with local data and local model updates. Data heterogeneity across the devices is one of the challenges confronting this emerging field. Personalization is a natural approach to simultaneously utilize information from the other users' data and take data heterogeneity into account. In this work, we study the linear regression problem where the data across users are generated from different regression vectors. We present an information-theoretic lower bound of the minimax expected excess risk of personalized linear models. We show an upper bound that matches the lower bound within constant factors. The results characterize the effect of data heterogeneity on learning performance and the trade-off between sample size, problem difficulty, and distribution discrepancy, suggesting that the discrepancy-to-difficulty ratio is the key factor governing the effectiveness of heterogeneous data.
Type
conference paper