图上分布式双层优化:无环算法更新和瞬态迭代复杂度
原文中文,约400字,阅读约需1分钟。发表于: 。通过引入单循环去中心化的 SBO(D-SOBA)算法,并建立其瞬态迭代复杂度,本文首次澄清了网络拓扑和数据异质性对去中心化双层算法的联合影响。与现有方法相比,D-SOBA 算法在更宽松的假设条件下实现了与现有方法相比最先进的渐近速率、渐近梯度 / 海森复杂度和瞬态迭代复杂度。数值实验验证了我们的理论发现。
该文章介绍了上下文随机双层优化(CSBO)框架,扩展了经典的随机双层优化,使得下层决策者能够对上层决策者的决策做出最优响应,并对侧面信息做出响应。该框架适用于元学习、个性化联邦学习、端到端学习和侧面信息的 Wasserstein 分布鲁棒优化等应用。文章介绍了一种基于多层蒙特卡罗(MLMC)技术的高效双循环梯度方法,并建立了其样本复杂度和计算复杂度。该方法在随机非凸优化方面与现有下界相匹配,并且在元学习中的复杂度不依赖于任务数量。数值实验验证了理论结果。