arXiv:2409.10470math.OCcs.LG2024-09被引 2

提出新型在线双层优化算法,提升超参数与元学习的动态适应能力。

Online Nonconvex Bilevel Optimization with Bregman Divergences

  • 基于Bregman散度设计自适应优化器,融合问题几何特性
  • 实现次线性局部后悔率,理论性能优于现有方法
  • 适用于实时数据流场景,尤其适合在线超参数调优

双层优化在机器学习中日益重要,尤其适用于超参数优化和元学习。与离线设置相比,在线双层优化(OBO)通过处理时变函数和逐次到达的数据,提供了更动态的框架。本文研究在线非凸-强凸双层优化问题。在确定性情况下,提出一种新型在线Bregman双层优化器(OBBO),利用自适应Bregman散度;通过新颖的超梯度误差分解,改进了已知的次线性局部后悔率。在随机情形下,首次提出随机在线双层优化器(SOBBO),采用滑动窗口平均法,用近期超梯度的加权平均更新外层变量,不仅实现次线性局部后悔率,还作为有效方差减少策略,避免每步额外采样随机梯度。在在线超参数优化和在线元学习上的实验表明,基于Bregman的算法相比已有在线与离线双层基准表现更优、效率更高、适应性更强。

原文摘要 · Abstract (English)

Bilevel optimization methods are increasingly relevant within machine learning, especially for tasks such as hyperparameter optimization and meta-learning. Compared to the offline setting, online bilevel optimization (OBO) offers a more dynamic framework by accommodating time-varying functions and sequentially arriving data. This study addresses the online nonconvex-strongly convex bilevel optimization problem. In deterministic settings, we introduce a novel online Bregman bilevel optimizer (OBBO) that utilizes adaptive Bregman divergences. We demonstrate that OBBO enhances the known sublinear rates for bilevel local regret through a novel hypergradient error decomposition that adapts to the underlying geometry of the problem. In stochastic contexts, we introduce the first stochastic online bilevel optimizer (SOBBO), which employs a window averaging method for updating outer-level variables using a weighted average of recent stochastic approximations of hypergradients. This approach not only achieves sublinear rates of bilevel local regret but also serves as an effective variance reduction strategy, obviating the need for additional stochastic gradient samples at each timestep. Experiments on online hyperparameter optimization and online meta-learning highlight the superior performance, efficiency, and adaptability of our Bregman-based algorithms compared to established online and offline bilevel benchmarks.

双层优化在线学习Bregman散度超参数优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。