提出无需海森矩阵的可微优化层，加速训练并节省内存。
A Fully First-Order Layer for Differentiable Optimization
- 将可微优化转为双层问题，用一阶信息计算梯度。
- 梯度计算时间复杂度为$ ilde{O}(1)$，整体复杂度$ ilde{O}(δ^{-1}ε^{-3})$。
- 开源库支持快速集成，适合需要高效优化的模型开发者。
可微优化层使系统通过求解嵌入式优化问题做出决策。然而，通过隐式微分计算梯度需解包含海森项的线性系统，计算和内存开销大。为此，我们提出一种新算法，仅用一阶信息计算梯度。核心思路是将可微优化重写为双层优化问题，并利用双层方法最新进展。具体地，引入主动集拉格朗日超梯度算子，避免海森矩阵计算，并提供有限时间、非渐近的近似保证。我们证明，近似超梯度可用仅一阶信息在$ ilde{O}(1)$时间内计算，从而使得约束双层优化的整体复杂度为$ ilde{O}(δ^{-1}ε^{-3})$，达到非光滑非凸优化的最佳已知速率。此外，我们发布了开源Python库，可轻松从现有求解器适配。源码见https://github.com/guaguakai/FFOLayer。
原文摘要 · Abstract (English)
Differentiable optimization layers enable learning systems to make decisions by solving embedded optimization problems. However, computing gradients via implicit differentiation requires solving a linear system with Hessian terms, which is both compute- and memory-intensive. To address this challenge, we propose a novel algorithm that computes the gradient using only first-order information. The key insight is to rewrite the differentiable optimization as a bilevel optimization problem and leverage recent advances in bilevel methods. Specifically, we introduce an active-set Lagrangian hypergradient oracle that avoids Hessian evaluations and provides finite-time, non-asymptotic approximation guarantees. We show that an approximate hypergradient can be computed using only first-order information in $\tilde{O}(1)$ time, leading to an overall complexity of $\tilde{O}(δ^{-1}ε^{-3})$ for constrained bilevel optimization, which matches the best known rate for non-smooth non-convex optimization. Furthermore, we release an open-source Python library that can be easily adapted from existing solvers. The source code is available at https://github.com/guaguakai/FFOLayer.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。