Problem-Parameter-Free Decentralized Bilevel Optimization¶

会议: NeurIPS 2025

arXiv: 2510.24288

代码: 无

领域: 优化

关键词: 去中心化优化, 双层优化, 无参数, 自适应步长, 单循环

一句话总结¶

提出 AdaSDBO，一种完全无需问题参数先验知识的去中心化双层优化算法，通过基于累积梯度范数的自适应步长实现 $\tilde{O}(1/\sqrt{T})$ 收敛率。

研究背景与动机¶

去中心化双层优化（Decentralized Bilevel Optimization）在大规模机器学习中有重要应用，如元学习、超参数优化和联邦学习。其形式为：

\[\min_x f(x, y^*(x)) \quad \text{s.t.} \quad y^*(x) = \arg\min_y g(x, y)\]

其中多个节点协作优化，无需中央服务器。

现有方法的关键问题：

依赖问题参数: 需要知道 Lipschitz 常数、强凸参数、通信图谱信息等来设置步长

调参困难: 在实践中这些参数通常不可知，导致大量手动调参

双循环结构: 许多方法需要内外两层循环,实现复杂

方法详解¶

整体框架¶

AdaSDBO 是一种单循环、完全无参数的算法，使用自适应步长同时更新上下层变量和通信变量。

关键设计¶

1. 自适应步长机制

基于累积梯度范数自动调整步长，无需任何问题参数： $$\eta_t^x = \frac{c}{\sqrt{\sum_{s=1}^{t} \|G_s^x\|^2}}$$ $$\eta_t^y = \frac{c}{\sqrt{\sum_{s=1}^{t} \|G_s^y\|^2}}$$

类似 AdaGrad 的思想，但应用于双层优化的特殊结构。

2. 单循环结构

同时更新上层变量 $x$、下层变量 $y$ 以及共识变量
使用超梯度近似: $\hat{\nabla} F(x) = \nabla_x f - \nabla_{xy}^2 g \cdot (\nabla_{yy}^2 g)^{-1} \cdot \nabla_y f$
通过 Neumann 级数或有限差分近似 Hessian 逆

3. 去中心化通信

节点间通过通信图交换信息
使用梯度跟踪（gradient tracking）实现共识
自适应步长也同样应用于通信步骤

损失函数 / 训练策略¶

上层更新: $x_{t+1} = x_t - \eta_t^x \cdot \hat{\nabla}_x F(x_t, y_t)$
下层更新: $y_{t+1} = y_t - \eta_t^y \cdot \nabla_y g(x_t, y_t)$
共识更新: 通过混合矩阵 $W$ 进行节点间信息聚合

实验关键数据¶

主实验¶

数据hyper-清洗任务 (Data Hyper-cleaning, 测试精度):

方法	MNIST	CIFAR-10	FashionMNIST
DSBO (手动调参)	95.2%	68.5%	85.3%
MA-DSBO	94.8%	67.1%	84.5%
BSMD	94.5%	66.8%	83.9%
AdaSDBO (Ours)	95.4%	68.3%	85.1%

超参数搜索任务 (最终损失值):

方法	最佳调参	随机步长1	随机步长2	随机步长3
DSBO	0.032	0.156	0.089	发散
MA-DSBO	0.038	0.125	0.076	0.345
AdaSDBO	0.035	0.037	0.036	0.038

消融实验¶

不同步长初始化下的鲁棒性 (MNIST hyper-cleaning):

步长倍数	DSBO	MA-DSBO	AdaSDBO
0.01x	88.2%	90.1%	94.8%
0.1x	93.5%	93.8%	95.1%
1x (最佳)	95.2%	94.8%	95.4%
10x	91.1%	92.5%	95.2%
100x	发散	85.3%	95.0%

关键发现¶

AdaSDBO 在所有步长配置下都表现稳健，而基线方法对步长极其敏感
收敛率 $\tilde{O}(1/\sqrt{T})$ 与精心调参的SOTA方法匹配（仅差多对数因子）
在不同网络拓扑（环形、随机图、完全图）下,自适应步长均能自动调整
单循环结构的实际运行时间比双循环方法快 2-3 倍

亮点与洞察¶

实用性突破: 完全消除了对问题参数的依赖，真正实现"即插即用"
鲁棒性优异: 100 倍步长变化范围内性能几乎不变
理论保证完整: $\tilde{O}(1/\sqrt{T})$ 收敛率，匹配精调基线

局限与展望¶

理论分析仅针对非凸-强凸设置（上层非凸、下层强凸）
Polylogarithmic 因子的差距在某些场景可能不可忽略
通信压缩等去中心化优化的高级技巧未被整合
大规模神经网络训练的验证不足

评分¶

⭐ 创新性: 7/10 — 将AdaGrad思想应用到双层优化是自然但有价值的扩展
⭐ 实用性: 9/10 — 消除调参需求是实践中的重大便利
⭐ 写作质量: 8/10 — 理论推导完整，实验设计突出鲁棒性