More Like this

1. SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning

   Yang, Y; Xiao, P; Ji, K (February 2024, Advances in Neural Information Processing Systems)

   Federated bilevel optimization (FBO) has shown great potential recently in machine learning and edge computing due to the emerging nested optimization structure in meta-learning, fine-tuning, hyperparameter tuning, etc. However, existing FBO algorithms often involve complicated computations and require multiple sub-loops per iteration, each of which contains a number of communication rounds. In this paper, we propose a simple and flexible FBO framework named SimFBO, which is easy to implement without sub-loops, and includes a generalized server-side aggregation and update for improving communication efficiency. We further propose System-level heterogeneity robust FBO (ShroFBO) as a variant of SimFBO with stronger resilience to heterogeneous local computation. We show that SimFBO and ShroFBO provably achieve a linear convergence speedup with partial client participation and client sampling without replacement, as well as improved sample and communication complexities. Experiments demonstrate the effectiveness of the proposed methods over existing FBO algorithms. 

   more » « less
2. First-Order Federated Bilevel Learning

   https://doi.org/10.1609/aaai.v39i21.34355  

   Yang, Yifan; Xiao, Peiyao; Ma, Shiqian; Ji, Kaiyi (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   Federated bilevel optimization (FBO) has garnered significant attention lately, driven by its promising applications in meta-learning and hyperparameter optimization. Existing algorithms generally aim to approximate the gradient of the upper-level objective function (hypergradient) in the federated setting. However, because of the nonlinearity of the hypergradient and client drift, they often involve complicated computations. These computations, like multiple optimization sub-loops and second-order derivative evaluations, end up with significant memory consumption and high computational costs. In this paper, we propose a computationally and memory-efficient FBO algorithm named MemFBO. MemFBO features a fully single-loop structure with all involved variables updated simultaneously, and uses only first-order gradient information for all local updates. We show that MemFBO exhibits a linear convergence speedup with milder assumptions in both partial and full client participation scenarios. We further implement MemFBO in a novel FBO application for federated data cleaning. Our experiments, conducted on this application and federated hyper-representation, demonstrate the effectiveness of the proposed algorithm. 

   more » « less
3. First-Order Federated Bilevel Learning

   Yang, Yifan; Xiao, Peiyao; Ma, Shiqian; Ji, Kaiyi (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   Federated bilevel optimization (FBO) has garnered significant attention lately, driven by its promising applications in meta-learning and hyperparameter optimization. Existing algorithms generally aim to approximate the gradient of the upper-level objective function (hypergradient) in the federated setting. However, because of the nonlinearity of the hypergradient and client drift, they often involve complicated computations. These computations, like multiple optimization sub-loops and second-order derivative evaluations, end up with significant memory consumption and high computational costs. In this paper, we propose a computationally and memory-efficient FBO algorithm named MemFBO. MemFBO features a fully single-loop structure with all involved variables updated simultaneously, and uses only first-order gradient information for all local updates. We show that MemFBO exhibits a linear convergence speedup with milder assumptions in both partial and full client participation scenarios. We further implement MemFBO in a novel FBO application for federated data cleaning. Our experiments, conducted on this application and federated hyper-representation, demonstrate the effectiveness of the proposed algorithm. 

   more » « less
4. Anarchic Federated Bilevel Optimization

   Li, Dongsheng; Zhu, Ye; Gong, Xiaowen; Mao, Shiwen; Zhou, Yang (December 2024, Proceedings of the International Symposium on Modeling and Optimization in Mobile Ad Hoc and Wireless Networks)

   Rapid federated bilevel optimization (FBO) developments have attracted much attention in various emerging machine learning and communication applications. Existing work on FBO often assumes that clients participate in the learning process with some particular pattern (such as balanced participation), and/or in a synchronous manner, and/or with homogeneous local iteration numbers, which might be hard to hold in practice. This paper proposes a novel Anarchic Federated Bilevel Optimization (AFBO) algorithm, which allows clients to 1) participate in any inner or outer rounds; 2) participate asynchronously; and 3) participate with any number of local iterations. The AFBO algorithm enables clients to participate in FBO training flexibly. We provide a theoretical analysis of the learning loss of AFBO for both cases of non-convex and strongly convex loss functions. The convergence results of the AFBO algorithm match that of the existing benchmarks. Numerical studies are conducted to verify the effectiveness of AFBO. 

   more » « less
5. Towards Understanding Biased Client Selection in Federated Learning

   Yae Jee Cho; Jianyu Wang; Gauri Joshi (April 2022, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics)

   Federated learning is a distributed optimization paradigm that enables a large number of resource-limited client nodes to cooperatively train a model without data sharing. Previous works analyzed the convergence of federated learning by accounting for data heterogeneity, communication/computation limitations, and partial client participation. However, most assume unbiased client participation, where clients are selected such that the aggregated model update is unbiased. In our work, we present the convergence analysis of federated learning with biased client selection and quantify how the bias affects convergence speed. We show that biasing client selection towards clients with higher local loss yields faster error convergence. From this insight, we propose Power-of-Choice, a communication- and computation-efficient client selection framework that flexibly spans the trade-off between convergence speed and solution bias. Extensive experiments demonstrate that Power-of-Choice can converge up to 3 times faster and give 10% higher test accuracy than the baseline random selection. 

   more » « less