FedNest: Federated Bilevel, Minimax, and Compositional Optimization
This addresses federated learning for complex nested optimization problems, which is incremental as it extends standard methods to more general structures.
The paper tackles the challenge of federated optimization for nested bilevel, minimax, and compositional problems, such as adversarial robustness and hyperparameter tuning, by proposing FedNest, a federated alternating stochastic gradient method with provable convergence rates and innovations like federated hypergradient computation, demonstrating practical benefits in experiments.
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 \fedblo: A federated alternating stochastic gradient method to address general nested problems. We establish provable convergence rates for \fedblo in the presence of heterogeneous data and introduce variations for bilevel, minimax, and compositional optimization. \fedblo 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/ucr-optml/FedNest.