# Local quantum uncertainty of a two-qubit XY Heisenberg model with different
Dzyaloshinskii-Moriya couplings

Younes Moqine  Research Laboratory of Physics and Engineers Sciences, Team of
Applied Physics and New Technologies, Polydisciplinary Faculty, Sultan Moulay
Slimane University, Béni Mellal, Morocco  Brahim Adnane  LPMC. Laboratory,
Theoretical Physics Group, Faculty of Sciences, Chouaïb Doukkali University,
PO Box 20, 24000 El Jadida, Morocco  Abdelhadi Belouad  LPMC. Laboratory,
Theoretical Physics Group, Faculty of Sciences, Chouaïb Doukkali University,
PO Box 20, 24000 El Jadida, Morocco  Soufiane Belhouideg  Research Laboratory
of Physics and Engineers Sciences, Team of Applied Physics and New
Technologies, Polydisciplinary Faculty, Sultan Moulay Slimane University, Béni
Mellal, Morocco  Rachid Houça<EMAIL_ADDRESS>LPMC. Laboratory, Theoretical
Physics Group, Faculty of Sciences, Chouaïb Doukkali University, PO Box 20,
24000 El Jadida, Morocco  LPTHE. Laboratory, Theoretical Physics and High
Energy, Faculty of Sciences, Ibn Zohr University, PO Box 8106, Agadir, Morocco

This study investigates the local quantum uncertainty (LQU) of a two–qubit
Heisenberg XY chain with different directions of Dzyaloshinskii–Moriya (DM)
interactions. The DM interaction parameters and coupling coefficient $J$ are
demonstrated to be beneficial in managing correlation. The DM interaction’s
x–axis parameter has more influence on correlation than the DM interaction’s
z–axis. As a result, adjusting the direction of the DM interaction may be
capable of producing a more efficient operation to improve the correlation.

PACS numbers: 03.65.Ud

Keywords: Local quantum uncertainty, partition function, density matrix,
Dzyaloshinskii-Moriya interaction.

##  1 Introduction

Entanglement is an entirely quantum correlation between the parts of a
multipartite quantum system that has no classical equivalent. It is
acknowledged as a basic physical resource that may be used in various
beneficial works in quantum information science [1, 2]. Recently, everyone
assumed that quantum correlations were intimately tied to quantum entanglement
and that manipulating quantum information was often done in the context of
entanglement and separability [1]. However, various investigations have
demonstrated that entanglement is not the only correlation suitable for
implementing quantum protocols and that certain separable states may perform
better than their classical counterparts [3, 4]. These efforts have resulted
in the invention of a new generation of quantifiers that can identify
unclassical correlations beyond entanglement [4, 5, 6, 7]. Studying
correlations in quantum systems is not confined to linking them to practical
applications. Quantum information theory techniques have also been
demonstrated to be effective in the investigation of condensed matter systems
[8].

Condensed matter systems’ quantum entanglement is a significant field, as is
well known. Various studies on quantum entanglement have been accomplished on
the thermal equilibrium states of spin chains at a fixed temperature [9, 10,
11, 12, 13]. Moreover, two-qubit quantum correlations with the DM interaction
receive much attention from researchers [14, 15, 16, 17, 18, 19]. In addition,
the Heisenberg model was used to study entanglement. A number of important
works were produced, including the isotropic Heisenberg XX model [20, 21], the
XXX model [22, 23, 24], the anisotropic Heisenberg XY model [25, 26], the
completely anisotropic Heisenberg XYZ model [27].

Local quantum uncertainty captures exclusively quantum correlations and
excludes classical correlations. This measure is of the quantum discord type,
but it has the benefit of not requiring a complex optimization technique over
measurements. This measure was first developed for bipartite quantum systems,
and there is no closed formula for $2\otimes D$ systems. A discord-like
measurement named local quantum uncertainty [30] was recently introduced. This
measurement uses skew information from a single local measurement [31, 32,
33]. For $2\otimes D$ bipartite quantum systems, the LQU measure has a closed
formula [34]. Later, other researchers attempted to study local quantum
uncertainty for the orthogonally invariant class of states [35]. This
measurement was also examined in the context of quantum phase transitions [36,
37]. It also explored the link between local quantum uncertainty and quantum
Fisher information in a non-Markovian environment [38]. Some authors have
recently examined LQU under different decoherence models and produced early
findings for three qubits [39, 40, 41, 42].

Our motivation in this work is to examine the impact of the various DM
interaction components on LQU. To this end, we will explore a two-qubit
Heisenberg XY chain with an x–axis and z–axis DM interaction in order to
investigate LQU’s thermal entanglement. Our centrosymmetric Hamiltonian matrix
of x–axis DM interaction will be transformed into the X–form via a double
Hadamard transformation to examine the effects of the two DM interactions on
the entanglement.

The structure of our article is as follows. We introduce the basics of the LQU
in section 2 and offer an analytical expression of an X–types matrix. In
Section 3, we present the two–qubit anisotropic Heisenberg XY chain
Hamiltonian with the z–axis DM interaction, evaluate the LQU of this system
and examine the effects of parameters on the entanglement in the ground state
and thermal state. Section 4 studies the two-qubit Heisenberg XY chain model
using the x–axis DM interaction. Then, in Section 5, we compared the effects
of the two DM directions on the entanglement. Finally, the discussion in
Section 6 completes the article.

##  2 LQU of a two–qubit X states

It is reasonable to think of the idea of LQU as a way to quantify non-
classical correlations in multipartite systems. This difference was put up in
an effort to measure the lowest quantum uncertainty that may be introduced
into a quantum state by measuring one local observable [47]. Considering the
density matrix

$\varrho=\left(\begin{array}[]{cccc}\rho_{11}&0&0&\rho_{14}\\\
0&\rho_{22}&\rho_{23}&0\\\ 0&\overline{\rho_{23}}&\rho_{33}&0\\\
\overline{\rho_{14}}&0&0&\rho_{44}\end{array}\right)$ (1)

For two subsystems $A$ and $B$, The LQU in relation to the $A$ is defined by

$\mathcal{U}(\rho_{AB}):=\min_{\varpi_{A}^{\mu}\otimes\operatorname{\emph{I}}_{B}}\mathcal{I}\Big{(}\rho_{AB},\varpi_{A}^{\mu}\otimes\operatorname{\emph{I}}_{B}\Big{)}.$
(2)

where $\varpi_{A}^{\mu}\otimes\operatorname{\emph{I}}_{B}$ denotes a local
observable, with $\varpi_{A}^{\mu}$ is a Hermitian operator on subsystem $A$
which is an adequate uncertainty quantifier with spectrum $\mu$ and
$\operatorname{\emph{I}}_{B}$ is the identity matrix operating on $B$. The
minimal is optimized overall local observables on $A$ with

$\mathcal{I}(\chi,\varpi_{A}^{\mu}\otimes\operatorname{\emph{I}}_{B}):=-\frac{1}{2}{\text{
Tr}}\left(\Big{[}\sqrt{\chi},\varpi_{A}^{\mu}\otimes\operatorname{\emph{I}}_{B}\Big{]}^{2}\right).$
(3)

is the Wigner-Yanase skew information [32, 31]. It measures the uncertainty of
the observable $\varpi$ for the state $\chi$. We can simply show for pure
states $(\chi^{2}=\chi)$ which the skew information reduces the usual variance
formula

$\text{Var}\left(\chi,\varpi\right)=\text{Tr}\left(\chi\varpi^{2}\right)-\Big{(}\text{Tr}\big{(}\chi\varpi\big{)}\Big{)}^{2}.$
(4)

Through the ensemble of all observables operating on the element $A$, a
minimization approach is used to accomplish the analytical calculation of the
local quantum uncertainty. A closed form for qubit–qudit systems was obtained
after optimization in [48]. The local quantum uncertainty concerning subsystem
$A$ is specifically provided for a qubit by [47]

$\mathcal{U}(\rho_{AB})=1-\lambda_{\max}\left\\{\mathcal{W}_{AB}\right\\},$
(5)

where $\lambda_{\max}$ is the greatest eigenvalue of the $3\times 3$ symmetric
matrix $\mathcal{W}_{AB}$ with

$\Big{(}\mathcal{W}_{AB}\Big{)}_{lk}\equiv{\text{
Tr}}\left\\{\sqrt{\rho_{AB}}\Big{(}\sigma_{A}^{l}\otimes{\operatorname{\emph{I}}}_{B}\Big{)}\sqrt{\rho_{AB}}\Big{(}\sigma_{A}^{k}\otimes{\operatorname{\emph{I}}}_{B}\Big{)}\right\\}$
(6)

where $\sigma_{A}^{l,k}(l,k=x,y,z)$ indicates the Pauli matrices of the
subsystem $A$. The LQU has been shown to meet all of the physical proprieties
for a quantum correlations measurement [47]. The LQU has several fascinating
features. Among them are its invariance under any local unitary operations.
Furthermore, LQU is a dependable discord-like measure with geometrical
importance in terms of Hellinger distance [31, 47].
The phase factors $e^{i\alpha_{14}}$ and $e^{i\alpha_{23}}$ may be omitted
from the off–diagonal components since the LQU is invariant under local
unitary transformations. Using the following local unitary transformations
[49, 50]

$|0\rangle_{A}=\exp\Big{(}-\frac{i}{2}\big{(}\alpha_{14}+\alpha_{23}\big{)}\Big{)}|0\rangle_{A}\
\ \ {\text{and}}\ \ \
|0\rangle_{B}=\exp\Big{(}-\frac{i}{2}\big{(}\alpha_{14}-\alpha_{23}\big{)}\Big{)}|0\rangle_{B},$

the density matrix $\varrho$ becomes

$\varrho\longrightarrow\varrho^{\prime}=\left(\begin{array}[]{cccc}\rho_{11}&0&0&|\rho_{14}|\\\
0&\rho_{22}&|\rho_{23}|&0\\\ 0&|\rho_{23}|&\rho_{33}&0\\\
|\rho_{14}|&0&0&\rho_{44}\end{array}\right).$ (7)

The Fano–Bloch decomposition of the state $\rho$ reads

$\rho={1\over
4}\sum_{\alpha,\beta}R_{\alpha,\beta}\sigma_{\alpha}\otimes\sigma_{\beta}$ (8)

where the correlation matrix $R_{\alpha,\beta}$ are given by
$R_{\alpha,\beta}={\rm
Tr}\left(\rho\sigma_{\alpha}\otimes\sigma_{\beta}\right)$, with
$\alpha,\beta=0,1,2,3$. Explicitly, they write

$\displaystyle R_{00}$ $\displaystyle=$ $\displaystyle{\rm Tr}(\rho)=1$ (9)
$\displaystyle R_{11}$ $\displaystyle=$ $\displaystyle
2\left(|\rho_{23}|+|\rho_{41}|\right)$ $\displaystyle R_{22}$ $\displaystyle=$
$\displaystyle 2\left(|\rho_{23}|-|\rho_{41}|\right)$ $\displaystyle R_{33}$
$\displaystyle=$ $\displaystyle 1-2\left(\rho_{22}+\rho_{33}\right)$
$\displaystyle R_{03}$ $\displaystyle=$ $\displaystyle
1-2\left(\rho_{22}+\rho_{44}\right)$ $\displaystyle R_{30}$ $\displaystyle=$
$\displaystyle 1-2\left(\rho_{33}+\rho_{44}\right)$

To determine the LQU defined by (5), one should compute the eigenvalues of the
matrix $\mathcal{W}_{AB}$ (6). Explicitly, they are given by [51]

$\displaystyle\omega_{1}$ $\displaystyle=$
$\displaystyle\sqrt{\left(2\sqrt{d_{1}}+t_{1}\right)\left(2\sqrt{d_{2}}+t_{2}\right)}+\frac{R_{03}^{2}+R_{11}^{2}-R_{22}^{2}-R_{30}^{2}}{4\sqrt{\left(2\sqrt{d_{1}}+t_{1}\right)\left(2\sqrt{d_{2}}+t_{2}\right)}}$
(10) $\displaystyle\omega_{2}$ $\displaystyle=$
$\displaystyle\sqrt{\left(2\sqrt{d_{1}}+t_{1}\right)\left(2\sqrt{d_{2}}+t_{2}\right)}+\frac{R_{03}^{2}-R_{11}^{2}+R_{22}^{2}-R_{30}^{2}}{4\sqrt{\left(2\sqrt{d_{1}}+t_{1}\right)\left(2\sqrt{d_{2}}+t_{2}\right)}}$
$\displaystyle\omega_{3}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(2\left(\sqrt{d_{1}}+\sqrt{d_{2}}\right)+1\right)+\frac{1}{8}\left(\frac{\left(R_{03}+R_{03}\right){}^{2}-\left(R_{22}-R_{11}\right){}^{2}}{2\sqrt{d_{1}}+t_{1}}+\frac{\left(R_{03}-R_{30}\right){}^{2}-\left(R_{11}+R_{22}\right){}^{2}}{2\sqrt{d_{2}}+t_{2}}\right)$

where

$\displaystyle t_{1}$ $\displaystyle=$ $\displaystyle\rho_{11}+\rho_{44}$ (11)
$\displaystyle t_{2}$ $\displaystyle=$ $\displaystyle\rho_{22}+\rho_{33}$
$\displaystyle d_{1}$ $\displaystyle=$
$\displaystyle\rho_{11}\rho_{44}-\rho_{14}\rho_{41}$ $\displaystyle d_{2}$
$\displaystyle=$ $\displaystyle\rho_{22}\rho_{33}-\rho_{23}\rho_{32}$

It is must be noticed that $R_{11}\geq R_{22}$. This implies that
$\omega_{1}>\omega_{2}$. As a result of the equation (5), the LQU measuring
the pairwise quantum correlation in the state $\varrho$ reads as

$\mathcal{U}(\varrho)=1-{\max}\left\\{\omega_{1},\omega_{3}\right\\}.$ (12)

Lastly, comparing the eigenvalues $\omega_{1}$ and $\omega_{3}$ is an
essential aspect of the LQU calculation technique, and the largest one must be
found.

##  3 XY Heisenberg model with z–axis DM interaction

###  3.1 Theoretical model and density matrix

The Hamiltonian $\mathcal{H}$ for a two-qubit anisotropic Heisenberg XY model
with z–axis DM interaction is written by

$\mathcal{H}=J\left(\sigma_{x}^{1}\sigma_{x}^{2}+\Delta\sigma_{y}^{1}\sigma_{y}^{2}\right)+D_{z}\left(\sigma_{x}^{1}\sigma_{y}^{2}-\sigma_{y}^{1}\sigma_{x}^{2}\right)$
(13)

where $D_{z}$ is the z–axis DM interaction, $\sigma_{i}(i=x,y,z)$ denotes the
spin–1/2 Pauli matrices, the dimensionless factor $\Delta\in[0,1]$ is the
anisotropy parameter along y–direction. It should be noted that $J$ represents
the coupling between the spin chains. For $J>0$, the chain is
antiferromagnetic, and for $J<0$, the chain is ferromagnetic. As seen below,
the Hamiltonian (13) may be represented under its matrix form in the usual
computational basis $|00>$, $|01>$, $|10>$, $|11>$ by

$\mathcal{H}=\left(\begin{array}[]{cccc}0&0&0&J(1-\Delta)\\\
0&0&J(\Delta+1)+2iD_{z}&0\\\ 0&J(\Delta+1)-2iD_{z}&0&0\\\ J(1-\Delta)&0&0&0\\\
\end{array}\right)$ (14)

The solution of the eigenvalue equation leads to the eigenvalues, which are
listed below

$\displaystyle\epsilon_{1,2}$ $\displaystyle=$ $\displaystyle\pm J(\Delta-1)$
(15) $\displaystyle\epsilon_{3,4}$ $\displaystyle=$ $\displaystyle\pm\Omega$

and the eigenvectors of the system

$\displaystyle|\varphi_{1}\rangle$ $\displaystyle=$
$\displaystyle-\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{\sqrt{2}}|11\rangle$ (16)
$\displaystyle|\varphi_{2}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{\sqrt{2}}|11\rangle$
$\displaystyle|\varphi_{3}\rangle$ $\displaystyle=$
$\displaystyle\frac{e^{i\theta}}{\sqrt{2}}|01\rangle+\frac{1}{\sqrt{2}}|10\rangle$
$\displaystyle|\varphi_{4}\rangle$ $\displaystyle=$
$\displaystyle-\frac{e^{i\theta}}{\sqrt{2}}|01\rangle+\frac{1}{\sqrt{2}}|10\rangle$

where the quantities $\Omega$ and $\theta$ are defined by

$\displaystyle\Omega$ $\displaystyle=$
$\displaystyle\sqrt{4D_{z}^{2}+(\Delta+1)^{2}J^{2}}$ (17)
$\displaystyle\theta$ $\displaystyle=$
$\displaystyle\arctan\left(\frac{2D_{z}}{J(\Delta+1)}\right)$

Prior to investigating the thermal quantum entanglements at finite
temperatures, we must first address the entanglement of the system’s ground
state at absolute zero temperature. Given that the energies rely on the
exchange coupling $J$, it is conceivable to think that ground state
entanglement arises in both antiferromagnetic and ferromagnetic cases.
In the case $J>0$, using the equation (15), we can write the ground state
energies as

$\displaystyle\epsilon_{1}$ $\displaystyle=J(\Delta-1),$
$\displaystyle\qquad\text{if}\quad J>\frac{\Omega}{(1-\Delta)},$ (18)
$\displaystyle\epsilon_{4}$ $\displaystyle=-\Omega,$
$\displaystyle\qquad\text{if}\quad J<\frac{\Omega}{(1-\Delta)}.$

Consequently, when the condition $J>\frac{\Omega}{(1-\Delta)}$ is fulfilled,
$|\varphi_{1}\rangle$ becomes the ground state which is an entangled state
but, when $J<\frac{\Omega}{(1-\Delta)}$ is verified, the ground state turns
into the ground state $|\varphi_{4}\rangle$. In addition,
$|\varphi_{1}\rangle$ and $|\varphi_{4}\rangle$ are maximally entangled
states, thus conducting to the maximum of $LQU=1$ is achieved at low
temperatures.
In the case J < 0, the ground state energies are written by

$\displaystyle\epsilon_{2}$ $\displaystyle=-J(\Delta-1),$
$\displaystyle\qquad\text{if}\quad J<-\frac{\Omega}{(1-\Delta)},$ (19)
$\displaystyle\epsilon_{4}$ $\displaystyle=-\Omega,$
$\displaystyle\qquad\text{if}\quad J>-\frac{\Omega}{(1-\Delta)}.$

where the maximally entangled states $|\varphi_{2}\rangle$ and
$|\varphi_{4}\rangle$ that corresponds to the maximum local quantum
uncertainty $LQU=1$.
After obtaining the spectrum of our system, it is easy to calculate the
thermal density, which is essential for performing measurements of the
examined system’s entanglement at temperature $T$. Indeed the expression of
the $\rho(T)$ is given by

$\rho(T)={1\over\mathbb{Z}}e^{-\beta\mathcal{H}}$ (20)

such that the canonical partition function $\mathbb{Z}$ is written by

$\mathbb{Z}={\rm Tr}e^{-\beta\mathcal{H}}$ (21)

where $k_{B}$ is the constant of the Boltzmann, for convenience, it is
considered as unity in the next. The temperature’s inverse is represented by
the parameter $\beta=1/T$. The spectrum of the Hamiltonian (14) allows
expressing the thermal density $\rho(T)$ as

$\rho(T)={1\over\mathbb{Z}}\sum_{l=1}^{4}e^{-\beta\epsilon_{l}}|\phi_{l}\rangle\langle\phi_{l}|$
(22)

By inserting (15) and (16) in the equation (22), we may derive the system’s
density matrix in the standard computational basis

$\rho(T)={1\over\mathbb{Z}}\left(\begin{array}[]{cccc}\cosh(\beta
J(\Delta-1))&0&0&\sinh(\beta J(\Delta-1))\\\
0&\cosh(\beta\Omega)&-e^{i\theta}\sinh(\beta\Omega)&0\\\
0&-e^{-i\theta}\sinh(\beta\Omega)&\cosh(\beta\Omega)&0\\\ \sinh(\beta
J(\Delta-1))&0&0&\cosh(\beta J(\Delta-1))\\\ \end{array}\right)$ (23)

whereby the partition function is defined explicitly by

$\mathbb{Z}=2\cosh(\beta\Omega)+2\cosh(\beta J(\Delta-1))$ (24)

Because $\rho(T)$ represents a thermal state, the quantum correlations it
generates are referred to as thermal quantum correlations. The following
section will quantify the quantum correlations in the aforementioned two-qubit
system as a function of the system’s characteristics, which include the x–axis
parameter $D_{x}$ and the z–axis $D_{z}$ DM interaction parameters, as well as
the temperature $T$ and coupling coefficient $J$.

###  3.2 Local quantum uncertainty

The density matrix (23) clearly has the X–type form. Consequently, the LQU may
be easily calculated using the findings mentioned earlier. To get the LQU
expression, we must determine the eigenvalues of the matrix
$\mathcal{W}_{AB}$. The non-vanishing matrix correlation components
$R_{\mu,\nu}$ that emerge during the Fano-Bloch decomposition of the density
matrix $\rho(T)$ must first be evaluated. The outcome of combining the
equations (9), (11), and the density matrix components (23) are

$\displaystyle R_{00}$ $\displaystyle=$ $\displaystyle{\rm Tr}(\rho)=1$ (25)
$\displaystyle R_{11}$ $\displaystyle=$
$\displaystyle\frac{\left|\sinh(\beta(\Delta-1)J)\right|+\sinh(\beta\Omega)}{\cosh(\beta\Omega)+\cosh(\beta(\Delta-1)J)}$
$\displaystyle R_{22}$ $\displaystyle=$
$\displaystyle\frac{\sinh(\beta\Omega)-\left|\sinh(\beta(\Delta-1)J)\right|}{\cosh(\beta\Omega)+\cosh(\beta(\Delta-1)J)}$
$\displaystyle R_{33}$ $\displaystyle=$ $\displaystyle
1-\frac{2\cosh(\beta\Omega)}{\cosh(\beta\Omega)+\cosh(\beta(\Delta-1)J)}$
$\displaystyle R_{03}$ $\displaystyle=$ $\displaystyle R_{03}=0$

and the quantities $t_{1}$ and $d_{1}$ are given by

$\displaystyle t_{1}$ $\displaystyle=$ $\displaystyle
1-t_{2}=\frac{1}{\cosh(\beta\Omega)\text{sech}(\beta(\Delta-1)J)+1}$ (26)
$\displaystyle d_{1}$ $\displaystyle=$ $\displaystyle
d_{2}=\frac{1}{4(\cosh(\beta\Omega)+\cosh(\beta(\Delta-1)J))^{2}}$

Now we have all the ingredients to obtain the eigenvalues of the matrix
$\mathcal{W}_{AB}$, just replace the different quantities in (10) and (11) by
their expressions found in (38) and (39) and therefore, the LQU may be
expressed in terms of $\omega_{1}$ and $\omega_{3}$ as follows:

$\mathcal{LQU}=1-{\max}\left\\{\omega_{1},\omega_{3}\right\\}.$ (27)

We examine the LQU of Eq. (27) in order to identify how the entanglement has
changed. After deriving the LQU equation, which depends on the temperature
$T$, the z–axis DM interaction $D_{z}$, the y–direction anisotropy parameter
$\Delta$, and the coefficient $J$. Therefore, we have all the elements needed
to examine how the recommended system behaves concerning the quantities
specified before. We may learn about the functions of other factors and the
variations in entanglement by setting the other parameters.

Figure 1: : The LQU versus logarithmic temperature. (a): for various values of
z-component parameter $D_{z}$ with $J=1$. (b): for various values of $J$ with
$D_{z}=1$ and $\Delta$ is set equal $0.5$. All the parameters are
dimensionless

In Fig. (1.a), the LQU is plotted versus logarithmic temperature $Log(T)$ for
different z–axis parameter $D_{z}$ where the coupling constants $J=1$ and
$\Delta=0.5$. The figure shows three significant remarks. In the First one, we
observe that the thermal LQU decreases when the temperature increases. In the
second one, the LQU remain equal to one at a low–temperature regime even $T$
raise. In this case, the system’s ground state is $|\varphi_{4}\rangle$ which
is the maximally entangled state. In addition, we note that the LQU decreases
rapidly for the value of $Log(T)=0.4$ (see the solid black curve).
Long–lasting entanglement in low temperatures requires large values of
z–component of DM interaction. The last one, in the high–temperature regime,
one can notice critical temperatures $T_{c}$ beyond which the LQU disappears.
The threshold temperature $T_{c}$ is influenced by the DM interaction via the
parameter $D_{z}$, such that $T_{c}$ and $D_{z}$ rise proportionally. From
Fig. (1.b), we notice that the impact of $J$ is similar to the influence of
$D_{z}$ on the LQU. For this, the remarks of a figure (1.a) remain the same.

Figure 2: : The LQU versus $D_{z}$ for various values of $T$, with $J=1$ and
$\Delta=0.5$.

In Fig. (2), we graph the LQU in terms of the z–axis $D_{z}$ for different
temperature values such as $T=1,2,3$. The first finding is that the LQU is
symmetrical for $D_{z}=0$ and goes to a fixed value $LQU=1$ for the high
absolute value of the z–axis of DM interaction even as temperature increases.
Furthermore, for $D_{z}=0$, we see that the LQU has a minimum for any
temperature value, which diminishes as the temperature decreases and vice
versa, as seen in Fig. (1). Then we may deduce that the DM interaction impacts
the correlation, i.e., the system becomes increasingly entangled due to the
high values of $|D_{z}|$.

##  4  XY HEISENBERG MODEL WITH x–axis DM INTERACTION

###  4.1 Theoretical model and density matrix

In this part, we take into consideration the same Hamiltonian as before, but
we reverse the direction of DM interaction such that

$\mathcal{H^{\prime}}=J\left(\sigma_{x}^{1}\sigma_{x}^{2}+\Delta\sigma_{y}^{1}\sigma_{y}^{2}\right)+D_{x}\left(\sigma_{y}^{1}\sigma_{z}^{2}-\sigma_{z}^{1}\sigma_{y}^{2}\right)$
(28)

where $D_{x}$ is the x–axis DM interaction, J, $\Delta$ and
$\sigma_{i}(i=x,y,z)$ are the same as those in section (3). In the usual
computational basis $|00>$, $|01>$, $|10>$, $|11>$ the Hamiltonian (28) can be
rewritten as

$\mathcal{H^{\prime}}=\left(\begin{array}[]{cccc}0&iD_{x}&-iD_{x}&J(1-\Delta)\\\
-iD_{x}&0&J(\Delta+1)&iD_{x}\\\ iD_{x}&J(\Delta+1)&0&-iD_{x}\\\
J(1-\Delta)&-iD_{x}&iD_{x}&0\\\ \end{array}\right)$ (29)

solving the eigenvalue equation of $\mathcal{H^{\prime}}$ leads to the
eigenstates

$\displaystyle|\phi_{1}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(|01\rangle+|10\rangle\right)$ (30)
$\displaystyle|\phi_{2}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{\sqrt{2}}|11\rangle$
$\displaystyle|\phi_{3}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(-\frac{1}{\sqrt{\frac{\zeta_{1}^{2}}{4}+1}}|00\rangle+\frac{i\zeta_{1}}{\sqrt{\zeta_{1}^{2}+4}}|01\rangle-\frac{i\zeta_{1}}{\sqrt{\zeta_{1}^{2}+4}}|10\rangle+\frac{1}{\sqrt{\frac{\zeta_{1}^{2}}{4}+1}}|11\rangle\right)$
$\displaystyle|\phi_{4}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(-\frac{1}{\sqrt{\frac{\zeta_{2}^{2}}{4}+1}}|00\rangle-\frac{i\zeta_{2}}{\sqrt{\zeta_{2}^{2}+4}}|01\rangle+\frac{i\zeta_{2}}{\sqrt{\zeta_{2}^{2}+4}}|10\rangle+\frac{1}{\sqrt{\frac{\zeta_{2}^{2}}{4}+1}}|11\rangle\right)$

with corresponding eigenvalues

$\displaystyle\epsilon_{1,2}^{\prime}$ $\displaystyle=$ $\displaystyle
J(1\pm\Delta)$ (31) $\displaystyle\epsilon_{3,4}^{\prime}$ $\displaystyle=$
$\displaystyle-J\pm\Omega_{1}$

where $\Omega_{1}=\sqrt{4D_{x}^{2}+\Delta^{2}J^{2}}$, and
$\zeta_{1,2}=\frac{\Omega_{1}\mp\Delta J}{D_{x}}$. The equation (31) shows
that the energies depends on the sign of $J$, then for $J<0$, the ground state
energies are given by

$\displaystyle\epsilon_{2}^{\prime}$ $\displaystyle=J(1-\Delta),$
$\displaystyle\qquad\text{if}\quad J<-\frac{\Omega_{1}}{(2-\Delta)},$ (32)
$\displaystyle\epsilon_{4}^{\prime}$ $\displaystyle=-J-\Omega_{1},$
$\displaystyle\qquad\text{if}\quad J>-\frac{\Omega_{1}}{(2-\Delta)}.$

While if $J>0$, it is given by

$\displaystyle\epsilon_{4}^{\prime}$ $\displaystyle=$
$\displaystyle-J-\Omega_{1}.$ (33)

As a result, $|\phi_{4}\rangle$ is always the ground state pertinent to the
antiferromagnetic system. It is the ground state for ferromagnetic systems as
well, but only when the condition $J>-\frac{\Omega_{1}}{(2-\Delta)}$ is
fulfilled.
Inserting the Eqs. (30) and (31) into Eq.(22) the density matrix can be
written by

$\rho^{\prime}(T)=\left(\begin{array}[]{cccc}a&\mu&\nu&b\\\ \nu&c&d&\mu\\\
\mu&d&c&\nu\\\ b&\nu&\mu&a\\\ \end{array}\right)$ (34)

such as their elements are represented by the expressions

$\displaystyle a$ $\displaystyle=$ $\displaystyle\frac{e^{\beta
J}\left(\cosh(\beta\Omega_{1})-\frac{\Delta
J\sinh(\beta\Omega_{1})}{\Omega_{1}}\right)+e^{\beta
J(\Delta-1)}}{2\mathcal{Z^{\prime}}}$ (35) $\displaystyle b$ $\displaystyle=$
$\displaystyle\frac{e^{\beta J(\Delta-1)}-e^{\beta
J}\left(\cosh(\beta\Omega_{1})-\frac{\Delta
J\sinh(\beta\Omega_{1})}{\Omega_{1}}\right)}{2\mathcal{Z^{\prime}}}$
$\displaystyle c$ $\displaystyle=$ $\displaystyle\frac{e^{\beta
J}\left(\cosh(\beta\Omega_{1})+\frac{\Delta
J\sinh(\beta\Omega_{1})}{\Omega_{1}}\right)+e^{-\beta
J(\Delta+1)}}{2\mathcal{Z^{\prime}}}$ $\displaystyle d$ $\displaystyle=$
$\displaystyle\frac{e^{-\beta J(\Delta+1)}-e^{\beta
J}\left(\cosh(\beta\Omega_{1})+\frac{\Delta
J\sinh(\beta\Omega_{1})}{\Omega_{1}}\right)}{2\mathcal{Z^{\prime}}}$
$\displaystyle\mu$ $\displaystyle=$ $\displaystyle-\frac{iD_{x}e^{\beta
J}\sinh(\beta\Omega_{1})}{\Omega_{1}\mathcal{Z^{\prime}}}$ $\displaystyle\nu$
$\displaystyle=$ $\displaystyle\frac{iD_{x}e^{\beta
J}\sinh(\beta\Omega_{1})}{\Omega_{1}\mathcal{Z^{\prime}}}$

where the partition function $\mathcal{Z^{\prime}}=2\left(e^{-\beta
J}\cosh(\beta\Delta J)+e^{\beta J}\cosh(\beta\Omega_{1})\right)$. At this
stage, the determination of LQU is complicated. For this reason, we will make
a unitary transformation of the density matrix to render the density matrix in
the X–form. To do this, we will apply a double Hadamard transformation to our
centrosymmetric density matrix by the unitary matrix

$H=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\ 1&-1\\\
\end{array}\right)$ (36)

After a straightforward calculation we obtain

$\rho^{\prime}_{H}=\frac{e^{-\beta
J}}{\mathcal{Z^{\prime}}}\left(\begin{array}[]{cccc}\cosh(\beta\Delta
J)&0&0&\sinh(\beta\Delta J)\\\ 0&e^{2\beta
J}\cosh(\beta\Omega_{1})&-\frac{e^{2\beta J}\sinh(\beta\Omega_{1})\left(\Delta
J+2iD_{x}\right)}{\Omega_{1}}&0\\\ 0&-\frac{e^{2\beta
J}\sinh(\beta\Omega_{1})\left(\Delta J-2iD_{x}\right)}{\Omega_{1}}&e^{2\beta
J}\cosh(\beta\Omega_{1})&0\\\ \sinh(\beta\Delta J)&0&0&\cosh(\beta\Delta J)\\\
\end{array}\right)$ (37)

The density matrix (37) clearly have now the X–type form, which is very easy
to calculate the LQU for the studied system.

###  4.2 Local quantum uncertainty

To get the expression of LQU, we will determine the eigenvalues of the
$\mathcal{W}_{AB}$ matrix. One must first evaluate the non–vanishing matrix
correlation components $R^{\prime}_{\mu,\nu}$ that emerge during the
Fano–Bloch decomposition of the density matrix $\rho_{H}$. When the equations
(9), (11) and the density matrix elements (23) are combined, the result is

$\displaystyle R^{\prime}_{00}$ $\displaystyle=$ $\displaystyle{\rm
Tr}(\rho)=1$ (38) $\displaystyle R^{\prime}_{11}$ $\displaystyle=$
$\displaystyle\frac{\left|\sinh(J\beta\Delta)\right|+e^{2\beta
J}\sinh(\beta\Omega_{1})}{\cosh(\beta\Delta J)+e^{2\beta
J}\cosh(\beta\Omega_{1})}$ $\displaystyle R^{\prime}_{22}$ $\displaystyle=$
$\displaystyle\frac{e^{2\beta
J}\sinh(\beta\Omega_{1})-\left|\sinh(J\beta\Delta)\right|}{\cosh(\beta\Delta
J)+e^{2\beta J}\cosh(\beta\Omega_{1})}$ $\displaystyle R^{\prime}_{33}$
$\displaystyle=$ $\displaystyle\frac{2}{e^{2\beta
J}\cosh(\beta\Omega_{1})\text{sech}(\beta\Delta J)+1}-1$ $\displaystyle
R^{\prime}_{03}$ $\displaystyle=$ $\displaystyle R^{\prime}_{30}=0$

and the quantities $t_{1}$ and $d_{1}$ are given by

$\displaystyle t^{\prime}_{1}$ $\displaystyle=$ $\displaystyle
1-t^{\prime}_{2}=\frac{1}{e^{2\beta
J}\cosh(\beta\Omega_{1})\text{sech}(\beta\Delta J)+1}$ (39) $\displaystyle
d^{\prime}_{1}$ $\displaystyle=$
$\displaystyle\frac{1}{4\left(\cosh(\beta\Delta J)+e^{2\beta
J}\cosh(\beta\Omega_{1})\right)^{2}}$ $\displaystyle d^{\prime}_{2}$
$\displaystyle=$ $\displaystyle\frac{e^{4\beta J}}{4\left(\cosh(\beta\Delta
J)+e^{2\beta J}\cosh(\beta\Omega_{1})\right)^{2}}$

then the LQU for this situation is

$\mathcal{LQU^{\prime}}=1-{\max}\left\\{\omega^{\prime}_{1},\omega^{\prime}_{3}\right\\}.$
(40)

Figure 3: : The LQU’ versus $Log(T)$. (a): for various values of x-component
parameter $D_{x}$ with $J=1$. (b): for various values of $J$ with $D_{x}=1$
and $\Delta$ is set equal $0.5$. All the parameters are dimensionless.

Fig.(3.a) shows the LQU’ versus Logarithmic temperature for different DM
coupling parameter $D_{x}$ when $J=1$ and $\Delta=0.5$. We observe that at low
temperatures and precisely in the interval $0<Log(T)<0.5$, the value of LQU’
equals one whatever the value of $D_{x}$. In this case, the ground state of
the system is $|\varphi_{4}\rangle$, which is the maximally entangled state,
then it starts decreasing for small values of $D_{x}$, and Obviously,
increasing temperature will decrease entanglement and increasing $D_{x}$ will
increase entanglement and critical temperature $T_{c}$. Figure (3.b)
demonstrates that the LQU’ with respect to $Log(T)$ for different $J$ with the
x–component parameter $D_{x}=1$ and $\Delta=0.5$, it is easy to find that
increasing $J$ can increase the critical temperature and improve entanglement
for a certain temperature. Thus, $D_{x}$ and $J$ are also effective control
parameters for entanglement.

Figure 4: : The LQU’ versus $J$ for various values of $T$ with $D_{x}=1$ and
$\Delta=0.5$.

Fig.(4) shows the changes of LQU’ in terms of interaction parameter $J$ for
various values of $T$, where the x-component parameter $D_{x}=1$ and
$\Delta=0.5$. As the value of this parameter increases, the amount of LQU’
increases and reaches to constant value one both for the systems with
ferromagnetic and anti-ferromagnetic nature. It also can be seen the LQU’ is
decreased by increasing temperature, which is confirmed by fig.(3.b).

##  5 Impact of the DM interaction directions on LQU

We know from sections 3 and 4 that the x-axis parameter $D_{x}$ and the z–axis
parameter $D_{z}$ of the DM interaction have comparable properties. They are
both efficient correlation control factors; raising them may improve
correlation or raise the critical temperature, slowing the decline of
entanglement. This section focuses on the distinctions between the x–axis and
z–axis DM interaction parameters on the LQU.

Figure 5: : The LQU is plotted as a function of the logarithmic temperature
$Log(T)$ for $D_{z}=2$ and $D_{x}=2$, here $J=1$ and $\Delta=0.5$.

We can see from graph (5) that raising the x–axis parameter $D_{x}$ causes the
correlation measured by LQU to grow more rapidly. Furthermore, when
$Log(T)=2$, the value of LQU for the $D_{x}$ parameter (blue dashed curve) is
superior to that of $D_{z}$ (black dashed curve). These phenomena indicate
that the x–axis parameter $D_{x}$ has a more significant effect than the
z-axis parameter $D_{z}$ on the quantum correlations.

##  6 Conclusion

The correlation of a two–qubit Heisenberg XY system with distinct DM
interaction parameters has been examined using local quantum uncertainty
measurement. The DM interaction and coupling parameter $J$ are excellent
correlation control basic features. We may improve the correlation by raising
the parameters. Furthermore, we studied the impact of the x–axis and z–axis DM
interaction components on the LQU. Correlation may be increased faster by
raising $D_{x}$ rather than $D_{z}$. When the values of $D_{x}$ and $D_{z}$
are the same, as a result, by modifying the direction of the DM interaction,
we may achieve a more efficient command parameter for increasing correlation.

## References

  * [1] R. Horodecki, P. Horodecki, M. Horodecki and K. Horodecki, Rev. Mod. Phys. 81 865 (2009).
  * [2] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000).
  * [3] A. Ferraro, L. Aolita, D. Cavalcanti, F. M. Cucchietti and A. Acin, Phys. Rev. A 81 052318 (2010).
  * [4] K. Modi, A. Brodutch, H. Cable, T. Paterek and V. Vedral, Rev. Mod. Phys. 84 1655 (2012).
  * [5] L. Henderson and V. Vedral, J. Phys. A : Math. Gen. 34 6899 (2001).
  * [6] H. Ollivier and W. H. Zurek, Phys. Rev. Lett. 88 017901 (2001).
  * [7] B. Dakic, V. Vedral and C. Brukner, Phys. Rev. Lett. 105 190502 (2010) .
  * [8] A. Osterloh, L. Amico, G. Falci and R. Fazio, Nature (London) 416 608 (2002).
  * [9] M. C. Amesen, S. Bose, and V. Vedral, Phys. Rev. Lett. 87 (2001) 017901
  * [10] X. G. Wang, Phys. Rev. A 64 (2001) 012313
  * [11] L. Zhou, H. S. Song, Y. Q. Guo, and C. Li, Phys. Rev. A. 68 (2003) 024301
  * [12] G. F. Zhang, and S. S. Li, Phys. Rev. A. 72 (2005) 034302
  * [13] J. L. Guo, and H. S. Song, Eur. Phys. J. D. 56 (2010) 265
  * [14] R. Houça, A. Belouad, E. B. Choubabi, A. Kamal, and M. El Bouziani, J. Magn. Magn. Mater. 563 (2022) 169816
  * [15] T. Tufarelli, D. Girolami, R. Vasile, S. Bose, and G. Adesso, Phys. Rev. A. S86 (2012) 052326
  * [16] Y. Yao, and al, Phys. Rev. A. 86 (2012) 062310
  * [17] S. Xu, X. K. Song, and L. Ye, Int. J. Mod. Phys. B. 27 (2013) 1350074
  * [18] Y. Yao, and al. Phys. Rev. A. 86 (2012) 042102
  * [19] F. W. Ma, S. X. Liu, and X. M. Kong, Phys. Rev. A. 84 (2011) 042302
  * [20] X. G. Wang, Phys. Rev. A. 64 (2001) 012313
  * [21] X. G. Wang, Phys. Rev. A. 66 (2002) 034302
  * [22] R. Houça, A. Belouad, E. B. Choubabi, A. Kamal, and M. El Bouziani, Quant. Infor. Proc. 21 (2022) 1
  * [23] M. A. Nielsen,”Quantum information theory” PhD thesis, University of New Mexico (1998). arXiv:quant-ph/0011036
  * [24] M. C. Arnesen, S.Bose, and V. Vedral, Phys. Rev. Lett. 87 (2001) 017901
  * [25] G. L. Kamta, and A F. Starace, Phys. Rev. Lett. 88 (2002) 107901
  * [26] X. G. Wang, Phys. Lett. A. 281 (2001) 101
  * [27] L. Zhou, H. S. Song, Y. Q. Guo, et al. Phys. Rev. A. 68 (2003) 024301
  * [28] K. W. William, Phys. Rev. Lett. 80 (1998) 2245
  * [29] X. Wang, H. B. Li,Z. Sun, et al, J. Phys. A. 38 (2005) 870
  * [30] D. Girolami, T. Tufarelli, G. Adesso, Phys. Rev. Lett. 110, 240402 (2013).
  * [31] S. Luo, Phys. Rev. Lett. 91, 180403 (2003).
  * [32] E.P. Wigner, M.M. Yanase, Proc. Natl. Acad. Sci. U.S.A. 49, 910 (1963).
  * [33] S. Luo, S. Fu, C.H. Oh, Phys. Rev. A 85, 032117 (2012).
  * [34] M. Ali, Eur. Phys. J. D 74 186 (2020).
  * [35] A. Sen, A. Bhar, D. Sarkar, Quan. Info. Proc. 14, 269 (2015).
  * [36] G. Karpat, B. Cakmak, F.F. Fanchini, Phys. Rev. B 90, 104431 (2014).
  * [37] I.B. Coulamy, J.H. Warnes, M.S. Sarandy, A. Saguia, Phys. Lett. A 380, 1724 (2016).
  * [38] S-X. Wu, Y. Zhang, C-S. Yu, Ann. Phys. 390, 71 (2018).
  * [39] A. Slaoui, M.I. Shaukat, M. Daoud, R. Ahl Laamara, Eur. Phys. J. Plus 133, 413 (2018).
  * [40] A. Slaoui, M. Daoud, R. Ahl Laamara, Quan. Info. Proc. 17, 178 (2018).
  * [41] A. Slaoui, L. Bakmou, M. Daoud, R. Ahl Laamara, Phys. Lett. A 383, 2241 (2019).
  * [42] A. Slaoui, M. Daoud, R. Ahl Laamara, Quan. Info. Proc. 18, 250 (2019).
  * [43] New Journal of Physics Focus Issue on Gravitational Quantum Physics (2014) http://iopscience. iop.org/1367–2630/focus/Focus
  * [44] F. Karolyhazy, Nuov. Cim. A42, 390 (1966).
  * [45] C. Anastopoulos and B. L. Hu, Class. Quantum Grav. 37, 235012 (2020).
  * [46] M. Rojas, and I. P. Lobo, ”Thermal quantum correlations in two gravitational cat states”, [arXiv:21.06.05696] (2021).
  * [47] D. Girolami, T. Tufarelli and G. Adesso, Phys. Rev. Lett. 110, 240402 (2013).
  * [48] S. Wang, H. Li, X. Lu and G-L, Long arXiv:1307.0576v2.
  * [49] Y. Khedif and M. Daoud, Int. J. Mod. Phys. B 32, 1850218 (2018).
  * [50] Y. Khedif and M. Daoud, Quantum Inf. Process. 18, 45 (2019).
  * [51] L. Jebli, B. Benzimoun and M. Daoud, Int. J. Quantum Inf. 15, 1750020 (2017).


# An Efficient Interior-Point Method for Online Convex Optimization

Elad Hazan Princeton Unviersity and Google DeepMind Nimrod Megiddo IBM Almaden
Research Center

###### Abstract

A new algorithm for regret minimization in online convex optimization is
described. The regret of the algorithm after $T$ time periods is
$O(\sqrt{T\log T})$ \- which is the minimum possible up to a logarithmic term.
In addition, the new algorithm is adaptive, in the sense that the regret
bounds hold not only for the time periods $1,\ldots,T$ but also for every sub-
interval $s,s+1,\ldots,t$. The running time of the algorithm matches that of
newly introduced interior point algorithms for regret minimization: in
$n$-dimensional space, during each iteration the new algorithm essentially
solves a system of linear equations of order $n$, rather than solving some
constrained convex optimization problem in $n$ dimensions and possibly many
constraints.

This paper is a journal submission from 2010.
Some of the referenced results have since been improved.

##  1 Introduction.

In this paper we present an interior point algorithm for the general online
learning framework of online convex optimization with computational and
prediction advantages compared to the state of the art. The setting of online
convex optimization (OCO) is a widely considered framework for online learning
capable of modeling a host of prediction problems such as portfolio selection,
online routing, prediction from expert advice and more 111we refer the reader
to the book and survey [5, 8] for more details..

In online convex optimization a decision maker makes a sequence of choices,
which are represented as points in a convex set in Euclidean space. After
revealing her decision, the adversary presents the decision maker with a cost
function that determines the cost of the decision maker in this particular
round. The goal of the decision maker is to minimize regret, or the difference
in cost between her aggregate loss and the loss of the best fixed decision in
hindsight.

The literature of online learning extensively covers polynomial-time
algorithms for OCO. Essentially all known algorithms for OCO are variants of
the online gradient descent algorithm [18] and its generalizations to mirror-
decent [4, 16, 10] with various Bregman regularizations. The structure of such
algorithms is similar: a gradient step is taken with respect to the previous
cost function followed by a projection to the convex decision set, as depicted
in figure 1.

Figure 1: Gradient-based vs. new Interior point algorithm

The computation of projections into convex sets can be carried out in
polynomial time under reasonable assumptions 222i.e. under assumption that the
underlying convex decision set is equipped with a membership oracle, see [8]
for more details.. However, in many scenarios the computation of projections
are computationally prohibitive and constitute the most time consuming
operation in OCO algorithms. In this paper we present an interior point
algorithm for online convex optimization that never leaves the underlying
convex set without sacrificing the near-optimal regret guarantees of existing
gradient-based methods.

Our interior point algorithm, depicted in Figure 1, is also an iterative
algorithm. Every iteration it moves in a direction based on the gradient of
the previous cost function. However, instead of moving exactly in the
direction of the gradient, which may take us outside of the decision set, the
new algorithm first linearly-transforms the gradient according to a self-
concordant barrier function of the decision set. The resulting direction and
new point are guaranteed to be inside the decision set. Thus, the need for
projections is completely removed, and replaced by a linear transformation
which is much more efficient to compute.

###  1.1 Formal problem statement

### Online convex optimization.

In the Online Convex Optimization problem [18], an adversary picks a sequence
of convex functions $f_{t}:\mathcal{K}\rightarrow{\mathbb{R}}$,
$t=1,2,\ldots,T$, where $\mathcal{K}\subset{\mathbb{R}}^{n}$ is convex,
compact and bounded. At stage $t$, the player has to pick an
$\mathbf{x}_{t}\in\mathcal{K}$ without knowing the function $f_{t}$. The
player then incurs a cost of $f_{t}(\mathbf{x}_{t})$. The setting in the paper
is that after choosing $\mathbf{x}_{t}$, the player is informed of the entire
function $f_{t}$ over $\mathcal{K}$. The total cost to the player is
$\sum_{t=1}^{T}f_{t}(\mathbf{x}_{t})$. Online Convex Optimization encompasses,
for example, experts algorithms [14] with arbitrary convex loss function, the
problem of universal portfolio optimization [6], online routing [3] and more.
The reader is referred to [8] for a survey of recent applications in machine
learning.

### Regret minimization.

Suppose the minimum cost over all possible single choices is attained at some
$\mathbf{x}^{*}=\mathop{\rm
argmin}_{\mathbf{x}\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(\mathbf{x})$. In this
case the regret resulting from the choices
$(\mathbf{x}_{1};f_{1},\ldots,\mathbf{x}_{T};f_{T})$ is defined as

$R(\mathbf{x}^{*})=R(\mathbf{x}_{1};f_{1},\ldots,\mathbf{x}_{T};f_{T})~{}\equiv~{}\mbox{$\sum_{t=1}^{T}$}\left[f_{t}(\mathbf{x}_{t})-f_{t}(\mathbf{x}^{*})\right]~{}.$

The problem of regret minimization calls for choosing the points
$\mathbf{x}_{1},\ldots,\mathbf{x}_{T}$ so as to minimize $R$, subject to the
condition that, when $\mathbf{x}_{t+1}$ is chosen, only
$\mathbf{x}_{1},f_{1},\ldots,\mathbf{x}_{t},f_{t}$ are known. It is known
that, in the worst case, the minimum possible regret is $\Omega(\sqrt{T})$
(see e.g. [5] or [9] footnote on page 7.).

### Computational efficiency.

Until recently, known algorithms that attain minimum possible regret require
that in each stage the algorithm solve some constrained convex optimization
problem over $\mathcal{K}$, which can be prohibitive in some practical
applications. In particular, if $\mathcal{K}$ is a convex polyhedron, the best
known worst-case bound333See, for example, [17]. on the number of iterations
of an optimization algorithm is $O(\sqrt{n}\,L)$, where $L$ is the number of
bits in the description of $\mathcal{K}$, and each iteration requires solving
a linear system of order $n$.

Recently, [2] introduce a novel interior point method which is much more
efficient. Building upon their work, we propose a new method for constructing
an almost-minimum-regret algorithm, which requires in each stage only solving
a system of linear equations of order $n$, rather than solving an optimization
problem over $\mathcal{K}$. Thus, this method improves the running time at
least by a factor $\sqrt{n}$, and much more than that when $\mathcal{K}$ is
more complicated, for example, a convex polyhedron with many facets. In
contrast to the algorithm of [2], our algorithm is provably “adaptive” in the
sense that its regret is almost the minimum possible not only over the stages
$1,\ldots,T$ but also over every sub-interval of stages $s,s+1,\ldots,t$. In
addition, it does not require an initial computation of the analytic center of
the convex set.

###  1.2 Previous Algorithms

There are numerous algorithms for Online Convex Optimization, some of which
attain the minimum possible regret of $O(\sqrt{T})$. Most of these algorithms
can be classified into the following two classes: (i) link-function
algorithms, developed in [7, 13], and (ii) regularized follow-the-leader
algorithms (see [8] for bibliography).

### Follow-The-Regularized-Leader algorithms.

The intuitive “Follow-The-Leader”
(FTL) algorithm picks for $\mathbf{x}_{t+1}$ a minimizer of the function
$F_{t}(\mathbf{x})\equiv\sum_{s=1}^{t}f_{s}(\mathbf{x})$ over $\mathcal{K}$.
It is folklore that the regret of FTL is not optimal 444This can be seen by
taking $\mathcal{K}=[-1,1]$ and $f_{t}$ to alternate between $f_{t}(x)=x$ or
$f_{t}=-x$. FTL will alternate between $-1$ and $1$, always suffering maximal
loss. In contrast - staying with either point in the long run attains half the
loss of FTL. See also [8] page 6.. This fact suggested the more general
“Follow-The-Regularized-Leader” (FTRL) algorithm that picks $\mathbf{x}_{t+1}$
as a minimizer of the function $F_{t}(\mathbf{x})+\rho(\mathbf{x})$ over
$\mathcal{K}$, where $\rho(\mathbf{x})$ is a certain function that serves as a
“regularizer”. Different variants of the method correspond to different
choices of $\rho(\mathbf{x})$. The FTRL approach led to the resolution of some
prediction problems, notably the resolution of the value of bandit information
in [2]. One advantage of the FTRL approach is its relatively intuitive
analysis due to Kalai and Vempala [12]. On the negative side, FTRL algorithms
are known to be “non-adaptive”, in the sense that the regret over a general
sub-interval $s,s+1,\ldots,t$ may be linear in $t-s$ rather than
$O(\sqrt{t-s})$ [11]. Furthermore, the running time of the algorithm in each
stage may not be practical because the algorithm has to solve some
optimization problem over $\mathcal{K}$.

### The “link function” methodology.

In contrast to the intuitive FTRL methodology, which relies on the entire past
of history of the play, link-function algorithms, as developed in [7, 13], use
less information and proceed “incrementally”. They are also known as “primal-
dual” or “online mirrored descent” algorithms, in analogy to their offline
counterparts - mirrored descent algorithms for convex optimization [1].
Perhaps the easiest algorithm to describe is Zinkevich’s [18] online gradient
descent, which picks $\mathbf{x}_{t+1}$ to be the orthogonal projection of the
point $\mathbf{y}_{t+1}\equiv\mathbf{x}_{t}-\eta\nabla f_{t}(\mathbf{x}_{t})$
into $\mathcal{K}$. Of course, $\mathbf{x}_{t+1}$ is the point in
$\mathcal{K}$ nearest $\mathbf{y}_{t+1}$, hence its computation can be costly,
for example, if $\mathcal{K}$ has many facets. On the other hand, link-
function algorithms are adaptive (in the sense explained above) and are
usually more efficiently computable than FTRL algorithms in case projections
turn out to be easy.

### Merging the two approaches.

The main idea in the new algorithm is to follow the incremental-update
approach, but make sure it never requires projections from the exterior of
$\mathcal{K}$ into $\mathcal{K}$ (hence the name “interior point”). This is
accomplished by moving from $\mathbf{x}_{t}$ to $\mathbf{x}_{t+1}$ in a
direction that is obtained from the gradient of $\nabla f_{t}(\mathbf{x}_{t})$
by a linear transformation (like in Newton’s method), which depends on
$\mathcal{K}$ and $\mathbf{x}_{t}$. The assumption is that $\mathcal{K}$ is
specified by means of a self-concordant barrier function (see below). This
idea was introduced to learning theory by Abernethy, Hazan and Rakhlin [2],
who used these barriers as regularizers. Our technique can be interpreted as
using the barrier function as a link function rather than a regularizer.

###  1.3 The new contribution compared to previous work

The contribution of this paper is the design and analysis of a new algorithm
for online convex optimization. The regret of the algorithm is almost the
minimum possible. It is adaptive and requires only solving one system of
linear equations of order $n$ per stage. In comparison to previous work, most
other minimum-regret algorithms require, in the worst case, solving a complete
optimization problem each iteration. The one exception which matches this
running time is [2, Algorithm 2]. It has minimum regret and its computation
complexity is close to that of our algorithm. However, [2, Algorithm 2] is not
adaptive. In addition, it requires computing of the so-called analytic center
of $\mathcal{K}$ for the starting point $\mathbf{x}_{1}$, which requires
solving a nontrivial optimization problem, and as originally defined works
only for linear cost functions (although this is correctable by taking the
gradient approximation of the loss functions). We prove that an efficient
interior point algorithm can be derived via the “link function” methodology
together with tools from interior point methods. Previously, such results were
proven only from the “follow the leader” methodology.

##  2 Preliminaries.

In the following we denote for two points
$\mathbf{x},\mathbf{y}\in{\mathbb{R}}^{n}$ by $[\mathbf{x},\mathbf{y}]$ the
line segment between them, or formally:

$[\mathbf{x},\mathbf{y}]=\\{\mathbf{z}\in{\mathbb{R}}^{n}\ |\
\mathbf{z}=\alpha\mathbf{x}+(1-\alpha)\mathbf{y}\ ,\ \alpha\in[0,1]\\}$

### Self-concordant barrier.

We assume that $\mathcal{K}$ is given by means of a barrier function
$\beta:\mathop{\rm int}\mathcal{K}\rightarrow{\mathbb{R}}$, i.e., for every
sequence $\\{\mathbf{x}^{k}\\}_{k=1}^{\infty}\subset\mathop{\rm
int}\mathcal{K}$ that converges to the boundary of $\mathcal{K}$, the sequence
$\\{\beta(\mathbf{x}^{k})\\}$ tends to infinity. We further assume that for
some $\vartheta>0$, $\beta(\mathbf{x})$ is a $\vartheta$-self-concordant
barrier [15], i.e., it is thrice differentiable and for every
$\mathbf{x}\in\mathop{\rm int}\mathcal{K}$ and every
$\mathbf{h}\in{\mathbb{R}}^{n}$, the function
$\tilde{f}(t)=\tilde{f}(t;\mathbf{x},\mathbf{h})\equiv\beta(\mathbf{x}+t\mathbf{h})$
satisfies (i) $|\tilde{f}^{\prime\prime\prime}(0)|\leq
2[\tilde{f}^{\prime\prime}(0)]^{3/2}$ (i.e., $\tilde{f}$ is a self-concordant
function), and also (ii)
$[\tilde{f}^{\prime}(0)]^{2}\leq\vartheta\cdot\tilde{f}^{\prime\prime}(0)$. It
follows that $\beta(\mathbf{x})$ is strictly convex. For example, for
$\mathbf{A}\in{\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in{\mathbb{R}}^{m}$,
the function
$\beta(\mathbf{x})\equiv-\sum_{i=1}^{m}\ln[(\mathbf{A}\mathbf{x})_{i}-b_{i}]$,
(defined for $\mathbf{x}$ such that $\mathbf{A}\mathbf{x}>\mathbf{b}$) is an
$m$-self-concordant barrier for the polyhedron
$\\{\mathbf{x}\in{\mathbb{R}}^{n}~{}|~{}\mathbf{A}\mathbf{x}\geq\mathbf{b}\\}$.

### The Dikin ellipsoid.

For every $\mathbf{v}\in{\mathbb{R}}^{n}$ and
$\mathbf{A}\in{\mathbb{R}}^{n\times n}$, denote
$\|\mathbf{v}\|_{\mathbf{A}}\equiv\sqrt{\mathbf{v}^{\top}\mathbf{A}\mathbf{v}}$,
and for every $\mathbf{h}\in{\mathbb{R}}^{n}$, denote
$\|\mathbf{h}\|_{\mathbf{x}}\equiv\sqrt{\mathbf{h}^{\top}[\nabla^{2}\beta(\mathbf{x})]\mathbf{h}}$.
The open _Dikin ellipsoid_ of radius $r$ centered at $\mathbf{x}$, denoted by
$W_{r}(\mathbf{x})$, is the set of all
$\mathbf{y}=\mathbf{x}+\mathbf{h}\in\mathcal{K}$ such that
$\|\mathbf{h}\|_{\mathbf{x}}^{2}=\mathbf{h}^{\top}[\nabla^{2}\beta(\mathbf{x})]\mathbf{h}<r^{2}$.

Below we use the following known facts about the Dikin ellipsoid and self-
concordant functions, whose proofs can be found in [15, Section 2.2, p. 23].

######  Proposition 1.

For every $\mathbf{x}\in\mathcal{K}$, $W_{1}(\mathbf{x})\subset\mathop{\rm
int}\mathcal{K}$.

The next proposition provides “bounds” on the Hessian
$\nabla^{2}\beta(\mathbf{x}+\mathbf{h})$ of $\beta(\mathbf{x}+\mathbf{h}))$
within Dikin’s ellipsoid. For $\mathbf{A},\mathbf{B}\in{\mathbb{R}}^{n\times
n}$, the notation $\mathbf{A}\succeq\mathbf{B}$ means that
$\mathbf{A}-\mathbf{B}$ is positive semi-definite.

######  Proposition 2.

For every $\mathbf{h}$ such that $\|\mathbf{h}\|_{\mathbf{x}}<1$,

$(1-\|\mathbf{h}\|_{\mathbf{x}})^{2}\nabla^{2}\beta(\mathbf{x})~{}\preceq~{}\nabla^{2}\beta(\mathbf{x}+\mathbf{h})~{}\preceq~{}(1-\|\mathbf{h}\|_{\mathbf{x}})^{-2}\nabla^{2}\beta(\mathbf{x})~{}.$
(1)

We denote the diameter of $\mathcal{K}$ by $\Delta$.

######  Proposition 3.

If (i ) $\beta(\mathbf{x})$ is a barrier function for $\mathcal{K}$, and (ii )
$\beta(\mathbf{x})$ is self-concordant, then for every
$\mathbf{x}\in\mathop{\rm int}\mathcal{K}$, all the eigenvalues of
$\nabla^{2}\beta(\mathbf{x})$ are greater than or equal to
$\frac{1}{\Delta^{2}}$.

###### Proof.

Proof. Fix $\mathbf{x}\in\mathop{\rm int}\mathcal{K}$ and a unit vector
$\mathbf{u}\in{\mathbb{R}}^{n}$. Denote

$t_{\max}=t_{\max}(\mathbf{x},\mathbf{u})\equiv\max\\{t\,|\,\mathbf{x}+t\,\mathbf{u}\in\mathcal{K}\\}\leq\Delta~{}.$
(2)

Define a function $\tilde{\beta}:[0,t_{\max})\rightarrow{\mathbb{R}}$ by

$\tilde{\beta}(t)=\tilde{\beta}(t;\mathbf{x},\mathbf{u})\equiv\beta(\mathbf{x}+t\,\mathbf{u})~{}.$
(3)

Note that
$\tilde{\beta}^{\prime}(t)=\mathbf{u}^{\top}[\nabla\beta(\mathbf{x}+t\mathbf{u})]$
and
$\tilde{\beta}^{\prime\prime}(t)=\mathbf{u}^{\top}[\nabla^{2}\beta(\mathbf{x}+t\mathbf{u})]\mathbf{u}$.
Since $\beta(\mathbf{x})$ is self-concordant, for every $t\in[0,t_{\max})$,
$\bigg{|}\left[(\tilde{\beta}^{\prime\prime}(t))^{-\mbox{$\frac{1}{2}$}}\right]^{\prime}\bigg{|}=\frac{|\tilde{\beta}^{\prime\prime\prime}(t)|}{2[\tilde{\beta}^{\prime\prime}(t)]^{3/2}}\leq
1$. It follows that
$t\geq\bigg{|}\int_{0}^{t}\frac{\tilde{\beta}^{\prime\prime\prime}(s)}{2[\tilde{\beta}^{\prime\prime}(s)]^{3/2}}\,ds\bigg{|}=\left|[\tilde{\beta}^{\prime\prime}(t)]^{-\mbox{$\frac{1}{2}$}}-[\tilde{\beta}^{\prime\prime}(0)]^{-\mbox{$\frac{1}{2}$}}\right|$.
Now, as $t$ tends to $t_{\max}$, $\tilde{\beta}(t)$ tends to infinity, and
hence also $\tilde{\beta}^{\prime}(t)$ and $\tilde{\beta}^{\prime\prime}(t)$
tend to infinity; thus,
$[\tilde{\beta}^{\prime\prime}(t)]^{-\mbox{$\frac{1}{2}$}}$ tends to zero. It
follows that $[\tilde{\beta}^{\prime\prime}(0)]^{-\mbox{$\frac{1}{2}$}}\leq
t_{\max}\leq\Delta$ and hence
$\mathbf{u}^{\top}\nabla^{2}\beta(\mathbf{x})\mathbf{u}=\tilde{\beta}^{\prime\prime}(0)\geq\frac{1}{\Delta^{2}}$.
Since this holds for every unit vector $\mathbf{u}$, the claim follows. ∎

######  Corollary 4.

For every $\mathbf{x}\in\mathop{\rm int}\mathcal{K}$, all the eignevalues of
$[\nabla^{2}\beta(\mathbf{x})]^{-1}$ are less than or equal to $\Delta^{2}$.

##  3 Algorithm and regret bounds

###  3.1 The algorithm and its performance.

We assume in this section that when the player has to pick the next point
$\mathbf{x}_{t+1}$, the player recalls $\mathbf{x}_{t}$ and knows $\nabla
f_{t}(\mathbf{x}_{t})$ and $\nabla^{2}\beta(\mathbf{x}_{t})$. Interior-point
algorithms for optimization typically utilize the Newton direction. In the
case of minimizing a function of the form $F_{\mu}(\mathbf{x})\equiv
f(\mathbf{x})-\mu\cdot\beta(\mathbf{x})$, while at a point $\mathbf{x}$, the
newton direction would be
$\mathbf{n}=-[\nabla^{2}F_{\mu}(\mathbf{x})]^{-1}\nabla(F_{\mu})(\mathbf{x})$.
However, for minimum-regret online optimization, it turns out that the
following direction is useful:

$\mathbf{n}_{t}=-[\nabla^{2}\beta(\mathbf{x}_{t})]^{-1}\nabla
f_{t}(\mathbf{x}_{t})~{},$

i.e., the gradient factor is determined by the previous objective function
$f_{t}$, while the Hessian factor is determined by the barrier function
$\beta$. This is reminiscent to the online gradient descent algorithm of [18],
in which only the gradient of the last cost function is used, although we also
use the linear transformation defined by the barrier. The standard Newton
direction is not used since our objective in online convex optimization is to
minimize regret rather than reach a global optimum.

Thus, when our algorithm is employed, the player picks
$\mathbf{x}_{t+1}=\mathbf{x}_{t}+\eta\,\mathbf{n}_{t}$, where $0<\eta<1$ is a
scalar whose value depends on $T$; it tends to zero as $T$ tends to infinity.
Denote $\mathbf{g}_{t}=\nabla f_{t}(\mathbf{x}_{t})$ and
$\mathbf{H}_{t}=\nabla^{2}\beta(\mathbf{x}_{t})$. Hence,
$\mathbf{n}_{t}=-\mathbf{H}_{t}^{-1}\mathbf{g}_{t}$.

Algorithm 1 Online IP-step

1: Input: $\vartheta$-self-concordant barrier $\beta$ for
$\mathcal{K}\subseteq{\mathbb{R}}^{n}$, learning rate $\eta>0$.

2: Initialize $\mathbf{x}_{1}$ arbitrarily.

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

4: Play $\mathbf{x}_{t}$ and observe $f_{t}$.

5: Set $\mathbf{x}_{t+1}=\mathbf{x}_{t}+\eta\mathbf{n}_{t}$.

6: end for

Our main theorem bounds the regret of Algorithm 1 by $O(\sqrt{T\log T})$,
where the $O$ notation hides constants of the setting independent of $T$. The
formal statement is the following theorem, which we proceed to prove it in the
rest of this section.

######  Theorem 5.

Suppose that $\eta=\frac{D}{\sqrt{10}G\Delta}\cdot\frac{1}{\sqrt{T}}$ for
$D=\sqrt{\vartheta\ln T+G\Delta}$, and $\eta G\Delta\leq\frac{1}{4}$. Then for
every $\mathbf{x}^{*}\in\mathcal{K}$, Algorithm 1 attains

$\displaystyle R(\mathbf{x}^{*})$ $\displaystyle\leq
9\sqrt{\vartheta}G\Delta\sqrt{T\log T}+9(G\Delta)^{3/2}\sqrt{T}$
$\displaystyle=O(\sqrt{\vartheta}G\Delta\sqrt{T\log T})$

###  3.2 Validity.

We first prove that the algorithm generates only points in $\mathcal{K}$.

######  Proposition 6.

For every $t$, if $\mathbf{x}_{t}\in\mathop{\rm int}\mathcal{K}$ and
$\eta<(\mathbf{g}_{t}^{\top}\mathbf{H}_{t}^{-1}\mathbf{g}_{t})^{-\mbox{$\frac{1}{2}$}}$,
then $\mathbf{x}_{t+1}\in\mathop{\rm int}\mathcal{K}$.

###### Proof.

Proof. In view of Proposition 1, it suffices to prove that
$\mathbf{x}_{t+1}\in W_{1}(\mathbf{x}_{t})$. By the definition of the Dikin
ellipsoid, it suffices to show that
$\|\eta\mathbf{n}_{t}\|_{\mathbf{x}_{t}}=\sqrt{(\eta\mathbf{n}_{t})^{\top}[\nabla^{2}\beta(\mathbf{x}_{t})](\eta\mathbf{n}_{t})}<1$.
Indeed,

$\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\|_{\mathbf{x}_{t}}^{2}\equiv(\mathbf{x}_{t+1}-\mathbf{x}_{t})^{\top}\mathbf{H}_{t}(\mathbf{x}_{t+1}-\mathbf{x}_{t})=\eta^{2}\,\mathbf{n}_{t}^{\top}\mathbf{H}_{t}\mathbf{n}_{t}=\eta^{2}\,\mathbf{g}_{t}^{\top}\mathbf{H}_{t}^{-1}\mathbf{g}_{t}<1~{}.$

Thus, $\mathbf{x}_{t+1}\in W_{1}(\mathbf{x}_{t})\subset\mathop{\rm
int}\mathcal{K}$. ∎

By Corollary 4,

$\mathbf{g}_{t}^{\top}\mathbf{H}_{t}^{-1}\mathbf{g}_{t}\leq\Delta^{2}\cdot\|\mathbf{g}_{t}\|^{2}~{}.$
(4)

Thus, we also have

######  Corollary 7.

If $\eta<\frac{1}{\Delta\cdot\|\mathbf{g}_{t}\|}$, then
$\mathbf{x}_{t+1}\in\mathop{\rm int}\mathcal{K}$.

###  3.3 A bound on the gradients.

As with any first-order method, the smoothness of the objective function, or
alternatively an upper bound on the gradient size, plays a role in its
convergence rate. The convexity and boundedness properties of the loss
functions also affect regret minimization, and thus we wish to express our
bound on the regret with respect to bounds on the gradients of the functions
selected by the adversary. Thus, we denote

$G=\max\left\\{\|\nabla f_{t}(\mathbf{x})\|\,:\,\mathbf{x}\in\mathcal{K},\
t=1,\ldots,T\right\\}~{}.$

Since the player does not know the function $f_{t}$ at the time of picking
$\mathbf{x}_{t}$, and that choice depends on $G$, we simply assume that the
adversary is restricted to choosing only functions $f$ such that $\|\nabla
f(\mathbf{x})\|\leq G$ for every $\mathbf{x}\in\mathcal{K}$.

We note that standard techniques, in particular the “doubling trick”, can be
used, without harming our asymptotic regret bounds, to eliminate the
requirement that the algorithm knows an upper bound $G$ a priori. Roughly
speaking, this simple technique assumes an a-priory fixed upper bound on $G$.
If during the repeated game this bound is exceeded, then the assumed upper
bound is doubled. It can be shown that the overall regret forms a geometric
series, and this way our results can be extended to the case that $G$ is not
known in advance.

######  Proposition 8.

Assuming $\eta G\Delta\leq\frac{1}{4}$, then for every $t=1,\ldots,T$, and
every $\mathbf{x}^{*}\in\mathcal{K}$

$\eta\,\mathbf{g}_{t}^{\top}(\mathbf{x}_{t}-\mathbf{x}^{*})~{}\leq~{}[\nabla\beta(\mathbf{x}_{t+1})-\nabla\beta(\mathbf{x}_{t})]^{\top}(\mathbf{x}^{*}-\mathbf{x}_{t})+8G^{2}\Delta^{2}\cdot\eta^{2}$
(5)

Before diving into the proof, we note that in our algorithm $\eta$ is indeed
chosen to satisfy the assumption of this hypothesis.

###### Proof.

Proof. Denote $\mathbf{v}=\mathbf{x}_{t}-\mathbf{x}^{*}$. Consider the
function $\gamma:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ defined by
$\gamma(\mathbf{y})=[\nabla\beta(\mathbf{y})]^{\top}\mathbf{v}$. Note that
$\nabla\gamma(\mathbf{y})=[\nabla^{2}\beta(\mathbf{y})]\mathbf{v}$. By
Taylor’s theorem, there exists a point
$\mathbf{z}\in[\mathbf{x}_{t},\mathbf{x}_{t+1}]$ such that
$\gamma(\mathbf{x}_{t+1})-\gamma(\mathbf{x}_{t})=(\mathbf{x}_{t+1}-\mathbf{x}_{t})^{\top}\nabla\gamma(\mathbf{z})=[-\eta\mathbf{H}_{t}^{-1}\mathbf{g}_{t}]^{\top}[\nabla^{2}\beta(\mathbf{z})]\mathbf{v}=-\eta\mathbf{g}_{t}^{\top}\mathbf{v}-\eta\mathbf{g}_{t}^{\top}\mathbf{H}_{t}^{-1}[\nabla^{2}\beta(\mathbf{z})-\mathbf{H}_{t}]\mathbf{v}$.
Denote $\mathbf{H}_{\mathbf{z}}=\nabla^{2}\beta(\mathbf{z})$ and
$\mathbf{B}=\mathbf{H}^{-1}_{t}\mathbf{H}_{\mathbf{z}}-\mathbf{I}$. Thus,

$\eta\mathbf{g}_{t}^{\top}\mathbf{v}+[\nabla\beta(\mathbf{x}_{t+1})-\nabla\beta(\mathbf{x}_{t})]^{\top}\mathbf{v}=-\eta\,\mathbf{g}_{t}^{\top}\mathbf{H}_{t}^{-1}(\mathbf{H}_{\mathbf{z}}-\mathbf{H}_{t})\mathbf{v}=-\eta\mathbf{g}_{t}^{\top}\mathbf{B}\mathbf{v}~{},$
(6)

We proceed to bound the LHS of the above. Notice that:

$\displaystyle(\mathbf{g}_{t}^{\top}\mathbf{B}\mathbf{v})^{2}$
$\displaystyle=(\mathbf{g}_{t}^{\top}\mathbf{B}\mathbf{v})(\mathbf{v}^{\top}\mathbf{B}^{T}\mathbf{g}_{t}^{\top})=\mathbf{g}_{t}^{\top}\mathbf{B}\mathbf{v}\mathbf{v}^{\top}\mathbf{B}^{T}\mathbf{g}_{t}^{\top}$
(7)
$\displaystyle\leq\|\mathbf{g}_{t}\|^{2}\|\mathbf{B}\mathbf{v}\mathbf{v}^{\top}\mathbf{B}^{T}\|$
$\|B\|$ denotes spectral norm $\displaystyle\leq
G^{2}\|\mathbf{B}(\|\mathbf{v}\|^{2}\mathbf{I})\mathbf{B}^{T}\|$
$BAB^{T}\preceq BCB^{T}$ for $A\preceq C$
$\displaystyle=G^{2}\|\mathbf{v}\|^{2}\|\mathbf{B}\mathbf{B}^{T}\|$
$\displaystyle\leq 4G^{2}\Delta^{2}\|\mathbf{B}\mathbf{B}^{T}\|$ defn of
$\mathbf{v}=\mathbf{x}_{t}-\mathbf{x}^{*}$

We proceed to bound $\|\mathbf{B}\mathbf{B}^{T}\|$

Since $\mathbf{z}\in[\mathbf{x}_{t},\mathbf{x}_{t+1}]$, $\mathbf{x}_{t+1}\in
W_{1}(\mathbf{x}_{t})$, and $W_{1}(\mathbf{x}_{t})$ is convex, it follows that
$\mathbf{z}\in W_{1}(\mathbf{x}_{t})$. Thus, by (1),
$(1-\|\mathbf{z}-\mathbf{x}_{t}\|_{\mathbf{H}_{t}})^{2}\mathbf{H}_{t}\preceq\mathbf{H}_{\mathbf{z}}\preceq~{}(1-\|\mathbf{z}-\mathbf{x}_{t}\|_{\mathbf{H}_{t}})^{-2}\mathbf{H}_{t}$.
Since $\mathbf{z}-\mathbf{x}_{t}=\alpha\cdot(\mathbf{x}_{t+1}-\mathbf{x}_{t})$
for some $\alpha\in[0,1]$, it follows that
$\|\mathbf{z}-\mathbf{x}_{t}\|_{\mathbf{H}_{t}}=\alpha\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\|_{\mathbf{H}_{t}}$
and hence
$(1-\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\|_{\mathbf{H}_{t}})^{2}\mathbf{H}_{t}\preceq\mathbf{H}_{\mathbf{z}}\preceq~{}(1-\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\|_{\mathbf{H}_{t}})^{-2}\mathbf{H}_{t}$.
Equivalently,

$\left(1-\eta\sqrt{\mathbf{g}_{t}^{\top}\mathbf{H}^{-1}_{t}\mathbf{g}_{t}}\right)^{2}\mathbf{H}_{t}\preceq\mathbf{H}_{\mathbf{z}}\preceq~{}\left(1-\eta\sqrt{\mathbf{g}_{t}^{\top}\mathbf{H}^{-1}_{t}\mathbf{g}_{t}}\right)^{-2}\mathbf{H}_{t}~{}.$
(8)

Since by Corollary 4
$\sqrt{\mathbf{g}_{t}^{\top}\mathbf{H}^{-1}_{t}\mathbf{g}_{t}}~{}\leq~{}\|\mathbf{g}_{t}\|\cdot\Delta~{}\leq~{}G\cdot\Delta$,
and we assume $\eta G\Delta<\frac{1}{4}<1$, it follows from (8) that

$(1-\eta
G\Delta)^{2}\mathbf{H}_{t}\preceq\mathbf{H}_{\mathbf{z}}\preceq~{}(1-\eta
G\Delta)^{-2}\mathbf{H}_{t}~{}.$ (9)

Obviously, if a matrix $\mathbf{H}$ is positive semi-definite, then so is
$\mathbf{A}^{\top}\mathbf{H}\mathbf{A}$ for every matrix $\mathbf{A}$. Thus,
if $\mathbf{H}\succeq{\mathbf{M}}$, then for every matrix $\mathbf{A}$,
$\mathbf{A}^{\top}\mathbf{H}\mathbf{A}\succeq\mathbf{A}^{\top}{\mathbf{M}}\mathbf{A}$.
Since $\mathbf{H}_{t}$ is positive-definite, there exists an
$\mathbf{A}\in{\mathbb{R}}^{n\times n}$ such that
$\mathbf{H}_{t}^{-1}=\mathbf{A}\mathbf{A}^{\top}$, so
$\mathbf{A}^{\top}\mathbf{H}_{t}\mathbf{A}=\mathbf{I}$. Thus,

$(1-\eta
G\Delta)^{2}\mathbf{I}\preceq\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A}\preceq(1-\eta
G\Delta)^{-2}\mathbf{I}~{}.$ (10)

We now bound the eigenvalues of
$\mathbf{B}=\mathbf{H}^{-1}_{t}\mathbf{H}_{\mathbf{z}}-\mathbf{I}=\mathbf{A}\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A}\mathbf{A}^{-1}-\mathbf{I}=\mathbf{A}(\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A}-\mathbf{I})\mathbf{A}^{-1}$.
Recall that a matrix $\mathbf{H}$ and a matrix
${\mathbf{M}}^{-1}\mathbf{H}{\mathbf{M}}$ have the same eigenvalues. Thus,
$\lambda_{\max}(\mathbf{B})=\lambda_{\max}(\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A}-\mathbf{I})=\lambda_{\max}(\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A})-1$
and
$\lambda_{\min}(\mathbf{B})=\lambda_{\min}(\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A})-1$.
It follows from (10) that all the eigenvalues of
$\mathbf{A}^{\top}\mathbf{H}_{\mathbf{z}}\mathbf{A}$ are between $(1-\eta
G\Delta)^{2}$ and $(1-\eta G\Delta)^{-2}$; hence, all the eigenvalues of
$\mathbf{B}$ are between $\ell\equiv(1-\eta G\Delta)^{2}-1=-2\eta
G\Delta+(\eta G\Delta)^{2}\geq-2\eta G\Delta$ and $u\equiv(1-\eta
G\Delta)^{-2}-1=\frac{2\eta G\Delta-(\eta G\Delta)^{2}}{1-2\eta G\Delta+(\eta
G\Delta)^{2}}\leq\frac{2\eta G\Delta}{1-2\eta G\Delta}$. Assuming $\eta
G\Delta<1/4$, we have $u<4\eta G\Delta$.

Thus,

$\displaystyle\|\mathbf{B}\mathbf{B}^{T}\|$
$\displaystyle\leq\max\\{u^{2},l^{2}\\}\leq 16\eta^{2}G^{2}\Delta^{2}$

Plugging back into 7 we get

$\left|\mathbf{g}_{t}^{\top}\mathbf{B}\mathbf{v}\right|\leq 2G\Delta\cdot\eta
4G\Delta\leq\eta 8G^{2}\Delta^{2}$

Plugging the latter into (6), we get

$\displaystyle{\eta\mathbf{g}_{t}^{\top}\mathbf{v}+}$ | $\displaystyle{{}[\nabla\beta(\mathbf{x}_{t+1})-\nabla\beta(\mathbf{x}_{t})]^{\top}\mathbf{v}=-\eta\mathbf{g}^{\top}\mathbf{B}\mathbf{v}\leq 8\eta^{2}G^{2}\Delta^{2}}$
---|---

∎

###  3.4 A bound dependent on Bregman divergence.

For this section, denote by $\mathbf{x}_{1},\ldots,\mathbf{x}_{T}$ sequence
that is generated by Algorithm 1. Given the functions $f_{1},\ldots,f_{T}$ and
the choices $\mathbf{x}_{1},\ldots,\mathbf{x}_{T}$, recall that for any
$\mathbf{x}^{*}\in\mathcal{K}$, the regret with respect to $\mathbf{x}^{*}$ is
given by

$R(\mathbf{x}^{*})\equiv\mbox{$\sum_{t=1}^{T}f_{t}(\mathbf{x}_{t})-\sum_{t=1}^{T}f_{t}(\mathbf{x}^{*})$}~{}.$

For $\mathbf{x},\mathbf{y}\in\mathop{\rm int}\mathcal{K}$, the Bregman
divergence $B_{\beta}(\mathbf{x},\mathbf{y})$ with respect to the barrier
$\beta(\mathbf{x})$ is given by

$B_{\beta}(\mathbf{x},\mathbf{y})=\beta(\mathbf{x})-\beta(\mathbf{y})-[\nabla\beta(\mathbf{y})]^{\top}(\mathbf{x}-\mathbf{y})~{}.$

We note that this divergence is well defined for any convex function, not
necessarily a barrier.

Further, in this section we assume that we know a bound on the Bregman
divergence as follows. Although the player does not know the optimal point
$\mathbf{x}^{*}$, for the purpose of design and analysis of the algorithm we
use a bound $D$ that is guaranteed to satisfy

$D\geq\sqrt{B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{1})}~{}$

The parameter $D$ will be used in the choice of the learning rate $\eta$ in
Algorithm 1, and an explicit choice of $D$ will be used to obtain the regret
bound given by Theorem 5.

######  Theorem 9.

Suppose that $\eta=\frac{D}{\sqrt{10}G\Delta}\cdot\frac{1}{\sqrt{T}}$ and
$\eta G\Delta\leq\frac{1}{4}$. Then Algorithm 1 generates valid points in the
convex domain and satisfies for every $\mathbf{x}^{*}\in\mathop{\rm
int}\mathcal{K}$ for which
$D\geq\sqrt{B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{1})}$,

$R(\mathbf{x}^{*})\leq 8DG\Delta\cdot\sqrt{T}~{}.$

###### Proof.

Proof. The proof uses ideas from the proof of [2, Theorem 4.1] which, in turn,
follows [9], with the Bregman divergence replacing the Euclidean distance as a
potential function.

Notice that the assumptions of Corollary 7 are satisfied by choice of $\eta$.

Let $\mathbf{x}^{*}\in\mathop{\rm int}\mathcal{K}$ be fixed. Since the
functions $f_{t}$ are convex,

$f_{t}(\mathbf{x}_{t})-f_{t}(\mathbf{x}^{*})\leq[\nabla
f_{t}(\mathbf{x}_{t})]^{\top}(\mathbf{x}_{t}-\mathbf{x}^{*})~{}.$ (11)

Now,

$\displaystyle{B_{\beta}(\mathbf{x},\mathbf{y})-B_{\beta}(\mathbf{x},\mathbf{z})+B_{\beta}(\mathbf{y},\mathbf{z})=}$ | $\displaystyle{{}\ -[\nabla\beta(\mathbf{y})]^{\top}(\mathbf{x}-\mathbf{y})+[\nabla\beta(\mathbf{z})]^{\top}(\mathbf{x}-\mathbf{y})}$
---|---
$\displaystyle{=}$ | $\displaystyle{{}\ (\mathbf{x}-\mathbf{y})^{\top}[\nabla\beta(\mathbf{z})-\nabla\beta(\mathbf{y})]~{}.}$
(12)

Hence, by (11), (12) and Proposition 8 (whose assumptions are satisfied by
choice of $\eta$)

$\displaystyle{f_{t}(\mathbf{x}_{t})}$ | $\displaystyle{{}-f_{t}(\mathbf{x}^{*})\leq[\nabla f_{t}(\mathbf{x}_{t})]^{\top}(\mathbf{x}_{t}-\mathbf{x}^{*})}$
---|---
$\displaystyle{\leq}$ | $\displaystyle{{}\ \mbox{$\frac{1}{\eta}$}\cdot[\nabla\beta(\mathbf{x}_{t+1})-\nabla\beta(\mathbf{x}_{t})]^{\top}(\mathbf{x}^{*}-\mathbf{x}_{t})+8G^{2}\Delta^{2}\,\eta}$
$\displaystyle{=}$ | $\displaystyle{{}\ \mbox{$\frac{1}{\eta}$}\,\left[B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{t})-B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{t+1})+B_{\beta}(\mathbf{x}_{t},\mathbf{x}_{t+1})\right]+8G^{2}\Delta^{2}\,\eta~{}.}$
(13)

Summing (13) over all stages,

$\displaystyle{R(\mathbf{x}^{*})\leq}$ |  $\frac{1}{\eta}\left[B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{1})-B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{T})\right]+\frac{1}{\eta}\sum_{t=1}^{T}B_{\beta}(\mathbf{x}_{t},\mathbf{x}_{t+1})+T\,8G^{2}\Delta^{2}\,\eta$
---|---
$\displaystyle{\leq}$ | $\displaystyle{{}\ \mbox{$\frac{D^{2}}{\eta}+\frac{1}{\eta}\cdot\sum_{t=1}^{T}B_{\beta}(\mathbf{x}_{t},\mathbf{x}_{t+1})+T\cdot 8G^{2}\Delta^{2}\,\eta$}~{}.}$
(14)

To bound $B_{\beta}(\mathbf{x}_{t},\mathbf{x}_{t+1})$, note that by definition
of Bregman divergence, for some point
$\mathbf{z}\in[\mathbf{x}_{t},\mathbf{x}_{t+1}]$,

$\displaystyle{B_{\beta}(\mathbf{x}_{t},\mathbf{x}_{t+1})=}$ | $\displaystyle{{}\ \beta(\mathbf{x}_{t})-\beta(\mathbf{x}_{t+1})-[\nabla\beta(\mathbf{x}_{t+1})]^{\top}(\mathbf{x}_{t}-\mathbf{x}_{t+1})}$
---|---
$\displaystyle{=}$ | $\displaystyle{{}\ \mbox{$\frac{1}{2}$}(\mathbf{x}_{t}-\mathbf{x}_{t+1})^{\top}\mathbf{H}_{\mathbf{z}}(\mathbf{x}_{t}-\mathbf{x}_{t+1})~{}.}$

By (9), assuming $\eta G\Delta<\frac{1}{4}$,

$\displaystyle{(\mathbf{x}_{t}-\mathbf{x}_{t+1})^{\top}\mathbf{H}_{\mathbf{z}}(\mathbf{x}_{t}-\mathbf{x}_{t+1})\leq}$ | $\displaystyle{{}\ (1-\eta G\Delta)^{-2}(\mathbf{x}_{t}-\mathbf{x}_{t+1})^{\top}\mathbf{H}_{t}(\mathbf{x}_{t}-\mathbf{x}_{t+1})}$
---|---
$\displaystyle{<}$ | $\displaystyle{{}\ 2(\mathbf{x}_{t}-\mathbf{x}_{t+1})^{\top}\mathbf{H}_{t}(\mathbf{x}_{t}-\mathbf{x}_{t+1})~{}.}$

Thus, $B_{\beta}(\mathbf{x}_{t},\mathbf{x}_{t+1})\leq
2(\mathbf{x}_{t}-\mathbf{x}_{t+1})^{\top}\mathbf{H}_{t}(\mathbf{x}_{t}-\mathbf{x}_{t+1})=2\eta^{2}\mathbf{g}_{t}^{\top}\mathbf{H}_{t}^{-1}\mathbf{g}_{t}\leq
2\eta^{2}\,G^{2}\Delta^{2}$. It follows that

$\mbox{$R(\mathbf{x}^{*})\leq\frac{D^{2}}{\eta}+\frac{1}{\eta}\cdot T\cdot
2\eta^{2}G^{2}\Delta^{2}+T\cdot
8G^{2}\Delta^{2}\cdot\eta=\frac{D^{2}}{\eta}+10G^{2}\Delta^{2}\,T\,\eta$}~{}.$

Thus, picking $\eta=\frac{D}{\sqrt{10}G\Delta}\cdot\frac{1}{\sqrt{T}}$ yields
$R(\mathbf{x}^{*})\leq 2\sqrt{10}DG\Delta\cdot\sqrt{T}$. ∎

Note that as $\mathbf{x}^{*}$ tends to the boundary of $\mathcal{K}$,
$B_{\beta}(\mathbf{x}^{*},\mathbf{x}_{1})$ tends to infinity, and hence
necessarily so does $D$. Thus, the regret bound for $\mathbf{x}^{*}$ on the
boundary of $\mathcal{K}$ requires further analysis, as in [2]. This is what
we describe below.

###  3.5 The final regret bound

######  Proposition 10.

Let $\beta(\cdot)$ be a $\vartheta$-self-concordant barrier for $\mathcal{K}$,
and let $\mathbf{x}\in\mathop{\rm int}\mathcal{K}$ and a unit vector
$\mathbf{u}\in{\mathbb{R}}^{n}$ be such that
$\mathbf{u}^{\top}\nabla\beta(\mathbf{x})>0$. Let
$t_{\max}=t_{\max}(\mathbf{x},\mathbf{u})$ be defined as in (2). Under these
conditions,

$\mathbf{u}^{\top}\nabla\beta(\mathbf{x})\leq\frac{\vartheta}{t_{\max}(\mathbf{x},\mathbf{u})}~{}.$

###### Proof.

Proof. Note that $t_{\max}$ is equal to the distance from $\mathbf{x}$ to the
boundary of $\mathcal{K}$ along the direction of $\mathbf{u}$. Since
$\beta(\cdot)$ is a $\vartheta$-self-concordant barrier,

$\left[-\frac{1}{\tilde{\beta}^{\prime}(t)}\right]^{\prime}=\frac{\tilde{\beta}^{\prime\prime}(t)}{[\tilde{\beta}^{\prime}(t)]^{2}}\geq\frac{1}{\vartheta}~{}.$

Consider the function $\tilde{\beta}(t)$ that was defined in (3). For every
$t<t_{\max}$,

$\frac{1}{\tilde{\beta}^{\prime}(0)}-\frac{1}{\tilde{\beta}^{\prime}(t)}=\int_{0}^{t}\left[\frac{-1}{\tilde{\beta}^{\prime}(s)}\right]^{\prime}\,ds\geq\frac{t}{\vartheta}~{}$

and, since $\tilde{\beta}^{\prime}(t)$ tends to infinity as $t$ tends to
$t_{\max}$, it follows that
$t_{\max}\leq\frac{\vartheta}{\tilde{\beta}^{\prime}(0)}$. The latter implies
our proposition because
$\beta^{\prime}(0)=\mathbf{u}^{\top}\nabla\beta(\mathbf{x})$. ∎

For distinct vectors $\mathbf{x},\mathbf{y}\in\mathcal{K}$, denote
$\tau_{\max}(\mathbf{x},\mathbf{y})=t_{\max}\left(\mathbf{x},\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|}\right)$.

######  Proposition 11.

If $\mathbf{x},\mathbf{y}\in\mathop{\rm int}\mathcal{K}$ are distinct, then

$\beta(\mathbf{y})-\beta(\mathbf{x})\leq-\ln\left(1-\frac{\|\mathbf{y}-\mathbf{x}\|}{\tau_{\max}(\mathbf{x},\mathbf{y})}\right)\cdot\vartheta~{}.$

###### Proof.

Proof. Given any two distinct points $\mathbf{x},\mathbf{y}\in\mathop{\rm
int}\mathcal{K}$, denote
$\mathbf{u}=\frac{\mathbf{y}-\mathbf{x}}{\|\mathbf{y}-\mathbf{x}\|}$. For
every $t\in[0,\|\mathbf{y}-\mathbf{x}\|]$,
$t_{\max}(\mathbf{x}+t\mathbf{u},\mathbf{u})=t_{\max}(\mathbf{x},\mathbf{u})-t$.
It follows that

$\mathbf{u}^{\top}\nabla\beta(\mathbf{x}+t\mathbf{u})\leq\frac{\vartheta}{t_{\max}(\mathbf{x},\mathbf{u})-t}~{}.$

Thus,

$\displaystyle~{}~{}~{}~{}~{}~{}\beta(\mathbf{y})-\beta(\mathbf{x})$
$\displaystyle=$
$\displaystyle\int_{0}^{\|\mathbf{y}-\mathbf{x}\|}\tilde{\beta}(t)\,dt=\int_{0}^{\|\mathbf{y}-\mathbf{x}\|}\mathbf{u}^{\top}\nabla\beta(\mathbf{x}+t\mathbf{u})\,dt$
$\displaystyle\leq$
$\displaystyle\int_{0}^{\|\mathbf{y}-\mathbf{x}\|}\frac{\vartheta}{t_{\max}(\mathbf{x},\mathbf{u})-t}\,dt=-\ln\left(1-\frac{\|\mathbf{y}-\mathbf{x}\|}{\tau_{\max}(\mathbf{x},\mathbf{y})}\right)\cdot\vartheta~{}.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$

∎

######  Definition 1 ([15]).

Given the initial point $\mathbf{x}_{1}\in\mathop{\rm int}K$ and a real
$\delta>0$, the inner subset $\mathcal{K}(\delta;\mathbf{x}_{1})$ is defined
by

$\mathcal{K}(\delta;\mathbf{x}_{1})=\left\\{\mathbf{y}\in\mathcal{K}\,:\,\|\mathbf{y}-\mathbf{x}_{1}\|\leq\frac{1}{1+\delta}\cdot\tau_{\max}(\mathbf{x}_{1},\mathbf{y})\right\\}~{}.$

######  Corollary 12.

If $\mathbf{y}\in\mathcal{K}(\delta;\mathbf{x}_{1})$, then
$\beta(\mathbf{y})-\beta(\mathbf{x}_{1})\leq\ln\left(1+1/\delta\right)\cdot\vartheta$.

###### Proof.

Proof. By Proposition 11,

$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\beta(\mathbf{y})-\beta(\mathbf{x}_{1})$
$\displaystyle\leq$
$\displaystyle-\ln\left(1-\frac{\|\mathbf{y}-\mathbf{x}_{1}\|}{\tau_{\max}(\mathbf{x}_{1},\mathbf{y})}\right)\cdot\vartheta\leq-\ln\left(1-\frac{\tau_{\max}(\mathbf{x}_{1},\mathbf{y})/(1+\delta)}{\tau_{\max}(\mathbf{x}_{1},\mathbf{y})}\right)\cdot\vartheta$
$\displaystyle=$
$\displaystyle\ln\left(1+1/\delta\right)\cdot\vartheta~{}.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$

∎

We are now ready to conclude with the proof of Theorem 5:

###### Proof.

Proof.[proof of Theorem 5] The idea is to analyze the regret vs.
$\mathbf{x}^{*}$ by composing it into regret vs. $\mathbf{x}_{\delta}^{*}$
which is in the interior and for which we can use the results of the previous
section, as well as the total loss accumulated by taking a close point instead
of the exact. This is made precise as follows. Given any
$\mathbf{x}^{*}\in\mathcal{K}$ and $\delta>0$, denote

$\mathbf{x}^{*}_{\delta}=\mathbf{x}_{1}+\frac{\tau_{\max}(\mathbf{x}_{1},\mathbf{x}^{*})}{1+\delta}\cdot\frac{\mathbf{x}^{*}-\mathbf{x}_{1}}{\|\mathbf{x}^{*}-\mathbf{x}_{1}\|}~{}.$

Note that

$\displaystyle{\|\mathbf{x}^{*}_{\delta}-\mathbf{x}^{*}\|\leq}$ | $\displaystyle{{}\tau_{\max}(\mathbf{x}_{1},\mathbf{x}^{*})-\frac{\tau_{\max}(\mathbf{x}_{1},\mathbf{x}^{*})}{1+\delta}=\frac{\delta}{1+\delta}\cdot\tau_{\max}(\mathbf{x}_{1},\mathbf{x}^{*})<\delta\,\Delta~{}.}$
---|---

We have

$R(\mathbf{x}^{*})=\sum_{t=1}^{T}f_{t}(\mathbf{x}_{t})-\sum_{t=1}^{T}f_{t}(\mathbf{x}^{*})=R(\mathbf{x}^{*}_{\delta})+\sum_{t=1}^{T}\left[f_{t}(\mathbf{x}^{*}_{\delta})-f_{t}(\mathbf{x}^{*})\right]$.

Also,

$\sum_{t=1}^{T}\left[f_{t}(\mathbf{x}^{*}_{\delta})-f_{t}(\mathbf{x}^{*})\right]\leq\sum_{t=1}^{T}(\mathbf{x}^{*}_{\delta}-\mathbf{x}^{*})^{\top}\nabla
f_{t}(\mathbf{x}^{*}_{\delta})\leq\|\mathbf{x}^{*}_{\delta}-\mathbf{x}^{*}\|\cdot\sum_{t=1}^{T}\|\nabla
f_{t}(\mathbf{x}^{*}_{\delta})\|<\delta\,\Delta\,G\,T$ .

Since $\mathbf{x}^{*}_{\delta}\in\mathop{\rm int}\mathcal{K}$, Theorem 9 can
be applied, so

$R(\mathbf{x}^{*}_{\delta})\leq 8DG\Delta\cdot\sqrt{T}~{}.$

Furthermore, since
$\mathbf{x}^{*}_{\delta}\in\mathcal{K}(\delta;\mathbf{x}_{1})$, by Corollary
12

$\beta(\mathbf{x}^{*}_{\delta})-\beta(\mathbf{x}_{1})\leq\ln\left(1+1/\delta\right)\cdot\vartheta~{}$

and hence

$\displaystyle{B_{\beta}(\mathbf{x}^{*}_{\delta},\mathbf{x}_{1})=}$ | $\displaystyle{{}\ \beta(\mathbf{x}^{*}_{\delta})-\beta(\mathbf{x}_{1})-[\nabla^{\top}\beta(\mathbf{x}_{1})]^{\top}(\mathbf{x}^{*}_{\delta}-\mathbf{x}_{1})\leq\ln\left(1+1/\delta\right)\cdot\vartheta+G\Delta~{}.}$
---|---

Thus, may choose $D$ as follows - that will determine $\eta$ in Algorithm 1,
as given in Theorem 9 to be
$\eta=\frac{D}{\sqrt{10}G\Delta}\cdot\frac{1}{\sqrt{T}}$.

$D=\sqrt{\ln\left(1+1/\delta\right)\cdot\vartheta+G\Delta}$

so that the regret bound of Theorem 9 with respect to
$\mathbf{x}^{*}_{\delta}$ holds. It follows that

$R(\mathbf{x}^{*})\leq
8G\Delta\sqrt{\ln\left(1+1/\delta\right)\cdot\vartheta+G\Delta}\cdot\sqrt{T}+\delta\,\Delta\cdot
G\,T~{}.$

Thus, taking $\delta=1/T$, then we obtain

$\displaystyle R(\mathbf{x}^{*})$ $\displaystyle\leq
8G\Delta\sqrt{\ln\left(1+T\right)\cdot\vartheta+G\Delta}\cdot\sqrt{T}+G\Delta$
$\displaystyle\leq
9G\Delta\sqrt{\vartheta\ln\left(T\right)+G\Delta}\cdot\sqrt{T}$ assuming
$T>10G\Delta$ $\displaystyle\leq 9\sqrt{\vartheta}G\Delta\sqrt{T\log
T}+9(G\Delta)^{3/2}\sqrt{T}$ $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$

∎

#### Remark.

Since the point $\mathbf{x}_{1}$ can be chosen arbitrarily, the analysis of
the regret over the interval $1,2,\ldots,T$ can be applied to any subinterval
$s,s+1,\ldots,t$. Recall that the algorithm uses the parameter
$\eta=O(1/\sqrt{T})$. It follows that the regret over any subinterval is also
$O(\sqrt{T\log T})$.

## References

  * [1] D. B. Yudin A. S. Nemirovski.  Problem Complexity and Method Efficiency in Optimization.  Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons Ltd, 1983.
  * [2] J. Abernethy, E. Hazan, and A. Rakhlin.  Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization.  In R. Servedio and T. Zhang, editors, Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 264 – 274. Springer, Berlin, 2008.  http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.html.
  * [3] Baruch Awerbuch and Robert Kleinberg.  Online linear optimization and adaptive routing.  J. Comput. Syst. Sci., 74(1):97–114, 2008.
  * [4] Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  Operations Research Letters, 31(3):167 – 175, 2003.
  * [5] N. Cesa-Bianchi and G. Lugosi.  Prediction, Learning, and Games.  Cambridge University Press, 2006.
  * [6] T. Cover.  Universal portfolios.  Math. Finance, 1:1–19, 1991.
  * [7] A .J. Grove, N. Littlestone, and D. Schuurmans.  General convergence results for linear discriminant updates.  Machine Learning, 43(3):173–210, 2001.
  * [8] E. Hazan.  The convex optimization approach to regret minimization.  Optimization for machine learning, 1:287–302, 2011.
  * [9] Elad Hazan, Amit Agarwal, and Satyen Kale.  Logarithmic regret algorithms for online convex optimization.  Machine Learning, 69(2-3):169–192, 2007.
  * [10] Elad Hazan and Satyen Kale.  Extracting certainty from uncertainty: regret bounded by variation in costs.  Machine Learning, 80(2-3):165–188, 2010.
  * [11] Elad Hazan and C. Seshadhri.  Efficient learning algorithms for changing environments.  In Proceedings of the 26th Annual International Conference on Machine Learning (ICML 2009), volume 382, page 50, 2009.
  * [12] A. T. Kalai and S. Vempala.  Efficient algorithms for online decision problems.  Journal of Computer and System Sciences, 71(3):291–307, 2005.
  * [13] J. Kivinen and M. K. Warmuth.  Relative loss bounds for multidimensional regression problems.  Machine Learning, 45(3):301–329, 2001.
  * [14] N. Littlestone and M. K. Warmuth.  The weighted majority algorithm.  In Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, pages 256–261, 1989.
  * [15] A. Nemirovski.  Interior point polynomial time methods in convex programming.  Technical Report 8813, Georgia Institute of Technology, 2004.
http://www2.isye.gatech.edu/$\sim$nemirovs/Lect_IPM.pdf.

  * [16] Shai Shalev-Shwartz and Yoram Singer.  A primal-dual perspective of online learning algorithms.  Machine Learning, 69:115–142, 2007.  10.1007/s10994-007-5014-x.
  * [17] Yinyu Ye.  An o(n${}^{\mbox{3}}$L) potential reduction algorithm for linear programming.  Math. Program., 50:239–258, 1991.
  * [18] M. Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In T. Fawcett and N. Mishra, editors, Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928 – 936, 2003.