Kavli Affiliate: Jia Liu
| First 5 Authors: Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, Jia Liu
| Summary:
In recent years, decentralized bilevel optimization problems have received
increasing attention in the networking and machine learning communities thanks
to their versatility in modeling decentralized learning problems over
peer-to-peer networks (e.g., multi-agent meta-learning, multi-agent
reinforcement learning, personalized training, and Byzantine-resilient
learning). However, for decentralized bilevel optimization over peer-to-peer
networks with limited computation and communication capabilities, how to
achieve low sample and communication complexities are two fundamental
challenges that remain under-explored so far. In this paper, we make the first
attempt to investigate the class of decentralized bilevel optimization problems
with nonconvex and strongly-convex structure corresponding to the outer and
inner subproblems, respectively. Our main contributions in this paper are
two-fold: i) We first propose a deterministic algorithm called INTERACT
(inner-gradient-descent-outer-tracked-gradient) that requires the sample
complexity of $mathcal{O}(n epsilon^{-1})$ and communication complexity of
$mathcal{O}(epsilon^{-1})$ to solve the bilevel optimization problem, where
$n$ and $epsilon > 0$ are the number of samples at each agent and the desired
stationarity gap, respectively. ii) To relax the need for full gradient
evaluations in each iteration, we propose a stochastic variance-reduced version
of INTERACT (SVR-INTERACT), which improves the sample complexity to
$mathcal{O}(sqrt{n} epsilon^{-1})$ while achieving the same communication
complexity as the deterministic algorithm. To our knowledge, this work is the
first that achieves both low sample and communication complexities for solving
decentralized bilevel optimization problems over networks. Our numerical
experiments also corroborate our theoretical findings.
| Search Query: ArXiv Query: search_query=au:”Jia Liu”&id_list=&start=0&max_results=10