Achieving Linear Speedup in Non-IID Federated Bilevel Learning
- URL: http://arxiv.org/abs/2302.05412v1
- Date: Fri, 10 Feb 2023 18:28:00 GMT
- Title: Achieving Linear Speedup in Non-IID Federated Bilevel Learning
- Authors: Minhui Huang, Dewei Zhang and Kaiyi Ji
- Abstract summary: We propose a new federated bilevel algorithm named FedMBO.
We show that FedMBO achieves a convergence rate of $mathcalObig(frac1sqrtnK+frac1K+fracsqrtnK3/2big)$ on non-i.i.d.datasets.
This is the first theoretical linear speedup result for non-i.i.d.federated bilevel optimization.
- Score: 16.56643290676128
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Federated bilevel optimization has received increasing attention in various
emerging machine learning and communication applications. Recently, several
Hessian-vector-based algorithms have been proposed to solve the federated
bilevel optimization problem. However, several important properties in
federated learning such as the partial client participation and the linear
speedup for convergence (i.e., the convergence rate and complexity are improved
linearly with respect to the number of sampled clients) in the presence of
non-i.i.d.~datasets, still remain open. In this paper, we fill these gaps by
proposing a new federated bilevel algorithm named FedMBO with a novel client
sampling scheme in the federated hypergradient estimation. We show that FedMBO
achieves a convergence rate of
$\mathcal{O}\big(\frac{1}{\sqrt{nK}}+\frac{1}{K}+\frac{\sqrt{n}}{K^{3/2}}\big)$
on non-i.i.d.~datasets, where $n$ is the number of participating clients in
each round, and $K$ is the total number of iteration. This is the first
theoretical linear speedup result for non-i.i.d.~federated bilevel
optimization. Extensive experiments validate our theoretical results and
demonstrate the effectiveness of our proposed method.
Related papers
- Momentum-Based Federated Reinforcement Learning with Interaction and Communication Efficiency [16.002770483584694]
Federated Reinforcement Learning (FRL) has garnered increasing attention.
In this paper, we introduce a new FRL algorithm, named $texttMFPO$.
We prove that by proper selection of momentum parameters and interaction frequency, $texttMFPO$ can achieve $tildemathcalO(H-1Nepsilon-3/2N)$ and $tmathcalO(ilon-1N)$.
arXiv Detail & Related papers (2024-05-24T03:23:37Z) - On the Convergence of Federated Averaging under Partial Participation
for Over-parameterized Neural Networks [13.950558331060838]
Federated learning (FL) is a widely employed distributed paradigm for collaboratively machine learning models from multiple clients without sharing local data.
In this paper, we show that FedAvg converges to a global minimum at a global rate at a global focus.
arXiv Detail & Related papers (2023-10-09T07:56:56Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning.
Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
arXiv Detail & Related papers (2023-05-24T17:26:22Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
We propose a communication-efficient algorithm, named FedBiOAcc.
We prove that FedBiOAcc-Local converges at the same rate for this type of problems.
Empirical results show superior performance of our algorithms.
arXiv Detail & Related papers (2023-02-13T21:28:53Z) - Decentralized Gossip-Based Stochastic Bilevel Optimization over
Communication Networks [42.76623191830371]
We propose a gossip-based distributed bilevel optimization algorithm.
Agents can solve both networked and outer problems in a single time.
Our algorithm achieves the state-of-the-art efficiency and test accuracy.
arXiv Detail & Related papers (2022-06-22T06:38:54Z) - Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
Federated learning (FL) is a promising privacy-preserving machine learning paradigm over distributed located data.
We propose a learning-based reweighting approach to mitigate the effect of noisy labels in FL.
Our approach has shown superior performance on several real-world datasets compared to various baselines.
arXiv Detail & Related papers (2022-06-11T16:21:17Z) - FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
Many contemporary ML problems fall under nested bilevel programming that subsumes minimax and compositional optimization.
We propose FedNest: A federated alternating gradient method to address general nested problems.
arXiv Detail & Related papers (2022-05-04T17:48:55Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
We study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm.
We show FedBiO has complexity of $O(epsilon-1.5)$.
Our algorithms show superior performances compared to other baselines in numerical experiments.
arXiv Detail & Related papers (2022-05-03T16:40:22Z) - Faster Non-Convex Federated Learning via Global and Local Momentum [57.52663209739171]
textttFedGLOMO is the first (first-order) FLtexttFedGLOMO algorithm.
Our algorithm is provably optimal even with communication between the clients and the server.
arXiv Detail & Related papers (2020-12-07T21:05:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.