arXiv:2410.08497cs.LGstat.ML2024-10IJCAI

提出更紧的极小极大问题风险界,加速收敛分析。

Towards Sharper Risk Bounds for Minimax Problems

  • 用局部统一收敛分析梯度泛化误差,突破传统限制。
  • 在非凸-强凹设定下实现高概率更优泛化界,提升速度至n倍。
  • 适用于梯度下降上升等算法,适合研究对抗训练与强化学习者。

极小极大问题在对抗训练、鲁棒优化和强化学习中取得成功。现有最优超额风险界由泛化误差与优化误差构成,在强凸-强凹(SC-SC)设置下为1/n速率。以往研究多聚焦特定算法的优化误差,对泛化性能关注较少,制约了风险界进一步提升。本文通过均匀局部收敛,分析原函数梯度的泛化界,得到非凸-强凹(NC-SC)随机极小极大问题的更紧高概率泛化误差界。此外,在外层满足Polyak-Lojasiewicz条件时,获得维度无关结果。基于该泛化界,我们分析了经验鞍点(ESP)、梯度下降上升(GDA)与随机梯度下降上升(SGDA)等常见算法,推导出在合理假设下的更好超额原始风险界,据我们所知,其收敛速度比现有结果快约n倍。

原文摘要 · Abstract (English)

Minimax problems have achieved success in machine learning such as adversarial training, robust optimization, reinforcement learning. For theoretical analysis, current optimal excess risk bounds, which are composed by generalization error and optimization error, present 1/n-rates in strongly-convex-strongly-concave (SC-SC) settings. Existing studies mainly focus on minimax problems with specific algorithms for optimization error, with only a few studies on generalization performance, which limit better excess risk bounds. In this paper, we study the generalization bounds measured by the gradients of primal functions using uniform localized convergence. We obtain a sharper high probability generalization error bound for nonconvex-strongly-concave (NC-SC) stochastic minimax problems. Furthermore, we provide dimension-independent results under Polyak-Lojasiewicz condition for the outer layer. Based on our generalization error bound, we analyze some popular algorithms such as empirical saddle point (ESP), gradient descent ascent (GDA) and stochastic gradient descent ascent (SGDA). We derive better excess primal risk bounds with further reasonable assumptions, which, to the best of our knowledge, are n times faster than exist results in minimax problems.

极小极大风险界对抗训练

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。