\section{Introduction}

The exact higher spin black hole solutions in three spacetime dimensions that
have been recently found in \cite{GK, GKMP, CM} provide a unique arena in
order to acquire a deeper understanding of higher spin gravity
\cite{V1,V2,V3,V4}. These solutions possess a relaxed asymptotically AdS
behaviour as compared with the one proposed in refs. \cite{Henneaux-HS,
Theisen-HS, Campoleoni-HS, GH}. It is worth pointing out that a similar effect
occurs in the case of hairy black holes with scalar fields with slow fall-off
at infinity \cite{HMTZ-2+1,HMTZ-Log, HMTZ-D, HM, AM}. In this case, it is
known that the asymptotic conditions turn out to be relaxed with respect to
the ones of Brown and Henneaux \cite{Brown-Henneaux}, and as a consequence,
the global charges, and in particular the energy, acquire nontrivial
contributions given by nonlinear terms in the deviation of the fields with
respect to the reference background. Therefore, it is natural to wonder about
the persistence of this effect for black holes endowed with higher spin
fields. Here it is shown that this is indeed the case for the class of higher
spin black holes mentioned above. In fact, as they possess a relaxed
asymptotic behaviour, their energy does not depend linearly on the deviation
of the fields with respect to the background configuration. Therefore, the
higher spin black hole energy must be computed from scratch.

In the next section, higher spin gravity in three dimensions as a Chern-Simons
theory is revisited, where the canonical approach to construct conserved
charges as surface integrals is also briefly discussed. Section \ref{AGKP} is
devoted to perform the explicit computation of the energy, including the
analysis of nontrivial integrability conditions for the higher spin black hole
solution found in refs. \cite{GK,GKMP}. This is also carried out for the
solution of ref. \cite{CM} in section \ref{CMsect}, where it is also shown
that the first law of thermodynamics is automatically fulfilled in the
canonical ensemble, i.e., without work terms associated to the presence of
higher spin fields. The semiclassical entropy of this higher spin black hole
is also shown to be exactly reproduced by means of Cardy formula. Final
comments are discussed in section \ref{Discussion}.

\section{Higher spin gravity as a Chern-Simons theory in 3D}

As it was shown in \cite{Blencowe, BBS}, a Chern-Simons action whose gauge
group is given by $SL\left(  N,\mathbb{R}\right)  \times SL\left(
N,\mathbb{R}\right)  $ describes a theory of gravity with negative
cosmological constant, coupled to interacting fields of higher spin
$s=3,4,...,N$, in three dimensions. Analogously, a consistent theory of
gravity that includes the whole infinite tower of higher spin fields can be
constructed by means of two copies of the $hs(\lambda)$ algebra. Let us focus
on the simplest case that corresponds to $N=3$. The theory can then be
described in terms of two independent connection one-forms, $A^{+}$ and
$A^{-}$, associated to each copy of $SL\left(  3,\mathbb{R}\right)  $, so that
the action is given by%
\begin{equation}
I=I_{CS}\left[  A^{+}\right]  -I_{CS}\left[  A^{-}\right]  \ , \label{Itotal}%
\end{equation}
where%
\begin{equation}
I_{CS}\left[  A\right]  =\frac{k}{4\pi}\int_{M}\left\langle AdA+\frac{2}%
{3}A^{3}\right\rangle \ , \label{Ics}%
\end{equation}
and the level is determined by the Newton constant and the AdS radius
according to $k=\frac{l}{4G}$. Here the bracket stands for an invariant
nondegenerate bilinear form of $SL\left(  3,\mathbb{R}\right)  $ that is
proportional to the Cartan-Killing metric. The fundamental representation of
$SL\left(  3,\mathbb{R}\right)  $ is generated by $L_{i}$ and $W_{m}$, where
$i=-1,0,1$, and $m=-2,-1,...,+2$, and the bracket is given by a quarter of the
trace, i.e., $\left\langle \cdots\right\rangle =\frac{1}{4}\mathrm{tr}\left(
\cdots\right)  $, see e.g., \cite{Theisen-HS}.

Since the field equations imply the vanishing of $SL\left(  3,\mathbb{R}%
\right)  $ curvatures, i.e., $F^{\pm}=0$, the connections become locally flat
on shell.

It is useful to introduce a generalization of the dreibein and spin connection
according to%
\begin{equation}
A^{\pm}=\omega\pm\frac{e}{l}\ ,
\end{equation}
so that, in the principal embedding of $sl\left(  2,\mathbb{R}\right)  $ into
$sl\left(  3,\mathbb{R}\right)  $, the spacetime metric and the spin $3$ field
are recovered from%
\begin{equation}
g_{\mu\nu}=\frac{1}{2}\mathrm{tr}\left(  e_{\mu}e_{\nu}\right)  \ ,
\label{gmunu}%
\end{equation}
and%
\begin{equation}
\varphi_{\mu\nu\rho}=\frac{1}{3!}\mathrm{tr}\left(  e_{(\mu}e_{\nu}e_{\rho
)}\right)  \ , \label{phimunurho}%
\end{equation}
respectively.

It is worth pointing out that the metric transforms nontrivially under the
higher spin gauge symmetries embedded in $SL\left(  3,\mathbb{R}\right)
\times SL\left(  3,\mathbb{R}\right)  $, and as a consequence, some standard
geometric and physical notions may appear to be ambiguous, since they are no
longer gauge invariant. Therefore, in order to provide a reliable definition
of energy, our proposal is to stay attached to its very basic definition: the
energy corresponds to the conserved charge associated with the generator of
time evolution, i.e., it is given by the Hamiltonian.

\subsection{Canonical generators}

The suitable definition of energy we look for a Chern-Simons theory of the
form (\ref{Itotal}) can then be obtained following the Regge-Teitelboim
approach \cite{Regge-Teitelboim}. In the canonical formalism, the variation of
the conserved charge associated to an asymptotic gauge symmetry generated by
an algebra-valued parameter $\eta=\eta^{+}+\eta^{-}$ is given by%
\begin{equation}
\delta Q\left(  \eta\right)  =-\frac{k}{2\pi}\int_{\partial\Sigma}\left(
\left\langle \eta^{+}\delta A_{\phi}^{+}\right\rangle -\left\langle \eta
^{-}\delta A_{\phi}^{-}\right\rangle \right)  d\phi\ , \label{deltaqeta}%
\end{equation}
where $\partial\Sigma$ stands for the boundary of the spacelike section
$\Sigma\ $(see e.g., \cite{Balachandran, Banados-Q, Carlip-Q}). Since
diffeomorphisms are not independent of gauge transformations for a
Chern-Simons theory in three dimensions, the variation of the generator of an
asymptotic symmetry spanned by an asymptotic killing vector $\xi^{\mu}$,
reduces to%
\begin{equation}
\delta Q\left(  \xi\right)  =\frac{k}{2\pi}\int_{\partial\Sigma}\xi^{\mu
}\left(  \left\langle A_{\mu}^{+}\delta A_{\phi}^{+}\right\rangle
-\left\langle A_{\mu}^{-}\delta A_{\phi}^{-}\right\rangle \right)  d\phi\ .
\label{deltaqchi}%
\end{equation}
Therefore, the variation of the energy, $E=Q\left(  \partial_{t}\right)  $, is
given by%
\begin{equation}
\delta Q\left(  \partial_{t}\right)  =\frac{k}{2\pi}\int_{\partial\Sigma
}\left(  \left\langle A_{t}^{+}\delta A_{\phi}^{+}\right\rangle -\left\langle
A_{t}^{-}\delta A_{\phi}^{-}\right\rangle \right)  d\phi\ . \label{deltaM}%
\end{equation}
The variation of the canonical generators in eqs.\ (\ref{deltaqeta}),
(\ref{deltaqchi}), and (\ref{deltaM}) then corresponds to the ones of higher
spin gravity provided the parameter $\eta^{\pm}$ takes values on $hs\left(
\lambda\right)  $ or $sl\left(  N,\mathbb{R}\right)  $. In both cases, a
consistent set of asymptotic conditions has been proposed in refs.
\cite{Henneaux-HS} and \cite{Theisen-HS,Campoleoni-HS, GH}, respectively,
being such that the conserved charges turn out to be linear in the deviation
of the fields with respect to the AdS$_{3}$ background\footnote{The
supersymmetric extension of the asymptotic conditions of \cite{Henneaux-HS}
was developed in ref. \cite{Super-HS}.}. Indeed, for the case of $sl\left(
3,\mathbb{R}\right)  $, the asymptotic conditions for the gauge fields can be
written as%
\[
A^{\pm}=\bar{A}^{\pm}+\Delta A^{\pm}\ ,
\]
where the deviation with respect to the background configuration $\bar{A}%
^{\pm}$, which is assumed to be AdS$_{3}$ spacetime of radius $l$, is of the
form%
\begin{equation}
\Delta A^{\pm}=\pm\left(  -\frac{2\pi}{k}\mathcal{L}^{\pm}e^{-\rho}L_{\mp
1}^{\pm}\mp\frac{\pi}{2k}\mathcal{W}^{\pm}e^{-2\rho}W_{\mp2}^{\pm}\right)
dx^{\pm}\ , \label{DeltaA}%
\end{equation}
with $x^{\pm}=\frac{t}{l}\pm\phi$, and $L_{i}^{\pm}$ span two copies of the
$sl\left(  2,\mathbb{R}\right)  $ subalgebra. By virtue of (\ref{DeltaA}), it
is then simple to verify that the variation of the canonical generators in
(\ref{deltaqchi}) becomes linear in the deviation of the fields. Therefore,
the conserved charges can be readily integrated so that, in particular, the
zero modes of the Virasoro generators read%
\begin{equation}
L_{0}^{\pm}:=Q\left(  \partial_{\pm}\right)  =\int\mathcal{L}^{\pm}d\phi\ ,
\label{L0linear}%
\end{equation}
and hence, the energy (\ref{deltaM}) is given by%
\begin{equation}
E=Q\left(  \partial_{t}\right)  =\frac{1}{l}\int\left(  \mathcal{L}%
^{+}+\mathcal{L}^{-}\right)  d\phi\ . \label{MassLinear}%
\end{equation}
It is also simple to verify that eqs. (\ref{L0linear}) and (\ref{MassLinear})
also hold for the asymptotic conditions in \cite{Theisen-HS, Campoleoni-HS}
and \cite{Henneaux-HS, GH}, for $sl\left(  N,\mathbb{R}\right)  $ and
$hs\left(  \lambda\right)  $, where it has also been shown that the algebra of
the canonical generators acquires the same central extension as the one found
by Brown and Henneaux in \cite{Brown-Henneaux} for General Relativity with
negative cosmological constant,%
\begin{equation}
c=\frac{3l}{2G}\ . \label{C-BH}%
\end{equation}

In the next section we show that, since the higher spin black hole solutions
found in \cite{GK,GKMP,CM} do not fulfill the asymptotic conditions of ref.
\cite{Henneaux-HS, Theisen-HS}, their global charges, and then their energy,
differ from eqs. (\ref{L0linear}) and (\ref{MassLinear}), respectively,
because they acquire explicit nonlinear contributions that come from the
deviation of the fields with respect to the reference background. It is also
worth pointing out that further integrability conditions that guarantee that
the variation of the energy is an exact differential are also found. This
implies that some of the integration constants appearing on the higher spin
black hole solutions considered here generically become functionally related.

\section{Ammon-Gutperle-Kraus-Perlmutter solution}

\label{AGKP}

Let us first consider the higher spin black hole solution found in
refs.\ \cite{GK,GKMP} for the case $N=3$. The gauge field can be conveniently
written as%
\begin{equation}
A^{\pm}=g_{\pm}^{-1}a^{\pm}g_{\pm}+g_{\pm}^{-1}dg_{\pm}\ , \label{A+-}%
\end{equation}
where $g_{\pm}=g_{\pm}\left(  \rho\right)  $ stand for suitable elements of
each copy of $SL\left(  3,\mathbb{R}\right)  $ that depend only on the radial
coordinate, so that%
\begin{align}
a^{\pm}  &  =\pm\left(  L_{\pm1}^{\pm}-\frac{2\pi}{k}\mathcal{L}L_{\mp1}^{\pm
}\mp\frac{\pi}{2k}\mathcal{W}W_{\mp2}^{\pm}\right)  dx^{\pm}\nonumber\\
&  +\mu\left(  W_{\pm2}^{\pm}-\frac{4\pi}{k}\mathcal{L}W_{0}^{\pm}+\frac
{4\pi^{2}}{k^{2}}\mathcal{L}^{2}W_{\mp2}^{\pm}\pm\frac{4\pi}{k}\mathcal{W}%
L_{\mp1}^{\pm}\right)  dx^{\mp}\ ,
\end{align}
correspond to the connection in the \textquotedblleft wormhole
gauge\textquotedblright. As explained in \cite{GK,GKMP}, this solution does
not fulfill the asymptotic conditions of ref. \cite{Henneaux-HS, Theisen-HS}
in eq. (\ref{DeltaA}), since the metric asymptotically approaches to that of
AdS$_{3}$, but of radius $\tilde{l}=l/2$, and moreover the deviation with
respect to the background configuration, $\Delta A^{\pm}$, possesses
additional components along $dx^{\mp}=\frac{1}{\tilde{l}}dt\mp d\phi$.

It is simple to verify that, since $g_{\pm}=g_{\pm}\left(  \rho\right)  $, the
variation of the canonical generator in eq. (\ref{deltaM}) reduces to%
\begin{equation}
\delta Q\left(  \partial_{t}\right)  =\frac{k}{2\pi}\int_{\partial\Sigma
}\left(  \left\langle a_{t}^{+}\delta a_{\phi}^{+}\right\rangle -\left\langle
a_{t}^{-}\delta a_{\phi}^{-}\right\rangle \right)  d\phi\ , \label{DeltaQ-a}%
\end{equation}
and hence, the variation of the energy, $\delta E=\delta Q\left(  \partial
_{t}\right)  $, is given by%
\begin{equation}
\delta E=\frac{8\pi}{l}\left[  \delta\mathcal{L}-\frac{32\pi}{3k}%
\delta(\mathcal{L}^{2}\mu^{2})+\mu\delta\mathcal{W}+3\mathcal{W}\delta
\mu\right]  \ . \label{DeltaM-Kraus}%
\end{equation}

Since the configuration is static, by virtue of (\ref{deltaqchi}), one obtains
that%
\begin{equation}
\delta L_{0}^{\pm}=\delta Q\left(  \partial_{\pm}\right)  =\frac{\tilde{l}}%
{2}\delta E\ . \label{DeltaL0-Kraus}%
\end{equation}
According to eq. (\ref{DeltaM-Kraus}), the higher spin black hole energy not
only has the expected linear contribution in $\delta\mathcal{L}$, but also
acquires additional terms that depend nonlinearly in the integration
constants. Note that the energy is well defined provided its variation becomes
an exact differential, so that it can be integrated. Therefore, in order to
guarantee that, the last two terms at the r.h.s. of eq. (\ref{DeltaM-Kraus})
give a nontrivial integrability condition that have to be fulfilled. This
condition then reads%
\begin{equation}
\delta^{2}E=\frac{16\pi}{l}\ \delta\mathcal{W}\wedge\delta\mu=0\ ,
\end{equation}
and as a consequence, the integration constants $\mu$ and $\mathcal{W}$ are
not generically independent, i.e., they become functionally related as%
\begin{equation}
\mu=\mathcal{F}^{\prime}\left(  \mathcal{W}\right)  \ , \label{mu(W)}%
\end{equation}
where $\mathcal{F}^{\prime}$ is the derivative of an arbitrary function
$\mathcal{F}$ that is fixed once precise boundary conditions are provided.
Hence, the energy is given by
\begin{equation}
E=\frac{8\pi}{l}\left[  \mathcal{L}-\frac{32\pi}{3k}\mu^{2}\mathcal{L}%
^{2}+3\mu\mathcal{W}-2\mathcal{F}\right]  \ , \label{Mass-Kraus}%
\end{equation}
up to an arbitrary constant without variation. Note that in the case of
$\mu=\mu_{0}$, where $\mu_{0}$ is an arbitrary constant without variation,
which corresponds to the one considered in \cite{GK,GKMP}, the function
$\mathcal{F}$ becomes fixed according to $\mathcal{F}=\mu_{0}\mathcal{W}$, so
that the energy reduces to%
\begin{equation}
E=\frac{8\pi}{l}\left[  \mathcal{L}-\frac{32\pi}{3k}\mu_{0}^{2}\mathcal{L}%
^{2}+\mu_{0}\mathcal{W}\right]  \ . \label{Energy-mu0}%
\end{equation}

It is worth pointing out that the explicit dependence of the energy in terms
of the function $\mathcal{F}$, which is precisely specified through the fixed
data at the boundary, e.g., through Dirichlet, Neumann, mixed or generic
nonlinear boundary conditions, is an effect that is known to occur when the
fields possess a relaxed asymptotic behaviour, being such that the global
charges acquire nontrivial contributions given by nonlinear terms in the
deviation of the fields with respect to the background configuration. Indeed,
this is the generic case for scalar fields with relaxed AdS asymptotics, which
has been widely discussed in Refs. \cite{HMTZ-2+1,HMTZ-Log, HMTZ-D, HM,
AM,DG0,DG1,DG2,DG3,DG4,DG5}. Further details concerning with the precise
fixing of the function $\mathcal{F}$ are discussed in section \ref{Discussion}.

\section{Castro-Hijano-Lepage-Jutier-Maloney solution}

\label{CMsect}

The second example we consider is the static higher spin black hole solution
found in \cite{CM}\footnote{As pointed out to us by an anonymous referee, this
solution should not be named \textquotedblleft higher spin black
hole\textquotedblright, in the sense that it carries a $U(1)$ spin 1 charge
instead of a higher spin charge.}, also for $N=3$. As in the previous case, it
is convenient to express the gauge field as in eq. (\ref{A+-}), where now
$g_{\pm}=e^{\pm\rho L_{0}^{\pm}}$, and%
\begin{equation}
a^{\pm}=\pm\left(  \ell_{P}L_{\pm1}^{\pm}-\mathcal{L}L_{\mp1}^{\pm}\pm\Phi
W_{0}^{\pm}\right)  dx^{\pm}+\left(  \ell_{D}W_{\pm2}^{\pm}+\mathcal{W}%
W_{\mp2}^{\pm}-QW_{0}^{\pm}\right)  dx^{\mp}\ ,
\end{equation}
with\footnote{We have chosen a different orientability as compared with the
one in \cite{CM}, i.e., $x^{+}\leftrightarrow x^{-}$. As in the previous
section, here $x^{\pm}=\frac{t}{\tilde{l}}\pm\phi$, and hereafter we will
consider the branch with $\ell_{P}$,$\ \ell_{D}\neq0$.}%
\begin{equation}
Q\ell_{P}-2\mathcal{L}\ell_{D}=0\ \ ;\ \ Q\mathcal{L}-2\mathcal{W}\ell
_{P}=0\ .
\end{equation}

It is simple to verify that this solution does not fit within the asymptotic
conditions in eq. (\ref{DeltaA}). Indeed, the asymptotic form of the metric
approaches to AdS$_{3}$ of radius $\tilde{l}=l/2$, and the deviation of the
gauge field $A^{\pm}$ also possesses additional components along $dx^{\mp}$.

The variation of the energy can then be obtained from eq. (\ref{DeltaQ-a}),
which reads%
\begin{equation}
\delta E=\delta Q\left(  \partial_{t}\right)  =\frac{1}{3G}\left[
\delta\left(  3\mathcal{L}\ell_{P}-4Q^{2}-2Q\Phi+\Phi^{2}\right)  +4\Phi\delta
Q\right]  \ . \label{DeltaM-Castro}%
\end{equation}
Therefore, as expected, the variation of the energy has a nonlinear dependence
in the integration constants. The integrability condition that comes from
(\ref{DeltaM-Castro}) is given by%
\begin{equation}
\delta^{2}E=\frac{4}{3G}\delta\Phi\wedge\delta Q=0\ ,
\end{equation}
which means that the integration constants $\Phi$ and $Q$ are functionally
related. It is convenient to express this relation as%
\begin{equation}
\Phi=\mathcal{F}^{\prime}(Q)\ , \label{F(Phi)}%
\end{equation}
for some arbitrary function $\mathcal{F}$. Hence, up to an arbitrary constant
without variation, the energy can be written as%
\begin{equation}
E=\frac{1}{G}\left[  \mathcal{L}\ell_{P}+4Q^{2}\right]  +w(Q)\ ,
\label{MassCM}%
\end{equation}
with%
\begin{equation}
w(Q):=\frac{1}{3G}\left[  (\Phi-4Q)(\Phi+4Q)-2(Q\Phi-2\mathcal{F})\right]  \ ,
\label{w}%
\end{equation}
so that%
\begin{equation}
L_{0}:=L_{0}^{\pm}=Q\left(  \partial_{\pm}\right)  =\frac{\tilde{l}}{2}%
E=\frac{l}{4}E\ . \label{Lo-CM}%
\end{equation}

\subsection{Thermodynamics}

As it was shown in \cite{CM}, requiring the holonomy around the thermal cycle
of the Euclidean solution to be trivial, allows to fix Hawking temperature
according to%
\begin{equation}
T=\frac{2}{\pi l}\sqrt{\mathcal{L}\ell_{p}+4Q^{2}}\ , \label{T-CMq}%
\end{equation}
and gives an additional condition that reads
\begin{equation}
\Phi=4Q\ . \label{phi4q}%
\end{equation}
This restricts the precise form of the function $\mathcal{F}$ in
(\ref{F(Phi)}), according to $\mathcal{F}=2Q^{2}$. As a consequence, the
function $w(Q)$ in (\ref{w}) vanishes, so that the energy becomes proportional
to the square of the temperature, i.e.,%
\begin{equation}
E=\frac{\pi^{2}l^{2}}{4G}T^{2}\ , \label{M(T)}%
\end{equation}
and then the entropy can be readily found in the canonical ensemble, $dE=TdS$,
to be given by%
\begin{equation}
S=\pi l\sqrt{\frac{E}{G}}\ . \label{S(M)}%
\end{equation}
Note that, according to eq. (\ref{Lo-CM}), the semiclassical entropy of the
higher spin black hole (\ref{S(M)}) reads%
\begin{equation}
S=4\pi\sqrt{\frac{l}{4G}L_{0}}\ , \label{S(L0)}%
\end{equation}
which exactly agrees with Cardy formula,%
\begin{equation}
S=4\pi\sqrt{\frac{c}{6}L_{0}}\ , \label{Cardy standard}%
\end{equation}
provided
\begin{equation}
c=\frac{3l}{2G}\ ,
\end{equation}
i.e., precisely the standard central charge that has been found to hold also
for higher spin gravity with asymptotically AdS$_{3}$ boundary conditions
\cite{Henneaux-HS, Theisen-HS, Campoleoni-HS, GH}. This result suggests that
the higher spin black hole found in \cite{CM} could be naturally regarded as a
large nonperturbative deviation with respect to the AdS$_{3}$ vacuum of radius
$l$.

\section{Discussion}

\label{Discussion}

The canonical formalism to compute conserved charges as surface integrals
\cite{Regge-Teitelboim} has been briefly reviewed in the case of higher spin
gravity in three dimensions, and it was applied in order to obtain the energy
of the higher spin black holes in refs. \cite{GK,GKMP} and \cite{CM}. In both
cases, it was found that the energy acquires nonlinear terms in the deviation
of the fields with respect to the reference background. This goes by hand with
non trivial functional relationships between the integration constants that
have to be fulfilled in order to ensure integrability of the charges. This
effect occurs due to the fact that these solutions possess a relaxed
asymptotically AdS behavior as compared with the ones in \cite{Henneaux-HS,
Theisen-HS, Campoleoni-HS, GH}, and hence the global charges, in particular
their energy, differ from eqs. (\ref{L0linear}) and (\ref{MassLinear}%
)\footnote{Further examples exhibiting similar features have also been
discussed in refs. \cite{HMTmore, HMTwarped} in the context of topologically
massive gravity \cite{Deser:1982vy,DeserJT,DeserCosmo}, as well as in
\cite{PTT} for BHT \textquotedblleft new\textquotedblright\ massive gravity
\cite{BHT} in vacuum.}. It is worth then pointing out that finite charges as
surface integrals that are obtained through different perturbative approaches
do not capture this effect. Indeed, although they may transform suitably under
the Virasoro symmetry, \textit{a priori}, there is no guarantee that they
reproduce the energy unless one explicitly check that they generate the time evolution.

For the specific examples considered here, some remarks are in order. In the
case of the higher spin black hole of \cite{GK,GKMP} the integrability
condition that makes the variation of the energy to be an exact differential
reduces to eq. (\ref{mu(W)}). The case $\mu=\mu_{0}$, where $\mu_{0}$ is
arbitrary and without variation is certainly one of the possibilities, and
hence along the lines of the AdS-CFT correspondence, the generic functional
relationship (\ref{mu(W)}) naturally arises in the context of multi-trace
deformations \cite{KW,W}. It is also worth mentioning that, as explained in
\cite{GK,GKMP}, for the Euclidean solution, requiring the holonomy around the
thermal cycle to be trivial not only determines the higher spin black hole
temperature, but also gives an additional condition. As a consequence, once
eq. (\ref{mu(W)}) is imposed, the energy in eq. (\ref{Mass-Kraus}) turns out
to depend on a single integration constant. Further subtleties concerning how
thermodynamics works once these results are taken into account for this and
other examples are discussed in \cite{PTT-Entropy}.

In the case of the higher spin black hole found in \cite{CM}, requiring
triviality of the holonomy around the thermal cycle singles out a unique
possibility for the functional relationship in eq. (\ref{F(Phi)}). Since the
energy becomes proportional to the square of the temperature, as in eq.
(\ref{M(T)}), the thermodynamics can be readily carried out in the canonical
ensemble. Remarkably, the semiclassical entropy of the higher spin black hole
was shown to exactly agree with Cardy formula, provided the central charge is
the one of Brown and Henneaux, which was found to hold also for higher spin
gravity with asymptotically AdS$_{3}$ boundary conditions \cite{Henneaux-HS,
Theisen-HS, Campoleoni-HS, GH}. Note that if the asymptotic conditions could
be relaxed in a consistent way with the asymptotic symmetries, the central
charge would not change, since it is determined by the the ground state
configuration. Therefore, although the higher spin black hole of \cite{CM}
asymptotically approaches to AdS$_{3}$ spacetime of radius $\tilde{l}=\frac
{l}{2}$, our result naturally suggests that it could be consistently regarded
as a large nonperturbative deviation with respect to the AdS$_{3}$ vacuum of
radius $l$. In this sense, it is worth mentioning that AdS$_{3}$ with radius
$l$ has been argued to be the only ground state for which the perturbative
spectrum of the theory could admit a unitary representation for large values
of the central charge \cite{CH-Unitarity}.

Curiously, in this sense, the usual practice that suggests the possibility of
regarding the asymptotics of the higher spin black hole as a perturbative
deviation with respect to AdS$_{3}$ of radius $\tilde{l}$ does not appear to
be an appealing one. Indeed, if this was the case, according to ref.
\cite{GKMP}, the central charge that corresponds to the ground state would be
given by $\tilde{c}=\frac{3l}{8G}$, and hence the standard form of Cardy
formula in eq. (\ref{Cardy standard}), with $c=\tilde{c}$, would fail in
reproducing its semiclassical entropy. It is also worth pointing out that in
this case, along the lines of refs. \cite{CMT1, CMT2}, Cardy formula still
would have a chance to work if it is generalized so as to admit nontrivial
lowest eigenvalues for the Virasoro operators, which would correspond to the
ones of a suitable ground state that asymptotically approaches to AdS$_{3}$ of
radius $\tilde{l}$. However, in this case, the lowest eigenvalues of the
Virasoro operators would be given by $\bar{L}_{0}^{\pm}=-\frac{l}{16G}%
<-\frac{\tilde{c}}{24}$, which manifestly violates the unitarity bound.

As an ending remark, it would be interesting to explore the possibility of
recovering the results discussed here from the dual theory at the boundary,
along the lines of \cite{H1,H2,H3,H4,H5,H6}, as well as inspecting whether
they persist for the different class of higher spin black holes found in
\cite{PK, TAN, GGR}, or for the generic solution of \cite{Banados-Theisen}.

\acknowledgments We thank H. Afshar, G. Barnich, X. Bekaert, E. Bergshoeff, N.
Boulanger, C. Bunster, A. Campoleoni, A. Castro, M. Gary, H. Gonz\'{a}lez, M.
Grigoriev, D. Grumiller, O. Hohm, C. Iazeolla, P. Kraus, S. Pfenninger, R.
Rahman, R. Rashkov, P. Sundell, M. Valenzuela, A. Waldron, J. Zanelli, and
specially to M. Henneaux, C. Mart\'{\i}nez and S. Theisen for many useful
discussions and comments. We also wish to thank the organizers of the Workshop
on Higher Spin Gravity, hosted by the Erwin Schr\"{o}dinger Institute (ESI),
during April 2012 in Vienna, for the opportunity of presenting this work. We
thank the kind hospitality at the Physique th\'{e}orique et math\'{e}matique
group of the Universit\'{e} Libre de Bruxelles, the International Solvay
Institutes, and the Max-Planck-Institut f\"{u}r Gravitationsphysik
(Albert-Einstein-Institut). This work has been partially funded by the
Fondecyt grants N${^{\circ}}$ 1130658, 1121031, 3110122, 3110141. The Centro
de Estudios Cient\'{\i}ficos (CECs) is funded by the Chilean Government
through the Centers of Excellence Base Financing Program of Conicyt.


\section{Introduction}
In this work we focus on solving optimization problems of the form
\begin{align} \label{eq:general_optimization_problem}
\underset{w \in \mathcal{W}}{\operatorname{minimize}}\ F(w) = \frac{1}{T} \sum_{t=1}^T f^t(w)
\end{align}
where each function $f^1(w), f^2(w), \dots,$ is convex over a convex set $\mathcal{W} \subseteq \mathds{R}^d$. This formulation applies widely in machine learning scenarios, where $f^t(w)$ measures the loss of model $w$ with respect to data point $t$, and $F(w)$ is the average loss over $T$ data points. In particular, we are interested in the behavior of online distributed optimization algorithms for this sort of problem as the number of data points $T$ tends to infinity. We describe a distributed algorithm which, for strongly convex functions $f^t$, converges at a rate $O\left( \frac{\log(\sqrt{n} T)}{T}\right)$. To the best of our knowledge this is the first distributed algorithm to achieve this converge rate for constrained optimization without relying on smoothness assumptions on the objective or non-trivial communication mechanisms between the nodes. The result is true both in the online and the batch optimization setting.

When faced with a non-linear convex optimization problem, gradient-based methods can be applied to find the solution. The behavior of these algorithms is well-understood in the single-processor (centralized) setting. Under the assumption that the objective is $L$-Lipschitz continuous, projected gradient descent-type algorithms converge at a rate $O(\frac{1}{\sqrt{T}})$~\cite{zinkOnlineConvexOpt,nesterovDualOpt}. This rate is achieved both in an online setting where the $f^t$'s are revealed to the algorithm sequentially and in the batch setting where all $f^t$ are known in advance. If the cost functions are also strongly convex then gradient algorithms can achieve linear rates, $O\left(\frac{1}{T}\right)$, in the batch setting \cite{largeScaleSGD} and nearly-linear rates, $O\left(\frac{\log(T)}{T}\right)$, in the online setting \cite{logRegRepeatedGames}. Under additional smoothness assumptions, such as Lipschitz continuous gradients, the same rate of convergence can also be achieved by second order methods in the online setting~\cite{LogRegretOCOot,AdaptiveOGD}, while accelerated methods can achieve a quadratic rate in the batch setting; see~\cite{TsengAccelerated} and references therein.

The aim of this work is to extend the aforementioned results to the distributed setting where a network of processors jointly optimize a similar objective. Assuming the network is arranged as an expander graph with constant spectral gap, for general convex cost functions that are only $L$-Lipschitz continuous, the rate at which existing algorithms on a network of $n$ processors will all reach the optimum value is $O(\frac{\log(T \sqrt{n})}{\sqrt{T}})$, i.e., similar to the optimal single processor algorithms up to a logarithmic factor~\cite{dualAveraging,ContrainedDistrOpt}. This is true both in a batch setting and in an online setting, even when the gradients are corrupted by noise. The technique proposed in~\cite{DekelMiniBatches} makes use of mini-batches to obtain asymptotic rates $O\left( \frac{\sqrt{\log{(n)}}}{\sqrt{n T}}\right)$ for online optimization of smooth cost functions that have Lipschitz continuous gradients corrupted by bounded variance noise, and $O\left( \frac{1}{nT}\right)$ for smooth strongly convex functions. However, this technique requires that each node exchange messages with every other node at the end of each iteration. Finally, if the objective function is strongly convex and three times differentiable, a distributed version of Nesterov's accelerated method~\cite{FastDistributedGradMethods} achieves a rate of $O\left(\frac{\log(T)}{T}\right)$ for unconstrained problems in the batch setting, but the dependence on $n$ is not characterized.

The algorithm presented in this paper achieves a rate $O\left( \frac{\log{(\sqrt{n} T )}}{T}\right)$ for strongly convex functions. Our formulation allows for convex constraints in the problem and assumes the objective function is Lipschitz continuous and strongly convex; no higher-order smoothness assumptions are made. Our algorithm works in both the online and batch setting and it scales nearly-linearly in number of iterations for network topologies with fast information diffusion. In addition, at each iteration nodes are only required to exchange messages with a subset of other nodes in the network (their neighbors).

The rest of the paper is organized as follows. Section~\ref{sec:into_convex_opt} introduces notation and formalizes the problem. Section~\ref{sec:algorithm} describes the proposed algorithm and states our main results. These results are proven in Section~\ref{sec:analysis}, and Section~\ref{sec:stochastic_opt} extends the analysis to the case where gradients are noisy. Section~\ref{sec:experiments} presents the results of numerical experiments illustrating the performance of the algorithm, and the paper concludes in Section~\ref{sec:future}.

\section{Online Convex Optimization}
\label{sec:into_convex_opt}
Consider the problem of minimizing a convex function $F(w)$ over a convex set $\mathcal{W} \subseteq \mathds{R}^d$. Of particular interest is the setting where the algorithm sequentially receives noisy samples of the (sub)gradients of $F(w)$. This setting arises in online loss minimization for machine learning when the data arrives as a steam and the (sub)gradient is evaluated using an individual data point at each step~\cite{zinkOnlineConvexOpt}. Suppose the $t$th data point $x(t) \in \mathcal{X} \subseteq \mathds{R}^d$ is drawn i.i.d.~from an unknown distribution $\mathcal{D}$, and let $f^t(w) = f(w, x(t))$ denote the loss of this data point with respect to a particular model $w$. In this setting one would like to find the model $w$ that minimizes the expected loss $\mathds{E}_{\mathcal{D}}[f(w,x)]$, possibly with the constraint that $w$ be restricted to a model space $\mathcal{W}$. Clearly, as $T \rightarrow \infty$, the objective $F(w) = \frac{1}{T} \sum_{t=1}^T f^t(w) \rightarrow \mathds{E}_{\mathcal{D}}[f(w,x)]$, and so if the data stream is finite this motivates minimizing the empirical loss $F(w)$.

An online convex optimization algorithm observes a data stream $x(1), x(2), \dots$, and sequentially chooses a sequence of models $w(1), w(2), \dots$, after each observation. Upon choosing $w(t)$, the algorithm receives a subgradient $g(t) \in \partial f^t(w(t))$. The goal is for the sequence $w(1), w(2), \dots$ to converge to a minimizer $w^*$ of $F(w)$.

The performance of  an online optimization algorithm is measured in terms of the \textit{regret}:
\begin{align}
R(T) = \sum_{t=1}^T f^t(w(t))  - \min_{w \in \mathcal{W}} \sum_{t=1}^T f^t(w).
\end{align}
The regret measures the gap between the cost accumulated by the online optimization algorithm over $T$ steps and that of a model chosen to simultaneously minimize the total regret over all $T$ cost terms. If the costs $f^t$ are allowed to be arbitrary convex functions then it can be shown that the best achievable rate for any online optimization algorithm is $\frac{R(T)}{T} = \Omega(\frac{1}{\sqrt{T}})$, and this bound is also achievable~\cite{zinkOnlineConvexOpt}. The rate can be significantly improved if the cost functions has more favourable properties.

\subsection{Assumptions}

\begin{ass} \label{ass:stronglyConvex}
We assume for the rest of the paper that each cost function $f^t(w) = f(w, x(t))$ is $\sigma$-strongly convex for all $x(t) \in \mathcal{X}$; i.e., there is a $\sigma > 0$ such that for all $\theta \in [0,1]$ and all $u,w \in \mathcal{W}$
\begin{align}
f^t(\theta u +& (1- \theta) w )  \leq  \notag  \\
&\theta f^t(u) + (1-\theta) f^t(w) - \frac{\sigma}{2} \theta (1 - \theta) \norm{u - w}^2.
\end{align}
\end{ass}

If each $f^t(w)$ is $\sigma$-strongly convex, it follows that $F(w)$ is also $\sigma$-strongly convex. Moreover, if $F(w)$ is strongly convex then it is also strictly convex, and so $F(w)$ has a unique minimizer which we denote by $w^*$.

\begin{ass} \label{ass:boundedGradients}
We also assume that the subgradients $\grad{g}(t)$ of each cost function $f^t$ are bounded by a known constant $L > 0$; i.e., $\norm{\grad{g}(t)} \leq L$ where $\norm{\cdot}$ is the ($\ell_2$) Euclidean norm.
\end{ass}

\subsection{Example: Training a Classifier}

For a specific example of this setup, consider the problem of training an SVM classifier using a hinge-loss with $\ell_2$ regularization \cite{logRegRepeatedGames}. In this case, the data stream consists of pairs $\{x(t), y(t)\}$ such that $x(t) \in \mathcal{X}$ and $y(t) \in \{-1, +1\}$. The goal is to minimize the misclassification error as measured by the $\ell_2$-regularized hinge loss. Formally, we wish to find the $w^* \in \mathcal{W} \subseteq \mathds{R}^d$ that solves
\begin{align} \label{eq:svm}
\operatorname{minimize}_{w \in \mathcal{W}} \frac{\sigma}{2} \norm{w}^2 + \frac{1}{m} \sum_{t=1}^{m} \max\{0, 1 - y(t) \langle w, x(t)\rangle\}
\end{align}
which is $\sigma$-strongly convex\footnote{Although the hinge loss itself is not strongly convex, adding a strongly convex regularizer makes the overall cost function strongly convex.}. For these types of problems, using a single-processor stochastic gradient descent algorithm, one can achieve $\frac{R(T)}{T} = O(\frac{\log{T}}{T})$\cite{logRegRepeatedGames} or $\frac{R(T)}{T} = O(\frac{1}{T})$ \cite{StochOptStrognlyConvex} by using different update schemes.

\subsection{Distributed Online Convex Optimization}

In this paper, we are interested in solving online convex optimization problems with a network of computers. The computers are organized as a network $G=(V,E)$ with $\abs{V} = n$ nodes, and messages are only exchanged between nodes connected with an edge in $E$.

\begin{ass} \label{ass:connected}
In this work we assume that $G$ is connected and undirected.
\end{ass}

Each node $i$ receives a stream of data $x_i(1), x_i(2), \dots$, similar to the serial case, and the nodes must collaborate to minimize the network-wide objective
\begin{align}
F(w) = \frac{1}{nT} \sum_{t=1}^T \sum_{i=1}^n f_i^t(w),
\end{align}
where $f_i^t(w) = f(w, x_i(t))$ is the cost incurred at processor $i$ at time $t$. In the distributed setting, the definition of regret is naturally extended to
\begin{align}
R(T) = \sum_{t=1}^T \sum_{i=1}^n f(w_i(t), x_i(t))  - \min_{w \in \mathcal{W}} \sum_{t=1}^T \sum_{i=1}^n f(w, x_i(t)).
\end{align}

For general convex cost functions, the distributed algorithm proposed in~\cite{dualAveraging} has been proven to have an average regret that decreases at a rate $\sqrt{T}$, similar to the serial case, and this result holds even when the algorithm receives noisy, unbiased, observations of the true subgradients at each step. In the next section, we present a distributed algorithm that achieves a nearly-linear rate of decrease of the average regret (up to a logarithmic factor) when the cost functions are strongly convex.

\section{Algorithm} \label{sec:algorithm}

Nodes must collaborate to solve the distributed online convex optimization problem described in the previous section. To that end, the network is endowed with a $n \times n$ consensus matrix $P$ which respects the structure of $G$, in the sense that $[P]_{ji} = 0$ if $(i,j) \notin E$. We assume that $P$ is doubly stochastic, although generalizations to the case where $P$ is row stochastic or column stochastic (but not both) are also possible \cite{TsianosCDC2012,TsianosACC2012}.

A detailed description of the proposed algorithm, \emph{distributed online gradient descent} (DOGD), is given in Algorithm~\ref{alg:dogd}. In the algorithm, each node performs a total of $T$ updates. One update involves processing a single data point $x_i(t)$ at each processor. The updates are performed over $k$ rounds, and $T_s$ updates are performed in round $s \leq k $. The main steps within each round (lines 9--11) involve updating an accumulated gradient variable, $z_i^k(t)$, by simultaneously incorporating the information received from neighboring nodes and taking a local gradient-descent like step. The accumulated gradient is projected onto the constraint set to obtain $w_i^k(t)$, where
\begin{align}
\proj{z} = \argmin{w \in \mathcal{W}} \norm{w - z}
\end{align}
denotes the Euclidean projection of $z$ onto $\mathcal{W}$, and then this projected value is merged into a running average $\hat{w}_i(r)$. The step size parameter $a_k$ remains constant within each round, and the step size is reduced by half at the end of each round. The number of updates per round doubles from one round to the next.

Note that the algorithm proposed here differs from the distributed dual averaging algorithm described in~\cite{dualAveraging}, where a proximal projection is used rather than the Euclidean projection. Also, in contrast to the distributed subgradient algorithms described in~\cite{distrStochSubgrOpt}, DOGD maintains an accumulated gradient variable in $z_i^k(t+1)$ which is updated using $\{z_j^k(t)\}$ as opposed to the primal feasible variables $\{w_j^k(t)\}$. Finally, key to achieving fast convergence is the exponential decrease of the learning rate after performing an exponentially increasing number of gradient steps together with a proper initialization of the learning rate.

The next section provides theoretical guarantees on the performance of DOGD.

\begin{algorithm}[t]
\caption{DOGD}
\label{alg:dogd}
\begin{algorithmic}[1]
\State $\operatorname{Initialize:} T_1 =  \left\lceil \frac{2 }{\sigma} \right\rceil, a_1 = 1, k=1, z_i^1(1) = w_i^1(1) = 0$
\State
\While{$\sum_{s=1}^k T_s \leq T$} \Comment{Each node $i$ repeats}
\For{$t=1$ to $T_k$}
\State Send/receive $z_i^k(t)$ and $z_j^k(t)$ to/from neighbors
\State Obtain next subgradient $\grad{g}_i(t) \in \partial_w f_i^t(w_i^k(t))$
\State $z_i^k(t+1) = \sum_{j=1}^n p_{ij} z_j^k(t) - a_k \grad{g}_i(t)$
\State $w_i^k(t+1) = \proj{z_i^k(t+1)}$
\EndFor
\State $w_i^{k+1}(1) = w_i^k(T_k)$
\State $z_i^{k+1}(1) = w_i^{k+1}(1)$
\State $\hat{w}_i^{k+1} = \frac{1}{T_k} \sum_{t=1}^{T_k} w_i^k(t) $
\State
\State $T_{k+1} \leftarrow 2  T_k$
\State $a_{k+1} \leftarrow  \frac{a_k}{2}$
\State $k = k + 1$
\EndWhile
\end{algorithmic}
\end{algorithm}

\begin{comment}
\begin{algorithm}[t]
\caption{DOGD}
\label{alg:dogd}
\begin{algorithmic}[1]
\State $\operatorname{Initialize:} T_1 =  \left\lceil \frac{2 n^2}{\sigma} \right\rceil, a_1 = \frac{1}{n}, k=1, r = 1, z_i^1(1) = 0,$
\State $\ \ \ \ \ \ \ \ \ \ \ \  \hat{w}_i^1 = \hat{w}_i(1) =  w_i^k(1) \in \mathds{R}^d$
\State
\While{$\sum_{s=1}^k T_s \leq T$} \Comment{Each node $i$ repeats}
\For{$t=1$ to $T_k$}
\State $r= r + 1$
\State Send/receive $z_i^k(t)$ and $z_j^k(t)$ to/from neighbors
\State Obtain next subgradient $\grad{g}_i(t) \in \partial_w f_i^t(w_i^k(t))$
\State $z_i^k(t+1) = \sum_{j=1}^n p_{ij} z_j^k(t) - a_k \grad{g}_i(t)$
\State $w_i^k(t+1) = \proj{z_i^k(t+1)}$
\State $\hat{w}_i(r) = \left( (r-1) \cdot \hat{w}_i(r-1)  + w_i^k(t+1)\right) / r$
\EndFor
\State $w_i^{k+1}(1) = w_i^k(T_k)$
\State $z_i^{k+1}(1) = z_i^k(T_k)$
\State $\hat{w}_i^{k+1} = \hat{w}_i(r)$
\State
\State $T_{k+1} \leftarrow 2  T_k$
\State $a_{k+1} \leftarrow  \frac{a_k}{2}$
\State $k = k + 1$
\EndWhile
\end{algorithmic}
\end{algorithm}
\end{comment}

\section{Convergence Analysis} \label{sec:analysis}

Our main convergence result, stated below, guarantees that the average regret decreases at a rate which is nearly linear.

\begin{thm} \label{thm:dogd_convergence}
Let Assumptions~\ref{ass:stronglyConvex}--\ref{ass:connected} hold and suppose that the consensus matrix $P$ is doubly stochastic with constant $\lambda_2$. Let $w^*$ be the minimizer of $F(w)$. Then the sequence $\{\hat{w}_i^k\}$ produced by nodes running DOGD to minimize $F(w)$ obeys
\begin{align}
F(\hat{w}_i^{k+1}) - F(w^*) = O\left( \frac{\log{(\sqrt{n} T )}}{T} \right),
\end{align}
where $k = \lfloor \log_2(T/2 + 1)\rfloor$ is the number of rounds executed during a total of $T$ gradient steps per node, and $\hat{w}_i^{k}$ is the running average maintained locally at each node.
\end{thm}

\textit{Remark 1:} We state the result for the case where $\lambda_2$ is constant. This is the case when $G$ is, e.g., a complete graph or an expander graph \cite{kRegExpanders}. For other graph topologies where $\lambda_2$ shrinks with $n$ and consensus does not converge fast, the convergence rate dependence on $n$ is going to be worse due to a factor $1 - \sqrt{\lambda_2}$ in the denominator; see the proof of Theorem~\ref{thm:dogd_convergence} below for the precise dependence on the spectral gap $1 - \sqrt{\lambda_2}$.

\textit{Remark 2:} The theorem characterizes performance of the online algorithm DOGD, where the data and cost functions $f^t_i$ are processed sequentially at each node in order to minimize an objective of the form
\begin{align}
F(w) = \frac{1}{n} \sum_{i=1}^n \frac{1}{T} \sum_{t=1}^T f_i^t(w).
\end{align}
However, as pointed out in \cite{logRegRepeatedGames}, if the entire dataset is available in advance, we can use the same scheme to do batch minimization by effectively setting $f_i^t(w) = f_i^1(w)$, where $f_i^1(w)$ is the objective function accounting for the entire dataset available to node $i$. Thus, the same result holds immediately for a batch version of DOGD.

The remainder of this section is devoted to the proof of Theorem~\ref{thm:dogd_convergence}. Our analysis follows arguments that can be found in \cite{zinkOnlineConvexOpt, StochOptStrognlyConvex,dualAveraging} and references therein. We first state and prove some intermediate results.

\subsection{Properties of Strongly Convex Functions}

Recall the definition of $\sigma$-strong convexity given in Assumption~\ref{ass:stronglyConvex}. A direct consequence of this definition is that if $F(w)$ is $\sigma$-strongly convex then
\begin{align}
F(w) - F(w^*) \geq \frac{\sigma}{2} \norm{w - w^*}^2.
\end{align}

Strong convexity can be combined with the assumptions above to upper bound the difference $F(w)-F(w^*)$ for an arbitrary point $w \in \mathcal{W}$.

\begin{lemma} \label{lem:startingPoint}
Let $w^*$ be the minimizer of $F(w)$. For all $w \in \mathcal{W}$, we have $F(w) - F(w^*) \leq \frac{2 L^2}{\sigma}$.
\end{lemma}
\begin{proof}
For any subgradient $\grad{g}$ of $F$ at $w$, by convexity we know that $F(w) - F(w^*) \leq \langle \grad{g}, w - w^* \rangle$. It follows from Assumption~\ref{ass:boundedGradients} that $F(w) - F(w^*) \leq L \norm{w- w^*} $. Furthermore, from Assumption~\ref{ass:stronglyConvex}, we obtain that $\frac{\sigma}{2} \norm{w - w^*}^2 \leq L \norm{w - w^*}$ or $\norm{w - w^*} \leq \frac{2 L}{ \sigma}$. As a result, $F(w) - F(w^*) \leq \frac{2 L^2}{\sigma}$.
\end{proof}

\subsection{The Lazy Projection Algorithm}

The analysis of DOGD below involves showing that the average state, $\frac{1}{n}\sum_{i=1}^n w_i^k(t)$, evolves according to the so-called (single processor) \textit{lazy projection} algorithm~\cite{zinkOnlineConvexOpt}, which we discuss next. The lazy projection algorithm is an online convex optimization scheme for the serial problem discussed at the beginning of Section~\ref{sec:into_convex_opt}. A single processor sequentially chooses a new variable $w(t)$ and receives a subgradient $g(t)$ of $f(w(t), x(t))$. The algorithm chooses $w(t+1)$ by repeating the steps
\begin{align}
z(t+1) = & z(t) - a \grad{g}(t) \label{eqn:lazyProjection1} \\
w(t+1) = & \proj{z(t+1)} \label{eqn:lazyProjection2}.
\end{align}
By unwrapping the recursive form of \eqref{eqn:lazyProjection1}, we get
\begin{align}
z(t+1) = -a \sum_{s=1}^t g(t) + z(1). \label{eqn:lazyProjectionUnwrapped}
\end{align}

The following is a typical result for subgradient descent-style algorithms, and is useful towards eventually characterizing how the regret accumulates. Its proof can be found in the appendix of the extended version of~\cite{zinkOnlineConvexOpt}.

\begin{thm}[Zinkevich~\cite{zinkOnlineConvexOpt}] \label{thm:zink}
Let $w(1) \in \mathcal{W}$, let $a > 0$, and set $z(1) = w(1)$. After $T$ rounds of the serial lazy projection algorithm \eqref{eqn:lazyProjection1}--\eqref{eqn:lazyProjection2}, we have
\begin{align}
\sum_{t=1}^T \langle \grad{g}(t), w(t) - w^* \rangle \leq \frac{\norm{w(1) - w^*}^2}{2 a} + \frac{T a L^2}{2}.
\end{align}
\end{thm}
Theorem \ref{thm:zink} immediately yields the same bound for the regret of lazy projection \cite{zinkOnlineConvexOpt}.

\subsection{Evolution of Network-Average Quantities in DOGD}

We turn our attention to Algorithm \ref{alg:dogd}. A standard approach to studying convergence of distributed optimization algorithms, such as DOGD, is to keep track of the discrepancy between every node's state and an average state sequence defined as
\begin{align}
\overline{z}^k(t) = \frac{1}{n} \sum_{i=1}^n z_i^k(t) \quad \text{and} \quad \overline{w}^k(t) = \proj{\overline{z}^k(t)}.
\end{align}
Observe that $\overline{z}^k(t)$ evolves in a simple recursive manner,
\begin{align}
\overline{z}^k(t+1) = &\frac{1}{n} \sum_{i=1}^n z_i^k(t+1) \\
= & \frac{1}{n} \sum_{i=1}^n \left[ \sum_{j=1}^n p_{ij} z_j^k(t) - a_k \grad{g}_i(t) \right] \\
= & \frac{1}{n} \sum_{j=1}^n z_j^k(t) \sum_{i=1}^n  p_{ij} - \frac{ a_k}{n} \sum_{i=1}^n \grad{g}_i(t) \\
= & \overline{z}(t) - \frac{ a_k}{n} \sum_{i=1}^n \grad{g}_i(t)  \label{eq:doubly_stoch_P}\\
= & -a_k \sum_{s=1}^t \frac{1}{n} \sum_{i=1}^n \grad{g}_i(s) + \frac{1}{n}\sum_{i=1}^n z_i^k(1) \label{eq:zbar}
\end{align}
where equation \eqref{eq:doubly_stoch_P} holds since $P$ is doubly stochastic. Notice (cf.~eqn.~\eqref{eqn:lazyProjectionUnwrapped}) that the states $\{\overline{z}^k(t), \overline{w}^k(t)\}$ evolve according to the lazy projection algorithm with gradients $\overline{g}(t)= \frac{1}{n}  \sum_{i=1}^n \grad{g}_i(t) $ and learning rate $a_k$.
In the sequel, we will also use an analytic expression for $z_i^k(t)$ derived by back substituting in its recursive update equation. After some algebraic manipulation, we obtain
\begin{align}
z_i^k(t) = & - a_k \sum_{s=1}^{t-1} \sum_{j=1}^n \left[P^{t-s+1}\right]_{ij} \grad{g}_j(s-1) - a_k \grad{g}_i(t-1) \nonumber \\
& + \sum_{j=1}^n [P^t]_{ij} z_j^k(1), \label{eqn:DOGD_unwrapped}
\end{align}
and since the projection in non-expansive and $z_i^1(1) = 0, \forall i$,
\begin{align}
\norm{z_i^{k+1}(1)}= & \norm{w_i^{k+1}(1)} = \norm{w_i^k(T_k)} = \norm{\proj{z_i^k(T_k)}}   \\
\leq &\norm{z_i^{k}(T_k)} \\
 \leq & \norm{ - a_{k} \sum_{t=1}^{T_{k}-1} \sum_{i=1}^n  \left[ P^{T_k - s + 1}\right]_{ij} g_i(s-1)} \nonumber \\
& + \norm{-a_k g_i(T_k - 1)} + \sum_{j=1}^n \left[P^{T_k} \right]_{ij} \norm{z_j^k(1) }  \\
\leq & a_k T_k L + \sum_{j=1}^n \left[P^{T_k} \right]_{ij} \norm{z_j^k(1) } \\
\leq & \cdots \\
\leq & L \sum_{s=1}^{k} a_{s} T_{s}. \label{eq:znorm_bound}
\end{align}

\subsection{Analysis of One Round of DOGD}

Next, we focus on bounding the amount of regret accumulated during the $k$th round of DOGD (lines 5--12 of Algorithm~1) during which the learning rate remains fixed at $a_k$.
Using Assumptions~\ref{ass:stronglyConvex}, \ref{ass:boundedGradients}, and the triangle inequality we have that
\begin{align}
\sum_{t=1}^{T_k} & [ F(w_i^{k}(t)) -   F(w^*)] \notag \\
= &  \sum_{t=1}^{T_k}\left[F\left(\overline{w}^k(t) \right) - F(w^*)  + F(w_i^{k}(t)) - F\left( \overline{w}^k(t) \right) \right]  \\
\leq &   \sum_{t=1}^{T_k} \left[ F( \overline{w}^k(t) ) - F(w^*)  + L\norm{  w_i^{k}(t) - \overline{w}^k(t) } \right]  \\
\leq & \sum_{t=1}^{T_k}  \frac{1}{n} \sum_{i=1}^n  \left[ f_i(w_i^k(t)) - f_i(w^*) \right]  \notag \\
& + \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n  \left[ f_i(\overline{w}^k(t))-  f_i(w_i^k(t)) \right]  \notag \\
& + \sum_{t=1}^{T_k} L \norm{w_i^k(t) - \overline{w}^k(t)} \\
 \leq  &  \underbrace{\sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle g_i(t), w_i^k(t) - w^*\rangle}_{A_1}   \notag \\
& + \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n L \norm{\overline{w}^k(t) -  w_i^k(t)}  \notag \\
& + \sum_{t=1}^{T_k} L \norm{w_i^k(t) - \overline{w}^k(t)}.
\end{align}
For the first summand we have
\begin{align}
A_1 =  &\sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle g_i(t), w_i^k(t) - w^*\rangle \\
 \leq & \sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle \grad{g}_i(t) , \overline{w}^k(t) - w^*\rangle  \notag \\
 & +    \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle \grad{g}_i(t) , w_i^k(t) - \overline{w}^k(t)\rangle  \\
  \leq & \underbrace{\sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle \grad{g}_i(t) , \overline{w}^k(t) - w^*\rangle}_{A_2}   \notag \\
 & +    \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n L \norm{w_i^k(t) - \overline{w}^k(t)}. \label{eq:optimization_error_term}
\end{align}
\begin{comment}
For the first summand in the last inequality we introduce the discrepancy between the true and the noisy gradient as follows:
\begin{align}
 \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle g_i(t), w_i(t) - & w^*\rangle  \leq  \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle \grad{g}_i(t) , w_i(t) - w^*\rangle  \notag \\
+ & \sum_{t=1}^{T_k}  \frac{1}{n}\sum_{i=1}^n \langle \grad{g}_i(t) - \grad{g}_i(t), w_i(t) - w^*\rangle  \\
 \leq &  \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle \grad{g}_i(t) , y(t) - w^*\rangle \notag \\
+ &   \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle \grad{g}_i(t) , w_i(t) - y(t)\rangle \notag \\
+ & \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle \grad{g}_i(t) - \grad{g}_i(t), w_i(t) - w^*\rangle \label{eq:optimization_error_term}
\end{align}
\end{comment}

To bound term $A_2$ we invoke Theorem \ref{thm:zink} for the average sequences $\{\overline{w}^k(t)\}$ and $\{\overline{z}^k(t)\}$.
\begin{align}
A_2  = & \sum_{t=1}^{T_k} \frac{1}{n} \sum_{i=1}^n \langle  \grad{g}_i(t) , \overline{w}^k(t) - w^*\rangle \label{eq:bound_starting_point} \\
 = & \sum_{t=1}^{T_k}  \Big\langle \frac{1}{n} \sum_{i=1}^n \grad{g}_i(t) , \proj{ \overline{z}^k(t)}  - w^* \Big\rangle \\
  = & \sum_{t=1}^{T_k}  \Big\langle \overline{\grad{g}}(t) , \proj{ \overline{z}^k(t)}  - w^* \Big\rangle \\
\leq & \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k \norm{\frac{1}{n} \sum_{i=1}^n \grad{g}_i(t)}^2 }{2} \\
= &  \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k L^2 }{2}.
\end{align}
Collecting now all the partial results and bounds, so far we have shown that
\begin{align}
\sum_{t=1}^{T_k}  [ F(w_i^{k}(t)) & -  F(w^*) ]\leq  \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k L^2 }{2} \notag \\
 & +\sum_{t=1}^{T_k} \frac{2}{n}  \sum_{i=1}^n L  \norm{w_i^k(t) - \overline{w}^k(t)}  \notag \\
& + \sum_{t=1}^{T_k} L\norm{w_i^k(t) - \overline{w}^k(t)} .
\end{align}
and since the projection operator is non-expansive, we have
\begin{align}
\sum_{t=1}^{T_k}  [ F(w_i^{k}(t)) & -  F(w^*) ] \leq  \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k L^2 }{2} \nonumber \\
 & +\sum_{t=1}^{T_k} \frac{2}{n}  \sum_{i=1}^n L \norm{z_i^k(t) - \overline{z}^k(t)}  \label{eqn:oneRoundBound}  \\
& + \sum_{t=1}^{T_k} L  \norm{z_i^k(t) - \overline{z}^k(t)} . \nonumber
\end{align}
The first two terms are standard for subgradient algorithms using a constant step size. The last two terms depend on the error between each node's iterate $z_i^k(t)$ and the network-wide average $\overline{z}^k(t)$, which we bound next.

\subsection{Bounding the Network Error}
What remains is to bound the term $\norm{z_i^k(t) - \overline{z}^k(t)}$ which describes an error induced by the network since the different nodes do not agree on the direction towards the optimum. By recalling that $P$ is doubly stochastic and manipulating the recursive expressions \eqref{eqn:DOGD_unwrapped} and \eqref{eq:zbar} for $z_i(t)$ and $\overline{z}^k(t)$ using arguments similar to those in~\cite{dualAveraging,TsianosACC2012}, we obtain the bound,
\begin{align}
\norm{z_i^k(t) - \overline{z}^k(t)} \leq & a_k L \sum_{s=1}^{t-1} \sum_{j=1}^n  \abs{ \frac{1}{n} \vc{1}^{T} - \left[ P^{t-s-1}\right]_{ij}}_1 + 2 a_k L \notag \\
& + \sum_{j=1}^n \abs{ \frac{1}{n} - [P^t]_{ij} } \norm{ z_j^k(1)} \\
= & a_k L \sum_{s=1}^{t-1} \norm{\frac{1}{n} \vc{1}^{T} - \left[ P^{t-s-1}\right]_{i,:}}_1 + 2 a_k L \notag \\
& + \sum_{j=1}^n \abs{ \frac{1}{n} - [P^t]_{ij} } \norm{ z_j^k(1)}.
\end{align}
The $\ell_1$ norm can be bounded using Lemma~\ref{lem:P_tv_convergence}, which is stated and proven in the Appendix, and using \eqref{eq:znorm_bound} we arrive at
\begin{align}
\norm{z_i^k(t) - \overline{z}^k(t)} \leq &2 a_k L \frac{\log{(T_k \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 3 a_k L   + \frac{L \sum_{s=1}^{k-1} a_{s} T_{s} }{T_k}
\end{align}
where $\lambda_2$ is the second largest eigenvalue of $P$. Using this bound in equation~\eqref{eqn:oneRoundBound},  along with the fact that $F(w)$ is convex, we conclude that
\begin{align}
F(\hat{w}_i^{k+1}) - F(w^*)  = & F\left(\frac{1}{T_k} \sum_{t=1}^{T_k} w_i^{k}(t) \right) - F(w^*)\\
\leq & \frac{1}{T_k} \sum_{t=1}^{T_k} \left[ F( w_i^{k}(t) ) - F(w^*) \right] \\
 \leq &  \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k T_k} + \frac{ a_k L^2 }{2} \notag \\
& + L^2 a_k \left[ 6 \frac{\log{(T_k \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 9 \right] \notag \\
& + \frac{3 L^2 \sum_{s=1}^{k-1} a_{s} T_{s} }{T_k},
\end{align}
where $\overline{w}^k(1) = \proj{\frac{1}{n} \sum_{i=1}^{n} z_i^k(1) }$.

\subsection{Analysis of DOGD over Multiple Rounds}

As our last intermediate step, we must control the learning rate and update of $T_k$ from round-to-round to ensure linear convergence of the error. From strong convexity of $F$ we have
\begin{align}
\norm{\overline{w}^k(1) - w^*}^2 \leq  2 \frac{ F(\overline{w}^k(1)) - F(w^*)}{\sigma}
\end{align}
and thus
\begin{align}
F(\hat{w}_i^{k+1}) & - F(w^*)  \leq   \frac{ F(\overline{w}^k(1)) - F(w^*)}{\sigma a_k T_k} \notag \\
&  + \frac{L^2 a_k}{2} \left[ 12 \frac{\log{(T_k \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 19\right]  \notag \\
& + \frac{3 L^2 \sum_{s=1}^{k-1} a_{s} T_{s} }{T_k}\label{eq:Fwhat_bound}.
\end{align}
Now, from Theorem $3$ in \cite{zinkOnlineConvexOpt} which is a direct consequence of Theorem \ref{thm:zink} for the average sequence $\overline{w}$ viewed as a single processor lazy projection algorithm, we have that after executing $T_{k-1}$ gradient steps in round $k-1$,
\begin{align}
 F(\overline{w}^k(1)) - F(w^*) \leq \frac{\norm{\overline{w}^{k-1}(1) - w^*}^2}{2 a_{k-1} T_{k-1}} + \frac{ a_{k-1} L^2}{2}
\end{align}
and by repeatedly using strong convexity and  Theorem \ref{thm:zink} we see that
\begin{align}
 F(\overline{w}^k(1)) - F(w^*) \leq & \frac{F(\overline{w}^{k-1}(1)) - F(w^*)}{\sigma a_{k-1} T_{k-1}} + \frac{ a_{k-1} L^2}{2} \\
 \leq & \cdots \\
 \leq & \frac{F(\overline{w}^{1}(1)) - F(w^*)}{\prod_{j=0}^{k-1} (\sigma a_{k-j} T_{k-j})} \notag \\
 & + \sum_{j=1}^{k-1} \frac{a_{k-j} L^2}{2 \prod_{s=1}^{j-1} (\sigma a_{k-s} T_{k-s})} \label{eq:Fwbar_bound}.
\end{align}
Now, let us fix positive integers $b$ and $c$, and suppose we use the following rules to determine the step size and number of updates performed within each round:
\begin{align}
a_k = &\frac{a_{k-1}}{b} = \cdots = \frac{a_1}{b^{k-1}} \\
T_k = & c T_{k-1} = \cdots = c^{k-1} T_1.
\end{align}
Combining \eqref{eq:Fwbar_bound} with \eqref{eq:Fwhat_bound} and invoking Lemma \ref{lem:startingPoint}, we have
\begin{align}
F(\hat{w}_i^{k+1}) & - F(w^*)  \leq  \frac{2 L^2}{\sigma \prod_{j=0}^{k-1} \left( \sigma a_1 T_1 \left( \frac{c}{b} \right)^{k-j-1} \right)}  \notag \\
& + \sum_{j=1}^{k-1} \frac{a_{1} L^2}{2 b^{k-j-1}   \prod_{s=0}^{j-1} \left(\sigma a_{1} T_{1} \left( \frac{c}{b} \right)^{k-s-1}  \right)} \notag \\
& +  \frac{L^2 a_1}{2 b^{k-1}} \left[ 12 \frac{\log{(T_1 c^{k-1} \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 19\right] \notag \\
& + \frac{3L^2 \sum_{s=1}^{k-1} a_1 T_1 \left( \frac{c}{b}\right)^{s-1}  }{T_1 c^{k-1}}.
\end{align}
To ensure convergence to zero, we need $c \geq b$ and  $\sigma a_1 T_1 > 1$ or $a_1 > \frac{1}{T_1 \sigma}$. Given these restrictions, let us make the choices
\begin{align}
a_1 = 1,\ \ T_1 = \left\lceil \frac{2 }{\sigma} \right\rceil ,\ \  c = b = 2.
\end{align}
To simplify the exposition, let us assume that $T_1 = \frac{2}{\sigma}$ is an integer. Using the selected values, we obtain
\begin{align}
F(\hat{w}_i^{k+1}) & - F(w^*)  \leq  \frac{2 L^2}{\sigma \prod_{j=0}^{k-1} \left( 2  \left( \frac{2}{2} \right)^{k-j-1} \right)} \notag \\
& + \sum_{j=1}^{k-1} \frac{L^2}{ \cdot 2 \cdot  2^{k-j-1}   \prod_{s=0}^{j-1} \left(2   \left( \frac{2}{2} \right)^{k-s-1}  \right)} \notag \\
& +  \frac{L^2 }{2 \cdot 2^{k-1}} \left[ 12 \frac{\log{(\frac{2 }{\sigma} \cdot  2^{k-1} \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 19\right] \notag \\
& + \frac{3L^2    \sum_{s=1}^{k-1}  \left( \frac{2}{2}\right)^{s-1}  }{ 2^{k-1}} \\
\leq  & \frac{2 L^2}{\sigma 2^k  } + \sum_{j=1}^{k-1} \frac{L^2}{ 2^{k-j}  2^j  } \notag \\
& +  \frac{L^2 }{2^{k}} \left[ 12 \frac{\log{( \frac{ 2^{k} \sqrt{n} }{\sigma})}}{1 - \sqrt{\lambda_2}} + 19\right]  + \frac{3L^2   (k-1) }{ 2^{k-1}} \\
\leq  & \frac{2 L^2}{\sigma 2^k } + \frac{L^2 (k-1)}{ 2^{k} }\notag \\
& +  \frac{L^2 }{ 2^{k}} \left[ 12 \frac{\log{(\frac{ 2^{k} \sqrt{n} }{\sigma})}}{1 - \sqrt{\lambda_2}} + 19\right]  + \frac{6L^2   (k-1) }{ 2^{k}} \\
\leq  & \frac{2 L^2}{\sigma 2^k } + \frac{L^2 (k-1)}{ 2^{k} }\notag \\
& +  \frac{L^2 }{2^{k}} \left[ 12 \frac{\log{(\frac{ 2^{k} \sqrt{n} }{\sigma})}}{1 - \sqrt{\lambda_2}} + 19\right]  + \frac{6L^2   (k-1) }{ 2^{k}}.
\end{align}
Finally, we have all we need to complete the analysis of Algorithm \ref{alg:dogd}.

\subsection{Proof of Theorem~\ref{thm:dogd_convergence}}

Suppose we run  Algorithm \ref{alg:dogd} for $T$ total steps at each node. This allows for $\tilde{k}$ rounds, where $\tilde{k}$ is determined by solving
\begin{align}
\sum_{i=1}^{\tilde{k}} T_i \leq T \Longleftrightarrow \sum_{i=1}^{\tilde{k}} 2 \cdot 2^i \leq T \Longleftrightarrow \tilde{k} \leq \log_2{\left( \frac{T}{2} + 1\right)}.
\end{align}
Using this value for $k$ we see that
\begin{align}
F(\hat{w}_i^{\tilde{k}+1}) & - F(w^*) \leq   \frac{L^2}{\sigma } 2^{\tilde{k}}  + \frac{L^2 (\tilde{k}-1)}{ 2^{\tilde{k}}} \notag \\
& +  \frac{L^2 }{ 2^{\tilde{k}}} \left[ 12 \frac{\log{( \frac{ 2^{\tilde{k}}  \sqrt{n} }{\sigma})}}{1 - \sqrt{\lambda_2}} + 19\right]  + \frac{6L^2   (\tilde{k}-1) }{  2^{\tilde{k}}} \\
\leq & \frac{L^2}{\sigma  \left( \frac{T}{2} + 1\right) }    + \frac{L^2 (\log_2 \left( \frac{T}{2} + 1\right)-1)}{\left( \frac{T}{2} + 1\right) } \notag \\
& +  \frac{ L^2 }{\left( \frac{T}{2} + 1\right)} \left[ 12 \frac{\log{\left( \frac{ \left( \frac{T}{2} + 1\right) \sqrt{n} }{\sigma}\right)}}{1 - \sqrt{\lambda_2}} + 19\right]  \notag \\
& + \frac{6L^2   (\left( \frac{T}{2} + 1\right)-1) }{\left( \frac{T}{2} + 1\right)} \notag \\
= & O\left(  \frac{ \log{(\sqrt{n} T)}}{ T (1 - \sqrt{\lambda_2})}\right) =  O\left( \frac{\log(\sqrt{n} T)}{T} \right),
\end{align}
when $\lambda_2$ is constant and does not scale with $n$, and this concludes the proof of Theorem~\ref{thm:dogd_convergence}.

\section{Extension to Stochastic Optimization}
\label{sec:stochastic_opt}
The proof presented in the previous section can easily be extended to the case where each node receives a random estimate $\hat{g}(t)$ of the gradient, satisfying $\mathds{E}[\hat{g}(t)] = g(t)$, instead of receiving $g(t)$ directly. We assume that noisy gradients still have bounded variance i.e., $\mathds{E}[ \norm{\hat{g}_i(t)}^2 ] \leq L^2$. In this setting, instead of equation \eqref{eq:bound_starting_point}, we have
\begin{align}
A_2 = & \sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle g_i(t), \overline{w}^k(t) - w^*\rangle \\
= & \sum_{t=1}^{T_k}  \langle \frac{1}{n}  \sum_{i=1}^n \hat{g}_i(t), \overline{w}^k(t) - w^*\rangle \notag \\
& + \sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle g_i(t) - \hat{g}_i(t), \overline{w}^k(t) - w^*\rangle.
\end{align}
However, the proof of Theorem~\ref{thm:zink} does not depend on the gradients being correct; rather, it holds for noisy gradients $\hat{g}_(t)$  as well. Moreover, we have $\mathds{E}[\norm{ \hat{g}_i(t)}] \leq L$, and by H\"{o}lder's inequality $\mathds{E}[ \norm{\hat{g}_i(t)} \norm{\hat{g}_j(t)} ] \leq  L^2$. Thus,
\begin{align}
\mathds{E} \left[ \norm{ \frac{1}{n} \sum_{i=1}^n \hat{g}_i(t) } \right] \leq \frac{1}{n^2} \sum_{i,j = 1}^n \mathds{E}[ \norm{\hat{g}_i(t)} \norm{\hat{g}_j(t)} ] \leq L^2.
\end{align}
Thus, invoking Theorem \ref{thm:zink},  if the new data and thus the subgradients are independent of the past, and since $\mathds{E}[\hat{g}_i(t)] = g_i(t)$, we have
\begin{align}
\mathds{E}[ A_2]  \leq & \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k L^2 }{2} \notag \\
& +\mathds{E}[\sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle g_i(t) -  \hat{g}_i(t), \overline{w}^k(t) - w^*\rangle ]  \\
= & \frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k L^2 }{2} \notag \\
&+ \sum_{t=1}^{T_k} \frac{1}{n}  \sum_{i=1}^n \langle \mathds{E} \left[ g_i(t) - \hat{g}_i(t) \right], \overline{w}^k(t) - w^*\rangle  \\
 = &\frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k} + \frac{{T_k} a_k L^2 }{2}.
\end{align}
Furthermore, the network error bound holds in expectation as well, i.e.,
\begin{align}
\mathds{E}[\norm{\overline{w}^k(t) - w_i^k(t)}& ] \leq  \mathds{E}[\norm{\overline{z}^k(t) - z_i^k(t)}] \notag \\
\leq & 2 a_k L \frac{\log{(T_k \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 3 a_k L  + \frac{L \sum_{s=1}^{k-1} a_s T_s}{T_k}
\end{align}
Collecting all these observations we have shown that, in expectation,
\begin{align}
\mathds{E}\left[ F(\hat{w}_i^{k+1}) - F(w^*) \right]  \leq &\frac{\norm{\overline{w}^k(1) - w^*}^2}{2 a_k T_k} + \frac{ a_k L^2 }{2} \notag \\
& + L^2 a_k \left[ 6 \frac{\log{(T_k \sqrt{n})}}{1 - \sqrt{\lambda_2}} + 9 \right] \notag \\
& + \frac{3L^2  \sum_{s=1}^{k-1} a_s T_s}{T_k}
\end{align}
which, after using the update rules for $a_k$ and $T_k$, is exactly the same rate as before. We note however that there may still be room for improvement in the distributed stochastic optimization setting since \cite{StochOptStrognlyConvex} describes a single-processor algorithm that converges at a rate $O\left( \frac{1}{T} \right)$.

\section{Simulation} \label{sec:experiments}

To illustrate the performance of DOGD we simulate online training of a classifier by solving the problem \eqref{eq:svm} using a network of $10$ nodes arranged as a random geometric graph. Each node is given $T=600$ data points, and the input dimension is $d=100$. We set $\sigma = 0.1$ and generate the data from a standard normal distribution and classify them as $-1$ or $1$ depending on their relative position to a randomly drawn hyperplane in $\mathds{R}^d$. As we see in Figure \ref{fig:svml2_minimization}, DODG minimizes the objective much faster than Distributed Dual Averaging (DDA)~\cite{dualAveraging} which has a convergence rate of $O\left( \frac{\log(T \sqrt{n})}{\sqrt{T}}\right)$. DDA is simulated using the learning rate that is suggested in~\cite{dualAveraging}. We have observed that boosting this learning rate may yield faster convergence, but still not as fast as DOGD. Figure~\ref{fig:svml2_minimization} also shows the performance of a version of Fast Distributed Gradient Descent (FDGD)~\cite{FastDistributedGradMethods}. As we can see, FDGD fails to converge in an online or stochastic setting and ends up oscillating.

\begin{figure}
\begin{center}
\includegraphics[width=3.3in]{svml2_minimization.pdf}
\end{center}
\caption{\label{fig:svml2_minimization} Optimization of a $d=100$ dimensional problem of the form \eqref{eq:svm} with a random network of $10$ nodes. Our proposed algorithm DOGD(red) converges faster than DDA(green) as expected from the $T$ instead of $\sqrt{T}$ in the denominator of the convergence rate bound. FDGD(black), is unable to converge in the online problem.}
 \end{figure}

\section{Future Work} \label{sec:future}

In this paper we have proposed and analyzed a novel distributed optimization algorithm which we call Distributed Online Gradient Descent (DOGD). Our analysis shows that DOGD converges at a rate $O(\frac{\log(\sqrt{n}T)}{T})$ when solving online, stochastic or batch constrained convex optimization problems if the objective function is strongly convex. This rate is optimal in the number of iterations for the online and batch setting and slower than a serial algorithm only by a logarithmic factor  in the stochastic optimization setting.

In its current form, DOGD requires the nodes in the network to exchange gradient information at every iteration. Our preliminary investigation suggests that gradually performing more and more updates between each communication can speed up distributed optimization algorithms in the batch setting when one explicitly accounts for the time required to communicate data. Our future work will carry out a similar analysis for online and stochastic optimization algorithms.

\section*{Appendix}

\begin{lemma} \label{lem:P_tv_convergence} If $P$ is a doubly stochastic matrix defined over a strongly connected graph $G=(V,E)$ with $\abs{V}=n$ nodes so that $p_{ji} = 0$ if $(i,j) \not \in E$, then for any $t \leq  T$,
\begin{align}
\sum_{s=1}^{t-1 }\norm{\frac{1}{n} \vc{1}^T - \left[ P^{t-s+1} \right]_{i,:}}_1 \leq 1 + \frac{\log{(T \sqrt{n})}}{1 - \sqrt{\lambda_2}}
\end{align}
where $\lambda_2$ is the second largest eigenvalue of $P$.
\end{lemma}

\begin{IEEEproof}
If the consensus matrix $P$ is doubly stochastic it is straightforward to show that $P^t \rightarrow \frac{1}{n} \vc{1} \vc{1}^T$ as $t \rightarrow \infty$. Moreover, from standard Perron-Frobenius is it easy to show (see e.g., \cite{StookDiaconis})
\begin{align}
\norm{\frac{1}{n} \vc{1}^T - \left[ P^t \right]_{i,:}}_1 = 2 \norm{\frac{1}{n} \vc{1}^T - \left[ P^t \right]_{i,:}}_{TV} \leq \sqrt{n} \left(\sqrt{\lambda_2}\right)^t
\end{align}
so in our case $\norm{\frac{1}{n} \vc{1}^T - \left[ P^{t - s+1} \right]_{i,:}}_1  \leq  \sqrt{n} \left(\sqrt{\lambda_2}\right)^{t -s + 1}$. Next, demand that the right hand side bound is less than $\sqrt{n} \delta$ with $\delta$ to be determined:
\begin{align}
\sqrt{n} \left(\sqrt{\lambda_2}\right)^{t - s + 1} \leq \sqrt{n} \delta \Rightarrow t - s +1 \geq \frac{\log{(\delta^{-1})}}{\log{(\sqrt{\lambda_2}^{-1})}}.
\end{align}
So with the  choice $\delta^{-1} = \sqrt{n} T$,
\begin{align}
 \norm{\frac{1}{n} \vc{1}^T - \left[ P^{t - s + 1} \right]_{i,:}}_1 \leq \sqrt{n} \frac{1}{\sqrt{n} T} = \frac{1}{T}
\end{align}
if $t - s +1 \geq \frac{\log{(\delta^{-1})}}{\log{(\sqrt{\lambda_2}^{-1})}} = \hat{t}$. When $s$ is large and $t - s + 1 < \hat{t}$ we  take $\norm{\frac{1}{n} \vc{1}^T - \left[ P^{t - s +1} \right]_{i,:}}_1 \leq 2$. The desired bound is not obtained as follows
\begin{align}
\sum_{s=1}^{t-1} \norm{  \frac{1}{n} \vc{1}^T - \left[ P^{ t- s + 1} \right]_{i,:} }_1  = & \sum_{s=1}^{t- \hat{t} -1 } \norm{  \frac{1}{n} \vc{1}^T - \left[ P^{ t- s +1} \right]_{i,:} }_1 \\
& + \sum_{s = t - \hat{t}}^{t - 1} \norm{  \frac{1}{n} \vc{1}^T - \left[ P^{t- s+1} \right]_{i,:} }_1 \notag \\
 \leq &\sum_{s=1}^{t - \hat{t} -1 } \frac{1}{T} + \sum_{s = t - \hat{t}}^{t - 1} 2 \\
\leq & \frac{t - \hat{t} }{T}    + 2 \hat{t} \leq  1  + 2 \hat{t}
\end{align}
Since $t \leq  T$ we know that $t - \hat{t} < T$. Moreover, $\log{(\sqrt{\lambda_2})^{-1}} \geq 1 - \sqrt{\lambda_2}$. Using there two fact we arrive at the result. The same bound is true for any individual entry of $P^t$ approaching  $\frac{1}{n}$.
\end{IEEEproof}

\bibliographystyle{IEEEtran}