提出新型随机方向，实现无需窗口平滑的在线双层优化新算法
Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
- 设计新搜索方向，支持一阶与零阶随机在线双层优化
- 在快速变化场景下实现次线性随机后悔值，优于现有方法
- 适合需要动态调参或黑盒攻击的在线学习任务
在线双层优化（OBO）是机器学习中动态目标随时间演化的强大框架，要求持续更新。现有方法依赖确定性的窗口平滑后悔最小化，在函数快速变化时可能无法准确反映系统性能。本文提出一种新型搜索方向，证明基于该方向的一阶与零阶（ZO）随机OBO算法可在无需窗口平滑的情况下实现次线性随机双层后悔。此外，该框架通过：(i) 降低超梯度估计的查询依赖，(ii) 同步求解线性系统并更新内层与外层变量，(iii) 使用零阶方法估计海森、雅可比及梯度，提升了效率。在在线参数损失调优与黑盒对抗攻击实验中验证了方法的有效性。
原文摘要 · Abstract (English)
Online bilevel optimization (OBO) is a powerful framework for machine learning problems where both outer and inner objectives evolve over time, requiring dynamic updates. Current OBO approaches rely on deterministic \textit{window-smoothed} regret minimization, which may not accurately reflect system performance when functions change rapidly. In this work, we introduce a novel search direction and show that both first- and zeroth-order (ZO) stochastic OBO algorithms leveraging this direction achieve sublinear {stochastic bilevel regret without window smoothing}. Beyond these guarantees, our framework enhances efficiency by: (i) reducing oracle dependence in hypergradient estimation, (ii) updating inner and outer variables alongside the linear system solution, and (iii) employing ZO-based estimation of Hessians, Jacobians, and gradients. Experiments on online parametric loss tuning and black-box adversarial attacks validate our approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。