Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization¶

会议: NeurIPS 2025
arXiv: 2509.15399
代码: 无
领域: 优化理论 / 层次化优化
关键词: minimax optimization, bilevel optimization, adaptive algorithm, convergence rate, stochastic gradient noise

一句话总结¶

首次为随机层次化优化（极小极大和双层优化）提供自适应且sharp的收敛保证，通过动量归一化技术和新型自适应参数选择，在无需事先知道噪声大小的情况下实现最优收敛率Õ(1/√T + √σ̄/T^{1/4})。

背景与动机¶

层次化优化（minimax和bilevel）是机器学习中的核心问题形式——对抗训练、元学习、超参数优化等都可以建模为此类问题。现有方法虽然有理论保证，但都需要预先知道随机梯度噪声的大小来设定步长等参数。当噪声水平未知或在训练过程中变化时，这些方法无法自动适应，导致实际收敛率远非最优。

核心问题¶

如何设计不需要预先知道梯度噪声大小σ̄的自适应优化算法，同时在非凸-强凹极小极大和非凸-强凸双层优化中都能达到sharp（最优）的收敛率？

方法详解¶

整体框架¶

结合动量归一化（momentum normalization）与新型自适应参数选择策略，使算法能够根据在线观测到的梯度信息自动调整步长，在不依赖先验噪声知识的前提下达到理论最优收敛速度。

关键设计¶

动量归一化技术：对梯度的动量估计进行归一化处理，使步长自动适应当前梯度噪声水平
自适应参数选择：不使用固定的学习率/步长，而是根据在线梯度统计量动态调整
双问题覆盖：同一框架同时处理minimax和bilevel两类层次化优化问题
Sharp收敛率：达到Õ(1/√T + √σ̄/T^{1/4})，匹配已知的理论下界

实验关键数据¶

在合成任务和深度学习任务上验证
在低噪声和高噪声两种regime下均表现有效
具体数值结果需要全文查看

消融实验要点¶

不同噪声水平下的自适应性验证
与非自适应方法在不同噪声regime下的对比

亮点¶

理论首创性：首个为随机层次化优化提供自适应+sharp收敛保证的工作
实用价值：消除了调参时对噪声水平先验知识的依赖
广覆盖：minimax和bilevel两类重要问题同时解决
理论最优：收敛率匹配下界，是sharp的

局限性 / 可改进方向¶

主要是理论贡献，大规模实验验证有限
仅考虑非凸-强凹/强凸设定，更一般的非凸-非凸情况待探索

与相关工作的对比¶

vs 非自适应层次化优化算法：这些方法需要σ̄作为输入参数；本工作自动适应
vs 自适应单层优化(如Adam)：本工作将自适应性扩展到更复杂的层次化优化结构

评分¶

新颖性: ⭐⭐⭐⭐ 自适应+sharp的理论保证是重要贡献
实验充分度: ⭐⭐⭐ 偏理论，实验规模有限
写作质量: ⭐⭐⭐⭐ 理论推导严谨
价值: ⭐⭐⭐⭐ 对优化理论社区有重要意义