A Single-Loop Algorithm for Decentralized Bilevel Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916219238481920 |
|---|---|
| author | Dong, Youran Ma, Shiqian Yang, Junfeng Yin, Chao |
| author_facet | Dong, Youran Ma, Shiqian Yang, Junfeng Yin, Chao |
| contents | Bilevel optimization has gained significant attention in recent years due to its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is a fully single-loop method that approximates the hypergradient using only two matrix-vector multiplications per iteration. Importantly, our algorithm does not require any gradient heterogeneity assumption, distinguishing it from existing methods for decentralized bilevel optimization and federated bilevel optimization. Our analysis demonstrates that the proposed algorithm achieves the best-known convergence rate for bilevel optimization algorithms. We also present experimental results on hyperparameter optimization problems using both synthetic and MNIST datasets, which demonstrate the efficiency of our proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_08945 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Single-Loop Algorithm for Decentralized Bilevel Optimization Dong, Youran Ma, Shiqian Yang, Junfeng Yin, Chao Optimization and Control Distributed, Parallel, and Cluster Computing Machine Learning Bilevel optimization has gained significant attention in recent years due to its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is a fully single-loop method that approximates the hypergradient using only two matrix-vector multiplications per iteration. Importantly, our algorithm does not require any gradient heterogeneity assumption, distinguishing it from existing methods for decentralized bilevel optimization and federated bilevel optimization. Our analysis demonstrates that the proposed algorithm achieves the best-known convergence rate for bilevel optimization algorithms. We also present experimental results on hyperparameter optimization problems using both synthetic and MNIST datasets, which demonstrate the efficiency of our proposed algorithm. |
| title | A Single-Loop Algorithm for Decentralized Bilevel Optimization |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Machine Learning |
| url | https://arxiv.org/abs/2311.08945 |