Fully First-Order Methods for Decentralized Bilevel Optimization
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 $\epsilon$-stationary point in our algorithm is $\mathcal{O}(n^{-1}\epsilon^{-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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationSimilar Papers 제목 키워드 기반
A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization
Bilevel optimization, crucial for hyperparameter tuning, meta-learning and reinforcement learning, remains less explored in the decentralized learning paradigm, such as decentralized federated learning (DFL). Typically, …
Bilevel OptimizationFederated LearningMeta-LearningDecentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity
Stochastic bilevel optimization (SBO) is becoming increasingly essential in machine learning due to its versatility in handling nested structures. To address large-scale SBO, decentralized approaches have emerged as effe…
Bilevel OptimizationA Single-Loop Algorithm for Decentralized Bilevel Optimization
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-lo…
Bilevel OptimizationHyperparameter OptimizationDecentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity
Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extendi…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningStochastic OptimizationNonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise
Existing decentralized stochastic optimization methods assume the lower-level loss function is strongly convex and the stochastic gradient noise has finite variance. These strong assumptions typically are not satisfied i…
Stochastic OptimizationBilevel Optimization