arXiv:2501.16919cs.LG2025-01被引 8

提出无需投影的在线优化算法,同时控制成本和约束违反。

Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints

  • 用线性优化替代投影,每轮仅调用一次线性优化器。
  • 实现 regret 与累积约束违反均为 $\tilde{O}(T^{3/4})$。
  • 适用于带对抗约束的在线组合优化,尤其适合离散动作场景。

我们研究了带有随时间变化的对抗性约束的在线凸优化(OCO)框架。每轮中,学习者从凸决策集 $X$ 中选择动作,随后揭示凸代价函数和凸约束函数。目标是设计一种计算高效的策略,在长度为 $T$ 的时域内同时实现低遗憾值与低累积约束违反(CCV)。标准 OCO 算法的主要瓶颈在于对决策集 $X$ 的投影操作。然而,对于许多结构化决策集,线性优化可高效执行。为此,我们提出一种基于在线条件梯度(OCG)的无投影算法,每轮仅需一次对 $X$ 的线性优化查询。该方法改进了现有最优无投影在线学习性能,实现了 $\tilde{O}(T^{3/4})$ 的遗憾值与 CCV。其核心思路是构造代价与约束函数的非负线性组合作为代理代价,并输入本文提出的自适应在线条件梯度子程序。我们还将框架拓展至带反馈设置,证明需引入新型代理损失以正确处理带反馈信息——此问题在先前工作中被忽略。最后,我们设计了一种基于跟随扰动领导者(FTPL)的高效算法,特别适用于具有离散动作的在线组合优化问题,同样达到 $O(T^{3/4})$ 的遗憾值与 CCV。

原文摘要 · Abstract (English)

We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this setting, at each round, the learner selects an action from a convex decision set $X$, after which both a convex cost function and a convex constraint function are revealed. The objective is to design a computationally efficient learning policy that simultaneously achieves low regret with respect to the cost functions and low cumulative constraint violation (CCV) over a horizon of length $T$. A major computational bottleneck in standard OCO algorithms is the projection operation onto the decision set $X$. However, for many structured decision sets, linear optimization can be performed efficiently. Motivated by this, we propose a projection-free online conditional gradient (OCG)-based algorithm that requires only a single call to a linear optimization oracle over $X$ per round. Our approach improves upon the state of the art for projection-free online learning with adversarial constraints, achieving $\tilde{O}(T^{\frac{3}{4}})$ bounds for both regret and CCV. Our algorithm is conceptually simple. It constructs a surrogate cost function as a nonnegative linear combination of the cost and constraint functions, and feeds these surrogate costs into a novel adaptive online conditional gradient subroutine introduced in this paper. We further extend our framework to the bandit setting, where we show that a new form of surrogate loss is necessary to properly handle bandit feedback - an issue overlooked in prior work. Finally, we develop an efficient Follow-the-Perturbed-Leader (FTPL)-based algorithm, particularly well-suited for online combinatorial optimization problems with discrete actions, which also achieves $O(T^{\frac{3}{4}})$ regret and CCV.

在线优化无投影对抗约束条件梯度

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