# Penalised FTRL With Time-Varying Constraints

Douglas J. Leith1 George Iosifidis2
1Trinity College Dublin  Ireland 2TU Delft  The Netherlands

###### Abstract

In this paper we extend the classical Follow-The-Regularized-Leader (FTRL)
algorithm to encompass time-varying constraints, through adaptive
penalization. We establish sufficient conditions for the proposed Penalized
FTRL algorithm to achieve $O(\sqrt{t})$ regret and violation with respect to
strong benchmark $\hat{X}^{max}_{t}$. Lacking prior knowledge of the
constraints, this is probably the largest benchmark set that we can reasonably
hope for. Our sufficient conditions are necessary in the sense that when they
are violated there exist examples where $O(\sqrt{t})$ regret and violation is
not achieved. Compared to the best existing primal-dual algorithms, Penalized
FTRL substantially extends the class of problems for which $O(\sqrt{t})$
regret and violation performance is achievable.

###### Keywords:

FTRL online convex optimisation constrained optimisation

##  1 Introduction

The introduction of online convex optimization (OCO) [14] offered an effective
way to tackle online learning and dynamic decision problems, with applications
that range from portfolio selection, to routing optimization and ad placement,
see [2]. One of the seminal OCO algorithms is the Follow-The-Regularized-
Leader (FTRL), which includes online gradient descent and mixture of experts
as special cases. Indeed, FTRL is widely used today and has been studied in
different contexts, e.g., with linear or non-linear objective functions,
composite objectives, budget constraints, etc., see [7].

The general form of the FTRL update is:

$\displaystyle x_{\tau+1}\in\arg\min_{x\in
X}\left\\{R_{\tau}(x)+\sum_{i=1}^{\tau}F_{i}(x)\right\\}$ (1)

where action set $X\subset\mathbb{R}^{n}$ is bounded, function
$F_{i}:X\rightarrow\mathbb{R}$ and regularizer
$R_{\tau}:X\rightarrow\mathbb{R}$ is strongly convex. When the sum-loss
$\sum_{i=1}^{\tau}F_{i}(x)$ is convex and $F_{i}(x)$ and
$\big{(}R_{i}(x)-R_{i-1}(x)\big{)}$ are uniformly Lipschitz, the FTRL-
generated sequence $\\{x_{\tau}\\}_{\tau=1}^{t}$ induces regret
$\sum_{i=1}^{t}\big{(}F_{i}(x_{i})-F_{i}(x)\big{)}\leq O(\sqrt{t})$, $\forall
x\\!\in\\!X$, cf. [7]. Importantly, the set $X$ of admissible actions must be
fixed and this is intrinsic to the method of proof, i.e., it is not a minor or
incidental assumption.

The focus of this paper is to extend the FTRL algorithm in order to
accommodate time-varying action sets, i.e., cases where at each time $\tau$
the fixed set action $X$ is replaced by set $X_{\tau}$ which may vary over
time. We refer to this extension to FTRL as _Penalised FTRL_.

In general, it is too much to expect to be able to simultaneously achieve
$O(\sqrt{t})$ regret and strict feasibility $x_{\tau}\in X_{\tau}$,
$\tau=1,\dots,t$. We therefore allow limited violation of the action sets
$\\{X_{\tau}\\}$ and instead aim to simultaneously achieve $O(\sqrt{t})$
regret and $O(\sqrt{t})$ constraint violation. That is, defining loss function
$f_{\tau}:D\rightarrow\mathbb{R}$ on domain $D\subset\mathbb{R}^{n}$ and
constraint functions $g_{\tau}^{(j)}:D\rightarrow\mathbb{R}$ such that
$X_{\tau}=\big{\\{}x\in D:g_{\tau}^{(j)}(x)\leq 0,j=1,\dots,m\big{\\}}$ then
we aim to simultaneously achieve regret and violation:

$\mathcal{R}_{t}=\sum_{i=1}^{t}\Big{(}f_{i}(x_{i})-f_{i}(x)\Big{)}\leq
O(\sqrt{t}),\
\mathcal{V}_{t}=\sum_{j=1}^{m}\max\\{0,\sum_{i=1}^{t}g_{i}^{(j)}(x_{i})\\}\leq
O(\sqrt{t})$

for all $x\in X^{max}_{t}:=\big{\\{}x\in D:\sum_{i=1}^{t}g_{i}^{(j)}(x)\leq
0,j=1,\dots,m\big{\\}}$.

_Importance of Using A Strong Benchmark._ We know from [6] that $O(\sqrt{t})$
regret and violation with respect to benchmark set $X^{max}_{t}$ is not
achievable for all possible sequences of constraints $\\{g_{i}^{(j)}\\}$. It
is therefore necessary to: _(i)_ change the benchmark set $X^{max}_{t}$ to
something more restrictive; or _(ii)_ restrict the admissible set of
constraint sequences $\\{g_{i}^{(j)}\\}$; or _(iii)_ both. In the literature,
it is common to adopt the weaker benchmark:

$X^{min}_{t}:=\left\\{x\in D:g_{i}^{(j)}(x)\leq
0,i=1,\dots,t,j=1,\dots,m\right\\}\subset X^{max}_{t}$

i.e., to focus on actions $x$ which _simultaneously satisfy every constraint
at every time_. But this weak benchmark is in fact so restrictive and easy for
a learning algorithm to outperform, where the achieved regret
$\mathcal{R}_{t}$ is often negative in practice, and indeed
$-\mathcal{R}_{t}\leq O(t)$.

One of our primary interests, therefore, is in retaining a benchmark that is
close to $X^{max}_{t}$. To this end, we consider the following benchmark:

$\hat{X}^{max}_{t}:=\bigg{\\{}x\in D:\sum_{i=1}^{\tau}g_{i}^{(j)}(x)\leq
0,\forall j\leq m,\tau\leq t\bigg{\\}}.$

Figure 1: Showing how our benchmark set $\hat{X}^{max}_{t}$ compares to
$X^{min}_{t}$.

We can see immediately that $X^{min}_{t}\subset\hat{X}^{max}_{t}$. The set
$\hat{X}^{max}_{t}$ requires $\sum_{i=1}^{\tau}g_{i}^{(j)}(x)\leq 0$ to hold
at every time $\tau\leq t$ rather than just at the end of the horizon $t$, and
so is still smaller than $X^{max}_{t}$. Lacking, however, predictions or prior
knowledge of the constraints $g_{i}^{(j)}$, it is probably the best we can
reasonably hope for. To illustrate the difference between $\hat{X}^{max}_{t}$
and $X^{min}_{t}$, suppose the time-varying constraint is $x\leq 1/\sqrt{t}$.
Then $X^{min}_{t}=[0,1/\sqrt{t}]$ which tends to set $\\{0\\}$ for $t$ large,
$X^{max}_{t}=D=[0,1]$ for $t\geq 1$, and $\hat{X}^{max}_{t}=D=[0,1]$.

##  2 Related Work

The literature on online learning with time-varying constraints focuses on the
use of primal-dual algorithms (see update (7) in the sequel), and largely
fails to obtain $O(\sqrt{t})$ regret and violation simultaneously even w.r.t.
the weak $X^{min}_{t}$ benchmark. The standard problem setup consists of a
sequence of convex cost functions $f_{t}:D\rightarrow\mathbb{R}$ and
constraints $g_{t}^{(j)}:X\rightarrow\mathbb{R}$, $j=1,\dots,m$, where actions
$x\in D\subset\mathbb{R}^{n}$. The canonical algorithm performs a primal-dual
gradient descent iteration, namely:

$\displaystyle\\!\\!\\!x_{t+1}\\!=\\!\Pi_{D}\left(x_{t}-\eta_{t}(\partial
f_{t}(x_{t})\\!+\lambda_{t}^{T}\partial g_{t}(x_{t}))\right),\
\lambda_{t+1}\\!=\\!\Big{[}(1\\!-\theta_{t})\lambda_{t}\\!+\\!\mu_{t}g_{t}(x_{t+1})\Big{]}^{+}$
(2)

with step-size parameters $\eta_{t}$, $\mu_{t}$ and regularisation parameter
$\theta_{t}$; while $\Pi_{D}(\alpha)$ denotes the project of $\alpha$ onto
$D$. Commonly, the parameter $\theta_{t}\equiv 0$, with exceptions being [5],
[3], and [9] that employ non-zero $\theta_{t}$. [13] approximate
$g_{t}(x_{t+1})$ in the $\lambda_{t+1}$ update by $g_{t}(x_{t})+\partial
g_{t}(x_{t})(x_{t+1}-x_{t})$.

The $\mathcal{R}_{t}$ is commonly measured w.r.t. the baseline action set
$X^{min}_{t}=\\{x\in D:g_{i}^{(j)}(x)\leq 0,i=1,\dots,t,j=1,\dots,m\\}$, with
the exception of [10] where a slightly larger set is considered; [13] that
considers stochastic constraints and the baseline action set is $\\{x\in
D:E[g_{i}^{(j)}(x)]\leq 0,j=1,\dots,m\\}$; and [4] which considers a $K$-slot
moving window for the sum-constraint satisfaction.

The original work on this topic restricted attention to time-invariant
constraints $g_{i}^{(j)}(x)\\!=\\!g^{(j)}(x)$. With this restriction, the work
in [3] achieves $\mathcal{R}_{t}\\!\leq\\!O(\max\\{t^{\beta},t^{1-\beta}\\})$
and $\mathcal{V}_{t}\\!\leq\\!O(t^{1-\beta/2})$ constraint violation, which
yields $\mathcal{R}_{t}$, $\mathcal{V}_{t}\\!\leq\\!O(t^{2/3})$ with
$\beta\\!=\\!2/3$. Similar bounds are derived in [5]. It is worth noting that
these results are primarily of interest for their analysis of the primal-dual
algorithm rather than the performance bounds per se, since classical
algorithms such as FTRL are already known to achieve $O(\sqrt{t})$ regret and
no constraint violation for constant constraints. For general time-varying
cost and constraint functions, [9] achieve $O(\sqrt{t})$ regret and
$O(t^{3/4})$ constraint violation; [4] achieve
$\mathcal{R}_{t}=O(t^{1/2}+KT/V)$ and $\mathcal{V}_{t}=O((Vt)^{1/2})$, with
$K=1$ corresponding to baseline set $X^{min}_{t}$ and $V$ a design parameter.
Selecting $V=t^{1/2}$ gives $O(t^{1/2})$ regret and $O(t^{3/4})$ constraint
violation, similarly to [9]. By restricting the constraints, [10] improves
this to $O(t^{1/2})$ regret and constraint violation. As already noted, this
requires restricting the constraints to be $g_{i}^{(j)}(x)=g^{(j)}(x)-b_{i,j}$
with $b_{i,j}\in\mathbb{R}$ i.e. the constraints are $g^{(j)}(x)\leq
b_{i}^{(j)}$ with time-variation confined to threshold $b_{i}^{(j)}$. Yu et al
[13] also achieve $O(t^{1/2})$ regret and expected constraint violation (i.e.
$E[\sum_{i=1}^{t}g_{i}^{(j)}(x_{t})]\leq O(t^{1/2})$), this time by
restricting the constraints to be i.i.d. stochastic. Yi et al [12] obtain
$O(t^{2/3})$ regret and constraint violation by restricting the cost and
constraint functions to be separable. Chen et al [1] focus on a form of
dynamic regret that upper bounds the static regret and show $o(t)$ regret and
$O(t^{2/3})$ constraint violation under a slow variation condition on the
constraints and dynamic baseline action.

##  3 Preliminaries

###  3.1 Exact Penalties

We begin by recalling a classical result of Zangwill [11]. Consider the convex
optimisation problem $P$:

$\min_{x\in D}f(x)\qquad\text{s.t.}\qquad g^{(j)}(x)\leq 0,\ j=1,\cdots,m$

where $D\subset\mathbb{R}^{n}$, $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
$g^{(j)}:\mathbb{R}^{n}\rightarrow\mathbb{R}$, $j=1,\cdots,m$ are convex. Let
$X:=\\{x:x\in D,g^{(j)}(x)\leq 0,j=1,\cdots,m\\}$ denote the feasible set and
$X^{*}\subset X$ the set of optimal points. Define:

$\displaystyle
F(x):=f(x)+\gamma\sum_{j=1}^{m}\max\left\\{0,g^{(j)}(x)\right\\},\quad\gamma\in\mathbb{R}.$
(3)

$F(x)$ is convex since $f(\cdot)$, $g^{(j)}(\cdot)$ are convex and
$\max\\{\cdot\\}$ preserves convexity.

Figure 2: Illustrating use of a penalty to convert constrained optimization
$\min_{x:g(x)\\!\leq\\!0}f(x)$ into unconstrained optimization
$\min_{x}f(x)\\!+\gamma\max\\{0,g(x)\\}$, $\gamma\\!>\\!0$. Within the
feasible set $g(x)\leq 0$ and $\gamma\max\\{0,g(x)\\}\\!=\\!0$. Outwith this
set $\gamma\max\\{0,g(x)\\}=\gamma g(x)\\!>\\!0$. The idea is that $\gamma$ is
selected large enough that outwith the feasible set
$f(x)\\!+\\!\gamma\max\\{0,g(x)\\}>f^{*}$, the min value of $f$ inside the
feasible set.

The key idea is that the penalty (second term in (3)) is zero for $x\in X$,
but large when $x\notin X$. Provided $\gamma$ is selected large enough, the
penalty forces the minimum of $F(x)$ to _(i)_ lie in $X$ and _(ii)_ match
$\min_{x\in X}f(x)$; see example in Fig. 2. The next lemma, proved in the
Appendix, corresponds to [11, Lemma 2].

######  Lemma 1 (Exact Penalty)

Assume that a Slater point exists i.e. a feasible point $z\in D$ such that
$g^{(j)}(z)<0$, $j=1,\cdots,m$. Let $f^{*}:=\inf_{x\in X}f(x)$ (the solution
to optimization $P$) . Then there exists a finite threshold $\gamma_{0}\geq 0$
such that $F(x)\geq f^{*}$ for all $x\in D$, $\gamma\geq\gamma_{0}$, with
equality only when $x\in X^{*}$. It is sufficient to choose
${\gamma}_{0}=\frac{f^{*}-f(z)-1}{\max_{j\in\\{1,\cdots,m\\}}\\{g^{(j)}(z)\\}}$.

###  3.2 FTRL Results

We also recall the following standard FTRL results (for proofs see, e.g.,
[8]).

######  Lemma 2 (Be-The-Leader)

Let $F_{i},i=1,\dots,t$ be a sequence of (possibly non-convex) functions
$F_{i}:D\rightarrow\mathbb{R}$, $D\subset\mathbb{R}^{n}$. Assume that
$\arg\min_{x\in D}\sum_{i=1}^{\tau}F_{i}(x)$ is not empty for
$\tau=1,\dots,t$. Selecting sequence $w_{i+1},i=1,\dots,t$ according to the
Follow The Leader (FTL) update $w_{\tau+1}\in\arg\min_{x\in
D}\sum_{i=1}^{\tau}F_{i}(x)$, ensures
$\sum_{i=1}^{t}F_{i}(w_{i+1})\leq\sum_{i=1}^{t}F_{i}(y)$ for every $y\in D$.

######  Condition 1 (FTRL)

(i) Domain $D$ is bounded (potentially non-convex), (ii)
$\sum_{i=1}^{\tau}F_{i}(x)$ is convex (the individual $F_{i}$’s need not be
convex), (iii) $F_{i}(x)$ is uniformly $L_{f}$-Lipschitz on $D$ i.e.
$|F_{i}(x)-F_{i}(y)|\leq L_{f}\|x-y\|$ for all $x,y\in D$ and where $L_{f}$
does not depend on $i$, and (iv) $R_{\tau}(x)$ is $\sqrt{\tau}$-strongly
convex and $\big{(}R_{i}(x)-R_{i-1}(x)\big{)}$ is uniformly Lipschitz, e.g.
$\sqrt{\tau}\|x\|_{2}^{2}$.

######  Lemma 3 (Regret of FTRL)

When Condition 1 holds, the sequence $\\{x_{\tau}\\}_{\tau=1}^{t}$ generated
by the FTRL update $x_{\tau+1}\in\arg\min_{x\in
D}R_{\tau}(x)+\sum_{i=1}^{\tau}F_{i}(x)$ has regret
$\mathcal{R}_{t}=\sum_{i=1}^{t}F_{i}(x_{i})-F_{i}(x)\leq O(\sqrt{t})$ for all
$x\in D$.

######  Lemma 4 ($\sigma_{\tau}$-Strongly Convex Regulariser)

When $\sum_{i=1}^{\tau}F_{i}(x)$ is $\sigma_{\tau}$-strongly convex,
$F_{i}(x)$ uniformly $L_{f}$-Lipschitz over $D$ and
$w_{\tau+1}\in\arg\min_{x\in D}\sum_{i=1}^{\tau}F_{i}(x)$, it holds
$\|w_{\tau+1}-w_{\tau}\|\leq 2L_{f}/(\sigma_{\tau}+\sigma_{\tau-1})$

##  4 Penalised FTRL

###  4.1 Exact Penalties For Time-Invariant Constraints

We begin by demonstrating the application of Lemma 1 to FTRL update (1) with
time-invariant action set $X$. Selecting $F_{i}(x)=f_{i}(x)+\gamma h(x)$ with
$h(x)=\sum_{j=1}^{m}\max\\{0,g^{(j)}(x)\\}$ and defining the bounded domain
$D$ with $X\subset D$, then by standard analysis, cf. [7], the penalized FTRL
update111Note the subtle yet crucial difference w.r.t. non-penalized FTRL
update (1).:

$\displaystyle x_{\tau+1}\in\arg\min_{x\in
D}\left\\{R_{\tau}(x)+\sum_{i=1}^{\tau}F_{i}(x)\right\\}$ (4)

ensures regret $\sum_{i=1}^{t}(F_{i}(x_{i})-F_{i}(x))\leq O(\sqrt{t})$ for all
$x\in D$, and since $X\subset D$ for all $x\in X$. Of course this says nothing
about whether the actions $x_{i}$ lie in set $X$ nor anything much about the
regret of $f_{i}(x_{i})$, but when set $X$ has a Slater point and $\gamma$ is
selected large enough then by Lemma 1 we have that $x_{\tau+1}\in X$ for all
$\tau$. It follows that $F_{i}(x_{i})=f_{i}(x_{i})$ (since $h(x_{i})=0$ when
$x_{i}\in X$) and so regret
$\sum_{i=1}^{t}(F_{i}(x_{i})-F_{i}(x))=\sum_{i=1}^{t}(f_{i}(x_{i})-f_{i}(x))\leq
O(\sqrt{t})$ for all $x\in X$.

###  4.2 Penalties For Time-Varying Constraints

We now extend consideration to FTRL with time-varying constraints. Our aim is
to define a penalty which is zero on a set $\hat{X}_{\tau}^{max}\approx
X_{max}$, and large enough outside this set to force the minimum of
$\sum_{i=1}^{\tau}F_{i}(x)$ to lie in $\hat{X}^{max}$.

####  4.2.1 Penalties Which Are Zero When $x\in\hat{X}^{max}_{\tau}$.

Consider extending the penalty-based FTRL (4) to time-varying constraints. We
might try selecting:

$F_{i}(x)=f_{i}(x)+\gamma h_{i}(x),\quad\text{with}\quad
h_{i}(x)=\sum_{j=1}^{m}\max\left\\{0,g_{i}^{(j)}(x)\right\\},$

but we immediately run into the following difficulty. We have that
$\sum_{i=1}^{\tau}F_{i}(x)=\sum_{i=1}^{\tau}f_{i}(x)+\gamma\sum_{i=1}^{\tau}\sum_{j=1}^{m}\max\\{0,g_{i}^{(j)}(x)\\}$
and so to make the second term zero requires $g_{i}^{(j)}(x)\leq 0$ for all
$i\leq\tau$ and $j\leq m$, i.e. requires every constraint over all time to
simultaneously be satisfied. This penalty choice $h_{i}(\cdot)$ therefore
corresponds to benchmark $X^{min}_{t}$, whereas our interest is in set
$X^{max}_{t}$. It is perhaps worth noting that this corresponds to the penalty
used in the primal-dual literature, so it is unsurprising that those results
are confined to $X^{min}$.

With this in mind, consider instead selecting

$h_{\tau}(x)=\sum_{j=1}^{m}\max\left\\{0,\sum_{i=1}^{\tau}g_{i}^{(j)}(x)\right\\}-\sum_{j=1}^{m}\max\left\\{0,\sum_{i=1}^{\tau-1}g_{i}^{(j)}(x)\right\\}$

with $h_{1}(x)=\sum_{j=1}^{m}\max\\{0,g_{i}^{(j)}(x)\\}$. Then,

$\sum_{i=1}^{\tau}F_{i}(x)=\sum_{i=1}^{\tau}f_{i}(x)+\gamma\sum_{j=1}^{m}\max\left\\{0,\sum_{i=1}^{\tau}g_{i}^{(j)}(x)\right\\}.$

We now have a sum-constraint in the second term, as desired. Unfortunately,
this choice of $h_{i}(\cdot)$ violates the conditions needed for FTRL to
achieve $O(\sqrt{t})$ regret. Namely, it is required that $F_{i}(\cdot)$ is
uniformly Lipschitz but $h_{i}(\cdot)$ does not satisfy this condition, and so
neither does $F_{i}(\cdot)$. To see this, observe that when
$g_{i}^{(j)}(\cdot)$ is uniformly Lipschitz with constant $L_{g}$, then
$\sum_{i=1}^{\tau}g_{i}^{(j)}(x)$ has a Lipschitz constant $\tau L_{g}$ that
scales with $\tau$, and so there exists no uniform upper bound. The $\max$
operator in $h_{i}(\cdot)$ does not change the Lipschitz constant (see Lemma
5); thus $h_{i}(\cdot)$ is $\tau L_{g}$ Lipschitz, which prevents FTRL
achieving $\mathcal{R}_{t}\leq O(\sqrt{t})$.

These considerations lead us to the following penalty,

$\displaystyle
h_{\tau}(x)=\sum_{j=1}^{m}\max\left\\{0,\frac{1}{\tau}\sum_{i=1}^{\tau}g_{i}^{(j)}(x)\right\\}.$
(5)

When $g_{i}^{(j)}(\cdot)$ is uniformly Lipschitz with constant $L_{g}$ then so
is $h_{i}(\cdot)$ due to the $1/\tau$ prefactor added to the sum and the
following Lemma which just states that when a function $h(x)$ is $L$-Lipschitz
then $\max\\{0,h(x)\\}$ is also $L$-Lipschitz:

###### Lemma 5

When $|h(x)-h(y)|\leq L\|x-y\|$ then $|\max\\{0,h(x)\\}-\max\\{0,h(y)\\}|\leq
L\|x-y\|$.

###### Proof

Observe that $2\max\\{0,h(x)\\}=h(x)+|h(x)|$. Therefore,
$2|\max\\{0,h(x)\\}-\max\\{0,h(y)\\}|=|h(x)-h(y)+|h(x)|-|h(y)||\leq|h(x)-h(y)|+||h(x)|-|h(y)||\leq|h(x)-h(y)|+|h(x)-h(y)|\leq
2L\|x-y\|$.

With this choice, we can write:

$\displaystyle\sum_{i=1}^{\tau}F_{i}(x)$
$\displaystyle=\sum_{i=1}^{\tau}f_{i}(x)+\gamma\sum_{j=1}^{m}\sum_{i=1}^{\tau}\max\left\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\right\\}.$

The second term is zero when

$\displaystyle x_{\tau}$ $\displaystyle\in\hat{X}^{max}_{\tau}:=\Big{\\{}x\in
D:\sum_{i=1}^{\tau}h_{i}(x)\leq
0\Big{\\}}=\Big{\\{}x:\sum_{k=1}^{i}g_{k}^{(j)}(x)\leq 0,j\leq
m,i\leq\tau\Big{\\}}$

####  4.2.2 Penalties Which Are Large When $x\notin\hat{X}^{max}_{\tau}$

In addition to requiring the penalty for time-varying constraints to be zero
for $x\in\hat{X}^{max}_{\tau}$ we also require the penalty to large enough
when $x\notin\hat{X}^{max}_{\tau}$ so as to force the minimum of
$\sum_{i=1}^{\tau}F_{i}(x)$ to lie in set $\hat{X}^{max}_{\tau}$, or at least
to only result in $O(\sqrt{\tau})$ violation.

As already noted, to use FTRL we need $F_{i}(\cdot)$ to be uniformly
Lipschitz, which requires $f_{i}(\cdot)$ to be uniformly Lipschitz. When
$f_{i}(\cdot)$ is $L_{f}$-Lipschitz then $|\sum_{i=1}^{\tau}f_{i}(x)|$ may
grow linearly with $\tau$ at rate $\tau L_{f}$. We therefore require the
penalty $\sum_{i=1}^{\tau}h_{i}(x)$ to also grow at least linearly with $\tau$
since otherwise for all $\tau$ large enough
$|\sum_{i=1}^{\tau}f_{i}(x)|\gg\sum_{i=1}^{\tau}h_{i}(x)$ and the penalty may
become ineffective i.e. we can have $x_{\tau}\notin\hat{X}_{\tau}$ for all
$\tau$ large enough and so end up with $O(t)$ constraint violation, which is
no good.

We formalize the requirement the sum-penalty $\sum_{i=1}^{\tau}h_{i}(x)$ in
(5) needs to grow quickly enough as follows. Let
$\partial\hat{X}^{max}_{\tau}$ denote the boundary of $\hat{X}^{max}_{\tau}$.
Let:

$k_{\tau}:=\min_{x\in\partial\hat{X}^{max}_{\tau}}|\\{(i,j):\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\geq
0,i\in\\{1,\dots,\tau\\},j=\\{1,\dots,m\\}\\}|.$

That is, $k_{\tau}$ is the minimum number of constraints active at the
boundary of $\hat{X}^{max}_{\tau}$. Observe that $1\leq k_{\tau}\leq\tau$
with, for example, $k_{\tau}=\tau$ when $g_{i}^{(j)}(x)=g^{(j)}(x)$ does not
depend on $i$.

######  Condition 2 (Penalty Growth)

Let $z\in D$ be a common Slater point such that
$\frac{1}{\tau}\sum_{i=1}^{\tau}g_{i}^{(j)}(z)<-\eta<0$ for $j=1,\dots,m$ and
$\tau>t_{\epsilon}$ (the same $z$ must work for all $\tau$ and $j$). We
require that $k_{\tau}\geq\frac{\beta}{\eta}\tau$ for all $\tau>t_{\epsilon}$,
where $\beta>0$ and the same $\beta$ must work for all $\tau=1,\dots,t$.

####  4.2.3 Time-Varying Exact Penalties

We are now in a position to extend the penalty approach to time-varying
constraints. We begin by applying Lemma 1 to optimisation problem
$P^{\prime}$: $\min_{x\in D}f(x)\ s.t.\
\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\leq 0,\ i=1,\cdots,t,\ j=1,\cdots,m$
where $f(\cdot)$ and $g_{i}^{(j)}(\cdot)$, $i=1,\dots,t$, $j=1,\cdots,m$ are
convex and $D\subset\mathbb{R}^{n}$ is convex and bounded. Let
$C^{*}=\arg\min_{x\in\hat{X}^{max}_{t}}f(x)$. Define

$\displaystyle
H(x):=f(x)+\gamma\sum_{i=1}^{t}\sum_{j=1}^{m}\max\left\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\right\\}$

where $\gamma\in\mathbb{R}$. Note that $H(\cdot)$ is convex since $f(\cdot)$,
$g_{i}^{(j)}(\cdot)$ are convex and composition with $\max$ preserves
convexity.

###### Lemma 6

Assume a Slater point exists, i.e. a $z\\!\in\\!D$ such that
$\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(z)\\!<\\!-\eta<0$, $i=1,\dots,t$,
$j=1,\dots,m$. Let $f^{*}:=\min_{x\in\hat{X}^{max}_{t}}f(x)$. Then there
exists a finite threshold $\gamma_{0}\geq 0$ such that $H(x)\geq f^{*}$ for
all $x\in D$, $\gamma\geq\gamma_{0}$, with equality only when
$x\in\hat{X}^{max}_{t}$. It is sufficient to choose
$\gamma_{0}\geq\frac{f^{*}-f(z)-1}{-k_{t}\eta}$.

###### Proof

Setting the expression for $\gamma_{0}$ to one side for now, the result
follows from applying Lemma 1 to $P^{\prime}$. Turning now to expression
$\gamma_{0}\\!\geq\\!\frac{f^{*}-f(z)-1}{k_{t}\eta}$, comparing this with the
expression in Lemma 1, observe that the only change is in the denominator,
which applying Lemma 1 to $P^{\prime}$ is $\max_{i\leq t,j\leq
m}\\{\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(z)\\}\\!=\\!-\eta$. Referring to (8)
in the proof of Lemma 1, it is sufficient the denominator $G$ of $\gamma_{0}$
is such that $\frac{\sum_{(i,j)\in
A}\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(z)}{G}\geq 1$, where
$A\subset\\{1,\dots,t\\}\times\\{1,\dots,m\\}$. By assumption
$g_{k}^{(j)}(z)\\!\leq\\!-\eta$ and so $\sum_{j\in
A}\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(z)\\!\leq\\!-|A|\eta$ with
$|A|\\!\geq\\!1$. Now $k_{t}\\!\in[1,|A|]$, thus suffices to see setting
$G=-k_{t}\eta$ also meets this requirement.

######  Theorem 4.1 (Time-Varying Exact Penalty)

The sequence $x_{\tau}$, $\tau=1,\dots,t$ generated by the FTRL update (4)
with $F_{i}(x)=f_{i}(x)+\gamma h_{i}(x)$ and
$h_{i}(x):=\sum_{j=1}^{m}\max\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\\}$
satisfies $x_{\tau+1}\in\hat{X}^{max}_{\tau}$ for $\tau>t_{\epsilon}$ when
Condition 2 holds and parameter $\gamma>\frac{E+L+1}{\beta}$ where
$E\geq\max_{y\in D,i\in\\{1,\dots,t\\}}(R_{i}(y)-R_{i}(z))/i,\ L\geq\max_{y\in
D,i\in\\{1,\dots,t\\}}f_{i}(y)-f_{i}(z)$ with $z\in D$ a Slater point.

###### Proof

The result follows by application of Lemma 6 at times $\tau>t_{\epsilon}$ with
$h(x)=R_{\tau}(x)+\sum_{i=1}^{\tau}f_{i}(x)$. We have that
$h(x)-h(z)=R_{\tau}(x)-R_{\tau}(z)+\sum_{i=1}^{\tau}(f_{i}(x)-f_{i}(z))\leq
E\tau+L\tau$. Hence for $x_{\tau+1}\in\hat{X}^{max}_{\tau}$ it is sufficient
to choose:

$\gamma>\gamma_{0}=\frac{(E+L)\tau-1}{k_{\tau}\eta}\leq\frac{E+L+1/\tau}{\beta}\leq\frac{E+L+1}{\beta}.$

When Condition 2 holds, $\beta>0$.

Theorem 4.1 states a lower bound on $\gamma$ in terms of constants $E$, $L$
and $\beta$. For a quadratic regulariser
$R_{\tau}(x)=\sqrt{\tau}\|x\|_{2}^{2}$ we can choose $E=\max_{y,z\in
D}(\|y\|_{2}^{2}-\|z\|_{2}^{2})$. Since functions $f_{i}$ are uniformly
Lipschitz then $|f_{i}(z)-f_{i}(y)|\leq L_{f}\|z-y\|\leq L_{f}\|D\|$ and so we
can choose $L=L_{f}\|D\|$. A value for $\beta$ may be unknown but to apply
Theorem 4.1 in practice we just need to select $\gamma$ large enough, so a
pragmatic approach is simply to make $\gamma$ grow with time and then freeze
it when it is large enough i.e. when the constraint violations are observed to
cease.

###  4.3 Main Result: Penalised FTRL $O(\sqrt{t})$ Regret & Violation

Our main result extends the standard FTRL analysis to time-varying
constraints:

######  Theorem 4.2 (Penalised FTRL)

Assume Conditions 1 and 2 hold for $F_{i}(x)=f_{i}(x)+\gamma h_{i}(x)$ with
$h_{i}(x)=\sum_{j=1}^{m}\max\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\\}$,
and the constraints $g_{i}^{(j)}$ are uniformly Lipschitz. Let the sequence of
actions $\\{x_{\tau}\\}_{\tau=1}^{t}$ be generated by the Penalised FTRL
update:

$\displaystyle x_{\tau+1}\in\arg\min_{x\in
D}R_{\tau}(x)+\sum_{i=1}^{\tau}F_{i}(x)$ (6)

Then, if $\gamma$ is sufficiently large, the regret and constraint violation
satisfy:

$\displaystyle\mathcal{R}_{t}:=\sum_{i=1}^{t}f_{i}(x_{i})-f_{i}(y)\leq
O(\sqrt{t}),\qquad\mathcal{V}_{t}:=\sum_{i=1}^{t}h_{i}(x_{i})\leq
O(\sqrt{t}),\quad\forall y\in\hat{X}^{max}_{t}$
$\displaystyle\hat{X}^{max}_{t}\\!\\!=\\!\Big{\\{}x\in
D:\sum_{k=1}^{i}g_{k}^{(j)}(x)\\!\leq\\!0,\forall i\leq t,j\leq
m\Big{\\}}\\!\\!=\\!\Big{\\{}x\in D:\sum_{k=1}^{i}h_{k}(x)\\!=\\!0,\forall
i\leq t\Big{\\}}$

###### Proof

Regret: Applying Lemma 3 then $\sum_{i=1}^{t}F_{i}(x_{i})-F_{i}(y)\leq
O(\sqrt{t})$ for all $y\in D$. This holds in particular for all
$y\in\hat{X}^{max}_{t}$ and for these points
$\sum_{i=1}^{t}F_{i}(y)=\sum_{i=1}^{t}f_{i}(y)$. Therefore,
$\sum_{i=1}^{t}F_{i}(x_{i})-f_{i}(y)\leq O(\sqrt{t})$ i.e.
$\mathcal{R}_{t}=\sum_{i=1}^{t}f_{i}(x_{i})-f_{i}(y)\leq\
O(\sqrt{t})-\gamma\sum_{i=1}^{t}h_{i}(x_{i})\leq O(\sqrt{t})$ since
$h_{i}(x_{i})\geq 0$.

Constraint Violation: By Theorem 4.1, $x_{\tau+1}\in\hat{X}^{max}_{\tau}$ for
$\tau>t_{\epsilon}$. Our interest is in bounding the violation of
$\hat{X}^{max}_{\tau+1}$ by $x_{\tau+1}$. We can ignore the finite interval
from 1 to $t_{\epsilon}$ since it will incur at most a finite constraint
violation and so not affect an $O(\sqrt{t})$ bound i.e. when obtaining the
$O(\sqrt{t})$ bound we can take $t_{\epsilon}=0$. We follow a “Be-The-Leader”
type of approach and apply Lemma 2 with ${F}_{i}(x)=h_{i}(x)$. We have that
$h_{i}(x)\geq 0$ and by Condition 2, there exists a Slater point $z\in D$ such
that $h_{i}(z)=0$, $i=1,\dots,t$. Hence, $\min_{x\in
D}\sum_{i=1}^{\tau}{F}_{i}(x)\\!=\\!0$ and $\arg\min_{x\in
D}\sum_{i=1}^{\tau}{F}_{i}(x)$ is not empty. Now,
$x_{\tau+1}\in\hat{X}^{max}_{\tau}\\!=\\!\big{\\{}x\in
D:\sum_{i=1}^{\tau}h_{i}(x)=0\big{\\}}=\arg\min_{x\in
D}\sum_{i=1}^{\tau}{h}_{i}(x)$ i.e. $x_{\tau+1}$ is a Follow-The-Leader update
with respect to $\sum_{i=1}^{\tau}{h}_{i}(x)$. Hence, by Lemma 2, it is
$\sum_{i=1}^{t}h_{i}(y)\\!\geq\\!\sum_{i=1}^{t}h_{i}(x_{i+1})$, $\forall
y\\!\in\\!D$. Multiplying both sides of this inequality by -1 and adding
$\sum_{i=1}^{t}h_{i}(x_{i})$, it follows that:

$\sum_{i=1}^{t}\Big{(}h_{i}(x_{i})-h_{i}(y)\Big{)}\leq\sum_{i=1}^{t}\Big{(}h_{i}(x_{i})-h_{i}(x_{i+1})\Big{)}\,\,\,\forall
y\in D.$

In particular, for $y\in\hat{X}^{max}_{t}$ then $\sum_{i=1}^{t}h_{i}(y)=0$ and
so

$\mathcal{V}_{t}=\sum_{i=1}^{t}h_{i}(x_{i})\leq\sum_{i=1}^{t}\Big{(}h_{i}(x_{i})-h_{i}(x_{i+1})\Big{)}.$

Since $g_{i}^{(j)}$ is uniformly Lipschitz then by Lemma 5, we get that
$h_{i}$ is uniformly Lipschitz, i.e. $|h_{i}(x_{i})-h_{i}(x_{i+1})|\leq
L_{g}\|x_{i}-x_{i+1}\|$ and $\mathcal{V}_{t}\leq
L_{g}\sum_{i=1}^{t}\|x_{i}-x_{i+1}\|$, where $L_{g}$ is the Lipschitz
constant. Since the regularizer $R_{\tau}(x)$ in the Penalized FTRL update is
$\sqrt{\tau}$-strongly convex, by Lemma 4 we get that $\|x_{i}-x_{i+1}\|$ is
$O(1/\sqrt{i})$ and so $\sum_{i=1}^{t}\|x_{i}-x_{i+1}\|$ is $O(\sqrt{t})$.
Hence, $\mathcal{V}_{t}\leq O(\sqrt{t})$ as claimed.

We can immediately generalize Theorem 4.2 by observing that a sequence of
constraints $\\{g_{i}^{(j)}\\}$ which are active at no more than $O(\sqrt{t})$
time steps can be violated while still maintaining $O(\sqrt{t})$ overall sum-
violation.

######  Corollary 1 (Relaxation)

Define the sets

$P_{-}=\\{j:\sum_{i=1}^{t}\max\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\\}\leq
O(\sqrt{t})\\},\,\,\,\text{and}\,\,\,\,P_{+}=\\{1,\dots,m\\}\setminus P_{-}.$

In Theorem 4.2 relax Condition 2 so that it only holds for the subset $P_{+}$
of constraints. Then the Penalised FTRL update still ensures $O(\sqrt{t})$
regret and constraint violation with respect to:

$\hat{X}^{max}_{t}=\Big{\\{}x\in D:\sum_{k=1}^{i}g_{k}^{(j)}(x)\leq
0,i=1,\dots,t,j\in P_{+}\Big{\\}}.$

In effect, Corollary 1 says that we only need Condition 2 to hold for a
_subset_ of the constraints (i.e. subset $P_{+}$). The effect will be to
increase the sum-violation, but only by $O(\sqrt{t})$. This is the key
advantage of the penalty-based approach, namely it allows a soft trade-off
between sum-constraint satisfaction/violation, Condition 2 and benchmark set
$\hat{X}^{max}_{t}$. Importantly, note that the Penalised FTRL update itself
remains unchanged and does not require knowledge of the partitioning of
constraints into sets $P_{+}$ and $P_{-}$.

With this in mind, it is worth noting that we also have the flexibility to
partition the constraints in other ways. For example:

###### Corollary 2

Consider the setup in Theorem 4.2 but using penalty

$h_{i}(x)=\sum_{j=1}^{m}\max\left\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{k}^{(j)}(x)\right\\}+\delta_{i}^{(j)}(x)$

Then the Penalised FTRL update ensures regret and violation

$\displaystyle\mathcal{R}_{t}:=\sum_{i=1}^{t}\Big{(}f_{i}(x_{i})-f_{i}(y)\Big{)}\leq
O(\sqrt{t})-\sum_{i=1}^{t}\sum_{j=1}^{m}\Big{(}\delta_{i}^{(j)}(x_{i})-\delta_{i}^{(j)}(y)\Big{)}$
$\displaystyle\mathcal{V}_{t}:=\sum_{i=1}^{t}h_{i}(x_{i})\leq
O(\sqrt{t})+\sum_{i=1}^{t}\sum_{j=1}^{m}\delta_{i}^{(j)}(x)$

for all $y\in\hat{X}^{max}_{t}=\Big{\\{}x\in
D:\sum_{k=1}^{i}g_{k}^{(j)}(x)\leq 0,i=1,\dots,t,j=1,\dots,m\Big{\\}}$.

When $\delta_{i}^{(j)}\\!\leq\\!O(1/\sqrt{t})$ then Corollary 2 shows that the
Penalised FTRL update achieves $O(\sqrt{t})$ regret and violtion, this
Corollary will prove useful in the next section. Other variations of this sort
are also possible.

###  4.4 Necessity of Penalty Growth Condition

Condition 2 is necessary for Theorems 4.1 and 4.2 to hold in the sense that
when the condition is violated then there exist examples where these theorems
fail.

Returning again to the example from the Introduction, selecting $h_{i}(x)$
according to (5) then
$h_{i}(x)=\max\\{0,-0.01\\}+\max\\{0,\frac{n_{2,i}}{i}x\\}=\max\\{0,\frac{n_{2,i}}{i}x\\}$.
Hence, the penalty
$\sum_{i=1}^{\tau}h_{i}(x)\leq\sum_{i=1}^{\tau}\frac{n_{2,i}}{i}x$. When
$n_{2,i}<O(i)$ then $\sum_{i=1}^{\tau}h_{i}(x)<O(\tau)$ (since
$\sum_{i=1}^{\tau}\frac{1}{i^{c}}\leq\int_{0}^{\tau}\frac{1}{i^{c}}di=\frac{\tau^{1-c}}{1-c}$
for $0\leq c\leq 1$) and Condition 2 is violated (since $k_{\tau}\leq
n_{2,\tau}<O(\tau)$ and so there does not exist any $\beta>0$ such that
$k_{\tau}\geq\frac{\beta}{\eta}\tau$). For $\tau$ large enough the penalty
$\sum_{i=1}^{\tau}h_{i}(x)$ therefore inevitably becomes small relative to
$\sum_{i=1}^{\tau}f_{i}(x)=-2\tau x$, which leads to persistent violation of
constraint $x\leq 0$ i.e. Theorem 4.1 fails. This is what we see in Figure
3(a).

When $n_{2,i}\leq O(\sqrt{i})$ then $\frac{n_{2,i}}{i}\leq O(1/\sqrt{i})$ and
the constraint sum-violation $\sum_{i=1}^{\tau}h_{i}(x)\leq O(\sqrt{i})$.
Hence, Corollary 1 still works even though Theorem 4.1 fails. However, when
$n_{2,i}$ greater than $O(\sqrt{i})$ but less than $O(i)$ then the constraint
violation is greater than $O(\sqrt{i})$ and so Corollary 1 also fails.

It is worth noting that while we might consider gaining penalty growth by
scaling $\gamma$ with $t$ this in inadmissible because Condition 1 requires
$F_{t}(x)=f_{t}(x)+\gamma h_{t}(x)$ to be uniformly Lipschitz i.e. for the
same Lipschitz constant to apply at all times $t$.

###  4.5 Constraints Satisfying Penalty Growth Condition

A natural question to ask is which classes of time-varying constraints satisfy
Condition 2. In this section we present some useful examples. In particular,
we consider the classes of constraints considered by [10] and [13], since
these are the only previous works for time-varying constraints that report
$\mathcal{R}_{t},\mathcal{V}_{t}=O(\sqrt{t})$.

####  4.5.1 Perturbed Constraints

In [10] the considered constraints are of the form:

$g_{i}^{(j)}(x)=g^{(j)}(x)+b_{i}^{(j)}$

with common Slater point and $b_{i}^{(j)}$ upper bounded by some value, i.e.,
$b_{i}^{(j)}\\!\leq\\!\bar{b}^{(j)},\forall i$. For this class of constraints
we have that:

$\displaystyle h_{i}(x)$
$\displaystyle=\sum_{j=1}^{m}\max\left\\{0,\frac{1}{i}\sum_{k=1}^{i}(g^{(j)}(x)+b_{k}^{(j)})\right\\}=\sum_{j=1}^{m}\max\left\\{0,g^{(j)}(x)+\frac{1}{i}\sum_{k=1}^{i}b_{k}^{(j)}\right\\}$

Defining $\underline{b}^{(j)}_{t}=\frac{1}{t}\sum_{k=1}^{t}b_{k}^{(j)}$ and
$\Delta_{i}^{(j)}(x)=\frac{1}{i}\sum_{k=1}^{i}(b_{k}^{(j)}-\underline{b}_{t})$,
then we can rewrite the penalty equivalently as

$h_{i}(x)=\sum_{j=1}^{m}\max\left\\{0,g^{(j)}(x)+\underline{b}_{t}^{(j)}\right\\}+\delta_{i}^{(j)}(x)$

with
$\delta_{i}^{(j)}(x)=\max\big{\\{}0,g^{(j)}(x)+\underline{b}_{t}^{(j)}+\Delta_{i}^{(j)}(x)\big{\\}}-\max\big{\\{}0,g^{(j)}(x)+\underline{b}_{t}^{(j)}\big{\\}}$.
When $|\Delta_{i}^{(j)}(x)|$ is $O(1/\sqrt{i})$ then, by Lemma 5, so is
$|\delta_{i}^{(j)}(x)|$. Hence, when $|\Delta_{i}^{(j)}(x)|$ is
$O(1/\sqrt{i})$ then we can use the fact that Condition 2 holds for
constraints $g^{(j)}(x)+\underline{b}^{(j)}_{t}\leq 0$ to show, by Corollary
2, that the Penalised FTRL update achieves $O(\sqrt{t})$ regret and violation
with respect to benchmark set
$\hat{X}_{t}^{max}=\\{x:g^{(j)}(x)+\underline{b}^{(j)}_{t}\leq 0\\}$. This
corresponds to one extreme of [10]’s benchmark but Theorem 1 provides more
general conditions under which it is applicable, while [10] only considers
constraints that are either time-invariant or i.i.d.

Alternatively, defining
$\Delta_{i}^{(j)}(x)=\frac{1}{i}\sum_{k=1}^{i}(b_{k}^{(j)}-\bar{b}^{(j)})$ and
we can rewrite the penalty equivalently as

$h_{i}(x)=\sum_{j=1}^{m}\max\left\\{0,g^{(j)}(x)+\bar{b}^{(j)}\right\\}+\delta_{i}^{(j)}(x)$

with
$\delta_{i}^{(j)}(x)=\max\\{0,g^{(j)}(x)+\bar{b}^{(j)}+\Delta_{i}^{(j)}(x)\\}-\max\\{0,g^{(j)}(x)+\bar{b}^{(j)}\\}$.
Observe that $\delta_{i}^{(j)}(x)\leq 0$ since $\Delta_{i}^{(j)}(x)\leq 0$.
Hence, $\delta_{i}^{(j)}(x)$ does not add to the upper bound on the sum-
constraint violation and so, by Corollary 2, that the Penalised FTRL update
achieves $O(\sqrt{t})$ regret and violation with respect to benchmark set
$\hat{X}_{t}^{max}=\\{x:g^{(j)}(x)+\bar{b}^{(j)}\leq 0\\}$. This corresponds
to the other extreme of [10]’s benchmark, and in fact corresponds to the weak
benchmark $X_{t}^{min}$ and so is perhaps less interesting.

####  4.5.2 Families Of Constraints

Suppose the time-varying constraint functions $g_{i}^{(j)}$ are selected from
some family. That is, let $A^{(j)}=\\{a_{1}^{(j)},\dots,a_{n_{j}}^{(j)}\\}$ be
a family of functions indexed by $k=1,\dots,n_{j}$ with
$a_{k}^{(j)}:D\rightarrow\mathbb{R}$ being $L_{g}$-Lipschitz and
$|a_{k}^{(j)}(x)|\leq a_{max}$ for all $x\in D$. At time $i$, constraint
$g_{i}^{(j)}=a_{k}^{(j)}$ for some $k\in\\{1,\dots,n_{j}\\}$, i.e. at each
time step the constraint $g_{i}^{(j)}$ is selected from family $A^{(j)}$. Let
$n_{k,\tau}^{(j)}$ denote the number of times that function $a_{k}^{(j)}$is
visited up to time $\tau$ and $p_{k,\tau}^{(j)}=n_{k,\tau}^{(j)}/\tau$ the
fraction of times that $a_{k}^{(j)}$ is visited. With this setup the penalty
is:

$\displaystyle h_{i}(x)$
$\displaystyle=\sum_{j=1}^{m}\max\left\\{0,\frac{1}{i}\sum_{k=1}^{i}g_{i}^{(j)}\right\\}=\sum_{j=1}^{m}\max\left\\{0,\sum_{k=1}^{n_{j}}p_{k,i}^{(j)}a_{k}^{(j)}(x)\right\\}$

We proceed by rewriting the penalty equivalently as

$h_{i}(x)=\sum_{j=1}^{m}\max\left\\{0,\sum_{k=1}^{n_{j}}p_{k}^{(j)}a_{k}^{(j)}(x)\right\\}+\delta_{i}^{(j)}(x)$

with
$\delta_{i}^{(j)}(x)=\max\big{\\{}0,\sum_{k=1}^{n_{j}}p_{k,i}^{(j)}a_{k}^{(j)}(x)\big{\\}}-\max\big{\\{}0,\sum_{k=1}^{n_{j}}p_{k}^{(j)}a_{k}^{(j)}(x)\big{\\}}$
By Lemma 5,
$|\delta_{i}^{(j)}(x)|\leq|\sum_{k=1}^{n_{j}}(p_{k,i}^{(j)}-p_{k}^{(j)})a_{k}^{(j)}(x)|$.
Assume the following condition holds:

######  Condition 3 ($1/\sqrt{t}$-Convergence)

For $\epsilon>0$ there exists $t_{0}>0$ and $0\leq p_{k}^{(j)}\leq 1$,
$\sum_{j=1}^{m}\sum_{k=1}^{n_{j}}p_{k}^{(j)}=1$ such that
$|p_{k,\tau}^{(j)}-p_{k}^{(j)}|\leq\epsilon/\sqrt{\tau}$ for all $\tau>t_{0}$.

Then for all $\tau>t_{0}$, $|\delta_{i}^{(j)}(x)|\leq
n_{j}\frac{\epsilon}{\sqrt{\tau}}a_{max}\leq\bar{n}\frac{\epsilon}{\sqrt{\tau}}a_{max}$
with $\bar{n}:=\max_{j}n_{j}$. By Corollary 2 it now follows that Penalised
FTRL achieves $O(\sqrt{t})$ regret and violation with respect to benchmark
$\hat{X}^{max}_{t}=\big{\\{}x:\sum_{k=1}^{n_{j}}p_{k}^{(j)}a_{k}^{(j)}(x)\leq
0\big{\\}}$. Observe that in this case $\hat{X}^{max}_{t}={X}^{max}_{\infty}$,
i.e., we obtain $O(\sqrt{t})$ regret and violation with respect to the strong
benchmark, which is very appealing. Note that we don’t need to know the
relative frequencies in advance for this analysis to work.

####  4.5.3 Example

Suppose $D\\!=\\![-10,10]$, loss function $f_{\tau}(x)\\!=\\!-2x$ and
constraint $g_{\tau}(x)$ alternates between $a_{1}(x)\\!=\\!-0.01$ and
$a_{2}(x)\\!=\\!x$, equaling $a_{2}(x)$ at time $\tau$ with
probability222Recall that $c\sum_{\tau=0}^{t}\frac{1}{\tau^{1-c}}\approx
c\int_{0}^{t}\frac{1}{\tau^{1-c}}d\tau=t^{c}$ for $0\leq c\leq 1$. Hence, with
this choice $E[n_{2,t}]\approx 0.1t^{c}$ and $E[p_{2,t}]\approx 0.1t^{c-1}$.
$0.1c/\tau^{1-c}$. Figure 3(a) shows the performance vs $c$ of the Penalised
FTRL update with quadratic regulariser $R_{\tau}(x)=\sqrt{\tau}x^{2}$ and
$F_{\tau}(x)=f_{\tau}(x)+\gamma\max\\{0,p_{1,\tau}a_{1}(x)+p_{2,\tau}a_{2}(x)\\}$
with parameter $\gamma=25$. It can be seen that for $c=1$ and $c=0.5$ the
constraint violation is well-behaved, staying close to zero, but for
$c\\!\in\\!(0.5,1)$ the constraint violation grows with time.

What is happening here is that when $c\\!=\\!1$ then $p_{1,\tau}\rightarrow
0.9$, $p_{2,\tau}\rightarrow 0.1$ and the penalty term
$\gamma\max\\{0,p_{1,\tau}a_{1}(x)+p_{2,\tau}a_{2}(x)\\}$ in $F_{\tau}(x)$
ensures the violation
$\sum_{i=1}^{t}g_{i}(x)=t(p_{1,t}a_{1}(x)+p_{2,t}a_{2}(x))$ stays small. When
$c=0.5$, then $p_{1,\tau}\rightarrow 1$, $p_{2,\tau}\rightarrow 0$ and the
penalty term ensures $tp_{1,t}a_{1}(x)$ stays small while $tp_{2,t}a_{2}(x)$
is $O(\sqrt{t})$, thus $\sum_{i=1}^{t}g_{i}(x)$ is $O(\sqrt{t})$. When
$c\\!\in(0.5,1)$ then again $p_{1,\tau}\rightarrow 1$, $p_{2,\tau}\rightarrow
0$ and the penalty term ensures $tp_{1,t}a_{1}(x)$ stays small but now
$tp_{2,t}a_{2}(x)$ is larger than $O(\sqrt{t})$ and so
$\sum_{i=1}^{t}g_{i}(x)$ is also larger than $O(\sqrt{t})$.

We claim that $1/\sqrt{t}$-convergence is sufficient for Penalised FTRL to
achieve $O(\sqrt{t})$ regret and violation with respect to $X^{*}$, but it
remains an open question whether or not it is also a necessary condition.
Nevertheless, in simulations we observe that when $1/\sqrt{t}$-convergence
does not hold then performance is often poor and that this is not specific to
the FTRL algorithm, e.g. Figure 3(b) illustrates the performance of the
canonical online primal-dual update (e.g. see [10]),

$\displaystyle x_{t+1}$ $\displaystyle=\Pi_{D}\left(x_{t}-\alpha_{t}(\partial
f_{t}(x_{t})+\lambda_{t}\partial g_{t}(x_{t}))\right),\
\lambda_{t+1}=\Big{[}\lambda_{t}+\alpha_{t}g_{t}(x_{t+1}\Big{]}^{+}$ (7)

where $\Pi_{D}$ denotes projection onto set $D$ and step size
$\alpha_{t}=5/\sqrt{t}$.

(a) Penalised FTRL (b) Primal-Dual

Figure 3: Example about the role of $1/\sqrt{t}$-convergence in achieving
$\mathcal{V}_{t}=O(\sqrt{t})$.

####  4.5.4 I.i.d Stochastic Constraints

In [13] i.i.d. constraint functions drawn from a family are considered and a
primal-dual algorithm is presented that achieves $O(\sqrt{t})$ regret and
expected violation. Since with high probability the empirical mean converges
at rate $1/\sqrt{t}$ with high probability we can immediately apply the
foregoing analysis to the sample paths to show that Penalised FTRL achieves
$O(\sqrt{t})$ regret and violation with respect to ${X}^{max}_{t}$ with high
probability. In more detail, let indicator random variiable $I^{j}_{k,i}=1$
when constraint function $a_{k}^{(j)}$ is selected at time $i$, and otherwise
$I^{(j)}_{k,i}=0$. By the law of large numbers (we can use any convenient
concentration inequality, e.g. Chebyshev), with high probabilty the emprical
mean satisfies $|\frac{1}{\tau}\sum_{i=1}^{\tau}I^{(j)}_{k,i}-p^{j}_{k}]|\leq
1/\sqrt{\tau}$ with high probability. That is, Condition 3 holds with high
probability and we are done.

####  4.5.5 Periodic Constraints

Let indicator $I^{j}_{k,i}=1$ when constraint function $a_{k}^{(j)}$ is
selected at time $i$, and otherwise $I^{(j)}_{k,i}=0$. When the constraints
are visitied in a periodic fashion then

$I^{(j)}_{k,i}=\begin{cases}1&i=nT_{k}^{(j)},n=1,2,\dots\\\
0&\text{otherwise}\end{cases}$

where $T_{k}^{(j)}$ is the period of constraint $a_{k}^{(j)}$. Then
$|\frac{1}{\tau}\sum_{i=1}^{\tau}I^{(j)}_{k,i}-\frac{1}{T_{k}^{(j)}}|=\frac{1}{\tau}|\lfloor\frac{\tau}{T_{k}^{(j)}}\rfloor-\frac{\tau}{T_{k}^{(j)}}|\leq\frac{1}{\tau}$.
Hence Condition 3 holds and we are done.

##  5 Summary and Conclusions

In this paper we extend the classical FTRL algorithm to encompass time-varying
constraints by leveraging, for the first time in this context, the seminal
penalty method of [11]. We establish sufficient conditions for this new
Penalised FTRL algorithm to achieve $O(\sqrt{t})$ regret and violation with
respect to a strong benchmark $\hat{X}^{max}_{t}$ that expands significantly
the previously-employed benchmarks in the literature. This result matches the
performance of the best existing primal-dual algorithms in terms of regret and
constraint violation growth rates , while substantially extending the class of
problems covered. The key to this improvement lies in how the time-varying
constraints are incorporated into the FTRL algorithm. We conjecture that
adopting a similar formulation with a primal-dual algorithm, namely using:

$\displaystyle x_{t+1}$ $\displaystyle=\Pi_{D}(x_{t}-\alpha_{t}(\partial
f_{t}(x_{t})+\lambda_{t}\partial h_{t}(x_{t}))),\
\lambda_{t+1}=[\lambda_{t}+\alpha_{t}h_{t}(x_{t+1}]^{+}$

where $h_{t}(x)=\frac{1}{t}\sum_{i=1}^{t}g_{i}(x_{t+1}$, would allow similar
performance to be achieved by primal-dual algorithms as by FTRL but we leave
this to future work.

## References

  * [1] Chen, T., Ling, Q., Giannakis, G.B.: An online convex optimization approach to proactive network resource allocation. IEEE Transactions on Signal Processing 65(24), 6350–6364 (2017)
  * [2] Hazan, E.: Introduction to online convex optimization. Foundations and Trends in Optimization 2, 157–325 (2016)
  * [3] Jenatton, R., Huang, J.C., Archambeau, C.: Adaptive algorithms for online convex optimization with long- term constraints. In: Proc. of ICML. pp. 402–411 (2016)
  * [4] Liakopoulos, N., Destounis, A., Paschos, G., Spyropoulos, T., Mertikopoulos, P.: Cautious regret minimization: Online optimization with long-term budget constraints. In: Proceedings of ICML. pp. 3944–3952 (2019)
  * [5] Mahdavi, M., Jin, R., Yang, T.: Trading regret for efficiency: Online convex optimization with long term constraints. Journal of Machine Learning Research 13(81), 2503–2528 (2012)
  * [6] Mannor, S., Tsitsiklis, J.N., Yu, J.Y.: Online learning with sample path constraints. Journal of Machine Learning Research 10(20), 569–590 (2009)
  * [7] McMahan, H.B.: A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research 18, 1–50 (2017)
  * [8] Shalev-Shwartz, S.: Online learning and online convex optimization. Foundations and Trends in Optimization 4, 107–194 (2011)
  * [9] Sun, W., Dey, D., Kapoor, A.: Safety-aware algorithms for adversarial contextual bandit. In: Proc. of ICML. pp. 3280–3288 (2017)
  * [10] Valls, V., Iosifidis, G., Leith, D., Tassiulas, L.: Online convex optimization with perturbed constraints: Optimal rates against stronger benchmarks. In: Proceedings of AISTATS. pp. 2885–2895 (2020)
  * [11] W.J.Zangwill: Nonlinear Programming via Penalty Functions. Management Science 13(5), 344–358 (1967)
  * [12] Yi, X., Li, X., Xie, L., Johansson, K.H.: Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Transactions on Signal Processing 68, 731–746 (2020)
  * [13] Yu, H., Nelly, M., Wei, X.: Online convex optimization with stochastic constraints. In: Proceedings of NIPS (2017)
  * [14] Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: Proc. of ICML (2003)

## Appendix A: Proofs

###  5.1 Proof of Lemma 1

###### Proof

Firstly note that for feasible points $x\in X$ we have that $g^{(j)}(x)\leq
0$, $j=1,\cdots,m$ and so $F(x)=f(x)$. By definition $f(x)\geq
f^{*}=\inf_{x\in X}f(x)$ and so the stated result holds trivially for such
points. Now consider an infeasible point $w\notin X$. Let $z$ be an interior
point satisfying $g^{(j)}(z)<0$, $j=1,\cdots,m$; by assumption such a point
exists. Let ${\gamma}_{0}=\frac{f^{*}-f(z)-1}{G}$. It is sufficient to show
that $F(w)>f^{*}$ for ${\gamma}\geq{\gamma}_{0}$ and
$G=\max_{j\in\\{1,\cdots,m\\}}\\{g^{(j)}(z)\\}$.

Let $v=\beta z+(1-\beta)w$ be a point on the chord between points $w$ and $z$,
with $\beta\in(0,1)$ and $v$ on the boundary of $X$ (that is $g^{(j)}(v)\leq
0$ for all $j=1,\cdots,m$ and $g^{(j)}(v)=0$ for at least one
$j\in\\{1,\cdots,m\\}$). Such a point $v$ exists since $z$ lies in the
interior of $X$ and $w\notin X$. Let
$A:=\\{j:j\in\\{1,\cdots,m\\},g^{(j)}(v)=0\\}$ and
$t(x):=f(x)+{\gamma}\sum_{j\in A}g^{(j)}(x)$. Then $t(v)=f(v)\geq f^{*}$.
Also, by the convexity of $g^{(j)}(\cdot)$ we have that for $j\in A$ that
$g^{(j)}(v)=0\leq\beta g^{(j)}(z)+(1-\beta)g^{(j)}(w)$. Since $g^{(j)}(z)<0$,
it follows that $g^{(j)}(w)>0$. Hence, $\sum_{j\in A}g^{(j)}(w)=\sum_{j\in
A}\max\\{0,g^{(j)}(w)\\}\leq\sum_{j=1}^{m}\max\\{0,g^{(j)}(w)\\}$ and so
$t(w)\leq F(w,{\gamma})$. Now, observe that $t(z)=f(z)+{\gamma}\sum_{j\in
A}g^{(j)}(z)\leq f(z)+{\gamma}_{0}\sum_{j\in A}g^{(j)}(z)$ since
$g^{(j)}(z)<0$ and ${\gamma}\geq{\gamma}_{0}$. Hence,

$\displaystyle t(z)$ $\displaystyle\leq f(z)+(f^{*}-f(z)-1)\frac{\sum_{j\in
A}g^{(j)}(z)}{G}$ (8)

Selecting $G$ such that $\frac{\sum_{j\in A}g^{(j)}(z)}{G}\geq 1$ then
$t(z)\leq f^{*}-1\leq t(v)-1$. So we have established that $f^{*}\leq t(v)$,
$t(z)\leq t(v)-1$ and $t(w)\leq F(w)$. Finally, by the convexity of
$t(\cdot)$, $t(v)\leq\beta t(z)+(1-\beta)t(w)$. Since $t(z)\leq t(v)-1$ it
follows that $t(v)\leq\beta(t(v)-1)+(1-\beta)t(w)$ i.e.
$t(v)\leq-\frac{\beta}{1-\beta}+t(w)$. Therefore
$f^{*}\leq-\frac{\beta}{1-\beta}+F(w)<F(w)$ as claimed.