Dynamic Regret in Online Convex Optimization with Indicator Switching Costs¶
会议: NeurIPS 2026（任务清单归档；所读版本为 arXiv v1）
arXiv: 2609.30556
领域: 优化/理论
关键词: 在线凸优化、动态遗憾、指示切换成本、最大耦合、强自适应遗憾
一句话总结¶
本文把二进制尺度重启的随机惰性 FTRL 分布交给切换感知元学习器，以最大耦合控制真实动作变化，在期望意义下获得分段常数比较器的近最优动态遗憾，并给出适用于小路径长度比较器的另一条保证。
研究背景与动机¶
在线凸优化中，学习器先选动作，随后才看到本轮损失函数。动态遗憾允许比较器随时间变化，但生产环境里的模型重新部署、缓存更新或服务器启动可能对每一次改变收取固定费用：即使两个动作只差一点，仍然付费。范数切换成本允许“每轮小步移动”，指示切换成本却要求真正重复同一动作。在直径有界的决策域上，控制动作变化次数可以控制范数移动量，反过来并不成立。
已有惰性在线凸优化主要解决静态比较器。FPRLL 保留完整历史，能导出随机最优解的可求值密度，再通过惰性采样减少变化次数；但历史累积让它难以应对环境反转。本文证明，不重启的这一算法族即使面对只切换一次的比较器，也可能有线性动态遗憾。固定周期重启又遇到另一个障碍：周期长，区间内部的变化跟不上；周期短，重新开始的代价不断累积。另一方面，直接改用递归的镜像下降更新，不容易获得最大耦合所需的动作密度。
本文因此不试图寻找一个预先最优的重启周期，而是同时保留多个周期，并让元学习器在任意局部区间上选择合适尺度。这里不能只按预测损失挑选专家，否则专家内部变化和专家权重变化都可能引入额外切换费用。核心 idea：在密度空间聚合多尺度惰性 FTRL，把专家的总变差计入代理损失，再用切换感知的强自适应元学习器控制混合权重变化。
方法详解¶
整体框架¶
输入是有界凸决策域以及逐轮揭示的完整凸损失函数，输出是随机动作序列；不存在离线训练集或神经网络训练阶段。算法维护二进制重启专家，由各专家提供 FPRLL 密度，混合后在相邻混合分布之间最大耦合采样。动作执行、损失揭示之后，切换感知元学习器更新下一轮权重；各专家也更新自己的累计目标，必要时重启。
性能指标对学习器收取切换费，而不对比较器收取切换费：
比较器复杂度由两种不同的量衡量。切换次数只看是否变化，路径长度则累加欧氏距离：
若决策域直径是 \(D\)，则 \(P_T\le DS_T\)，但每轮都移动很小距离的比较器可以有很大的 \(S_T\) 和很小的 \(P_T\)。算法不需要预先知道这两个量，也不根据事后较小的那个量重新运行。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["过去损失与当前轮次"] --> B["二进制重启"]
B --> C["FPRLL 密度"]
C --> D["混合最大耦合"]
D --> E["执行动作<br/>随后揭示完整损失"]
E --> F["切换感知元学习"]
C -. "专家期望损失与 TV<br/>或附录 F 的代理量" .-> F
F -. "下一轮混合权重" .-> D
E -. "更新累计目标" .-> A实线表示本轮决策与损失反馈次序，虚线表示专家评分和下一轮状态更新。这里混合的是动作分布，不是多个专家动作的加权平均；后者在连续域上通常仍会每轮变化。
关键设计¶
1. 二进制重启：让局部区间有一个从正确位置开始的专家
算法维护 \(\mathcal{H}=\{1,2,4,\ldots,2^{\lfloor\log_2T\rfloor}\}\) 中的所有周期，共 \(K=\lfloor\log_2T\rfloor+1\) 个专家。周期为 \(H\) 的专家每隔 \(H\) 轮清除本块历史，重新运行一次 FPRLL。短周期专家迅速遗忘旧环境，长周期专家则减少重启代价；这不是把未知变化点直接提供给算法。
尺度选择能覆盖任意局部区间，是因为任意长度为 \(L\) 的区间可以分割成至多 \(2\lceil\log_2L\rceil+2\) 个相邻二进制区间。这些块的长度平方根之和至多为 \((2+\sqrt{2})\sqrt{L}\)。每个块都有一个恰好在其起点重启、且周期等于块长的专家。因此，区间遗憾不是靠“整段碰巧落在一个重启块内”来保证，而是靠几何覆盖以及元学习器对每个子区间的竞争保证。
固定周期为什么不够，附录 B 给出了算法族下界。不重启时，先持续一种线性梯度、再反转梯度的两阶段序列，让全历史领头者迟迟无法改向；定理 17 用对称扰动和配对论证得到至少 \(T/2\) 的期望损失遗憾。重启版本则存在长周期跟踪代价与短周期静态代价的冲突。这些结论针对所分析的 FPRLL 结构，不是说所有在线算法都无法追踪变化。
2. FPRLL 密度：用扰动最优解的分布而非递归动作更新作为接口
每个专家在当前块内累计已经揭示的原始损失，加上二次正则项及缩放对数障碍。二次项使累计目标强凸，障碍把扰动最优解留在内部；新揭示的损失只需凸，不需要强凸。原文把决策域写成有限个凹约束 \(s_c(x)\ge0\)，并设原点严格可行且 \(s_c(0)=1\)，以构造障碍及收缩比较器。
设当前块起点为 \(a\)，用 \(F_{t-1}\) 表示正则项、障碍与从 \(a\) 到 \(t-1\) 的累计损失。采样拉普拉斯扰动 \(p\) 后，求解扰动目标的最小值；从最优性条件及变量代换得到：
这里 \(\nu(p)=(2\mu)^{-d}\exp(-\|p\|_1/\mu)\)。密度公式的作用不是声称优化便宜，而是允许在给定位置比较新旧密度；最大耦合正需要这种点值访问。元算法把专家当密度接口使用，不要求先生成所有专家的惰性动作，再选其中一个。
专家在长度为 \(H\) 的块内按块长调整收缩参数、正则强度和扰动尺度。原文取 \(\gamma=1/\sqrt{H}\)、\(\mu_H=\sqrt{\lambda GH/(R\sqrt{2})}\)、\(\sigma_H=\sqrt{(G^2+2\lambda\beta d)H}/R\)，其中 \(R\) 是决策域半径，\(G\) 是 Lipschitz 常数，\(\beta\) 是平滑常数。静态块遗憾达到平方根阶，块内总变差则由正则强度和扰动尺度控制。
证明上，附录 C 将预测遗憾拆成静态稳定性、比较器漂移及收缩误差，再加总变差切换项。漂移项包含累计历史长度乘路径长度，这解释了为什么长周期专家适合稳定区间，但单个长期 FPRLL 并不能自然得到最优动态遗憾。
3. 混合最大耦合：把密度变化精确变成动作切换概率
主学习器用权重 \(v_t\) 形成混合密度。连续域中独立重采样几乎必然改变动作，因此即使两个分布很接近，也不能每轮独立抽取。最大耦合先尝试复用上一动作，只有无法复用时才从新分布的剩余部分抽取。
总变差距离定义为两个密度绝对差积分的一半，取值在 \([0,1]\)。具体地，在旧动作处以新旧密度比决定是否保留；保留失败，就从新分布反复提议，并拒绝落入新旧共有部分的提议。附录 A 的引理 16 证明两件事：下一动作仍有正确边缘分布，变化概率恰好等于总变差。概率恒等式是期望分析的基础，不是每条随机动作轨迹的确定性保证。
由于专家密度变化和混合权重变化都会改变主分布，引理 10 将两者分离：
附录 E.1 的证明先添加并减去“新权重、旧专家分布”的混合，再用三角不等式。权重变化的正负质量相等，因此其代价是权重的 \(\ell_1\) 移动量的一半，而不是任意额外的专家切换预算。
4. 切换感知元学习：既追踪好尺度，也支付切换尺度的代价
每个专家的代理损失包含它的期望预测损失和自身密度移动代价：
使用已知上界 \(\lambda\) 而非逐轮实际费用 \(\lambda_t\)，使该代理量保守覆盖学习器的实际切换成本。主学习器的期望成本因此至多为加权代理损失，再加 \(\lambda\|v_t-v_{t-1}\|_1/2\)。这把连续动作问题变成有限专家上的切换感知在线线性优化，而不是普通的无移动惩罚专家问题。
元学习器采用 Daniely–Mansour 的折扣正态预测器机制。其内部还维护多个时间尺度的 fixed-share 学习器，并用二路软组合器从粗到细合并；组合器用折扣累计代理损失差调整门控权重，同时把内部权重移动费用计入评分。这里内部时间尺度与外层 FPRLL 重启周期是两层不同对象。
损失有界确保 \(M=M_f+\lambda\) 能归一化代理向量；附录 E.3 取离散专家切换参数 \(D_{\mathrm{meta}}=\lambda/M\)，换回单纯形后对应上述 \(\lambda/2\) 系数。引理 11 在每个长度为 \(L\) 的区间给出相对最佳固定尺度的额外费用 \(C_{\mathrm{dm}}\sqrt{M(M+\lambda)L\log(KT)}\)。这正是从局部块保证拼成强自适应保证所缺少的一环。
一个完整示例¶
考虑 \(T=8\) 的示意运行，外层专家周期是 \(1,2,4,8\)。周期为 \(2\) 的专家在第 \(1,3,5,7\) 轮重启，周期为 \(4\) 的专家在第 \(1,5\) 轮重启。假设环境在第 \(5\) 轮进入新阶段，这两个专家恰好都能从新阶段重新累计；周期为 \(8\) 的专家仍保留早期历史。
这并不表示主学习器第 \(5\) 轮必然换动作。它先按本轮混合密度与上一轮混合密度做最大耦合，可以保留原动作；损失揭示之后，才计算各尺度的反馈并调整第 \(6\) 轮权重。若某专家重启，实用代理只按总变差上界 \(1\) 记账，而非宣称其实际切换概率就是 \(1\)。这只是时序示例，不是论文实验，也不提供测得的收益。
损失函数 / 训练策略¶
这里的“训练”是在线更新，不是离线拟合。原文假设完整损失函数在动作执行后揭示，不能把方法理解成只观察所选动作损失的 bandit 算法。精确期望损失和高维总变差一般不能直接计算，正文的精确代理主要服务于分析。
附录 F 以独立辅助采样估计损失，并以可计算的保守量替代总变差。记 \(\epsilon_H=\beta d/\sigma_H+\sqrt{d}G/\mu_H\)，其规则是：
辅助样本在损失揭示后、每轮每个尺度新抽取，并在给定历史时独立于当前元动作。因此条件均值是 \(\bar g_t^{(H)}=\ell_t^{(H)}+\lambda\hat c_t^{(H)}\ge g_t^{(H)}\)；它无偏估计的是这个上界，而不是精确代理。附录 F 说明，块内和重启边界的上界与基础证明已经使用的费用一致，所以仍保留同阶期望保证。
复杂度只可分层描述：\(K=\mathcal{O}(\log T)\) 个专家的元层额外开销为每轮 \(\mathcal{O}(\log^2T)\)。总成本还包括各专家目标更新、扰动优化、Hessian 行列式/密度点值、辅助样本以及最大耦合的拒绝采样；论文没有给出这些操作合起来的统一维度相关运行时保证。
实验关键数据¶
原文无经验实验，以下为理论结果与假设比较。
主实验¶
下表是定理对比，不是数据集成绩。期望针对算法随机性；下界的随机对抗分布还需要对其随机性取期望。主上界对每个固定比较器序列、所有区间同时适用，不需要预先输入 \(S_T\) 或 \(P_T\)，但不是一次随机运行上同时成立的高概率结论。
| 理论结果 | 保证或下界 | 适用边界与证据 |
|---|---|---|
| 强自适应遗憾 | \(\tilde{\mathcal{O}}(\sqrt{L})\) | 任意区间和固定比较器；定理 12、附录 E.4 |
| 分段常数动态遗憾 | \(\tilde{\mathcal{O}}(\sqrt{(S_T+1)T})+\lambda S_T\) | 每个比较器序列；推论 13、附录 E.5 |
| 路径长度动态遗憾 | \(\tilde{\mathcal{O}}(\max\{T^{2/3}P_T^{1/3},\sqrt{T}\})\) | 每个比较器序列；定理 14、附录 E.6 |
| 不重启 FPRLL | 至少 \(T/2\) 的期望损失遗憾 | 一维线性损失、一次比较器切换；定理 17 |
| 固定周期跟踪下界 | \(\Omega(k\tau/\log(T/\tau))\) | 存在一个 oblivious 分布，对所有整数 \(4\le k\le T/\tau\) 困难，且 \(T\ge4\tau\)；定理 8 |
| 固定周期联合下界 | \(\Omega(k\tau/\log(T/\tau)+T/\sqrt{k})\) | 分布可依赖固定 \(k\)；静态分支另假设每块期望切换至多 \(C\sqrt{k}\)；命题 20、引理 19 |
推论 13 的额外 \(\lambda S_T\) 来自比较器分段边界上的学习器切换，不是比较器自己被收费。对固定问题常数，它可被平方根主阶吸收；若让 \(\lambda\) 随 \(T\) 增长，则不能忽略常数依赖。正文的统一式为 \(\tilde{\mathcal{O}}(\min\{\sqrt{(S_T+1)T},T^{2/3}(P_T+1)^{1/3}\})\)，但保留定理 14 的最大值形式更能反映 \(P_T=0\) 的边界。
消融实验¶
以下是理论条件与机制分析，不是删模块后的经验消融。
| 条件或机制 | 原文要求/作用 | 不能据此声称 |
|---|---|---|
| 决策域 | 凸、有界，半径 \(R\)、直径 \(D\)；密度实现另使用严格可行原点和有限凹约束的障碍表示 | 无界域保证或任意不可求值域的高效实现 |
| 损失函数 | 二次可微、凸、\(G\)-Lipschitz、\(\beta\)-平滑，且 \(0\le f_t\le M_f\) | 新损失必须强凸，或已经去掉平滑假设 |
| 切换系数 | \(0<\lambda_t\le\lambda\)，已知 \(\lambda>0\) | 对未知、任意无界切换费用自适应 |
| 最大耦合 | 保持正确边缘分布，并以 TV 实现变化概率 | 独立采样也具有相同切换保证 |
| 实用代理 | 条件均值是精确代理的上界；附录 F | 对精确 \(g_t^{(H)}\) 的无偏估计 |
| 对抗范围 | 引理 26 及 E.3 明确使用 oblivious 损失；附录 F 要求辅助样本的条件独立性 | 自动推广到观察学习器当前动作后选损失的 adaptive adversary |
关键发现¶
- 分段常数分支达到忽略对数因子的 minimax 阶，是同一个算法的保证，不是已知变化点的 oracle 结果。
- 路径分支来自 \(AT/\sqrt{k}+(B+G)P_Tk\) 的周期权衡，内点最优周期随 \((T/P_T)^{2/3}\) 缩放，并需裁剪到 \([1,T]\)。这解释了 \(T^{2/3}P_T^{1/3}\)，而非范数成本中的平方根路径率。
- 路径长度为零时仍有静态遗憾基线 \(\sqrt{T}\)；不能把纯乘积率误读为零遗憾。证明 C.1 的裁剪边界和定理 14 比定理 7 的简写更完整。
亮点与洞察¶
- 密度级惰性采样把“少改参数”变成“重复完全相同的动作”。固定启动开销需要这种离散的稳定性，单纯控制距离不够。
- 代理损失不只是方便优化的替代目标，而是对实际切换成本的分解。专家内部 TV 与主权重移动分别定价，避免元学习过程抹掉基础专家的惰性收益。
- 几何覆盖让一个周期一个专家就能服务任意区间。关键不是给每个可能起点新建专家，而是同时具有匹配的重启块与元层局部竞争能力。
局限与展望¶
- 作者明确指出，指示成本下能否达到 \(\tilde{\mathcal{O}}(\sqrt{T(1+P_T)})\) 仍是开放问题；本文没有证明当前路径率对所有算法最优。固定周期算法族下界不能代替一般 minimax 下界。
- 没有经验实验、实现吞吐量或高维采样评估。可求值密度不等于便宜的密度积分、扰动优化或拒绝采样，元层多对数开销也不等于端到端运行时间。
- 主结论不能无条件扩展到自适应对抗者。所导入的专家定理明确假设 oblivious 损失，辅助随机反馈的讨论不等于解决动作依赖损失。
- 精确常数存在需核对之处：引理 22 证明把两点距离以半径 \(R\) 控制，一般只能直接保证至多 \(2R\)；推论 6 将含常数项的表达式写成 \(C_{\mathrm{base}}\sqrt{k}\) 的等号，按定义应理解为上界。这些不改变笔记所述阶数，但不宜把原文常数当成已独立核证。
- 周期 \(H=1\) 的调参给出 \(\gamma=1\)，而基础定义要求 \(\gamma\in(0,1)\)；单轮专家的端点处理未在所读文本中单独说明。实际实现前应补充约定，而不是默默假设障碍构造在该端点无问题。
相关工作与启发¶
- vs Sherman–Koren 的 Lazy OCO：已有 FPRLL 主要控制静态遗憾与切换预算；本文保留其密度和耦合工具，但通过多尺度重启及元层得到局部与动态保证。
- vs Revisiting Smoothed Online Learning：范数成本已有 \(\mathcal{O}(\sqrt{T(1+P_T)})\) 路径保证；本文面对每次变化都收费的更强稳定性要求，采用 TV 聚合，路径率仍较弱。
- vs Daniely–Mansour：折扣正态预测器提供切换感知的强自适应专家工具；本文的新连接是将一般凸动作密度问题归约成该有限专家问题，而不是重新发明整个元学习器。
- 研究线索：可研究不依赖平滑 Hessian 的可耦合基础分布，或更紧的路径变化分析；判断能否改善路径率时，须把算法族障碍与一般指示成本障碍分开。此处仅为后续方向，不是本文已证明的结论。
评分¶
- 新颖性: 4/5 — 将指示切换控制与动态/强自适应遗憾结合，归约结构清晰。
- 实验充分度: 不适用 — 纯理论论文，无经验实验；正文和附录提供上下界证明。
- 写作质量: 4/5 — 主线和证明分层清楚，但部分常数、端点与对抗范围需谨慎理解。
- 价值: 4/5 — 为固定重配置开销提供理论工具，路径最优性与高效实现仍待解决。