无需调参的双层优化新算法，理论保证收敛性。
Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis
- 提出两种免调参算法，通过梯度累积反比自适应调整步长。
- 迭代次数分别为 $O(1/ε)$ 和 $O(1/ε\log^4(1/ε))$，逼近最优解。
- 首次实现完全免调参且有理论保障，适合复杂模型训练场景。
双层优化在机器学习中应用广泛，但现有方法依赖对问题参数的先验知识来设定步长，导致参数未知时需大量调参。本文提出两种新型免调参算法：D-TFBO 采用双循环结构，步长通过“累计梯度范数倒数”策略自适应调整；S-TFBO 为更简单的全单循环结构，同时更新三个变量，并基于理论设计所有变量的自适应步长。我们为两者提供完整收敛性分析，证明 D-TFBO 和 S-TFBO 分别只需 $O(1/ε)$ 与 $O(1/ε\log^4(1/ε))$ 次迭代即可找到 $ε$-精确驻点，近乎匹配已知参数下表现良好的经典方法。实验表明，新方法性能媲美成熟调参方案，且对初始步长选择更鲁棒。据我们所知，这是首个完全消除步长调参需求并具备理论保障的方法。
原文摘要 · Abstract (English)
Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require $O(\frac{1}ε)$ and $O(\frac{1}ε\log^4(\frac{1}ε))$ iterations to find an $ε$-accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。