arXiv:2609.06921cs.LGcs.AI2026-09

在噪声约束下实现在线优化,兼顾后悔与违规代价的平衡。

Constrained Online Learning with Noisy Constraint Values

  • 设计新算法 LEDGER,通过追踪净消耗余额来动态调整约束权重。
  • 在固定参数下,实现 $O(\ rac{\sqrt{T}}{V})$ 回报损失和 $O(\sqrt{V}T^{3/4} + \sigma\sqrt{T})$ 预算违规。
  • 无需 Slater 条件,适用于预测性路径,适合资源受限的在线决策场景。

我们研究对抗性约束下的在线凸优化问题,其中约束值和梯度通过无偏噪声观测。标准差为 $\sigma$ 的高斯值噪声导致最大期望后悔与期望硬违规的最坏情况下界为 $\Omega(\min\{\sigma,1\}T/\log^7T)$,即使已知梯度也无法实现任何联合 $O(T^{1-\delta})$ 的保证($\delta > 0$ 固定,噪声水平正)。因此我们转向预算违规:在固定时域内任意窗口的最大累计超支。提出 LEDGER 算法,通过非负余额追踪观测到的净消耗,并在当前反馈噪声前设定约束权重。在常见可行性与条件有限方差反馈下,对固定问题参数, LEDGER 实现 $O(\sqrt{T}/V)$ 期望后悔与 $O(\sqrt{V}\,T^{3/4} + \sigma\sqrt{T})$ 期望预算违规,$V\in[T^{-1/2},1]$。当 $V=1$ 时得到 $(O(\sqrt{T}), O(T^{3/4}))$;当 $V=T^{-1/6}$ 时得 $(O(T^{2/3}), O(T^{2/3}))$,无需 Slater 条件。在 $V=T^{-1/2}$ 的预算导向端点处,结果为 $(O(T), O(\sqrt{T}))$。相同更新规则还带来 $O((1+E[P_T])\sqrt{T}/V)$ 期望动态后悔,无需常见可行性或路径长度输入,其预算界依赖于最短可行路径(至多维度因子)。

原文摘要 · Abstract (English)

We study constrained online convex optimization with adversarial constraints when constraint values and gradients are observed through unbiased noise. Gaussian value noise of standard deviation $\sigma$ yields a worst-case lower bound of $\Omega(\min\{\sigma,1\}T/\log^7T)$ on the maximum of expected regret and expected hard violation, even with known gradients. This rules out any jointly $O(T^{1-\delta})$ guarantee for fixed $\delta>0$ and fixed positive noise level. We therefore study budget violation: the largest cumulative overspend over any window within a fixed horizon. We introduce \LEDGER, which tracks observed net consumption in a nonnegative balance and sets constraint weights before the current feedback noise. Under common feasibility and conditional finite-variance feedback, for fixed problem parameters, \LEDGER\ achieves $O(\sqrt T/V)$ expected regret and $O(\sqrt V\,T^{3/4}+\sigma\sqrt T)$ expected budget violation for $V\in[T^{-1/2},1]$. This gives the pair $(O(\sqrt T),O(T^{3/4}))$ at $V=1$ and $(O(T^{2/3}),O(T^{2/3}))$ at $V=T^{-1/6}$, without a Slater condition. The budget-focused endpoint $V=T^{-1/2}$ gives $(O(T),O(\sqrt T))$. The same update yields $O((1+E[P_T])\sqrt T/V)$ expected dynamic regret for predictable feasible comparator paths, without common feasibility or path-length input. Its budget bound instead depends on the shortest feasible path, up to a dimension factor.

在线学习约束优化噪声鲁棒预算控制

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