  Federated Learning (FL) is a distributed learning paradigm that scales
on-device learning collaboratively and privately. Standard FL algorithms such
as FedAvg are primarily geared towards smooth unconstrained settings. In this
paper, we study the Federated Composite Optimization (FCO) problem, in which
the loss function contains a non-smooth regularizer. Such problems arise
naturally in FL applications that involve sparsity, low-rank, monotonicity, or
more general constraints. We first show that straightforward extensions of
primal algorithms such as FedAvg are not well-suited for FCO since they suffer
from the "curse of primal averaging," resulting in poor convergence. As a
solution, we propose a new primal-dual algorithm, Federated Dual Averaging
(FedDualAvg), which by employing a novel server dual averaging procedure
circumvents the curse of primal averaging. Our theoretical analysis and
empirical experiments demonstrate that FedDualAvg outperforms the other
baselines.
