Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.11218 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910033946607616 |
|---|---|
| author | Niu, Youcheng Xu, Jinming Sun, Ying Chai, Li Chen, Jiming |
| author_facet | Niu, Youcheng Xu, Jinming Sun, Ying Chai, Li Chen, Jiming |
| contents | This paper considers a class of distributed bilevel optimization (DBO) problems with a coupled inner-level subproblem. Existing approaches typically rely on hypergradient estimations involving computationally expensive Hessian evaluation. To address this, we approximate the DBO problem as a minimax problem by properly designing a penalty term that enforces both the constraint imposed by the inner-level subproblem and the consensus among the decision variables of agents. Moreover, we propose a loopless distributed algorithm, AHEAD, that employs multiple-timescale updates to solve the approximate problem asymptotically without requiring Hessian computation. Theoretically, we establish sharp convergence rates for nonconvex-strongly-convex settings and for distributed minimax problems as special cases. Our analysis reveals a clear dependence of convergence performance on node heterogeneity, penalty parameters, and network connectivity, with a weaker assumption on heterogeneity that only requires bounded gradients at the optimum. Numerical experiments corroborate our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11218 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hessian-Free Distributed Bilevel Optimization via Penalization with Time-Scale Separation Niu, Youcheng Xu, Jinming Sun, Ying Chai, Li Chen, Jiming Optimization and Control This paper considers a class of distributed bilevel optimization (DBO) problems with a coupled inner-level subproblem. Existing approaches typically rely on hypergradient estimations involving computationally expensive Hessian evaluation. To address this, we approximate the DBO problem as a minimax problem by properly designing a penalty term that enforces both the constraint imposed by the inner-level subproblem and the consensus among the decision variables of agents. Moreover, we propose a loopless distributed algorithm, AHEAD, that employs multiple-timescale updates to solve the approximate problem asymptotically without requiring Hessian computation. Theoretically, we establish sharp convergence rates for nonconvex-strongly-convex settings and for distributed minimax problems as special cases. Our analysis reveals a clear dependence of convergence performance on node heterogeneity, penalty parameters, and network connectivity, with a weaker assumption on heterogeneity that only requires bounded gradients at the optimum. Numerical experiments corroborate our theoretical results. |
| title | Hessian-Free Distributed Bilevel Optimization via Penalization with Time-Scale Separation |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.11218 |