# Online Convex Optimization in Changing Environments
and its Application to Resource Allocation

Jianjun Yuan

###### Abstract

In the era of the big data, we create and collect lots of data from all
different kinds of sources: the Internet, the sensors, the consumer market,
and so on. Many of the data are coming sequentially, and would like to be
processed and understood quickly. One classic way of analyzing data is based
on batch processing, in which the data is stored and analyzed in an offline
fashion. However, when the volume of the data is too large, it is much more
difficult and time-consuming to do batch processing than sequential
processing. What’s more, sequential data is usually changing dynamically, and
needs to be understood on-the-fly in order to capture the changes. Online
Convex Optimization (OCO) is a popular framework that matches the above
sequential data processing requirement. Applications using OCO include online
routing, online auctions, online classification and regression, as well as
online resource allocation. Due to the general applicability of OCO to the
sequential data and the rigorous theoretical guarantee, it has attracted lots
of researchers to develop useful algorithms to fulfill different needs. In
this thesis, we show our contributions to OCO’s development by designing
algorithms to adapt to changing environments.

In the first part of the thesis, we propose algorithms to have better
adaptivity by examining the notion of _dynamic regret_ , which compares the
algorithm’s cumulative loss against that incurred by a comparison sequence.
Dynamic regret extends a common performance measure known as static regret.
Since it may not be known whether the environment is dynamic or not, it is
desirable to take advantage of both regrets by having a trade-off between
them. To achieve that, we discuss recursive least-squares algorithms and show
how forgetting factors can be used to develop new OCO algorithms that have
such a regret trade-off. More specifically, we rigorously characterize the
effect of forgetting factors for a class of online Newton algorithms. For exp-
concave or strongly convex objective, the improved dynamic regret of
$\max\\{O(\log T),O(\sqrt{TV})\\}$ is achieved, where $V$ is a bound on the
path length of the comparison sequence. In particular, we show how classic
recursive least-squares with a forgetting factor achieves this dynamic regret
bound. By varying $V$, we obtain the regret trade-off. In order to obtain more
computationally efficient algorithm, we also propose a novel gradient descent
step size rule for strongly convex functions, which recovers the dynamic
regret bounds described above. For smooth problems, we can obtain static
regret of $O(T^{1-\beta})$ and dynamic regret of $O(T^{\beta}V^{*})$, where
$\beta\in(0,1)$ and $V^{*}$ is the path length of the sequence of minimizers.
By varying $\beta$, we obtain the regret trade-off.

The second part of the thesis describes how to design efficient algorithms to
adapt to the changing environments. Previous literature runs a pool of
algorithms in parallel to gain better adaptivity, which increases both the
running time and the online implementation complexity. Instead, we propose a
new algorithm requiring only one update per time step, while with the same
_adaptive regret_ performance guarantee as the current state-of-the-art
result. We then apply the algorithm to online Principal Component Analysis
(online PCA) and variance minimization under changing environments, since the
previous literature on online PCA has focused on performance guarantee under
stationary environment. We demonstrate both theoretically and experimentally
that the proposed algorithms can adapt to the changing environments.

The third part of the thesis starts from the observation that the projection
operator used in constrained OCO algorithms cannot really achieve true online
implementation due to the high time-consumption. To accelerate the OCO
algorithms’ update, previous literature is proposed to approximate the true
desired projection with a simpler closed-form one at the cost of constraint
violation ($g(\theta)>0$) for some time steps. Nevertheless, it can guarantee
sub-linearity for both the static regret and the long-term constraint,
$\sum\limits_{t=1}^{T}g(\theta_{t})$, having constraint satisfaction on
average. However, the sub-linear long-term constraint does not enforce small
constraint violation for every time step, because a strictly feasible solution
can cancel out the effects of violated constraints. To resolve it, we propose
algorithms to have the cumulative constraint of the form
$\sum\limits_{t=1}^{T}\big{(}\max\\{g(\theta_{t}),0\\}\big{)}^{2}$ upper
bounded sub-linearly. This new form heavily penalizes large constraint
violations while the cancellation effects cannot occur. Furthermore, useful
bounds on the single step constraint violation are derived. For convex
objectives, our result generalizes existing bounds, and for strongly convex
objectives we give improved regret bounds. In numerical experiments, we show
that our algorithm closely follows the constraint boundary leading to low
cumulative violation. Furthermore, we extend the proposed algorithms’ idea to
the more general time-dependent online resource allocation problems with
performance guarantee by a variant of _dynamic regret_.

University of Minnesota Electrical and Computer Engineering DOCTOR OF
PHILOSOPHY Andrew Lamperski, Advisor

December 2019

First of all, I want to express my sincere gratitude to my smart advisor,
Prof. Andrew Lamperski for his unconditional support and guidance throughout
my whole PhD study. His enthusiasm towards the useful research, rigorous
attitude, and good taste of the research topics are infectious. It would not
be possible to complete this thesis without his invaluable encouragement as
well as inspired interesting research advice. As a mentor, he shared with me
how to select good research topics, how to tackle difficult/complex problems
by getting ideas from easy ones, how to write a good paper, and how to make a
good presentation. All these together shape me to become a qualified
researcher, who needs not only knowledge and solid understandings on his/her
own area, but also the capability to explore new directions and overcome new
challenging problems. Moreover, I hope my PhD work can help push the research
in my area a little bit forward as promised to Andy at the beginning of my PhD
study. I will miss my every-Friday meeting and the joyfulness of deriving
various theoretical bounds on the white-board with him.

I want to thank Prof. Murti Salapaka, Prof. Mingyi Hong, and Prof. Steven Wu
for being in my thesis committee and providing feedback about my research. I
also want to thank Prof. Daniel Boley and Prof. Georgios B. Giannakis for
being in my preliminary exam committee and the useful suggestions for my
future work. I also want to thank all the professors that I have taken classes
from over my PhD study.

I am grateful to the University of Minnesota ECE department for the fellowship
in the academic year 2015-16, without which I would not be able to come to
Minnesota to pursue my PhD degree. I am indebted to University of Minnesota
MnDRIVE program for providing me with the Graduate Assistantship in the
academic year 2018-19. I will not complete this thesis without its resource
and financial support. I want to express my gratitude to the ECE staff,
especially Linda Jagerson, Jeanine Maiden, and Hallie White, for their help
and support.

I want to thank Prof. Mu Zhou, Prof. Weiwei Chen, Ruiliang Zhang, Prof. Ying
Chen for their help during the start of my graduate study. I would also like
to thank my lab mates Venkat Ram Subramanian, Tyler Lekang, Ran Tian, and
Bolei Di for sharing with me useful experience and information.

I am grateful to my terrific friends Kun Xu, Zheran Li, Jiadong Chen, Dr.
Tengtao Li, Dr. Qianqian Fan, Dr. Bingzhe Li, Ruilin Dong, Chengyao Tan,
Xiaonan Zhang, Jiaji Qi, Dongsheng Ding, Xiangyi Chen for their companion and
support, which make my PhD study full of happiness.

Finally, I want to thank my wonderful family. I want to thank my parents, my
sister, my brother-in-law, and my parents-in-law for their constant
encouragement and support. Especially, I want to thank my cute wife, Dingyi
Liu, for her companion, encouragement, care, and inspiration. I am also
grateful to our baby to be born.

To my parents, sister and dear wife. 771

##  Chapter 1 Introduction

###  1 Why Online Convex Optimization?

We live in an era that is full of accessible data: the Internet, different
sensors, the consumer and financial markets, and so on. Many people prefer to
first store the entire data set and then process it together like the classic
machine learning algorithms do. But when the volume of data is too large, such
batch processing would fail or be computationally inefficient due to the
large-scale dataset that needs to be loaded into the memory. In order to
understand and analyze the data quickly and efficiently, we can treat the
large-scale dataset as a stream, so that it can be processed one data point-
by-one data point or in a mini-batch fashion. Online learning is such a
popular framework in doing so, which is more computationally efficient because
it does not require loading the whole dataset. Moreover, it is theoretically
guaranteed to be competitive with the best fixed choice in hindsight (the
batch processing solution).

Besides the advantages for offline data analysis, online learning is also a
natural choice for treating sequential data. The reason is that it meets the
requirement of processing and understanding the data as quickly as possible.

One important framework of online learning is Online Convex Optimization
(OCO), which considers the case when the objective function is convex.
Featured by the high computational efficiency and proven theoretical
guarantees against different notions of performance, OCO algorithms have many
applications in the areas of online routing [1], online auctions [2], as well
as online classification and regression [3]. More specific applications are:
1\. Online linear dynamical system identification [4] that updates the
identified system parameters on-the-fly as the sequential observation comes
in; 2\. Online expert selection [5, 6, 7] which is about online decision
making on the best expert; 3\. Online Principal Component Analysis [8, 9, 10,
11] in picking up the subspace for the sequential data/observation to be
projected into; 4\. Online resource allocation [12, 13, 14] to sequentially
allocate budgets or other resources.

Another property that makes the OCO framework unique from any other framework
is that there is no statistical assumptions on how the data/observation is
generated. It can be generated deterministically, stochastically from a
mixture of different fixed distributions, or even adversarially. This property
is preferable when there is no clear conclusion on what kind of data
distribution we should use. Also, it makes more sense if the data is given by
our opponent in an adversarial manner. Such a game playing perspective [15]
further enables the application to the adversarial data processing like online
portfolio selection in the stock market [16, 17].

Influenced by the development of convex optimization tools, there are many
advances in the design of the OCO algorithms trying to fulfill different needs
under different considerations and scenarios. One of the most important
considerations is the guaranteed performance against different types of
comparators. For example, for the best fixed comparator in hindsight (which is
suitable in stationary environment), the guaranteed performance is called
_static regret_ [18]. For a changing environment, two other types of
comparators are usually used. One is the maximum static regret over any
contiguous time interval, which leads to the _adaptive regret_ performance
guarantee [19]. The other one is against all comparator sequences in a
constrained set, having performance guarantee named _dynamic regret_ [20, 21,
22]. In this thesis, we show our contributions to the OCO’s development by
designing algorithms to adapt to the changing environment.

###  2 Motivation

The general motivation for this thesis is to design OCO algorithms to enable
the decision making on-the-fly with better adaptivity to the changing
environments and extend them to online resource allocation.

Tracking the changes of the environments is a key difference between OCO
algorithms and the batch processing based approaches, because sequential
data/observation tends to be shifting over time. However, previous works on
OCO problems are mainly focused on the static regret, a performance metric
well-suited for stationary environments. Since the algorithms having sub-
linear static regret will converge to the single best fixed solution in
hindsight, their claimed performance somehow contradicts the original tracking
goal. In order to be aligned with the tracking objective, dynamic regret is
proposed to let the cumulative loss of OCO algorithms compete with any
sequence of comparators within the constrained set. Our first part of the
thesis is motivated by designing algorithms to upper bound the dynamic regret
for different types of problem setups.

Tracking the changing environments is usually achieved by running a pool of
algorithms with either different parameters (for upper bounding dynamic
regret) or different starting points (for upper bounding adaptive regret).
Such complex online implementaion is very time-consuming and not appropriate
in some problem setups. Proposing an efficient and easy-to-implement algorithm
is the goal of our second part of the thesis. In particular, we show that such
an algorithm exists and can be applied to the online Principal Component
Analysis (online PCA) and the online variance minimization. Compared to the
mentioned general adaptive algorithms, our proposed algorithm uses only one
update per time step, while maintains the same adaptive regret theoretical
guarantee as the general adaptive algorithms.

For constrained OCO algorithms, a projection operator is almost unavoidable.
When the constraint set is complex, such operation is very time-consuming and
prevents the algorithms from having a true online implementation. Our third
part of the thesis starts from the question of how to accelerate the
computations. Previous works propose to replace the true desired projection
with an approximate closed-form one, since closed-form update eliminates any
minimization-based computation. The ’downside’ is the possible constraint
violation from time to time. The remedy for it is the guarantee for the
constraint satisfaction on average. However, on-average constraint
satisfaction does not lead to the desired small constraint violation for each
time step. To achieve that, we propose a new algorithm to enforce small
constraint violation not only on average but also for every time step. The
idea of the on-average constraint satisfaction is also applied to online
resource allocation by some previous works. However, such application is only
limited to the budget type resource because of the considered on-average
constraint form. Our second motivation in the third part of the thesis is to
extend our proposed algorithms to have time-dependent dynamic regret guarantee
in order to solve broader online resource allocation problems.

###  3 Thesis Organization

The thesis is organized as follows:

  1. 1.

Chapter 2 discusses related work for Online Convex Optimization, that are
relevant to the algorithms or problem setups we consider in the later
chapters.

  2. 2.

Chapter 3 is mainly concerned with the question of how to enable the decision
making on-the-fly with better adaptivity to the changing environments.
Algorithms equipped with static regret performance guarantee are not
appropriate due to the fixed comparator they converge to. One way to better
track the changes of the environments is to use dynamic regret, which compares
the algorithm’s cumulative loss against that incurred by a comparison
sequence. Inspired by the forgetting factor used in the Recursive Least
Squares algorithms, we propose a discounted Online Newton algorithm to have
improved dynamic regret guarantee for both exp-concave and strongly convex
objectives. Moreover, the trade-off between static and dynamic regret is
analyzed for both Online Least-Squares and its generalization to strongly
convex and smooth objectives. To obtain more computationally efficient
algorithms, we also propose a novel gradient descent step size rule for
strongly convex functions, which recovers the dynamic regret bound described
above.

  3. 3.

Chapter 4 develops an online adaptive algorithm for Principal Component
Analysis (PCA) and its extension of variance minimization under changing
environments. The main idea is mixing the exponentiated gradient descent with
a fixed-share step. Compared with the previous algorithms having adaptive or
dynamic regret guarantee, our algorithm saves the need of running a pool of
algorithms in parallel, while achieves the same adaptive regret performance
guarantee.

  4. 4.

Chapter 5 contributes to the development of the OCO algorithms in achieving
fast online computation as well as online resource allocation. The projection
operator for the constrained OCO algorithms is the main bottleneck in
preventing the algorithms from having a quick update. We propose algorithms to
approximate the true desired projection with a simpler closed-form one at the
cost of the constraint violation for some time steps. Nevertheless, our
proposed algorithms lead to a sub-linear cumulative constraint violation to
ensure the constraint satisfaction on average. It also has mild and bounded
single step constraint violation. For convex objectives, our results
generalize existing ones, and for strongly convex objectives we give improved
regret bounds. Finally, we extend our proposed algorithms’ idea to solve the
general time-dependent online resource allocation problems.

  5. 5.

Chapter 6 draws some conclusions for the thesis.

###  4 Notation

For the $n$ dimensional vector $\theta\in\mathbb{R}^{n}$, we use
$\left\|\theta\right\|_{1}$ and $\left\|\theta\right\|$ to denote the
$\ell_{1}$-norm and $\ell_{2}$-norm, respectively. The gradient and Hessian of
the function $f_{t}$ at time step $t$ in terms of the $\theta$ are denoted as
$\nabla f_{t}(\theta)$ and $\nabla^{2}f_{t}(\theta)$, respectively. In order
to differentiate between the vector at time step $i$ and the $i$-th element of
it, we sometimes use bold lower-case symbols to denote the vector. The $i$-th
element of a sequence of vectors at time step $t$, $\mathbf{x_{t}}$, is
denoted by $x_{t,i}$.

For two probability vectors $\mathbf{q},\mathbf{w}\in\mathbb{R}^{n}$, we use
$d(\mathbf{q},\mathbf{w})$ to represent the relative entropy between them,
which is defined as $\sum_{i=1}^{n}q_{i}\ln(\frac{q_{i}}{w_{i}})$.
$\mathbf{q_{1:T}}$ is the sequence of vectors
$\mathbf{q_{1}},\dots,\mathbf{q_{T}}$, and $m(\mathbf{q_{1:T}})$ is defined to
be equal to $\sum\limits_{t=1}^{T-1}D_{TV}(\mathbf{q_{t+1}},\mathbf{q_{t}})$,
where $D_{TV}(\mathbf{q_{t}},\mathbf{q_{t-1}})$ is defined as
$\sum\limits_{i:q_{t,i}\geq q_{t-1,i}}(q_{t,i}-q_{t-1,i})$. The expected value
operator is denoted by $\mathbb{E}$.

For the matrix $A\in\mathbb{R}^{m\times n}$, its transpose is denoted by
$A^{\top}$ and $A^{\top}A$ denotes the matrix multiplication. The inverse of
$A$ is denoted as $A^{-1}$. We use $\left\|A\right\|_{2}$ to represent the
induced $2$ norm. For the two square matrices $A\in\mathbb{R}^{n\times n}$ and
$B\in\mathbb{R}^{n\times n}$, $A\preceq B$ means $A-B$ is negative semi-
definite, while $A\succeq B$ means $A-B$ is positive semi-definite. For a
positive definite matrix, $M$, let $\|x\|_{M}^{2}=x^{\top}Mx$. The standard
inner product between matrices is given by $\langle
A,B\rangle=\mathrm{Tr}(A^{\top}B)$. The determinant of a square matrix, $A$ is
denoted by $|A|$. We use $I$ to represent the identity matrix.

The quantum relative entropy between two density matrices111A density matrix
is a symmetric positive semi-definite matrix with trace equal to 1. Thus, the
eigenvalues of a density matrix form a probability vector. $P$ and $Q$ is
defined as $\Delta(P,Q)=\mathrm{Tr}(P\ln P)-\mathrm{Tr}(P\ln Q)$, where $\ln
P$ is the matrix logarithm for symmetric positive definite matrix $P$ (and
$\exp(P)$ is the matrix exponential).

##  Chapter 2 Related Work

In this chapter, we do a literature review for the works that are related to
the contents of this thesis as well as some necessary background and concepts.

As the previous chapter shows, online learning has attracted lots of
researchers to develop different algorithms for many interesting settings and
applications. Some of them are concerned with more theoretical parts. One
particular aspect is deriving lower and upper bounds for the performance in
various problem setups such as the expert problem [5, 23, 6, 7], the general
OCO setup [18, 24, 15, 25], online Reinforcement Learning [26], online non-
convex optimization [27, 28], the online bandit problem [29, 30, 31], and so
on. Other works apply or extend the existing algorithms to different
scenarios. Besides the ones mentioned in the previous chapter, other scenarios
include online time-series prediction with ARMA/ARIMA [32], online controller
design [33], as well as the well-known classification algorithm AdaBoost [34].

Amongst all the techniques and applications mentioned above, Online Convex
Optimization (OCO) is one of the most important unified frameworks that
provides efficient, and theoretically guaranteed solutions to many problems
and helps facilitate the development of online learning’s theoretical
analysis.

This chapter is divided into three sections with the literature review ranging
from classic OCO algorithms to the applications related to this thesis. More
specifically, Section 5 first discusses the basic concepts and definitions in
the OCO framework. It then covers popular OCO algorithms like Online Gradient
Descent and Online Newton’s method, with different performance guarantees.
Section 6 focuses on a specific problem setup, online Principal Component
Analysis (online PCA). It describes one classic online algorithm as well as
some extensions of it from the literature. Section 7 does the literature
review about how the previous works try to accelerate the online update in the
OCO algorithms. Two different kinds of algorithms are described and discussed
for their pros and cons. Furthermore, the extensions of them to handle online
resource allocation are also included.

###  5 Online Convex Optimization (OCO)

The formula for Online Convex Optimization (OCO) is: at each time step $t$,
before the true time-dependent convex objective function $f_{t}(\theta)$ is
revealed, we need to make a prediction $\theta_{t}$ from the convex set
$\mathcal{S}$, based on the history of the observations $f_{i}(\theta)$,
$i<t$. Then the value $f_{t}(\theta_{t})$ is the loss suffered due to the lack
of the knowledge of the true objective function $f_{t}(\theta)$. Our
prediction of $\theta$ is then updated to include the information of
$f_{t}(\theta)$. This whole process is repeated until termination. The convex
function, $f_{t}(\theta)$, can be chosen from the convex function class in an
arbitrary, possibly adversarial manner.

To better understand different OCO algorithms, we first describe the basic
definitions and concepts related to them.

####  5.1 The Basics of OCO

Since the key to the design of OCO algorithms is the convex optimization
tools, we would like to first discuss some important concepts about the convex
optimization.

A set $\mathcal{S}$ is a convex set if $\forall x,y\in\mathcal{S}$,
$\forall\lambda\geq 0,\mu\geq 0$ such that $\lambda+\mu=1$, we have that
$\lambda x+\mu y\in\mathcal{S}$.

A function $f:\mathcal{S}\mapsto\mathbb{R}$ is convex if $\forall
x,y\in\mathcal{S}$ and $\forall\alpha\in[0,1]$, we always have:

$f(\alpha x+(1-\alpha)y)\leq\alpha f(x)+(1-\alpha)f(y)$

If $f(x)$ is first-order differentiable, then $f(x)$ is convex if and only if

$f(x)\geq f(y)+\nabla f(y)^{\top}(x-y),\forall x,y\in\mathcal{S}$

For second-order differentiable function $f(x)$, it is convex if and only if
$\nabla^{2}f(x)\succeq 0$.

For the non-differentiable convex function $f(x)$, the above inequality still
holds when we replace the gradient $\nabla f(y)$ with any element of the sub-
gradient, $\partial f(y)$, which is defined as the set of vectors satisfying
the above inequality for all $x\in\mathcal{S}$.

When a convex function $f(x)$ is $\ell$-strongly convex, it means $\forall
x,y\in\mathcal{S}$, we have

$f(x)\geq f(y)+\nabla f(y)^{\top}(x-y)+\frac{\ell}{2}\|x-y\|^{2}$

If $f(x)$ is second-order differentiable, $\ell$-strong convexity is
equivalent to $\nabla^{2}f(x)\succeq\ell I$.

Sometimes the convex function $f(x)$ is also $\mu$-smooth, which means its
gradient $\nabla f(x)$ satisfies the relation

$\|\nabla f(x)-\nabla f(y)\|\leq\mu\|x-y\|,$

which is also equivalent to $f(x)\leq f(y)+\nabla
f(y)^{\top}(y-x)+\frac{\mu}{2}\|x-y\|^{2}$.

The projection operator $\Pi_{\mathcal{S}}(y)$ is defined as
$\operatornamewithlimits{argmin}_{x\in\mathcal{S}}\|x-y\|$. An important
property of this operator that we use a lot in this thesis is the Pythagorean
theorem, which is listed below for completeness:

######  Theorem 2.1 (Pythagoras, circa 500 BC).

Let $y\in\mathbb{R}^{n}$, $\mathcal{S}\subseteq\mathbb{R}^{n}$ be a convex
set, and $x=\Pi_{\mathcal{S}}(y)$. Then we have the following inequality

$\|y-z\|\geq\|x-z\|,\forall z\in\mathcal{S}$

Many OCO algorithms are designed by using the above convex optimization tools.
To measure the effectiveness of these OCO algorithms, one commonly used metric
is called _regret_. _Static regret_ $\mathcal{R}_{s}$ is one type of the
regret defined as

$\mathcal{R}_{s}=\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(\theta^{*})$

where $\theta_{1},\theta_{2},\dots,\theta_{T}$ is the prediction sequence
given by the OCO algorithm,
$\theta^{*}=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}\sum\limits_{t=1}^{T}f_{t}(\theta)$
is a fixed comparator, and $T$ is called time horizon.

According to [35], the solution to the above static regret is called Hannan
consistent if $\mathcal{R}_{s}$ is sub-linear in $T$, which means the
prediction sequence will converge to $\theta^{*}$, the best fixed solution in
hindsight. In order to achieve the useful regret bound, the following
assumptions are required: 1\. the gradient $\nabla f_{t}(\theta)$ is upper
bounded; 2\. the convex constraint set $\mathcal{S}$ is compact and bounded.

####  5.2 Online Gradient Descent

The most classic OCO algorithm designed for convex objective is called Online
Gradient Descent (OGD) proposed by [18] in 2003. The update rule after the
observation $f_{t}(\theta)$ is

$\begin{array}[]{l}\hat{\theta}_{t+1}=\theta_{t}-\eta_{t}\nabla
f_{t}(\theta_{t})\\\
\theta_{t+1}=\Pi_{\mathcal{S}}(\hat{\theta}_{t+1})\end{array}$

where $\eta_{t}$ is the step size at time step $t$ and we abuse the
subgradient notation when $f_{t}$ is not differentiable by denoting it as
$\nabla f_{t}(\theta_{t})$.

Although the above update rule is very simple, which is just doing gradient
descent and then projecting back to the feasible set, it has an optimal static
regret theoretical guarantee. In other words, by setting $\eta_{t}$ to be
equal to $O(1/\sqrt{T})$ or $O(1/\sqrt{t})$, the $\mathcal{R}_{s}$ can be
upper bounded by $O(\sqrt{T})$, which meets the lower bound shown in [15].
Note that when $f_{t}$ is $\ell$-strongly convex, $\mathcal{R}_{s}$ can be
upper bounded by $O(\log T)$ by having $\eta_{t}=\frac{1}{\ell t}$, which is
also optimal [24].

According to [36], OGD is a special case of Online Mirror Descent (OMD) when
the distance function $\psi$ is the squared Euclidean one
($\psi(x)=\frac{1}{2}\|x\|^{2}$). For the OMD algorithm, its prediction for
the time step $t+1$ is updated as

$\theta_{t+1}=\operatornamewithlimits{argmin}\limits_{\theta\in\mathcal{S}}\eta_{t}\nabla
f_{t}(\theta_{t})^{\top}(\theta-\theta_{t})+d_{\psi}(\theta,\theta_{t})$

where $d_{\psi}$ is the Bregman divergence defined as
$d_{\psi}(x,y)=\psi(x)-\psi(y)-\nabla\psi(y)^{\top}(x-y)$ with $\psi$ being
the strongly convex differentiable function.

When the constraint set $\mathcal{S}$ is specified to the unit simplex
constraint $\mathcal{S}=\\{\theta:\|\theta\|_{1}=1,\theta\geq 0\\}$, the above
OMD update rule has closed-form solution if the Bregman divergence $d_{\psi}$
is replaced by the relative entropy. The closed-form update is

$\begin{array}[]{l}\theta_{t+1,i}=\frac{\theta_{t,i}\exp(-\eta_{t}\nabla
f_{t}(\theta_{t})_{i})}{\sum_{j=1}^{n}\theta_{t,j}\exp(-\eta_{t}\nabla
f_{t}(\theta_{t})_{i})}\end{array}$

which is called Exponentiated Gradient Descent [37].

####  5.3 Online Newton Step

The OMD and OGD are designed for the general convex objective function. When
the objective function is $\alpha$-exp-concave, we could use Online Newton
Step (ONS) to further reduce its upper bound from $O(\sqrt{T})$ to $O(\log
T)$.

The definition of being $\alpha$ exp-concave is that the function $e^{-\alpha
f_{t}(\theta)}$ is concave. If $f_{t}$ is twice differentiable, it can be
shown that $f_{t}$ is $\alpha$-exp-concave if and only if

$\nabla^{2}f_{t}(x)\succeq\alpha\nabla f_{t}(x)\nabla f_{t}(x)^{\top}$

for all $x\in\mathcal{S}$. What’s more, class of being exp-concave functions
is broader than the strongly convex class if the gradient is bounded, as shown
in [24, 38].

The update rule of ONS [24] is described below

$\begin{array}[]{l}A_{t}=A_{t-1}+\nabla f_{t}(\theta_{t})\nabla
f_{t}(\theta_{t})^{\top}\\\
\hat{\theta}_{t+1}=\theta_{t}-\frac{1}{\gamma}A_{t}^{-1}\nabla
f_{t}(\theta_{t})\\\
\theta_{t+1}=\Pi_{\mathcal{S}}^{P_{t}}(\hat{\theta}_{t+1})\end{array}$

where
$\Pi_{\mathcal{S}}^{P_{t}}(y)=\operatornamewithlimits{argmin}_{z\in\mathcal{S}}\|z-y\|_{P_{t}}^{2}$
is the projection onto $\mathcal{S}$ with respect to the norm induced by
$P_{t}$.

####  5.4 Dynamic OCO

When the goal of the OCO algorithm is to track the changes of the underlying
environments, the classic static regret is not appropriate anymore. This is
because the algorithms achieving sub-linear static regret only guarantee that
the prediction will converge to the single best fixed solution in hindsight
[39, 20, 22].

In order to better track the changes of the underlying environments, _dynamic
regret_ is proposed to compare the cumulative loss against that incurred by a
comparison sequence, $z_{1},\ldots,z_{T}\in\mathcal{S}$:

$\mathcal{R}_{d}=\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(z_{t})$

The classic OGD [18] achieves dynamic regret of order $O(\sqrt{T}(1+V))$,
where $V$ is a bound on the path length of the comparison sequence:

$\sum_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq V.$

This has been improved to $O(\sqrt{T(1+V)})$ in [22] by applying a meta-
optimization over different step sizes.

There are also other ways to bound the dynamic regret including a variant of
path-length [39], functional variation [20], as well as gradient variation
[40].

####  5.5 Adaptive OCO

Adaptive OCO algorithms are also concerned with how to enable the algorithms
to better track changing environments. Different from the Dynamic OCO setup,
the Adaptive OCO uses a ’different’ performance metric called _adaptive
regret_ defined as the maximum static regret over any contiguous time interval

$\mathcal{R}_{a}=\max_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}f_{t}(\theta_{t})-\min\limits_{\theta\in\mathcal{S}}\sum\limits_{t=r}^{s}f_{t}(\theta)\Big{\\}}$

To upper bound the adaptive regret $\mathcal{R}_{a}$, [19] proposed to run a
pool of OGD or OMD with different step sizes and different starting points.
Compared with the classic OGD or OMD, its running time is increased by an
order of $\log(T)$ due to the total number of the parallel running algorithms
is $O(\log T)$.

Most recently, [6, 7] discovered that for the specific online expert problem,
there is no need to run a pool of algorithms in order to bound the adaptive
regret. Instead, they showed that the same adaptive regret performance
guarantee can be obtained by incorporating the fixed-share step [5] into the
Exponentiated Gradient update, which not only reduces the running time by
$O(\log T)$, but also makes the update easy to implement.

###  6 Online Principal Component Analysis

The purpose of the online Principal Component Analysis (online PCA) is to find
the underlying subspace for the sequential data/observation to be projected to
[10, 11].

To achieve sub-linear static regret, [10] extended the idea of selecting the
subset of experts to the subset selection of the subspace. Due to the
eigendecomposition at every time step, the online PCA’s computational
complexity is $O(n^{3})$, where $n$ is the dimension of the data/observation.
This online PCA idea was used in the online variance minimization [9].

In order to reduce the running time, we need to avoid the eigendecomposition
step in [10]. [41] proposed another algorithm replacing the full
eigendecomposition at each time step by the problem finding $k$ principal
components of the current covariance matrix that is perturbed by Gaussian
noise. In this way, the algorithm requires $O(kn^{2})$ per time step with a
worse static regret bound, which is off by a factor of $O(n^{1/4})$.

###  7 OCO with Long-term Constraint

Online Convex Optimization (OCO) with long-term constraint is first proposed
by [42] in 2012, aiming to accelerate the OCO algorithms to achieve real
online computation. The problem it tried to solve is the high computational
complexity of the projection operator step for constrained OCO algorithms.

To do that, it used a closed-form update to approximate the true desired
projection step at the cost of the constraint violation for some time steps.
Its main goal is still keeping the static regret in a sub-linear order, but it
also aims to make sure that there is no constraint violation on average. More
specifically, it can get $\mathcal{R}_{s}\leq O(\sqrt{T})$, while the sum of
the constraint functions $\sum\limits_{t=1}^{T}g(\theta_{t})$ is upper bounded
by $O(T^{3/4})$.

The above result is later improved by [43] via designing a version with time-
dependent step size, which can have $\mathcal{R}_{s}\leq
O(T^{\max\\{\beta,1-\beta\\}})$ and $\sum\limits_{t=1}^{T}g(\theta_{t})\leq
O(T^{1-\beta/2})$ with $\beta\in(0,1)$.

Later on, [12] considered the stochastic version of the problem. Instead of
following update idea in [42, 43], it used the idea in the stochastic network
optimization to handle time-dependent constraints. Although both the static
regret and the long-term constraint $\sum\limits_{t=1}^{T}g(\theta_{t})$ can
be upper bounded by $O(\sqrt{T})$, it requires a very strong additional Slater
condition, which does not hold for many problems like equality constraint.

The long-term idea is also extended to do the online resource allocation. [12]
applied it to the online job scheduling (although not appropriate as explained
in Chapter 5). [14] used the long-term idea in an online budget allocation
problem. Compared with [12], [14] has a tighter regret guarantee due to the
increasing difficulty in finding a feasible comparator in [12].

##  Chapter 3 Trading-Off Static and Dynamic Regret in Online Least-Squares
and Beyond

In this chapter, we are mainly concerned with online discounted recursive
least-squares and how the discounted factor idea can be used to derive
improved dynamic regret as well as dynamic/static regret trade-off in
different problem setups.

As discussed in the previous chapters, the general procedure for online
learning algorithms is as follows: at each time $t$, before the true time-
dependent objective function $f_{t}(\theta)$ is revealed, we need to make the
prediction, $\theta_{t}$, based on the history of the observations
$f_{i}(\theta)$, $i<t$. Then the value of $f_{t}(\theta_{t})$ is the loss
suffered due to the lack of the knowledge for the true objective function
$f_{t}(\theta)$. Our prediction is then updated to include the information of
$f_{t}(\theta)$. This whole process is repeated until termination. The
functions, $f_{t}(\theta)$, can be chosen from a function class in an
arbitrary, possibly adversarial manner.

The performance of an online learning algorithm is typically assessed using
various notions of _regret_. _Static regret_ , $\mathcal{R}_{s}$, measures the
difference between the algorithm’s cumulative loss and the cumulative loss of
the best fixed decision in hindsight [35]:

$\mathcal{R}_{s}=\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\min\limits_{\theta\in\mathcal{S}}\sum\limits_{t=1}^{T}f_{t}(\theta),$

where $\mathcal{S}$ is a constraint set. For convex functions, variations of
gradient descent achieve static regret of $O(\sqrt{T})$, while for strongly
convex functions these can be improved to $O(\log T)$ [1]. However, when the
underlying environment is changing, due to the fixed comparator [5] the
algorithm converges to, static regret is no longer appropriate.

In order to better track the changes of the underlying environments, _dynamic
regret_ is proposed to compare the cumulative loss against that incurred by a
comparison sequence, $z_{1},\ldots,z_{T}\in\mathcal{S}$:

$\mathcal{R}_{d}=\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(z_{t})$

The classic work on online gradient descent [18] achieves dynamic regret of
order $O(\sqrt{T}(1+V))$, where $V$ is a bound on the path length of the
comparison sequence:

$\sum_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq V.$

This has been improved to $O(\sqrt{T(1+V)})$ in [22] by applying a meta-
optimization over step sizes.

In works such as [21, 44], it is assumed that
$z_{t}=\theta_{t}^{*}=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}f_{t}(\theta)$.
We denote that particular version of dynamic regret by:

$\mathcal{R}_{d}^{*}=\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(\theta^{*}_{t})$

In particular, if $V^{*}$ is the corresponding path length:

$V^{*}=\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|,$
(1)

then [21] shows that for strongly convex functions, $\mathcal{R}_{d}^{*}$ of
order $O(V^{*})$ is obtained by gradient descent. However, as pointed out by
[22], $V^{*}$ metric is too pessimistic and unsuitable for stationary
problems, which will result in poor generalization due to the random
perturbation caused by sampling from the _same_ distribution. Thus, a trade-
off between static regret $\mathcal{R}_{s}$ and dynamic regret
$\mathcal{R}_{d}^{*}$ is desired to maintain the abilities of both
generalization to stationary problem and tracking to the local changes.

_Adaptive regret_ [19] is another metric when dealing with changing
environments, which is defined as the maximum static regret over any
contiguous time interval. Although it shares the similar goal as the dynamic
regret, their relationship is still an open question.

Closely related to the problem of online learning is adaptive filtering, in
which time series data is predicted using a filter that is designed from past
data [45]. The performance of adaptive filters is typically measured in an
average case setting under statistical assumptions. One of the most famous
adaptive filtering techniques is recursive least squares, which bears strong
resemblance to the online Newton method of [24]. The work in [24] proves a
static regret bound of $O(\log T)$ for online Newton methods, but dynamic
regret bounds are not known.

In order to have an algorithm that adapts to non-stationary data, it is common
to use a forgetting factor in recursive least squares. [46] analyzed the
effect of the forgetting factor in terms of the tracking error covariance
matrix, and [47] made the tracking error analysis with the assumptions that
the noise is sub-Gaussian and the parameter follows a drifting model. However,
none of the analysis mentioned is done in terms of the regret, which
eliminates any noise assumption. For the online learning, [48] analyzed the
discounted UCB, which uses the discounted empirical average as the estimate
for the upper confidence bound. [49] used the weighted least-squares to update
the linear bandit’s underlying parameter.

This chapter is adapted from the published work [38], and we are mainly
concerned with exp-concave and strongly convex objectives. The following is a
summary of the main results:

  1. 1.

For exp-concave and strongly convex problems, we propose a discounted Online
Newton algorithm which generalizes recursive least squares with forgetting
factors and the original online Newton method of [24]. We show how tuning the
forgetting factor can achieve a dynamic regret bound of
$\mathcal{R}_{d}\leq\max\\{O(\log T),O(\sqrt{TV})\\}$. This gives a rigorous
analysis of forgetting factors in recursive least squares and improves the
bounds described in [22]. However, this choice requires a bound on the path
length, $V$. For an alternative choice of forgetting factors, which does not
require path length knowledge, we can simultaneously bound static regret by
$\mathcal{R}_{s}\leq O(T^{1-\beta})$ and dynamic regret by
$\mathcal{R}_{d}\leq\max\\{O(T^{1-\beta}),O(T^{\beta}V)\\}$. Note that tuning
$\beta$ produces a trade-off between static and dynamic regret.

  2. 2.

Based on the analysis of discounted recursive least squares, we derive a novel
step size rule for online gradient descent. Using this step size rule for
smooth, strongly convex functions we obtain a static regret bound of
$\mathcal{R}_{s}\leq O(T^{1-\beta})$ and a dynamic regret bound against
$\theta_{t}^{*}=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}f_{t}(\theta)$
of $\mathcal{R}_{d}^{*}\leq O(T^{\beta}(1+V^{*}))$. This improves the trade-
off obtained in the exp-concave case, since static regret or dynamic regret
can be made small by appropriate choice of $\beta\in(0,1)$.

  3. 3.

We show how the step size rule can be modified further so that gradient
descent recovers the $\max\\{O(\log T),O(\sqrt{TV})\\}$ dynamic regret bounds
obtained by discounted Online Newton methods. However, as above, these bounds
require knowledge of the bound on the path length, $V$.

  4. 4.

Finally, we describe a meta-algorithm, similar to that used in [22], which can
recover the $\max\\{O(\log T),O(\sqrt{TV})\\}$ dynamic regret bounds without
knowledge of $V$. These bounds are tighter than those in [22], since they
exploit exp-concavity to reduce the loss incurred by running an experts
algorithm. Furthermore, we give a lower bound for the corresponding problems,
which matches the obtained upper bound for certain range of $V$.

###  8 Discounted Online Newton Algorithm

As described above, the online Newton algorithm from [24] strongly resembles
the classic recursive least squares algorithm from adaptive filtering [45].
Currently, only the static regret of the online Newton method is studied. To
obtain more adaptive performance, forgetting factors are often used in
recursive least squares. However, the regret of forgetting factor algorithms
has not been analyzed. This section proposes a class of algorithms that
encompasses recursive least squares with forgetting factors and the online
Newton algorithm. We show how dynamic regret bounds for these methods can be
obtained by tuning the forgetting factor.

First we describe the problem assumptions. Throughout this chapter we assume
that $f_{t}:\mathcal{S}\to\mathbb{R}$ are convex, differentiable functions,
$\mathcal{S}$ is a compact convex set, $\|x\|\leq D$ for all
$x\in\mathcal{S}$, and $\|\nabla f_{t}(x)\|\leq G$ for all $x\in\mathcal{S}$.
Without loss of generality, we assume throughout the chapter that $D\geq 1$.

In this section we assume that all of the objective functions,
$f_{t}:\mathcal{S}\to\mathbb{R}$ are $\alpha$-exp-concave for some $\alpha>0$.
This means that $e^{-\alpha f_{t}(\theta)}$ is concave.

If $f_{t}$ is twice differentiable, it can be shown that $f_{t}$ is
$\alpha$-exp-concave if and only if

$\nabla^{2}f_{t}(x)\succeq\alpha\nabla f_{t}(x)\nabla f_{t}(x)^{\top}$ (2)

for all $x\in\mathcal{S}$.

For an $\alpha$-exp-concave function $f_{t}$, Lemma 4.2 of [1] implies that
the following bound holds for all $x$ and $y$ in $\mathcal{S}$ with $\rho$
$\leq$ $\frac{1}{2}\min\\{\frac{1}{4GD},\alpha\\}$:

$\displaystyle f_{t}(y)\geq f_{t}(x)+\nabla
f_{t}(x)^{\top}(y-x)+\frac{\rho}{2}(x-y)^{\top}\nabla f_{t}(x)\nabla
f_{t}(x)^{\top}(x-y).$ (3a)

In some variations on the algorithm, we will require extra conditions on the
function, $f_{t}$. In particular, in one variation we will require
$\ell$-strong convexity. As shown in the previous chapter, this means that
there is a number $\ell>0$ such that

$\displaystyle f_{t}(y)\geq f_{t}(x)+\nabla
f_{t}(x)^{\top}(y-x)+\frac{\ell}{2}\|x-y\|^{2}$ (3b)

for all $x$ and $y$ in $\mathcal{S}$. For twice-differentiable functions,
strong convexity implies $\alpha$-exp-concavity for $\alpha\leq\ell/G^{2}$ on
$\mathcal{S}$.

In another variant, we will require that the following bound holds for all $x$
and $y$ in $\mathcal{S}$:

$\displaystyle f_{t}(y)\geq f_{t}(x)+\nabla
f_{t}(x)^{\top}(y-x)+\frac{1}{2}\|x-y\|_{\nabla^{2}f_{t}(x)}^{2}.$ (3c)

This bound does not correspond to a commonly used convexity class, but it does
hold for the important special case of quadratic functions:
$f_{t}(x)=\frac{1}{2}\|y_{t}-A_{t}x\|^{2}$. This fact will be important for
analyzing the classic discounted recursive least-squares algorithm. Note that
if $y_{t}$ and $A_{t}$ are restricted to compact sets, $\alpha$ can be chosen
so that $f_{t}$ is $\alpha$-exp-concave.

Additionally, the algorithms for strongly convex functions and those
satisfying (3c) will require that the gradients $\nabla f_{t}(x)$ are
$u$-Lipschitz for all $x\in\mathcal{S}$ (equivalently, $f_{t}(x)$ is
$u$-smooth as discussed in the previous chapter), which means the gradient
$\nabla f_{t}(x)$ satisfies the relation

$\left\|\nabla f_{t}(x)-\nabla f_{t}(y)\right\|\leq
u\left\|x-y\right\|,\forall t.$

This smoothness condition is equivalent to $f_{t}(y)\leq f_{t}(x)+\nabla
f_{t}(x)^{\top}(y-x)+\frac{u}{2}\left\|y-x\right\|^{2}$ and implies, in
particular, that $\nabla^{2}f_{t}(x)\preceq uI$.

Algorithm 1 Discounted Online Newton Step

Given constants $\epsilon>0$, $\eta>0$, and $\gamma\in(0,1)$.

Let $\theta_{1}\in\mathcal{S}$ and $P_{0}=\epsilon I$.

for t=1,…,T do

Play $\theta_{t}$ and incur loss $f_{t}(\theta_{t})$

Observe $\nabla_{t}=\nabla f_{t}(\theta_{t})$ and
$H_{t}=\nabla^{2}f_{t}(\theta_{t})$ (if needed)

Update $P_{t}$:  $\displaystyle P_{t}$ $\displaystyle=\gamma
P_{t-1}+\nabla_{t}\nabla_{t}^{\top}$ (Quasi-Newton) (4a) $\displaystyle P_{t}$
$\displaystyle=\gamma P_{t-1}+H_{t}$ (Full-Newton) (4b)

Update $\theta_{t}$:
$\theta_{t+1}=\Pi_{\mathcal{S}}^{P_{t}}\left(\theta_{t}-\frac{1}{\eta}P_{t}^{-1}\nabla_{t}\right)$

end for

To accommodate these three different cases, we propose Algorithm 1, in which
$\Pi_{\mathcal{S}}^{P_{t}}(y)=\operatornamewithlimits{argmin}_{z\in\mathcal{S}}\|z-y\|_{P_{t}}^{2}$
is the projection onto $\mathcal{S}$ with respect to the norm induced by
$P_{t}$.

By using Algorithm 1, the following theorem can be obtained:

######  Theorem 3.1.

Consider the following three cases of Algorithm 1:

  1. 1.

$f_{t}$ is $\alpha$-exp-concave. The algorithm uses
$\eta\leq\frac{1}{2}\min\\{\frac{1}{4GD},\alpha\\}$, $\epsilon=1$ 222The value
used here is only for proof simplicity, please see Section 12 for more
discussion., and (4a).

  2. 2.

$f_{t}$ is $\alpha$-exp-concave and $\ell$-strongly convex while $\nabla
f_{t}(x)$ is $u$-Lipschitz. The algorithm uses $\eta\leq\ell/u$, $\epsilon=1$,
and (4b).

  3. 3.

$f_{t}$ is $\alpha$-exp-concave and satisfy (3c) while $\nabla f_{t}(x)$ is
$u$-Lipschitz. The algorithm uses $\eta\leq 1$, $\epsilon=1$, and (4b).

For each of these cases, there are positive constants $a_{1},\ldots a_{4}$
such that

$\begin{array}[]{l}\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))\leq-
a_{1}T\log\gamma-a_{2}\log(1-\gamma)+\frac{a_{3}}{1-\gamma}V+a_{4}\end{array}$

for all $z_{1},\ldots,z_{T}\in\mathcal{S}$ such that
$\sum_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq V$.

Before proving the theorem, let us first describe some consequences of it.

######  Corollary 3.1.

Setting $\gamma=1-T^{-\beta}$ with $\beta\in(0,1)$ leads to the following
form:

$\begin{array}[]{ll}\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))\leq
O(T^{1-\beta}+\beta\log T+T^{\beta}V)\end{array}$

###### Proof.

The first term is bounded as:

$\displaystyle-T\log\gamma=-T\log(1-T^{-\beta})\leq\frac{T^{1-\beta}}{1-T^{-\beta}}=O(T^{1-\beta}),$

where the inequality follows from $-\log(1-x)\leq\frac{x}{1-x}$ for $0\leq
x<1$.

The other terms follow by direct calculation. ∎

This corollary guarantees that the static regret is bounded in the order of
$O(T^{1-\beta})$ since $V=0$ in that case. The dynamic regret is of order
$O(T^{1-\beta}+T^{\beta}V)$. By choosing $\beta\in(0,1)$, we are guaranteed
that both the static and dynamic regrets are both sublinear in $T$ as long as
$V<O(T)$. Also, small static regret can be obtained by setting $\beta$ near
$1$.

In the setting of Corollary 3.1, the algorithm parameters do not depend on the
path length $V$. Thus, the bounds hold for any path length, whether or not it
is known a priori. The next corollary shows how tighter bounds could be
obtained if knowledge of $V$ were exploited in choosing the discount factor,
$\gamma$.

######  Corollary 3.2.

Setting $\gamma=1-\frac{1}{2}\sqrt{\frac{\max\\{V,\log^{2}T/T\\}}{2DT}}$ leads
to the form:

$\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))\leq\max\\{O(\log
T),O(\sqrt{TV})\\}$

The proof is similar to the proof of Corollary 3.1.

Note that Corollary 3.2 implies that the discounted Newton method achieves
logarithmic static regret by setting $V=0$. This matches the bounds obtained
in [24]. For positive path lengths bounded by $V$, we improve the
$O(\sqrt{T(1+V)})$ dynamic bounds from [22]. However, the algorithm above
current requires knowing a bound on the path length, whereas [22] achieves its
bound without knowing the path length, a priori.

If we view $V$ as the variation budget that $z_{1}^{T}={z_{1},\dots,z_{T}}$
can vary over $\mathcal{S}$ like in [20], and use this as a pre-fixed value to
allow the comparator sequence to vary arbitrarily over the set of admissible
comparator sequence
$\\{z_{1}^{T}\in\mathcal{S}:\sum\limits_{t=2}^{T}\left\|z_{t}-z_{t-1}\right\|\leq
V\\}$, we can tune $\gamma$ in terms of $V$.

In order to bound the dynamic regret without knowing a bound on the path
length, the method of [22] runs a collection of gradient descent algorithms in
parallel with different step sizes and then uses a meta-optimization [35] to
weight their solutions. In a later section, we will show how a related meta-
optimization over the discount factor leads to $\max\\{O(\log
T),O(\sqrt{TV})\\}$ dynamic regret bounds for unknown $V$.

For the Algorithm 1, we need to invert $P_{t}$, which can be achieved in time
$O(n^{2})$ for the Quasi-Newton case in (4a) by utilizing the matrix inversion
lemma. However, for the Full-Newton step (4b), the inversion requires
$O(n^{3})$ time.

##### Proof of Theorem 3.1:

Before proving the theorem, the following observation is helpful.

######  Lemma 3.1.

If $P_{t}$ is updated via (4a) then
$\|P_{t}\|\leq\epsilon+\frac{G^{2}}{1-\gamma}$, while if $P_{t}$ is updated
via $\eqref{eq:fullP}$, then $\|P_{t}\|\leq\epsilon+\frac{u}{1-\gamma}$.

###### Proof.

First consider the quasi-Newton case. The bound holds at $P_{0}=\epsilon I$,
so assume that it holds at time $t-1$ for $t\geq 1$. Then, by induction we
have

$\displaystyle\|P_{t}\|=\|\gamma
P_{t-1}+\nabla_{t}\nabla_{t}\|\leq\gamma\|P_{t-1}\|+G^{2}\leq\gamma\epsilon+\frac{G^{2}}{1-\gamma}\leq\epsilon+\frac{G^{2}}{1-\gamma}.$

The full-Newton case is identical, except it uses the bound $\|H_{t}\|\leq u$.

∎

The generalized Pythagorean theorem implies that

$\displaystyle\|\theta_{t+1}-z_{t}\|_{P_{t}}^{2}$
$\displaystyle\leq\left\|\theta_{t}-\frac{1}{\eta}P_{t}^{-1}\nabla_{t}-z_{t}\right\|_{P_{t}}^{2}$
$\displaystyle=\|\theta_{t}-z_{t}\|_{P_{t}}^{2}+\frac{1}{\eta^{2}}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}-\frac{2}{\eta}\nabla_{t}^{\top}(\theta_{t}-z_{t}).$

Re-arranging shows that

$\nabla_{t}^{\top}(\theta_{t}-z_{t})\leq\frac{1}{2\eta}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}+\frac{\eta}{2}\Big{(}\|\theta_{t}-z_{t}\|_{P_{t}}^{2}-\|\theta_{t+1}-z_{t}\|_{P_{t}}^{2}\Big{)}$
(5)

Let $c_{1}$ be the upper bound on $\|P_{t}\|$ from Lemma 3.1. Then we can
lower bound $\|\theta_{t+1}-z_{t}\|_{P_{t}}^{2}$ by

$\displaystyle\|\theta_{t+1}-z_{t}\|_{P_{t}}^{2}$
$\displaystyle=\|\theta_{t+1}-z_{t+1}\|_{P_{t}}^{2}+\|z_{t+1}-z_{t}\|_{P_{t}}^{2}+2(\theta_{t+1}-z_{t+1})^{\top}P_{t}(z_{t+1}-z_{t})$
$\displaystyle\geq\|\theta_{t+1}-z_{t+1}\|_{P_{t}}^{2}-4Dc_{1}\|z_{t+1}-z_{t}\|$
(6)

Combining (5) and (6) gives

$\nabla_{t}^{\top}(\theta_{t}-z_{t})\leq\frac{1}{2\eta}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}+2Dc_{1}\eta\|z_{t+1}-z_{t}\|+\frac{\eta}{2}\left(\|\theta_{t}-z_{t}\|_{P_{t}}^{2}-\|\theta_{t+1}-z_{t+1}\|_{P_{t}}^{2}\right)$
(7)

Summing over $t$, dropping the term $-\|\theta_{T+1}-z_{T+1}\|_{P_{T}}^{2}$,
setting $z_{T+1}=z_{T}$, and re-arranging gives

$\sum_{t=1}^{T}\nabla_{t}^{\top}(\theta_{t}-z_{t})\leq\sum_{t=1}^{T}\frac{1}{2\eta}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}+2Dc_{1}\eta
V\\\
+\frac{\eta}{2}\epsilon\|\theta_{1}-z_{1}\|^{2}+\frac{\eta}{2}\sum_{t=1}^{T}(\theta_{t}-z_{t})^{\top}(P_{t}-P_{t-1})(\theta_{t}-z_{t})$
(8)

Now we will see how the choices of $\eta$ enable the final sum from (8) to
cancel the terms from (3). In Case 1, we have that
$\eta(P_{t}-P_{t-1})\preceq\eta\nabla_{t}\nabla_{t}^{\top}$ and the bound from
(3a) holds for $\rho=\eta$. In Case 2, $\eta(P_{t}-P_{t-1})\preceq\eta
H_{t}\preceq\ell I$. In Case 3, $\eta(P_{t}-P_{t-1})\preceq\eta H_{t}\preceq
H_{t}$. Thus in all cases, $\eta$ has been chosen so that combining the
appropriate term of (3) with (8) gives

$\begin{array}[]{ll}\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))&\leq\sum_{t=1}^{T}\frac{1}{2\eta}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}+2Dc_{1}\eta
V+2\eta\epsilon D^{2}\end{array}$ (9)

Now we will bound the first sum of (9). Note that
$\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}=\langle
P_{t}^{-1},\nabla_{t}\nabla_{t}^{\top}\rangle$. In Case 1, we have that
$\nabla_{t}\nabla_{t}^{\top}=P_{t}-\gamma P_{t-1}$, while in Cases 2 and 3, we
have that
$\nabla_{t}\nabla_{t}^{\top}\preceq\frac{1}{\alpha}H_{t}=\frac{1}{\alpha}(P_{t}-\gamma
P_{t-1})$. So, in Case 1, let $c_{2}=1$ and in Cases 2 and 3, let
$c_{2}=1/\alpha$. Then in all cases, we have that

$\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}\leq c_{2}\langle
P_{t}^{-1},P_{t}-\gamma P_{t-1}\rangle.$ (10)

Lemma 4.5 of [1] shows that

$\langle P_{t}^{-1},P_{t}-\gamma P_{t-1}\rangle\leq\log\frac{|P_{t}|}{|\gamma
P_{t-1}|}=\log\frac{|P_{t}|}{|P_{t-1}|}-n\log\gamma,$ (11)

where $n$ is the dimension of $x_{t}$.

Combining (10) with (11), summing, and then using the bound that
$\|P_{T}\|\leq c_{1}$ gives,

$\displaystyle\sum_{t=1}^{T}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}$
$\displaystyle\leq c_{2}\log|P_{T}|-c_{2}n\log\epsilon-nT\log\gamma$
$\displaystyle\leq c_{2}n\log\frac{c_{1}}{\epsilon}-c_{2}nT\log\gamma$ (12)

Recall that $c_{1}=\epsilon+\frac{c_{3}}{1-\gamma}$, where $c_{3}=G^{2}$ or
$c_{3}=u$, depending on the case. Then a more explicit upper bound on (12) is
given by:

$\sum_{t=1}^{t}\nabla_{t}^{\top}P_{t}^{-1}\nabla_{t}\leq
c_{2}n\log\left(1+\frac{c_{3}}{\epsilon(1-\gamma)}\right)-c_{2}nT\log\gamma.$
(13)

Combining (9) and (13) gives the bound:

$\begin{array}[]{l}\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))\leq-\frac{c_{2}nT}{2\eta}\log\gamma+\\\
\frac{c_{2}n}{2\eta}\log\left(1+\frac{c_{3}}{\epsilon(1-\gamma)}\right)+2D\eta\left(\epsilon+\frac{c_{3}}{1-\gamma}\right)V+2\eta\epsilon
D^{2}\end{array}$

The desired regret bound can now be found by simplifying the expression on the
right, using the fact that $\frac{1}{1-\gamma}>1$. ∎

###  9 From Forgetting Factors to a Step Size Rule

In the next few sections, we aim to derive gradient descent rules that achieve
similar static and regret bounds to the discounted Newton algorithm, without
the cost of inverting matrices. We begin by analyzing the special case of
quadratic functions of the form:

$f_{t}(\theta)=\frac{1}{2}\left\|\theta-y_{t}\right\|^{2},$ (14)

where $y_{t}\in\mathcal{S}$. In this case, we will see that discounted
recursive least squares can be interpreted as online gradient descent with a
special step size rule. We will show how this step size rule achieves a trade-
off between static regret and dynamic regret with the specific comparison
sequence
$\theta_{t}^{*}=y_{t}=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}f_{t}(\theta)$.
For a related analysis of more general quadratic functions,
$f_{t}(\theta)=\frac{1}{2}\|A_{t}\theta-y_{t}\|^{2}$, please see the appendix.

Note that the previous section focused on dynamic regret for arbitrary
comparison sequences, $z_{1}^{T}\in\mathcal{S}$. The analysis techniques in
this and the next section are specialized to comparisons against
$\theta_{t}^{*}=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}f_{t}(\theta)$,
as studied in works such as [21, 44].

Classic discounted recursive least squares corresponds to Algorithm 1 running
with full Newton steps, $\eta=1$, and initial matrix $P_{0}=0$. When $f_{t}$
is defined as in (14), we have that $P_{t}=\sum_{k=0}^{t-1}\gamma^{k}I$. Thus,
the update rule can be expressed in the following equivalent ways:

$\displaystyle\theta_{t+1}$
$\displaystyle=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}\sum\limits_{i=1}^{t}\gamma^{i-1}f_{t+1-i}(\theta)$
(15a)
$\displaystyle=\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\theta_{t}+\frac{1-\gamma}{1-\gamma^{t}}y_{t}$
(15b) $\displaystyle=\theta_{t}-P_{t}^{-1}\nabla f_{t}(\theta_{t})$ (15c)
$\displaystyle=\theta_{t}-\eta_{t}\nabla f_{t}(\theta_{t}),$ (15d)

where $\eta_{t}=\frac{1-\gamma}{1-\gamma^{t}}$. Note that since
$y_{t}\in\mathcal{S}$, no projection steps are needed.

The above update is the ubiquitous gradient descent with a changing step size.
The only difference between standard methods is the choice of $\eta_{t}$,
which will lead to the useful trade-off between dynamic and static regret.

By using the above update, we can get the relationship between
$\theta_{t+1}-\theta_{t}^{*}$ and $\theta_{t}-\theta_{t}^{*}$ as the following
result:

######  Lemma 3.2.

Let
$\theta_{t}^{*}=\operatornamewithlimits{argmin}_{\theta\in\mathcal{S}}f_{t}(\theta)$
in Eq.(14). When using the discounted recursive least-squares update in
Eq.(15), we have the following relation:

$\theta_{t+1}-\theta_{t}^{*}=\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}(\theta_{t}-\theta_{t}^{*})$

###### Proof.

Since $\theta_{t}^{*}$ $=$ $\operatornamewithlimits{argmin}f_{t}(\theta)$
$=y_{t}$, for $\theta_{t+1}-\theta_{t}^{*}$, we have:

$\begin{array}[]{ll}\theta_{t+1}-\theta_{t}^{*}=\theta_{t+1}-y_{t}=\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\theta_{t}+\frac{1-\gamma}{1-\gamma^{t}}y_{t}-y_{t}=\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}(\theta_{t}-y_{t})=\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}(\theta_{t}-\theta_{t}^{*})\end{array}$

∎

Recall from (1) that the path length of optimizer sequence is denoted by
$V^{*}$. With the help of Lemma 3.2, we can upper bound the dynamic regret in
the next theorem:

######  Theorem 3.2.

Let $\theta_{t}^{*}$ be the solution to $f_{t}(\theta)$ in Eq.(14). When using
the discounted recursive least-squares update in Eq.(15) with
$1-\gamma=1/T^{\beta},\beta\in(0,1)$, we can upper bound the dynamic regret
as:

$\mathcal{R}_{d}^{*}\leq
2DT^{\beta}\big{(}\left\|\theta_{1}-\theta_{1}^{*}\right\|+V^{*}\big{)}$

###### Proof.

According to the Mean Value Theorem, there exists a vector
$x\in\\{v|v=\delta\theta_{t}+(1-\delta)\theta_{t}^{*},\delta\in[0,1]\\}$ such
that $f_{t}(\theta_{t})-f_{t}(\theta_{t}^{*})=\nabla
f_{t}(x)^{T}(\theta_{t}-\theta_{t}^{*})\leq\left\|\nabla
f_{t}(x)\right\|\left\|\theta_{t}-\theta_{t}^{*}\right\|$. For our problem,
$\left\|\nabla
f_{t}(x)\right\|=\left\|x-y_{t}\right\|\leq\left\|x\right\|+\left\|y_{t}\right\|$.
For $\left\|x\right\|$, we have:

$\begin{array}[]{ll}\left\|x\right\|&=\left\|\delta\theta_{t}+(1-\delta)\theta_{t}^{*}\right\|\\\
&\leq\delta\left\|\theta_{t}\right\|+(1-\delta)\left\|y_{t}\right\|\\\
&=\delta\left\|\frac{\sum\limits_{i=1}^{t-1}\gamma^{i-1}y_{t-i}}{\sum\limits_{i=1}^{t-1}\gamma^{i-1}}\right\|+(1-\delta)\left\|y_{t}\right\|\leq
D\end{array}$

where the second inequality is due to $\left\|y_{i}\right\|\leq D,\forall i$.

As a result, the norm of the gradient can be upper bounded as $\left\|\nabla
f_{t}(x)\right\|\leq 2D$. Then we have
$\mathcal{R}_{d}^{*}=\sum\limits_{t=1}^{T}\Big{(}f_{t}(\theta_{t})-f_{t}(\theta_{t}^{*})\Big{)}\leq
2D\sum\limits_{t=1}^{T}\left\|\theta_{t}-\theta_{t}^{*}\right\|$. Now we could
instead upper bound
$\sum\limits_{t=1}^{T}\left\|\theta_{t}-\theta_{t}^{*}\right\|$, which can be
achieved as follows:

$\begin{array}[]{ll}\sum\limits_{t=1}^{T}\left\|\theta_{t}-\theta_{t}^{*}\right\|&=\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}-\theta_{t-1}^{*}+\theta_{t-1}^{*}-\theta_{t}^{*}\right\|\\\
&\leq\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=1}^{T-1}\left\|\theta_{t+1}-\theta_{t}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|\\\
&=\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=1}^{T-1}\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\left\|\theta_{t}-\theta_{t}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|\\\
&\leq\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=1}^{T}\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\left\|\theta_{t}-\theta_{t}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|\end{array}$

where in the second equality, we substitute the result from Lemma 3.2.

From the above inequality, we get

$\sum\limits_{t=1}^{T}\Big{(}1-\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\Big{)}\left\|\theta_{t}-\theta_{t}^{*}\right\|\leq\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|$

Since
$\Big{(}1-\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\Big{)}=\frac{1-\gamma}{1-\gamma^{t}}\geq
1-\gamma$, we get

$\begin{array}[]{ll}\sum\limits_{t=1}^{T}\left\|\theta_{t}-\theta_{t}^{*}\right\|&\leq\frac{1}{1-\gamma}\left\|\theta_{1}-\theta_{1}^{*}\right\|+\frac{1}{1-\gamma}\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|\\\
&=T^{\beta}(\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|)\end{array}$

Thus, $\mathcal{R}_{d}\leq
2D\sum\limits_{t=1}^{T}\left\|\theta_{t}-\theta_{t}^{*}\right\|\leq
2DT^{\beta}(\left\|\theta_{1}-\theta_{1}^{*}\right\|+\sum\limits_{t=2}^{T}\left\|\theta_{t}^{*}-\theta_{t-1}^{*}\right\|)$.
∎

Theorem 3.2 shows that if we choose the discounted factor
$\gamma=1-T^{-\beta}$ we obtain a dynamic regret of $O(T^{\beta}(1+V^{*}))$.
This is a refinement of the Corollary 3.1 since the bound no longer has the
$T^{1-\beta}$ term. Thus, the dynamic regret can be made small by choosing a
small $\beta$.

In the next theorem, we will show that this carefully chosen $\gamma$ can also
lead to useful static regret, which can give us a trade-off between them.

######  Theorem 3.3.

Let $\theta^{*}$ be the solution to $\min\sum\limits_{t=1}^{T}f_{t}(\theta)$.
When using the discounted recursive least-squares update in Eq.(15) with
$1-\gamma=1/T^{\beta},\beta\in(0,1)$, we can upper bound the static regret as:

$\mathcal{R}_{s}\leq O(T^{1-\beta})$

Recall that the algorithm of this section can be interpreted both as a
discounted recursive least squares method, and as a gradient descent method.
As a result, this theorem is actually a direct consequence of Corollary 3.1,
by setting $V=0$. However, we will give a separate proof, since the techniques
extend naturally to the analysis of more general work on gradient descent
methods of the next section.

Before presenting the proof, the following integral bound will be used in a
few places.

######  Lemma 3.3.

If $\gamma\in(0,1)$, then

$\sum_{t=1}^{T}\frac{1}{1-\gamma^{t}}\leq\frac{1}{1-\gamma}+T-1+\frac{\log(1-\gamma)}{\log\gamma}$

###### Proof.

$\displaystyle\sum\limits_{t=1}^{T}\frac{1}{1-\gamma^{t}}$
$\displaystyle\leq\frac{1}{1-\gamma}+\int_{1}^{T}\frac{1}{1-\gamma^{t}}\mathrm{d}t$
$\displaystyle=\frac{1}{1-\gamma}+\Big{(}t-\frac{\ln(1-\gamma^{t})}{\ln(\gamma)}\Big{)}\Big{|}_{1}^{T}$
$\displaystyle=\frac{1}{1-\gamma}+T-1+\frac{\ln(1-\gamma)}{\ln\gamma}-\frac{\ln(1-\gamma^{T})}{\ln\gamma}$
$\displaystyle\leq\frac{1}{1-\gamma}+T-1+\frac{\ln(1-\gamma)}{\ln\gamma}.$

∎

##### Proof of Theorem 3.3:

###### Proof.

To proceed, recall that the update in Eq.(15) is

$\begin{array}[]{ll}\theta_{t+1}&=\frac{\gamma-\gamma^{t}}{1-\gamma^{t}}\theta_{t}+\frac{1-\gamma}{1-\gamma^{t}}y_{t}=\theta_{t}-\eta_{t}\nabla
f_{t}(\theta_{t})\end{array}$

where $\eta_{t}=\frac{1-\gamma}{1-\gamma^{t}}$.

Then we get the relationship between $\nabla
f_{t}(\theta_{t})^{T}(\theta_{t}-\theta^{*})$ and
$\left\|\theta_{t}-\theta^{*}\right\|^{2}-\left\|\theta_{t+1}-\theta^{*}\right\|^{2}$
as:

$\begin{array}[]{ll}\left\|\theta_{t+1}-\theta^{*}\right\|^{2}&=\left\|\theta_{t}-\eta_{t}\nabla
f_{t}(\theta_{t})-\theta^{*}\right\|^{2}\\\
&=\left\|\theta_{t}-\theta^{*}\right\|^{2}-2\eta_{t}\nabla
f_{t}(\theta_{t})^{T}(\theta_{t}-\theta^{*})+\eta_{t}^{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}\end{array}$ $\begin{array}[]{ll}\nabla
f_{t}(\theta_{t})^{T}(\theta_{t}-\theta^{*})&=\frac{1}{2\eta_{t}}\big{(}\left\|\theta_{t}-\theta^{*}\right\|^{2}-\left\|\theta_{t+1}-\theta^{*}\right\|^{2}\big{)}+\frac{\eta_{t}}{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}\end{array}$

Moreover, we write $f_{t}(\theta^{*})$ as
$f_{t}(\theta^{*})=f_{t}(\theta_{t})+\nabla
f_{t}(\theta_{t})^{T}(\theta^{*}-\theta_{t})+\frac{1}{2}\left\|\theta^{*}-\theta_{t}\right\|^{2}$,
which combined with the previous equation gives us the following equation:

$\begin{array}[]{ll}f_{t}(\theta_{t})-f_{t}(\theta^{*})&=\frac{1}{2\eta_{t}}\big{(}\left\|\theta_{t}-\theta^{*}\right\|^{2}-\left\|\theta_{t+1}-\theta^{*}\right\|^{2}\big{)}+\frac{\eta_{t}}{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}-\frac{1}{2}\left\|\theta^{*}-\theta_{t}\right\|^{2}\\\
&\leq
2D^{2}\eta_{t}+\frac{1}{2\eta_{t}}\big{(}\left\|\theta_{t}-\theta^{*}\right\|^{2}-\left\|\theta_{t+1}-\theta^{*}\right\|^{2}\big{)}-\frac{1}{2}\left\|\theta^{*}-\theta_{t}\right\|^{2}\end{array}$

where the inequality is due to $\left\|\nabla f_{t}(\theta_{t})\right\|\leq
2D$ as shown in Theorem 3.2.

Sum the above inequality from $t=1$ to $T$, we get:

$\begin{array}[]{ll}\sum\limits_{t=1}^{T}\Big{(}f_{t}(\theta_{t})-f_{t}(\theta^{*})\Big{)}&\leq
2D^{2}\sum\limits_{t=1}^{T}\eta_{t}+\frac{1/\eta_{1}-1}{2}\left\|\theta_{1}-\theta^{*}\right\|^{2}\\\
&\quad+\frac{1}{2}\sum\limits_{t=2}^{T}\big{[}(\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-1)\left\|\theta^{*}-\theta_{t}\right\|^{2}\big{]}-\frac{1}{2\eta_{T}}\left\|\theta_{T+1}-\theta^{*}\right\|^{2}\end{array}$

Since $\eta_{t}=\frac{1-\gamma}{1-\gamma^{t}}$, $\eta_{1}=1$,
$\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-1<0$. Then for the static regret, we
have:

$\begin{array}[]{ll}\mathcal{R}_{s}=\sum\limits_{t=1}^{T}\Big{(}f_{t}(\theta_{t})-f_{t}(\theta^{*})\Big{)}\leq
2D^{2}\sum\limits_{t=1}^{T}\eta_{t}=2D^{2}(1-\gamma)\sum\limits_{t=1}^{T}\frac{1}{1-\gamma^{t}}\end{array}$
(16)

Now we will use the integral bound from Lemma 3.3 to bound the regret. Since
$1-\gamma=1/T^{\beta}$, $\frac{\log(1-\gamma)}{\log\gamma}=\frac{\beta\log
T}{\log(1+\frac{1}{T^{\beta}-1})}$. Since
$\log(1+x)\geq\frac{1}{2}x,x\in(0,1)$,
$\log(1+\frac{1}{T^{\beta}-1})\geq\frac{1}{2}\frac{1}{T^{\beta}-1}$. Thus, we
have $\frac{\log(1-\gamma)}{\log\gamma}\leq 2\beta(T^{\beta}-1)\log T$. Then
$(1-\gamma)\sum\limits_{t=1}^{T}\frac{1}{1-\gamma^{t}}=O(T^{1-\beta})$, which
results in $\mathcal{R}_{s}\leq O(T^{1-\beta})$. ∎

Theorems 3.2 and 3.3 build a trade-off between dynamic and static regret by
the carefully chosen discounted factor $\gamma$. Compared with the result from
the last section, there are two improvements: 1\. The two regrets are
decoupled so that we could reduce the $\beta$ to make the dynamic regret
result smaller than bound from Corollary 3.1; 2\. The update is the first-
order gradient descent, which is computationally more efficient than second
order methods.

In the next section, we will consider the strongly convex and smooth case,
whose result is inspired by this section’s analysis.

###  10 Online Gradient Descent for Smooth, Strongly Convex Problems

In this section, we generalize the results of the previous section idea to
functions which are $\ell$-strongly convex and $u$-smooth. We will see that
similar bounds on $\mathcal{R}_{s}$ and $\mathcal{R}_{d}^{*}$ can be obtained.

Our proposed update rule for the prediction $\theta_{t+1}$ at time step $t+1$
is:

$\theta_{t+1}=\operatornamewithlimits{argmin}\limits_{\theta\in\mathcal{S}}\left\|\theta-(\theta_{t}-\eta_{t}\nabla
f_{t}(\theta_{t}))\right\|^{2}$ (17)

where $\eta_{t}=\frac{1-\gamma}{\ell(\gamma-\gamma^{t})+u(1-\gamma)}$ and
$\gamma\in(0,1)$.

This update rule generalizes the step size rule from the last section.

Before getting to the dynamic regret, we will first derive the relation
between $\left\|\theta_{t+1}-\theta_{t}^{*}\right\|$ and
$\left\|\theta_{t}-\theta_{t}^{*}\right\|$ to try to mimic the result in Lemma
3.2 of the quadratic case:

######  Lemma 3.4.

Let $\theta_{t}^{*}\in\mathcal{S}$ be the solution to $f_{t}(\theta)$ which is
strongly convex and smooth. When we use the update in Eq.(17), the following
relation is obtained:

$\left\|\theta_{t+1}-\theta_{t}^{*}\right\|\leq\sqrt{1-\frac{l(1-\gamma)}{u(1-\gamma)+l\gamma}}\left\|\theta_{t}-\theta_{t}^{*}\right\|$

Since the idea is similar to the proof of Lemma 3.2, please refer to the
appendix for the proof.

Following the idea of Theorem 3.2, now we are ready to present the dynamic
regret result:

######  Theorem 3.4.

Let $\theta_{t}^{*}$ be the solution to $f_{t}(\theta),\theta\in\mathcal{S}$.
When using the update in Eq.(17) with $1-\gamma=1/T^{\beta},\beta\in(0,1)$, we
can upper bound the dynamic regret:

$\mathcal{R}_{d}^{*}\leq
G\big{(}2(T^{\beta}-1)+u/l\big{)}(\left\|\theta_{1}-\theta_{1}^{*}\right\|+V^{*})$

Since the proof follows the similar steps in the proof of Theorem 3.3, please
refer to the appendix.

Theorem 3.4’s result seems promising in achieving the trade-off, since it has
a similar form of the result from quadratic problems in Theorem 3.2. Next, we
will present the static regret result, which assures that the desired trade-
off can be obtained.

######  Theorem 3.5.

Let $\theta^{*}$ be the solution to
$\min\limits_{\theta\in\mathcal{S}}\sum\limits_{t=1}^{T}f_{t}(\theta)$. When
using the update in Eq.(17) with $1-\gamma=1/T^{\beta},\beta\in(0,1)$, we can
upper bound the static regret:

$\mathcal{R}_{s}\leq O(T^{1-\beta})$

The proof follows the similar steps in the proof of Theorem 3.3. Please refer
to the appendix.

The regret bounds of this section are similar to those obtained for simple
quadratics. Thus, this gradient descent rule maintains all of the advantages
over the discounted Newton method that were described in the previous section.

###  11 Online Gradient Descent for Strongly Convex Problems

In this section, we extend step size idea from previous section to problems
which are $\ell$-strongly convex, but not necessarily smooth. We obtain the
same order dynamic regret as the discounted online Newton method:
$\mathcal{R}_{d}$ $\leq$ $\max\\{O(\log T),O(\sqrt{TV})\\}$. However, our
analysis does not lead to the clean trade-off of $\mathcal{R}_{s}\leq
O(T^{1-\beta})$ and $\mathcal{R}_{d}^{*}\leq O(T^{\beta}(1+V^{*}))$ obtained
when smoothness is also used.

The update rule is online gradient descent:

$\theta_{t+1}=\operatornamewithlimits{argmin}\limits_{\theta\in\mathcal{S}}\left\|\theta-(\theta_{t}-\eta_{t}\nabla
f_{t}(\theta_{t}))\right\|^{2}$ (18)

where $\eta_{t}=\frac{1-\gamma}{\ell(1-\gamma^{t})}$, and $\gamma\in(0,1)$.

We can see that the update rule is the same as the one in Eq.(17) while the
step size $\eta_{t}$ is replaced with $\frac{1-\gamma}{\ell(1-\gamma^{t})}$.

By using the new step size with the update rule in Eq.(18), we can obtain the
following dynamic regret bound:

######  Theorem 3.6.

If using the update rule in Eq.(18) with
$\eta_{t}=\frac{1-\gamma}{\ell(1-\gamma^{t})}$ and $\gamma\in(0,1)$, the
following dynamic regret can be obtained:

$\sum\limits_{t=1}^{T}\Big{(}f_{t}(\theta_{t})-f_{t}(z_{t})\Big{)}\leq
2D\ell\frac{1}{1-\gamma}V+\frac{G^{2}}{2}\sum\limits_{t=1}^{T}\eta_{t}$

###### Proof.

According to the non-expansive property of the projection operator and the
update rule in Eq.(18), we have

$\begin{array}[]{ll}\left\|\theta_{t+1}-z_{t}\right\|^{2}&\leq\left\|\theta_{t}-\eta_{t}\nabla
f_{t}(\theta_{t})-z_{t}\right\|^{2}\\\
&=\left\|\theta_{t}-z_{t}\right\|^{2}-2\eta_{t}\nabla
f_{t}(\theta_{t})^{T}(\theta_{t}-z_{t})+\eta_{t}^{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}\end{array}$

The reformulation gives us

$\begin{array}[]{ll}\nabla
f_{t}(\theta_{t})^{T}(\theta_{t}-z_{t})&\leq\frac{1}{2\eta_{t}}\big{(}\left\|\theta_{t}-z_{t}\right\|^{2}-\left\|\theta_{t+1}-z_{t}\right\|^{2}\big{)}+\frac{\eta_{t}}{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}\end{array}$ (19)

Moreover, from the strong convexity, we have $f_{t}(z_{t})\geq
f_{t}(\theta_{t})+\nabla
f_{t}(\theta_{t})^{T}(z_{t}-\theta_{t})+\frac{\ell}{2}\left\|z_{t}-\theta_{t}\right\|^{2}$,
which is equivalent to $\nabla f_{t}(\theta_{t})^{T}(\theta_{t}-z_{t})\geq
f_{t}(\theta_{t})-f_{t}(z_{t})+\frac{\ell}{2}\left\|z_{t}-\theta_{t}\right\|^{2}$.
Combined with Eq.(19), we have

$\begin{array}[]{ll}f_{t}(\theta_{t})-f_{t}(z_{t})&\leq\frac{1}{2\eta_{t}}\big{(}\left\|\theta_{t}-z_{t}\right\|^{2}-\left\|\theta_{t+1}-z_{t}\right\|^{2}\big{)}+\frac{\eta_{t}}{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}-\frac{\ell}{2}\left\|z_{t}-\theta_{t}\right\|^{2}\end{array}$
(20)

Then we can lower bound $\|\theta_{t+1}-z_{t}\|^{2}$ by

$\begin{array}[]{ll}\|\theta_{t+1}-z_{t}\|^{2}&=\|\theta_{t+1}-z_{t+1}\|^{2}+\|z_{t+1}-z_{t}\|^{2}+2(\theta_{t+1}-z_{t+1})^{\top}(z_{t+1}-z_{t})\\\
&\geq\|\theta_{t+1}-z_{t+1}\|^{2}-4D\|z_{t+1}-z_{t}\|\end{array}$ (21)

Combining (20) and (21) gives

$\begin{array}[]{ll}f_{t}(\theta_{t})-f_{t}(z_{t})&\leq\frac{1}{2\eta_{t}}\big{(}\left\|\theta_{t}-z_{t}\right\|^{2}-\left\|\theta_{t+1}-z_{t+1}\right\|^{2}\big{)}+\frac{2D}{\eta_{t}}\|z_{t+1}-z_{t}\|\\\
&\quad+\frac{\eta_{t}}{2}\left\|\nabla
f_{t}(\theta_{t})\right\|^{2}-\frac{\ell}{2}\left\|z_{t}-\theta_{t}\right\|^{2}\end{array}$

Summing over $t$ from $1$ to $T$, dropping the term
$-\frac{1}{2\eta_{T}}\|\theta_{T+1}-z_{T+1}\|^{2}$, setting $z_{T+1}=z_{T}$,
using the inequality $\|\nabla f_{t}(\theta_{t})\|^{2}\leq G^{2}$, and re-
arranging gives

$\begin{array}[]{ll}\sum\limits_{t=1}^{T}\Big{(}f_{t}(\theta_{t})-f_{t}(z_{t})\Big{)}&\leq\frac{1}{2}(\frac{1}{\eta_{1}}-\ell)\|\theta_{1}-z_{1}\|^{2}+\frac{1}{2}\sum\limits_{t=1}^{T}(\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-\ell)\|\theta_{t}-z_{t}\|^{2}\\\
&\quad+2D\sum\limits_{t=1}^{T-1}\frac{1}{\eta_{t}}\|z_{t+1}-z_{t}\|+\frac{G^{2}}{2}\sum\limits_{t=1}^{T}\eta_{t}\\\
&\leq
2D\ell\frac{1}{1-\gamma}V+\frac{G^{2}}{2}\sum\limits_{t=1}^{T}\eta_{t}\end{array}$

where for the second inequality, we use the following results:
$\frac{1}{\eta_{1}}-\ell=0$,
$\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-\ell=\frac{\ell(1-\gamma)(\gamma^{t-1}-1)}{1-\gamma}\leq
0$,
$\frac{1}{\eta_{t}}=\frac{\ell(1-\gamma^{t})}{1-\gamma}\leq\frac{\ell}{1-\gamma}$,
and the definition of $V$.

∎

Similar to the case of discounted online Newton methods, if a bound on the
path length, $V$, is known, the discount factor can be tuned to achieve low
dynamic regret:

######  Corollary 3.3.

By setting $\gamma=1-\frac{1}{2}\sqrt{\frac{\max\\{V,\log^{2}T/T\\}}{2DT}}$,
the following bound can be obtained:

$\sum\limits_{t=1}^{T}\Big{(}f_{t}(\theta_{t})-f_{t}(z_{t})\Big{)}\leq\max\\{O(\log
T),O(\sqrt{TV})\\}.$

This result is tighter than the $O(\sqrt{T(1+V)})$ bound obtained by [22] on
convex functions, but not directly comparable to the $O(V^{*})$ bounds
obtained in [21] for smooth, strongly convex functions.

Similar to the Corollary 3.2 on discounted online Newton methods, Corollary
3.3 requires knowing $V$. In the next section, we will see how a meta-
algorithm can be used to obtain the same bounds without knowing $V$.

Please refer to the appendix for the proof of Corollary 3.3.

###  12 Meta-algorithm

In previous sections, we discussed the results on dynamic regret for both
$\alpha$-exp-concave and $\ell$-strongly convex objectives. The tightest
regret bounds were obtained by choosing a discount factor that depends on $V$,
a bound on the path length. In this section, we solve this issue by running
multiple algorithms in parallel with different discount factors.

For online convex optimization, a similar meta-algorithm has been used by [22]
to search over step sizes. However, the method of [22] cannot be used directly
in either the $\alpha$-exp-concave or $\ell$-strongly convex case due to the
added $O(\sqrt{T})$ regret from running multiple algorithms. In order to
remove this factor, we exploit the exp-concavity in the experts algorithm, as
in Chapter 3 in [35].

In this section, we will show that by using appropriate parameters and
analysis designed specifically for our cases, the meta-algorithm can be used
to solve our issues.

Algorithm 2 Meta-Algorithm

Given step size $\lambda$, and a set $\mathcal{H}$ containing discount factors
for each algorithm.

Activate a set of algorithms $\\{A^{\gamma}|\gamma\in\mathcal{H}\\}$ by
calling Algorithm 1 (exp-concave case) or the update in Eq.(18) (strongly
convex case) for each parameter $\gamma\in\mathcal{H}$.

Sort $\gamma$ in descending order
$\gamma_{1}\geq\gamma_{2}\geq\dots\geq\gamma_{N}$, and set
$w_{1}^{\gamma_{i}}=\frac{C}{i(i+1)}$ with $C=1+1/|\mathcal{H}|$.

for t=1,…,T do

Obtain $\theta_{t}^{\gamma}$ from each algorithm $A^{\gamma}$.

Play
$\theta_{t}=\sum\limits_{\gamma\in\mathcal{H}}w_{t}^{\gamma}\theta_{t}^{\gamma}$,
and incur loss $f_{t}(\theta_{t}^{\gamma})$ for each $\theta_{t}^{\gamma}$.

Update $w_{t}^{\gamma}$ by
$w_{t+1}^{\gamma}=\frac{w_{t}^{\gamma}\exp(-\lambda
f_{t}(\theta_{t}^{\gamma}))}{\sum\limits_{\mu\in\mathcal{H}}w_{t}^{\mu}\exp(-\lambda
f_{t}(\theta_{t}^{\mu}))}.$

Send back the gradient $\nabla f_{t}(\theta_{t}^{\gamma})$ for each algorithm
$A^{\gamma}$.

end for

####  12.1 Exp-concave Case

Before showing the regret result, we first show that the cumulative loss of
the meta-algorithm is comparable to all $A^{\gamma}\in\mathcal{H}$:

######  Lemma 3.5.

If $f_{t}$ is $\alpha$-exp-concave and $\lambda=\alpha$, the cumulative loss
difference of Algorithm 2 for any $\gamma\in\mathcal{H}$ is bounded as:

$\sum\limits_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(\theta_{t}^{\gamma}))\leq\frac{1}{\alpha}\log\frac{1}{w_{1}^{\gamma}}$

This result shows how $O(\sqrt{T})$ regret incurred by running an experts
algorithm is reduced in the $\alpha$-exp-concave case. The result is similar
to Proposition 3.1 of [35]. We also provide a proof in the appendix.

Based on the above lemma, if we can show that there exists an algorithm
$A^{\gamma}$, which can bound the regret
$\sum_{t=1}^{T}(f_{t}(\theta_{t}^{\gamma})-f_{t}(z_{t}))\leq\max\\{O(\log
T),O(\sqrt{TV})\\}$, then we can combine these two results and show that the
regret holds for $\theta_{t},t=1,\dots,T$ as well:

######  Theorem 3.7.

For any comparator sequence $z_{1},\dots,z_{T}\in\mathcal{S}$, setting
$\mathcal{H}=\Big{\\{}\gamma_{i}=1-\eta_{i}\Big{|}i=1,\dots,N\Big{\\}}$ with
$T\geq 2$ where $\eta_{i}=\frac{1}{2}\frac{\log T}{T\sqrt{2D}}2^{i-1}$,
$N=\lceil\frac{1}{2}\log_{2}(\frac{2DT^{2}}{\log^{2}T})\rceil+1$, and
$\lambda=\alpha$ leads to the result:

$\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))\leq O(\max\\{\log
T,\sqrt{TV}\\})$

As described previously, the proof’s main idea is to show that we could both
find an algorithm $A^{\gamma}$ bounding the regret
$\sum_{t=1}^{T}(f_{t}(\theta_{t}^{\gamma})-f_{t}(z_{t}))\leq\max\\{O(\log
T),O(\sqrt{TV})\\}$ and cover the $V$ with $O(\log T)$ different $\gamma$
choices. Please see the appendix for the formal proof.

In practice, we include the additional case when $\gamma=1$ to make the
overall algorithm explicitly balance the static regret. Also, the free
parameter $\epsilon$ used in Algorithm 1 is important for the actual
performance. If it is too small, the update will be easily effected by the
gradient to have high generalization error. In practice, it can be set to be
equal to $1/(\rho^{2}D^{2})$ or $1/(\rho^{2}D^{2}N)$ with
$\rho=\frac{1}{2}\min\\{\frac{1}{4GD},\alpha\\}$ like in [1].

####  12.2 Strongly Convex Case

For the strongly convex problem, since the parameter $\gamma$ used in
Corollary 3.3 is the same as the one in Corollary 3.2, it seems likely that
the meta-algorithm should work with the same setup in as Theorem 3.7. The only
parameter that needs to be changed is $\lambda$, which was set above to
$\alpha$, the parameter of $\alpha$-exp-concavity.

To proceed, we first show that the $\ell$-strongly convex function with
bounded gradient is also $\ell/G^{2}$-exp-concave (e.g.,$\left\|\nabla
f_{t}\right\|$$\leq$$G$). Previous works also pointed out this, but their
statement only works when $f_{t}$ is second-order differentiable, while our
result is true when $f_{t}$ is first-order differentiable.

######  Lemma 3.6.

For the $\ell$-strongly convex function $f_{t}$ with $\|\nabla f_{t}\|\leq G$,
it is also $\alpha$-exp-concave with $\alpha=\ell/G^{2}$.

Please refer to the appendix for the proof.

Lemma 3.6 indicates that running Algorithm 2 with strongly convex function
leads to the same result as in Lemma 3.5. Thus, using the similar idea as
discussed in the case of $\alpha$-exp-concavity and Algorithm 2, the theorem
below can be obtained:

######  Theorem 3.8.

For any comparator sequence $z_{1},\dots,z_{T}\in\mathcal{S}$, setting
$\mathcal{H}=\Big{\\{}\gamma_{i}=1-\eta_{i}\Big{|}i=1,\dots,N\Big{\\}}$ with
$T\geq 2$ where $\eta_{i}=\frac{1}{2}\frac{\log T}{T\sqrt{2D}}2^{i-1}$,
$N=\lceil\frac{1}{2}\log_{2}(\frac{2DT^{2}}{\log^{2}T})\rceil+1$, and
$\lambda=\ell/G^{2}$ leads to the result:

$\sum_{t=1}^{T}(f_{t}(\theta_{t})-f_{t}(z_{t}))\leq O(\max\\{\log
T,\sqrt{TV}\\})$

Since the proof shares the same idea as Theorem 3.7, please refer to the
appendix for the proof.

As discussed in the previous subsection, in practice, we also include the case
when $\gamma=1$ to make the overall algorithm explicitly balance the static
regret and set $\epsilon$ accordingly as in the exp-concave case.

####  12.3 A Lower Bound

In the previous subsections, we show how to achieve the improved dynamic
regret for both the exp-concave and strongly convex problems without knowing
$V$. In this subsection, we will give a lower bound, which approaches the
upper bound for large and small $V$.

######  Proposition 3.1.

For losses of the form $f_{t}(\theta)=(\theta-\epsilon_{t})^{2}$, for all
$\gamma_{0}\in(0,1)$ and all $V=T^{\frac{2+\gamma_{0}}{4-\gamma_{0}}}$, there
is a comparison sequence $z_{1}^{T}$ such that
$\sum\limits_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq V$ and

$\mathcal{R}_{d}\geq\max\\{O(\log
T),O\big{(}(VT)^{\frac{\gamma_{0}}{2}}\big{)}\\}.$

The above result has the following indications: 1\. For $V=o(T)$ but
approaching to $T$, it is impossible to achieve better bound of
$\mathcal{R}_{d}\geq O\Big{(}(VT)^{\frac{\alpha_{0}}{2}}\Big{)}$ with
$\alpha_{0}<1$. 2\. For other ranges of $V$ like $V=O(\sqrt{T})$, its lower
bound is not established and still an open question.

##### Proof of Proposition 3.1:

###### Proof.

Since strongly convex problem with bounded gradient is also exp-concave due to
Lemma 3.6 shown in the next section, we will only consider the strongly convex
problem.

For the case when $V=0$, $\mathcal{R}_{d}$ reduces to the static regret
$\mathcal{R}_{s}$, which has the lower bound $O(\log T)$ as shown in [15].

Let us now consider the case when $V>0$. The analysis is inspired by [44]. We
will use $f_{t}(\theta)=(\theta-\epsilon_{t})^{2}$ as the special case to show
the lower bound. Here $\epsilon_{1}^{T}$ is a sequence of independently
generated random variables from $\\{-2\sigma,2\sigma\\}$ with equal
probabilities. For the dynamic regret
$\mathcal{R}_{d}=\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\min\limits_{z_{1}^{T}\in\mathcal{S}_{V}}\sum\limits_{t=1}^{T}f_{t}(z_{t})\geq\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(z_{t})$,
where $\mathcal{S}_{V}=\\{z_{1}^{T}:\sum\limits_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq
V\\}$, and $z_{t}=\frac{1}{2}\epsilon_{t}$. As a result, the expected value of
$\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(z_{t})$ is
$\mathbb{E}[\sum\limits_{t=1}^{T}f_{t}(\theta_{t})-\sum\limits_{t=1}^{T}f_{t}(z_{t})]$
$=$
$\mathbb{E}[\sum\limits_{t=1}^{T}(\theta_{t}^{2}-2\theta_{t}\epsilon_{t}+\frac{3}{4}\epsilon_{t}^{2})]$
$\geq$
$\sum\limits_{t=1}^{T}\mathbb{E}[-2\theta_{t}\epsilon_{t}+\frac{3}{4}\epsilon_{t}^{2}]$
$=$ $3\sigma^{2}T$. This implies that $\mathcal{R}_{d}\geq 3\sigma^{2}T$. For
the path length, $\sum\limits_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq 2\sigma T$. Let
us set $\sigma=T^{-\frac{2(1-\gamma_{0})}{4-\gamma_{0}}}$ and
$\gamma_{0}\in(0,1)$. Then $V=2\sigma
T=2T^{\frac{2+\gamma_{0}}{4-\gamma_{0}}}$ and $(VT)^{\frac{\gamma_{0}}{2}}$
$=$ $2^{\frac{\gamma_{0}}{2}}T^{\frac{3\gamma_{0}}{4-\gamma_{0}}}$. Then
$\mathcal{R}_{d}-\frac{3}{\sqrt{2}}(VT)^{\frac{\gamma_{0}}{2}}$ $\geq$
$3T^{\frac{3\gamma_{0}}{4-\gamma_{0}}}-\frac{3}{\sqrt{2}}2^{\frac{\gamma_{0}}{2}}T^{\frac{3\gamma_{0}}{4-\gamma_{0}}}$
$\geq 0$. In other words, $\mathcal{R}_{d}\geq
O\Big{(}(VT)^{\frac{\gamma_{0}}{2}}\Big{)}$, $\forall\gamma_{0}\in(0,1)$ with
$V=2T^{\frac{2+\gamma_{0}}{4-\gamma_{0}}}$.

In summary, we have that there always exist a exist a sequence of loss
functions $f_{1}^{T}$ and a comparison sequence $z_{1}^{T}$ such that
$\sum\limits_{t=2}^{T}\|z_{t}-z_{t-1}\|\leq
V=O(T^{\frac{2+\gamma_{0}}{4-\gamma_{0}}})$ and
$\mathcal{R}_{d}\geq\max\\{O(\log
T),O\big{(}(VT)^{\frac{\gamma_{0}}{2}}\big{)}\\},\forall\gamma_{0}\in(0,1)$.

∎

###  13 Conclusion

In this chapter, we propose a discounted online Newton algorithm that
generalizes recursive least squares with forgetting factors and existing
online Newton methods. We prove a dynamic regret bound $\max\\{O(\log
T),O(\sqrt{TV})\\}$ which provides a rigorous analysis of forgetting factor
algorithms. In the special case of simple quadratic functions, we demonstrate
that the discounted Newton method reduces to a gradient descent algorithm with
a particular step size rule. We show how this step size rule can be
generalized to apply to strongly convex functions, giving a substantially more
computationally efficient algorithm than the discounted online Newton method,
while recovering the dynamic regret guarantees. The strongest regret
guarantees depend on knowledge of the path length, $V$. We show how to use a
meta-algorithm that optimizes over discount factors to obtain the same regret
guarantees without knowledge of $V$ as well as a lower bound which matches the
obtained upper bound for certain range of $V$. Finally, when the functions are
smooth we show how this new gradient descent method enables a static regret of
$\mathcal{R}_{s}\leq O(T^{1-\beta})$ and $\mathcal{R}_{d}^{*}\leq
O(T^{\beta}(1+V^{*}))$, where $\beta\in(0,1)$ is a user-specified trade-off
parameter.

##  Chapter 4 Online Adaptive Principal Component Analysis and Its extensions

In the previous chapter, we discussed several dynamic/static regret results
under changing environments, including the online least-squares and its
extension to the exp-concave and strongly convex problem setups. In this
chapter, we are mainly concerned with the problem of online Principal
Component Analysis (online PCA) under changing environments.

As discussed in Chapter 2, previous online PCA algorithms are based on either
online gradient or matrix exponentiated gradient descent [8, 9, 10, 11]. These
works bound online PCA by the static regret, which, as argued in previous
chapters, is not appropriate for changing environments. To have better
adaptivity to the changing environments, previous works proposed to run a pool
of algorithms with either different parameters like in [22, 38] (for upper
bounding dynamic regret) or different starting points like in [19] (for upper
bounding adaptive regret). This not only requires complex implementation, but
also increases the computational complexity per step by a factor of $O(\log
T)$ due to the parallel running of different algorithms.

It is thus desired to have an efficient and easy-to-implement algorithm, which
can eliminate the need of running multiple algorithms while having the same
theoretical guarantee. This chapter introduces such an efficient algorithm for
the specific online PCA problem under adaptive regret measure, which is
adapted from the published work [50]. The proposed method mixes the randomized
algorithm from [10] with a fixed-share step [5]. This is inspired by the work
of [6, 7], which shows that the Hedge algorithm [34] together with a fixed-
share step provides low regret under a variety of measures, including adaptive
regret.

Furthermore, we extend the idea of the additional fixed-share step to the
online adaptive variance minimization in two different parameter spaces: the
space of unit vectors and the simplex. In Section 18, we also do the
experiments to test our algorithm’s effectiveness. In particular, we show that
our proposed algorithm can adapt to the changing environments faster than the
previous online PCA algorithm.

###  14 Problem Formulation

The goal of the PCA (uncentered) algorithm is to find a rank $k$ projection
matrix $P$ that minimizes the compression loss:
$\sum\limits_{t=1}^{T}\left\|\mathbf{x_{t}}-P\mathbf{x_{t}}\right\|^{2}$. In
this case, $P\in\mathbb{R}^{n\times n}$ must be a symmetric positive semi-
definite matrix with only $k$ non-zero eigenvalues which are all equal to 1.

In online PCA, the data points come in a stream. At each time $t$, the
algorithm first chooses a projection matrix $P_{t}$ with rank $k$, then the
data point $\mathbf{x_{t}}$ is revealed, and a compression loss of
$\left\|\mathbf{x_{t}}-P_{t}\mathbf{x_{t}}\right\|^{2}$ is incurred.

The online PCA algorithm [10] aims to minimize the static regret
$\mathcal{R}_{s}$ ,which is the difference between the total expected
compression loss and the loss of the best projection matrix $P^{*}$ chosen in
hindsight:

$\mathcal{R}_{s}=\sum\limits_{t=1}^{T}\mathbb{E}[\mathrm{Tr}((I-P_{t})\mathbf{x_{t}}\mathbf{x_{t}}^{\top})]-\sum\limits_{t=1}^{T}\mathrm{Tr}((I-P^{*})\mathbf{x_{t}}\mathbf{x_{t}}^{\top}).$
(22)

The algorithm from [10] is randomized and the expectation is taken over the
distribution of $P_{t}$ matrices. The matrix $P^{*}$ is the solution to the
following optimization problem with $\mathcal{S}$ being the set of rank-$k$
projection matrices:

$\min_{P\in\mathcal{S}}\sum\limits_{t=1}^{T}\mathrm{Tr}((I-P)\mathbf{x_{t}}\mathbf{x_{t}}^{\top})$
(23)

Algorithms that minimize static regret will converge to $P^{*}$, which is the
best projection for the entire data set. However, in many scenarios the data
generating process changes over time. In this case, a solution that adapts to
changes in the data set may be desirable. To model environmental variation,
several notions of dynamically varying regret have been proposed [5, 19, 6].
In this chapter, we study adaptive regret $\mathcal{R}_{a}$ from [19], which
results in the following online adaptive PCA problem:

$\begin{array}[]{l}\mathcal{R}_{a}=\max\limits_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}\mathbb{E}[\mathrm{Tr}((I-P_{t})\mathbf{x_{t}}\mathbf{x_{t}}^{\top})]-\min\limits_{U\in\mathcal{S}}\sum\limits_{t=r}^{s}\mathrm{Tr}((I-U)\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\Big{\\}}\end{array}$
(24)

In the next few sections, we will present an algorithm that achieves low
adaptive regret.

###  15 Learning the Adaptive Best Subset of Experts

Algorithm 3 Adaptive Best Subset of Experts

1: Input: $1\leq k<n$ and an initial probability vector
$\mathbf{w_{1}}\in\mathcal{B}_{\text{n-k}}^{\text{n}}$.

2: for $t=1$ to $T$ do

3: Use Algorithm 4 with input $d=n-k$ to decompose $\mathbf{w_{t}}$ into
$\sum_{j}p_{j}\mathbf{r_{j}}$, which is a convex combination of at most $n$
corners of $\mathbf{r_{j}}$.

4: Randomly select a corner $\mathbf{r}=\mathbf{r_{j}}$ with associated
probability $p_{j}$.

5: Use the k components with zero entries in the drawn corner $\mathbf{r}$ as
the selected subset of experts.

6: Receive loss vector $\mathbf{\ell_{t}}$.

7: Update $\mathbf{w_{t+1}}$ as:  $\displaystyle
v_{t+1,i}=\frac{w_{t,i}\exp(-\eta\ell_{t,i})}{\sum_{j=1}^{n}w_{t,j}\exp(-\eta\ell_{t,j})}$
(25a) $\displaystyle\hat{w}_{t+1,i}=\frac{\alpha}{n}+(1-\alpha)v_{t+1,i}$
(25b)
$\displaystyle\mathbf{w_{t+1}}=\text{cap}_{\text{n-k}}(\mathbf{\hat{w}_{t+1}})$
(25c) where $\text{cap}_{\text{n-k}}()$ calls Algorithm 5.

8: end for

Algorithm 4 Mixture Decomposition [10]

1: Input: $1\leq d<n$ and $\mathbf{w}\in\mathcal{B}_{\text{d}}^{\text{n}}$.

2: repeat

3: Let $\mathbf{r}$ be a corner for a subset of $d$ non-zero components of
$\mathbf{w}$ that includes all components of $\mathbf{w}$ equal to
$\frac{\left|\mathbf{w}\right|}{d}$.

4: Let $s$ be the smallest of the $d$ chosen components of $\mathbf{r}$ and
$l$ be the largest value of the remaining $n-d$ components.

5: update $\mathbf{w}$ as
$\mathbf{w}-\min(ds,\left|\mathbf{w}\right|-dl)\mathbf{r}$ and Output $p$ and
$\mathbf{r}$.

6: until $\mathbf{w}=0$

Algorithm 5 Capping Algorithm [10]

1: Input: probability vector $\mathbf{w}$ and set size $d$.

2: Let $\mathbf{w}^{\downarrow}$ index the vector in decreasing order, that
is, $\mathbf{w_{1}}^{\downarrow}=\max(\mathbf{w})$.

3: if $\max(\mathbf{w})\leq 1/d$ then

4: return $\mathbf{w}$.

5: end if

6: $i=1$.

7: repeat

8: (* Set first $i$ largest components to $1/d$ and normalize the rest to
$(d-i)/d$ *)

9: $\mathbf{\tilde{w}}=\mathbf{w}$, $\tilde{w}_{j}^{\downarrow}=1/d$, for
$j=1,\dots,i$.

10:
$\tilde{w}_{j}^{\downarrow}=\frac{d-i}{d}\frac{\tilde{w}_{j}^{\downarrow}}{\sum_{l=j}^{n}\tilde{w}_{l}^{\downarrow}}$,
for $j=i+1,\dots,n$.

11: $i=i+1$.

12: until $\max(\mathbf{\tilde{w}})\leq 1/d$.

In [10], it was shown that online PCA can be viewed as an extension of a
simpler problem known as the _best subset of experts_ problem. In particular,
they first propose an online algorithm to solve the best subset of experts
problem, and then they show how to modify the algorithm to solve PCA problems.
In this section, we show how the addition of a fixed-share step [5, 6] can
lead to an algorithm for an adaptive variant of the best subset of experts
problem. Then we will show how to extend the resulting algorithm to PCA
problems.

The _adaptive best subset of experts_ problem can be described as follows: we
have $n$ experts making decisions at each time $t$. Before revealing the loss
vector $\mathbf{\ell_{t}}\in\mathbb{R}^{n}$ associated with the experts’
decisions at time $t$, we select a subset of experts of size $n-k$
(represented by vector $\mathbf{v_{t}}$) to try to minimize the adaptive
regret defined as:

$\mathcal{R}_{a}^{\text{subexp}}=\max_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}\mathbb{E}[\mathbf{v_{t}}^{\top}\mathbf{\ell_{t}}]-\min_{\mathbf{u}\in\mathcal{S}_{\text{vec}}}\sum\limits_{t=r}^{s}\mathbf{u}^{\top}\mathbf{\ell_{t}}\Big{\\}}.$
(26)

Here, the expectation is taken over the probability distribution of
$\mathbf{v_{t}}$. Both $\mathbf{v_{t}}$ and $\mathbf{u}$ are in
$\mathcal{S}_{\text{vec}}$ which denotes the vector set with only $n-k$ non-
zero elements equal to 1.

Similar to the static regret case from [10], the problem in Eq.(26) is
equivalent to:

$\mathcal{R}_{a}^{\text{subexp}}=\max_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}(n-k)\mathbf{w_{t}}^{\top}\mathbf{\ell_{t}}-\min_{\mathbf{q}\in\mathcal{B}_{\text{n-k}}^{\text{n}}}\sum\limits_{t=r}^{s}(n-k)\mathbf{q}^{\top}\mathbf{\ell_{t}}\Big{\\}}$
(27)

where $\mathbf{w_{t}}\in\mathcal{B}_{\text{n-k}}^{\text{n}}$, and
$\mathcal{B}_{\text{n-k}}^{\text{n}}$ represents the capped probability
simplex defined as $\sum_{i=1}^{n}w_{t,i}=1$ and $0\leq w_{t,i}\leq 1/(n-k)$,
$\forall i$.

Such equivalence is due to the Theorem 2 in [10] ensuring that any vector
$\mathbf{q}\in\mathcal{B}_{\text{n-k}}^{\text{n}}$ can be decomposed as convex
combination of at most $n$ corners of $\mathbf{r_{j}}$ by using Algorithm 4,
where the corner $\mathbf{r_{j}}$ is defined as having $n-k$ non-zero elements
equal to $1/(n-k)$. As a result, the corner can be sampled by the associated
probability obtained from the convex combination, which is a valid subset
selection vector $\mathbf{v_{t}}$ with the multiplication of $n-k$.

Connection to the online adaptive PCA. The problem from Eq.(26) can be viewed
as restricted version of the online adaptive PCA problem from Eq.(24). In
particular, say that $I-P_{t}=\mathrm{diag}(\mathbf{v_{t}})$. This corresponds
to restricting $P_{t}$ to be diagonal. If $\mathbf{\ell_{t}}$ is the diagonal
of $\mathbf{x_{t}}\mathbf{x_{t}}^{\top}$, then the objectives of Eq.(26) and
Eq.(24) are equal.

We now return to the adaptive best subset of experts problem. When $r=1$ and
$s=T$, the problem reduces to the standard static regret minimization problem,
which is studied in [10]. Their solution applies the basic Hedge Algorithm to
obtain a probability distribution for the experts, and modifies the
distribution to select a subset of the experts.

To deal with the adaptive regret considered in Eq.(27), we propose the
Algorithm 3, which is a simple modification to Algorithm 1 in [10]. More
specifically, we add Eq.(25b) when updating $\mathbf{w_{t+1}}$ in Step $7$,
which is called a _fixed-share_ step. This is inspired by the analysis in [6],
which shows that the online adaptive best expert problem can be solved by
simply adding this fixed-share step to the standard Hedge algorithm.

With the Algorithm 3, the following lemma can be obtained:

######  Lemma 4.1.

For all $t\geq 1$, all $\mathbf{\ell_{t}}\in[0,1]^{n}$, and for all
$\mathbf{q_{t}}\in\mathcal{B}_{\text{n-k}}^{\text{n}}$, Algorithm 3 satisfies

$\mathbf{w_{t}}^{\top}\mathbf{\ell_{t}}(1-\exp(-\eta))-\eta\mathbf{q_{t}}^{\top}\mathbf{\ell_{t}}\leq\sum_{i=1}^{n}q_{t,i}\ln(\frac{v_{t+1,i}}{\hat{w}_{t,i}})$

###### Proof.

With the update in Eq.(25), for any
$\mathbf{q_{t}}\in\mathcal{B}_{\text{n-k}}^{\text{n}}$, we have

$d(\mathbf{q_{t}},\mathbf{w_{t}})-d(\mathbf{q_{t}},\mathbf{v_{t+1}})=-\eta\mathbf{q_{t}}^{\top}\mathbf{\ell_{t}}-\ln(\sum_{j=1}^{n}w_{t,j}\exp(-\eta\ell_{t,j}))$

Also,
$-\ln(\sum_{j=1}^{n}w_{t,j}\exp(-\eta\ell_{t,j}))\geq\mathbf{w_{t}}^{\top}\mathbf{\ell_{t}}(1-\exp(-\eta))$
based on the proof of Theorem 1 in [10]. Thus, we get

$d(\mathbf{q_{t}},\mathbf{w_{t}})-d(\mathbf{q_{t}},\mathbf{v_{t+1}})\geq-\eta\mathbf{q_{t}}^{\top}\mathbf{\ell_{t}}+\mathbf{w_{t}}^{\top}\mathbf{\ell_{t}}(1-\exp(-\eta))$
(28)

Moreover, Eq.(25c) is the solution to the following projection problem as
shown in [10]:

$\mathbf{w_{t}}=\operatornamewithlimits{argmin}\limits_{\mathbf{w}\in\mathcal{B}_{\text{n-k}}^{\text{n}}}d(\mathbf{w},\mathbf{\hat{w}_{t}})$

Since the relative entropy is one kind of Bregman divergence [51, 52], the
Generalized Pythagorean Theorem holds [53]:

$d(\mathbf{q_{t}},\mathbf{\hat{w}_{t}})-d(\mathbf{q_{t}},\mathbf{w_{t}})\geq
d(\mathbf{w_{t}},\mathbf{\hat{w}_{t}})\geq 0$ (29)

where the last inequality is due to the non-negativity of Bregman divergence.

Combining Eq.(28) with Eq.(29) and expanding the left part of
$d(\mathbf{q_{t}},\mathbf{\hat{w}_{t}})-d(\mathbf{q_{t}},\mathbf{v_{t+1}})$,
we arrive at Lemma 4.1. ∎

Now we are ready to state the following theorem to upper bound the adaptive
regret $\mathcal{R}_{a}^{\text{subexp}}$:

######  Theorem 4.1.

If we run the Algorithm 3 to select a subset of $n-k$ experts, then for any
sequence of loss vectors $\mathbf{\ell_{1}}$, $\dots$, $\mathbf{\ell_{T}}$
$\in$ $[0,1]^{n}$ with $T\geq 1$,
$\min_{\mathbf{q}\in\mathcal{B}_{\text{n-k}}^{\text{n}}}\sum\limits_{t=r}^{s}(n-k)\mathbf{q}^{\top}\mathbf{\ell_{t}}\leq
L$, $\alpha=1/(T(n-k)+1)$, $D=(n-k)\ln(n(1+(n-k)T))+1$, and
$\eta=\ln(1+\sqrt{2D/L})$, we have

$\mathcal{R}_{a}^{\text{subexp}}\leq O(\sqrt{2LD}+D)$

###### Proof sktech.

After showing the inequality from Lemma 4.1, the main work that remains is to
sum the right side from $t=1$ to $T$ and provide an upper bound. This is
achieved by following the proof of the Proposition 2 in [6]. The main idea is
to expand the term $\sum_{i=1}^{n}q_{t,i}\ln(\frac{v_{t+1,i}}{\hat{w}_{t,i}})$
as follows:

$\begin{array}[]{ll}\sum_{i=1}^{n}q_{t,i}\ln(\frac{v_{t+1,i}}{\hat{w}_{t,i}})=\underbrace{\sum_{i=1}^{n}\Big{(}q_{t,i}\ln\frac{1}{\hat{w}_{t,i}}-q_{t-1,i}\ln\frac{1}{v_{t,i}}\Big{)}}_{A}+\underbrace{\sum_{i=1}^{n}\Big{(}q_{t-1,i}\ln\frac{1}{v_{t,i}}-q_{t,i}\ln\frac{1}{v_{t+1,i}}\Big{)}}_{B}\end{array}$

Then we can upper bound the expression of $A$ with the _fixed-share_ step,
since $\hat{w}_{t,i}$ is lower bounded by $\frac{\alpha}{n}$. We can telescope
the expression of $B$. Then our desired upper bound can be obtained with the
help of Lemma 4 from [34]. ∎

Please refer to the Appendix for all the omitted/sketched proofs in this
chapter.

###  16 Online Adaptive PCA

Recall that the online adaptive PCA problem is below:

$\begin{array}[]{l}\mathcal{R}_{a}=\max\limits_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}\mathbb{E}[\mathrm{Tr}((I-P_{t})\mathbf{x_{t}}\mathbf{x_{t}}^{\top})]-\min\limits_{U\in\mathcal{S}}\sum\limits_{t=r}^{s}\mathrm{Tr}((I-U)\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\Big{\\}}\end{array}$
(30)

where $\mathcal{S}$ is the rank $k$ projection matrix set.

Again, inspired by [10], we first reformulate the above problem into the
following ’capped probability simplex’ form:

$\begin{array}[]{ll}\mathcal{R}_{a}=\max\limits_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}(n-k)\mathrm{Tr}(W_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})-\min\limits_{Q\in\mathscr{B}_{\text{n-k}}^{\text{n}}}\sum\limits_{t=r}^{s}(n-k)\mathrm{Tr}(Q\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\Big{\\}}\end{array}$
(31)

where $W_{t}\in\mathscr{B}_{\text{n-k}}^{\text{n}}$, and
$\mathscr{B}_{\text{n-k}}^{\text{n}}$ is the set of all density matrices with
eigenvalues bounded by $1/(n-k)$. Note that
$\mathscr{B}_{\text{n-k}}^{\text{n}}$ can be expressed as the convex set
$\\{W:W\succeq 0,\left\|W\right\|_{2}\leq 1/(n-k),\mathrm{Tr}(W)=1\\}$.

Algorithm 6 Uncentered online adaptive PCA

1: Input: $1\leq k<n$ and an initial density matrix
$W_{1}\in\mathscr{B}_{n-k}^{n}$.

2: for $t=1$ to $T$ do

3: Apply eigendecomposition to $W_{t}$ as
$W_{t}=\bar{D}\operatornamewithlimits{diag}(\mathbf{w_{t}})\bar{D}^{\top}$.

4: Apply Algorithm 4 with $d=n-k$ to the vector $\mathbf{w_{t}}$ to decompose
it into a convex combination $\sum_{j}p_{j}\mathbf{r_{j}}$ of at most $n$
corners $\mathbf{r_{j}}$.

5: Randomly select a corner $\mathbf{r}=\mathbf{r_{j}}$ with the associated
probability $p_{j}$.

6: Form a density matrix
$R=(n-k)\bar{D}\operatornamewithlimits{diag}(\mathbf{r})\bar{D}^{\top}$

7: Form a rank $k$ projection matrix $P_{t}=I-R$

8: Obtain the data point $\mathbf{x_{t}}$, which incurs the compression loss
$\left\|\mathbf{x_{t}}-P_{t}\mathbf{x_{t}}\right\|^{2}$ and expected
compression loss $(n-k)\mathrm{Tr}(W_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})$.

9: Update $W_{t+1}$ as:  $\displaystyle V_{t+1}=\frac{\exp(\ln
W_{t}-\eta\mathbf{x_{t}}\mathbf{x_{t}}^{\top})}{\mathrm{Tr}(\exp(\ln
W_{t}-\eta\mathbf{x_{t}}\mathbf{x_{t}}^{\top}))}$ (32a)
$\displaystyle\hat{w}_{t+1,i}=\frac{\alpha}{n}+(1-\alpha)v_{t+1,i},\widehat{W}_{t+1}=U\operatornamewithlimits{diag}(\mathbf{\hat{w}_{t+1}})U^{\top}$
(32b) $\displaystyle W_{t+1}=\text{cap}_{n-k}(\widehat{W}_{t+1})$ (32c) where
we apply eigendecomposition to $V_{t+1}$ as
$V_{t+1}=U\operatornamewithlimits{diag}(\mathbf{v_{t+1}})U^{\top}$, and
$\text{cap}_{n-k}(W)$ invokes Algorithm 5 with input being the eigenvalues of
$W$.

10: end for

The static regret online PCA is a special case of the above problem with $r=1$
and $s=T$, and is solved by Algorithm 5 in [10].

Follow the idea in the last section, we propose the Algorithm 6. Compared with
the Algorithm 5 in [10], we have added the fixed-share step in the update of
$W_{t+1}$ at step $9$, which will be shown to be the key in upper bounding the
adaptive regret of the online PCA.

In order to analyze Algorithm 6, we need a few supporting results. The first
result comes from [9]:

######  Theorem 4.2.

[9] For any sequence of data points $\mathbf{x_{1}}$, $\dots$,
$\mathbf{x_{T}}$ with $\mathbf{x_{t}}\mathbf{x_{t}}^{\top}\preceq I$ and for
any learning rate $\eta$, the following bound holds for any matrix
$Q_{t}\in\mathscr{B}_{\text{n-k}}^{\text{n}}$ with the update in Eq.(32a):

$\mathrm{Tr}(W_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\leq\frac{\Delta(Q_{t},W_{t})-\Delta(Q_{t},V_{t+1})+\eta\mathrm{Tr}(Q_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})}{1-\exp(-\eta)}$

Based on the above theorem’s result, we have the following lemma:

######  Lemma 4.2.

For all $t\geq 1$, all $\mathbf{x_{t}}$ with
$\left\|\mathbf{x_{t}}\right\|\leq 1$, and for all
$Q_{t}\in\mathscr{B}_{n-k}^{n}$, Algorithm 6 satisfies:

$\begin{array}[]{l}\mathrm{Tr}(W_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})(1-\exp(-\eta))-\eta\mathrm{Tr}(Q_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\leq-\mathrm{Tr}(Q_{t}\ln\widehat{W}_{t})+\mathrm{Tr}(Q_{t}\ln
V_{t+1})\end{array}$

###### Proof.

First, we need to reformulate the above inequality in Theorem 4.2, we have:

$\begin{array}[]{l}\Delta(Q_{t},W_{t})-\Delta(Q_{t},V_{t+1})\geq-\eta\mathrm{Tr}(Q_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})+\mathrm{Tr}(W_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})(1-\exp(-\eta))\end{array}$
(33)

which is very similar to the Eq.(28).

As is shown in [10], the Eq.(32c) is the solution to the following
optimization problem:

$W_{t}=\operatornamewithlimits{argmin}\limits_{W\in\mathscr{B}_{\text{n-k}}^{\text{n}}}\Delta(W,\widehat{W}_{t})$

As a result, the Generalized Pythagorean Theorem holds [53] for any
$Q_{t}\in\mathscr{B}_{\text{n-k}}^{\text{n}}$:

$\Delta(Q_{t},\widehat{W}_{t})-\Delta(Q_{t},W_{t})\geq\Delta(W_{t},\widehat{W}_{t})\geq
0$

Combining the above inequality with Eq.(33) and expanding the left part, we
have

$\begin{array}[]{l}\mathrm{Tr}(W_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})(1-\exp(-\eta))-\eta\mathrm{Tr}(Q_{t}\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\leq-\mathrm{Tr}(Q_{t}\ln\widehat{W}_{t})+\mathrm{Tr}(Q_{t}\ln
V_{t+1})\end{array}$

which proves the result. ∎

In the next theorem, we show that with the addition of the fixed-share step in
Eq.(32b), we can solve the online adaptive PCA problem in Eq.(30).

######  Theorem 4.3.

For any sequence of data points $\mathbf{x_{1}}$, $\dots$, $\mathbf{x_{T}}$
with $\left\|\mathbf{x_{t}}\right\|\leq 1$, and
$\min\limits_{Q\in\mathscr{B}_{\text{n-k}}^{\text{n}}}\sum\limits_{t=r}^{s}(n-k)\mathrm{Tr}(Q\mathbf{x_{t}}\mathbf{x_{t}}^{\top})\leq
L$, if we run Algorithm 6 with $\alpha=1/(T(n-k)+1)$,
$D=(n-k)\ln(n(1+(n-k)T))+1$, and $\eta=\ln(1+\sqrt{2D/L})$, for any $T\geq 1$
we have:

$\mathcal{R}_{a}\leq O(\sqrt{2LD}+D)$

###### Proof sktech.

The proof idea is the same as in the proof of Theorem 4.1. After getting the
inequality relationship in Lemma 4.2 which has a similar form as in Lemma 4.1,
we need to upper bound sum over $t$ of the right side. To achieve this, we
first reformulate it as two parts below:

$\begin{array}[]{l}-\mathrm{Tr}(Q_{t}\ln\widehat{W}_{t})+\mathrm{Tr}(Q_{t}\ln
V_{t+1})=\bar{A}+\bar{B}\end{array}$ (34)

where $\bar{A}=-\mathrm{Tr}(Q_{t}\ln\widehat{W}_{t})+\mathrm{Tr}(Q_{t-1}\ln
V_{t})$, and $\bar{B}=-\mathrm{Tr}(Q_{t-1}\ln V_{t})+\mathrm{Tr}(Q_{t}\ln
V_{t+1})$.

The first part can be upper bounded with the help of the fixed-share step in
lower bounding the singular value of $\hat{w}_{t,i}$. After telescoping the
second part, we can get the desired upper bound with the help of Lemma 4 from
[34]. ∎

###  17 Extension to Online Adaptive Variance Minimization

In this section, we study the closely related problem of online adaptive
variance minimization. The problem is defined as follows: At each time $t$, we
first select a vector $\mathbf{y_{t}}\in\Omega$, and then a covariance matrix
$C_{t}\in\mathbb{R}^{n\times n}$ such that $0\preceq C_{t}\preceq I$ is
revealed. The goal is to minimize the adaptive regret defined as:

$\mathcal{R}_{a}^{\text{var}}=\max_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}\mathbb{E}[\mathbf{y_{t}}^{\top}C_{t}\mathbf{y_{t}}]-\min_{\mathbf{u}\in\Omega}\sum\limits_{t=r}^{s}\mathbf{u}^{\top}C_{t}\mathbf{u}\Big{\\}}$
(35)

where the expectation is taken over the probability distribution of
$\mathbf{y_{t}}$.

This problem has two different situations corresponding to different parameter
space $\Omega$ of $\mathbf{y_{t}}$ and $\mathbf{u}$.

Situation 1: When $\Omega$ is the set of
$\\{\mathbf{x}|\left\|\mathbf{x}\right\|=1\\}$ (e.g., the unit vector space),
the solution to
$\min_{\mathbf{u}\in\Omega}\sum_{t=r}^{s}\mathbf{u}^{\top}C_{t}\mathbf{u}$ is
the minimum eigenvector of the matrix $\sum_{t=r}^{s}C_{t}$.

Situation 2: When $\Omega$ is the probability simplex (e.g., $\Omega$ is equal
to $\mathcal{B}_{\text{1}}^{\text{n}}$), it corresponds to the risk
minimization in stock portfolios [54].

We will start with Situation 1 since it is highly related to the previous
section.

####  17.1 Online Adaptive Variance Minimization over the Unit vector space

We begin with the observation of the following equivalence [9]:

$\min_{\left\|\mathbf{u}\right\|=1}\mathbf{u}^{\top}C\mathbf{u}=\min_{U\in\mathscr{B}_{\text{1}}^{\text{n}}}\mathrm{Tr}(UC)$

where $C$ is any covariance matrix, and $\mathscr{B}_{\text{1}}^{\text{n}}$ is
the set of all density matrices.

Thus, the problem in (35) can be reformulated as:

$\mathcal{R}_{a}^{\text{var-
unit}}=\max_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}\mathrm{Tr}(Y_{t}C_{t})-\min_{U\in\mathscr{B}_{\text{1}}^{\text{n}}}\sum\limits_{t=r}^{s}\mathrm{Tr}(UC_{t})\Big{\\}}$
(36)

where $Y_{t}\in\mathscr{B}_{\text{1}}^{\text{n}}$.

To see the equivalence between
$\mathbb{E}[\mathbf{y_{t}}^{\top}C_{t}\mathbf{y_{t}}]$ in Eq.(35) and
$\mathrm{Tr}(Y_{t}C_{t})$, we do the eigendecomposition of
$Y_{t}=\sum_{i=1}^{n}\sigma_{i}\mathbf{y_{i}}\mathbf{y_{i}}^{\top}$. Then
$\mathrm{Tr}(Y_{t}C_{t})$ is equal to
$\sum_{i=1}^{n}\sigma_{i}\mathrm{Tr}(\mathbf{y_{i}}\mathbf{y_{i}}^{\top}C_{t})$
$=$ $\sum_{i=1}^{n}\sigma_{i}\mathbf{y_{i}}^{\top}C_{t}\mathbf{y_{i}}$. Since
$Y_{t}\in\mathscr{B}_{\text{1}}^{\text{n}}$, the vector $\mathbf{\sigma}$ is a
simplex vector, and
$\sum_{i=1}^{n}\sigma_{i}\mathbf{y_{i}}^{\top}C_{t}\mathbf{y_{i}}$ is equal to
$\mathbb{E}[\mathbf{y_{i}}^{\top}C_{t}\mathbf{y_{i}}]$ with probability
distribution defined by the vector $\mathbf{\sigma}$.

If we examine Eq.(36) and (31) together, we will see that they share some
similarities: First, they are almost the same if we set $n-k=1$ in Eq.(31).
Also, $\mathbf{x_{t}}\mathbf{x_{t}}^{\top}$ in Eq.(31) is a special case of
$C_{t}$ in Eq.(36).

Thus, it is possible to apply Algorithm 6 to solving the problem (36) by
setting $n-k=1$. In this case, Algorithms 4 and 5 are not needed. This is
summarized in Algorithm 7.

Algorithm 7 Online adaptive variance minimization over unit sphere

1: Input: an initial density matrix $Y_{1}\in\mathscr{B}_{1}^{n}$.

2: for $t=1$ to $T$ do

3: Perform eigendecomposition
$Y_{t}=\widehat{D}\operatornamewithlimits{diag}(\sigma_{t})\widehat{D}^{\top}$.

4: Use the vector $\mathbf{y_{t}}=\widehat{D}[:,j]$ with probability
$\sigma_{t,j}$.

5: Receive covariance matrix $C_{t}$, which incurs the loss
$\mathbf{y_{t}}^{\top}C_{t}\mathbf{y_{t}}$ and expected loss
$\mathrm{Tr}(Y_{t}C_{t})$.

6: Update $Y_{t+1}$ as:  $\displaystyle V_{t+1}=\frac{\exp(\ln Y_{t}-\eta
C_{t})}{\mathrm{Tr}(\exp(\ln Y_{t}-\eta C_{t}))}$ (37a)
$\displaystyle\sigma_{t+1,i}=\frac{\alpha}{n}+(1-\alpha)v_{t+1,i},Y_{t+1}=\widehat{U}\operatornamewithlimits{diag}(\sigma_{t+1})\widehat{U}^{\top}$
(37b) where we apply eigendecomposition to $V_{t+1}$ as
$V_{t+1}=\widehat{U}\operatornamewithlimits{diag}(\mathbf{v_{t+1}})\widehat{U}^{\top}$.

7: end for

The theorem below is analogous to Theorem 4.3 in the case that $n-k=1$.

######  Theorem 4.4.

For any sequence of covariance matrices $C_{1}$, $\dots$, $C_{T}$ with
$0\preceq C_{t}\preceq I$, and for
$\min\limits_{U\in\mathscr{B}_{\text{1}}^{\text{n}}}\sum\limits_{t=r}^{s}\mathrm{Tr}(UC_{t})\leq
L$, if we run Algorithm 7 with $\alpha=1/(T+1)$, $D=\ln(n(1+T))+1$, and
$\eta=\ln(1+\sqrt{2D/L})$, for any $T\geq 1$ we have:

$\mathcal{R}_{a}^{\text{var-unit}}\leq O(\sqrt{2LD}+D)$

###### Proof sktech.

Similar inequality can be obtained as in Lemma 4.2 by using the Theorem 2 in
[9]. The rest follows the proof of Theorem 4.3. ∎

In order to apply the above theorem, we need to either estimate the step size
$\eta$ heuristically or estimate the upper bound $L$, which may not be easily
done.

In the next theorem, we show that we can still upper bound the
$\mathcal{R}_{a}^{\text{var-unit}}$ without knowing $L$, but the upper bound
is a function of time horizon $T$ instead of the upper bound $L$.

Before we get to the theorem, we need the following lemma which lifts the
vector case of Lemma 1 in [6] to the density matrix case:

######  Lemma 4.3.

For any $\eta\geq 0$, $t\geq 1$, any covariance matrix $C_{t}$ with $0\preceq
C_{t}\preceq I$, and for any $Q_{t}\in\mathscr{B}_{1}^{n}$, Algorithm 7
satisfies:

$\begin{array}[]{l}\mathrm{Tr}(Y_{t}C_{t})-\mathrm{Tr}(Q_{t}C_{t})\leq\frac{1}{\eta}\Big{(}\mathrm{Tr}(Q_{t}\ln
V_{t+1})-\mathrm{Tr}(Q_{t}\ln Y_{t})\Big{)}+\frac{\eta}{2}\end{array}$

Now we are ready to present the upper bound on the regret for Algorithm 7.

######  Theorem 4.5.

For any sequence of covariance matrices $C_{1}$, $\dots$, $C_{T}$ with
$0\preceq C_{t}\preceq I$, if we run Algorithm 7 with $\alpha=1/(T+1)$ and
$\eta=\frac{\sqrt{\ln(n(1+T))}}{\sqrt{T}}$, for any $T\geq 1$ we have:

$\mathcal{R}_{a}^{\text{var-unit}}\leq
O\Big{(}\sqrt{T\ln\big{(}n(1+T)\big{)}}\Big{)}$

###### Proof.

In the proof, we will use two cases of $Q_{t}$: $Q_{t}\in\mathscr{B}_{1}^{n}$,
and $Q_{t}=0$.

From Lemma 4.3, the following inequality is valid for both cases of $Q_{t}$:

$\begin{array}[]{l}\mathrm{Tr}(Y_{t}C_{t})-\mathrm{Tr}(Q_{t}C_{t})\leq\frac{1}{\eta}\Big{(}\mathrm{Tr}(Q_{t}\ln
V_{t+1})-\mathrm{Tr}(Q_{t}\ln Y_{t})\Big{)}+\frac{\eta}{2}\end{array}$

Follow the same analysis as in the proof of Theorem 4.3, we first do the
eigendecomposition to $Q_{t}$ as
$Q_{t}=\widetilde{D}\operatornamewithlimits{diag}(q_{t})\widetilde{D}^{\top}$.
Since $\left\|q_{t}\right\|_{1}$ is either $1$ or $0$, we will re-write the
above inequality as:

$\begin{array}[]{l}\left\|q_{t}\right\|_{1}\mathrm{Tr}(Y_{t}C_{t})-\mathrm{Tr}(Q_{t}C_{t})\leq\frac{1}{\eta}\Big{(}\mathrm{Tr}(Q_{t}\ln
V_{t+1})-\mathrm{Tr}(Q_{t}\ln
Y_{t})\Big{)}+\frac{\eta}{2}\left\|q_{t}\right\|_{1}\end{array}$ (38)

Analyzing the term $\mathrm{Tr}(Q_{t}\ln V_{t+1})-\mathrm{Tr}(Q_{t}\ln Y_{t})$
in the above inequality is the same as the analysis of the Eq.(34) in the
appendix.

Thus, summing over $t=1$ to $T$ to the above inequality, and setting
$Q_{t}=Q\in\mathscr{B}_{1}^{n}$ for $t=r,\dots,s$ and $0$ elsewhere, we have

$\begin{array}[]{l}\sum\limits_{t=r}^{s}\mathrm{Tr}(Y_{t}C_{t})-\min\limits_{U\in\mathscr{B}_{1}^{n}}\sum\limits_{t=r}^{s}\mathrm{Tr}(UC_{t})\leq\frac{1}{\eta}\Big{(}\ln\frac{n}{\alpha}+T\ln\frac{1}{1-\alpha}\Big{)}+\frac{\eta}{2}T,\end{array}$

since it holds for any $Q\in\mathscr{B}_{1}^{n}$.

After plugging in the expression of $\eta$ and $\alpha$, we have

$\begin{array}[]{l}\sum\limits_{t=r}^{s}\mathrm{Tr}(Y_{t}C_{t})-\min\limits_{U\in\mathscr{B}_{1}^{n}}\sum\limits_{t=r}^{s}\mathrm{Tr}(UC_{t})\leq
O\Big{(}\sqrt{T\ln\big{(}n(1+T)\big{)}}\Big{)}\end{array}$

Since the above inequality holds for any $1\leq r\leq s\leq T$, we put a
$\max\limits_{[r,s]\subset[1,T]}$ in the left part, which proves the result. ∎

####  17.2 Online Adaptive Variance Minimization over the Simplex space

We first re-write the problem in Eq.(35) when $\Omega$ is the simplex below:

$\mathcal{R}_{a}^{\text{var-
sim}}=\max_{[r,s]\subset[1,T]}\Big{\\{}\sum\limits_{t=r}^{s}\mathbb{E}[\mathbf{y_{t}}^{\top}C_{t}\mathbf{y_{t}}]-\min_{\mathbf{u}\in\mathcal{B}_{1}^{n}}\sum\limits_{t=r}^{s}\mathbf{u}^{\top}C_{t}\mathbf{u}\Big{\\}}$
(39)

where $\mathbf{y_{t}}\in\mathcal{B}_{1}^{n}$, and $\mathcal{B}_{1}^{n}$ is the
simplex set.

When $r=1$ and $s=T$, the problem reduces to the static regret problem, which
is solved in [9] by the exponentiated gradient algorithm as below:

$y_{t+1,i}=\frac{y_{t,i}\exp\big{(}-\eta(C_{t}\mathbf{y_{t}})_{i}\big{)}}{\sum_{i}y_{t,i}\exp\big{(}-\eta(C_{t}\mathbf{y_{t}})_{i}\big{)}}$

As is done in the previous sections, we add the fixed-share step after the
above update, which is summarized in Algorithm 8.

Algorithm 8 Online adaptive variance minimization over simplex

1: Input: an initial vector $\mathbf{y_{1}}\in\mathcal{B}_{1}^{n}$.

2: for $t=1$ to $T$ do

3: Receive covariance matrix $C_{t}$.

4: Incur the loss $\mathbf{y_{t}}^{\top}C_{t}\mathbf{y_{t}}$.

5: Update $\mathbf{y_{t+1}}$ as:  $\displaystyle
v_{t+1,i}=\frac{y_{t,i}\exp\big{(}-\eta(C_{t}\mathbf{y_{t}})_{i}\big{)}}{\sum_{i}y_{t,i}\exp\big{(}-\eta(C_{t}\mathbf{y_{t}})_{i}\big{)}},$
(40a) $\displaystyle y_{t+1,i}=\frac{\alpha}{n}+(1-\alpha)v_{t+1,i}.$ (40b)

6: end for

With the update of $y_{t}$ in the Algorithm 8, we have the following theorem:

######  Theorem 4.6.

For any sequence of covariance matrices $C_{1}$, $\dots$, $C_{T}$ with
$0\preceq C_{t}\preceq I$, and for
$\min\limits_{\mathbf{u}\in\mathcal{B}_{\text{1}}^{\text{n}}}\sum\limits_{t=r}^{s}\mathbf{u}^{\top}C_{t}\mathbf{u}\leq
L$, if we run Algorithm 8 with $\alpha=1/(T+1)$,
$c=\frac{\sqrt{2\ln\big{(}(1+T)n\big{)}+2}}{\sqrt{L}}$, $b=\frac{c}{2}$,
$a=\frac{b}{2b+1}$, and $\eta=2a$, for any $T\geq 1$ we have:

$\mathcal{R}_{a}^{\text{var-sim}}\leq
2\sqrt{2L\Big{(}\ln\big{(}(1+T)n\big{)}+1\Big{)}}+2\ln\big{(}(1+T)n\big{)}$

###  18 Experiments

Figure 1:  (a): The cumulative loss of the toy example with data samples
coming from three different subspaces. (b): The detailed comparison for the
two online algorithms.

In this section, we use two examples to illustrate the effectiveness of our
proposed online adaptive PCA algorithm. The first example is synthetic, which
shows that our proposed algorithm (denoted as Online Adaptive PCA) can adapt
to the changing subspace faster than the method of [10]. The second example
uses the practical dataset Yale-B to demonstrate that the proposed algorithm
can have lower cumulative loss in practice when the data/face samples are
coming from different persons.

The other algorithms that are used as comparators are: 1\. Follow the Leader
algorithm (denoted as Follow the Leader) [55], which only minimizes the loss
on the past history; 2\. The best fixed solution in hindsight (denoted as Best
fixed Projection), which is the solution to the Problem described in Eq.(23);
3\. The online static PCA (denoted as Online PCA) [10]. Other PCA algorithms
are not included, since they are not designed for regret minimization.

####  18.1 A Toy Example

Figure 2: The cumulative loss for the face example with data samples coming
from 20 different persons

In this toy example, we create the synthetic data samples coming from changing
subspace, which is a similar setup as in [10]. The data samples are divided
into three equal time intervals, and each interval has 200 data samples. The
200 data samples within same interval is randomly generated by a Gaussian
distribution with zero mean and data dimension equal to 20, and the covariance
matrix is randomly generated with rank equal to 2. In this way, the data
samples are from some unknown 2-dimensional subspace, and any data sample with
$\ell_{2}$-norm greater than 1 is normalized to 1. Since the stepsize used in
the two online algorithms is determined by the upper bound of the batch
solution, we first find the upper bound and plug into the stepsize function,
which gives $\eta=0.19$. We can tune the stepsize heuristically in practice
and in this example we just use $\eta=1$ and $\alpha=1\mathrm{e}{-5}$.

After all data samples are generated, we apply the previously mentioned
algorithms with $k=2$ and obtain the cumulative loss as a function of time
steps, which is shown in Fig.1. From this figure we can see that: 1\. Follow
the Leader algorithm is not appropriate in the setting where the sequential
data is shifting over time. 2\. The static regret is not a good metric under
this setting, since the best fixed solution in hindsight is suboptimal. 3\.
Compared with Static PCA, the proposed Adaptive PCA can adapt to the changing
environment faster, which results in lower cumulative loss and is more
appropriate when the data is shifting over time.

####  18.2 Face data Compression Example

In this example, we use the Yale-B dataset which is a collection of face
images. The data is split into 20 time intervals corresponding to 20 different
people. Within each interval, there are 64 face image samples. Like the
previous example, we first normalize the data to ensure its $\ell_{2}$-norm
not greater than 1. We use $k=2$, which is the same as the previous example.
The stepsize $\eta$ is also tuned heuristically like the previous example,
which is equal to $5$ and $\alpha=1\mathrm{e}{-4}$.

We apply the previously mentioned algorithms and again obtain the cumulative
loss as the function of time steps, which is displayed in Fig.2. From this
figure we can see that although there is no clear bumps indicating the shift
from one subspace to another as the Fig.1 of the toy example, our proposed
algorithm still has the lowest cumulative loss, which indicates that upper
bounding the adaptive regret is still effective when the compressed faces are
coming from different persons.

###  19 Conclusion

In this chapter, we propose an online adaptive PCA algorithm, which augments
the previous online static PCA algorithm with a fixed-share step. However,
different from the previous online PCA algorithm which is designed to minimize
the static regret, the proposed online adaptive PCA algorithm aims to minimize
the adaptive regret which is more appropriate when the underlying environment
is changing or the sequential data is shifting over time. We demonstrate
theoretically and experimentally that our algorithm can adapt to the changing
environments. Furthermore, we extend the online adaptive PCA algorithm to
online adaptive variance minimization problems.

One may note that the proposed algorithms suffer from the per-iteration
computation complexity of $O(n^{3})$ due to the eigendecomposition step,
although some tricks mentioned in [56] could be used to make it comparable
with incremental PCA of $O(k^{2}n)$. For the future work, one possible
direction is to investigate algorithms with slightly worse adaptive regret
bound but with better per-iteration computation complexity.

##  Chapter 5 Online Convex Optimization for Cumulative Constraints

Previous chapter focuses on how to enable the online PCA algorithm to have
better adaptivity to the changing environments.

In this chapter, we come back to the general online convex optimization (OCO)
problem. For online convex optimization with constraints, a projection
operator is typically applied in order to make the updated prediction feasible
for each time step [18, 57, 58]. However, when the constraints are complex,
the computational burden of the projection may be too high to have online
computation.

To circumvent this dilemma, [42, 43, 12] proposed algorithms which
approximates the true desired projection with a simpler closed-form
projection. The algorithm can still upper bound the static regret
$\mathcal{R}_{s}$ by $\sqrt{T}$ as the optimal result in [18], but the
constraint $\mathcal{S}=\\{\theta:g_{i}(\theta)\leq 0,i=1,\dots,m\\}$ may not
be satisfied in every time step. Instead, the long-term constraint violation
$\sum\limits_{t=1}^{T}g_{i}(\theta_{t}),\forall i$ can be upper bounded in a
sub-linear order $o(T)$, which is useful when we only require the constraint
violation to be non-positive on average:
$\lim_{T\to\infty}\sum\limits_{t=1}^{T}g_{i}(\theta_{t})/T\leq 0,\forall i$.
However, this bound does not enforce that the violation of the constraint gets
small, which is originally desired. A situation can arise in which strictly
satisfied constraints at one time step can cancel out violations of the
constraints at other time steps.

Along the line of the long-term constraint work, there are some variations,
which make the long-term constraint idea apply to the online resource
allocation. This is achieved by regarding the total resource consumption
constraint for different time steps as the long-term time-dependent
constraint.

For the online job scheduling, [12] considered the stochastic long-term
constraint case. It achieves $O(\sqrt{T})$ bound for both $\mathcal{R}_{s}$
and the expected long-term constraint
$\mathbb{E}[\sum\limits_{t=1}^{T}g_{t}(\theta_{t})]$ with Slater condition
assumption. However, such Slater condition assumes that the compared static
action needs to be strictly feasible, which means there exists at least one
point lying in the intersection of constraints
$\mathbb{E}[g_{t}(\theta)]<0,t=1,\dots,T$. This limits the claimed regret
performance due to the increasing difficulty in satisfying all the
constraints, resulting in _loose regret_.

To solve this loose regret problem, [14] came up with the idea that the fixed
comparator only needs to satisfy part of the time-dependent (possibly
adversarial) constraints. That is, it used a different fixed comparator
$\hat{\theta}=\operatornamewithlimits{argmin}_{\theta\in\Theta_{K}}\sum\limits_{t=1}^{T}f_{t}(\theta)$,
where
$\Theta_{K}=\\{\theta\in\mathcal{S}_{0}:\sum\limits_{i=t}^{t+K-1}g_{i}(\theta)\leq
0,1\leq t\leq T-K+1\\}$, $\mathcal{S}_{0}$ is the fixed convex set, and $K$ is
a user-determined parameter.

Although $\hat{\theta}\in\Theta_{K}$ can be used in the long-term budget
constraint when $g_{t}$ represents budget at each time step, it is sometimes
not a reasonable choice in that many other resource allocation problems’
constraints cannot simply be added together due to causality. For example, in
the online job scheduling, previous time step’s vacancy of the server cannot
be carried over to the next time step, while the unfinished jobs can. Or we
want to ensure that the rate of failures (the constraint violation itself) is
upper bounded.

In this chapter, we show how our proposed algorithms can be used to tackle the
two previously mentioned problems: not enforcing low constraint violation and
limited application in resource allocation.

In the first part of the chapter which is adapted from the published work
[13], we will show how the proposed algorithms can enforce low constraint
violation for the following two different problem setups:

Convex Case: The first algorithm is for the convex case, which also has the