We study a generalization of the classic Online Convex Optimization (OCO)
framework by considering additional long-term adversarial constraints.
Specifically, after an online policy decides its action on a round, in addition
to a convex cost function, the adversary also reveals a set of $k$ convex
constraints. The cost and the constraint functions could change arbitrarily
with time, and no information about the future functions is assumed to be
available. In this paper, we propose a meta-policy that simultaneously achieves
a sublinear cumulative constraint violation and a sublinear regret. This is
achieved via a black box reduction of the constrained problem to the standard
OCO problem for a recursively constructed sequence of surrogate cost functions.
We show that optimal performance bounds can be achieved by solving the
surrogate problem using any adaptive OCO policy enjoying a standard
data-dependent regret bound. A new Lyapunov-based proof technique is presented
that reveals a connection between regret and certain sequential inequalities
through a novel decomposition result. We conclude the paper by highlighting
applications to online multi-task learning and network control problems.

我们研究了经典的在线凸优化（OCO）框架的一种推广，通过考虑额外的长期对抗性约束。我们提出了一种元策略，能够同时达到亚线性的累积约束违规和亚线性的遗憾，通过将约束问题转化为递归构建的一系列代理代价函数的标准 OCO 问题的黑盒减缩。我们展示了通过使用任何享有标准数据相关遗憾上界的自适应 OCO 策略求解代理问题，可以达到最优性能界限。通过一种新的基于李雅普诺夫的证明技术，我们揭示了遗憾和某些顺序不等式之间的联系，通过一种新颖的分解结果。最后，我们强调了在在线多任务学习和网络控制问题中的应用。

黑暗中的游戏：带有对抗性约束的无悔学习

Playing in the Dark: No-regret Learning with Adversarial Constraints

In many applications, learning systems are required to process continuous
non-stationary data streams. We study this problem in an online learning
framework and propose an algorithm that can deal with adversarial time-varying
and nonlinear constraints. As we show in our work, the algorithm called
Constraint Violation Velocity Projection (CVV-Pro) achieves $\sqrt{T}$ regret
and converges to the feasible set at a rate of $1/\sqrt{T}$, despite the fact
that the feasible set is slowly time-varying and a priori unknown to the
learner. CVV-Pro only relies on local sparse linear approximations of the
feasible set and therefore avoids optimizing over the entire set at each
iteration, which is in sharp contrast to projected gradients or Frank-Wolfe
methods. We also empirically evaluate our algorithm on two-player games, where
the players are subjected to a shared constraint.

本研究提出了一种名为 CVV-Pro 的算法，通过利用局部稀疏线性逼近来处理不断变化的非线性约束条件的连续数据流，在面对共享限制的两人博弈时表现良好。

对抗性非线性约束下的在线学习

Online Learning under Adversarial Nonlinear Constraints

This paper considers distributed online convex optimization with adversarial
constraints. In this setting, a network of agents makes decisions at each
round, and then only a portion of the loss function and a coordinate block of
the constraint function are privately revealed to each agent. The loss and
constraint functions are convex and can vary arbitrarily across rounds. The
agents collaborate to minimize network regret and cumulative constraint
violation. A novel distributed online algorithm is proposed and it achieves an
$\mathcal{O}(T^{\max\{c,1-c\}})$ network regret bound and an
$\mathcal{O}(T^{1-c/2})$ network cumulative constraint violation bound, where
$T$ is the number of rounds and $c\in(0,1)$ is a user-defined trade-off
parameter. When Slater's condition holds (i.e, there is a point that strictly
satisfies the inequality constraints), the network cumulative constraint
violation bound is reduced to $\mathcal{O}(T^{1-c})$. Moreover, if the loss
functions are strongly convex, then the network regret bound is reduced to
$\mathcal{O}(\log(T))$, and the network cumulative constraint violation bound
is reduced to $\mathcal{O}(\sqrt{\log(T)T})$ and $\mathcal{O}(\log(T))$ without
and with Slater's condition, respectively. To the best of our knowledge, this
paper is the first to achieve reduced (network) cumulative constraint violation
bounds for (distributed) online convex optimization with adversarial
constraints under Slater's condition. Finally, the theoretical results are
verified through numerical simulations.

本文提出了一种新的分布式在线优化算法，旨在协同解决网络遗憾和累积约束违规等问题，可以适用于多个代理在有限的回合中进行最小化操作，具有一定的抗干扰能力和优化效果。

斯莱特条件下带对抗性约束的分布式在线凸优化：降低累积约束违反的限制界

Distributed Online Convex Optimization with Adversarial Constraints:  Reduced Cumulative Constraint Violation Bounds under Slater's Condition

Existing approaches to online convex optimization (OCO) make sequential
one-slot-ahead decisions, which lead to (possibly adversarial) losses that
drive subsequent decision iterates. Their performance is evaluated by the
so-called regret that measures the difference of losses between the online
solution and the best yet fixed overall solution in hindsight. The present
paper deals with online convex optimization involving adversarial loss
functions and adversarial constraints, where the constraints are revealed after
making decisions, and can be tolerable to instantaneous violations but must be
satisfied in the long term. Performance of an online algorithm in this setting
is assessed by: i) the difference of its losses relative to the best dynamic
solution with one-slot-ahead information of the loss function and the
constraint (that is here termed dynamic regret); and, ii) the accumulated
amount of constraint violations (that is here termed dynamic fit). In this
context, a modified online saddle-point (MOSP) scheme is developed, and proved
to simultaneously yield sub-linear dynamic regret and fit, provided that the
accumulated variations of per-slot minimizers and constraints are sub-linearly
growing with time. MOSP is also applied to the dynamic network resource
allocation task, and it is compared with the well-known stochastic dual
gradient method. Under various scenarios, numerical experiments demonstrate the
performance gain of MOSP relative to the state-of-the-art.

该论文探讨了在线凸优化涉及敌对损失函数和敌对约束的情况，开发了一种修改的在线鞍点（MOSP）方案，并在动态网络资源分配任务中进行了应用，证明了其相对于梯度方法的性能优势。