提出高效去中心化双层优化方法,仅用一阶信息降低通信与计算开销。
A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization
- 用梯度替代海森矩阵,实现全一阶优化
- 内层迭代压缩参数残差,显著减少通信量
- 适用于异构数据和多种任务场景
双层优化在超参数调优、元学习和强化学习中至关重要,但在去中心化学习(如去中心化联邦学习)中仍研究不足。传统方法依赖梯度和海森矩阵来近似上层模型的超梯度,但获取和共享二阶信息计算与通信开销大。本文提出一种全一阶的去中心化双层优化方法 $ ext{C}^2$DFB,每个节点通过求解最小化-最小化-最大化问题,仅使用梯度信息近似超梯度。为降低内层求解时的通信负载,$ ext{C}^2$DFB 采用轻量级通信协议,高效传输本地参数残差。理论分析证明算法收敛,所需一阶黑盒调用次数为 $ ilde{ ext{O}}(ε^{-4})$。在超参数调优和超表示任务上的实验验证了其在多种网络拓扑和异构数据分布下的优越性。
原文摘要 · Abstract (English)
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, decentralized bilevel methods rely on both gradients and Hessian matrices to approximate hypergradients of upper-level models. However, acquiring and sharing the second-order oracle is compute and communication intensive. % and sharing this information incurs heavy communication overhead. To overcome these challenges, this paper introduces a fully first-order decentralized method for decentralized Bilevel optimization, $\text{C}^2$DFB which is both compute- and communicate-efficient. In $\text{C}^2$DFB, each learning node optimizes a min-min-max problem to approximate hypergradient by exclusively using gradients information. To reduce the traffic load at the inner-loop of solving the lower-level problem, $\text{C}^2$DFB incorporates a lightweight communication protocol for efficiently transmitting compressed residuals of local parameters. % during the inner loops. Rigorous theoretical analysis ensures its convergence % of the algorithm, indicating a first-order oracle calls of $\tilde{\mathcal{O}}(ε^{-4})$. Experiments on hyperparameter tuning and hyper-representation tasks validate the superiority of $\text{C}^2$DFB across various typologies and heterogeneous data distributions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。