arXiv:2508.00392cs.LG2025-08

提出可自适应多种函数与环境的通用算法,解决在线学习中动态变化问题。

Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions

  • 构建元专家框架,动态生成专家并用元算法聚合。
  • 无需预先知道函数类型,可同时处理凸、指数凹和强凸函数。
  • 适用于静态或变化环境,适合实际复杂场景应用。

为应对环境变化,提出了自适应遗憾(adaptive regret)这一新性能度量,定义为任意区间内静态遗憾的最大值。在在线凸优化设置下,已有算法能有效最小化自适应遗憾,但现有方法缺乏普适性,仅适用于特定类型的凸函数,且需预先知晓参数,限制了其在真实场景的应用。为此,本文研究具有双重自适应性的通用算法,可自动适应函数性质(凸、指数凹或强凸)及环境特性(平稳或变化)。具体地,提出一种元专家框架,动态创建多个专家并通过元算法聚合;元算法需满足二阶边界,以适应未知函数类型。进一步引入睡眠专家技术捕捉环境变化。在专家构造上,采用增加专家数量或提升专家能力两种策略实现普适性。理论分析表明,所提算法能同时最小化多种凸函数的自适应遗憾,且允许函数类型在轮次间切换。此外,将元专家框架扩展至在线复合优化,开发出复合函数自适应遗憾的通用算法。

原文摘要 · Abstract (English)

To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existing algorithms lack universality in the sense that they can only handle one type of convex functions and need apriori knowledge of parameters, which hinders their application in real-world scenarios. To address this limitation, this paper investigates universal algorithms with dual adaptivity, which automatically adapt to the property of functions (convex, exponentially concave, or strongly convex), as well as the nature of environments (stationary or changing). Specifically, we propose a meta-expert framework for dual adaptive algorithms, where multiple experts are created dynamically and aggregated by a meta-algorithm. The meta-algorithm is required to yield a second-order bound, which can accommodate unknown function types. We further incorporate the technique of sleeping experts to capture the changing environments. For the construction of experts, we introduce two strategies (increasing the number of experts or enhancing the capabilities of experts) to achieve universality. Theoretical analysis shows that our algorithms are able to minimize the adaptive regret for multiple types of convex functions simultaneously, and also allow the type of functions to switch between rounds. Moreover, we extend our meta-expert framework to online composite optimization, and develop a universal algorithm for minimizing the adaptive regret of composite functions.

在线学习凸优化自适应算法

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