# Simultaneously Achieving Sublinear Regret and Constraint Violations for
Online Convex Optimization with Time-varying Constraints

Qingsong Liu<EMAIL_ADDRESS>Institute for Interdisciplinary
Information Sciences, Tsinghua UniversityChina ,  Wenfei Wu
<EMAIL_ADDRESS>School of Electronics Engineering and Computer Science,
Peking UniversityChina ,  Longbo Huang<EMAIL_ADDRESS>Institute
for Interdisciplinary Information Sciences, Tsinghua UniversityChina and
Zhixuan Fang  Institute for Interdisciplinary Information Sciences, Tsinghua
UniversityChina Shanghai Qi Zhi InstituteShanghaiChina
<EMAIL_ADDRESS>
(2021)

###### Abstract.

In this paper, we develop a novel virtual-queue-based online algorithm for
online convex optimization (OCO) problems with long-term and time-varying
constraints and conduct a performance analysis with respect to the dynamic
regret and constraint violations. We design a new update rule of dual
variables and a new way of incorporating time-varying constraint functions
into the dual variables. To the best of our knowledge, our algorithm is the
first parameter-free algorithm to simultaneously achieve sublinear dynamic
regret and constraint violations. Our proposed algorithm also outperforms the
state-of-the-art results in many aspects, e.g., our algorithm does not require
the Slater condition. Meanwhile, for a group of practical and widely-studied
constrained OCO problems in which the variation of consecutive constraints is
smooth enough across time, our algorithm achieves $O(1)$ constraint
violations. Furthermore, we extend our algorithm and analysis to the case when
the time horizon $T$ is unknown. Finally, numerical experiments are conducted
to validate the theoretical guarantees of our algorithm, and some applications
of our proposed framework will be outlined.

Constrained optimization, Online convex optimization, Online network resource
allocation, Online job scheduling.

††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/1122445.1122456††conference: Performance ’21: International Symposium
on Computer Performance, Modeling, Measurements and Evaluation; Nov 08–12,
2021; Italy††booktitle: Performance ’21, Nov 08–12, 2021, Italy††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Online Convex Optimization (OCO) with long-term constraints has become one of
the most popular online learning frameworks in recent years due to its
powerful modeling capability for various problems such as network routing (Yu
et al., 2017), online display advertising (Hazan, 2019), and resources
management (Chen et al., 2017). In the formulation of OCO with long-term
constraints, the agent wants to minimize the accumulated loss while satisfying
the constraints as much as possible in the long-term. And most existing works
considers the scenarios where the constraints are time-invariant (Yu and
Neely, 2020; Qiu and Wei, 2020).

However, _time-varying constraints_ arise in many practical applications in
which the underlying time-varying system is dynamic and uncertain, e.g., smart
grid with uncertain renewable energy supply (Zhang et al., 2016) and data
centers with dynamic user demands (Liu et al., 2014). Thus, this paper
considers recently proposed _OCO framework with long-term and time-varying
constraints_ (Cao and Liu, 2018; Chen and Giannakis, 2019; Yi et al., 2020),
which is more general and practical than the one with time-variant constraints
setting.

Reference | Regret(R) | Constraint violations(C) | Parameter-free |  Slater condition-free111[3] assumes a slightly stronger Slater condition. | Simultaneous
---|---|---|---|---|---
|  |  |  |  | sublinear R&C
(Chen et al., 2017) | $O(\max\\{{V}_{x}{T}^{a},$ |  |  |  |
| ${V}_{g}{T}^{a},{T}^{1-a}\\})$ | $O({T}^{1-a})$ | ✓ | ✕ | ✕
(Chen et al., 2018) | $O({T}^{\frac{7}{8}}{V}_{x})$ | $O(\max\\{{T}^{\frac{15}{16}},{T}^{\frac{7}{8}}{V}_{x}\\})$ | ✓ | ✓ | ✕
(Chen and Giannakis, 2019) | $O({V}_{x}{T}^{\frac{3}{4}})$ | $O({T}^{\frac{3}{4}})$ | ✓ | ✕ | ✕
(Chen and Giannakis, 2019) | $O({V}_{x}{T}^{\frac{1}{2}})$ | $O({T}^{\frac{1}{2}})$ | ✓ | ✕ | ✕
(Cao and Liu, 2018) | $O({V}_{x}^{\frac{1}{2}}{T}^{\frac{1}{2}})$ | $O({V}_{x}^{\frac{1}{4}}{T}^{\frac{3}{4}})$ | ✕ | ✕ | ✓
Thm.1 | $O(\max\\{\sqrt{T{V}_{x}},{V}_{g}\\})$ | $O(\max\\{\sqrt{T},{V}_{g}\\})$ | ✓ | ✓ | ✓
Thm.1 | $O(\sqrt{T{V}_{x}})$ | $O(\max\\{{T}^{\frac{3}{4}},{V}_{g}\\})$ | ✓ | ✓ | ✓

Table 1.  Comparison of performance bounds for OCO with long-term and time-
varying constraints w.r.t. dynamic benchmark.

###  1.1. Prior work

OCO with long-term and time-invariant constraints has been extensively studied
in the past few years. This branch of literature usually focuses on the
minimization of the static regret. (Mahdavi et al., 2012) first studied the
OCO with long-term and time-invariant constraints and developed an online
algorithm with sublinear static regret and accumulated constraint violations.
Later (Jenatton et al., 2016; Yuan and Lamperski, 2018) improved the
performance bounds in (Mahdavi et al., 2012). These bounds are further
improved in the recent work (Yu and Neely, 2020; Qiu and Wei, 2020), where a
state-of-the-art static regret and constraint violations upper bounds are
shown under the assumption of the Slater condition. However, the setting of
time-invariant constraints means the constraints will be learned by the agent
easily, and hence does not capture the scenarios in which the underlying
environment is dynamic and uncertain.

The Time-varying constraints. To overcome the limitations above, recent
advances in OCO with long-term constraints considered the time-varying
constraints and usually adopt a more practical but challenging metric, the
dynamic regret. In this setting, a crucial challenge is to achieve sublinear
dynamic regret and constraint violation simultaneously. (Cao and Liu, 2018)
studied OCO with long-term and time-varying constraints both in full-
information setting and bandit setting with two-point feedback. It is the
first work to simultaneously achieve sublinear dynamic regret and constraint
violations. But the performance bounds attained in (Cao and Liu, 2018) are
only valid when the order of the accumulated variations of the environment is
known to the agent in advance, i.e., parameter-dependent. For parameter-free
work, (Chen et al., 2017) analyzed the performance of a modified online
saddle-point (MOSP) method and showed that sublinear dynamic regret and
constraints violation may be achieved if the accumulated variations of the
environment are sublinear. Later (Chen et al., 2018) improves upon it in terms
of fewer assumptions but incurs a degradation of the performance. (Chen and
Giannakis, 2019) proposed a variant of MOSP method for bandit setting with
two-point feedback and established the state-of-the-art performance upper
bounds. However, all these parameter-free methods do not always guarantee the
sublinear regret and constraint violations simultaneously, even given the
accumulated variations of the environment is sublinear. Besides, most of them
assume the Slater condition holds while it is not true in many scenarios. We
list these works in Table 1.

Most related to our work is (Yu and Neely, 2020) and (Qiu and Wei, 2020),
which developed virtual-queue-based online algorithms and achieved the best
performance bounds on static regret for the time-invariant constraints setting
and the time-varying constraints setting, respectively. These results provide
an inspiring insights for OCO with long-term constraints. However, a
challenging question remains _if a virtual-queue-based algorithm can improve
the state-of-the-art performance on OCO with long-term and time-varying
constraints in terms of dynamic regret, and achieve sublinear regret and
constraint violations simultaneously under only common assumptions._ The
answer is yes and our main contributions are summarized in the following part.

###  1.2. Contributions

We summarize our main contributions as follows.

  * •

We develop and analyze a novel _parameter-free_ virtual-queue-based algorithm
for OCO with long-term and time-varying constraints. Specifically, We prove
that our algorithm achieves sublinear dynamic regret and constraint violations
_simultaneously_ without Slater condition. The dynamic regret and constraint
violations bounds of our developed algorithm outperform the state-of-the-art
in many aspects. See also Table 1 for details.

  * •

We show that when the variation of consecutive constraints is smooth enough
across time, which holds in many practical applications (Chen et al., 2017),
our algorithm can achieve $O(1)$ constraint violations.

  * •

To the best of our knowledge, we are the first to consider the unknown time
horizon case for OCO with long-term and time-varying constraints. Furthermore,
our algorithm with a doubling trick can still preserve the order of
performance bounds when the time horizon is unknown.

  * •

We outline some examples of applications, and fit them in the framework of OCO
with long-term and time-varying constraints.

##  2\. Problem setup

In this section, we first introduce the OCO problem with long term and time-
varying constraints. Then, we present the assumptions in our paper, which are
widely-adopted.

###  2.1. Formulation

In each round _t_ , the agent incurs a loss function ${f}_{t}$ and a
constraint requirement ${\bm{g}}_{t}$, i.e., the agent wants to make a
decision ${x}_{t}\in\chi$ to minimize the loss ${f}_{t}({x}_{t})$ while
satisfying ${\bm{g}}_{t}({x}_{t})\leq 0$, where ${\bm{g}}_{t}(x)$ is defined
as $[{g}_{t,1}(x),{g}_{t,2}(x),..,{g}_{t,K}(x){]}^{T}$. In this paper, we
assume that ${f}_{t}(x)$ and ${g}_{t,i}(x)$ are defined over a closed convex
set $\chi\subseteq{R}^{n}$. Denote ${\\{f}_{t}(x){\\}}_{t=1}^{\infty}$ and
${\\{\bm{g}}_{t}(x){\\}}_{t=1}^{\infty}$ as the sequence of the time-varying
loss functions and constraint functions , respectively. Thus, the agent’s goal
is to compute the ${x}_{t}^{*}$ defined as follows:

${x}_{t}^{*}=\arg\min_{x\in\chi}{\\{{f}_{t}(x)|{\bm{g}}_{t}(x)\leq\bm{0}\\}}.$

However, solving this problem is challenging in the online setting since the
information about the loss and constraint functions is unknown a priori to the
agent. In particular, since ${\bm{g}}_{t}$ is unknown a priori, the constraint
${\bm{g}}_{t}({x}_{t})\leq\bm{0}$ is hard to be satisfied in every time slot
$t$. Rather, previous work (Chen et al., 2017; Cao and Liu, 2018; Chen and
Giannakis, 2019) allows instantaneous constraints to be violated at each
round, but tries to satisfy the constraints in the long run. In other words,
the agent wants to ensure the long term constraint of
$\sum_{t=1}^{T}{{\bm{g}}_{t}({x}_{t})}\leq\bm{0}$ over some given period of
length $T$. This type of long-term constraint is appropriate in many
applications (e.g., smart grid with renewable energy supply (Cao and Liu,
2018) ). Thus, we aim to solve the following online optimization problem.

(P1)
$\begin{split}\min_{\\{{x}_{t}{\\}}_{t=1}^{T}}{\sum_{t=1}^{T}{{f}_{t}({x}_{t})}},\;s.t.\;\sum_{t=1}^{T}{{\bm{g}}_{t}({x}_{t})}\leq\bm{0}.\end{split}$

Solving problem (P1) exactly is still impossible in the online setting, since
the information about the ${f}_{t}$ and ${\bm{g}}_{t}$ is unknown before the
action ${x}_{t}$ is chosen. Instead, our goal is to make the total loss
$\sum_{t=1}^{T}{{f}_{t}({x}_{t})}$ as low as possible compared to the total
loss incurred by the benchmark sequence $\\{{x}_{t}^{*}{\\}}_{t=1}^{T}$
(${x}_{t}^{*}$ is commonly termed the per-slot minimizer since
${x}_{t}^{*}=\arg\min_{x\in\chi,{\bm{g}}_{t}(x)\leq 0}{{f}_{t}(x)}$) and
meanwhile, to ensure that $\sum_{t=1}^{T}{{\bm{g}}_{t}({x}_{t})}$ is not too
positive, i.e., the long-term constraint is not violated too much. Therefore,
for any sequence $\\{{x}_{t}{\\}}_{t=1}^{T}$ yielded by online algorithms, we
define the dynamic regret and the constraint violations, respectively as
follow,

(1)
$\begin{split}&Regret=\sum_{t=1}^{T}{{f}_{t}({x}_{t})}-\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}.\\\
&{Vio}_{k}=\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})},\;k\in\\{1,2,...,K\\}.\end{split}$

In this paper, we consider the dynamic regret and constraint violations as the
performance metrics. We emphasize that the definition of dynamic regret and
constraint violations in (LABEL:regret_constraint_violations) are prevalent
and widely adopted in the literature (Chen et al., 2017, 2018; Chen and
Giannakis, 2019; Cao and Liu, 2018). Our goal is to choose ${x}_{t}$ in each
round $t$ such that both the dynamic regret and constraint violations grow
sub-linearly with respect to the time horizon $T$. Note that the regret
defined in (LABEL:regret_constraint_violations) may be negative but this also
makes sense. This is because we aim to minimize the total cost defined in (P1)
as small as possible, while the comparator sequence can be arbitrarily given.
The significance of the regret bound guarantee is to make sure the total cost
incurred by the agent does not exceed that incurred by a comparator sequence
too much, and we would like to see the appearance of the negative regret, i.e,
the total cost incurred by the agent is smaller than that incurred by a
comparator sequence. Indeed, negative regret is very common in the standard
OCO in terms of universal dynamic regret in which the comparator sequence is
arbitrary (Zhao et al., 2020; Zhang, [n.d.]; Zhang et al., 2018).

Intuitively, the performance bounds of any online algorithm should depend on
how drastically $\\{{f}_{t}\\}$ and $\\{{\bm{g}}_{t}\\}$ vary across time,
that is, the temporal variations of $\\{{f}_{t}\\}$ and $\\{{\bm{g}}_{t}\\}$.
Thus we need to quantify the temporal variations of the dynamic environment.
Specifically, we need to quantify the temporal variations of functions
sequence. There are mainly two kinds of regularities in the literature of
constrained OCO (Chen et al., 2017; Cao and Liu, 2018; Chen and Giannakis,
2019; Yi et al., 2020; Sharma et al., 2020; Chen et al., 2018).

  * •

Path-length: the accumulated variation of per-slot minimizers
$\\{{x}_{t}^{*}\\}$

${V}_{x}=\sum_{t=2}^{T}{||{x}_{t}^{*}-{x}_{t-1}^{*}||}$

  * •

Function variation: the accumulatd variation of consecutive constraints

${V}_{\bm{g}}=\sum_{t=2}^{T}{\underset{x\in\chi}{sup}||{\bm{g}}_{t}(x)-{\bm{g}}_{t-1}(x)||}$

The reason we define the accumulative variation ${V}_{x}$ with respect to
${x}_{t}^{*}$ is that it can quantify the temporal variations of the dynamic
environment including loss functions ${f}_{t}$ and constraint functions
${g}_{t}$ since
${x}_{t}^{*}=\arg\min_{x\in\chi}{\\{{f}_{t}(x)|{\bm{g}}_{t}(x)\leq\bm{0}\\}}$.
While other definitions of it like
$\sum_{t=2}^{T}{\max_{x\in\chi}{|{f}_{t}-{f}_{t-1}|}}$ can only quantify the
temporal variations of the loss functions.

We let $||\cdot||$ be the Euclidean norm throughout this paper. In general, it
is challenging to achieve sublinear performance bounds for any online
algorithm unless regularity measures are sublinear; that is, the optimization
problem is feasible. For example, a non-oblivious adversary may choose a new
objective function ${f}_{t}$ and constraint function ${g}_{t}$ such that the
current per-slot minimizer ${x}_{t}^{*}$ is at least $O(1)$ distance away from
the selected action ${x}_{t}$ at each round $t$ (i.e., the accumulative
variations are the of order $T$). In such case, any online algorithm cannot
track the per-slot minimizers sequence $\\{{x}_{t}^{*}\\}$ well and guarantee
the sublinear dynamic regret/constraint violations.

###  2.2. Assumptions

After specifying the problem, we introduce some assumptions in this paper,
which are also common in the literature of constraint OCO (Cao and Liu, 2018;
Chen and Giannakis, 2019; Yu and Neely, 2020).

###### Assumption 1.

We make following assumptions with respect to feasible set $\chi$, objective
functions ${\\{f}_{t}(x){\\}}_{t=1}^{T}$ and constraint functions
${\\{\bm{g}}_{t}(x){\\}}_{t=1}^{T}$:

  * •

The feasible set $\chi$ is closed, convex, and compact with diameter $R$,
i.e., $\forall x,y\in\chi$, it holds that $||x-y||\leq R$.

  * •

The loss functions and constraint functions are convex, and bounded on $\chi$,
i.e., there exists a positive constant _F_ such that
$max\\{|{f}_{t}(x)|,{||\bm{g}}_{t}(x)||\\}\leq F,\forall x\in\chi,t.$

  * •

The gradients of ${g}_{k,t}$ and ${f}_{t}$ are upper-bounded by $G$ over
$\chi$, i.e., $max\\{||\nabla{f}_{t}(x)||,||\nabla{g}_{k,t}(x)||\\}\leq
G,\forall x\in\chi,k,t$. This is equivalent to ${\bm{g}}_{t}$ is Lipschitz
continuous with parameter $\beta$ ($\beta=KG$), i.e.,
$||{\bm{g}}_{t}(x)-{\bm{g}}_{t}(y)||\leq\beta||x-y||,\forall x,y\in\chi,t.$

Under Assumption 1, we study problem (P1) in the full-information setting;
that is, at round $t$, the agent can observe the complete loss and constraint
functions after the decision ${x}_{t}$ is submitted. In the following
sections, we will propose a virtual-queue-based parameter-free algorithm and
show that it simultaneously achieves sublinear regret and constraint
violations without the Slater condition.

##  3\. Algorithm

Algorithm 1 VQB

1: Initialize: ${\alpha}_{1},{\gamma}_{0}>0$,
${\bm{g}}_{0}=\bm{\lambda}(0)=0$, and ${x}_{1}\in\chi$.

2: for round $t=1...T-1$ do

3: Update the dual iterate $\bm{\lambda}(t)$:

4:
${\bm{\lambda}}(t)=\max\\{{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}),-{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})\\}$

5: Update the primal iterate that satisfies:

6:
${x}_{t+1}=\arg{\min}_{x\in\chi}{\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+[\bm{\lambda}(t)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}){]}^{T}({\gamma}_{t}{\bm{g}}_{t}(x))+{\alpha}_{t}||x-{x}_{t}{||}^{2}$

7: Choose the action ${x}_{t+1}$

8: end for

In this section, we propose a novel virtual-queue-based algorithm, VQB, which
is illustrated in Algorithm 1. It introduces a sequence of dual variables
$\\{{\bm{\lambda}}_{t}\\}$, which is also called virtual queue. The purpose of
introducing the virtual queue is that we can characterize the regret and
constraint violations through the drift-plus-penalty expression and then
analysis the regret and the constraint violations based on it. Similar ideas
of updating dual variables based on virtual queues are adopted in several very
recent works (e.g., (Yu and Neely, 2020; Qiu and Wei, 2020)) for OCO with
long-term and time-invariant constraints.

But there are some differences between our algorithm and theirs. First, in
order to ensure both regret and constraint violations are simultaneously
sublinear for the time-varying constraints setting, we design a new way of
involving instantaneous per-slot constraint violation into the virtual queues
and decision sequence update. Moreover, the learning rates of our algorithm,
i.e., ${\alpha}_{t}$ and ${\gamma}_{t}$ are time-varying, while the learning
rates of algorithm in (Yu et al., 2017; Yu and Neely, 2020; Qiu and Wei, 2020)
are unchanged in the whole time horizon. Therefore, our algorithm needs a new
regret and constraint violation analysis due to the new update rule of virtual
queues and the time-varying parameters. We will show more details in the
theoretical analysis part of section $4$.

Here we elaborate on the novelty and intuition of the entire algorithmic
approach of VQB. Note that if there are no constraints ${\bm{g}}_{t}$ (i.e.,
${\bm{g}}_{t}=\bm{0}$), then VQB has ${\bm{\lambda}}_{t}=\bm{0},\forall t$ and
becomes the OGD algorithm, which is wildly-used in standard OCO with learning
rate $\eta=\frac{1}{2{\alpha}_{t}}$ since

(2)
$\begin{split}&{x}_{t+1}=\arg\min_{x\in\chi}{\underbrace{{\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+{\alpha}_{t}||x-{x}_{t}{||}^{2}}}={\Pi}_{\chi}({x}_{t}-\frac{1}{2{\alpha}_{t}}\nabla{f}_{t}({x}_{t})).\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
penalty\end{split}$

Call the term marked by an underbrace in (LABEL:1) the penalty. Hence, the OGD
algorithm is to minimize the penalty term and is a special case of VQB. In our
algorithm VQB, if we define
$\bm{Q}(t)={{\bm{\lambda}}}(t)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})=\max\\{{\bm{\lambda}}(t-1)+2{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}),0\\}$
to be the vector of virtual queue backlogs and define Lyapunov drift
$\Delta(t)=\frac{1}{2}||{\bm{Q}}(t+1){||}^{2}-\frac{1}{2}||{\bm{Q}}(t){||}^{2}$,
the intuition behind VQB is to choose ${x}_{t+1}$ to minimize an upper bound
of the following expression (Since ${x}_{t+1}$ has not been determined at
round $t$, we replace ${\bm{g}}_{t}({x}_{t+1})$ with ${\bm{g}}_{t}(x)$ in
$\Delta(t)$ and omit the constant term.)

$\displaystyle\underbrace{\Delta(t)}+\underbrace{{\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+{\alpha}_{t}||x-{x}_{t}{||}^{2}}.$
$\displaystyle drift\quad\quad\quad\quad\quad\quad penalty$

Thus, the intention is to minimize penalty plus the Lyapunov drift, which is a
natural method in stochastic network optimization incorporated with the
stability condition (e.g., (Huang and Neely, 2011; Huang et al., 2012; Huang
et al., 2014)). The drift term $\Delta(t)$ could be used to evaluate the
constraint violations and is closely related to the virtual queues. The
penalty term includes the regularization term $||{x}_{t}-{x}_{t-1}{||}^{2}$
which could smoothen the difference between the coherent actions and make the
whole expression strongly-convex. The remaining term describes the
optimization problem.

Our algorithm also has a close connection with the saddle point methods
proposed in the literature of constrained OCO (Chen et al., 2017; Mahdavi et
al., 2012), which also incorporates dual variables to the decision-making
process. For example, in Algorithm 1,
${\bm{\lambda}}(t)=\max\\{{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}),-{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})\\}$
is a virtual queue vector for the constraint violation. The role of
$[\bm{\lambda}(t)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}){]}^{T}$ is similar to
a dual variable vector in saddle point-typed OCO algorithms. The main
differences between our algorithm and them is the update of dual variables and
the way of incorporating constraint functions into the dual variables (e.g.,
our algorithm uses a virtual queue to track the constraint violation, and the
dual variables in our algorithm are adaptively adjusted by the per-time slot
constraint violation). These differences render our algorithm some advantages
over saddle point methods in terms of performance guarantees.

##  4\. Results

In this section, we first present the major theoretical results and analysis
of our algorithm. Next, we extend our results to the case when the time
horizon is unknown and the case where the variation of consecutive constraints
is smooth enough across time, which captures many practical scenarios and has
been frequently considered in (Chen et al., 2017; Xu et al., 2019; Amiri,
2019).

###  4.1. Main results

Within this subsection, we present the upper bounds on the dynamic regret and
constraint violations for VQB.

###### Theorem 1.

Consider OCO problem (P1) under Assumption 1, let
$\\{{x}_{t}^{*}{\\}}_{t=1}^{T}$ be the per-slot minimizers sequence which
satisfies ${x}_{t}^{*}={\text{argmin}}_{x\in\chi,{\bm{g}}_{t}(x)\leq
0}{f}_{t}(x)$.

  * •

(Case 1) Setting ${\alpha}_{t}=\sqrt{\frac{T}{R+\sum_{i\leq
t}{||{x}_{i}^{*}-{x}_{i-1}^{*}{||}}}}$ and
${\gamma}_{t}^{2}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}$ in VQB, then we
have the following performance upper bounds

(3) $\begin{split}&regret\leq O(\max\\{\sqrt{T{V}_{x}},{V}_{g}\\}),\\\
&{Vio}_{k}\leq O(\max\\{\sqrt{T},{V}_{g}\\}),\forall k=1,2,...,K.\end{split}$

  * •

(Case 2) Setting ${\alpha}_{t}=\sqrt{\frac{T}{R+\sum_{i\leq
t}{||{x}_{i}^{*}-{x}_{i-1}^{*}{||}}}}$ and
${\gamma}_{t}^{2}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}\frac{1}{\sqrt{t+1}}$
in VQB, then we have the following performance upper bounds

(4) $\begin{split}&regret\leq O(\sqrt{T{V}_{x}}),\\\ &{Vio}_{k}\leq
O(\max\\{{T}^{\frac{3}{4}},{V}_{g}\\}),\forall k=1,2,...,K.\end{split}$

There are several advantages stated as following that makes our results
outperform previous studies. First, Theorem 1 implies that VQB can guarantee
sublinear regret and constraint violations simultaneously, as long as the
accumulated variations of the environment are sublinear, i.e., ${V}_{x}=o(T)$
and ${V}_{\bm{g}}=o(T)$. Previous studies listed in Table 1 do not always
simultaneously guarantee the sublinear performance bounds since they introduce
the $o(T){V}_{x}$ or $o(T){V}_{\bm{g}}$ term in their performance bounds,
which may be at least of the order _T_ even the optimization problem is
feasible, i.e., $\max\\{O({V}_{x}),O({V}_{\bm{g}})\\}=o(T)$.

Second, the dynamic regret upper bound guaranteed by both two cases of Theorem
1 could match the state-of-the-art dynamic regret bound $O(\sqrt{T{V}_{x}})$
in general OCO (Zhang et al., 2018; Zhao et al., 2018, 2020), when the path-
length of the benchmark sequence is ${V}_{x}$.

Moreover, our algorithm is parameter-free, that is, the parameters in our
algorithm do not require prior information of the regularities (e.g.,
${V}_{x}$ or ${V}_{\bm{g}}$). Meanwhile, Theorem 1 holds no matter whether the
Slater condition holds or not. The theoretical results of most previous study
are valid either under the Slater condition, or the order of the regularities
are known prior to the learner. Only (Chen et al., 2018) is both parameter-
free and independent of the assumption of the Slater condition, however, it
introduced degraded performance bounds and cannot guarantee the sublinear
regret and constraint violations simultaneously. Readers could see Table 1 for
the detailed comparisons.

We compare the performance bounds of our algorithm with the previous studies
listed in Table 1. When ${V}_{x}$ is not too large (e.g.,
${V}_{x}=o(\sqrt{T})$), the regret and constraint violations bounds presented
in the first case of Theorem 1 are all no worse than the state-of-the-art
results, i.e., $O[\sqrt{T}{V}_{x},\sqrt{T}]$ and
$O[\sqrt{T{V}_{x}},{V}_{x}^{1/4}{T}^{3/4}]$, established in (Chen and
Giannakis, 2019) and (Cao and Liu, 2018), respectively. Besides, the dynamic
regret bound presented in the second case of Theorem 1 is superior to all
existing works, and the corresponding constraint violations are also strictly
sublinear when the optimization problem is feasible.

Proof sketch of Theorem 1. Within this subsection, we give a proof sketch of
Theorem 1. All the proof details of listed lemmas could be found in the
Appendix. Since the drift-plus-penalty expression characterizes the dynamic
regret expression, we can translate the bounds of virtual queues
$\\{\bm{\lambda}(t)\\}$ into bounds of constraint violations. Thus, our proof
starts with the analysis of virtual queues properties and drift-plus-penalty
expression, that is, the Lyapunov drift term
$\Delta(t)=\frac{1}{2}[||\bm{\lambda(t+1)}{||}^{2}-||{\bm{\lambda}}(t){||}^{2}]$
plus the penalty term ${f}_{t}({x}_{t})$, which is associated with the loss
value after choosing an action. First, we present the main properties for
virtual queues $\\{{\lambda}_{t}{\\}}^{T}_{t=1}$ introduced in Algorithm 1 and
Lyapunov drift term.

###### Lemma 0.

(Properties of virtual queues) In Algorithm 1, we have the following
properties for virtual queues ${\bm{\lambda}}(t)$ and Lyapunov drift term
$\Delta(t)$:

  1. (1)

${\bm{\lambda}}(t)\geq\bm{0}$

  2. (2)

${\bm{\lambda}}(t)+{{\gamma}_{t-1}\bm{g}}_{t-1}({x}_{t})\geq 0$

  3. (3)

${||\bm{\lambda}}(t){||}\geq{{\gamma}_{t-1}||\bm{g}}_{t-1}({x}_{t}){||}$

  4. (4)

${{\gamma}_{t-1}\bm{g}}_{t-1}({x}_{t})\leq{\bm{\lambda}}(t)-{\bm{\lambda}}(t-1)$,
furthermore,
${||\bm{\lambda}}(t){||}-{||\bm{\lambda}}(t-1){||}{\leq{\gamma}_{t-1}||\bm{g}}_{t-1}({x}_{t}){||}$

  5. (5)

$\Delta(t)\leq{\gamma}_{t}[\bm{\lambda}(t){]}^{T}{\bm{g}}_{t}({x}_{t+1})+{\gamma}_{t}^{2}||{\bm{g}}_{t}({x}_{t+1}){||}^{2}$

The proof of this lemma is motivated by (Yu and Neely, 2020; Qiu and Wei,
2020). However, due to our new algorithm, different constraints setting and
fewer assumptions, our proof techniques is slightly different from theirs.
Then we present the upper bound of drift-plus-penalty expression in the
following lemma.

###### Lemma 0.

(Upper bound of the drift-plus-penalty expression) Under Assumption 1, let
$\delta>0$ and $\\{{\alpha}_{t}{\\}}_{t=1}^{T}$,
$\\{{\gamma}_{t}{\\}}_{t=1}^{T}$ be any positive non-increasing sequences, if
$2{\gamma}_{t}\leq{\gamma}_{t-1}+{\gamma}_{t+1}$ holds for all $t$, then VQB
ensures that:

(5)
$\begin{split}&{f}_{t}({x}_{t})+\Delta(t)\leq{\alpha}_{t}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}_{t+1}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+({\beta}^{2}{\gamma}_{t-1}^{2}+\frac{\delta}{2}-{\alpha}_{t})||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&+\frac{1}{2\delta}{G}^{2}+\frac{1}{2}{\gamma}_{t}{\gamma}_{t+1}||{{{\bm{g}}}}_{t}({x}_{t+1}){||}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{{\bm{g}}}}_{t-1}({x}_{t}){||}^{2}+{\gamma}_{t-1}{\gamma}_{t}||{{{\bm{g}}}}_{t-1}({x}_{t})-{{{\bm{g}}}}_{t}({x}_{t}){||}^{2}+{f}_{t}({x}_{t}^{*}).\end{split}$

This is the key lemma in our theoretical analysis, which is used to yield the
eventual bounds of regret and virtual queues. Next, we bound the dynamic
regret as follows based on Lemma 3.

###### Lemma 0.

(Regret bound) Under Assumption 1, for arbitrary $\delta>0$ which satisfies
${\alpha}_{t}\geq{\beta}^{2}{\gamma}_{t-1}^{2}+\frac{\delta}{2}$, if
${\gamma}_{t}\leq{\gamma}_{t+1}$, ${\alpha}_{t}\leq{\alpha}_{t+1}$ and
$2{\gamma}_{t}\leq{\gamma}_{t-1}+{\gamma}_{t+1}$ hold for all $t$, then VQB
ensures that

(6)
$\begin{split}\sum_{t=1}^{T}{{f}_{t}({x}_{t})}&\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}_{1}{R}^{2}+4R\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+\frac{T{G}^{2}}{2\delta}+\frac{1}{2}{\gamma}_{T}{\gamma}_{T+1}||{{\bm{g}}}_{T}({x}_{T+1}){||}^{2}\\\
&+\frac{1}{2}||{\bm{\lambda}}(1){||}^{2}+2F\sum_{t=1}^{T}{{{\gamma}_{t-1}^{2}||{\bm{g}}_{t-1}({x}_{t})-{\bm{g}}_{t}({x}_{t})||}}.\end{split}$

Here we define ${x}_{T+1}^{*}={x}_{T}^{*}$.

We further bound the eventual virtual queues length in the following lemma
based on Lemma 3.

###### Lemma 0.

Under Assumption 1, setting $\delta,{\alpha}_{t}\;and\;{\gamma}_{t}$ to be the
same as Lemma 4, then VQB ensures that

(7) $\begin{split}||\bm{\lambda}(T){||}&\leq
2\sqrt{F(T-1)}+\sqrt{2{\alpha}_{1}{R}^{2}}+\sqrt{\frac{(T-1){G}^{2}}{\delta}}+{\gamma}_{T-1}||{{{\bm{g}}}}_{T-1}({x}_{T}){||}\\\
&+2\sqrt{2R\sum_{t=1}^{T-1}{{\alpha}_{t}||{x}_{t+1}^{*}-{x}_{t}^{*}{||}}}+2\sqrt{F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{{\bm{g}}}}_{t-1}({x}_{t})-{{{\bm{g}}}}_{t}({x}_{t}){||}}}.\end{split}$

This is another critical lemma in our theoretical analysis that could be used
to yield the constraint violations’ upper bounds. We upper bound the
constraint violations in the following two lemmas.

###### Lemma 0.

For any non-increasing sequence $\\{{\gamma}_{t}\\}$, VQB ensures that

(8)
$\sum_{t=1}^{T}{{g}_{k,t}({x}_{t})}\leq\frac{||{\bm{\lambda}}(T)||}{{\gamma}_{T}}+{V}_{\bm{g}},\;\forall
k=1,2,...,K.$

Recall that Lemma 5 bounds the virtual queue length. Thus combining this lemma
with the Lemma 6, we can bound the constraint violations in the following
lemma.

###### Lemma 0.

(Constraint violations’ bounds) Setting $\delta,{\alpha}_{t}$ and
${\gamma}_{t}$ to be the same as Lemma 4, then VQB ensures that

(9)
$\begin{split}\sum_{t=1}^{T}{{g}_{k,t}({x}_{t})}&\leq\frac{2}{{\gamma}_{T}}\sqrt{F(T-1)}+\frac{1}{{\gamma}_{T}}\sqrt{2{\alpha}_{1}{R}^{2}}+{V}_{{\bm{g}}}+\frac{{\gamma}_{T-1}}{{\gamma}_{T}}||{{{\bm{g}}}}_{T-1}({x}_{T}){||}\\\
&+\frac{2}{{\gamma}_{T}}\sqrt{2R\sum_{t=1}^{T-1}{{\alpha}_{t}||{x}_{t+1}^{*}-{x}_{t}^{*}{||}}}+\frac{2}{{\gamma}_{T}}\sqrt{F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{{\bm{g}}}}_{t-1}({x}_{t})-{{{\bm{g}}}}_{t}({x}_{t}){||}}}+\frac{G}{{\gamma}_{T}}\sqrt{\frac{T-1}{\delta}}.\end{split}$

According to Lemmas 4 and 7, with parameters stated in Theorem 1, we could
prove the theoretical results of Theorem 1. First we consider the Case 1 in
Theorem 1, by the setting of ${\alpha}_{t}$ and according to Lemma 2, we can
obtain

(10)
$\begin{split}&\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}=\sum_{t=1}^{T}{\sqrt{\frac{T}{R+\sum_{i\leq
t}{||{x}_{i}-{x}_{i-1}{||}}}}||{x}_{t+1}^{*}-{x}_{t}^{*}||}\\\
&=\sqrt{T}\sum_{t=1}^{T}{\frac{||{x}_{t+1}^{*}-{x}_{t}^{*}||}{\sqrt{R+\sum_{i\leq
t}{||{x}_{i}-{x}_{i-1}{||}}}}}\leq
2\sqrt{T}\sqrt{\sum_{t=0}^{T}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}=2\sqrt{T{V}_{x}}\end{split}$

By the setting of ${\gamma}_{t}$ and according to Lemma 1, we also have

(11)
$\begin{split}&\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}\sum_{t=1}^{T}{||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}\\\
&\leq\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}\sum_{t=1}^{T}{\max_{x\in\chi}{||{{\bm{g}}}_{t-1}({x})-{{\bm{g}}}_{t}({x}){||}}}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}{V}_{\bm{g}}\end{split}$

Setting $\delta=\frac{1}{2}\sqrt{\frac{T}{R+{V}_{x}}}$, it is easy to verity
that ${\alpha}_{t}\geq{\beta}^{2}{\gamma}_{t-1}^{2}+\frac{\delta}{2}$,
$2{\gamma}_{t}\leq{\gamma}_{t-1}+{\gamma}_{t+1}$, and both
$\\{{\alpha}_{t}\\}$ and $\\{{\gamma}_{t}\\}$ are non-increasing sequences.
Thus combing Lemma 2 with (LABEL:1_proof_of_theorem_1),
(LABEL:2_proof_of_theorem_1) and rearranging terms yields

(12)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}-\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}\\\
&\leq
4R\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+{\alpha}_{1}{R}^{2}+\frac{T{G}^{2}}{2\delta}+\frac{1}{2}{\gamma}_{T}{\gamma}_{T+1}||{{\bm{g}}}_{T}({x}_{T+1}){||}^{2}+2F\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}\\\
&\leq
8R\sqrt{T{V}_{x}}+\sqrt{\frac{T}{R}}{R}^{2}+\frac{T{G}^{2}}{2\delta}+\frac{1}{4{\beta}^{2}}\frac{1}{\sqrt{2R}}{F}^{2}+\frac{F}{{\beta}^{2}}\frac{{V}_{\bm{g}}}{\sqrt{2R}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}\\\
&\overset{(a)}{\leq}8R\sqrt{T{V}_{x}}+\sqrt{\frac{T}{R}}{R}^{2}+T{G}^{2}\sqrt{\frac{R+{V}_{x}}{T}}+\frac{1}{4{\beta}^{2}}\frac{1}{\sqrt{2R}}{F}^{2}+\frac{F}{{\beta}^{2}}\frac{{V}_{\bm{g}}}{\sqrt{2R}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}\\\
&=8R\sqrt{T{V}_{x}}+{R}^{2/3}\sqrt{T}+{G}^{2}\sqrt{T(R+{V}_{x})}+\frac{1}{4{\beta}^{2}}\frac{1}{\sqrt{2R}}{F}^{2}+\frac{F}{{\beta}^{2}}\frac{{V}_{\bm{g}}}{\sqrt{2R}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}\\\
&=O(max\\{\sqrt{T{V}_{x}},{V}_{\bm{g}}\\})\end{split}$

Where (a) holds since we set $\delta=\frac{1}{2}\sqrt{\frac{T}{R+{V}_{x}}}$.
According to Lemma $5$ and Assumption 1, we have

$\displaystyle\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{2}{{\gamma}_{T}}\sqrt{F(T-1)}+\frac{1}{{\gamma}_{T}}\sqrt{2{\alpha}_{1}{R}^{2}}+\frac{{\gamma}_{T-1}}{{\gamma}_{T}}||{{{\bm{g}}}}_{T-1}({x}_{T}){||}+\frac{G}{{\gamma}_{T}}\sqrt{\frac{T-1}{\delta}}$
$\displaystyle+\frac{2}{{\gamma}_{T}}\sqrt{2R\sum_{t=1}^{T-1}{{\alpha}_{t}||{x}_{t+1}^{*}-{x}_{t}^{*}{||}}}+\frac{2}{{\gamma}_{T}}\sqrt{F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{{\bm{g}}}}_{t-1}({x}_{t})-{{{\bm{g}}}}_{t}({x}_{t}){||}}}+{V}_{\bm{g}}$
$\displaystyle\overset{(a)}{\leq}\sqrt{\frac{1}{2\sqrt{2R}{\beta}^{2}}}[2\sqrt{F(T-1)}+R\sqrt{2\sqrt{\frac{T}{R}}}+G\sqrt{2\frac{(T-1)\sqrt{R+{V}_{x}}}{\sqrt{T}}}]$
(13)
$\begin{split}&+F+\sqrt{\frac{2}{\sqrt{2R}{\beta}^{2}}}[\sqrt{4R\sqrt{T{V}_{x}}}+\sqrt{\frac{F}{2{\beta}^{2}}\frac{{V}_{\bm{g}}}{\sqrt{2R}}}]+{V}_{\bm{g}}\\\
&\overset{(b)}{\leq}\sqrt{\frac{1}{2\sqrt{2R}{\beta}^{2}}}[2\sqrt{F(T-1)}+R\sqrt{2\sqrt{\frac{T}{R}}}+G\sqrt{2R\sqrt{T(1+T})}]\\\
&+F+\sqrt{\frac{2}{\sqrt{2R}{\beta}^{2}}}[\sqrt{4R\sqrt{R}T}+\sqrt{\frac{F}{2{\beta}^{2}}\frac{{V}_{\bm{g}}}{\sqrt{2R}}}]+{V}_{\bm{g}}=O(max\\{\sqrt{T},{V}_{\bm{g}}\\})\end{split}$

Where (a) is due to (LABEL:1_proof_of_theorem_1) and
(LABEL:2_proof_of_theorem_1); (b) is due to ${V}_{x}\leq RT$. For the Case 2
in Theorem 1, since the settings of ${\alpha}_{t}$ in both two cases are the
same, we can also derive that

(14) $\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}\leq
2\sqrt{T{V}_{x}}$

For term
$\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}$,
according to Lemma 1 and by the setting of ${\gamma}_{t}$, we have

(15)
$\begin{split}&\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}\sum_{t=1}^{T}{\frac{1}{\sqrt{t}}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}\\\
&\leq\frac{F}{{\beta}^{2}}\frac{1}{\sqrt{2R}}\sum_{t=1}^{T}{\frac{1}{\sqrt{t}}}\leq\frac{F}{{\beta}^{2}}\frac{\sqrt{2T}}{\sqrt{R}}\end{split}$

Setting $\delta=\frac{1}{2}\sqrt{\frac{T}{R+{V}_{x}}}$, it is easy to verity
that ${\alpha}_{t}\geq{\beta}^{2}{\gamma}_{t-1}^{2}+\frac{\delta}{2}$,
$2{\gamma}_{t}\leq{\gamma}_{t-1}+{\gamma}_{t+1}$, and both
$\\{{\alpha}_{t}\\}$ and $\\{{\gamma}_{t}\\}$ are non-increasing sequences.
Based on Lemma 2, combining (14), (LABEL:4_proof_theorem_1) and Assumption 1
gives

(16)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}-\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}\\\
&\leq
4R\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+{\alpha}_{1}{R}^{2}+\frac{T{G}^{2}}{2\delta}+\frac{1}{2}{\gamma}_{T}{\gamma}_{T+1}||{{\bm{g}}}_{T}({x}_{T+1}){||}^{2}+2F\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}\\\
&\leq
8R\sqrt{T{V}_{x}}+{R}^{3/2}\sqrt{T}+T{G}^{2}\sqrt{\frac{R+{V}_{x}}{T}}+\frac{{F}^{2}}{4{\beta}^{2}}\frac{1}{\sqrt{2R}}\frac{1}{\sqrt{T}}+\frac{2{F}^{2}}{{\beta}^{2}}\frac{\sqrt{2T}}{\sqrt{R}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}=O(\sqrt{T{V}_{x}})\end{split}$

Furthermore, based on Lemma 5, we obtain the bounds of constraint violations
as follows

$\displaystyle\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{2}{{\gamma}_{T}}\sqrt{F(T-1)}+\frac{1}{{\gamma}_{T}}\sqrt{2{\alpha}_{1}{R}^{2}}+\frac{{\gamma}_{T-1}}{{\gamma}_{T}}||{{{\bm{g}}}}_{T-1}({x}_{T}){||}+\frac{G}{{\gamma}_{T}}\sqrt{\frac{T-1}{\delta}}$
$\displaystyle+\frac{2}{{\gamma}_{T}}\sqrt{2R\sum_{t=1}^{T-1}{{\alpha}_{t}||{x}_{t+1}^{*}-{x}_{t}^{*}{||}}}+\frac{2}{{\gamma}_{T}}\sqrt{F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{{\bm{g}}}}_{t-1}({x}_{t})-{{{\bm{g}}}}_{t}({x}_{t}){||}}}+{V}_{\bm{g}}$
$\displaystyle\overset{(a)}{\leq}{T}^{1/4}\sqrt{\frac{1}{2\sqrt{2R}{\beta}^{2}}}[2\sqrt{F(T-1)}+R\sqrt{2\sqrt{\frac{T}{R}}}+G\sqrt{2\frac{(T-1)\sqrt{R+{V}_{x}}}{\sqrt{T}}}]$
(17)
$\begin{split}&+{(\frac{T+1}{T})}^{1/4}F+{T}^{1/4}\sqrt{\frac{2}{\sqrt{2R}{\beta}^{2}}}[\sqrt{4R\sqrt{T{V}_{x}}}+\frac{F}{{\beta}}\sqrt{\frac{\sqrt{2T}}{\sqrt{R}}}]+{V}_{\bm{g}}\\\
&\overset{(b)}{\leq}{T}^{1/4}\sqrt{\frac{1}{2\sqrt{2R}{\beta}^{2}}}[2\sqrt{F(T-1)}+R\sqrt{2\sqrt{\frac{T}{R}}}+G\sqrt{2R\sqrt{T(1+T})}]\\\
&+{2}^{1/4}F+{T}^{1/4}\sqrt{\frac{2}{\sqrt{2R}{\beta}^{2}}}[\sqrt{4R\sqrt{T{V}_{x}}}+\frac{F}{{\beta}}\sqrt{\frac{\sqrt{2T}}{\sqrt{R}}}]+{V}_{\bm{g}}=O(max\\{{T}^{3/4},{V}_{\bm{g}}\\})\end{split}$

Where (a) follows from (14) and (LABEL:4_proof_theorem_1); (b) holds by the
fact that ${V}_{x}\leq RT$ and $\frac{T+1}{T}\leq 2$. It completes the proof.

###### Remark 1.

When feasible set $\chi$ is time-varying, i.e., $\chi(t)$, our algorithm VQB
is valid and we can verify that its corresponding theoretical results also
hold.

###  4.2. Slater condition

In the previous section, we have shown that as long as the optimization
problem is feasible, our algorithm could simultaneously achieve sublinear
dynamic regret and constraint violation with only limited common assumptions
in the literature of constrained OCO. Meanwhile, (Chen et al., 2017) pointed
out that in many practical constrained OCO problems, the variation of
consecutive constraints is smooth across time. Thus, we examine whether the
smoothness of the dynamic environment’s temporal variations can lead to better
bounds of constraint violations for VQB. Within this subsection, we consider a
slightly stronger Slater condition that has been considered in (Chen et al.,
2017). We will show that our variant of VQB, illustrated in Algorithm 2, could
guarantee the $O(1)$ constraint violations under this assumption. The
difference between VQB and Algorithm 2 is the way of incorporating constraints
into the virtual queues updates and decision iterations, i.e., Algorithm 2
uses ${\bm{g}}_{t}({x}_{t})$ instead of ${\bm{g}}_{t-1}({x}_{t})$ to update
the dual iterate ${\bm{\lambda}}_{t}$ and primal iterate ${x}_{t}$ compared
with VQB. Technically, the update step in Algorithm 2 can yield much lower
constraint violations when the variation of consecutive constraints is smooth
across time, as shown in Theorem 2. First, we give the definition of the
Slater condition.

Algorithm 2

1: Initialize: ${\alpha},\gamma>0$, ${\bm{g}}_{0}=\bm{\lambda}(0)=0$, and
${x}_{1}\in\chi$.

2: for round $t=1...T-1$ do

3: Update the dual iterate $\bm{\lambda}(t)$:

4:
${\bm{\lambda}}(t)=max\\{{\bm{\lambda}}(t-1)+{\gamma\bm{g}}_{t}({x}_{t}),-{\gamma\bm{g}}_{t}({x}_{t})\\}$

5: Update the primal iterate that satisfies:

6:
${x}_{t+1}={argmin}_{x\in\chi}{\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+[\bm{\lambda}(t)+\gamma{\bm{g}}_{t}({x}_{t}){]}^{T}(\gamma{\bm{g}}_{t}(x))+{\alpha}||x-{x}_{t}{||}^{2}$

7: Choose the action ${x}_{t+1}$

8: end for

###### Assumption 2.

(Slater condition). There exists $\epsilon>0$ and $\hat{x}\in\chi$ such that
${\bm{g}}_{t}(\hat{x})\leq-\epsilon I,\forall t$.

Assumption 2 is known as the interior point condition or Slater condition,
which is also used widely in the literature of OCO with time-varying
constraints (Chen et al., 2017; Chen and Giannakis, 2019; Sharma et al., 2020;
Yi et al., 2020). Based on Assumption 2, we next introduce a slightly stronger
Slater condition assumption, which is valid in many practical scenarios (Chen
et al., 2017; Xu et al., 2019; Amiri, 2019).

###### Assumption 3.

The slater constant $\epsilon$ is larger than the maximum variation of
consecutive constraints, i.e.,
$\epsilon>{\bar{V}}_{\bm{g}}=\underset{t}{\max}\underset{x\in\chi}{\max}||{\bm{g}}_{t+1}(x)-{\bm{g}}_{t}(x)||$.

Note that this assumption was adopted in (Chen et al., 2017), which is valid
when the region defined by $\\{x|x\in\chi,{g}_{t}(x)\leq 0\\}$ is large
enough, or the variation of consecutive constraints is smooth enough across
time.

With a similar intuition of VQB, if we define
$\bm{Q}(t)={{\bm{\lambda}}}(t)+{\gamma}_{t}{\bm{g}}_{t}({x}_{t})=\max\\{{\bm{\lambda}}(t-1)+2{\gamma}_{t}{\bm{g}}_{t}({x}_{t}),0\\}$
as the vector of virtual queue backlogs and let parameters
${\alpha}_{t},{\gamma}_{t}$ be time-invariant, Algorithm 2 also chooses
${x}_{t+1}$ to minimize an upper bound of the following expression:

$\displaystyle\underbrace{\Delta(t)}+\underbrace{{\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+{\alpha}_{t}||x-{x}_{t}{||}^{2}}.$
$\displaystyle drift\quad\quad\quad\quad\quad\quad penalty$

The reason to replace ${\bm{g}}_{t-1}({x}_{t})$ with ${\bm{g}}_{t}({x}_{t})$
in Algorithm 2 is motivated by the observation that ${\bm{g}}_{t}({x}_{t})$
could be directly accumulated into queue ${\bm{\lambda}}(t)$ (recall that
${\bm{\lambda}}(t)=\max\\{{\bm{\lambda}}(t-1)+{\gamma\bm{g}}_{t}({x}_{t}),-{\gamma\bm{g}}_{t}({x}_{t})\\}$)
and we intend to have small queue backlogs when the variation of consecutive
constraint functions is smooth across time. This is important for a much
tighter analysis of the constraint violations under the strongly Slater
condition. If we use ${\bm{g}}_{t}({x}_{t})$ instead of
${\bm{g}}_{t-1}({x}_{t})$ in VQB, we could get ${\gamma
g}_{t,k}({x}_{t})\leq{\lambda}_{k}(t)-{\lambda}_{k}(t-1)$. Then, we can
characterize the constraint violations only by the bounds of virtual queues
$\\{\bm{\lambda}(t)\\}$ without the term ${V}_{g}$ (comparing with the Lemma
5), i.e.,
$\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{{\lambda}_{k}(T)}{\gamma}\leq\frac{||\bm{\lambda}(T)||}{\gamma},\forall
k.$ In such case, the length of virtual queues
$\\{||{\bm{\lambda}}(t)||{\\}}_{t=1}^{T}$ is upper bounded by a constant under
the strongly Slater condition (Lemma 11). Then we could obtain an $O(1)$ bound
of constraint violations, shown in the following theorem.

###### Theorem 8.

Under Assumption 1,2 and 3, setting ${\alpha}={T}^{a}$ and
${\gamma}^{2}=\frac{1}{2{\beta}^{2}}{T}^{a}$ in Algorithm 2, the dynamic
regret and constraint violations are upper bounded by

(18) $\begin{split}&regret\leq
O(\max\\{{T}^{a}{V}_{x},{T}^{a}{V}_{g},{T}^{1-a}\\})\\\ &{Vio}_{k}\leq
O(1),\;\forall k=1,2,...,K\end{split}$

In particular, the performance upper bounds become $O(\max$
$\\{\sqrt{T}{V}_{x},\sqrt{T}{V}_{g}\\})$ and $O(1)$ if we set
${\alpha}=2{\beta}^{2}{\gamma}^{2}=\sqrt{T}$.

Note that our performance bounds established by Algorithm 2 are strictly
better than (Chen et al., 2017) under the same assumptions. Besides, the
constraint violations for Algorithm 2 can decrease into $O(1)$ when the
variations of consecutive constraints are smooth enough across time.

Proof sketch of Theorem 2. Here we give a proof sketch of Theorem 2. All the
proof details of listed lemmas could be found in the Appendix. Note that both
$\\{{\alpha}_{t}\\}$ and $\\{{\gamma}_{t}\\}$ are constant sequences in
Algorithm 2, thus here we omit the subscript $t$. Similar as Lemma 2, in
Algorithm 2, we have the following lemma for the properties of virtual queues
and Lyapunov drift term.

###### Lemma 0.

In algorithm 2, at each round $t$, we have

  1. (1)

${\bm{\lambda}}(t)\geq\bm{0}$

  2. (2)

${\bm{\lambda}}(t)+{\gamma\bm{g}}_{t}({x}_{t})\geq\bm{0}$

  3. (3)

${||\bm{\lambda}}(t){||}\geq{\gamma||\bm{g}}_{t-1}({x}_{t}){||}$

  4. (4)

${\gamma\bm{g}}_{t}({x}_{t})\leq{\bm{\lambda}}(t)-{\bm{\lambda}}(t-1)$,
furthermore,
${||\bm{\lambda}}(t){||}-{||\bm{\lambda}}(t-1){||}{\leq\gamma||\bm{g}}_{t}({x}_{t}){||}$

  5. (5)

$\Delta(t)\leq\gamma[\bm{\lambda}(t){]}^{T}{\bm{g}}_{t+1}({x}_{t+1})+{\gamma}^{2}||{\bm{g}}_{t+1}({x}_{t+1}){||}_{2}^{2}$

The proof of this Lemma is similar as the proof of Lemma 2 and hence we omit
the details.

###### Lemma 0.

Under Assumption 1,2 and 3, setting $\alpha,\gamma,\delta$ such that
$\alpha\geq\frac{1}{2}({\beta}^{2}{\gamma}^{2}+\delta)$, then Algorithm 2
ensures that

(19) $\begin{split}&{f}_{t}({x}_{t})+\Delta(t)\\\
&\leq{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}^{2}+{\gamma}^{2}F||{{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{{\bm{g}}}}_{t}({x}_{t+1})||}\\\
&+\frac{1}{2\delta}{G}^{2}+\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t+1}({x}_{t+1}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t}({x}_{t}){||}^{2}+\gamma||{{\bm{\lambda}}}(t){||}||{{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{\bm{g}}}}_{t}({x}_{t+1}){||}\end{split}$

Take a similar derivation process as the proof of Theorem 1, we also
characterize the regret and constraint violations through the bound of drift-
plus-penalty expression stated above. Therefore, we bound the dynamic regret
and constraint violations in the following lemmas, respectively.

###### Lemma 0.

Under the Assumption 1, 2 and 3, setting $\alpha,\gamma,\delta$ such that
$\alpha\geq\frac{1}{2}{\beta}^{2}{\gamma}^{2}+\frac{1}{2}\delta$, then
Algorithm 2 ensures that

(20)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}||{x}_{1}^{*}-{x}_{1}{||}^{2}+4R\alpha{V}_{x}+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{g}+L(1)+\gamma\max_{t}{||{{\bm{\lambda}}}(t){||}}{V}_{\bm{g}}\end{split}$

###### Lemma 0.

In Algorithm 2, we have

(21)
$\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{{\lambda}_{k}(T)}{\gamma}\leq\frac{||\bm{\lambda}(T)||}{\gamma},\;\forall
k\in\\{1,2,...,K\\}.$

Note that the above two lemmas show that the final bounds of dynamic regret
and constraint violations can be obtained by bounding the ${\bm{\lambda}}(t)$.
Since we are allowed to introduce the assumption of strongly Slater condition,
we will show that the length of virtual queues is upper bounded by a constant
in this case. Hence we adopt different techniques for the virtual queues
analysis compared with the proof of Lemma 5, and bound them by accomplishing
the following lemma.

###### Lemma 0.

In Algorithm 2, we have

(22) $||{\bm{\lambda}}(t){||}\leq\gamma F+\frac{GR+{\gamma}^{2}\epsilon
F+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}}{\gamma(\epsilon-{\bar{V}}_{g})},\;\forall
t.$

Finally, based on the above lemmas, we prove the Theorem 2 as follows. We
setting $\delta=\frac{1}{2}{T}^{a}$, and it is easy to verity that
${\alpha}_{t}\geq\frac{1}{2}{\beta}^{2}{\gamma}^{2}+\frac{\delta}{2}$.
Combining the Lemma 11 with Lemma 13, we have

(23)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}-\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}\\\
&\leq{\alpha}||{x}_{1}^{*}-{x}_{1}{||}^{2}+4R\alpha{V}_{x}+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{\bm{g}}+\frac{1}{2}||{\bm{\lambda}}(1){||}^{2}+\gamma\max_{t}{||{{\bm{\lambda}}}(t){||}}{V}_{\bm{g}}\\\
&\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}{R}^{2}+4R\alpha{V}_{x}+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{\bm{g}}+\frac{1}{2}||{\bm{\lambda}}(1){||}^{2}+({\gamma}^{2}F+\frac{GR+{\gamma}^{2}\epsilon
F+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}}{(\epsilon-{\bar{V}}_{\bm{g}})}){V}_{\bm{g}}\\\
&=O(max\\{{T}^{a}{V}_{x},{\gamma}^{2}{V}_{\bm{g}},{T}^{1-a}\\})=O(max\\{{T}^{a}{V}_{x},{V}_{\bm{g}}{T}^{a},{T}^{1-a}\\})\end{split}$

Furthermore, combining the Lemma 12 with Lemma 13, we can obtain

(24)
$\begin{split}&\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{||{\bm{\lambda}}(T)||}{\gamma}\leq
F+\frac{GR+{\gamma}^{2}\epsilon
F+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}}{{\gamma}^{2}(\epsilon-{\bar{V}}_{\bm{g}})}\\\
&=O(\frac{\alpha}{{\gamma}^{2}})=O({T}^{1-a}),\;\forall
k=1,2,...,K.\end{split}$

In particular, when setting $\alpha=\frac{1}{2}\sqrt{T}$ and
${\gamma}^{2}=\frac{1}{2{\beta}^{2}}\sqrt{T}$ , the performance upper bounds
become $O(max\\{\sqrt{T}{V}_{x},\sqrt{T}{V}_{\bm{g}}\\})$ and $O(1)$. This
completes the proof.

###  4.3. Unknown time horizon _T_

Algorithm 3 The Doubling Trick for Online Algorithm A

1: Let $i=1$.

2: while not reach the end of the time horizon do

3: Reset _A_ with parameters chosen for $T={2}^{i}$.

4: Run _A_ for ${2}^{i}$ rounds.

5: Let $i=i+1$.

6: end while

In this subsection, we extend our algorithm and analysis the case when time
horizon is unknown. Recall that the parameters of VQB, i.e., ${\gamma}_{t}$
and ${\alpha}_{t}$, and previous methods for OCO with long-term and time-
varying constraints all depend on the time horizon _T_ , while the total
rounds $T$ is not known prior to the learner in many practical scenarios. In
such cases, we use the doubling trick strategy to tune the parameters for our
algorithm. To the best of our knowledge, we are the first to consider the
unknown time horizon case for OCO with long-term and time-varying constraints.
For any online Algorithm _A_ whose parameters depend on the time horizon $T$,
the doubling trick is described in Algorithm 3.

###### Theorem 14.

Under Assumption 1, for any unknown time horizon T, run VQB until reaching the
end of the time horizon. Let ${t}_{i}={2}^{i}$ be the index of the first round
of i-th epoch.

  * •

(Case 1) Setting ${\alpha}_{t}=\sqrt{\frac{{2}^{i}}{R+\sum_{{t}_{i}\leq i\leq
t}{||{x}_{i}^{*}-{x}_{i-1}^{*}{||}}}}$ and
${\gamma}_{t}^{2}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}$ for
$t\in[{t}_{i},{t}_{i+1}-1]$, then VQB with doubling trick ensures

(25) $\begin{split}&regret\leq O(\max\\{\sqrt{T{V}_{x}},{V}_{g}\\}),\\\
&{Vio}_{k}\leq O(\max\\{\sqrt{T},{V}_{g}\\}),\forall k=1,2,...,K.\end{split}$

  * •

(Case 2) Setting ${\alpha}_{t}=\sqrt{\frac{{2}^{i}}{R+\sum_{{t}_{i}\leq i\leq
t}{||{x}_{i}^{*}-{x}_{i-1}^{*}{||}}}}$ and
${\gamma}_{t}^{2}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}\frac{1}{\sqrt{t-{t}_{i}+2}}$
for $t\in[{t}_{i},{t}_{i+1}-1]$, then VQB with doubling trick ensures

(26) $\begin{split}&regret\leq O(\sqrt{T{V}_{x}}),\\\ &{Vio}_{k}\leq
O(\max\\{{T}^{\frac{3}{4}},{V}_{g}\\}),\forall k=1,2,...,K.\end{split}$

Theorem 3 shows that our algorithm with the doubling trick can still preserve
the order of dynamic regret and constraint violations bounds even though the
time horizon $T$ is unknown. Note that our algorithm adapts to the doubling
trick because of the property of parameter-free, while parameter-dependent
methods (e.g., (Cao and Liu, 2018)) cannot do this.

Proof sketch of Theorem 3. Here we give a proof of Theorem 3. For the Case 1
in Theorem 3, since the _i_ -th epoch consists of at most ${2}^{i}$ rounds,
the time horizon is divided into $N=\lceil{log}_{2}T\rceil$ epochs. Let
${\Delta}_{x}^{i}=\sum_{t={t}_{i}}^{t={t}_{i}-1}{||{x}_{t}^{*}-{x}_{t-1}^{*}||}$
and
${\Delta}_{g}^{i}=\sum_{t={t}_{i}}^{t={t}_{i}-1}{\underset{x\in\chi}{sup}||{\bm{g}}_{t}(x)-{\bm{g}}_{t-1}(x)||}$.
By Theorem 1, in the _i_ -th epoch there exists a constant _C_ such that the
dynamic regret and constraint violations are at most
$max\\{C\sqrt{T{\Delta}_{x}^{i}},C{\Delta}_{g}^{i}\\}$ and
$max\\{C\sqrt{{2}^{i}},C{\Delta}_{g}^{i}\\}$ respectively. The final bound
could be obtained by summing the individual bounds over all the epochs.
Therefore, we could upper bound the total dynamic regret and constraint
violations as follows

(27) $\begin{split}Regret&\leq
max\\{\sum_{i=0}^{N}{C\sqrt{{2}^{i}{\Delta}_{x}^{i}}},\sum_{i=0}^{N}{C{\Delta}_{g}^{i}}\\}\overset{(a)}{\leq}max\\{C\sqrt{\sum_{i=0}^{N}{{\Delta}_{x}^{i}}}\sqrt{\sum_{i=0}^{N}{{2}^{i}}},C\sum_{i=0}^{N}{{\Delta}_{g}^{i}}\\}\\\
&\leq
max\\{C\sqrt{{V}_{x}}\sqrt{{2}^{N+1}-1},C\sum_{i=0}^{N}{{\Delta}_{g}^{i}}\\}=max\\{C\sqrt{{V}_{x}}\sqrt{{2}^{\lceil{log}_{2}T\rceil+1}-1},C{V}_{\bm{g}}\\}\\\
&\leq
max\\{C\sqrt{{V}_{x}}\sqrt{{2}^{{log}_{2}T+2}},C{V}_{\bm{g}}\\}=max\\{2C\sqrt{T{V}_{x}},C{V}_{\bm{g}}\\}\end{split}$

Where (a) is due to the Cauchy-schwarz inequality. And the total constraint
violations are at most

(28) $\begin{split}{Vio}_{k}&\leq
max\\{\sum_{i=0}^{N}{C\sqrt{{2}^{i}}},\sum_{i=0}^{N}{C{\Delta}_{g}^{i}}\\}=max\\{\frac{C}{\sqrt{2}-1}[{\sqrt{2}}^{N+1}-1],C{V}_{\bm{g}}\\}\\\
&\leq
max\\{\frac{2C}{\sqrt{2}-1}{\sqrt{2}}^{{log}_{2}T},C{V}_{\bm{g}}\\}=max\\{\frac{2C}{\sqrt{2}-1}\sqrt{T},D{V}_{\bm{g}}\\},\forall
k=1,2,...,K.\end{split}$

For the Case 2, we conducting similar analysis as Case 1. By Theorem 1, in the
_i_ -th epoch there exists a constant _D_ such that the dynamic regret and
constraint violations are at most $D\sqrt{T{\Delta}_{x}^{i}}$ and
$max\\{D{2}^{\frac{3}{4}i},D{\Delta}_{g}^{i}\\}$ respectively. According to
(27), the total regret is still at most the order of $\sqrt{T{V}_{x}}$ without
changing. For the total constraint violations, we also have

(29) $\begin{split}{Vio}_{k}&\leq
max\\{D\sum_{i=0}^{N}{{2}^{\frac{3}{4}i}},\sum_{i=0}^{N}{D{\Delta}_{g}^{i}}\\}\leq
max\\{\frac{D}{{2}^{3/4}-1}({2}^{\frac{3}{4}\lceil{log}_{2}T\rceil}-1),D{V}_{\bm{g}}\\}\\\
&\leq
max\\{\frac{2D}{{2}^{3/4}-1}{2}^{\frac{3}{4}{log}_{2}T},D{V}_{\bm{g}}\\}=max\\{\frac{2D}{{2}^{3/4}-1}{T}^{3/4},D{V}_{\bm{g}}\\},\forall
k=1,2,...,K.\end{split}$

This completes the proof.

##  5\. Numerical experiments

In this section, we conduct numerical experiments to validate the theoretical
performance of our algorithm. Specifically, we consider the online ridge
regression (ORR) problem (Arce and Salinas, 2012) as the numerical example. We
compare the time-averaged regrets and constraint violations of our algorithm
with previous work in two different dynamic environments. The problem
formulation of ORR at round $t$ is as follows.

(30)
$\begin{split}&\underset{{x}_{t}\in\chi}{\text{Minimize}}\sum_{i=1}^{n}{({x}_{t}^{T}{p}_{i,t}+{b}-{q}_{i,t}{)}^{2}}\\\
&\quad\quad\quad\;s.t.\quad||{x}_{t}||\leq{a}_{t}\end{split}$

Here $\\{{p}_{i,t},{q}_{i,t}{\\}}_{i=1}^{n}$ are the training data at round
$t$ and ${a}_{t}$ characterizes the $t$-th round constraint on the ${l}_{2}$
norm of the decision variable, i.e., weight vector. We define
$\\{x|||x{||}_{\infty}\leq C,x\in{R}^{k}\\}$ as the feasible set. The above
ORR formulation could be applied in accurate and reliable forecasting of
traffic in intelligent transportation systems (Haworth et al., 2014). The
training data $\\{{p}_{i,t},{q}_{i,t}{\\}}_{i=1}^{n}$ and constraint ${a}_{t}$
may not be known prior to the agent at round $t$ due to the delayed arrival
training data.

Experimental setting. At round $t$, we generate the parameters
$\\{{p}_{i,t},{q}_{i,t},\forall i\\}$, ${a}_{t}$ and the per-slot minimizer
${x}_{t}^{*}$ in the following way. Let
${x}_{t}^{*}={\Pi}_{\chi}({x}_{t-1}^{*}+{\tau}_{t})$, where each entry of
${\tau}_{t}$ is a uniform random variable, sampled from a time-varying set
${B}_{t}$ (We will specialize it later). Then we generate ${a}_{t}$ and
$\\{{p}_{i,t},{q}_{i,t}{\\}}_{i=1}^{n}$ as follows. i)
${p}_{i,t}={p}_{i,t-1}+{u}_{i,t}$, where each entry of ${u}_{i,t}$ is i.i.d,
uniformly sampled from set ${B}_{t}$. ii)
${q}_{i,t}={p}_{i,t}^{T}{x}_{t}^{*}+b$. iii) ${a}_{t}=||{x}_{t}^{*}||$.

Next, we introduce the baslines (Chen et al., 2017, 2018; Cao and Liu, 2018;
Chen and Giannakis, 2019) for comparison. The algorithms in (Chen et al.,
2017, 2018) are based on MOSP method. Although (Chen and Giannakis, 2019) only
considered the bandit setting, their algorithm and theoretical guarantees are
also valid in the full-information setting. Meanwhile, note that the
theoretical guarantees in (Cao and Liu, 2018) are valid only when the agent
has prior knowledge of ${V}_{x}$ (or the order of it). For fair comparison, we
set the learning rates in their algorithm to be parameter-free, and obtain the
$O({V}_{x}{T}^{1/2})$ regret and
$O(\max\\{{V}_{x}^{1/2}{T}^{1/2},{T}^{3/4}\\})$ constraint violations.
Finally, we introduce our experimental details. In our experiment, we let
$n=k=5,\;C=7$. The parameters of our algorithm and other baselines are
presented in Table 2.

Table 2. Parameters of our algorithm and baselines Methods | Parameters
---|---
Baseline (Cao and Liu, 2018) |  $\delta=8n{C}^{2}+1,\;\eta=\frac{2}{\sqrt{T}}$
Baseline (Chen et al., 2017) |  $\alpha=\mu={T}^{\frac{1}{3}}$
Baseline (Chen et al., 2018) |  $\delta=1$, ${\lambda}_{1}=4\sqrt{2}{T}^{\frac{1}{8}}$
Baseline (Chen and Giannakis, 2019) |  $\mu={T}^{-\frac{1}{2}},\;\alpha=2{T}^{-\frac{1}{2}}$
VQB(Case 1) |  ${\alpha}_{t}=\sqrt{\frac{T}{R+\sum_{i\leq t}{||{x}_{i}^{*}-{x}_{i-1}^{*}{||}}}}$, ${\gamma}_{t}^{2}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}$
VQB(Case 2) |  ${\alpha}_{t}=\sqrt{\frac{T}{R+\sum_{i\leq t}{||{x}_{i}^{*}-{x}_{i-1}^{*}{||}}}}$, ${\gamma}_{t}^{2}=\frac{1}{2{\beta}^{2}}\frac{1}{\sqrt{2R}}\frac{1}{\sqrt{t+1}}$

Results and analysis. We first consider the case when
${V}_{x}={V}_{\bm{g}}=O(\log(T))$. To do this, we set ${B}_{t}$ to be
$[-\frac{1}{2t},\frac{1}{2t}]$. From figure 1(a) and (b), we can see that our
algorithm VQB achieves lowest time-averaged regret $\frac{regret(t)}{t}$ and
constraint violation $\frac{Vio(t)}{t}$, which validates our theoretical
results. Moreover, we can also see that the regrets achieved by VQB under two
parameter settings are very close, which is consistent with the theoretical
results in Theorem 1 that the regret upper bounds between them are identical
by noting that ${V}_{\bm{g}}=O(\log(T))$.

Figure 1. (a) Evolutions of $Regret(t)/t$; (b) Evolations of $Vio(t)/t$.

Figure 2. (a) Evolutions of $Regret(t)/t$; (b) Evolations of $Vio(t)/t$.

We also consider the case when ${V}_{x}={V}_{\bm{g}}=O(\sqrt{T})$. To do this,
we set ${B}_{t}$ to be $[-\frac{1}{2\sqrt{t}},\frac{1}{2\sqrt{t}}]$. In this
case, the regret bounds of all baselines are at least the order of $T$. From
Figure 2, we notice that all methods can guarantee sublinear constraint
violation in this case, which matches the theoretical results listed in Table
1. Figure 2 also shows that VQB can achieve simultaneous sublinear regret and
constraint violation, while other baselines ((Chen et al., 2017, 2018; Chen
and Giannakis, 2019)) cannot, which matches their theoretical results. We
observe that baseline (Cao and Liu, 2018) achieves a near sublinear regret in
this setting, yet this may not always be the case due to its $O(T)$ regret
bound, or the performance bounds established by (Cao and Liu, 2018) may not be
tight. Besides, the regrets of the VQB are better, which also coincides our
theoretical bounds in this case.

##  6\. Applications

In this section, we show several applications of our formulation to diverse
problems across resource allocation and job scheduling. We emphasize that none
of these applications would be possible without a simultaneously achieving
sublinear regret and constraint violations algorithm, which has not been
attainable with previous approaches.

Figure 3. The overview of the system.

###  6.1. Online Network Resource Allocation

Within this subsection, we consider an online resource allocation problem over
a cloud network (Chen et al., 2016, 2017). The network consists of mapping
nodes $\mathcal{J}=\\{1,...,J\\}$ and data centers
$\mathcal{K}=\\{1,...,K\\}$. We use a directed graph
$\mathcal{G}=(\mathcal{I},\mathcal{\epsilon})$ to represent it, where
$\mathcal{I}=\mathcal{J}\cup\mathcal{K}$, $|\mathcal{I}|=J+K$, and
$|\mathcal{\epsilon}|=E$. $\mathcal{\epsilon}$ includes all the links which
connect mapping nodes with data centers, and the ”virtual” exogenous edges
coming out of the data centers. At each time slot $t$, each mapping node $j$
receives a data request ${b}_{t}^{j}$ from exogenous user, and schedules
${x}_{t}^{jk}$ workload to data center $k$. Each data center $k$ serves
workload ${y}_{t}^{k}$ based on its source availability. We assume each node
(including data center and mapping node) could buffer the unserved workloads
into its local queue. Next we describe the workflow of the overall system,
which is illustrated in Figure 3. Specifically, at each time slot $t$, mapping
node $j$ has an exogenous workload ${b}_{t}^{j}$ plus that stored in its local
queue ${q}_{t}^{j}$, then it schedules workload ${x}_{t}^{jk}$ to data center
$k$. Data center $k$ has a received workload of the amount of
$\sum_{j=1}^{J}{{x}_{t}^{jk}}$ plus that stored in its local queue
${q}_{t}^{J+k}$, and serves an amount of workload ${y}_{t}^{k}$.

We define a resource allocation vector
${\bm{x}}_{t}=[{x}_{t}^{11},...,{x}_{t}^{JK},{y}_{t}^{1},...,{y}_{t}^{K}{]}^{T}\in{R}_{+}^{E}$,
and load arrival vector
${\bm{b}}_{t}=[{b}_{t}^{1},...,{b}_{t}^{J},0,...,0{]}^{T}$ $\in{R}_{+}^{I}$ to
represent the exogenous load arrival rates of all nodes at time slot $t$. We
also define $I\times E$ node-incidence matrix $\bm{A}$, where $(i,j)$-th entry
${\bm{A}}_{(i,j)}=1$ if link $j$ enters node $i$, or ${\bm{A}}_{(i,j)}=-1$ if
link $j$ leaves node $i$, otherwise ${\bm{A}}_{(i,j)}=0$. Hence the vector
$\bm{A}{\bm{x}}_{t}+{\bm{b}}_{t}$ represents the aggregate workloads of all
nodes. There is service residual at node $i$ if
$(\bm{A}{\bm{x}}_{t}+{\bm{b}}_{t}{)}_{i}>0$, otherwise the current load of
node $i$ exceeds its service capacity. At each time slot $t$, the queue length
vector of all nodes is given by
${\bm{q}}_{t}=[{q}_{t}^{1},...,{q}_{t}^{J+K}{]}^{T}$, and its update rule of
${\bm{q}}_{t}$ is
${\bm{q}}_{t+1}=({\bm{q}}_{t}+\bm{A}{\bm{x}}_{t}+{\bm{b}}_{t}{)}^{+}$. We
denote ${B}_{jk}$ be the maximum bandwidth of link $(j,k)$, and ${C}_{k}$ be
the resource capacity of data center $k$. Thus the feasible set is
$\chi=\\{x|0\leq x\leq c\\}$, where
$c=[{B}_{11},...,{B}_{JK},{C}_{1},...,{C}_{K}]$.

Here we formulate the accumulated cost of the overall system. We divide it
into two parts, the one is power cost, the other is bandwidth cost. The power
cost characterizes the energy price and renewable generation, and the
bandwidth cost characterizes the transmission delay. The power cost of each
data center $k$ at time slot $t$ is ${f}_{t,k}({y}_{t}^{k})$. The bandwidth
cost of link $(j,k)$ is ${f}_{t,jk}({x}_{t}^{jk})$. Both of them are unknown
before the resource allocation at time slot $t$. Hence at each time slot $t$,
the instantaneous cost of the overall system is

(31)
${f}_{t}({\bm{x}}_{t})=\sum_{k\in\mathcal{K}}{{f}_{t,k}({y}_{t}^{k})}+\sum_{j\in\mathcal{J}}{\sum_{k\in\mathcal{K}}{{f}_{t,jk}({x}_{t}^{jk})}}$

Our goal is to minimize the accumulated cost of the overall system while
ensuring all workloads are served, shown in the following optimization problem
${\bm{P}}_{1}$:

(32)
$\begin{split}{\bm{P}}_{1}\bm{:}\quad&\min_{\\{{\bm{x}}_{t}\in\chi\\}}{\sum_{t=1}^{T}{{f}_{t}({x}_{t})}}\\\
&s.t.\quad{\bm{q}}_{t+1}=[{\bm{q}}_{t}+\bm{A}{\bm{x}}_{t}+{\bm{b}}_{t}{]}^{+},\forall
t,\\\ &\quad\quad\quad{\bm{q}}_{1}={\bm{q}}_{T+1}=0,\end{split}$

where the initial queue length is given by ${\bm{q}}_{1}$, and
${\bm{q}}_{T+1}=0$ implies that all workloads should be served before the end
of scheduling horizon $T$. However, solving ${P}_{1}$ is generally challenging
using traditional methods since the future workload arrivals are not known a
prior. Therefore, we could relax the first constraint in ${\bm{P}}_{1}$ as
follows:

(33)
${\bm{q}}_{T+1}\geq{\bm{q}}_{T}+\bm{A}{\bm{x}}_{T}+{\bm{b}}_{T}\geq...\geq{\bm{q}}_{1}+\sum_{t=1}^{T}{(\bm{A}{\bm{x}}_{t}+{\bm{b}}_{t})}\Rightarrow\sum_{t=1}^{T}{(\bm{A}{\bm{x}}_{t}+{\bm{b}}_{t})}\leq{\bm{q}}_{T+1}-{\bm{q}}_{1}=0$

Then we transform ${\bm{P}}_{1}$ into the following optimization problem
${\bm{P}}_{2}$:

(34)
${\bm{P}}_{2}\bm{:}\quad\min_{\\{{x}_{t}\in\chi\\}}{\sum_{t=1}^{T}{{f}_{t}({x}_{t})}}\quad
s.t.\quad\sum_{t=1}^{T}{(\bm{A}{x}_{t}+{\bm{b}}_{t})}\leq 0,$

which could be solved by our framework of OCO with long-term and time-varying
constraints.

###  6.2. Online Job Scheduling

Within this subsection, we consider an online job scheduling problem (Im et
al., 2016b, a; Liu et al., 2019), in which the computing cluster consists of
multiple servers with heterogeneous computation resources. Specifically,
consider a computing cluster, and it consists of $M$ servers, which indexed
from $1$ to $M$. We assume server $i$ has ${C}_{i}$ CPU cores and can process
multiple jobs simultaneously unless the total demand of its execution jobs
exceeds ${C}_{i}$. Time is slotted and job $j$ arrives the cluster at time
slot ${a}_{j}$. The total number of jobs is $N$. Each incoming job joins a
global queue managed by a scheduler, waiting to be assigned to an available
server(s) for execution in the subsequent time slots. At the beginning of each
time slot, the scheduler has to decide which job(s) to schedule and which
sever(s) assigned to it(them). We assume job $j$ requires ${d}_{j}$ CPU cores
to run and ${p}_{j}$ units of time to finish when its demand of ${d}_{j}$ CPU
cores are fully satisfied, where both ${d}_{j}$ and ${p}_{j}$ are integers and
will be reported to the scheduler once job $j$ arrives at the cluster. Thus
the quantity ${v}_{j}={p}_{j}{d}_{j}$ is the volume of job $j$. We also assume
that preemption and migration are allowed, i.e., a running job can be check-
pointed, preempted, and then recovered on the same server or on a different
server.

We denote ${u}_{j}^{i}(t)$ be the number of CPU cores allocated to job $j$ on
server $i$ at time-slot $t$. By time-division-multiplexing of CPU cores, any
job could also be processed even if it is allocated fewer than ${d}_{j}$ CPU
cores, but it needs to take more than ${p}_{j}$ time-slots to finish. We say
job $j$ finishes when its completion time ${c}_{j}$ satisfies
$\sum_{t={a}_{j}+1}^{{c}_{j}}{\sum_{i=1}^{M}{{u}_{j}^{i}(t)}}\geq{d}_{j}{p}_{j}$,
that is, its volume is fully served, and the flowtime of job $j$ is
${c}_{j}-{a}_{j}$. We assume that any job $j$ cannot benefit from the extra
number of cores (i.e., it is allocated more than ${d}_{j}$ cores). To avoid
the waste of resources, we have $\sum_{i=1}^{M}{{u}_{j}^{i}(t)}\leq{d}_{j}$.
The online scheduler strikes a balance between fairness and job latency.
Hence, like (Liu et al., 2019), we adopt the ${l}_{k}$ norm of job flowtime
(Liu et al., 2019) to represent job’s ”cost”. Then our goal is to minimize the
sum of ${l}_{k}$ norm of all jobs’ flowtime while satisfying some constraints,
shown in the following optimization problem ${\bm{P}}_{3}$:

(35)
$\begin{split}{\bm{P}}_{3}\bm{:}\quad&\min_{\\{{u}_{j}^{i}(t)\\}}{\sum_{j=1}^{N}{({c}_{j}-{a}_{j}{)}^{k}}}\\\
&s.t.\quad\sum_{t={a}_{j}+1}^{{c}_{j}}{\sum_{i=1}^{M}{{u}_{j}^{i}(t)}}\geq{d}_{j}{p}_{j},\forall
j,\\\ &\quad\quad\sum_{i}{{u}_{j}^{i}(t)}\leq{d}_{j},\forall j,t,\\\
\quad\quad&\quad\quad\sum_{j:t>{a}_{j}}{{u}_{j}^{i}(t)}\leq{C}_{i},\forall
i,t,\\\ &\quad\quad\;{u}_{j}^{i}(t)\in N,\end{split}$

where the third constraint means the total number of allocated CPU cores on
server $i$ cannot exceed its capacity ${C}_{i}$ at any time slot. However, it
can be verified that ${\bm{P}}_{3}$ is NP-hard since it is an integer
programming problem. Hence here we could adopt the approximation algorithm to
solve ${\bm{P}}_{3}$. Specifically, we approximate ${l}_{k}$ norm of flowtime
$({c}_{j}-{a}_{j}{)}^{k}$ with its fractional job flowtime counterpart (Im et
al., 2015), that is,

$({c}_{j}-{a}_{j}{)}^{k}\approx\sum_{t={a}_{j}+1}{\sum_{i=1}^{M}{{({(t-{a}_{j}{)}^{k}}/{{p}_{j}}+{p}_{j}^{k-1}){u}_{j}^{i}(t)}/{{d}_{j}}}}.$

We define ${y}_{j}(t)={\sum_{i}{{u}_{j}^{i}(t)}}/{{d}_{j}(t)}$ be the total
CPU cores rates allocated to job $j$ at time slot $t$. We could transform
${\bm{P}}_{3}$ into the following optimization problem ${\bm{P}}_{4}$:

$\displaystyle\begin{split}{\bm{P}}_{4}\bm{:}\quad\min_{\\{{u}_{j}^{i}(t)\\}}{\sum_{t=1}\sum_{j:t\geq{a}_{j}+1}{({(t-{a}_{j}{)}^{k}}/{{p}_{j}}+{p}_{j}^{k-1}){y}_{j}(t)}}\end{split}$
(36)
$\displaystyle\begin{split}&s.t.\quad\sum_{t={a}_{j}+1}{{y}_{j}(t)}\geq{p}_{j},\forall
j,\\\ &\quad\quad\quad 0\leq{y}_{j}(t)\leq 1,\forall j,t,\\\
&\quad\quad\quad\sum_{j:t>{a}_{j}}{{d}_{j}{y}_{j}(t)}\leq\sum_{i=1}^{M}{{C}_{i}},\forall
t,\\\ &\quad\quad\quad{d}_{j}{y}_{j}(t)\in N,\forall j,t.\end{split}$

We denote by ${OPT}_{{\bm{P}}_{3}}^{*}$ and ${OPT}_{{\bm{P}}_{4}}^{*}$ the
optimal objective values of optimization problem ${\bm{P}}_{3}$ and
${\bm{P}}_{4}$ respectively, then by using the same argument as (Im et al.,
2015), we have ${OPT}_{{\bm{P}}_{4}}^{*}\leq 2{OPT}_{{\bm{P}}_{3}}^{*}$. Next
we show that we could use the framework of OCO with long-term and time-varying
constraints to solve problem ${\bm{P}}_{4}$.

Solve ${\bm{P}}_{4}$ using the framework of OCO with long-term and time-
varying constraints. We formulate the third constraint in ${\bm{P}}_{4}$ as
the short-term constraint which needs to be satisfied strictly at each time
slot. We also notice that the first constraint could be formulated as the
long-term constraint. Thus, we separate the first constraint in ${\bm{P}}_{4}$
into each time slot constraint:

(37) ${g}_{t,j}({y}_{j}(t))=\frac{{p}_{j}}{T-{a}_{j}}-{y}_{j}(t)\leq 0,$

where $T$ is the predicted completion time for all jobs, which could be known
or estimated ahead of time in many scenarios. The per time slot constraint
(37) could be violated in some time slots but the accumulated constraint
violations should be controlled. We relax the integer constraint of
${y}_{j}(t)$ and define the feasible set of it as:

$\chi(t)=\\{\bm{y}|\sum_{j:t>{a}_{j}}{{d}_{j}{y}_{j}}\leq\sum_{i=1}^{M}{{C}_{i}},0\leq{y}_{j}\leq
1.\\}.$

Indeed, we could still make the resultant online algorithm satisfies the
integer constraint in the sequel. Therefore, the optimization problem
${\bm{P}}_{4}$ could be transformed into the following optimization problem
${\bm{P}}_{5}$:

(38)
$\begin{split}{\bm{P}}_{5}\bm{:}\quad&\min_{\bm{y}(t)\in\chi(t)}{{f}_{t}(\bm{y}(t))=\sum_{t=1}^{T}\sum_{j:t\geq{a}_{j}+1}{({(t-{a}_{j}{)}^{k}}/{{p}_{j}}+{p}_{j}^{k-1}){y}_{j}(t)}}\\\
&\quad s.t.\quad\sum_{t={a}_{j}+1}^{T}{{g}_{t,j}({y}_{j}(t))}\leq 0,\forall
j,\end{split}$

which could be solved by our framework of OCO with long-term and time-varying
constraints. As stated before, although feasible set $\chi$ is a time-varying
set, our algorithm is valid and the corresponding theoretical results also
hold.

##  7\. Conclusion and future work

In this paper, we develop and analyze a novel algorithm for OCO with long term
and time-varying constraints. To the best of our knowledge, our algorithm is
the first parameter-free algorithm to simultaneously achieve sublinear dynamic
regret and violation under common assumptions. We then extend our algorithm
and analysis to some practical cases. For future work, It is a good direction
to investigate sharper performance bounds for OCO with long-term and time-
varying constraints. Moreover, whether incorporating other properties, like
strong convexity and smoothness, can lead to better performance bounds is also
an open question.

## References

  * (1)
  * Amiri (2019) Maryam Amiri. 2019\.  _Towards enhancing QoE for software defined networks based cloud gaming services_.  Ph.D. Dissertation. Université d’Ottawa/University of Ottawa.
  * Arce and Salinas (2012) Paola Arce and Luis Salinas. 2012.  Online ridge regression method using sliding windows. In _2012 31st International Conference of the Chilean Computer Science Society_. IEEE, 87–90.
  * Cao and Liu (2018) Xuanyu Cao and KJ Ray Liu. 2018.  Online convex optimization with time-varying constraints and bandit feedback.  _IEEE Trans. Automat. Control_ 64, 7 (2018), 2665–2680.
  * Chen and Giannakis (2019) Tianyi Chen and Georgios B Giannakis. 2019.  Bandit Convex Optimization for Scalable and Dynamic IoT Management.  _IEEE INTERNET OF THINGS JOURNAL_ 6, 1 (2019).
  * Chen et al. (2017) Tianyi Chen, Qing Ling, and Georgios B Giannakis. 2017\.  An Online Convex Optimization Approach to Proactive Network Resource Allocation.  _IEEE Transactions on Signal Processing_ 65, 24 (2017), 6350–6364.
  * Chen et al. (2018) Tianyi Chen, Qing Ling, Yanning Shen, and Georgios B Giannakis. 2018.  Heterogeneous Online Learning for “Thing-Adaptive” Fog Computing in IoT.  _IEEE Internet of Things Journal_ 5, 6 (2018), 4328–4341.
  * Chen et al. (2016) Tianyi Chen, Antonio G Marques, and Georgios B Giannakis. 2016\.  DGLB: Distributed stochastic geographical load balancing over cloud networks.  _IEEE Transactions on Parallel and Distributed Systems_ 28, 7 (2016), 1866–1880.
  * Fang et al. (2020) Huang Fang, Nicholas JA Harvey, Victor S Portella, and Michael P Friedlander. 2020.  Online mirror descent and dual averaging: keeping pace in the dynamic case.  _arXiv preprint arXiv:2006.02585_ (2020).
  * Haworth et al. (2014) James Haworth, John Shawe-Taylor, Tao Cheng, and Jiaqiu Wang. 2014.  Local online kernel ridge regression for forecasting of urban travel times.  _Transportation research part C: emerging technologies_ 46 (2014), 151–178.
  * Hazan (2019) Elad Hazan. 2019\.  Introduction to online convex optimization.  _arXiv preprint arXiv:1909.05207_ (2019).
  * Huang et al. (2014) Longbo Huang, Xin Liu, and Xiaohong Hao. 2014.  The power of online learning in stochastic network optimization. In _The 2014 ACM international conference on Measurement and modeling of computer systems_. 153–165.
  * Huang et al. (2012) Longbo Huang, Scott Moeller, Michael J Neely, and Bhaskar Krishnamachari. 2012.  LIFO-backpressure achieves near-optimal utility-delay tradeoff.  _IEEE/ACM Transactions On Networking_ 21, 3 (2012), 831–844.
  * Huang and Neely (2011) Longbo Huang and Michael J Neely. 2011.  Utility optimal scheduling in processing networks.  _Performance Evaluation_ 68, 11 (2011), 1002–1021.
  * Im et al. (2015) Sungjin Im, Janardhan Kulkarni, and Benjamin Moseley. 2015\.  Temporal fairness of round robin: Competitive analysis for lk-norms of flow time. In _Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures_. 155–160.
  * Im et al. (2016a) Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, and Kamesh Munagala. 2016a.  A competitive flow time algorithm for heterogeneous clusters under polytope constraints. In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * Im et al. (2016b) Sungjin Im, Mina Naghshnejad, and Mukesh Singhal. 2016b.  Scheduling jobs with non-uniform demands on multiple servers without interruption. In _IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications_. IEEE, 1–9.
  * Jenatton et al. (2016) Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. 2016\.  Adaptive algorithms for online convex optimization with long-term constraints. In _International Conference on Machine Learning_. 402–411.
  * Liu et al. (2019) Yang Liu, Huanle Xu, and Wing Cheong Lau. 2019.  Online job scheduling with resource packing on a cluster of heterogeneous servers. In _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 1441–1449.
  * Liu et al. (2014) Zhenhua Liu, Iris Liu, Steven Low, and Adam Wierman. 2014\.  Pricing data center demand response.  _ACM SIGMETRICS Performance Evaluation Review_ 42, 1 (2014), 111–123.
  * Mahdavi et al. (2012) Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. 2012.  Trading regret for efficiency: online convex optimization with long term constraints.  _The Journal of Machine Learning Research_ 13, 1 (2012), 2503–2528.
  * Qiu and Wei (2020) Shuang Qiu and Xiaohan Wei. 2020.  Beyond O($\sqrt{T}$) Regret for Constrained Online Optimization: Gradual Variations and Mirror Prox.  _arXiv preprint arXiv:2006.12455_ (2020).
  * Sharma et al. (2020) Pranay Sharma, Prashant Khanduri, Lixin Shen, Donald J Bucci Jr, and Pramod K Varshney. 2020.  On distributed online convex optimization with sublinear dynamic regret and fit.  _arXiv preprint arXiv:2001.03166_ (2020).
  * Xu et al. (2019) Huanle Xu, Yang Liu, Wing Cheong Lau, Jun Guo, and Alex Liu. 2019.  Efficient online resource allocation in heterogeneous clusters with machine variability. In _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 478–486.
  * Yi et al. (2020) Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl H Johansson. 2020\.  Distributed bandit online convex optimization with time-varying coupled inequality constraints.  _IEEE Trans. Automat. Control_ (2020).
  * Yu et al. (2017) Hao Yu, Michael Neely, and Xiaohan Wei. 2017.  Online convex optimization with stochastic constraints. In _Advances in Neural Information Processing Systems_. 1428–1438.
  * Yu and Neely (2020) Hao Yu and Michael J Neely. 2020.  A Low Complexity Algorithm with O($\sqrt{T}$) Regret and O(1) Constraint Violations for Online Convex Optimization with Long Term Constraints.  _Journal of Machine Learning Research_ 21, 1 (2020), 1–24.
  * Yuan and Lamperski (2018) Jianjun Yuan and Andrew Lamperski. 2018.  Online convex optimization for cumulative constraints. In _Advances in Neural Information Processing Systems_. 6137–6146.
  * Zhang ([n.d.]) Lijun Zhang. [n.d.].  Online Learning in Changing Environments.
  * Zhang et al. (2018) Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. 2018.  Adaptive online learning in dynamic environments. In _Advances in neural information processing systems_. 1323–1333.
  * Zhang et al. (2016) Ying Zhang, Mohammad H Hajiesmaili, Sinan Cai, Minghua Chen, and Qi Zhu. 2016.  Peak-aware online economic dispatching for microgrids.  _IEEE transactions on smart grid_ 9, 1 (2016), 323–335.
  * Zhao et al. (2020) Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. 2020\.  Dynamic regret of convex and smooth functions.  _Advances in Neural Information Processing Systems_ 33 (2020).
  * Zhao et al. (2018) Yawei Zhao, Shuang Qiu, and Ji Liu. 2018.  Proximal Online Gradient is Optimum for Dynamic Regret.  _arXiv preprint arXiv:1810.03594_ (2018).

##  Appendix A Proofs for Section 4.1

###  A.1. Preliminary Lemmas

###### Lemma 0.

For any $t\geq 1$, we have

(39) $\sum_{i=1}^{t}{\frac{1}{\sqrt{i}}}\leq 2\sqrt{t}-1$

###### Lemma 0.

(Proposition A.5 in (Fang et al., 2020)) Let $R>0$ and any real numbers
${x}_{1},{x}_{2},...,{x}_{T}\in[0,R]$, then we have

(40) $\sum_{t=1}^{T}{\frac{{x}_{t}}{\sqrt{R+\sum_{i<t}{{x}_{i}}}}}\leq
2\sqrt{\sum_{t=1}^{T}{{x}_{t}}}$

###  A.2. Proof of Lemma 1

_Proof._

  1. (1)

We prove the inequality (_1_) by induction. Assume
${\bm{\lambda}}(\tau)\geq\bm{0}$ holds for all $\tau\in\\{0,1,...,t\\}$, then
for $\forall k$ we consider two cases.
Case 1: If ${g}_{k,t}({x}_{t+1})\geq 0$, then we have

${\lambda}_{k}(t+1)=max\\{{\lambda}_{k}(t)+{\gamma}_{t}{g}_{k,t}({x}_{t+1}),-{\gamma}_{t}{g}_{k,t}({x}_{t+1})\\}\geq{\lambda}_{k}(t)+{\gamma}_{t}{g}_{k,t}({x}_{t+1})\geq
0$

Case 2: If ${g}_{k,t}({x}_{t+1})<0$, then we have

${\lambda}_{k}(t+1)=max\\{{\lambda}_{k}(t)+{\gamma}_{t}{g}_{k,t}({x}_{t+1}),-{\gamma}_{t}{g}_{k,t}({x}_{t+1})\\}\geq-{\gamma}_{t}{g}_{k,t}({x}_{t+1})\geq
0$

Thus ${\bm{\lambda}}(t)\geq\bm{0}$ holds for $\forall t$.

  2. (2)

Since
${\bm{\lambda}}(t)=max\\{{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}),-{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})\\}\geq-{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})$,
then we can derive that
${\bm{\lambda}}(t)+{{\gamma}_{t-1}\bm{g}}_{t-1}({x}_{t})\geq 0$, $\forall t$.

  3. (3)

It is obvious that (_3_) holds if $t=1$, then for $t\geq 2$ and $\forall k$ we
consider two cases.
Case 1: If ${g}_{k,t}({x}_{t+1})\geq 0$, then we have

${\lambda}_{k}(t)=max\\{{\lambda}_{k}(t-1)+{\gamma}_{t-1}{g}_{k,t-1}({x}_{t}),-{\gamma}_{t-1}{g}_{,t-1}({x}_{t})\\}$
$\geq{\lambda}_{k}(t-1)+{\gamma}_{t-1}{g}_{k,t-1}({x}_{t})\geq{\gamma}_{t-1}|{g}_{k,t-1}({x}_{t})|$

Case 2: If ${g}_{k,t}({x}_{t+1})<0$, then we have

${\lambda}_{k}(t)=max\\{{\lambda}_{k}(t-1)+{\gamma}_{t-1}{g}_{k,t-1}({x}_{t}),-{\gamma}_{t-1}{g}_{,t-1}({x}_{t})\\}\geq-{\gamma}_{t-1}{g}_{,t-1}({x}_{t})={\gamma}_{t-1}|{g}_{k,t-1}({x}_{t})|$

Thus we have
${\lambda}_{k}(t)\geq{\gamma}_{t-1}|{g}_{k,t-1}({x}_{t})|,\;\forall t$.
Squaring both sides and summing over $k$, we obtain
${||\bm{\lambda}}(t){||}^{2}\geq{{\gamma}_{t-1}^{2}||\bm{g}}_{t-1}({x}_{t}){||}^{2}$,
which is equivalent to the inequality (_3_).

  4. (4)

Since
${\bm{\lambda}}(t)=max\\{{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}),-{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})\\}\geq{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})$,
then we have
${{\gamma}_{t-1}\bm{g}}_{t-1}({x}_{t})\leq{\bm{\lambda}}(t)-{\bm{\lambda}}(t-1)$.
Furthermore,

${\lambda}_{k}(t)=max\\{{\lambda}_{k}(t-1)+{\gamma}_{t-1}{g}_{k,t-1}({x}_{t}),-{\gamma}_{t-1}{g}_{,t-1}({x}_{t})\\}$
$\leq|{\lambda}_{k}(t-1)|+|{\gamma}_{t-1}{g}_{k,t-1}({x}_{t})|={\lambda}_{k}(t-1)+{\gamma}_{t-1}|{g}_{k,t-1}({x}_{t})|$

Squaring both sides and summing over $k$, we obtain

$||{\bm{\lambda}}(t){||}^{2}\leq||{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t}){||}^{2}\Leftrightarrow||{\bm{\lambda}}(t)||\leq||{\bm{\lambda}}(t-1)+{\gamma}_{t-1}{\bm{g}}_{t-1}({x}_{t})||$

By the triangle inequality we have
${||\bm{\lambda}}(t){||}{\leq{\gamma}_{t-1}||\bm{g}}_{t-1}({x}_{t}){||}+{||\bm{\lambda}}(t-1){||}$.

  5. (5)

According to the above inequality
${||\bm{\lambda}}(t){||}{\leq{\gamma}_{t-1}||\bm{g}}_{t-1}({x}_{t}){||}+{||\bm{\lambda}}(t-1){||}$
, we have

${||\bm{\lambda}}(t+1){||}{\leq{\gamma}_{t}||\bm{g}}_{t}({x}_{t+1}){||}+{||\bm{\lambda}}(t){||}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$
$\Rightarrow||{\bm{\lambda}}(t+1){||}^{2}\leq||{\bm{\lambda}}(t){||}^{2}+2{\gamma}_{t}[{\bm{\lambda}}(t){]}^{T}{\bm{g}}_{t}({x}_{t+1})+{\gamma}_{t}^{2}||{\bm{g}}_{t}({x}_{t+1}){||}^{2}$

Rearranging terms yields the inequality (_5_).

###  A.3. Proof of Lemma 2

_Proof._ Since
${\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+[{\bm{\lambda}}(t)+{\gamma}_{t-1}{{\bm{g}}}_{t-1}({x}_{t}){]}^{T}({\gamma}_{t}{{\bm{g}}}_{t}(x))+{\alpha}_{t}||x-{x}_{t}{||}^{2}$
is a $2{\alpha}_{t}$-strong convex function with respect to _x_ and
${x}_{t+1}$ minimizes this expression over $\chi$, we have

(41)
$\begin{split}&{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})+[{\bm{\lambda}}(t)+{\gamma}_{t-1}{{\bm{g}}}_{t-1}({x}_{t}){]}^{T}({\gamma}_{t}{{\bm{g}}}_{t}({x}_{t+1}))+{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\leq{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t}^{*}-{x}_{t})+[{\bm{\lambda}}(t)+{\gamma}_{t-1}{{\bm{g}}}_{t-1}({x}_{t}){]}^{T}({\gamma}_{t}{{\bm{g}}}_{t}({x}_{t}^{*}))+{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\\\
&\overset{(a)}{\leq}{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t}^{*}-{x}_{t})+{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\end{split}$

Where (a) follows from the fact that ${\bm{g}}_{t}({x}_{t}^{*})\leq 0$ and
Lemma 2. Adding ${f}_{t}({x}_{t})$ on both sides of
(LABEL:convexity_analysis_1) and using the convexity of ${f}_{t}$, we have

(42)
$\begin{split}&{f}_{t}({x}_{t})+{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})+[{\bm{\lambda}}(t)+{\gamma}_{t-1}{{\bm{g}}}_{t-1}({x}_{t}){]}^{T}({\gamma}_{t}{{\bm{g}}}_{t}({x}_{t+1}))+{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\leq{{f}_{t}({x}_{t})+\nabla{f}_{t}({x}_{t})}^{T}({x}_{t}^{*}-{x}_{t})+{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\\\
&\leq{f}_{t}({x}_{t}^{*})+{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\end{split}$

Rearranging terms in (LABEL:1_proof_of_lemma_1), we have

(43)
$\begin{split}&{f}_{t}({x}_{t})+[{\bm{\lambda}}(t)]^{T}({\gamma}_{t}{\bm{g}}_{t}({x}_{t+1}))-{f}_{t}({x}_{t}^{*})\\\
&\leq{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}_{t-1}{\gamma}_{t}[{\bm{g}}_{t-1}({x}_{t}){]}^{T}{\bm{g}}_{t}({x}_{t+1})-{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})\\\
&\overset{(a)}{\leq}{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}_{t-1}{\gamma}_{t}[{\bm{g}}_{t-1}({x}_{t}){]}^{T}{\bm{g}}_{t}({x}_{t+1})+||{\nabla{f}_{t}({x}_{t})}{||}||{x}_{t+1}-{x}_{t}{||}\\\
&\overset{(b)}{\leq}{{\alpha}_{t}}||{x}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}_{t-1}{\gamma}_{t}[{\bm{g}}_{t-1}({x}_{t}){]}^{T}{\bm{g}}_{t}({x}_{t+1})+\frac{1}{2\delta}||\nabla{f}_{t}({x}_{t}){||}^{2}+\frac{\delta}{2}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\overset{(c)}{\leq}{{\alpha}_{t}}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{{\alpha}_{t}}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{\alpha}_{t}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}_{t-1}{\gamma}_{t}[{\bm{g}}_{t-1}({x}_{t}){]}^{T}{\bm{g}}_{t}({x}_{t+1})+\frac{1}{2\delta}{G}^{2}+\frac{\delta}{2}||{x}_{t+1}-{x}_{t}{||}^{2}\end{split}$

Where (a) holds by the Cauchy-Schwarz inequality; (b) comes from the AM–GM
inequality; (c) holds due to the Assumption 1. Based on Assumption 1, we note
that

(44)
$\begin{split}&||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t}^{*}||}^{2}=||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t+1}^{*}+{x}_{t+1}^{*}-{x}_{t}^{*}||}^{2}\\\
&\leq||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}-||{{x}_{t+1}^{*}-{x}_{t}^{*}||}^{2}-2||{x}_{t+1}{-{x}_{t+1}^{*}{||}||{x}_{t+1}^{*}-{x}_{t}^{*}||}\\\
&\leq||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{||{x}_{t+1}^{*}-{x}_{t}^{*}||}\end{split}$

And

(45)
$\begin{split}&-[{{\bm{g}}}_{t-1}({x}_{t}){]}^{T}{{\bm{g}}}_{t}({x}_{t+1})=-\frac{1}{2}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+\frac{1}{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}\\\
&=-\frac{1}{2}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+\frac{1}{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t})+{{\bm{g}}}_{t}({x}_{t})-{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}\\\
&\overset{(a)}{\leq}-\frac{1}{2}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+\frac{1}{2}[2||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}+2||{{\bm{g}}}_{t}({x}_{t})-{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}]\\\
&\overset{(b)}{\leq}-\frac{1}{2}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}+{\beta}^{2}||{x}_{t+1}-{x}_{t}{||}^{2}\end{split}$

Where (a) follows from the AM-GM inequality; (b) holds by the Lipschitz
continuity of ${\bm{g}}_{t}$ (Assumption 1). Substituting
(LABEL:3_proof_of_lemma_1) and (LABEL:4_proof_of_lemma_1) into
(LABEL:2_proof_of_lemma_1) we obtain

(46)
$\begin{split}&{f}_{t}({x}_{t})+[{\bm{\lambda}}(t)]^{T}(\gamma{{\bm{g}}}_{t}({x}_{t+1}))-{f}_{t}({x}_{t}^{*})\\\
&\leq{\alpha}_{t}[||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+({\beta}^{2}{\gamma}_{t}{\gamma}_{t-1}+\frac{\delta}{2}-{\alpha}_{t})||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&+\frac{1}{2\delta}{G}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+{\gamma}_{t-1}{\gamma}_{t}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}\\\
&\overset{(a)}{\leq}{\alpha}_{t}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}_{t+1}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+({\beta}^{2}{\gamma}_{t-1}+\frac{\delta}{2}-{\alpha}_{t})||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&+\frac{1}{2\delta}{G}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}\end{split}$

Where (a) comes from the fact that both $\\{{\alpha}_{t}\\}$ and
$\\{{\gamma}_{t}\\}$ are non-increasing sequence. According to Lemma 2 and
adding Lyapunov drift term on both sides of (LABEL:5_proof_of_lemma_1) yields:

(47) $\begin{split}&{f}_{t}({x}_{t})+\Delta(t)-{f}_{t}({x}_{t}^{*})\\\
&\leq{\alpha}_{t}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}_{t+1}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+({\beta}^{2}{\gamma}_{t-1}+\frac{\delta}{2}-{\alpha}_{t})||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&+\frac{1}{2\delta}{G}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{\bm{g}}}_{t-1}({x}_{t}){||}^{2}+({\gamma}_{t}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t})||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}\\\
&\overset{(a)}{\leq}{\alpha}_{t}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}_{t+1}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+({\beta}^{2}{\gamma}_{t-1}+\frac{\delta}{2}-{\alpha}_{t})||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&+\frac{1}{2\delta}{G}^{2}-\frac{1}{2}{\gamma}_{t-1}{\gamma}_{t}||{{{g}}}_{t-1}({x}_{t}){||}^{2}+\frac{1}{2}{\gamma}_{t}{\gamma}_{t+1}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}\end{split}$

Where (a) is due to the fact that
$2{\gamma}_{t}\leq{\gamma}_{t-1}+{\gamma}_{t+1}$. This completes the proof.

###  A.4. Proof of Lemma 3

_Proof._ According to Lemma 1, taking a telescoping sum over $t=1,...,T$, we
obtain

(48)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}+\sum_{t=1}^{T}{\Delta(t)}\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+4R\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+{\alpha}_{1}||{x}_{1}^{*}-{x}_{1}{||}^{2}+\frac{T{G}^{2}}{2\delta}\\\
&+\frac{1}{2}{\gamma}_{T}{\gamma}_{T+1}||{{\bm{g}}}_{T}({x}_{T+1}){||}^{2}+\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}^{2}}+\sum_{t=1}^{T}{({\beta}^{2}{\gamma}_{t-1}^{2}+\frac{\delta}{2}-{\alpha}_{t})||{x}_{t+1}-{x}_{t}{||}^{2}}\\\
&\overset{(a)}{\leq}\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+4R\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+{\alpha}_{1}{R}^{2}+\frac{T{G}^{2}}{2\delta}\\\
&+\frac{1}{2}{\gamma}_{T}{\gamma}_{T+1}||{{\bm{g}}}_{T}({x}_{T+1}){||}^{2}+2F\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}\end{split}$

Where (a) holds by the Assumption 1 and the fact that
${\alpha}_{t}\geq{\beta}^{2}{\gamma}^{2}+\frac{\delta}{2}$. Rearranging terms
yields:

(49)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+4R\sum_{t=1}^{T}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+{\alpha}_{1}{R}^{2}+\frac{T{G}^{2}}{2\delta}\\\
&+\frac{1}{2}{\gamma}_{T}{\gamma}_{T+1}||{{{g}}}_{T}({x}_{T+1}){||}^{2}+2F\sum_{t=1}^{T}{{\gamma}_{t-1}^{2}||{{{g}}}_{t-1}({x}_{t})-{{{g}}}_{t}({x}_{t}){||}}+\frac{1}{2}||\lambda(1){||}^{2}\end{split}$

It completes the proof.

###  A.5. Proof of Lemma 4

_Proof._ According to Lemma 1, taking a telescoping sum over $t=1,...,T-1$ and
using the fact that
${\alpha}_{t}\geq{\beta}^{2}{\gamma}_{t-1}^{2}+\frac{\delta}{2}$, we obtain

(50)
$\begin{split}&\sum_{t=1}^{T-1}{{f}_{t}({x}_{t})}+\sum_{t=1}^{T-1}{\Delta(t)}\leq\sum_{t=1}^{T-1}{{f}_{t}({x}_{t}^{*})}+4R\sum_{t=1}^{T-1}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+{\alpha}_{1}{R}^{2}\\\
&+\frac{(T-1){G}^{2}}{2\delta}+\frac{1}{2}{\gamma}_{T-1}{\gamma}_{T}||{{\bm{g}}}_{T-1}({x}_{T}){||}^{2}+2F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}\end{split}$

Rearranging terms and multiplying both sides by 2 yields:

(51) $\begin{split}&||\bm{\lambda}(t){||}^{2}\leq
2(\sum_{t=1}^{T-1}{{f}_{t}({x}_{t}^{*})}-\sum_{t=1}^{T-1}{{f}_{t}({x}_{t})})+8R\sum_{t=1}^{T-1}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+2{\alpha}_{1}{R}^{2}\\\
&+\frac{(T-1){G}^{2}}{\delta}+{\gamma}_{T-1}{\gamma}_{T}||{{\bm{g}}}_{T-1}({x}_{T}){||}^{2}+4F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}\\\
&\overset{(a)}{\leq}2F(T-1)+8R\sum_{t=1}^{T-1}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}+2{\alpha}_{1}{R}^{2}+\frac{(T-1){G}^{2}}{\delta}\\\
&+{\gamma}_{T-1}^{2}||{{\bm{g}}}_{T-1}({x}_{T}){||}^{2}+4F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}\end{split}$

Where (a) holds by the Assumption 1 and the fact that
${\gamma}_{T}\leq{\gamma}_{T-1}$. Taking the square root of both sides and
using the fact that
$\sqrt{\sum_{i}{{a}_{i}}}\leq\sum_{i}{\sqrt{{a}_{i}}},\;\forall{a}_{i}\geq 0$,
we obtain

(52)
$\begin{split}&||\bm{\lambda}(t){||}\leq\sqrt{2F(T-1)}+2\sqrt{2R\sum_{t=1}^{T-1}{{\alpha}_{t}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}}}+\sqrt{2{\alpha}_{1}{R}^{2}}\\\
&+\sqrt{\frac{(T-1){G}^{2}}{\delta}}+{\gamma}_{T-1}||{{\bm{g}}}_{T-1}({x}_{T}){||}+2\sqrt{F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{\bm{g}}}_{t-1}({x}_{t})-{{\bm{g}}}_{t}({x}_{t}){||}}}\end{split}$

It completes the proof.

###  A.6. Proof of Lemma 5

_Proof._ According to Lemma 2, we have
${{\gamma}_{t-1}g}_{t-1,k}({x}_{t})\leq{\lambda}_{k}(t)-{\lambda}_{k}(t-1)\Leftrightarrow{g}_{t-1,k}({x}_{t})\leq\frac{{\lambda}_{k}(t)}{{\gamma}_{t-1}}-\frac{{\lambda}_{k}(t-1)}{{\gamma}_{t-1}}$.
Adding ${g}_{t,k}({x}_{t})$ on both sides of it and telescoping it over $t$
yields:

(53)
$\begin{split}&\sum_{t=1}^{T}{{g}_{t-1,k}({x}_{t})+{g}_{t,k}({x}_{t})}\leq\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}+\sum_{t=1}^{T}{\frac{{\lambda}_{k}(t)}{{\gamma}_{t-1}}-\frac{{\lambda}_{k}(t-1)}{{\gamma}_{t-1}}}\\\
&\overset{(a)}{\leq}\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}+\sum_{t=1}^{T}{\frac{{\lambda}_{k}(t)}{{\gamma}_{t}}-\frac{{\lambda}_{k}(t-1)}{{\gamma}_{t-1}}}\leq\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}+\frac{{\lambda}_{k}(T)}{{\gamma}_{T}}\\\
&\Rightarrow\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})-{g}_{t-1,k}({x}_{t})}+\frac{{\lambda}_{k}(T)}{{\gamma}_{T}}\\\
&\overset{(b)}{\leq}\sum_{t=1}^{T}{{max\\{|g}_{t,k}({x})-{g}_{t-1,k}({x})|\\}}+\frac{{\lambda}_{k}(T)}{{\gamma}_{T}}\overset{(c)}{\leq}\frac{||{\bm{\lambda}}(T)||}{{\gamma}_{T}}+{V}_{\bm{g}},\;\forall
k=1,2,...,K\end{split}$

Where (a) comes from the fact that ${\gamma}_{t}$ is non-increasing with
respect to $t$; (b) follows from the fact that
${|g}_{t,k}({x}_{t})-{g}_{t-1,k}({x}_{t})|\leq{max\\{|g}_{t,k}({x})-{g}_{t-1,k}({x})|\\}$;
(c) is due to the fact that
${|g}_{t,k}({x})-{g}_{t-1,k}({x})|\leq||{\bm{g}}_{t}(x)-{\bm{g}}_{t-1}(x){||}_{2}$
and ${\lambda}_{k}(T)\leq||{\bm{\lambda}}(T)||$. It completes the proof.

###  A.7. Proof of Lemma 6

_Proof._ Combining Lemma 4 with Lemma 5, we have

(54)
$\begin{split}&\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{||{{\bm{\lambda}}}(T)||}{{\gamma}_{T}}+{V}_{\bm{g}}\leq\frac{2}{{\gamma}_{T}}\sqrt{F(T-1)}+\frac{1}{{\gamma}_{T}}\sqrt{2{\alpha}_{1}{R}^{2}}+\frac{{\gamma}_{T-1}}{{\gamma}_{T}}||{{{\bm{g}}}}_{T-1}({x}_{T}){||}+\frac{G}{{\gamma}_{T}}\sqrt{\frac{T-1}{\delta}}\\\
&+\frac{2}{{\gamma}_{T}}\sqrt{2R\sum_{t=1}^{T-1}{{\alpha}_{t}||{x}_{t+1}^{*}-{x}_{t}^{*}{||}}}+\frac{2}{{\gamma}_{T}}\sqrt{F\sum_{t=1}^{T-1}{{\gamma}_{t-1}^{2}||{{{\bm{g}}}}_{t-1}({x}_{t})-{{{\bm{g}}}}_{t}({x}_{t}){||}}}+{V}_{\bm{g}}\end{split}$

It completes the proof.

##  Appendix B Proofs for Section 4.2

Note that both $\\{{\alpha}_{t}\\}$ and $\\{{\gamma}_{t}\\}$ are constant
sequences in Algorithm 2, thus here we omit the subscript $t$. We give the
complete proofs of all lemmas in section 4.2 in the following.

###  B.1. Proof of Lemma 8

_Proof._ We conduct a similar derivation process as the proof of Lemma 1, note
that
${\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+[{\bm{\lambda}}(t)+\gamma{{\bm{g}}}_{t}({x}_{t}){]}^{T}(\gamma{{\bm{g}}}_{t}(x))+{\alpha}||x-{x}_{t}{||}^{2}$
is a $2{\alpha}$-strong convex function with respect to _x_ and ${x}_{t+1}$
minimizes this expression over $\chi$, we have

(55)
$\begin{split}&{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})+[{\lambda}(t)+\gamma{{\bm{g}}}_{t}({x}_{t}){]}^{T}(\gamma{{\bm{g}}}_{t}({x}_{t+1}))+{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\leq{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t}^{*}-{x}_{t})+[{\lambda}(t)+\gamma{{\bm{g}}}_{t}({x}_{t}){]}^{T}(\gamma{{\bm{g}}}_{t}({x}_{t}^{*}))+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\\\
&\overset{(a)}{\leq}{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t}^{*}-{x}_{t})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\end{split}$

Where (a) follows from the fact that ${{g}}_{t}({x}_{t}^{*})\leq 0$ and Lemma
10. Next we add ${f}_{t}({x}_{t})$ on both sides of
(LABEL:1_proof_of_lemma_B_2_2) and use the convexity of ${f}_{t}$, then we
obtain

(56)
$\begin{split}&{f}_{t}({x}_{t})+{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})+[{\lambda}(t)+\gamma{{\bm{g}}}_{t}({x}_{t}){]}^{T}(\gamma{{\bm{g}}}_{t}({x}_{t+1}))+{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\leq{{f}_{t}({x}_{t})+\nabla{f}_{t}({x}_{t})}^{T}({x}_{t}^{*}-{x}_{t})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\\\
&\leq{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}\end{split}$

Rearranging terms in (LABEL:2_proof_of_lemma_B_2_2), we have

(57)
$\begin{split}&{f}_{t}({x}_{t})+[{\bm{\lambda}}(t)]^{T}(\gamma{{\bm{g}}}_{t}({x}_{t+1}))\\\
&\leq{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}^{2}[{{\bm{g}}}_{t}({x}_{t}){]}^{T}{{\bm{g}}}_{t}({x}_{t+1})-{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})\\\
&\overset{(a)}{\leq}{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}^{2}[{{\bm{g}}}_{t}({x}_{t}){]}^{T}{{\bm{g}}}_{t}({x}_{t+1})+||{\nabla{f}_{t}({x}_{t})}{||}||{x}_{t+1}-{x}_{t}{||}\\\
&\overset{(b)}{\leq}{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}^{2}[{{\bm{g}}}_{t}({x}_{t}){]}^{T}{{\bm{g}}}_{t}({x}_{t+1})\\\
&+\frac{1}{2\delta}||\nabla{f}_{t}({x}_{t}){||}^{2}+\frac{\delta}{2}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\overset{(c)}{\leq}{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}^{*}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}-{\gamma}^{2}[{{\bm{g}}}_{t}({x}_{t}){]}^{T}{{\bm{g}}}_{t}({x}_{t+1})\\\
&+\frac{1}{2\delta}{G}^{2}+\frac{\delta}{2}||{x}_{t+1}-{x}_{t}{||}^{2}\end{split}$

Where (a) holds by the Cauchy-Schwarz inequality; (b) comes from the AM–GM
inequality; (c) holds due to the Assumption 1. Recall that we have the
following inequality stated before,

(58)
$\begin{split}||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t}^{*}||}^{2}\leq||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{||{x}_{t+1}^{*}-{x}_{t}^{*}||}\end{split}$

Furthermore, we have

(59)
$\begin{split}-[{{\bm{g}}}_{t}({x}_{t}){]}^{T}{{\bm{g}}}_{t}({x}_{t+1})&=-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t}){||}^{2}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t})-{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}\\\
&\overset{(a)}{\leq}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t}){||}^{2}-\frac{1}{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}+\frac{1}{2}{\beta}^{2}||{x}_{t+1}-{x}_{t}{||}^{2}\end{split}$

Where (a) holds by the Lipschitz continuity of ${\bm{g}}_{t}$ (Assumption 1).
Substituting above two inequalities into (LABEL:3_proof_of_lemma_B_2_2) we
obtain

(60)
$\begin{split}&{f}_{t}({x}_{t})+[{{\bm{\lambda}}}(t)]^{T}(\gamma{{\bm{g}}}_{t}({x}_{t+1}))\\\
&\leq{f}_{t}({x}_{t}^{*})+{\alpha}_{t}[||{x}_{t}^{*}-{x}_{t}{||}^{2}-||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{||{x}_{t+1}^{*}-{x}_{t}^{*}||}]+(\frac{1}{2}{\beta}^{2}{\gamma}^{2}+\frac{\delta}{2}-{\alpha})||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&+\frac{1}{2\delta}{G}^{2}-\frac{1}{2}{\gamma}^{2}||{{\bm{g}}}_{t}({x}_{t}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}\\\
&\overset{(a)}{\leq}{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+\frac{1}{2\delta}{G}^{2}-\frac{1}{2}{\gamma}^{2}||{{\bm{g}}}_{t}({x}_{t}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{\bm{g}}}_{t}({x}_{t+1}){||}^{2}\end{split}$

Where (a) holds since
$\alpha\geq\frac{1}{2}{\beta}^{2}{\gamma}^{2}+\frac{1}{2}\delta$. Based on
Lemma 9, adding Lyapunov drift term on both sides of
(LABEL:6_proof_of_lemma_B_2_2) and rearranging terms yields:

(61) $\begin{split}&{f}_{t}({x}_{t})+\Delta(t)\\\
&\leq{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+\frac{1}{2\delta}{G}^{2}+\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t+1}({x}_{t+1}){||}^{2}\\\
&-\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t}({x}_{t+1}){||}^{2}+\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t+1}({x}_{t+1}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t}({x}_{t}){||}^{2}+\gamma[{{\bm{\lambda}}}(t)]^{T}({{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{\bm{g}}}}_{t}({x}_{t+1}))\\\
&\overset{(a)}{\leq}{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}+\frac{1}{2\delta}{G}^{2}\\\
&+{\gamma}^{2}F||{{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{{\bm{g}}}}_{t}({x}_{t+1})||}+\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t+1}({x}_{t+1}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t}({x}_{t}){||}^{2}+\gamma[{{\bm{\lambda}}}(t)]^{T}({{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{\bm{g}}}}_{t}({x}_{t+1}))\\\
&\overset{(b)}{\leq}{f}_{t}({x}_{t}^{*})+{\alpha}||{x}_{t}^{*}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}{-{x}_{t+1}^{*}||}^{2}+4R{\alpha}{||{x}_{t+1}^{*}-{x}_{t}^{*}||}^{2}+\frac{1}{2\delta}{G}^{2}\\\
&+{\gamma}^{2}F||{{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{{\bm{g}}}}_{t}({x}_{t+1})||}+\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t+1}({x}_{t+1}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{t}({x}_{t}){||}^{2}+\gamma||{{\bm{\lambda}}}(t){||}||{{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{\bm{g}}}}_{t}({x}_{t+1}){||}\end{split}$

Where (a) is due to
$||{{{{\bm{g}}}}}_{t-1}({x}_{t})-{{{{\bm{g}}}}}_{t}({{x}_{t}}){||}\leq 2F$;
(b) holds by the Cauchy-Schwarz inequality. It completes the proof.

###  B.2. proof of Lemma 9

_Proof._ According to Lemma 10, taking a telescoping sum over $t=1,...,T$, we
obtain

(62)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}+\sum_{t=1}^{T}{\Delta(t)}\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}||{x}_{1}^{*}-{x}_{1}{||}^{2}+4R\sum_{t=1}^{T}{{\alpha}||{x}_{t+1}^{*}-{x}_{t}^{*}{||}}\\\
&+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{\bm{g}}+\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{T+1}({x}_{T+1}){||}^{2}-\frac{1}{2}{\gamma}^{2}||{{{\bm{g}}}}_{1}({x}_{1}){||}^{2}+\gamma\sum_{t=1}^{T}{||{{\bm{\lambda}}}(t){||}||{{{\bm{g}}}}_{t+1}({x}_{t+1})-{{{\bm{g}}}}_{t}({x}_{t+1}){||}}\\\
&\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}||{x}_{1}^{*}-{x}_{1}{||}^{2}+4R\alpha{V}_{x}+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{\bm{g}}+\gamma\max_{t}{||{{\bm{\lambda}}}(t){||}}{V}_{\bm{g}}\end{split}$

Here we define ${\bm{g}}_{T+1}={\bm{g}}_{T}$, rearranging terms yields:

(63)
$\begin{split}&\sum_{t=1}^{T}{{f}_{t}({x}_{t})}\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}||{x}_{1}^{*}-{x}_{1}{||}^{2}+4R\alpha{V}_{x}+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{\bm{g}}+L(1)-L(T+1)+\gamma\max_{t}{||{{\bm{\lambda}}}(t){||}}{V}_{\bm{g}}\\\
&\leq\sum_{t=1}^{T}{{f}_{t}({x}_{t}^{*})}+{\alpha}||{x}_{1}^{*}-{x}_{1}{||}^{2}+4R\alpha{V}_{x}+\frac{T{G}^{2}}{2\delta}+{\gamma}^{2}F{V}_{\bm{g}}+\frac{1}{2}||\bm{\lambda}(1){||}^{2}+\gamma\max_{t}{||{{\bm{\lambda}}}(t){||}}{V}_{\bm{g}}\end{split}$

This completes the proof.

###  B.3. proof of Lemma 10

_Proof._ Recall that Lemma 9 implies that ${\gamma
g}_{t,k}({x}_{t})\leq{\lambda}_{k}(t)-{\lambda}_{k}(t-1),\;\forall k$.
Telescoping it over $t$ yields:

(64) $\begin{split}&\sum_{t=1}^{T}{{\gamma
g}_{t,k}({x}_{t})}\leq{\lambda}_{k}(T)-{\lambda}_{k}(0),\;\forall
k\in\\{1,2,...,K\\}.\\\
&\Rightarrow\sum_{t=1}^{T}{{g}_{t,k}({x}_{t})}\leq\frac{{\lambda}_{k}(T)}{\gamma}\leq\frac{||\bm{\lambda}(T)||}{\gamma},\;\forall
k\in\\{1,2,...,K\\}.\end{split}$

It completes the proof.

###  B.4. Proof of Lemma 11

Proof: According to the strong convexity of
${\nabla{f}_{t}({x}_{t})}^{T}(x-{x}_{t})+[{\bm{\lambda}}(t)+\gamma{{\bm{g}}}_{t}({x}_{t}){]}^{T}(\gamma{{\bm{g}}}_{t}(x))+{\alpha}||x-{x}_{t}{||}^{2}$
with respect to _x_ and recalling that ${x}_{t+1}$ minimizes this expression
over $\chi$, we have

(65)
$\begin{split}&{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})+[{\bm{\lambda}}(t)+\gamma{{{\bm{g}}}}_{t}({x}_{t}){]}^{T}(\gamma{{{\bm{g}}}}_{t}({x}_{t+1}))+{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}\\\
&\leq{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t})+[{\bm{\lambda}}(t)+\gamma{{{\bm{g}}}}_{t}({x}_{t}){]}^{T}(\gamma{{{\bm{g}}}}_{t}(\hat{x}))+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}\\\
&\overset{(a)}{\leq}{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t})-\gamma\epsilon\sum_{k=1}^{K}{{[\lambda}_{k}(t)+\gamma{g}_{t,k}({x}_{t})]}+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}\\\
&\overset{(b)}{=}{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t})-\gamma\epsilon||{\bm{\lambda}}(t)+\gamma{{{\bm{g}}}}_{t}({x}_{t}){||}_{1}+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}\\\
&\overset{(c)}{\leq}{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t})-\gamma\epsilon||{\bm{\lambda}}(t)+\gamma{{{\bm{g}}}}_{t}({x}_{t}){||}+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}\\\
&\overset{(d)}{\leq}{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t})-\gamma\epsilon[||{\bm{\lambda}}(t){||}-||\gamma{{{\bm{g}}}}_{t}({x}_{t}){||}]+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}\end{split}$

Where (a) is due to the Slater condition (Assumption 2); (b) holds since
${\lambda}_{k}(t)+\gamma{g}_{t,k}({x}_{t})\geq 0,\;\forall k$; (c) holds due
to the fact that $||x{||}_{1}\geq||x{||}$ for any vector $x\in\chi$; (d) holds
by the triangle inequality $||u-v{||}\geq||u{||}-||v{||},\;\forall
u,v\in\chi$. Base on Lemma 9, we add Lyapunov drift term $\Delta(t)$ on both
sides and rearranging some terms yields:

(66)
$\begin{split}&\Delta(t)\leq{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t})-{\nabla{f}_{t}({x}_{t})}^{T}({x}_{t+1}-{x}_{t})-{\gamma}^{2}{{{{{\bm{g}}}}}}_{t}({x}_{t})^{T}{{{{{\bm{g}}}}}}_{t}({x}_{t+1})-\gamma\epsilon[||{{\bm{\lambda}}}(t){||}-||\gamma{{{{{\bm{g}}}}}}_{t}({x}_{t}){||}]\\\
&+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}+{\gamma}^{2}||{{\bm{g}}}_{t+1}({x}_{t+1}){||}^{2}+\gamma[\bm{\lambda}(t){]}^{T}({{\bm{g}}}_{t+1}({x}_{t+1})-{{\bm{g}}}_{t}({x}_{t+1}))\\\
&\leq{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t+1})-\gamma\epsilon||{{\bm{\lambda}}}(t){||}+{\gamma}^{2}\epsilon||{{{{{\bm{g}}}}}}_{t}({x}_{t}){||}+{\gamma}^{2}||{{\bm{g}}}_{t+1}({x}_{t+1}){||}^{2}-{\gamma}^{2}{{{{{\bm{g}}}}}}_{t}({x}_{t})^{T}{{{{{\bm{g}}}}}}_{t}({x}_{t+1})\\\
&+{\alpha}||\hat{x}-{x}_{t}{||}^{2}-{\alpha}||{x}_{t+1}-\hat{x}{||}^{2}-{\alpha}||{x}_{t+1}-{x}_{t}{||}^{2}+\gamma[\bm{\lambda}(t){]}^{T}({{\bm{g}}}_{t+1}({x}_{t+1})-{{\bm{g}}}_{t}({x}_{t+1}))\\\
&\leq{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t+1})-\gamma\epsilon||{{\bm{\lambda}}}(t){||}+{\gamma}^{2}\epsilon||{{{{{\bm{g}}}}}}_{t}({x}_{t}){||}+{\gamma}^{2}||{{\bm{g}}}_{t+1}({x}_{t+1}){||}^{2}-{\gamma}^{2}{{{{{\bm{g}}}}}}_{t}({x}_{t})^{T}{{{{{\bm{g}}}}}}_{t}({x}_{t+1})\\\
&+{\alpha}||\hat{x}-{x}_{t}{||}^{2}+\gamma[\bm{\lambda}(t){]}^{T}({{\bm{g}}}_{t+1}({x}_{t+1})-{{\bm{g}}}_{t}({x}_{t+1}))\\\
&\overset{(a)}{\leq}{\nabla{f}_{t}({x}_{t})}^{T}(\hat{x}-{x}_{t+1})-\gamma\epsilon||{{\bm{\lambda}}}(t){||}+{\gamma}^{2}\epsilon
F+{\gamma}^{2}{F}^{2}-{\gamma}^{2}{{{{{\bm{g}}}}}}_{t}({x}_{t})^{T}{{{{{\bm{g}}}}}}_{t}({x}_{t+1})\\\
&+{\alpha}||\hat{x}-{x}_{t}{||}^{2}+\gamma[\bm{\lambda}(t){]}^{T}({{\bm{g}}}_{t+1}({x}_{t+1})-{{\bm{g}}}_{t}({x}_{t+1}))\\\
&\overset{(b)}{\leq}||\nabla{f}_{t}({x}_{t}){||}||\hat{x}-{x}_{t+1}{||}-\gamma\epsilon||{{\bm{\lambda}}}(t){||}+{\gamma}^{2}\epsilon
F+{\gamma}^{2}{F}^{2}+{\gamma}^{2}||{{{{{\bm{g}}}}}}_{t-1}({x}_{t}){||}||{{{{{\bm{g}}}}}}_{t}({x}_{t+1}){||}\\\
&+{\alpha}||\hat{x}-{x}_{t}{||}^{2}+\gamma||\bm{\lambda}(t){||}||{{g}}_{t+1}({x}_{t+1})-{{g}}_{t}({x}_{t+1}){||}\end{split}$
(67)
$\begin{split}&\overset{(c)}{\leq}-\gamma\epsilon||{{\bm{\lambda}}}(t){||}+GR+{\gamma}^{2}\epsilon
F+{\gamma}^{2}{F}^{2}+{\gamma}^{2}{F}^{2}+\alpha{R}^{2}+\gamma||\bm{\lambda}(t){||}||{{\bm{g}}}_{t+1}({x}_{t+1})-{{\bm{g}}}_{t}({x}_{t+1}){||}\\\
&=-\gamma(\epsilon-||{{\bm{g}}}_{t+1}({x}_{t+1})-{{\bm{g}}}_{t}({x}_{t+1}){||})||{{\bm{\lambda}}}(t){||}+GR+{\gamma}^{2}\epsilon
F+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}\\\
&\leq-\gamma(\epsilon-\max_{t}{\max_{x\in\chi}{\\{||{{\bm{g}}}_{t+1}({x})-{{\bm{g}}}_{t}({x}){||}\\}}})||{{\bm{\lambda}}}(t){||}+GR+{\gamma}^{2}\epsilon
F+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}\end{split}$

Where (a) holds by Assumption 1; (b) is due to the Cauchy–Schwarz inequality;
(c) follows from the Assumption 1. We have
$\hat{\epsilon}=\epsilon-\max_{t}{\max_{x\in\chi}{\\{||{{\bm{g}}}_{t+1}({x})-{{\bm{g}}}_{t}({x}){||}\\}}}>0$
since
$\epsilon>{\bar{V}}_{g}=\max_{t}{\max_{x\in\chi}{\\{||{\bm{g}}_{t+1}(x)-{\bm{g}}_{t}(x){||}\\}}}$,
Next we perform a reduction to absurdity process to prove this Lemma. Recall
that ${\lambda}_{k}(1)=0$ for all $k\in\\{1,2,...,K\\}$ implies that
$||{\bm{\lambda}}(1){||}=0\leq\gamma
F+\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}$. Assume that there exists a $\tau\geq 2$ such that
$||{\bm{\lambda}}(\tau){||}>\gamma
F+\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}$ and $||{\bm{\lambda}}(t){||}\leq\gamma
F+\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}$ for all $t<\tau$, then we consider two cases about
the value of $||{\bm{\lambda}}(\tau-1){||}$.
Case 1: If
$||{\bm{\lambda}}(\tau-1){||}>\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}$, then we can derive $\Delta(\tau-1)<0$. According to
(LABEL:1_of_lemma_B6), we have

(68)
$\begin{split}&||{{\lambda}}(\tau){||}<||{{\lambda}}(\tau-1){||}\leq\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}\\\ &<\gamma
F+\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}\end{split}$

Which contradicts the definition of $\tau$.

Case 2: If
$||{\bm{\lambda}}(\tau-1){||}\leq\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}$, then according to Lemma 9 we have

(69)
$\begin{split}&||{{\lambda}}(\tau){||}\leq||{{\lambda}}(\tau-1){||}+\gamma||{{g}}_{t-1}({x}_{t}){||}\leq\gamma
F+\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}\end{split}$

Which also contradicts the definition of $\tau$. Hence
$||{\bm{\lambda}}(t){||}\leq\gamma
F+\frac{GR+2{\gamma}^{2}{F}^{2}+{\alpha}{R}^{2}+{\gamma}^{2}\epsilon
F}{\gamma\hat{\epsilon}}$ holds for all $t>1$. It completes the Proof.