用经验费雪信息矩阵替代海森逆，加速双层优化求解
Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementation
- 以经验费雪矩阵近似海森逆，同步更新降低计算开销
- 理论证明误差与样本复杂度达到顶尖水平，计算耗时大幅减少
- 适合大规模机器学习中的双层优化任务，尤其看重效率的场景
本文提出自然超梯度下降（NHGD），用于求解双层优化问题。为克服超梯度估计中计算或近似海森逆带来的计算瓶颈，我们利用内层优化问题的统计结构，采用经验费雪信息矩阵作为海森逆的渐近一致替代品。该设计支持并行的‘优化-近似’框架，使海森逆近似与随机内层优化同步更新，仅以可忽略的额外成本复用梯度信息。主要理论贡献在于建立了高概率误差界与样本复杂度保证，其性能与现有最优-后-近似方法相当，但显著降低了计算时间开销。在典型双层学习任务上的实验进一步验证了NHGD的实际优势，凸显其在大规模机器学习场景下的可扩展性与有效性。
原文摘要 · Abstract (English)
In this work, we propose Natural Hypergradient Descent (NHGD), a new method for solving bilevel optimization problems. To address the computational bottleneck in hypergradient estimation--namely, the need to compute or approximate Hessian inverse--we exploit the statistical structure of the inner optimization problem and use the empirical Fisher information matrix as an asymptotically consistent surrogate for the Hessian. This design enables a parallel optimize-and-approximate framework in which the Hessian-inverse approximation is updated synchronously with the stochastic inner optimization, reusing gradient information at negligible additional cost. Our main theoretical contribution establishes high-probability error bounds and sample complexity guarantees for NHGD that match those of state-of-the-art optimize-then-approximate methods, while significantly reducing computational time overhead. Empirical evaluations on representative bilevel learning tasks further demonstrate the practical advantages of NHGD, highlighting its scalability and effectiveness in large-scale machine learning settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。