Achieving Linear Speedup in Non-IID Federated Bilevel Learning

Federated learning is a privacy-preserving training paradigm over distributed networks that are designed for edge computing (McMahan et al., 2017). In federated learning, multiple edge devices (or clients) work together to learn a global model under the coordination of a central server. Instead of transmitting user data directly to the central server, each client stores data and computes locally and only transmits the privacy-preserving information. This paradigm is increasingly attractive due to the growing computational power of edge devices and the increasing demand for privacy protection. Federated learning is facing more challenges than traditional distributed optimization due to the high communication cost, data and system heterogeneity, and privacy concerns. Recent years have witnessed great progress in the algorithmic design and system deployment to address such challenges (Wang & Joshi, 2021; Karimireddy et al., 2019; Stich & Karimireddy, 2020). Recently, federated bilevel learning has received increasing attention (Chen et al., 2018; Fallah et al., 2020; Zeng et al., 2021) because many modern machine learning problems naturally exhibit a bilevel optimization structure. For example, Chen et al. 2018; Fallah et al. 2020 studied the federated meta-learning problems, Khodak et al. 2021 proposed federated hyperparameter optimization approaches, and Zeng et al. 2021 improved the fairness in federated learning using a bilevel method. This motivates us to study the following federated bilevel optimization problem.