FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization
Standard federated optimization methods successfully apply to stochastic
problems with single-level structure. However, many contemporary ML problems --
including adversarial robustness, hyperparameter tuning, and actor-critic --
fall under nested bilevel programming that subsumes minimax and compositional
optimization. In this work, we propose FEDNEST: A federated alternating
stochastic gradient method to address general nested problems. We establish
provable convergence rates for FEDNEST in the presence of heterogeneous data
and introduce variations for bilevel, minimax, and compositional optimization.
FEDNEST introduces multiple innovations including federated hypergradient
computation and variance reduction to address inner-level heterogeneity. We
complement our theory with experiments on hyperparameter \&
hyper-representation learning and minimax optimization that demonstrate the
benefits of our method in practice. Code is available at
https://github.com/mc-nya/FedNest.