首次分析一阶双层极小极大优化的泛化能力，揭示稳定与泛化的权衡关系。
On the Stability and Generalization of First-order Bilevel Minimax Optimization
- 基于算法稳定性理论，推导三种梯度方法的泛化界
- 发现算法稳定性、泛化误差与实际设置间的精确权衡
- 适用于超参数优化、强化学习等双层极小极大任务
双层优化和双层极小极大优化近年来成为机器学习中一系列任务的统一框架，包括超参数优化和强化学习。现有研究集中于经验效率和收敛性保证，但对这些算法泛化能力的理论理解仍存在关键空白。为此，本文首次针对具有下层极小极大问题的一阶梯度双层极小极大求解器，提供系统性的泛化分析。通过算法稳定性论证，我们为三种代表性算法——单时标随机梯度下降-上升法，以及两种双时标随机梯度下降-上升法变体——导出了精细的泛化边界。结果揭示了算法稳定性、泛化差距与实际设置之间的精确权衡。此外，大量实验评估验证了理论洞察在具有双层极小极大结构的真实优化任务中的有效性。
原文摘要 · Abstract (English)
Bilevel optimization and bilevel minimax optimization have recently emerged as unifying frameworks for a range of machine-learning tasks, including hyperparameter optimization and reinforcement learning. The existing literature focuses on empirical efficiency and convergence guarantees, leaving a critical theoretical gap in understanding how well these algorithms generalize. To bridge this gap, we provide the first systematic generalization analysis for first-order gradient-based bilevel minimax solvers with lower-level minimax problems. Specifically, by leveraging algorithmic stability arguments, we derive fine-grained generalization bounds for three representative algorithms, including single-timescale stochastic gradient descent-ascent, and two variants of two-timescale stochastic gradient descent-ascent. Our results reveal a precise trade-off among algorithmic stability, generalization gaps, and practical settings. Furthermore, extensive empirical evaluations corroborate our theoretical insights on realistic optimization tasks with bilevel minimax structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。