  This paper advocates a new paradigm Personalized Empirical Risk Minimization
(PERM) to facilitate learning from heterogeneous data sources without imposing
stringent constraints on computational resources shared by participating
devices. In PERM, we aim to learn a distinct model for each client by learning
who to learn with and personalizing the aggregation of local empirical losses
by effectively estimating the statistical discrepancy among data distributions,
which entails optimal statistical accuracy for all local distributions and
overcomes the data heterogeneity issue. To learn personalized models at scale,
we propose a distributed algorithm that replaces the standard model averaging
with model shuffling to simultaneously optimize PERM objectives for all
devices. This also allows us to learn distinct model architectures (e.g.,
neural networks with different numbers of parameters) for different clients,
thus confining underlying memory and compute resources of individual clients.
We rigorously analyze the convergence of the proposed algorithm and conduct
experiments that corroborate the effectiveness of the proposed paradigm.
