提出无需海森向量积的在线双层优化算法，显著降低计算成本。
Fully First-Order Algorithms for Online Bilevel Optimization
- 将双层问题重构成带不等式约束的单层问题，避免使用海森向量积
- 理论证明算法达到O(log T + V_T)的次线性后悔界，优于已有方法
- 适用于需要低计算开销的在线学习场景，如自适应控制与元学习
本文研究仅使用一阶信息的非凸-强凸在线双层优化（OBO）问题。现有算法多基于超梯度下降，需访问海森向量积（HVP）且计算成本高。通过将原问题重构为带不等式约束的单层在线问题，并构造拉格朗日函数序列，我们消除了隐式微分带来的HVP需求。提出一种完全一阶的OBO算法，理论上证明其后悔界为$O(1 + V_T + H_{2,T})$，总迭代次数为$O(T\log T)$，其中$V_T$衡量函数值变化，$H_{2,T}$刻画内层最优解漂移。在单循环结构下引入额外梯度变差项，获得子线性后悔界。进一步设计自适应内层迭代版本，消除对$H_{2,T}$的依赖，实现$O(\log T + V_T)$的后悔界。在随机设置下，全一阶算法的后悔界为$O(T^{2/3}(1 + σ^2) + V_T + H_{2,T})$。数值实验验证了算法可行性并支持理论结果。
原文摘要 · Abstract (English)
In this work, we study nonconvex-strongly convex online bilevel optimization (OBO) using only first-order oracle. Existing OBO algorithms are mainly based on hypergradient descent, which requires access to a Hessian-vector product (HVP) oracle and potentially incurs high computational costs. By reformulating the original OBO problem as a single-level online problem with inequality constraints and constructing a sequence of Lagrangian function, we eliminate the need for HVPs arising from implicit differentiation. Specifically, we propose a fully first-order algorithm for OBO, and provide theoretical guarantees showing that it achieves regret of $O(1 + V_T + H_{2,T})$ with a total of $O(T\log T)$ iterations, where $V_T$ measures the variation in function values and $H_{2,T}$ characterizes the drift variation of the inner-level optimal solution. We also establish a sublinear regret bound under the single-loop structure by introducing additional gradient-variation terms. Furthermore, we develop an improved variant with an adaptive inner-iteration scheme, which removes the dependence on $H_{2,T}$ and achieves regret of $O(\log T + V_T)$. Finally, under the stochastic OBO setting, we establish the regret bound for the fully first-order algorithm, i.e., $O(T^{2/3}(1 + σ^2) + V_T + H_{2,T})$. Numerical experiments demonstrate the feasibility of our algorithm and support our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。