Fully First-Order Methods for Decentralized Bilevel Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917181355196416 |
|---|---|
| author | Wang, Xiaoyu Chen, Xuxing Ma, Shiqian Zhang, Tong |
| author_facet | Wang, Xiaoyu Chen, Xuxing Ma, Shiqian Zhang, Tong |
| contents | This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis showing that for $n$ agents collaboratively solving the DSBO problem, the sample complexity of finding an $ε$-stationary point in our algorithm is $\mathcal{O}(n^{-1}ε^{-7})$, which matches the currently best-known results of the single-agent counterpart with linear speedup. The numerical experiments demonstrate both the communication and training efficiency of our algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19319 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fully First-Order Methods for Decentralized Bilevel Optimization Wang, Xiaoyu Chen, Xuxing Ma, Shiqian Zhang, Tong Optimization and Control Machine Learning 90C06, 90C15, 90C47 This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis showing that for $n$ agents collaboratively solving the DSBO problem, the sample complexity of finding an $ε$-stationary point in our algorithm is $\mathcal{O}(n^{-1}ε^{-7})$, which matches the currently best-known results of the single-agent counterpart with linear speedup. The numerical experiments demonstrate both the communication and training efficiency of our algorithm. |
| title | Fully First-Order Methods for Decentralized Bilevel Optimization |
| topic | Optimization and Control Machine Learning 90C06, 90C15, 90C47 |
| url | https://arxiv.org/abs/2410.19319 |