技术摘要：具有时变移动成本的无参数动态遗憾

1. 问题设定

本文研究了在非平稳环境下，学习者会产生**时变移动成本（time-varying movement costs）的无约束在线凸优化（Unconstrained Online Convex Optimization, OCO）**问题。

在标准的 OCO 设置中，学习者从凸空间 $\mathcal{W}$（在本研究中具体为 $\mathbb{R}^n$）中选择决策 $w_t$，并承受凸损失 $f_t(w_t)$。目标是最小化相对于比较序列 $(u_1, \dots, u_T)$ 的动态遗憾（dynamic regret）：
$$R_T(u_{1:T}) = \sum_{t=1}^T f_t(w_t) - \sum_{t=1}^T f_t(u_t)$$

本研究通过增加一个与连续决策之间的距离成比例的移动成本惩罚项来扩展该问题。至关重要的是，控制该成本的系数 $\lambda_t$ 是随时间变化且任意的。学习者的目标是最小化非对称动态遗憾（asymmetric dynamic regret）：
$$R_T(u_{1:T}, \lambda_{1:T}) = \sum_{t=1}^T \left( f_t(w_t) - f_t(u_t) + \lambda_t \|w_t - w_{t-1}\| \right)$$
请注意，在此非对称公式中，比较序列 $(u_t)$ 不承担移动成本惩罚，这使得该问题比对称变体更难。

主要挑战在于设计无参数（parameter-free）（即对比较器自适应）的算法，这些算法不需要预先知道以下信息：

1. 比较器范数界限 $M = \max_t \|u_t\|$。
2. 比较器路径长度 $P_T = \sum_{t=2}^T \|u_t - u_{t-1}\|$。
3. 梯度范数序列 $\|g_t\|$。
4. 移动成本系数序列 $\lambda_t$。

2. 方法论

作者提出了一个由三个主要部分组成的层次化算法框架：

A. 带有随时间变化的正则化的复合镜像下降（算法 1）

基础算法利用**复合镜像下降（Composite Mirror Descent）**更新。在每一轮 $t$，在观察到梯度 $g_t$ 和下一个移动成本 $\lambda_{t+1}$ 后，学习者通过最小化以下式子来更新 $w_{t+1}$：
$$w_{t+1} = \arg\min_{w} \left( \langle g_t, w \rangle + D_\psi(w | w_t) + \phi_t(w) \right)$$

• 正则化函数 $\psi(w)$： 一个旨在处理无界域的对数线性函数。
• 修正项 $\phi_t(w)$： 一个由 $\beta_t^2 = (\|g_t\| + \lambda_{t+1})^2$ 缩放的时变二次项。该项充当“动态摩擦”，使迭代过程稳定。当移动成本或梯度较高时，惩罚增加，限制更新；当它们较低时，惩罚放宽。

B. 无参数元算法（算法 2）

为了消除对 $M$、$P_T$ 以及梯度/移动规模的先验知识的需求，作者采用了一种元算法（meta-algorithm），该算法维护着算法 1 的一组具有不同学习率 $\eta_i$ 的并行实例网格。

• 学习者采取所有实例决策之和作为决策。
• 总遗憾被分解为“最佳”实例（近似最优 $\eta$）的遗憾加上来自其他实例的一个微小的加性成本。
• 结果： 这产生了一个遗憾界限 $\tilde{O}\left( \sqrt{(M + P_T) \sum_{t} (\|g_t\|^2 + \lambda_{t+1}^2) \|u_t\|} \right)$。
• 局限性： 该界限对移动成本呈二次方依赖（$\lambda_{t+1}^2$），当梯度较小但移动成本较高时，这并非最优。

C. 自适应一阶归约（算法 3）

为了将对移动成本的依赖从二次方改进为线性，作者引入了一种**自适应批处理（adaptive batching）**机制。

• 机制： 算法在一个周期（epoch）内将梯度累积到缓冲区 $H_\tau$ 中。只有当累积梯度范数 $\|H_\tau\|$ 超过当前移动成本 $\lambda_{t+1}$ 时，才会触发对基础学习器的更新。
• 逻辑： 如果移动成本很高，算法会等待直到“信号”（梯度）足够强大，足以抵消移动的“成本”。
• 结果： 这将遗憾对移动成本的依赖从 $\lambda^2$ 降低到了 $\lambda \|g\|$。

3. 核心贡献

1. 首个具有时变成本的无参数动态遗憾研究： 本文建立了针对具有任意、时变移动成本的无约束 OCO 的首个比较器自适应动态遗憾界限。
2. 最优自适应性： 所提算法能同时自适应于：
   • 比较器复杂度（$M$ 和 $P_T$）。
   • 实现的梯度序列（$\|g_t\|$）。
   • 时变移动系数（$\lambda_t$）。
3. 改进的移动成本依赖关系： 通过引入自适应批处理策略（算法 3），作者实现了遗憾对移动成本的依赖从 $\lambda^2$ 到 $\lambda \|g\|$ 的改进。在梯度较小的情形下，这相对于之前的二阶界限（依赖于 $\lambda_t^2$）是一个显著的提升。
4. 新颖的问题归约： 该框架被证明可以通过将其他在线学习问题转化为时变移动成本设置，从而作为解决这些问题的原语（primitive）：
   • 具有延迟反馈的 OCO： 缺失梯度的数量被视为移动成本的规模。
   • 具有时变记忆的 OCO： 记忆长度的波动被映射为时变移动成本。

4. 主要结果

理论保证

对于算法 3（改进版本），论文保证了如下动态遗憾：
$$\tilde{O}\left( (M + P_T)L + \sqrt{(M + P_T) \sum_{t=1}^T (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|} \right)$$
其中 $L$ 是与 $G + \lambda_{\max}$ 相关的类 Lipschitz 常数。

应用 1：延迟反馈

作者通过设置 $\lambda_t = G |m_t|$（其中 $|m_t|$ 是在时间 $t$ 缺失的梯度数量）将具有延迟反馈的 OCO 归约为其设置。

• 结果： 他们实现了无参数动态遗憾 $\tilde{O}\left( (M + P_T)L + G\sqrt{(M^2 + MP_T)(T + d_{\text{tot}})} \right)$。
• 优势： 通过处理无界域并实现对总延迟 $d_{\text{tot}}$ 而非最大延迟 $d_{\max}$ 的更紧凑依赖，改进了先前的工作（如 Wan et al., 2024），且无需“按序”反馈这一严格假设。

应用 2：时变记忆

作者将具有时变记忆（即损失取决于过去 $b_t$ 个决策）的 OCO 归约为其设置。

• 结果： 他们得到了遗憾界限 $\tilde{O}\left( (M + P_T)L + \sqrt{M(M + P_T)(H^2 T + GH \sum b_t^2)} \right)$。
• 优势： 这是针对无约束 OCO 具有时变记忆长度的第一个动态遗憾保证。通过移除有界域假设并优化对记忆长度序列的依赖，改进了 Zhao et al. (2023) 的工作。

5. 重要性与主张

论文声称其结果代表了在线学习中几个挑战性方向的统一：

• 统一性： 它弥合了无约束优化、动态遗憾和移动成本之间的鸿隙，这是一种此前从未被探索过的组合。
• 多功能性： 该框架表明，具有移动成本的 OCO 是一个强大的原语。通过简单地将“缺失信息”（在延迟反馈中）或“记忆依赖”（在时变记忆中）解释为移动惩罚，可以推导出这些复杂设置下的最优动态遗憾界限。
• 最优性： 作者断言，其对路径长度 $P_T$ 和比较器范数的依赖在（忽略对数因子的情况下）是极小极大（minimax）最优的，并且一阶对移动成本的依赖是实现具有波动惩罚设置下最优性的必要改进。
• 实用性： 算法是高效的，每轮仅需 $O(d \log T)$ 的计算量，与标准的无参数 OCO 算法复杂度相匹配。

该工作并不声称解决凸优化范围之外的问题，也不提供在真实世界数据集上的实验验证，而是专注于理论保证和归约。