# Online Convex Optimization with Switching Cost and Delayed Gradients

Spandan Senapati<EMAIL_ADDRESS>Rahul Vaze
<EMAIL_ADDRESS>Department of Computer Science and Engineering, Indian
Institute of Technology Kanpur, Kanpur, India  School of Technology and
Computer Science, Tata Institute of Fundamental Research, Mumbai, India

###### Abstract

We consider the online convex optimization (OCO) problem with quadratic and
linear switching cost in the limited information setting, where an online
algorithm can choose its action using only gradient information about the
previous objective function. For $L$-smooth and $\mu$-strongly convex
objective functions, we propose an online multiple gradient descent (OMGD)
algorithm and show that its competitive ratio for the OCO problem with
quadratic switching cost is at most $4(L+5)+\frac{16(L+5)}{\mu}$. The
competitive ratio upper bound for OMGD is also shown to be order-wise tight in
terms of $L,\mu$. In addition, we show that the competitive ratio of any
online algorithm is $\max\\{\Omega(L),\Omega(\frac{L}{\sqrt{\mu}})\\}$ in the
limited information setting when the switching cost is quadratic. We also show
that the OMGD algorithm achieves the optimal (order-wise) dynamic regret in
the limited information setting. For the linear switching cost, the
competitive ratio upper bound of the OMGD algorithm is shown to depend on both
the path length and the squared path length of the problem instance, in
addition to $L,\mu$, and is shown to be order-wise, the best competitive ratio
any online algorithm can achieve. Consequently, we conclude that the optimal
competitive ratio for the quadratic and linear switching costs are
fundamentally different in the limited information setting.

###### keywords:

Online optimization, online algorithm, limited information, competitive ratio,
dynamic regret.

###  1 Introduction

Online convex optimization (OCO) is a very popular optimization paradigm where
decisions have to be made with unknown utility functions. With OCO, at each
time $t$, the goal of an online algorithm $\mathcal{A}$ is to choose an action
$\boldsymbol{x}_{t}$ that minimizes a convex objective function $f_{t}$,
however $f_{t}$ is revealed after
${\boldsymbol{x}}_{t}\in\mathcal{X}\subseteq{\mathbb{R}}^{d}$ has been chosen.
In most settings with OCO, once ${\boldsymbol{x}}_{t}$ is chosen both
$f_{t}({\boldsymbol{x}}_{t})$ and $\nabla f_{t}({\boldsymbol{x}}_{t})$ are
revealed. Knowing all the $f_{t}$’s, $t=1,\dots,T$ ahead of time, where $T$ is
the time horizon, an optimal offline algorithm ($\mathsf{OPT}$) chooses action
${\boldsymbol{x}}^{\star}:=\arg\min_{{\boldsymbol{x}}\in\mathcal{X}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}})$,
and the static regret for $\mathcal{A}$ is defined as
$Sr\coloneqq\max_{f_{t},t=1,\dots,T}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})-\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}^{\star}),$
i.e., an adversary can choose the functions $f_{t}$. The name static comes
from the fact that $\mathsf{OPT}$ is constrained to use a single action.

Large body of work is known for static regret [1, 2, 3, 4, 5], where if the
functions $f_{t}$’s are convex, the optimal regret is $\Theta(\sqrt{T})$,
while if the functions $f_{t}$’s are strongly convex then algorithms with
regret at most $\mathcal{O}(\log T)$ are known. When the functions $f_{t}$’s
are chosen by an adversary, but the arrival order is randomized, algorithms
with better guarantees are also known [3].

Natural generalization of the static regret is the dynamic regret [6, 7],
where the regret for a comparator sequence
${\boldsymbol{u}}=({\boldsymbol{u}}_{1},\dots,{\boldsymbol{u}}_{T})$ is
defined as
$Dr({\boldsymbol{u}}):=\max_{f_{t},t=1,\dots,T}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})-\sum_{t=1}^{T}f_{t}({\boldsymbol{u}}_{t}).$
For this general dynamic regret definition, sub-linear (in $T$) regret is not
always possible, unless some structure is enforced on the comparator sequence.
For example, for a sequence ${\boldsymbol{u}}$, defining
$\mathcal{P}_{T}({\boldsymbol{u}}):=\sum_{t=2}^{T}||{\boldsymbol{u}}_{t}-{\boldsymbol{u}}_{t-1}||$,
the online gradient descent (OGD) algorithm was shown to achieve dynamic
regret
$Dr({\boldsymbol{u}})=\mathcal{O}(\sqrt{T}(1+\mathcal{P}_{T}({\boldsymbol{u}}))$
[6], which has been improved to
$\mathcal{O}(\sqrt{T(1+\mathcal{P}_{T}({\boldsymbol{u}}))})$ in [8], matching
the lower bound $\Omega(\sqrt{T(1+\mathcal{P}_{T}({\boldsymbol{u}}))})$ [8].

A special case of $Dr({\boldsymbol{u}})$ that is popularly studied [9, 10, 11,
12, 13, 14, 15, 16] is by restricting
${\boldsymbol{u}}={\boldsymbol{x}}^{\star}=({\boldsymbol{x}}_{1}^{\star},\dots,{\boldsymbol{x}}_{T}^{\star})$,
where
${\boldsymbol{x}}_{t}^{\star}\coloneqq\arg\min_{{\boldsymbol{x}}\in\mathcal{X}}f_{t}({\boldsymbol{x}})$
is the local minimizer of $f_{t}({\boldsymbol{x}})$. For this case, the best
known bound on the dynamic regret has been shown to be
$\mathcal{O}(\mathcal{P}_{T}({\boldsymbol{x}}^{\star}))$ in [12] by using the
online gradient descent (OGD) algorithm, when the functions $f_{t}$’s are
strongly convex and smooth. Under the special case that the minimizers
${\boldsymbol{x}}_{t}^{\star}$ lie in the interior of the feasible set,
$\mathcal{O}(\mathcal{P}_{T}({\boldsymbol{x}}^{\star}))$ regret can be
achieved when the functions $f_{t}$’s are just convex and smooth [11]. For
strongly convex and smooth functions, defining
$\mathcal{P}_{2,T}^{\star}:=\sum_{t=2}^{T}||{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}||^{2}$,
[13] showed that
$\mathcal{O}(\min\\{\mathcal{P}_{T}({\boldsymbol{x}}^{\star}),\mathcal{P}_{2,T}^{\star}\\})$
is also achievable as long as at each time $t$, the gradient of $f_{t}$ at
multiple points is available. Most recently, [16] improved this guarantee to
$\mathcal{O}(\min\\{\mathcal{P}_{T}({\boldsymbol{x}}^{\star}),\mathcal{P}_{2,T}^{\star},FV\\})$,
where
$FV:=\sum_{t=2}^{T}\sup_{{\boldsymbol{x}}\in\mathcal{X}}|f_{t}({\boldsymbol{x}})-f_{t-1}({\boldsymbol{x}})|$
denotes the functional variation.

The constrained version of OCO has also been considered recently in [17, 18,
19, 20], where at each time $t$, the objective is to minimize the loss
function $f_{t}$ subject to a constraint $g_{t}({\boldsymbol{x}})\leq 0$.
Compared to OCO, there are two performance measures, the usual dynamic regret
and in addition the constraint violation penalty
$\max_{f_{t},g_{t},t=1,\dots,T}\sum_{t=1}^{T}g_{t}({\boldsymbol{x}}_{t})$.

One generalization of OCO that has applications in data centers is the OCO
with switching cost (OCO-S) problem, where in addition to the penalty paid for
choosing sub-optimal decisions, there is a cost for changing actions in
successive time slots. In particular, the cost of an online algorithm
$\mathcal{A}$ for OCO-S is

$C_{\mathcal{A}}:=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1}),$
(1)

where $c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})$ is a non-negative
function that denotes the cost of switching from ${\boldsymbol{x}}_{t-1}$ to
${\boldsymbol{x}}_{t}$. The goal of $\mathcal{A}$ is to either minimize the
dynamic regret

$R_{d}(\mathcal{A}):=\max_{f_{t}}(C_{\mathcal{A}}-C_{\mathsf{OPT}}),$ (2)

or the competitive ratio

$\text{cr}_{\mathcal{A}}:=\max_{f_{t}}\frac{C_{\mathcal{A}}}{C_{\mathsf{OPT}}},$
(3)

where $C_{\mathsf{OPT}}$ denotes the cost of the $\mathsf{OPT}$, that knows
all the $f_{t}$’s ahead of time, for solving (1), i.e.

$C_{\mathsf{OPT}}:=\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1}).$

Two of the most common forms of the switching cost that have been considered
in the literature are (a) quadratic switching cost, where
$c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})=\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}$,
and (b) linear switching cost, where
$c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})=\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|$.
In this paper, we consider both the competitive ratio (3) as well as the
dynamic regret (2) for (a) and competitive ratio for (b).

The OCO with switching cost model is a versatile framework that captures a
number of important problems in real-life. To build motivation, we consider
the following problems that can be formulated within the framework.

  * 1.

Server Management in Data Centers: The pioneering work on the OCO problem with
switching cost was [21] that considered the problem of the dynamic right
sizing for power-proportional data centers. A data center is modelled as an
ensemble of servers, and it involves two important determinations: (i)
determining $x_{t}$, the count of the active servers at time $t$, and (ii)
assigning jobs to servers, i.e., determining $r_{i,t}$ which represents the
arrival rate to server $i$ at time $t$. Let $r_{t}$ denote the total job
arrival rate at time $t$. Then, $\sum_{i=1}^{x_{t}}r_{i,t}=r_{t}$ must hold,
to ensure that all the jobs are processed. The goal is to choose the number of
active servers $x_{t}$ and assign jobs to each active server $r_{i,t}$, such
that the total cost incurred by the data center across $T$ time slots is
minimized.

At each time $t$, the data center’s cost is modelled as a combination of (i)
operational cost, representing the cost of running an active server, and (ii)
the switching cost to model the cost of toggling a server on/off. The costs of
operation are modelled by a convex function $\phi(r_{i,t})$, where the
function $\phi$ is the same for all the servers. This assumption is quite
standard and captures a number of commonly used server models. We refer
interested readers to the discussion in [21] for examples of $\phi$. The
switching cost $c(x_{t},x_{t-1})$ denotes the cost of changing the number of
active servers.

With the cost model as mentioned above, the goal of the data center is to
choose $x_{t}$ and $r_{i,t}$ to solve the following convex optimization
problem:

$\displaystyle\min\sum_{t=1}^{T}\bigg{(}\sum_{i=1}^{x_{t}}\phi(r_{i,t})+\beta
c(x_{t},x_{t-1})\bigg{)},$ $\displaystyle\text{subject to }r_{i,t}\geq
0,\quad\sum_{i=1}^{x_{t}}r_{i,t}=r_{t}\text{ for all }t,$

where the switching cost $c(x_{t},x_{t-1})$ can take many forms, for example
$(x_{t}-x_{t-1})^{2}$ or $(x_{t}-x_{t-1})^{+}$.

  * 2.

Trajectory Tracking: Given a target trajectory $\\{\theta_{t}\\}_{t=1}^{T}$, a
robot positioned at $x_{t}$ at time $t$ aims to chase the target while
maintaining proximity to it, meaning the distance
$\left\|x_{t}-{\theta}_{t}\right\|$ is small. Additionally, the robot wishes
to minimize the energy expended in changing its position from $x_{t-1}$ to
$x_{t}$. This energy expenditure is influenced by the rate of change between
positions and is proportional to the kinetic energy
$\big{(}\frac{\left\|x_{t}-x_{t-1}\right\|}{\Delta}\big{)}^{2}$, where
$\Delta$ denotes the time taken by the robot to move from $x_{t-1}$ to
$x_{t}$. Therefore, the problem that we wish to solve for the robot can be
formulated as (1) with $f_{t}(x_{t})=\left\|x_{t}-\theta_{t}\right\|$ and
switching cost
$c(x_{t},x_{t-1})=\frac{\gamma}{2}\left\|x_{t}-x_{t-1}\right\|^{2}$, or
equivalently $\frac{\gamma}{2}\left\|x_{t}-x_{t-1}\right\|$, for a certain
$\gamma>0$.

  * 3.

Economic Power Dispatch: We consider the problem of economic power dispatch as
outlined in [22]. This scenario involves a set of $k$ generators with non-
negative outputs $(x_{t}^{(1)},\dots,x_{t}^{(k)})$ (collectively represented
as a vector ${\boldsymbol{x}}_{t}\in\mathbb{R}_{+}^{k}$) at a given time $t$.
The main objective here is to minimize the overall generation cost
$\sum_{i=1}^{k}g(x_{t}^{(i)})$, all the while ensuring a balance between the
changing power demand $d_{t}$ and the availability of renewable energy supply
$s_{t}$. To achieve this, a cost function $f_{t}({\boldsymbol{x}}_{t})$ is
introduced, which accounts for the generation cost and also incorporates a
penalty for any deviation from the demand-supply equilibrium. The cost
function is given by

$\displaystyle
f_{t}({\boldsymbol{x}}_{t})=\sum_{i=1}^{k}g_{i}(x_{t}^{(i)})+\lambda_{t}\bigg{(}\sum_{i=1}^{k}x_{t}^{(i)}+s_{t}-d_{t}\bigg{)}^{2},$

where $\lambda_{t}>0$ governs the penalty imposed when the demand-supply gap
is not adequately maintained. Within the context of power systems, altering
the power output of generators incurs significant operational costs. These are
known as ramp costs and similar to [22, 23, 24], we model the switching cost
as a quadratic function
$c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})=\frac{\gamma}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}=\frac{\gamma}{2}\sum_{i=1}^{k}(x_{t,i}-x_{t-1,i})^{2}$.
Therefore, the goal is to minimize the total generation cost, including the
imbalance penalty and the ramp costs summed across $T$ time slots. This can be
formulated as (1) with $f_{t}({\boldsymbol{x}}_{t})$ and
$c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})$ as discussed above.

For the OCO-S problem with quadratic switching cost (OCO-SQ), if $f_{t}$’s are
convex, then one can show that the competitive ratio (3) of any online
algorithm is unbounded. Thus, starting with [25], to solve (3), $f_{t}$’s were
assumed to have properties beyond convexity, such as strong convexity. The
online balanced descent (OBD) algorithm, initially proposed by [25], was shown
to attain a competitive ratio of at most $3+\mathcal{O}(\frac{1}{\mu})$ for
$\mu$-strongly convex functions in [26]. An improved variant of OBD was
considered in [27] with competitive ratio $\mathcal{O}(\frac{1}{\sqrt{\mu}})$
as ${\mu\to 0}$, which was also shown to be the best possible (order-wise with
respect to $\mu$) competitive ratio for all possible online algorithms in
[27].

OCO-S with linear switching cost (OCO-SL), where
$C_{\mathcal{A}}=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|$,
has also been considered. When $f_{t}$’s are convex, the competitive ratio of
any online algorithm has a lower bound $\Omega(\sqrt{d})$ [25]. OBD was the
first algorithm to achieve a dimension free competitive ratio upper bound of
$3+\mathcal{O}(\frac{1}{\alpha})$ for $\alpha$-locally polyhedral functions in
[25]. When $f_{t}$’s are $\mu$-strongly convex and $L$-smooth, [28] proposed a
constrained online balanced descent (COBD) algorithm with a competitive ratio
$\mathcal{O}(({L/\mu})^{\frac{1}{2}})$. Furthermore, [28] showed that the
competitive ratio of any online algorithm is
$\Omega(({L}/{\mu})^{\frac{1}{3}})$. When $d=1$, algorithms with constant
competitive ratios are known for the OCO-SL problem when $f_{t}$’s are just
convex [29, 21, 30, 31, 32].

The main limitation of most prior work on OCO-S for minimizing the competitive
ratio with quadratic or linear switching cost is that before the action
${\boldsymbol{x}}_{t}$ is chosen the full function $f_{t}$ is completely
revealed, referred to as the full information setting in the rest of the
paper. Recall that the information structure in the OCO problem is
fundamentally different; action ${\boldsymbol{x}}_{t}$ at time $t$ is chosen
without any information about $f_{t}$, and once the action is chosen, one or
more gradients $\nabla f_{t}(.)$ are revealed. We will refer to this as the
limited information setting hereafter. For minimizing the dynamic regret (2)
for OCO-S, a delayed information setting has also been considered in [33],
where at time $t$, an online algorithm $\mathcal{A}$ takes action
${\boldsymbol{x}}_{t}$ with complete information about $f_{1},\dots,f_{t-1}$.
However, a limitation of [33] is that it completely ignores the switching cost
of the $\mathsf{OPT}$ and trivially bounds the switching cost of its proposed
algorithm. This leads to a large gap between the upper and lower bound on the
dynamic regret with respect to $L,\mu$ for certain problem instances.

The full information setting (as well as the delayed information setting to
some extent) is quite imposing for many applications and difficult to realize
in practice. Thus, in this paper, we study the OCO-S problem under the limited
information setting, similar to the OCO problem. In particular, the limited
information setting we consider is as follows: At time $t$, $\mathcal{A}$
takes action ${\boldsymbol{x}}_{t}$ with only gradient information about
$f_{t-1}$ at multiple points. Moreover, given that the limited information
setting is far less imposing than the widely considered full information
setting, our proposed algorithms are readily applicable to practical settings
relevant to the performance modelling of computer systems and communication
networks, where obtaining large amount of sequential information may not be
viable.

Moving from the full information setting to the limited information setting to
solve (3) is challenging on account of the following reasons. Most algorithms
to solve (3) are of the following flavour: given the previous action
${\boldsymbol{x}}_{t-1}$ for algorithm $\mathcal{A}$, choose the new action
${\boldsymbol{x}}_{t}$ such that $f_{t}({\boldsymbol{x}}_{t})=\beta
c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})$, for some constant $\beta>0$.
This algorithm critically needs to know $f_{t}$ at all points before choosing
${\boldsymbol{x}}_{t}$. Moreover the analysis using a potential function
argument proceeds by comparing the hitting cost $f_{t}({\boldsymbol{x}}_{t})$
of $\mathcal{A}$ with that of the $\mathsf{OPT}$, and that is sufficient since
the hitting cost and the switching cost for $\mathcal{A}$ are multiples of
each other. An alternative approach to construct an algorithm in the full
information setting is to simply use
${\boldsymbol{x}}_{t}={\boldsymbol{x}}_{t}^{\star}$ [34] and use certain
structural properties of strongly convex functions.

With the limited information setting, neither can one directly connect the
hitting and the switching costs for an online algorithm $\mathcal{A}$, since
$\mathcal{A}$ is never aware of $f_{t}$ before making the decision at time
$t$, nor use ${\boldsymbol{x}}_{t}^{\star}$ to make decisions at time $t$.
This is the primary challenge we overcome in this paper, where we depart from
the potential function approach and proceed as follows: We propose a simple
online gradient descent algorithm that at each time slot makes
$\mathcal{O}(L/\mu)$ number of gradient descent steps in the limited
information setting, and upper bound its cost (1). Next, we separately lower
bound the cost (1) of the $\mathsf{OPT}$ for any problem instance. Taking the
ratio of the two bounds we get our result. As far as we know, this approach
has not been used for solving (3). A byproduct of our approach is that we also
get an upper bound on the dynamic regret (2) which is also shown to be order-
wise (with respect to the path length
$\mathcal{P}_{T}({\boldsymbol{x}}^{\star})$) optimal when the switching cost
is quadratic. Similar approach also works for the linear switching cost case
as well.

Notation: We use regular font letters to denote scalars, bold-faced lower case
letters to denote vectors, and bold-faced upper case letters to denote
matrices. The $\ell_{2}$ norm of ${\boldsymbol{x}}$ is denoted by
$\left\|{\boldsymbol{x}}\right\|$ and
$\langle{\boldsymbol{u}},{\boldsymbol{v}}\rangle$ denotes the standard inner
product of ${\boldsymbol{u}}$ and ${\boldsymbol{v}}$, defined as
$\langle{\boldsymbol{u}},{\boldsymbol{v}}\rangle:={\boldsymbol{u}}^{{\mathsf{T}}}{\boldsymbol{v}}$.
Further, $\mathbf{0}$ denotes the vector/matrix of all zeros whose size can be
inferred from the context. For a matrix ${\boldsymbol{X}}$,
$\lambda_{i}({\boldsymbol{X}})$ denotes its $i^{th}$ eigenvalue. We use the
notation ${\boldsymbol{X}}\succeq\mathbf{0}$
$({\boldsymbol{X}}\succ\mathbf{0})$ when ${\boldsymbol{X}}$ is a positive
semidefinite (positive definite) matrix which is equivalent to
$\lambda_{i}({\boldsymbol{X}})\geq 0$ $(\lambda_{i}({\boldsymbol{X}})>0),$ for
all $i$.

###  2 Contributions

####  2.1 Quadratic Switching Cost

Our contributions for solving the OCO-SQ problem, when all $f_{t}$’s are
$\mu$-strongly convex and $L$-smooth, in the limited information setting are
as follows.

  1. 1.

We consider an online multiple gradient descent (OMGD) algorithm that takes
$K$ gradient descent steps (if it can) at time slot $t$ using the gradients
$\nabla f_{t-1}$ at $K$ distinct points with step size equal to $\frac{1}{L}$.

OMGD algorithm essentially tries to choose action ${\boldsymbol{x}}_{t}$ that
is close to the optimizer of the function $f_{t-1}$. It is well-known that for
strongly convex functions, one iteration of the usual gradient descent
algorithm with appropriate step size has the contraction property that
$||{\boldsymbol{x}}_{i}-{\boldsymbol{x}}^{\star}||\leq
c||{\boldsymbol{x}}_{i-1}-{\boldsymbol{x}}^{\star}||$ for some $c<1$, where
${\boldsymbol{x}}^{\star}$ is the optimal point and
$\\{{\boldsymbol{x}}_{i}\\}$ are the iterates. Given that at time $t$, OMGD is
trying to get close to the optimizer ${\boldsymbol{x}}_{t-1}^{\star}$ of
$f_{t-1}$, using the contraction property and the triangle inequality it is
possible to bound the sum of squared distances of the action
${\boldsymbol{x}}_{t}$ produced by OMGD and the optimizer
${\boldsymbol{x}}_{t}^{\star}$ of $f_{t}$, i.e., the quantity
${\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|}^{2}$
in terms of the squared path length
$\mathcal{P}_{2,T}^{\star}={\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|}^{2}$,
a fundamental quantity for OCO. Finally using the $L$-smoothness property,
this can be translated to bound the sub-optimality gap
$f_{t}({\boldsymbol{x}}_{t})-f_{t}({\boldsymbol{x}}_{t}^{\star})$. This is the
usual recipe to bound the cost of OCO with a gradient descent based algorithm
in the limited information setting.

With the additional switching cost present in (1), analysing OMGD is lot more
challenging, since by its very definition OMGD disregards the presence of
switching cost. It turns out that the contraction property can be leveraged
for bounding the switching cost as well. In the analysis, we show that
choosing $K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$, the competitive ratio of
OMGD algorithm is at most

$4(L+5)+\frac{16(L+5)}{\mu}.$ (4)

To derive this competitive ratio bound, we separately upper bound the cost of
OMGD and lower bound the cost of the $\mathsf{OPT}$. Lower bounding the cost
of the $\mathsf{OPT}$ is a non-trivial exercise and as far as we know has not
been accomplished before. We also show that a similar competitive ratio
guarantee holds for OMGD even against an arbitrary comparator sequence in
Remark 6.

  2. 2.

By constructing a sequence of $f_{t}$’s, we show that the competitive ratio of
OMGD is at least $1+\frac{L+1}{4\mu}+\frac{L+1}{8}$, showing that order-wise
(with respect to $L,\mu$), the competitive ratio (4) for OMGD cannot be
improved. The analysis to derive the lower bound on the competitive ratio for
the OMGD algorithm also implies that any online algorithm that at time $t$
tries to ‘chase’ 111Defined after Lemma 6. the optimizer
${\boldsymbol{x}}^{\star}_{t-1}$ also has the same competitive ratio lower
bound as the OMGD algorithm.

  3. 3.

We also show that the competitive ratio of any online algorithm is at least
$\max\\{\Omega\left(L\right),\Omega\big{(}\frac{L}{\sqrt{\mu}}\big{)}\\}$.
These bounds follow rather easily by porting prior results from [27] on the
full information model to the limited information model. We in fact conjecture
that the competitive ratio of any online algorithm in the limited information
setting is at least $\Omega(\frac{L}{{\mu}})$, which will show a fundamental
difference in the dependence of $\mu$ on the order-wise optimal competitive
ratio in the full information setting versus the limited information setting.

  4. 4.

Our results to bound the competitive ratio of OMGD directly also provide an
upper bound on its dynamic regret (2) which is shown to be order-wise optimal
(with respect to the path length $\mathcal{P}_{T}({\boldsymbol{x}}^{\star})$)
when the feasible set has a finite diameter. Compared to [33], our upper bound
on the dynamic regret is order-wise tighter in the regime when $L\rightarrow
0$ and $\frac{L}{\mu}$ is finite, and matches in all other regimes.

####  2.2 Linear Switching Cost

Our contributions for solving the OCO-SL problem, when all $f_{t}$’s are
$\mu$-strongly convex and $L$-smooth, in the limited information setting are
as follows.

  1. 1.

Similar to the quadratic switching cost case, we consider the OMGD algorithm
with $K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$, and derive an upper bound on its
cost. To lower bound the cost of $\mathsf{OPT}$, we reduce any instance of the
linear switching cost problem to a quadratic switching cost problem, and use
the lower bound derived for the quadratic switching cost case. As a result, we
get the following upper bound on the competitive ratio of OMGD

$\displaystyle
L(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+\frac{3}{2}\frac{\big{(}\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|\big{)}^{2}}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}+\frac{8L}{\mu}+\frac{12}{\mu}\frac{\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}},$

where we use the shorthand $\mathcal{P}_{T}^{\star}$ for
$\mathcal{P}_{T}({\boldsymbol{x}}^{\star})$ throughout, and
$\mathcal{P}_{2,T}^{\star}=\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}$.
Different from the quadratic switching cost problem, where the competitive
ratio depends only on $L,\mu$, the competitive ratio for the linear switching
cost problem depends on problem specific quantities $\mathcal{P}_{T}^{\star}$
and $\mathcal{P}_{2,T}^{\star}$, in addition to $L$, $\mu$.

  2. 2.

By constructing a sequence of $f_{t}$’s that are $\mu$-strongly convex and
$\mu$-smooth, we show that the competitive ratio of any online algorithm can
be lower bounded by

$\displaystyle\Omega\bigg{(}\mu(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+\frac{3}{2}\frac{\big{(}\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|\big{)}^{2}}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}+\frac{12}{\mu}\frac{\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}\bigg{)},$

which order-wise (with respect to $\mathcal{P}_{T}^{\star}$ and
$\mathcal{P}_{2,T}^{\star}$) matches with the upper bound on the competitive
ratio of OMGD.

Recall that with the full information setting, algorithm with competitive
ratio of $2$ [31] is known even when the functions $f_{t}$’s are just convex
and $d=1$. Thus, our result shows that the limited information setting is
fundamentally different than the full information setting when the switching
cost is linear, and the competitive ratio of any online algorithm is a
function of the path length $\mathcal{P}_{T}^{\star}$ or the squared path
length $\mathcal{P}_{2,T}^{\star}$.

####  2.3  Comparison with prior work

#####  2.3.1 Quadratic Switching Cost

For $\mu$-strongly convex functions $f_{t}$’s, in the full information
setting, the optimal competitive ratio for (3) is
$\Theta(\frac{1}{\sqrt{\mu}})$ as $\mu\to 0$ [27]. Our results show that the
limited information setting is fundamentally different and any online
algorithm has to have a competitive ratio growing linearly in $L$ and
$\frac{L}{\sqrt{\mu}}$. Surprisingly, when $L=c\mu$, for some finite constant
$c\geq 1$ (that is independent of $T$ and the problem parameters, i.e.,
$L,\mu$, etc.), the competitive ratio of the OMGD algorithm is
$\mathcal{O}(\frac{1}{\mu})$ as $\mu\to 0$ similar to the OBD algorithm [25,
26] that requires full information about the functions $f_{t}$’s, which is
rather remarkable.

For the delayed information setting, [33] considered the problem of minimizing
dynamic regret (2) over a compact feasible set. The online gradient descent
algorithm that takes only one gradient step achieves a regret of
$\mathcal{O}\big{(}\frac{G}{1-\sqrt{1-\mu/L}}\big{(}1+\frac{1}{L}\big{)}(\mathcal{P}_{T}^{\star}+D)\big{)}$,
while the lower bound on the regret for $\mu$-strongly convex and $\mu$-smooth
$f_{t}$’s is $\Omega\left(\zeta
D(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star})\right)$,
where
$\zeta=\frac{\mu^{3}(1-\rho)^{2}}{32(\mu+1)^{2}},\rho=\frac{\sqrt{\mu+4}-\sqrt{\mu}}{\sqrt{\mu+4}+\sqrt{\mu}}$,
$D$ is the diameter of the feasible set $\mathcal{X}$,
$\max_{{\boldsymbol{x}}\in\mathcal{X}}\left\|\nabla
f_{t}({\boldsymbol{x}})\right\|\leq G$, and
$\mathcal{P}_{T}^{*}=\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|$.
Thus, when $L\rightarrow 0$ and $\frac{L}{\mu}$ is finite, the upper and lower
bounds of [33] are not close. This gap is primarily the result of [33]’s
analysis that ignores the switching cost of the $\mathsf{OPT}$ and bounds the
switching cost of its proposed algorithm trivially. In comparison to [33], we
show by a tighter analysis that the OMGD algorithm achieves a dynamic regret
which is order-wise (in terms of $\mathcal{P}_{T}^{\star}$) the same as the
lower bound of [33] and has a superior dependence of $L,\mu$ than the factor
$\frac{G}{1-\sqrt{1-\mu/L}}\big{(}1+\frac{1}{L}\big{)}$ of [33], even in the
limited information setting.

In comparison to the most related prior work [25, 27, 34] on the competitive
ratio analysis of OCO-SQ, our analysis strategy for deriving an upper bound on
the competitive ratio (3) for the OMGD algorithm is novel. We separately upper
bound the cost of the OMGD algorithm and lower bound the cost of
$\mathsf{OPT}$, while the known analysis methods use a potential function
argument [25, 27] or compare the relative costs of the algorithm against the
$\mathsf{OPT}$ using structural properties of strongly convex functions [34].
Lower bounding the cost of $\mathsf{OPT}$ for the quadratic switching cost is
non-trivial while taking into account the quadratic switching cost and as far
as we know has not been accomplished before.

####  2.4 Linear Switching Cost

In the full information setting, the competitive ratio of any online algorithm
for solving (3) has a lower bound
$\mathcal{O}(\big{(}\frac{L}{\mu}\big{)}^{\frac{1}{3}}\big{)}$ while the COBD
algorithm [28] attains a competitive ratio
$\mathcal{O}(\big{(}\frac{L}{\mu}\big{)}^{\frac{1}{2}})$. However, in the
limited information setting our results show that it is not possible to attain
dimension-free bounds on the competitive ratio and any online algorithm has a
competitive ratio that explicitly depends on $\mathcal{P}_{T}^{\star}$ and
$\mathcal{P}_{2,T}^{\star}$. Moreover, in comparison to the most related prior
work [28, 35] on the linear switching cost problem, our analysis strategy is
different. Motivated by our results on the quadratic switching cost problem,
we upper bound the cost of the OMGD algorithm and lower bound the cost of the
$\mathsf{OPT}$ for any given problem instance by reducing the linear switching
cost problem to an instance of the quadratic switching cost problem.

Our contributions on the competitive ratio of an algorithm for the quadratic
and the linear switching cost problems in the limited information setting, and
our comparison against prior works are summarized in Table 1. As mentioned in
the introduction, when the functions $f_{t}$’s are convex, [36] showed that
the lower bound on the competitive ratio is $\Omega(\sqrt{d})$, therefore no
online algorithm $\mathcal{A}$ can attain a constant competitive ratio that is
independent of $d$. Therefore, we exclude the case when $f_{t}$’s are convex
and $d$ is arbitrary from the table. Further, [34, 27] considered $f_{t}$’s to
satisfy the $\mu$-quadratic growth condition, i.e.
$f_{t}({\boldsymbol{x}})-f_{t}({\boldsymbol{x}}_{t}^{\star})\geq\frac{\mu}{2}\left\|{\boldsymbol{x}}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}$
for all ${\boldsymbol{x}}\in\mathcal{X}$, in addition to convexity [34],
quasiconvexity [27]. In our context, for simplicity, in Table 1 we state the
result for strongly convex functions as they satisfy the quadratic growth
condition.

information setting |  assumption on $f_{t}$ |  dimension ($d$) |  switching cost |  upper bound on $\mu_{\mathcal{A}}$ |  lower bound on $\mu_{\mathcal{A}}$
---|---|---|---|---|---
full |  convex |  1 |  linear |  2 [35] |  2 [37]
full |  $\alpha$-polyhedral∗ |  arbitrary |  linear |  $3+\frac{8}{\alpha}$ [36] |  not given
full |  $\alpha$-polyhedral∗ |  arbitrary |  linear |  $\max(1,\frac{2}{\alpha})$ [34] |  not given
full |  $\mu$-strongly convex + $L$-smooth |  arbitrary |  linear |  $\mathcal{O}({\frac{L}{\mu}})^{\frac{1}{2}}$ [28] |  $\Omega(\frac{L}{\mu})^{\frac{1}{3}}$ [28]
limited (this work) |  $\mu$-strongly convex + $L$-smooth |  arbitrary |  linear |  depends on $\mathcal{P}_{T}^{\star}$, $\mathcal{P}_{2,T}^{\star}$ (Theorem 4) |  depends on $\mathcal{P}_{T}^{\star}$, $\mathcal{P}_{2,T}^{\star}$ (Lemma 15)
full |  $\mu$-strongly convex |  arbitrary |  quadratic |  $3+\mathcal{O}(\frac{1}{\mu})$ [26] |  $\Omega(\frac{1}{\sqrt{\mu}})$ as $\mu\to 0$[27]
full |  $\mu$-strongly convex |  arbitrary |  quadratic |  $1+\frac{4}{\mu}$ [34] |  $\Omega(\frac{1}{\sqrt{\mu}})$ as $\mu\to 0$[27]
full |  $\mu$-strongly convex |  arbitrary |  quadratic |  $\mathcal{O}(\frac{1}{\sqrt{\mu}})$ as $\mu\to 0$ [27] |  $\Omega(\frac{1}{\sqrt{\mu}})$ as $\mu\to 0$[27]
limited (this work) |  $\mu$-strongly convex + $L$-smooth |  arbitrary |  quadratic |  $\mathcal{O}(\frac{L}{\mu})$ as $\mu\to 0$ (Theorem 1) |  $\Omega(\frac{L}{\sqrt{\mu}})$ as $\mu\to 0$ (Lemma 10)
Table 1: Comparison of the competitive ratio of the proposed algorithm with
existing works. **footnotetext: A function $f:\mathcal{X}\to{\mathbb{R}}$ is
$\alpha$-polyhedral if
$f({\boldsymbol{x}})-f({\boldsymbol{x}}^{\star})\geq\alpha\left\|{\boldsymbol{x}}-{\boldsymbol{x}}^{\star}\right\|$
for all $x\in\mathcal{X}$, where
${\boldsymbol{x}}^{\star}:=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f({\boldsymbol{x}})$.

###  3 Problem Setting

OCO with Switching Cost (OCO-S) Problem: Consider that at time
$t=1,2,\dots,T$, a convex function
$f_{t}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}^{+}$ is going to be revealed
and an online algorithm $\mathcal{A}$’s objective is to choose action
${\boldsymbol{x}}_{t}\in\mathcal{X}\subseteq{\mathbb{R}}^{d}$ so as to the
minimize the overall cost

$C_{\mathcal{A}}=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1}),$
(5)

which comprises of the hitting cost $f_{t}({\boldsymbol{x}}_{t})$ and a non-
negative switching cost $c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})$.
Compared to OCO, there is an additional penalty in (5) if $\mathcal{A}$
changes its decisions between time slots $t-1$ and $t$. The goal for
$\mathcal{A}$ is to either minimize the dynamic regret

$R_{d}(\mathcal{A})=\max_{f_{t}}(C_{\mathcal{A}}-C_{\mathsf{OPT}}),$ (6)

or the competitive ratio

$\text{cr}_{\mathcal{A}}=\max_{f_{t}}\frac{C_{\mathcal{A}}}{C_{\mathsf{OPT}}},$
(7)

where $C_{\mathsf{OPT}}$ denotes the cost of the $\mathsf{OPT}$, that knows
all $f_{t}$’s ahead of time, for solving (5). In this paper, we consider two
forms of the switching cost (a) quadratic switching cost, where
$c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})=\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}$,
and (b) linear switching cost, where
$c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})=\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|$.
For (a) and (b) both, we primarily focus on finding online algorithms with
small competitive ratios. Moreover, for (a), we also show how to bound the
dynamic regret using the corresponding analysis for the competitive ratio.

Throughout the paper we shall assume that $\mathcal{X}$ is a non-empty closed
convex set and contains the point $\mathbf{0}$. An additional assumption about
the compactness of $\mathcal{X}$ is made in Sec. 5.3 while bounding the
dynamic regret. Moreover, for bounding the cost attained by our proposed
algorithm $\mathcal{A}_{o}$, $C_{\mathcal{A}_{o}}$ (5), we assume that the
optimizers ${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$.
Discussion about this assumption can be found in Remark 2. Note that all
algorithms for (5), start from the same starting point
${\boldsymbol{x}}_{0}\in\mathcal{X}$.

For solving (7), as far as we know only the full information setting is
assumed, where $f_{t}$ is revealed completely before ${\boldsymbol{x}}_{t}$ is
chosen. Because of the switching cost, even in the full information setting,
solving (7) remains non-trivial. The full information setting requires
incredibly large amount of information compared to the limited information
setting in which OCO is studied, and is not reasonable to assume for many
applications. Thus, in this paper we intend to solve (7) under the limited
information setting, where in particular we make the following assumption.

######  A1.

At time $t$, $\mathcal{A}$ takes action ${\boldsymbol{x}}_{t}$ with only
gradient information about $f_{t-1}$ at multiple points.

From [27], we know that if functions $f_{t}$’s are just convex and the
switching cost is quadratic, the competitive ratio (7) of any online algorithm
even in the full information setting is unbounded. Similarly, from [36], we
know that the competitive ratio of any online algorithm when the switching
cost is linear in the full information setting is $\Omega(\sqrt{d})$ and is
therefore arbitarily large for high problem dimensionality. Thus, similar to
prior work for solving (7), we assume the following:

######  A2.

For all $1\leq t\leq T$, the function $f_{t}:\mathcal{X}\to\mathbb{R}^{+}$ is
$L$-smooth and $\mu$-strongly convex. Mathematically, this implies
$\frac{\mu}{2}\left\|{\boldsymbol{y}}-{\boldsymbol{x}}\right\|^{2}\leq
f_{t}({\boldsymbol{y}})-f_{t}({\boldsymbol{x}})-\langle\nabla
f_{t}({\boldsymbol{x}}),{\boldsymbol{y}}-{\boldsymbol{x}}\rangle\leq\frac{L}{2}\left\|{\boldsymbol{y}}-{\boldsymbol{x}}\right\|^{2},$
for all ${\boldsymbol{x}},{\boldsymbol{y}}\in\mathcal{X}$.

Note that with the full information setting, $L$-smoothness is not necessary,
however, we need it since we are working with the limited information setting.

We next propose a simple algorithm and bound its competitive ratio for both
the quadratic switching cost as well as linear switching cost separately. The
challenge in proposing algorithms and analysing them in the limited
information setting compared to the full information setting has been
discussed in the Introduction 1.

###  4 Algorithm

Let
$\mathcal{P}_{\mathcal{X}}\left({\boldsymbol{x}}\right):=\operatorname*{arg\,min}_{{\boldsymbol{y}}\in\mathcal{X}}\left\|{\boldsymbol{y}}-{\boldsymbol{x}}\right\|$
be the projection of point ${\boldsymbol{x}}$ onto set $\mathcal{X}$. We
consider the online multiple gradient descent (OMGD) algorithm (Algorithm 1)
for minimizing the cost (5) that was originally proposed for minimizing the
dynamic regret for OCO. The OMGD algorithm is a very simple algorithm that
takes $K$ gradient descent steps (if it can) with respect to the objective
function $f_{t-1}$ at each time $t$. Notably, it is disregarding the presence
of the switching cost in (5). The presence of the switching cost with OCO-S
makes the analysis of OMGD different from [13].

Algorithm 1 Online Multiple Gradient Descent (OMGD) for OCO-S

1: Input: Problem parameters, i.e., ${\boldsymbol{x}}_{0}(\text{starting
point)},\mathcal{X}(\text{feasible set}),L(\text{smoothness parameter})$;

2: Choose ${\boldsymbol{x}}_{1}={\boldsymbol{x}}_{0}$;

3: for $t=2,\ldots,T$

4: Set ${\boldsymbol{z}}_{t}^{(0)}={\boldsymbol{x}}_{t-1}$;

5: for $k=1,\ldots,K$

6: Query $\nabla f_{t-1}({\boldsymbol{z}}_{t}^{(k-1)})$;

7: Update
${\boldsymbol{z}}_{t}^{(k)}=\mathcal{P}_{\mathcal{X}}\left({\boldsymbol{z}}_{t}^{(k-1)}-\frac{1}{L}\nabla
f_{t-1}({\boldsymbol{z}}_{t}^{(k-1)})\right)$;

8: end

9: Choose ${\boldsymbol{x}}_{t}={\boldsymbol{z}}_{t}^{(K)}$;

10: end

######  Remark 1.

Eventually, we are going to select $K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$ for
the OMGD algorithm thus requiring the knowledge of both $L,\mu$. Note that for
any gradient descent algorithm, the step size is typically a function of $L$.
Thus, over and above the usual assumption of the knowledge of $L$, we are also
assuming that $\mu$ is known ahead of time.

######  Remark 2.

We discuss the reason to assume that the optimizers
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$. We require this
assumption in Theorem 1 in order to set $\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})=\mathbf{0}$, and get an upper bound on the
cost ${C}_{\mathcal{A}_{o}}$ (5) (where $\mathcal{A}_{o}$ is the OMGD
algorithm) that is independent on the norm of the gradient $\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})$. If
${\boldsymbol{x}}_{t}^{\star}\notin\text{int}(\mathcal{X})$, we show in E that
as long as the quantity $\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}$ is sufficiently small, i.e.,
$\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}=\mathcal{O}\big{(}\mathcal{P}_{2,T}^{\star})$,
we can get the same order-wise (with respect to $L,\mu$) bound as Theorem 1.
It is worth noting that for deriving a lower bound in Lemma 5 on the cost (5)
incurred by $\mathsf{OPT}$, we do not make the assumption that
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$.

###  5 Quadratic Switching Cost

In this section, we consider (5) in the context of the quadratic switching
cost, i.e., the cost of an online algorithm $\mathcal{A}$ is given by

$\displaystyle
C_{\mathcal{A}}=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}.$
(8)

Note that in (8), we can also include a scaling factor $\delta>0$ for the
switching cost
$\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}$ that can
tradeoff the relative importance of the two costs. However, that is not
necessary since equivalently, $f_{t}$’s can be scaled by $\frac{1}{\delta}$,
changing their strong convexity parameter appropriately. Since our guarantees
will be a function of the strong convexity parameter, we just consider (8).

####  5.1 Competitive Ratio

#####  5.1.1 Upper Bounding the Cost of OMGD

Let $\mathcal{A}_{o}$ be the OMGD algorithm. We now proceed towards upper
bounding the total cost (8) of $\mathcal{A}_{o}$. Let, the action chosen by
$\mathcal{A}_{o}$ at time $t$ be ${\boldsymbol{x}}_{t}$. The following Lemma
establishes a bound on the quantity
$\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}$,
where
${\boldsymbol{x}}_{t}^{\star}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f_{t}({\boldsymbol{x}})$,
which can be interpreted as the cumulative progress of $\mathcal{A}_{o}$,
measured as squared distance from the optimizers
$\\{{\boldsymbol{x}}_{t}^{\star}\\}_{t=1}^{T}$. This quantity will be useful
in bounding both the total hitting cost and the total switching cost of
$\mathcal{A}_{o}$.

######  Lemma 1.

Under assumption A2, for $\mathcal{A}_{o}$ (Algorithm 1) with
$K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$, we have

$\displaystyle\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}\leq
2\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+4{\mathcal{P}}_{2,T}^{\star},$
(9)

where
${\mathcal{P}}_{2,T}^{\star}=\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}$.

${\mathcal{P}}_{2,T}^{\star}$ is the squared path length that captures the
squared distance between consecutive optimizers and is a quantity that
naturally controls the cost of any algorithm.

###### Proof.

At time $t\geq 2$, upon taking a gradient descent step from
${\boldsymbol{z}}_{t}^{(k-1)}$ to ${\boldsymbol{z}}_{t}^{(k)}$, the following
contraction holds for $\mathcal{A}_{o}$ from Lemma 16 (refer A) with
$\eta=\frac{1}{L}$:

$||{{\boldsymbol{z}}_{t}^{(k)}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}\leq\bigg{(}\frac{L-\mu}{L+\mu}\bigg{)}||{{\boldsymbol{z}}_{t}^{(k-1)}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}.$

Therefore, the net contraction after the end of $k$ gradient steps at time $t$
is

$||{{\boldsymbol{z}}_{t}^{(k)}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}\leq\bigg{(}\frac{L-\mu}{L+\mu}\bigg{)}^{k}||{{\boldsymbol{z}}_{t}^{(0)}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}.$

Since,
${\boldsymbol{z}}_{t}^{(0)}={\boldsymbol{x}}_{t-1},{\boldsymbol{x}}_{t}={\boldsymbol{z}}_{t}^{(K)}$,
the contraction for ${\boldsymbol{x}}_{t}$ compared to
${\boldsymbol{x}}_{t-1}$ is given by
$||{{\boldsymbol{x}}_{t}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}\leq\big{(}\frac{L-\mu}{L+\mu}\big{)}^{K}||{{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}.$

Since $e^{x}\geq 1+x,$ for all $x\in\mathbb{R}$, choosing
$K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$, we get

$\displaystyle\bigg{(}1-\frac{2\mu}{L+\mu}\bigg{)}^{K}\leq\exp\bigg{(}-\frac{2\mu}{L+\mu}\left\lceil{\frac{L+\mu}{2\mu}\ln
4}\right\rceil\bigg{)}\leq\exp\bigg{(}-\frac{2\mu}{L+\mu}{\frac{L+\mu}{2\mu}\ln
4}\bigg{)}=\frac{1}{4}.$

Therefore, we get

$\displaystyle||{{\boldsymbol{x}}_{t}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}\leq\frac{1}{4}||{{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}^{\star}_{t-1}}||^{2}.$
(10)

It is important for further exposition that the constant in the contraction
(10) is a constant. If $K=1$ in the OMGD algorithm, then the constant will
depend on $\mu$ and $L$ and will limit further analysis. Using (10), we have
the following:

$\displaystyle\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=2}^{T}(2\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}+2\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}),$
$\displaystyle\stackrel{{\scriptstyle\text{\eqref{one_fourth_0}}}}{{\leq}}\frac{1}{2}\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star}\leq\frac{1}{2}\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star},$
(11)

where to get $(a)$ we have used the Triangle inequality followed by
$\left\|{\boldsymbol{u}}+{\boldsymbol{v}}\right\|^{2}\leq
2(\left\|{\boldsymbol{u}}\right\|^{2}+\left\|{\boldsymbol{v}}\right\|^{2})$.

Rearranging (11), we obtain
$\sum_{t=2}^{T}||{{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}}||^{2}\leq||{{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}||}^{2}+4{\mathcal{P}}_{2,T}^{\star}\implies\sum_{t=1}^{T}||{{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}}||^{2}\leq
2||{{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}}||^{2}+4{\mathcal{P}}_{2,T}^{\star}.$
This completes the proof. ∎

######  Remark 3.

From the discussion above, we know that at time $t$, OMGD can obtain
$\frac{1}{4}$-th contraction by performing gradient descent, using at most
$K=\mathcal{O}(\frac{L}{\mu})$ gradient steps. However, by using Nesterov
Accelerated Gradient (NAG), i.e., at time $t$, instead of performing $K$
gradient steps, execute $K$ steps of NAG, we can show that the number of steps
can be substantially reduced. In B, we show that
$K={\mathcal{O}}(\sqrt{\frac{L}{\mu}}\log{\frac{L}{\mu}})$ gradient steps are
sufficient to obtain $\frac{1}{4}$-th contraction (10).

The next Lemma bounds the total hitting cost
$\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})$ of $\mathcal{A}_{o}$.

######  Lemma 2.

Under assumption A2, the total hitting cost
$\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})$ of $\mathcal{A}_{o}$ with
$K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$ is bounded by

$\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+(L+\alpha)(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star}),$

for any $\alpha>0$.

The proof of Lemma 2 follows from the smoothness of $f_{t}$’s and can be found
in C. Note that for the OMGD algorithm, the contraction obtained in (10) is
with respect to the preceding optimizer ${\boldsymbol{x}}_{t-1}^{\star}$, and
the fact that all functions $f_{t}$’s have Lipschitz continuous gradients, it
is not surprising that we can upper bound the total hitting cost of
$\mathcal{A}_{o}$. What is not obvious is that it can also be used to upper
bound the total switching cost of $\mathcal{A}_{o}$ which we do in the
following manner in Lemma 3: (a) By applying the Triangle inequality and the
contraction result (10), we relate
$\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}$
with
$\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}$;
(b) Finally, applying the result of Lemma 1, we relate
$\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}$
with $\mathcal{P}_{2,T}^{\star}$.

Recall that the OMGD algorithm by itself does not have any feature to control
the switching cost.

######  Lemma 3.

Under assumption A2, for $\mathcal{A}_{o}$ with $K=\lceil\frac{L+\mu}{2\mu}\ln
4\rceil$, the total switching cost is bounded by

$\sum_{t=1}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\leq
5\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+10{\mathcal{P}}_{2,T}^{\star}.$

###### Proof.

Using the triangle inequality followed by
$\left\|{\boldsymbol{u}}+{\boldsymbol{v}}\right\|^{2}\leq
2(\left\|{\boldsymbol{u}}\right\|^{2}+\left\|{\boldsymbol{v}}\right\|^{2})$,
we obtain the following for all $t\geq 2$:

$\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\leq
2\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}+2\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}\stackrel{{\scriptstyle\text{\eqref{one_fourth_0}}}}{{\leq}}\frac{5}{2}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}.$

Hence, the total switching cost of $\mathcal{A}_{o}$ can be bounded by

$\displaystyle\sum_{t=1}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=2}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{t=1}^{T-1}\frac{5}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2},$
$\displaystyle\stackrel{{\scriptstyle\text{\eqref{actual_squared_bound}}}}{{\leq}}5\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+10{\mathcal{P}}_{2,T}^{\star},$

where $(a)$ follows since $\mathcal{A}_{o}$ chooses
${\boldsymbol{x}}_{1}={\boldsymbol{x}}_{0}$, $(b)$ follows from
$\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\leq\frac{5}{2}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}$
established above. This completes the proof. ∎

Finally, combining Lemma 2 and Lemma 3, we get the following Lemma that bounds
the total cost of $\mathcal{A}_{o}$.

######  Lemma 4.

Under Assumption A2, the total cost (8) of $\mathcal{A}_{o}$ with
$K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$ is bounded by

$C_{\mathcal{A}_{o}}\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+(L+\alpha+5)(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star}),$

for any $\alpha>0$.

#####  5.1.2 Lower bounding the cost of $\mathsf{OPT}$

In this section, we lower bound the cost of $\mathsf{OPT}$ (8). Without loss
of generality, the starting location for all algorithms is
${\boldsymbol{x}}_{0}=\mathbf{0}$. For deriving Lemma 5, we do not need the
assumption that ${\boldsymbol{x}}_{t}^{\star}\in\text{int}({\mathcal{X}})$.

######  Lemma 5.

Under assumption A2, the cost incurred by the $\mathsf{OPT}$ (8) satisfies

$\displaystyle{C_{\mathsf{OPT}}\geq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}^{\star}_{t})+\frac{\mu}{2(\mu+4)}\big{(}{\mathcal{P}}_{2,T}^{\star}+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}\big{)}.}$
(12)

To prove Lemma 5, we do the following: Using the strong convexity of
$f_{t}$’s, first, we lower bound $C_{\mathsf{OPT}}$ by an optimization problem
of the following quadratic form:

$C_{\mathsf{OPT}}\geq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{\\{\tilde{{\boldsymbol{x}}}_{k}\in\mathbb{R}^{T}\\}_{k=1}^{d}}\sum_{k=1}^{d}\psi(\tilde{{\boldsymbol{x}}}_{k}),$

where we perform a change of variable by
$\tilde{{\boldsymbol{x}}}_{k}=[x_{1}^{(k)},\ldots,x_{T}^{(k)}]^{{\mathsf{T}}}\in\mathbb{R}^{T}$,
where $T$ is the time horizon. The function
$\psi(\tilde{{\boldsymbol{x}}}_{k})$ is defined as

$\psi(\tilde{{\boldsymbol{x}}}_{k}):=\sum_{t=1}^{T}\big{(}\frac{\mu}{2}(x_{t}^{(k)}-x_{t}^{\star(k)})^{2}+\frac{1}{2}(x_{t}^{(k)}-x_{t-1}^{(k)})^{2}\big{)}=\frac{\mu}{2}(\tilde{{\boldsymbol{x}}}_{k}-\tilde{{\boldsymbol{x}}}_{k}^{\star})^{{\mathsf{T}}}(\tilde{{\boldsymbol{x}}}_{k}-\tilde{{\boldsymbol{x}}}_{k}^{\star})+\frac{1}{2}\tilde{{\boldsymbol{x}}}_{k}^{{\mathsf{T}}}{\boldsymbol{B}}\tilde{{\boldsymbol{x}}}_{k},$

where
$\tilde{{\boldsymbol{x}}}_{k}^{\star}=[x_{1}^{\star(k)},\dots,x_{T}^{\star(k)}]$,
and the matrix ${\boldsymbol{B}}$ given by (41) is of dimension $T\times T$.
Clearly, $\psi(\tilde{{\boldsymbol{x}}}_{k})$ is a quadratic function in
$\tilde{{\boldsymbol{x}}}_{k}$. Further, we define a matrix
${\boldsymbol{A}}:={\boldsymbol{B}}+\mu{\boldsymbol{I}}$ and bound the
eigenvalues of ${\boldsymbol{A}}$ using the Gershgorin’s Circle Theorem [38,
Thm. 6.1.1] by exploiting the special structure of ${\boldsymbol{B}}$. In
particular, we show that
$\lambda_{i}\big{(}\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}\big{)}\leq
1+\frac{\mu}{\mu+4},$ for all $1\leq i\leq T$. Combining these results, we get
the required lower bound (12). The full proof is rather long and can be found
in D.

######  Remark 4.

When $f_{t}=f,$ for all $1\leq t\leq T$, a simpler proof is possible for Lemma
5 and can be found in Lemma 20 of D.

######  Remark 5 (Upper bound on the cost incurred by the $\mathsf{OPT}$).

Unlike the lower bound (Lemma 5), the upper bound on $C_{\mathsf{OPT}}$ is
straightforward. Observe that setting
${\boldsymbol{x}}_{t}={\boldsymbol{x}}_{t}^{\star}$ in (8), gives us the
following:
$C_{\mathsf{OPT}}\leq\sum_{t=1}^{T}\big{(}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}^{\star}_{t-1}\right\|^{2}\big{)}=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2}({\mathcal{P}}_{2,T}^{\star}+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2})$,
which is similar to (12).

#####  5.1.3 Bounding the Competitive Ratio of OMGD

Combining Lemma 4 and Lemma 5, we upper bound the competitive ratio of
$\mathcal{A}_{o}$ (the OMGD algorithm) as follows.

######  Theorem 1.

Under assumption A2, and assuming that the minimizers
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$, the competitive
ratio of the OMGD algorithm $\mathcal{A}_{o}$ satisfies

${\text{cr}_{\mathcal{A}_{o}}=\frac{C_{\mathcal{A}_{o}}}{C_{\mathsf{OPT}}}\leq
4(L+5)+\frac{16(L+5)}{\mu}.}$

###### Proof.

Using the result of Lemma 5 and $\frac{\mu}{2(\mu+4)}<1$, we obtain
$C_{\mathsf{OPT}}\geq\frac{\mu}{2(\mu+4)}\big{(}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+{\mathcal{P}}_{2,T}^{\star}+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}\big{)}.$
From Lemma 4, we have

$\displaystyle
C_{\mathcal{A}_{o}}\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+(L+\alpha+5)(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star}).$
(13)

Since ${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$, we have
$\nabla f_{t}({\boldsymbol{x}}_{t}^{\star})=\mathbf{0}$. Taking $\lim\alpha\to
0$ in (13), we obtain

$\displaystyle
C_{\mathcal{A}_{o}}\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+(L+5)(\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star})\leq(2L+10)\big{(}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+{\mathcal{P}}_{2,T}^{\star}\big{)}.$

Taking the ratio of the obtained bounds on $C_{\mathcal{A}_{o}}$ and
$C_{\mathsf{OPT}}$ completes the proof. ∎

######  Remark 6.

In this remark, we generalize the competitive ratio attained by the OMGD
algorithm $\mathcal{A}_{o}$ against the $\mathsf{OPT}$ (7), to an arbitrary
comparator sequence chosen by an user. Formally, let
${\boldsymbol{u}}=({\boldsymbol{u}}_{1},\dots,{\boldsymbol{u}}_{T})$ be an
user-specified comparator sequence. The competitive ratio of an online
algorithm $\mathcal{A}$ that takes an action ${\boldsymbol{x}}_{t}$ at time
$t$, with respect to ${\boldsymbol{u}}$ is defined as

$\displaystyle\text{cr}_{\mathcal{A}}^{\boldsymbol{u}}:=\frac{\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+c({\boldsymbol{x}}_{t},{\boldsymbol{x}}_{t-1})}{\sum_{t=1}^{T}f_{t}({\boldsymbol{u}}_{t})+c({\boldsymbol{u}}_{t},{\boldsymbol{u}}_{t-1})}.$
(14)

Note that if the comparator sequence corresponds to the sequence of optimal
actions
$({\boldsymbol{x}}_{1}^{\mathsf{OPT}},\dots,{\boldsymbol{x}}_{T}^{\mathsf{OPT}})$
chosen by the $\mathsf{OPT}$, (14) corresponds to the competitive ratio
against the $\mathsf{OPT}$ (7). When the switching cost is quadratic, from the
proof of Theorem 1, we have
$C_{\mathcal{A}_{o}}\leq(2L+10)\big{(}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+{\mathcal{P}}_{2,T}^{\star}\big{)}$.
Therefore, $\text{cr}_{\mathcal{A}_{o}}^{{\boldsymbol{u}}}$ can be upper
bounded by

$\displaystyle\text{cr}_{\mathcal{A}_{o}}^{{\boldsymbol{u}}}\leq(2L+10)\frac{\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}}{\sum_{t=1}^{T}f_{t}({\boldsymbol{u}}_{t})+\frac{1}{2}\left\|{\boldsymbol{u}}_{t}-{\boldsymbol{u}}_{t-1}\right\|^{2}}\stackrel{{\scriptstyle(a)}}{{\leq}}4(L+5)\bigg{(}1+\frac{4}{\mu}\bigg{)},$

where we have defined ${\boldsymbol{x}}_{0}^{\star}\coloneqq\mathbf{0}$ and
$(a)$ follows from [34, Thm. 2], which states that

$\displaystyle\frac{\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}}{\sum_{t=1}^{T}f_{t}({\boldsymbol{u}}_{t})+\frac{1}{2}\left\|{\boldsymbol{u}}_{t}-{\boldsymbol{u}}_{t-1}\right\|^{2}}\leq
1+\frac{4}{\mu},$

for any ${\boldsymbol{u}}$. Therefore, our result on the total cost
$C_{\mathcal{A}_{o}}$ attained by OMGD, naturally allows us to generalize the
notion of competitive ratio to arbitrary comparator sequences.

Discussion: It is instructive to compare our result in Theorem 1 with that of
algorithms proposed in [26], called OBD, and [27], called Regularized OBD,
under the full information setting. When all functions $f_{t}$’s are assumed
to be strongly convex with strong convexity parameter $\mu$, the competitive
ratio of OBD is at most $3+\mathcal{O}(\frac{1}{\mu})$ [26] while the
competitive ratio of Regularized OBD is at most
$\frac{1}{2}\big{(}1+\sqrt{1+\frac{4}{\mu}}\big{)}$ [27]. Note that both these
algorithms require full information about the function $f_{t}$ before choosing
action ${\boldsymbol{x}}_{t}$ for their implementation. A lower bound of
$\Omega(\frac{1}{\sqrt{\mu}})$ as $\mu\to 0$ on the competitive ratio of all
algorithms under the full information setting has also been derived in [27],
showing that Regularized OBD is orderwise optimal.

Our result in Theorem 1 shows that as $\mu\to 0$, when $L=c\mu$, for some
finite constant $c\geq 1$ (that is independent of $T$ and all other problem
parameters), the competitive ratio of OMGD is bounded by
$\mathcal{O}(\frac{1}{\mu})$ which matches the bound of OBD [26] which is
surprising, since OBD requires full information while OMGD works with limited
information. As a function of $\mu$, there is an orderwise gap between the
lower bound $\Omega(\frac{1}{\sqrt{\mu}})$ [27] that is applicable under the
full information setting and the competitive ratio of OMGD. Therefore, a
natural question is: can the lower bound be improved in the limited
information setting. In the next section, we show that the upper bound
obtained in Theorem 1 is orderwise tight for the OMGD algorithm.

Also note that Theorem 1 shows that the competitive ratio of OMGD algorithm
depends on both $L,\mu$ in contrast to OBD or Regularized OBD whose bounds
only depend on $\mu$. This is a manifestation of the limited information
setting. In the next section, we also show that the competitive ratio of any
algorithm scales linearly with $L$ in the limited information setting.

####  5.2 Lower Bounds on the Competitive Ratio

We begin by showing that the upper bound on the competitive ratio of the OMGD
algorithm obtained in Theorem 1 is order-wise (with respect to $L,\mu$) tight.

######  Lemma 6.

There exists a sequence of functions that satisfy assumption A2, such that the
competitive ratio of the OMGD algorithm is lower bounded by

$\displaystyle\text{cr}_{\mathcal{A}_{o}}=\frac{C_{\mathcal{A}_{o}}}{{C_{\mathsf{OPT}}}}\geq
1+\frac{L+1}{4\mu}+\frac{L+1}{8}.$

The proof of Lemma 6 in F in fact shows that any algorithm, that at time $t$,
chases the optimizer ${\boldsymbol{x}}_{t-1}^{\star}$ has the same order-wise
competitive ratio lower bound as given by Lemma 6. By chasing the optimizer
${\boldsymbol{x}}_{t-1}^{\star}$ at time $t$, we mean that
$||{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}||<c||{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}||$
for some constant $0<c<1$ that is independent of all parameters of the problem
instance. Hence, we actually get the following result.

######  Lemma 7.

In the limited information setting, there exists a sequence of functions that
satisfy assumption A2, such that the competitive ratio of any algorithm
$\mathcal{A}$ that at time $t$, chases the optimizer
${\boldsymbol{x}}_{t-1}^{\star}$ is lower bounded by

$\displaystyle\text{cr}_{\mathcal{A}}=\frac{C_{\mathcal{A}}}{{C_{\mathsf{OPT}}}}\geq\Omega\bigg{(}\frac{L}{\mu}+L+\frac{1}{\mu}\bigg{)}.$

Considering the problem instance used to derive Lemma 6, it is clear that to
avoid the competitive ratio lower bound of Lemma 6 $\Omega(\frac{L}{\mu})$
when $\mu$ is small or $L$ is large, an algorithm has to move slowly (making
it a function of $\mu$ or $L$) at time $t=2$ from its current position
${\boldsymbol{x}}_{1}=\mathbf{0}$. This observation gives rise to the
consideration of the following class of slow algorithms that satisfy the
property
$||{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}||>||{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}||-\epsilon_{t}$,
where $\epsilon_{t}=\mathcal{O}(\mu)$ or $\mathcal{O}\left(\frac{1}{L}\right)$
for all $t$, where $\mu$ is small and $L$ is large. Since we are interested in
bounds depending on $\mu$ and $L$, and $L\geq\mu$ by definition, the regime of
interest for lower bounds are $\mu\rightarrow 0$ and $L\rightarrow\infty$. We
next show that slow algorithms cannot do better than OMGD in terms of the
competitive ratio.

######  Lemma 8.

In the limited information setting, there exists a sequence of functions that
satisfy assumption A2, such that the competitive ratio of any slow algorithm
$\mathcal{A}$ is lower bounded by

$\text{cr}_{\mathcal{A}}=\frac{C_{\mathcal{A}}}{{C_{\mathsf{OPT}}}}\geq\max\big{\\{}\Omega\left(\frac{1}{\mu}\right),\Omega\left(L^{2}\right)\big{\\}}.$

The proof of Lemma 8 can be found in G. Note that the union of
${\boldsymbol{x}}_{t-1}^{\star}$ chasing or slow algorithms does not cover the
class of all algorithms. Next, we present universal lower bounds that apply
for all algorithms. We begin by showing that with the information setting as
in assumption A1, the competitive ratio of any online algorithm is
$\Omega(L)$.

######  Lemma 9.

Under assumptions A1, A2, the competitive ratio of any online algorithm is at
least $L$.

The proof of Lemma 9 can be found in H. The $\Omega(L)$ bound in Lemma 9 can
be improved to $\Omega\big{(}\frac{L}{\sqrt{\mu}}\big{)}$ as $\mu\to 0$, which
is stated by the following Lemma.

######  Lemma 10.

Under assumptions A1, A2, the competitive ratio of any online algorithm is at
least $\Omega\big{(}\frac{L}{\sqrt{\mu}}\big{)}$ as $\mu\to 0$.

The proof of Lemma 10 can be found in I and follows by constructing an input
sequence for which the cost of any online algorithm $\mathcal{A}$ is
$C_{\mathcal{A}}=\Omega(L)$, while $C_{\mathsf{OPT}}=\mathcal{O}(\sqrt{\mu})$
as $\mu\to 0$. Finally, combining Lemma 9 and Lemma 10, we get the
$\max\\{\Omega(L),\Omega(\frac{L}{\sqrt{\mu}})\\}$ lower bound on the
competitive ratio of any online algorithm $\mathcal{A}$.

####  5.3 Dynamic Regret

In this section, we show that the OMGD algorithm attains a near optimal
dynamic regret (6) (order-wise with respect to the path length) under the
limited information setting. In order to upper bound the dynamic regret, we
assume, similar to [33] that $f_{t}$’s have bounded gradients however, relax
the assumption ${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$ that
was required for deriving Theorem 1.

######  A3.

For all $1\leq t\leq T$, there exists a finite constant $G<\infty$, such that
$\max_{{\boldsymbol{x}}\in\mathcal{X}}\left\|\nabla
f_{t}({\boldsymbol{x}})\right\|=G$.

With a generic lower bound on $C_{\mathsf{OPT}}$ (12) under our belt and the
contraction
$\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}\right\|\leq\frac{1}{2}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|$
(10) attained by OMGD with $K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$, it is easy
to bound the dynamic regret attained by the OMGD algorithm. As usual, we shall
assume ${\boldsymbol{x}}_{0}=\mathbf{0}$ as the starting point of all
algorithms.

######  Theorem 2.

Under assumptions A2, A3, the dynamic regret of $\mathcal{A}_{o}$ (Algorithm
1) with $K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$ is upper bounded by

$R_{d}(\mathcal{A}_{o})\leq
2G(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star})+5\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+\bigg{(}10-\frac{\mu}{2(\mu+4)}\bigg{)}\mathcal{P}_{2,T}^{\star}.$

The proof of Theorem 2 is similar to the proof of Theorem 1 and can be found
in J. The following Corollary shows that when the non-empty closed convex set
$\mathcal{X}$ has a finite diameter $D$, where
$\max_{{\boldsymbol{x}},{\boldsymbol{y}}\in\mathcal{X}}\left\|{\boldsymbol{x}}-{\boldsymbol{y}}\right\|=D$,
the dynamic regret ${R}_{d}(\mathcal{A}_{o})$ of the OMGD algorithm is
$\mathcal{O}\big{(}\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}\big{)}$.

######  Corollary 1.

Under assumptions A2, A3, and $\mathcal{X}$ is a non-empty closed convex set
with a finite diameter $D$, the dynamic regret of $\mathcal{A}_{o}$ is upper
bounded by

$R_{d}(\mathcal{A}_{o})\leq\bigg{(}2G+D\bigg{(}10-\frac{\mu}{2(\mu+4)}\bigg{)}\bigg{)}(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}).$

The proof of Corollary 1 follows from Theorem 2 by relating
$\mathcal{P}_{2,T}^{\star}$ with $\mathcal{P}_{T}^{\star}$ and can be found in
K. In [33], the delayed information setting is considered, where at time $t$,
an online algorithm $\mathcal{A}$ takes action ${\boldsymbol{x}}_{t}$ with
complete information about $f_{1},\dots,f_{t-1}$. In comparison to our
analysis, [33] showed that the online gradient descent algorithm that takes
only one gradient step under the delayed information setting achieves a regret
of
$\mathcal{O}\left(\frac{G}{1-\sqrt{1-\mu/L}}\big{(}1+\frac{1}{L}\big{)}(\mathcal{P}_{T}^{\star}+D)\right)$.
Thus, when $L\to 0$ and $\frac{L}{\mu}$ is finite, our bound is superior than
[33]. This will also reflect in Theorem 3 where we show that the OMGD
algorithm achieves the order-wise (with respect to the path length) optimal
regret.

A lower bound on the dynamic regret has been derived in [33] for the delayed
information setting. Given that the limited information setting is weaker than
the delayed information setting, this bound is valid for the limited
information setting as well, which we state next.

######  Lemma 11.

[33, Thm. 1] Consider $T\geq 1$, a closed convex set $\mathcal{X}$ with a
finite diameter $D$, and a constant $V_{T}$ s.t. $0\leq V_{T}\leq DT$. For any
deterministic online algorithm $\mathcal{A}$ for (8) under the delayed
information setting, there exists a sequence of quadratic functions
$\\{f_{t}\\}_{t=1}^{T}$ that are $\mu$-smooth and $\mu$-strongly convex on
$\mathbb{R}^{d}$, satisfy $\max_{{\boldsymbol{x}}\in\mathcal{X}}\left\|\nabla
f_{t}({\boldsymbol{x}})\right\|\leq(3\mu+1),$ for all $1\leq t\leq T$, and
$\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}\leq
V_{T}$, s.t.

$\displaystyle R_{d}(\mathcal{A})\geq\zeta DV_{T}\geq\zeta
D(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}),$ (15)

where
$\zeta=\frac{\mu^{3}(1-\rho)^{2}}{32(\mu+1)^{2}},\rho=\frac{\sqrt{\mu+4}-\sqrt{\mu}}{\sqrt{\mu+4}+\sqrt{\mu}}$.

Thus, we get the main result of this section.

######  Theorem 3.

The dynamic regret of the OMGD algorithm is order-wise (with respect to the
path length) optimal in the limited information setting when assumptions A2,
A3 hold, and $\mathcal{X}$ is a non-empty closed convex set with a finite
diameter $D$.

###### Proof.

The proof follows by combining Corollary 1 and Lemma 11. ∎

It is also interesting to study the regret bound of the OMGD algorithm under
the regime when $\mathcal{X}$ is a non-empty closed convex set and
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$, but $\mathcal{X}$ is
not necessarily bounded. In this case, $R_{d}(\mathcal{A}_{o})$ can be bounded
as

$\displaystyle
R_{d}(\mathcal{A}_{o})\leq\big{(}2L+10-\frac{\mu}{2\mu+8}\big{)}V_{T}^{2},$
(16)

as $V_{T}\to 0^{+}$. The proof of (16) and discussion regarding $V_{T}\to
0^{+}$ is provided in L. Comparing (16) with Lemma 11, we can conclude that
the lower bound on the dynamic regret derived in Lemma 11 ($\Omega(V_{T})$)
can be avoided in case $\mathcal{X}$ does not have a finite diameter and
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$ which is always true
if $\mathcal{X}={\mathbb{R}}^{d}$. To derive Lemma 11, the construction of
‘bad’ functions $\\{f_{t}\\}_{t=1}^{T}$ was such that the minimizer
${\boldsymbol{x}}_{t}^{\star}$ lied on the boundary of $\mathcal{X}$ and had a
non-zero gradient $\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|\neq 0$. Thus, a different lower
bound is necessitated when $\mathcal{X}$ does not have a finite diameter and
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$, compared to Lemma
11.

###  6 Linear Switching Cost

In this section, we consider (5) in the context of the linear switching cost,
i.e., the cost (5) of an online algorithm $\mathcal{A}$ is given by

$\displaystyle
C_{\mathcal{A}}=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|.$
(17)

Most of the results in this section are motivated from the derived results for
quadratic switching cost.

####  6.1 Competitive Ratio

#####  6.1.1 Upper Bounding the Cost (17) of OMGD

Compared to (8), (17) differs only in the switching cost. Thus, to analyze
OMGD $(\mathcal{A}_{o})$ with linear switching cost, we have to separately
bound the total switching cost, which we do as follows similar to Lemma 3.

######  Lemma 12.

Under assumption A2, for $\mathcal{A}_{o}$ with
$K=\lceil\frac{L+\mu}{2\mu}{\ln 4}\rceil$, the total switching cost is bounded
by

$\displaystyle\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\leq
3\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+3\mathcal{P}_{T}^{\star}.$

###### Proof.

We begin by bounding the quantity
$\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|$
for $\mathcal{A}_{o}$ in the following manner:

$\displaystyle\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=2}^{T}\big{(}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}\right\|+\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|\big{)},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{t=2}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|+\mathcal{P}_{T}^{\star},$
$\displaystyle=\frac{1}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+\sum_{t=2}^{T-1}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|+\mathcal{P}_{T}^{\star},$
$\displaystyle\leq\frac{1}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+\sum_{t=2}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|+\mathcal{P}_{T}^{\star},$

where $(a)$ follows from the Triangle inequality, while $(b)$ follows from the
contraction bound (10) attained by $\mathcal{A}_{o}$. Rearranging, we obtain

$\displaystyle\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|\leq\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+2\mathcal{P}_{T}^{\star}\implies\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|\leq
2\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+2\mathcal{P}_{T}^{\star}.$
(18)

The overall switching cost of $\mathcal{A}_{o}$ can therefore be bounded as

$\displaystyle\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{t=2}^{T}\big{(}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}\right\|+\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|\big{)}\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{3}{2}\sum_{t=1}^{T-1}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|,$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}3\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+3\mathcal{P}_{T}^{\star},$

where $(a)$ follows since ${\boldsymbol{x}}_{1}={\boldsymbol{x}}_{0}$, $(b)$
follows from the Triangle inequality, $(c)$ follows from (10), and $(d)$
follows from (18), derived above. ∎

Finally, combining Lemma 2 (total hitting cost of $\mathcal{A}_{o}$) and Lemma
12 (total switching cost of ${\mathcal{A}_{o}}$), we get a bound on the total
cost (17) attained by $\mathcal{A}_{o}$.

######  Lemma 13.

Under assumption A2, the total cost of $\mathcal{A}_{o}$ (17) with
$K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$ is bounded by

$C_{\mathcal{A}_{o}}\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+(L+\alpha)(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star})+3\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|+3\mathcal{P}_{T}^{\star},$

for any $\alpha>0$.

Observe from Lemma 13 that the total cost $C_{\mathcal{A}_{o}}$ depends on
both $\mathcal{P}_{2,T}^{\star}$ and $\mathcal{P}_{T}^{\star}$, unlike the
quadratic switching cost case where the total cost, given by Lemma 4, depends
only on $\mathcal{P}_{2,T}^{\star}$. This is a manifestation of the linear
switching cost. In the next section, we show that the total cost of the
$\mathsf{OPT}$, $C_{\mathsf{OPT}}$, also depends on both
$\mathcal{P}_{2,T}^{\star}$ and $\mathcal{P}_{T}^{\star}$.

#####  6.1.2 Lower Bounding the cost of the $\mathsf{OPT}$

In this section, we derive a lower bound on $C_{\mathsf{OPT}}$ for the linear
switching cost problem by reducing the linear switching cost problem to a
particular instance of the quadratic switching cost problem, and then reusing
the lower bound on $C_{\mathsf{OPT}}$ for the quadratic switching cost problem
(Lemma 5). Similar to the quadratic switching cost case, we assume
${\boldsymbol{x}}_{0}=\mathbf{0}$ as the starting point of all algorithms.

######  Lemma 14.

Under assumption A2, the cost incurred by the $\mathsf{OPT}$ (17) satisfies

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle\geq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{2\mu(\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2})}{\mu(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+8}.$
(19)

###### Proof.

We begin by lower bounding $C_{\mathsf{OPT}}$ in the following manner:

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle=\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}f_{t}({\boldsymbol{x}}_{t})+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\big{)},$
$\displaystyle\stackrel{{\scriptstyle\ref{function_structure}}}{{\geq}}\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}f_{t}({\boldsymbol{x}}_{t}^{\star})+\langle\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star}),{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\rangle+\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\big{)},$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\big{)},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t-1}^{\omega}\right\|\big{)},$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\frac{1}{2U}\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t-1}^{\omega}\right\|^{2}\big{)},$
$\displaystyle\geq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\frac{1}{2U}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\geq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{\mu}{\mu
U+4}\big{(}\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}\big{)},$
(20)

where $(a)$ follows from the optimality condition of
${\boldsymbol{x}}_{t}^{\star}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f_{t}({\boldsymbol{x}})$,
i.e., $\langle\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star}),{\boldsymbol{x}}-{\boldsymbol{x}}_{t}^{\star}\rangle\geq
0$, for all ${\boldsymbol{x}}\in\mathcal{X}$. To get $(b)$, we have defined

$\\{{\boldsymbol{x}}_{t}^{\omega}\\}_{t=1}^{T}:=\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\big{)},$

and in $(c)$ $U$ is such that
$\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t-1}^{\omega}\right\|\leq
2U$, for all $1\leq t\leq T$. To obtain $(d)$, we have used the result of
Lemma 5. It only remains to evaluate $U$ which we do as follows.

Since
$\\{{\boldsymbol{x}}_{t}^{\omega}\\}_{t=1}^{T}=\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\big{)}$,
we have the following:

$\displaystyle\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t-1}^{\omega}\right\|\big{)}\leq\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|,$
(21)

which follows by setting ${\boldsymbol{x}}_{t}={\boldsymbol{x}}_{t}^{\star}$
in the minimization
$\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|\big{)}$.
From (21), we obtain the following:

$\displaystyle\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t-1}^{\omega}\right\|\leq\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|\implies\left\|{\boldsymbol{x}}_{t}^{\omega}-{\boldsymbol{x}}_{t-1}^{\omega}\right\|\leq\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|,$

for all $1\leq t\leq T$. Therefore, it is sufficient to choose
$2U=\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|$.
Using this value of $U$ in (20), we get

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle\geq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{2\mu(\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2})}{\mu(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+8}.$

which completes the proof. ∎

#####  6.1.3 Bounding the Competitive Ratio of OMGD

Combining Lemma 13 and Lemma 14, we can bound the competitive ratio of
OMGD($\mathcal{A}_{o}$) for the linear switching cost case, for any value of
$f_{t}({\boldsymbol{x}}_{t}^{\star})$. However, to get a simplified expression
we consider $f_{t}({\boldsymbol{x}}_{t}^{\star})=0$ and derive the following
result.

######  Theorem 4.

Under assumption A2, and assuming that the minimizers
${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$ and
$f_{t}({\boldsymbol{x}}_{t}^{\star})=0$, the competitive ratio of the OMGD
algorithm $\mathcal{A}_{o}$ for the linear switching cost satisfies

$\displaystyle\text{cr}_{\mathcal{A}_{o}}=\frac{C_{\mathcal{A}_{o}}}{C_{\mathsf{OPT}}}\leq
L(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+\frac{3}{2}\frac{\big{(}\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|\big{)}^{2}}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}+\frac{8L}{\mu}+\frac{12}{\mu}\frac{\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}.$
(22)

###### Proof.

From Lemma 14, we have
$C_{\mathsf{OPT}}\geq\frac{2\mu(\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2})}{\mu(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+8}$.
Further, since ${\boldsymbol{x}}_{t}^{\star}\in\text{int}(\mathcal{X})$ and
$f_{t}({\boldsymbol{x}}_{t}^{\star})=0$, letting $\alpha\to 0$ in Lemma 13, we
have $C_{\mathcal{A}_{o}}\leq
2L(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+\mathcal{P}_{2,T}^{\star})+3(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star})$.
Taking the ratio of both the bounds completes the proof. ∎

Observe from Theorem 4, the competitive ratio of $\mathcal{A}_{o}$ depends on
$\mathcal{P}_{2,T}^{\star}$ and $\mathcal{P}_{T}^{\star}$, in addition to
$L,\mu$. This is in contrast to the competitive ratio of $\mathcal{A}_{o}$ for
the quadratic switching cost (Theorem 1), which solely depends on $L,\mu$.
Therefore, it is natural to consider whether the dependence of
$\mathcal{P}_{2,T}^{\star}$ and $\mathcal{P}_{T}^{\star}$ in the upper bound
of OMGD can be avoided. In the next section, we show that this dependence
cannot be avoided, by constructing a problem instance where the lower bound
for any online algorithm $\mathcal{A}$ depends on both
$\mathcal{P}_{2,T}^{\star}$ and $\mathcal{P}_{T}^{\star}$.

####  6.2 Lower Bound on the Competitive Ratio

To explicitly bring out the dependence of the lower bound for any online
algorithm $\mathcal{A}$ on $\mathcal{P}_{2,T}^{\star}$ and
$\mathcal{P}_{T}^{\star}$, we assume $\mu=L$ for simplicity. The following
Lemma shows that there exists a problem instance where the explicit dependence
of $\mathcal{P}_{2,T}^{\star}$ and $\mathcal{P}_{T}^{\star}$ in the lower
bound matches with the upper bound of OMGD (Theorem 4). The proof of Lemma 15
can be found in M and proceeds by creating two functions $f_{1},f_{2}$ s.t.
$f_{1}(x)=\frac{\mu}{2}(x-\theta)^{2}$, $f_{2}(x)=\frac{\mu}{2}x^{2}$. It can
be shown that for this choice of $f_{1},f_{2}$, any online algorithm
$\mathcal{A}$ incurs cost $C_{\mathcal{A}}$ which is quadratic in $\theta$
while $C_{\mathsf{OPT}}$ is linear in $\theta$. The ratio of $C_{\mathcal{A}}$
and $C_{\mathsf{OPT}}$ can then be appropriately expressed as $\frac{1}{8}$
times the quantity in (23).

######  Lemma 15.

In the limited information setting, there exists a sequence of functions that
satisfy assumption A2, such that the competitive ratio of any online algorithm
$\mathcal{A}$ for the linear switching cost problem is

$\displaystyle\Omega\bigg{(}\mu(\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|)+\frac{3}{2}\frac{\big{(}\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|\big{)}^{2}}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}+\frac{12}{\mu}\frac{\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|}{\mathcal{P}_{2,T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}}\bigg{)}.$
(23)

######  Remark 7.

In contrast to the quadratic switching cost case, the lower bound (Lemma 15)
on the competitive ratio of any online algorithm depends on both the path
length and the squared path length. An easy explanation for this can be
generated by restricting the strongly convex functions to the class of
strongly convex quadratic functions of the form
$f_{t}({\boldsymbol{x}})=\frac{\mu}{2}\left\|{\boldsymbol{x}}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}$.
In this case, when the switching cost is linear, choosing
${\boldsymbol{x}}_{t}={\boldsymbol{x}}_{t}^{\star}$, $\mathsf{OPT}$ only
incurs a cost of $\mathcal{P}_{T}^{\star}$, which however cannot be matched by
an online algorithm which ends up incurring a cost that is both a function of
$\mathcal{P}_{T}^{\star}$ and $\mathcal{P}_{2,T}^{\star}$. When the switching
cost is quadratic, however, choosing
${\boldsymbol{x}}_{t}={\boldsymbol{x}}_{t}^{\star}$, $\mathsf{OPT}$ also
incurs a cost of $\mathcal{P}_{2,T}^{\star}$, which is similar to that of an
online algorithm.

###  7 Conclusion

In this paper, we considered the OCO-S problem with quadratic and linear
switching cost in the limited information setting and proposed an algorithm
whose competitive ratio was shown to be order-wise (in terms of $L,\mu$) tight
when the objective functions are $L$-smooth and $\mu$-strongly convex, and the
switching cost is quadratic. Lower bounds on the competitive ratio of any
online algorithm for the quadratic switching cost are also derived, that show
that the linear dependence of $L$ on the competitive ratio is unavoidable. The
proposed algorithm is also shown to achieve the optimal order-wise (with
respect to the path length) dynamic regret in the limited information setting
when the feasible set is bounded and the switching cost is quadratic. We also
upper bounded the dynamic regret of the proposed algorithm when the feasible
set is unbounded, and showed that it can be smaller than the lower bound for
the case when the feasible set is bounded under a certain regime. Finally, we
showed that the linear switching cost problem is fundamentally different from
the quadratic switching cost problem, since the dependence of the squared path
length and path length on the competitive ratio is unavoidable for any online
algorithm in this case.

### References

  * [1] N. Srebro, K. Sridharan, A. Tewari, Smoothness, low noise and fast rates, Advances in neural information processing systems 23 (2010).
  * [2] P. Bartlett, E. Hazan, A. Rakhlin, Adaptive online gradient descent, in: Advances in Neural Information Processing Systems 20: Proceedings of the 2007 Conference, Neural Information Processing Systems (NIPS) Foundation, 2009, pp. 65–72.
  * [3] D. Garber, G. Korcia, K. Levy, Online convex optimization in the random order model, in: International Conference on Machine Learning, PMLR, 2020, pp. 3387–3396.
  * [4] E. Hazan, Introduction to online convex optimization, arXiv preprint arXiv:1909.05207 (2019).
  * [5] S. Shalev-Shwartz, et al., Online learning and online convex optimization, Foundations and trends in Machine Learning 4 (2) (2011) 107–194.
  * [6] M. Zinkevich, Online convex programming and generalized infinitesimal gradient ascent, in: Proc. Int. Conf. Mach. Learn., 2003, pp. 928–936.
  * [7] E. Hall, R. Willett, Dynamical models and tracking regret in online convex programming, in: International Conference on Machine Learning, PMLR, 2013, pp. 579–587.
  * [8] L. Zhang, S. Lu, Z.-H. Zhou, Adaptive online learning in dynamic environments, in: Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 1330–1340.
  * [9] O. Besbes, Y. Gur, A. Zeevi, Non-stationary stochastic optimization, Oper. Res. 63 (5) (2015) 1227–1244.
  * [10] A. Jadbabaie, A. Rakhlin, S. Shahrampour, K. Sridharan, Online optimization: Competing with dynamic comparators, in: Artificial Intelligence and Statistics, PMLR, 2015, pp. 398–406.
  * [11] T. Yang, L. Zhang, R. Jin, J. Yi, Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient, in: International Conference on Machine Learning, PMLR, 2016, pp. 449–457.
  * [12] A. Mokhtari, S. Shahrampour, A. Jadbabaie, A. Ribeiro, Online optimization in dynamic environments: Improved regret rates for strongly convex problems, in: 2016 IEEE 55th Conference on Decision and Control (CDC), IEEE, 2016, pp. 7195–7201.
  * [13] L. Zhang, T. Yang, J. Yi, R. Jin, Z.-H. Zhou, Improved dynamic regret for non-degenerate functions, Advances in Neural Information Processing Systems 30 (2017).
  * [14] P. Zhao, G. Wang, L. Zhang, Z.-H. Zhou, Bandit convex optimization in non-stationary environments, in: International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 1508–1518.
  * [15] L. Zhang, S. Lu, T. Yang, Minimizing dynamic regret and adaptive regret simultaneously, in: International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 309–319.
  * [16] P. Zhao, L. Zhang, Improved analysis for dynamic regret of strongly convex and smooth functions, in: Learning for Dynamics and Control, PMLR, 2021, pp. 48–59.
  * [17] T. Chen, G. B. Giannakis, Bandit convex optimization for scalable and dynamic iot management, IEEE Internet of Things Journal 6 (1) (2018) 1276–1286.
  * [18] X. Cao, K. R. Liu, Online convex optimization with time-varying constraints and bandit feedback, IEEE Transactions on automatic control 64 (7) (2018) 2665–2680.
  * [19] Q. Liu, W. Wu, L. Huang, Z. Fang, Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints, ACM SIGMETRICS Performance Evaluation Review 49 (3) (2022) 4–5.
  * [20] R. Vaze, On dynamic regret and constraint violations in constrained online convex optimization, in: 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), IEEE, 2022, pp. 9–16.
  * [21] M. Lin, A. Wierman, L. L. Andrew, E. Thereska, Dynamic right-sizing for power-proportional data centers, IEEE ACM Trans. Netw. 21 (5) (2012) 1378–1391.
  * [22] Y. Li, G. Qu, N. Li, Using predictions in online optimization with switching costs: A fast algorithm and a fundamental limit, in: 2018 Annual American Control Conference (ACC), IEEE, 2018, pp. 3008–3013.
  * [23] R. Mookherjee, B. F. Hobbs, T. L. Friesz, M. A. Rigdon, Dynamic oligopolistic competition on an electric power network with ramping costs and joint sales constraints, J. Ind. Manag. Optim 4 (3) (2008) 425–452.
  * [24] M. Tanaka, Real-time pricing with ramping costs: A new approach to managing a steep change in electricity demand, Energy Policy 34 (18) (2006) 3634–3643.
  * [25] N. Chen, G. Goel, A. Wierman, Smoothed online convex optimization in high dimensions via online balanced descent, in: Conference On Learning Theory, PMLR, 2018, pp. 1574–1594.
  * [26] G. Goel, A. Wierman, An online algorithm for smoothed regression and lqr control, in: The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 2504–2513.
  * [27] G. Goel, Y. Lin, H. Sun, A. Wierman, Beyond online balanced descent: An optimal algorithm for smoothed online optimization, Adv. Neural Inf. Process. Syst. 32 (2019).
  * [28] C. Argue, A. Gupta, G. Guruganesh, Dimension-free bounds for chasing convex functions, in: Conference on Learning Theory, PMLR, 2020, pp. 219–241.
  * [29] M. Lin, Z. Liu, A. Wierman, L. L. Andrew, Online algorithms for geographical load balancing, in: 2012 international green computing conference (IGCC), IEEE, 2012, pp. 1–10.
  * [30] L. Andrew, S. Barman, K. Ligett, M. Lin, A. Meyerson, A. Roytman, A. Wierman, A tale of two metrics: Simultaneous bounds on competitiveness and regret, in: Conference on Learning Theory, PMLR, 2013, pp. 741–763.
  * [31] N. Bansal, A. Gupta, R. Krishnaswamy, K. Pruhs, K. Schewior, C. Stein, A 2-competitive algorithm for online convex optimization with switching costs, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
  * [32] S. Albers, J. Quedenfeld, Optimal algorithms for right-sizing data centers, in: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018, pp. 363–372.
  * [33] Y. Li, G. Qu, N. Li, Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit, IEEE Trans. Autom. Control 66 (10) (2020) 4761–4768.
  * [34] L. Zhang, W. Jiang, S. Lu, T. Yang, Revisiting smoothed online learning, Advances in Neural Information Processing Systems 34 (2021) 13599–13612.
  * [35] N. Bansal, A. Gupta, R. Krishnaswamy, K. Pruhs, K. Schewior, C. Stein, A 2-competitive algorithm for online convex optimization with switching costs, in: APPROX/RANDOM 2015, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015\.
  * [36] N. Chen, G. Goel, A. Wierman, Smoothed online convex optimization in high dimensions via online balanced descent, in: Conference On Learning Theory, PMLR, 2018, pp. 1574–1594.
  * [37] A. Antoniadis, K. Schewior, A tight lower bound for online convex optimization with switching costs, in: International Workshop on Approximation and Online Algorithms, Springer, 2017, pp. 164–175.
  * [38] R. A. Horn, C. R. Johnson, Matrix analysis, Cambridge university press, 2012.
  * [39] Y. Nesterov, Introductory lectures on convex optimization: A basic course, Vol. 87, Springer Science & Business Media, 2003.
  * [40] J. M. Varah, A lower bound for the smallest singular value of a matrix, Linear Algebra and its applications 11 (1) (1975) 3–5.
  * [41] P. Concus, G. H. Golub, G. Meurant, Block preconditioning for the conjugate gradient method, SIAM Journal on Scientific and Statistical Computing 6 (1) (1985) 220–252.

## Appendices

###  Appendix A Lemma 16

The following result has been derived in [13] and is used in Lemma 1 for our
analysis.

######  Lemma 16.

[13, Lemma 5] Assume that $f:\mathcal{X}\to\mathbb{R}^{+}$ is $L$-smooth and
$\mu$-strongly convex, and
${\boldsymbol{x}}^{\star}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f({\boldsymbol{x}})$.
Let ${\boldsymbol{u}}\in\mathcal{X}$ be the current point, and let the new
point ${\boldsymbol{v}}=\mathcal{P}_{\mathcal{X}}({\boldsymbol{u}}-\eta\nabla
f({\boldsymbol{u}}))$ be obtained by using a single gradient descent step with
step size $\eta$, where $\eta\leq\frac{1}{L}$. Then,

$||{{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}}||^{2}\leq\bigg{(}1-\frac{2\mu}{\frac{1}{\eta}+\mu}\bigg{)}||{{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}}||^{2}.$

###### Proof.

Observe that the update
${\boldsymbol{v}}=\mathcal{P}_{\mathcal{X}}({\boldsymbol{u}}-\eta\nabla
f({\boldsymbol{u}}))$ can be expressed as the following:

$\displaystyle{\boldsymbol{v}}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{x}}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{x}}-{\boldsymbol{u}}\right\|^{2}.$
(24)

Next, consider a function $g:\mathcal{X}\to\mathbb{R}^{+}$, which is
$\lambda$-strongly convex. Denote
${\boldsymbol{x}}_{g}^{\star}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}g({\boldsymbol{x}})$,
which implies that

$\displaystyle\langle\nabla
g({\boldsymbol{x}}_{g}^{\star}),{\boldsymbol{x}}-{\boldsymbol{x}}_{g}^{\star}\rangle\geq
0,\forall{\boldsymbol{x}}\in\mathcal{X}.$ (25)

From the $\lambda$-strong convexity of $g$ over $\mathcal{X}$ we have the
following for all ${\boldsymbol{x}}\in\mathcal{X}$:

$\displaystyle g({\boldsymbol{x}})$ $\displaystyle\geq
g({\boldsymbol{x}}_{g}^{\star})+\langle\nabla
g({\boldsymbol{x}}_{g}^{\star}),{\boldsymbol{x}}-{\boldsymbol{x}}_{g}^{\star}\rangle+\frac{\lambda}{2}\left\|{\boldsymbol{x}}-{\boldsymbol{x}}_{g}^{\star}\right\|^{2}\stackrel{{\scriptstyle\text{\eqref{opt_cond_again}}}}{{\geq}}g({\boldsymbol{x}}_{g}^{\star})+\frac{\lambda}{2}\left\|{\boldsymbol{x}}-{\boldsymbol{x}}_{g}^{\star}\right\|^{2}.$
(26)

Observe that the minimization in (24) is performed over a function which is
$\frac{1}{\eta}$ strongly convex over $\mathcal{X}$, and has a minimizer
${\boldsymbol{v}}$. Also, recall that
${\boldsymbol{x}}^{\star}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f({\boldsymbol{x}})$.
Therefore, from (26) with
${\boldsymbol{x}}={\boldsymbol{x}}^{\star},g({\boldsymbol{x}})=f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{x}}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{x}}-{\boldsymbol{u}}\right\|^{2},{\boldsymbol{x}}^{\star}_{g}={\boldsymbol{v}}$,
we have the following:

$\displaystyle f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{x}}^{\star}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}\stackrel{{\scriptstyle\text{\eqref{hazan_result}}}}{{\geq}}f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{u}}\right\|^{2}+\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2},$
$\displaystyle\implies$ $\displaystyle f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{u}}\right\|^{2}\leq
f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{x}}^{\star}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2}.$
(27)

From the $\mu$-strong convexity of $f$ we have the following:

$\displaystyle f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{x}}^{\star}-{\boldsymbol{u}}\rangle\leq
f({\boldsymbol{x}}^{\star})-\frac{\mu}{2}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}.$

Using strong convexity to bound $f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{x}}^{\star}-{\boldsymbol{u}}\rangle$ in (27),
we obtain

$\displaystyle f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{u}}\right\|^{2}\leq
f({\boldsymbol{x}}^{\star})+\frac{1}{2\eta}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{\mu}{2}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2},$
$\displaystyle\implies$ $\displaystyle f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle\leq
f({\boldsymbol{x}}^{\star})+\frac{1}{2\eta}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{\mu}{2}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{u}}\right\|^{2}.$
(28)

The $L$-smoothness of $f$ and $\eta\leq\frac{1}{L}$ implies

$\displaystyle f({\boldsymbol{v}})\leq f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle+\frac{L}{2}\left\|{\boldsymbol{v}}-{\boldsymbol{u}}\right\|^{2}\leq
f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle+\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{u}}\right\|^{2}.$
(29)

Using (28) to bound $f({\boldsymbol{u}})+\langle\nabla
f({\boldsymbol{u}}),{\boldsymbol{v}}-{\boldsymbol{u}}\rangle$ in (29), we
obtain the following:

$\displaystyle
f({\boldsymbol{v}})\stackrel{{\scriptstyle\text{\eqref{intermediate_step_},
\eqref{another_step}}}}{{\leq}}f({\boldsymbol{x}}^{\star})+\frac{1}{2\eta}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{\mu}{2}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2}.$
(30)

Again, applying (26) with
$g=f,{\boldsymbol{x}}^{\star}_{g}={\boldsymbol{x}}^{\star},{\boldsymbol{x}}={\boldsymbol{v}}$,
we have

$\displaystyle
f({\boldsymbol{v}})\stackrel{{\scriptstyle\text{\eqref{hazan_result}}}}{{\geq}}f({\boldsymbol{x}}^{\star})+\frac{\mu}{2}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2}.$
(31)

Combining (30) and (31), we obtain

$\displaystyle\frac{\mu}{2}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2}\stackrel{{\scriptstyle\text{\eqref{hazan_again}}}}{{\leq}}f({\boldsymbol{v}})-f({\boldsymbol{x}}^{\star})\stackrel{{\scriptstyle\text{\eqref{penultimate_step}}}}{{\leq}}\frac{1}{2\eta}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{\mu}{2}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}-\frac{1}{2\eta}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2},$
$\displaystyle\hskip
56.9055pt\implies\bigg{(}\frac{1}{\eta}+\mu\bigg{)}\left\|{\boldsymbol{v}}-{\boldsymbol{x}}^{\star}\right\|^{2}\leq\bigg{(}\frac{1}{\eta}-\mu\bigg{)}\left\|{\boldsymbol{u}}-{\boldsymbol{x}}^{\star}\right\|^{2}.$

This completes the proof. ∎

###  Appendix B Nesterov Accelerated Gradient (NAG)

In this section, we show that to get $1/4$-th contraction as in (10), the
number of gradient queries can be reduced to ${\mathcal{O}}(\sqrt{Q}\log Q)$,
where $Q:=\frac{L}{\mu}$ is the condition number of $f$, by the use of NAG.
For simplicity, we assume that $\mathcal{X}={\mathbb{R}}^{d}$.

We begin with a brief introduction of NAG. Consider the following optimization
problem:

$\displaystyle{\boldsymbol{x}}^{\star}=\operatorname*{arg\,min}_{\boldsymbol{x}}f({\boldsymbol{x}}),$
($\mathcal{P}$)

where $f$ is $\mu$-strongly convex and $L$-smooth. For $\eqref{eq:problem}$,
NAG maintains the sequence $\\{{\boldsymbol{x}}_{k},{\boldsymbol{y}}_{k}\\}$
and is entailed by the following updates:

$\displaystyle{\boldsymbol{y}}_{k+1}={\boldsymbol{x}}_{k}-\frac{1}{L}\nabla
f({\boldsymbol{x}}_{k}),\quad{\boldsymbol{x}}_{k+1}=\bigg{(}1-\frac{\sqrt{Q}-1}{\sqrt{Q}+1}\bigg{)}{\boldsymbol{y}}_{k+1}+\frac{\sqrt{Q}-1}{\sqrt{Q}+1}{\boldsymbol{y}}_{k}.$
(32)

The following Theorem from [39] shows that NAG enjoys a convergence rate of
$\exp\big{(}-\frac{k}{\sqrt{Q}}\big{)}$.

######  Theorem 5.

[39] The sequence $\\{{\boldsymbol{x}}_{k},{\boldsymbol{y}}_{k}\\}$ produced
by NAG, satisfies

$\displaystyle
f({\boldsymbol{y}}_{k})-f({\boldsymbol{x}}^{\star})\leq\frac{L+\mu}{2}\left\|{\boldsymbol{x}}_{0}-{\boldsymbol{x}}^{\star}\right\|^{2}\exp(-\frac{k-1}{\sqrt{Q}}).$
(33)

From Theorem 5, we can easily bound the residual
$\left\|{\boldsymbol{y}}_{k}-{\boldsymbol{x}}^{\star}\right\|$ by the
following:

$\displaystyle f({\boldsymbol{y}}_{k})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}f({\boldsymbol{x}}^{\star})+\langle\nabla
f({\boldsymbol{x}}^{\star}),{\boldsymbol{y}}-{\boldsymbol{x}}^{\star}\rangle+\frac{\mu}{2}\left\|{\boldsymbol{y}}_{k}-{\boldsymbol{x}}^{\star}\right\|^{2},$
$\displaystyle=f({\boldsymbol{x}}^{\star})+\frac{\mu}{2}\left\|{\boldsymbol{y}}_{k}-{\boldsymbol{x}}^{\star}\right\|^{2},$
(34)

where $(a)$ follows from the $\mu$-strong convexity of $f$. Therefore, we have

$\displaystyle\frac{\mu}{2}\left\|{\boldsymbol{y}}_{k}-{\boldsymbol{x}}^{\star}\right\|^{2}\stackrel{{\scriptstyle\eqref{triv}}}{{\leq}}f({\boldsymbol{y}}_{k})-f({\boldsymbol{x}}^{\star})\stackrel{{\scriptstyle\eqref{exp_rate}}}{{\leq}}\frac{L+\mu}{2}\left\|{\boldsymbol{x}}_{0}-{\boldsymbol{x}}^{\star}\right\|^{2}\exp(-\frac{k-1}{\sqrt{Q}}),$
$\displaystyle\hskip
28.45274pt\implies\left\|{\boldsymbol{y}}_{k+1}-{\boldsymbol{x}}^{\star}\right\|^{2}\leq\frac{L+\mu}{\mu}\left\|{\boldsymbol{x}}_{0}-{\boldsymbol{x}}^{\star}\right\|^{2}\exp(-\frac{k}{\sqrt{Q}}).$
(35)

We now discuss the resulting counterpart of the OMGD algorithm. At time $t$,
we start with
${\boldsymbol{y}}_{0}^{t}={\boldsymbol{x}}_{0}^{t}={\boldsymbol{x}}_{t-1}$ and
execute NAG with gradients corresponding to $\nabla f_{t-1}$ (and therefore
${\boldsymbol{x}}^{\star}={\boldsymbol{x}}_{t-1}^{\star}$). The final action
is taken as ${\boldsymbol{x}}_{t}={\boldsymbol{y}}_{K+1}^{t}$, where
$K=\lceil\sqrt{Q}\ln 4(Q+1)\rceil$. From (35), we have the following:

$\displaystyle\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}$
$\displaystyle\leq\exp{(\ln(Q+1))}\exp(-\frac{K}{\sqrt{Q}})\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2},$
$\displaystyle\leq\exp{\big{(}\ln(Q+1)-\frac{K}{\sqrt{Q}}\big{)}}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2},$
$\displaystyle\leq\frac{1}{4}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}.$

###  Appendix C Proof of Lemma 2

From the $L$-smoothness of $f$, as per Assumption A2, we have

$\displaystyle f_{t}({\boldsymbol{x}}_{t})$ $\displaystyle\leq
f_{t}({\boldsymbol{x}}_{t}^{\star})+\langle\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star}),{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\rangle+\frac{L}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2},$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}f_{t}({\boldsymbol{x}}_{t}^{\star})+\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|+\frac{L}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+\frac{L+\alpha}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2},$

where $(a)$ follows by applying the Cauchy-Schwarz inequality
$\langle{\boldsymbol{u}},{\boldsymbol{v}}\rangle\leq\left\|{\boldsymbol{u}}\right\|\left\|{\boldsymbol{v}}\right\|$,
where ${\boldsymbol{u}},{\boldsymbol{v}}\in\mathbb{R}^{d}$, while $(b)$
follows by applying the Peter-Paul inequality
$ab\leq\frac{a^{2}}{2\alpha}+\frac{\alpha b^{2}}{2},$ which holds for any
$\alpha>0,a,b\in\mathbb{R}$. Thus the total hitting cost of $\mathcal{A}_{o}$
can be bounded by

$\displaystyle\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})$
$\displaystyle\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+\frac{L+\alpha}{2}\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2},$
$\displaystyle\stackrel{{\scriptstyle\text{\eqref{actual_squared_bound}}}}{{\leq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{1}{2\alpha}\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}+{(L+\alpha)}(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star}).$

This completes the proof.

###  Appendix D Proof of Lemma 5

###### Proof.

The cost of the $\mathsf{OPT}$ is given by

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle=\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\bigg{(}f_{t}({\boldsymbol{x}}_{t})+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\bigg{)},$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}f_{t}({\boldsymbol{x}}_{t}^{\star})+\langle\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star}),{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\rangle+\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$
$\displaystyle=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{\\{{\boldsymbol{x}}_{t}\in\mathcal{X}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$
(36)
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{\\{{\boldsymbol{x}}_{t}\in\mathbb{R}^{d}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$
(37)
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{x_{t}^{(k)}\in\mathbb{R}}\sum_{t=1}^{T}\sum_{k=1}^{d}\bigg{(}\frac{\mu}{2}(x_{t}^{(k)}-x_{t}^{\star(k)})^{2}+\frac{1}{2}(x_{t}^{(k)}-x_{t-1}^{(k)})^{2}\bigg{)},$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{x_{t}^{(k)}\in\mathbb{R}}\sum_{k=1}^{d}\sum_{t=1}^{T}\bigg{(}\frac{\mu}{2}(x_{t}^{(k)}-x_{t}^{\star(k)})^{2}+\frac{1}{2}(x_{t}^{(k)}-x_{t-1}^{(k)})^{2}\bigg{)},$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{=}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\min_{\\{\tilde{{\boldsymbol{x}}}_{k}\in\mathbb{R}^{T}\\}_{k=1}^{d}}\sum_{k=1}^{d}\psi(\tilde{{\boldsymbol{x}}}_{k}),$
(38)
$\displaystyle\stackrel{{\scriptstyle(g)}}{{=}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\sum_{k=1}^{d}\psi(\bar{{\boldsymbol{x}}}_{k}^{\star}),$
(39)

where $(a)$ follows from the $\mu$-strong convexity of $f_{t}$, $(b)$ follows
from the optimality condition $\langle\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star}),{\boldsymbol{x}}-{\boldsymbol{x}}_{t}^{\star}\rangle\geq
0$, $\forall{\boldsymbol{x}}\in\mathcal{X}$ of the minimization
${\boldsymbol{x}}_{t}^{\star}=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f_{t}({\boldsymbol{x}})$.
To get $(c)$, we use Lemma 18 that the constrained optimization over
$\mathcal{X}$ is equivalent to an unconstrained optimization over
$\mathbb{R}^{d}$. To get $(d)$, we have expressed the optimization over
${{\boldsymbol{x}}_{t}\in\mathbb{R}^{d}}$ as an optimization over
$x_{t}^{(k)}\in\mathbb{R}$, where
${\boldsymbol{x}}_{t}=[x_{t}^{(1)},\ldots,x_{t}^{(d)}]$ and
${\boldsymbol{x}}_{t}^{*}=[x_{t}^{\star(1)},\ldots,x_{t}^{\star(d)}]$. To get
$(e)$, we interchange the order of summation
$\sum_{t=1}^{T}\sum_{k=1}^{d}\to\sum_{k=1}^{d}\sum_{t=1}^{T}$, in $(f)$ we
have transformed the unconstrained optimization in the ${\boldsymbol{x}}_{t}$
space to $\tilde{{\boldsymbol{x}}}_{k}$ space by defining
$\tilde{{\boldsymbol{x}}}_{k}=[x_{1}^{(k)},\ldots,x_{T}^{(k)}]^{{\mathsf{T}}}\in\mathbb{R}^{T}$,
$\tilde{{\boldsymbol{x}}}_{k}^{\star}=[x_{1}^{\star(k)},\ldots,x_{T}^{\star(k)}]^{{\mathsf{T}}}\in\mathbb{R}^{T}$.
It is important to note that while the original optimization was over
${\boldsymbol{x}}_{t}\in\mathbb{R}^{d}$, the optimization in (38) is over
$\tilde{{\boldsymbol{x}}}_{k}\in\mathbb{R}^{T}$, where $T$ is the time
horizon. Finally, we get $(g)$ by defining
$\bar{{\boldsymbol{x}}}_{k}^{\star}:=\operatorname*{arg\,min}_{\tilde{{\boldsymbol{x}}}_{k}\in\mathbb{R}^{T}}\psi(\tilde{{\boldsymbol{x}}}_{k})$,
where the function $\psi(\tilde{{\boldsymbol{x}}}_{k})$ is defined as

$\displaystyle\psi(\tilde{{\boldsymbol{x}}}_{k}):=\sum_{t=1}^{T}\bigg{(}\frac{\mu}{2}(x_{t}^{(k)}-x_{t}^{\star(k)})^{2}+\frac{1}{2}(x_{t}^{(k)}-x_{t-1}^{(k)})^{2}\bigg{)}=\frac{\mu}{2}(\tilde{{\boldsymbol{x}}}_{k}-\tilde{{\boldsymbol{x}}}_{k}^{\star})^{{\mathsf{T}}}(\tilde{{\boldsymbol{x}}}_{k}-\tilde{{\boldsymbol{x}}}_{k}^{\star})+\frac{1}{2}\tilde{{\boldsymbol{x}}}_{k}^{{\mathsf{T}}}{\boldsymbol{B}}\tilde{{\boldsymbol{x}}}_{k},$
(40)

where the matrix ${\boldsymbol{B}}$ of dimension $T\times T$ is defined as

$\displaystyle{\boldsymbol{B}}:=\begin{bmatrix}2&-1&\cdots&\cdots&0\\\
-1&2&-1&\cdots&0\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\cdots&\cdots&-1&2&-1\\\ 0&\cdots&\cdots&-1&1\end{bmatrix}.$ (41)

Next, we consider the function
$\frac{1}{2}\tilde{{\boldsymbol{x}}}_{k}^{{\mathsf{T}}}{\boldsymbol{B}}\tilde{{\boldsymbol{x}}}_{k}=\sum_{t=1}^{T}\frac{1}{2}(x_{t}^{(k)}-x_{t-1}^{(k)})^{2}$
whose Hessian equals to the matrix ${\boldsymbol{B}}$ (41). To proceed
further, we first study the lower and upper bounds on
$\lambda_{i}({\boldsymbol{B}})$. For this we make use of the Gershgorin’s
Circle Theorem stated next.

######  Theorem 6 (Gershgorin’s Circle Theorem).

[38, Thm. 6.1.1] Let ${\boldsymbol{A}}=[a_{ij}]$ be a $n\times n$ matrix with
complex entries, i.e., $a_{ij}\in{\boldsymbol{C}}$, where ${\boldsymbol{C}}$
denotes the space of complex numbers. Let

$\displaystyle R_{i}({\boldsymbol{A}})=\sum_{j\neq i}\lvert
a_{ij}\rvert,\hskip 8.53581pti=1,\ldots,n,$

denote the sum of absolute values of the off-diagonal entries in the $i$-th
row of ${\boldsymbol{A}}$, and consider the $n$ Gershgorin discs

$\displaystyle G_{i}({\boldsymbol{A}})=\\{z\in\mathbf{C}:\lvert
z-a_{ii}\rvert\leq R_{i}({\boldsymbol{A}})\\},\hskip 8.53581pti=1,\ldots,n.$

Then, the eigenvalues of ${\boldsymbol{A}}$ belong to the union of the
Gershgorin discs

$\displaystyle G({\boldsymbol{A}})=\cup_{i=1}^{n}G_{i}({\boldsymbol{A}}),$

i.e., $\lambda_{i}({\boldsymbol{A}})\in G({\boldsymbol{A}})$, $i=1,\dots,n$.

######  Corollary 2.

The eigenvalues of ${\boldsymbol{B}}$ (41) lie in the interval $[0,4]$, i.e.,
$\lambda_{i}({\boldsymbol{B}})\in[0,4]$ for all $1\leq i\leq T$.

###### Proof.

Since ${\boldsymbol{B}}$ is symmetric, its eigenvalues are real. Therefore, it
suffices to only consider the real part of the Gershgorin discs. Note that
there are exactly $3$ distinct Gershgorin discs corresponding to the matrix
${\boldsymbol{B}}$. For $i=1$, the real part of
$G_{i}({\boldsymbol{B}})=\\{z\in{\boldsymbol{C}}:\lvert z-2\rvert\leq 1\\}$
corresponds to the interval $[1,3]$. Similarly, for all $i$ such that $2\leq
i\leq T-1$, the real part of $G_{i}({\boldsymbol{B}})$ corresponds to the
interval $[0,4]$. For $i=T$, the real part of $G_{i}({\boldsymbol{B}})$
corresponds to the interval $[0,2]$. Thus, the real part of
$G({\boldsymbol{B}})=\cup_{i=1}^{T}G_{i}({\boldsymbol{B}})$ corresponds to the
interval $[0,4]$. Applying Theorem 6, each eigenvalue
$\lambda_{i}({\boldsymbol{B}})\in[0,4]$. This completes the proof. ∎

Corollary 2 implies that ${\boldsymbol{B}}\succeq\mathbf{0}$. Thus, the
function
$\frac{1}{2}\tilde{{\boldsymbol{x}}}_{k}^{{\mathsf{T}}}{\boldsymbol{B}}\tilde{{\boldsymbol{x}}}_{k}=\sum_{t=1}^{T}\frac{1}{2}(x_{t}^{(k)}-x_{t-1}^{(k)})$
is jointly convex in $\tilde{{\boldsymbol{x}}}_{k}$. This implies that
$\psi(\tilde{{\boldsymbol{x}}}_{k})$ (40) is strongly convex in
$\tilde{{\boldsymbol{x}}}_{k}$ since it is the sum of a strongly convex
function
$\frac{1}{2}(\tilde{{\boldsymbol{x}}}_{k}-\tilde{{\boldsymbol{x}}}_{k}^{\star})^{{\mathsf{T}}}(\tilde{{\boldsymbol{x}}}_{k}-\tilde{{\boldsymbol{x}}}_{k}^{\star})$
and a convex function
$\frac{1}{2}\tilde{{\boldsymbol{x}}}_{k}^{{\mathsf{T}}}{\boldsymbol{B}}\tilde{{\boldsymbol{x}}}_{k}$.
Thus, $\psi(\tilde{{\boldsymbol{x}}}_{k})$ has a unique minimizer
$\bar{{\boldsymbol{x}}}_{k}^{\star}$, which is given by

$\displaystyle\bar{{\boldsymbol{x}}}_{k}^{\star}=\operatorname*{arg\,min}_{\tilde{{\boldsymbol{x}}}_{k}}\psi(\tilde{{\boldsymbol{x}}}_{k})\implies\nabla\psi(\bar{{\boldsymbol{x}}}_{k}^{\star})=\mathbf{0}\implies\mu(\bar{{\boldsymbol{x}}}_{k}^{\star}-\tilde{{\boldsymbol{x}}}_{k}^{\star})+{\boldsymbol{B}}\bar{{\boldsymbol{x}}}_{k}^{\star}=\mathbf{0}\implies\bar{{\boldsymbol{x}}}_{k}^{\star}=\mu({\boldsymbol{B}}+\mu{\boldsymbol{I}})^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star}.$
(42)

Define ${\boldsymbol{A}}:={\boldsymbol{B}}+\mu{\boldsymbol{I}}$, thus
${\boldsymbol{A}}\succ\mathbf{0}$
($\because{\boldsymbol{B}}\succeq\mathbf{0}$). Since
${\boldsymbol{A}}\succ\mathbf{0}$, ${\boldsymbol{A}}^{-1}$ exists with
${\boldsymbol{A}}^{-1}\succ\mathbf{0}$ (because ${\boldsymbol{A}}$ and
${\boldsymbol{A}}^{-1}$ have the same eigenvectors with
$\lambda_{i}({\boldsymbol{A}}^{-1})=\frac{1}{\lambda_{i}({\boldsymbol{A}})}$).
The optimal value $\psi(\bar{{\boldsymbol{x}}}_{k}^{\star})$ is obtained by
evaluating $\psi(\tilde{{\boldsymbol{x}}}_{k})$ at
$\tilde{{\boldsymbol{x}}}_{k}=\bar{{\boldsymbol{x}}}_{k}^{\star}$ (42) and is
given by

$\displaystyle\psi(\bar{{\boldsymbol{x}}}_{k}^{\star})$
$\displaystyle=\frac{\mu}{2}(\bar{{\boldsymbol{x}}}_{k}^{\star}-\tilde{{\boldsymbol{x}}}_{k}^{\star})^{{\mathsf{T}}}(\bar{{\boldsymbol{x}}}_{k}^{\star}-\tilde{{\boldsymbol{x}}}_{k}^{\star})+\frac{1}{2}\bar{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{B}}\bar{{\boldsymbol{x}}}_{k}^{\star},$
$\displaystyle=\frac{\mu}{2}\left\|\mu{\boldsymbol{A}}^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star}-\tilde{{\boldsymbol{x}}}_{k}^{\star}\right\|^{2}+\frac{\mu^{2}}{2}({\boldsymbol{A}}^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star})^{{\mathsf{T}}}({\boldsymbol{A}}-\mu{\boldsymbol{I}})({\boldsymbol{A}}^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star}),$
$\displaystyle=\frac{\mu}{2}\bigg{(}\mu^{2}\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{A}}^{-2}\tilde{{\boldsymbol{x}}}_{k}^{\star}+\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}\tilde{{\boldsymbol{x}}}_{k}^{\star}-2\mu\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{A}}^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star}\bigg{)}+\frac{\mu^{2}}{2}\bigg{(}\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{A}}^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star}-\mu\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{A}}^{-2}\tilde{{\boldsymbol{x}}}_{k}^{\star}\bigg{)},$
$\displaystyle=\frac{\mu}{2}\bigg{(}\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}\tilde{{\boldsymbol{x}}}_{k}^{\star}-\mu\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{A}}^{-1}\tilde{{\boldsymbol{x}}}_{k}^{\star}\bigg{)}=\frac{\mu}{2}\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}({\boldsymbol{I}}-\mu{\boldsymbol{A}}^{-1})\tilde{{\boldsymbol{x}}}_{k}^{\star}.$
(43)

Next, we establish that, for the particular matrix
${\boldsymbol{A}}={\boldsymbol{B}}+\mu{\boldsymbol{I}}$ with
${\boldsymbol{B}}$ defined as in (41), the following holds:

$\displaystyle{\boldsymbol{I}}-\mu{\boldsymbol{A}}^{-1}\succeq\frac{1}{\mu+4}({\boldsymbol{A}}-\mu{\boldsymbol{I}}).$

Note that this is equivalent to

$\displaystyle\bigg{(}1+\frac{\mu}{\mu+4}\bigg{)}{\boldsymbol{I}}\succeq\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}.$
(44)

To establish (44), we first upper bound the eigenvalues of the matrix
$\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}$. The following
Lemma establishes a relationship between the eigenvalues of
$\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}$ and the eigenvalues
of ${\boldsymbol{A}}$.

######  Lemma 17.

The eigenvalues of
$(\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}})$ are related with
the eigenvalues of ${\boldsymbol{A}}$ via the following relationship:

$\displaystyle\lambda_{i}\bigg{(}\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}\bigg{)}=\frac{\mu}{\lambda_{i}({\boldsymbol{A}})}+\frac{1}{\mu+4}\lambda_{i}({\boldsymbol{A}}).$
(45)

Further, the eigenvalues of ${\boldsymbol{A}}$ are related with the
eigenvalues of ${\boldsymbol{B}}$ as

$\displaystyle\lambda_{i}({\boldsymbol{A}})=\lambda_{i}({\boldsymbol{B}})+\mu.$
(46)

###### Proof.

Let ${\boldsymbol{v}}_{i}$ be an eigenvector of ${\boldsymbol{A}}$
corresponding to the eigenvalue $\lambda_{i}({\boldsymbol{A}})$. Therefore,
${\boldsymbol{A}}{\boldsymbol{v}}_{i}=\lambda_{i}({\boldsymbol{A}}){\boldsymbol{v}}_{i}\implies\frac{1}{\mu+4}{\boldsymbol{A}}{\boldsymbol{v}}_{i}=\frac{1}{\mu+4}\lambda_{i}({\boldsymbol{A}}){\boldsymbol{v}}_{i}$.
Also note that
${\boldsymbol{A}}^{-1}{\boldsymbol{v}}_{i}=\frac{1}{\lambda_{i}({\boldsymbol{A}})}{\boldsymbol{v}}_{i}\implies\mu{\boldsymbol{A}}^{-1}{\boldsymbol{v}}_{i}=\frac{\mu}{\lambda_{i}({\boldsymbol{A}})}{\boldsymbol{v}}_{i}$.
Adding, we get

$\bigg{(}\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}\bigg{)}{\boldsymbol{v}}_{i}=\bigg{(}\frac{\mu}{\lambda_{i}({\boldsymbol{A}})}+\frac{1}{\mu+4}\lambda_{i}({\boldsymbol{A}})\bigg{)}{\boldsymbol{v}}_{i}.$

Therefore, ${\boldsymbol{v}}_{i}$ is an eigenvector of the matrix
$\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}$ with eigenvalue
$\frac{\mu}{\lambda_{i}({\boldsymbol{A}})}+\frac{1}{\mu+4}\lambda_{i}({\boldsymbol{A}})$.

For the second part, let ${\boldsymbol{u}}_{i}$ be an eigenvector of
${\boldsymbol{B}}$ with eigenvalue $\lambda_{i}({\boldsymbol{B}})$. Therefore,
${\boldsymbol{B}}{\boldsymbol{u}}_{i}=\lambda_{i}({\boldsymbol{B}}){\boldsymbol{u}}_{i}$.
Observe that

$({\boldsymbol{B}}+\mu{\boldsymbol{I}}){\boldsymbol{u}}_{i}=\lambda_{i}({\boldsymbol{B}}){\boldsymbol{u}}_{i}+\mu{\boldsymbol{u}}_{i}=(\lambda_{i}({\boldsymbol{B}})+\mu){\boldsymbol{u}}_{i}.$

Hence, ${\boldsymbol{u}}_{i}$ is an eigenvector of the matrix
${\boldsymbol{B}}+\mu{\boldsymbol{I}}={\boldsymbol{A}}$ with eigenvalue
$\lambda_{i}({\boldsymbol{B}})+\mu$. This completes the proof. ∎

From Corollary 2 and Lemma 17 we have the following:

$\displaystyle\lambda_{i}({\boldsymbol{B}})\in[0,4]\stackrel{{\scriptstyle\eqref{eig_A_B}}}{{\equiv}}\lambda_{i}({\boldsymbol{A}})-\mu\in[0,4]\implies\lambda_{i}({\boldsymbol{A}})\in[\mu,\mu+4].$
(47)

Consider the function $g(\lambda)=\frac{\mu}{\lambda}+\frac{\lambda}{\mu+4}$
that is convex in $\lambda$. The maximum value of this function over the
interval $[\mu,\mu+4]$ is attained at either of the end points
$\\{\mu,\mu+4\\}$. Therefore, we have

$\displaystyle\max_{\lambda\in[\mu,\mu+4]}g(\lambda)=\max\\{g(\mu),g(\mu+4)\\}=1+\frac{\mu}{\mu+4}.$
(48)

Hence, from (45), (47), and (48), we obtain

$\displaystyle\lambda_{i}\bigg{(}\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}\bigg{)}\leq
1+\frac{\mu}{\mu+4},$ (49)

for all $1\leq i\leq T\\}$. Since,
${\boldsymbol{A}},{\boldsymbol{A}}^{-1}\succ 0$, from the orthogonal
decomposition theorem we have

$\displaystyle\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}=\sum_{i=1}^{T}\lambda_{i}\bigg{(}\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}\bigg{)}{\boldsymbol{v}}_{i}{\boldsymbol{v}}_{i}^{{\mathsf{T}}}\stackrel{{\scriptstyle\text{\eqref{eig_bound}}}}{{\preceq}}\sum_{i=1}^{T}\bigg{(}1+\frac{\mu}{\mu+4}\bigg{)}{\boldsymbol{v}}_{i}{\boldsymbol{v}}_{i}^{{\mathsf{T}}}=\bigg{(}1+\frac{\mu}{\mu+4}\bigg{)}{\boldsymbol{I}},$

where ${\boldsymbol{v}}_{1},\ldots,{\boldsymbol{v}}_{T}$ are the orthornomal
eigenvectors corresponding to the $T$ eigenvalues of
$\mu{\boldsymbol{A}}^{-1}+\frac{1}{\mu+4}{\boldsymbol{A}}$. Thus, we have
proved the claim in (44). Using (44) in (43), we obtain

$\displaystyle\psi(\hat{{\boldsymbol{x}}}_{k}^{\star})\geq\frac{\mu}{2(\mu+4)}\tilde{{\boldsymbol{x}}}_{k}^{\star}({\boldsymbol{A}}-\mu{\boldsymbol{I}})\tilde{{\boldsymbol{x}}}_{k}^{\star}=\frac{\mu}{2(\mu+4)}\tilde{{\boldsymbol{x}}}_{k}^{\star{\mathsf{T}}}{\boldsymbol{B}}\tilde{{\boldsymbol{x}}}_{k}^{\star}=\frac{\mu}{2(\mu+4)}\sum_{t=1}^{T}(x_{t}^{\star(k)}-x_{t-1}^{\star(k)})^{2},$
(50)

where we have set ${{\boldsymbol{x}}}_{0}^{\star}=\mathbf{0}$. Continuing from
step (39), we obtain

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle\geq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}^{\star}_{t})+\sum_{k=1}^{d}\psi(\bar{{\boldsymbol{x}}}_{k}^{\star}),$
$\displaystyle\stackrel{{\scriptstyle\text{\eqref{imp_step}}}}{{\geq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}^{\star}_{t})+\frac{\mu}{2(\mu+4)}\sum_{k=1}^{d}\sum_{t=1}^{T}(x_{t}^{\star(k)}-x_{t-1}^{\star(k)})^{2},$
$\displaystyle=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}^{\star}_{t})+\frac{\mu}{2(\mu+4)}\sum_{t=1}^{T}\sum_{k=1}^{d}(x_{t}^{\star(k)}-x_{t-1}^{\star(k)})^{2},$
$\displaystyle=\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}^{\star}_{t})+\frac{\mu}{2(\mu+4)}({\mathcal{P}}_{2,T}^{\star}+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}).$

This completes the proof. ∎

Next, we prove that the constrained optimization in (36) has the same solution
as the unconstrained optimization in (37). Although this has been shown in
[33], we provide a rigorous proof.

######  Lemma 18.

The constrained optimization in (36) has the same solution as the
unconstrained optimization in (37).

###### Proof.

We first consider the special case of $T=2$ to build intuition. For this case,
exact solutions to the unconstrained optimization in (37) are obtainable.
Consider the unconstrained problem (37) with $T=2$, i.e.,

$\displaystyle(\hat{{\boldsymbol{x}}}_{1},\hat{{\boldsymbol{x}}}_{2}):=\operatorname*{arg\,min}_{{\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2}}\bigg{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+\frac{\mu}{2}\left\|{\boldsymbol{x}}_{2}-{\boldsymbol{x}}^{\star}_{2}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{2}-{\boldsymbol{x}}_{1}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{1}\right\|^{2}\bigg{)}.$

The optimal solution can be expressed as the following system of equations:

$\displaystyle\mu(\hat{{\boldsymbol{x}}}_{1}-{\boldsymbol{x}}^{\star}_{1})+(\hat{{\boldsymbol{x}}}_{1}-\hat{{\boldsymbol{x}}}_{2})+\hat{{\boldsymbol{x}}}_{1}=\mathbf{0}$
$\displaystyle\implies(\mu+2)\hat{{\boldsymbol{x}}}_{1}-\hat{{\boldsymbol{x}}}_{2}=\mu{\boldsymbol{x}}^{\star}_{1},$
$\displaystyle\mu(\hat{{\boldsymbol{x}}}_{2}-{\boldsymbol{x}}^{\star}_{2})+(\hat{{\boldsymbol{x}}}_{2}-\hat{{\boldsymbol{x}}}_{1})=\mathbf{0}$
$\displaystyle\implies-\hat{{\boldsymbol{x}}}_{1}+(\mu+1)\hat{{\boldsymbol{x}}}_{2}=\mu{\boldsymbol{x}}^{\star}_{2}.$

The optimal solution is given by

$\displaystyle\begin{bmatrix}\hat{{\boldsymbol{x}}}_{1}\\\
\hat{{\boldsymbol{x}}}_{2}\end{bmatrix}=\begin{bmatrix}\mu+2&-1\\\
-1&\mu+1\end{bmatrix}^{-1}\begin{bmatrix}\mu{\boldsymbol{x}}^{\star}_{1}\\\
\mu{\boldsymbol{x}}^{\star}_{2}\end{bmatrix}=\frac{\mu}{\mu^{2}+3\mu+1}\begin{bmatrix}(\mu+1){\boldsymbol{x}}_{1}^{\star}+{\boldsymbol{x}}_{2}^{\star}\\\