Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks
Bilevel optimization have gained growing interests, with numerous
applications found in meta learning, minimax games, reinforcement learning, and
nested composition optimization. This paper studies the problem of distributed
bilevel optimization over a network where agents can only communicate with
neighbors, including examples from multi-task, multi-agent learning and
federated learning. In this paper, we propose a gossip-based distributed
bilevel learning algorithm that allows networked agents to solve both the inner
and outer optimization problems in a single timescale and share information via
network propagation. We show that our algorithm enjoys the
$\mathcal{O}(\frac{1}{K \epsilon^2})$ per-agent sample complexity for general
nonconvex bilevel optimization and $\mathcal{O}(\frac{1}{K \epsilon})$ for
strongly convex objective, achieving a speedup that scales linearly with the
network size. The sample complexities are optimal in both $\epsilon$ and $K$.
We test our algorithm on the examples of hyperparameter tuning and
decentralized reinforcement learning. Simulated experiments confirmed that our
algorithm achieves the state-of-the-art training efficiency and test accuracy.