高效处理非稳态在线学习的新方法

高效处理非稳态在线学习的新方法

彭昭， 谢燕峰， 张立军， 周志华； 26(208):1−66, 2025.

摘要

近年来，非稳态在线学习备受关注。具体而言，动态遗憾和自适应遗憾被提出作为非稳态环境下在线凸优化的两个原则性性能度量。为优化这两个指标，由于非稳态性固有的不确定性，通常采用双层在线集成方法，即维护多个基础学习器，并采用元算法动态追踪其中最佳者。然而，双层结构引发了计算复杂度的担忧——此类方法通常为一场T轮的在线博弈同时维护O(log T)个基础学习器，因此每轮需要在可行域上执行多次投影，当可行域复杂时，这就成为了计算瓶颈。

本文提出了优化动态遗憾和自适应遗憾的高效方法，将每轮所需的投影次数从O(log T)减少到1次。所提出的算法在每一轮仅需一次梯度查询和一次函数评估。我们的技术关键在于利用参数无关在线学习中开发的缩减机制，并针对非稳态在线方法进行了非平凡修改。此外，我们研究了一个更强的度量，即“区间动态遗憾”，并为了最小化该度量，将每轮投影次数从O(log² T)减少到1次。我们的缩减机制展示了广泛的通用性，并应用于两个重要领域：在线随机控制和在线主成分分析，从而产生了既高效又最优的方法。最后，实证研究验证了我们的理论发现。