\subsection{Matrix exponential learning as a dual averaging scheme}
\label{appendix:DA}

In our developments, the space of the covariance matrices of each user is equipped with the nuclear norm, given for any Hermitian matrix $\mat$ by 
$ 


\norm{\mat} = \trace{\sqrt{\mat\mat}} 


$, 
and equivalent to the $L_1$-norm of the vector of the eigenvalues of $\mat$. 


The dual of the nuclear norm, 
$
\dualnorm{\mat}= \max_{\altmat} \{ \trace{\mat\altmat} \setst \norm{\altmat}\leq 1 \}  

$, reduces to the $L_\infty$-norm of the vector of eigenvalues.
For every $m\times m$ Hermitian matrix $\mat$, one has

\begin{equation}\label{normsMO}
 \dualnorm{\mat} 
\leq 
\frobeniusnorm{\mat} 
\leq 
\norm{\mat}  
\leq
\sqrt{m} \frobeniusnorm{\mat} 
 \leq 
 m  \dualnorm{\mat} , 
\end{equation} 
where $\frobeniusnorm{\mat}=\sqrt{\trace{\mat\mat}}$ 
denotes the (Frobenius) $L^2$-norm of $\mat$.

From the  global perspective of matrix arrangements $\mat=\vect{\matk{1},...,\matk{\kk}}$---now regarded as block diagonal covariance matrices---, the trace norm and its dual naturally extend as


\begin{equation} \textstyle
\label{globalnorm}
\norm{\mat} = \sum\nolimits_{\nbk=1}^{\kk} \norm{\matk{\nbk}} ,
\qquad 
\dualnorm{\mat} = \max\limits_{\nbk\in\{1,\dots,\kk\}} \dualnorm{\matk{\nbk}}.
\end{equation}


 
 

We now derive the matrix exponential learning step and some properties of it.
To this end, we place ourselves in the compact set $\compactset=\{\mat\in\Herm{\mm}:\trace\mat=1, \mat\succeq 0\}$ of the $\mm$-dimensional positive semidefinite Hermitian matrices with unit trace---the parameter $\mm$ stands for the number of antennas of any of the $\kk$ users. 
 Let the inner product $\inner{\dualmat}{\mat}=\trace{\dualmat\mat}$ denote the value at $\mat\in\trMat$ of the linear function induced by $\dualmat\in\trZmat$, where $\trZmat=\{\trzmat\in\Herm{\mm}\setst\trace{\trzmat}=0\}$ 
is tangent to~$\compactset$. 
For any differentiable function~$\genericfunction$ on~$\Herm{\mm}$, we denote by $\projgrad\genericfunction:\compactset \mapsto\trZmat$ the \emph{orthogonal projection} of the gradient~$\grad\genericfunction$ on the tangent space~$\trZmat$, given  by 
 $\projgrad \genericfunction = \grad \genericfunction - \trace{\grad \genericfunction}\, \identity$.  

\begin{lemma} \label{lemma:reg}
\


\begin{enumerate}[(i),ref=\roman*,wide,labelwidth=!,labelindent=5pt]
\item \label{lemma:regi}

The regularization function\footnote{We use here the convention $0\log0=0$.}
    $
\reg{\mat}=\trace{\mat \log\mat}
    $ 

is $\forcestrongly$-strongly convex over $\compactset$ with respect to $\norm\cdot$.
\item \label{lemma:regii}
The conjugate of $\regfunction$,  $\conjregfunction : \trZmat\mapsto\Real$, defined by

\begin{equation}\label{conjregfunction}
\textstyle
\conjreg{\dualmat} =\max_{\mat\in \compactset} \{ \inner{\dualmat}{\mat} - \reg{\mat}\},

\end{equation}  
 is differentiable with gradient $\grad\conjregfunction = \matsolfunction$, where $\matsolfunction$ is the exponential learning mapping defined by
 

\begin{equation} \label{trmatsol}
\matsol{\dualmat} =\frac{ \exponential{ \dualmat } }{\trace{\exponential{ \dualmat } }} 
.


\end{equation}


\item \label{lemma:regiii}
For $\mat\in\compactset$ and $\dualmat\in\trZmat$, 
\begin{equation} \label{reciprocity}
\mat = \matsol{\dualmat}  \Leftrightarrow 
\dualmat = \projgrad\reg{\mat} .
\end{equation}
\item \label{lemma:regiv}
$\conjregfunction$ is $\forcestrongly$-smooth with respect to the dual norm $\dualnorm\cdot$.


\end{enumerate}
\end{lemma} 

\begin{proof}
We refer to \cite{yu13} for the strong convexity of $\regfunction$.
For \eqref{lemma:regii}, the differentiablity of $\conjregfunction$ is a consequence of Danskin's theorem (e.g. \cite{shapiro09}),
which, besides, gives us the gradient of \eqref{conjregfunction},

\begin{equation} \label{beforetrmatsol}
\textstyle

\grad\conjreg{\dualmat}
= \arg\max_{\mat\in \compactset} \{ \inner{\dualmat}{\mat} - \reg{\mat}\} 
.
\end{equation} 
Relaxing the constraint $ \trace{\mat}  - 1 = 0$ in  the subproblem \eqref{beforetrmatsol} and using $\grad\reg{\mat}=\identity+\log\mat$ 
yields the stationarity condition  

\begin{equation}
 \log\mat - \dualmat + (1+\multiplier)\, \identity = 0  
\tag{S} \label{KKTS}
,
\end{equation}
where $\multiplier\in\Real$ is the Lagrange multiplier related to  the constraint. Condition \eqref{KKTS} rewrites as
$
\mat 

= \exponential{- (1+\multiplier)} \, \exponential{ \dualmat } 
$,
which implies the primal feasibility condition $\mat\succeq 0$. The remaining KKT conditions $\trace{\mat}  - 1 \leq 0$ and $\multiplier \, (\trace{\mat}  - 1 ) = 0 $ 
 yield $\multiplier = \logarithm{\trace{\exponential{ \dualmat } } }-1$, and $\mat=\matsol{\dualmat}$ as the unique maximizer of \eqref{beforetrmatsol}, which completes the proof of \eqref{lemma:regii}.


Now, it follows from \eqref{beforetrmatsol} that, for any $\dualmat\in\trZmatk{\nbk}$, one has $\mat = \matsol{\dualmat}$ if and only if $\inner{\dualmat}{\altmat} - \reg{\altmat} \leq \inner{\dualmat}{\mat} - \reg{\mat}$ holds for all $\altmat \in \trMat$, i.e., iff $\dualmat$ is a subgradient of $\regfunction$ at $\mat$. Claim \eqref{lemma:regiii} follows by differentiability of $\regfunction$.

\obsolete{
Let $\identity$ denote the identity matrix in $\Herm{\mm}$. By relaxing the constraint $ \trace{\mat}  - 1 = 0$ in  the subproblem \eqref{beforetrmatsol} and using $\grad\reg{\mat}=\identity+\log\mat$, we end up with  the KKT conditions   
\begin{align}
\log\mat - \dualmat + (1+\multiplier)\identity = 0 
\tag{S} \label{KKTS}
\\
\mat\succeq 0
\tag{PF1} \label{KKTPF1}
\\
\trace{\mat}  - 1 \leq 0
\tag{PF2} \label{KKTPF2}
\\
\multiplier \in\Real
\tag{DF} \label{KKTDF}
\\
\multiplier \, (\trace{\mat}  - 1 ) = 0
\tag{CS} \label{KKTCS}
\end{align}
where $\multiplier$ denotes the Lagrange multiplier related to  the constraint.
Equation \eqref{KKTS} rewrites as
\obsolete{
\begin{equation} \label{MXL1}
\mat = \exponential{ \dualmat - (1+\multiplier)\identity } = \exponential{- (1+\multiplier)} \, \exponential{ \dualmat } ,
\end{equation}
}
$
\mat 

= \exponential{- (1+\multiplier)} \, \exponential{ \dualmat } 
$,
which implies \eqref{KKTPF1}. The remaining conditions \eqref{KKTPF2}, \eqref{KKTDF} and \eqref{KKTCS} yield $\multiplier = \logarithm{\trace{\exponential{ \dualmat } } }-1$, and $\mat=\matsol{\dualmat}$ as the unique maximizer of \eqref{beforetrmatsol}.


Now, if $\dualmat\in\trZmatk{\nbk}$,
\begin{align}
\notag &
\mat = \matsol{\dualmat}&
\\
\notag \Leftrightarrow \quad&
\inner{\dualmat}{\altmat} - \reg{\altmat} \leq \inner{\dualmat}{\mat} - \reg{\mat}
,& \forall \altmat \in \trMat
\obsolete{
\\
\label{LemmaB1-} \Leftrightarrow \quad&
\inner{\dualmat}{\altmat-\mat} \leq  \reg{\altmat}  - \reg{\mat}
,& \forall \altmat \in \trMat
}
\\
\label{LemmaB1} \Leftrightarrow \quad&
\dualmat \in \subdiff{\regfunction}{\mat} .

&
\end{align}

and \eqref{lemma:regiii} follows by differentiability of $\regfunction$.
}


Finally, \eqref{lemma:regiv} is a property of convex conjugation \cite{kakade12}.
Indeed, let $\dualmat,\altdualmat\in\trZmat$ and $\mat=\matsol{\dualmat}$. 
By convexity, 
\begin{equation} \label{strongconvexity}
\textstyle
\reg{\altmat} \geq \reg{\mat}+\inner{\projgrad\reg{\mat} }{\altmat-\mat} + \frac \forcestrongly 2 \norm{\altmat-\mat}^2
\end{equation}
holds for any $\altmat\in\compactset$. It follows that
\begin{equation} \label{stronglysmooth}
\nocolsep
\begin{array}{rl}
\conjreg{\altdualmat} \hspace{-9mm}
&\hspace{9mm}\refereq{\eqref{conjregfunction}}{=} 
\max_{\altmat\in \compactset} \{ \inner{\altdualmat}{\altmat} - \reg{\altmat}\}
\\
&{\refereq{{\eqref{strongconvexity}}}{\leq}}
\max_{\altmat\in \compactset} \{ \inner{\altdualmat}{\altmat} {\,-\,}  \reg{\mat}{\,-\,}\inner{\projgrad\reg{\mat} }{\altmat{\,-\,}\mat} 

{\,-\,} \frac \forcestrongly 2 \norm{\altmat{\,-\,}\mat}^2 \}
\\
&{\refereq{{\eqref{reciprocity}}}{=}} 

\inner{\dualmat }{\mat}  -  \reg{\mat}  + \inner{\altdualmat -\dualmat }{\mat}
 + \max_{\altmat\in \compactset} \{ \inner{\altdualmat -\dualmat }{\altmat{\,-\,}\mat} 
 \ \\&\hfill
- \frac \forcestrongly 2 \norm{\altmat-\mat}^2 \} 
\\
&{\refereq{{\eqref{beforetrmatsol}}}{\leq}} 
\conjreg{\dualmat}+ \inner{\altdualmat -\dualmat }{\grad\conjreg{\dualmat}} + \frac{1}{2\strongly} \dualnorm{\altdualmat-\dualmat}^2
\end{array}
\end{equation} 
and $\conjregfunction$ is $\forcestrongly$-smooth. Equivently, \eqref{stronglysmooth} rewrites as\cite{nesterov14}
\begin{equation} \label{DAlipschitz}
 \norm{\matsol{\dualmat}-\matsol{\altdualmat}} \leq \oneoverstrongly \dualnorm{\dualmat-\altdualmat}
\quad 
\forall \dualmat,\altdualmat\in\trZmatk{\nbk}
.
\end{equation}

\end{proof}


We now consider the Fenchel primal-dual coupling $\fenchelcoupling:\compactset\times\trZmat\mapsto\Real$ associated with the entropic regularizer $\regfunction$.

\begin{lemma} \label{lemma:fenchel}
The Fenchel coupling
\begin{equation}\label{fenchelkMO}
\fenchel{\mat}{\dualmat} = \reg{\mat} + \conjreg{\dualmat} - \inner{\dualmat}{\mat}


\end{equation}

satisfies the following properties. \begin{subequations}
For $\mat\in\compactset$ and $\dualmat,\altdualmat\in\trZmat$,
\begin{align}
\label{fenchelsmooth} 
  \textstyle
\hspace{-2mm}
\fenchel{\mat}{\altdualmat} 
&\leq \textstyle
\fenchel{\mat}{\dualmat }  {\,+\,}  \inner{  \altdualmat{-}\dualmat}{\matsol{\dualmat}{-}\mat} 

{\,+\,} \frac{1}{2\strongly} \dualnorm{\altdualmat{-}\dualmat }^2 
,  
 \\  \textstyle
\label{fenchelstronglyconvex}
\hspace{-6mm}
\fenchel{\mat}{\dualmat} 
&\geq \textstyle
\frac \forcestrongly 2    \norm{\mat-\matsol{\dualmat}}^2
,
 \\  \textstyle\label{fenchelnonnegativity}
\hspace{-6mm}
\fenchel{\mat}{\dualmat} 
&\geq  0 
\text{ with }
\fenchel{\mat}{\dualmat} = 0 
  \Leftrightarrow

 \dualmat =\projgrad\reg{\mat}

 
. 
\end{align}
\end{subequations}
\end{lemma}

\begin{proof}
Equations \eqref{fenchelsmooth} and \eqref{fenchelstronglyconvex} follow from the smoothness of $\conjregfunction$ and from the strong convexity of $\regfunction$, respectively. Indeed, we get \eqref{fenchelsmooth} by combining \eqref{fenchelkMO} with \eqref{stronglysmooth}, 
while
\begin{equation} \label{derivationfenchelstronglyconvex}
\nocolsep
\begin{array}{rcl}
\fenchel{\mat}{\dualmat} 

&\refereq{\eqref{fenchelkMO}}{=}&
 \max_{\altmat\in \compactset} \{   \reg{\mat} - \reg{\altmat} - \inner{\dualmat}{\mat-\altmat} \} 
\\ 
&\refereq{\eqref{reciprocity}}{\geq}&
  \reg{\mat} - \reg{\matsol{\dualmat}} - \inner{\projgrad\reg{\matsol{\dualmat}}}{\mat-\matsol{\dualmat}} 

\\
&\refereq{\eqref{strongconvexity}}{\geq}&


\frac \forcestrongly 2    \norm{\mat-\matsol{\dualmat}}^2
\end{array}
\end{equation}
yields \eqref{fenchelstronglyconvex}.
Then, \eqref{fenchelnonnegativity} follows from \eqref{fenchelstronglyconvex} and \eqref{reciprocity}.
\end{proof}

\renewcommand{\strongly}{}


\subsection{The \ac{SPSA} estimator}
\label{appendix:SPSA}

This section is concerned with the bias of the gradient estimator defined, for $\nbk=1,\dots,\kk$, by 
\begin{equation}\label{estgradratekO}\begin{array}{c}
\estgradratek{\nbk}{\mat}{\trzmat}{\offset}
=
\frac{\dimensionk{\nbk}}{\delta} \big[ \rate{ \testmat} - \offset \big] \, \trzmatk{\nbk} ,

\end{array}
\end{equation}
where $\delta>0$ is a given query radius, $\testmat = \vect{\testmatk{1},\dots,\testmatk{\kk}}$ is given by \eqref{linearperturbator}, $\trzmat=\vect{\trzmatk{1},\dots,\trzmatk{\kk}}$ with $\trzmatk{\nbk}$ sampled uniformly on the sphere $\trmspherei{\dimensionk{\nbk}-1}$, and $\offset$ an arbitrary scalar offset quantity independent of $\trzmat$. Observe that \eqref{estgradratekO} covers the gradient estimators of both \ac{MXL0} and \ac{MXL+}. 


The computation of a  bound for the bias of estimator \eqref{estgradratekO} is based on Stokes' theorem, applied to the sphere $\trmspherei{\dimensionk{\nbk}-1}  $:
\begin{equation}\label{stokes}

\int_{\trmspherei{\dimensionk{\nbk}-1}} \generic{ 
\trzmatk{\nbk} } \, \trzmatk{\nbk} \,  d\lebesgue{\trzmatk{\nbk}}
= 
\int_{\trmballi{\dimensionk{\nbk}}} \projgrad\generic{ 
 \momega} \,  d\lebesgue{\momega}
,
\end{equation}
where $\genericfunction$ is any function on $\Herm{\mmk{\nbk}}$ and $\lebesguemeasure$ denotes the Lebesgue measure.

Before proceeding, observe


 
that each
test covariance marix $\testmatk{\nbk}$  is bound to the initial matrix $\matk{\nbk}$ by
$
\frobeniusnorm{\testmatk{\nbk} - \matk{\nbk} }\leq \twitchFlipschitz \delta \frobeniusnorm{\trzmatk{\nbk}} 
$,

where, under our assumption $\dimensionk{\nbk}>0$,

$
\dualnorm{ \trzmatk{\nbk}}\leq {1}/{2}
$ 
for every
$
\trzmatk{\nbk}\in\trmspherei{\dimensionk{\nbk}-1}
$.


It follows from \eqref{normsMO} that  any test configuration $\testmat$ in \eqref{estgradratek} and \eqref{estgradratekMO} satisfies
\begin{equation} \label{perturbatorbound}
\frobeniusnorm{\testmat - \mat }
\leq 
\twitchFlipschitz\delta \kk,

\quad \text{and} \quad
\norm{\testmat  - \mat }
\leq 

\twitchFlipschitz\delta \kk \sqrt{\maxdimension} 
.
\end{equation}


 


\begin{lemma}\label{lemma:bias}
The estimator \eqref{estgradratekO} satisfies 
\begin{align}\textstyle &
 
\label{lipschitzconstantMO}
\dualnorm{ \expectation{\estgradratek{\nbk}{\mat}{\trzmat}{\offset} -\gradk{\nbk} \rate{\mat}   } }  
\leq
{2\kk\meanlipschitzk{\nbk}}\, \delta

,


\\&

\label{trboundgradientestimateMO}
\textstyle
\dualnorm{\estgradratek{\nbk}{\mat}{\trzmat}{\offset}}
\leq
 


\frac{  \dimensionk{\nbk}}{2^{\kk}\delta}  \max_{\altmat \in\compactset} \modulus{ \rate{ \altmat } - \offset }
.

\end{align}


\end{lemma}
\begin{proof}[Proof of \cref{lemma:bias}]
We argue as in \cite{FKM05,BLM18}.
\obsolete{
First observe that
\begin{equation}\label{integrationresult}
\begin{array}{r}
\frac{ 
\int_{\trmballi{\dimensionk{\nbk}}}
 \frobeniusnorm{  \momega} \, d\lebesgue{\momega}
}{\int_{\trmballi{\dimensionk{\nbk}}}
 \, d\lebesgue{\momega}} 
=
\frac{ 
\int_0^1 d\varrho
\int_{\varrho\trmspherei{\dimensionk{\nbk}-1}}
 \varrho \, d\lebesgue{\momega}
}{
\int_0^1 d\varrho
\int_{\varrho\trmspherei{\dimensionk{\nbk}-1}}
\, d\lebesgue{\momega}
} 
=
\frac{ 
\int_0^1 
\varrho\, \Volume{\varrho\trmspherei{\dimensionk{\nbk}-1}}
 d\varrho
}{
\int_0^1 \Volume{\varrho\trmspherei{\dimensionk{\nbk}-1}} d\varrho
} 
\quad \\
=
\frac{\dimensionk{\nbk}}{\dimensionk{\nbk}+1}
.
\end{array}
\end{equation}
}

By introducing the notation
$ \contrmatkdeltaZ{\nbk}{\delta}{\momega} = \vect{\testmatk{1}, \dots, \testmatk{\nbk-1}, \contrmatkdeltaZk{\nbk}{\delta}{\momega}{\nbk}  ,\testmatk{\nbk+1}, \dots, \testmatk{\kk} }$,
in which $ \contrmatkdeltaZk{\nbk}{\delta}{\momega}{\nbk}  = \matk{\nbk} + ({\delta}/{\radiusk{\nbk}}) (\cmatk{\nbk} - \matk{\nbk})  + \delta \momega$,


we find
\begin{equation}\label{earlylipschitzconstantMO}
\begin{array}{l}
\dualnorm{ \expectation{\estgradratek{\nbk}{\mat}{\trzmat}{\offset} -\projgradk{\nbk} \rate{\mat}   } }  

\\
\qquad
\qquad
\refereq{\eqref{estgradratekO}}{ =}
\dualNorm{ \expectation{\frac{\dimensionk{\nbk}}{\delta} [ \rate{ \testmat} - \offset ] \, \trzmatk{\nbk}
-\projgradk{\nbk} \rate{\mat}   } }  
\\
\qquad
\qquad
=
\dualNorm{ \frac{\dimensionk{\nbk}}{\delta}\expectation{  \rate{ \testmat} \, \trzmatk{\nbk}
   }  -\projgradk{\nbk} \rate{\mat} }  
\\
\qquad
\qquad
=  

\dualNorm{


\frac{\dimensionk{\nbk}}{\delta} \Expectation{ \frac{ \int_{\trmspherei{\dimensionk{\nbk}-1}}   \rate{\contrmatkdeltaZ{\nbk}{\delta}{\trzmatk{\nbk}}} \, \trzmatk{\nbk}
  \,  d\lebesgue{\trzmatk{\nbk}} 
}{\volume{\trmspherei{\dimensionk{\nbk}-1}}}}
-\projgradk{\nbk} \rate{\mat}

}
\\
\qquad
\qquad
\refereq{\eqref{linearperturbator}}{=}

\dualNorm{


\Expectation{
\frac{ \int_{\trmspherei{\dimensionk{\nbk}-1}} \rate{\contrmatkdeltaZ{\nbk}{\delta}{\trzmatk{\nbk}}} \, \trzmatk{\nbk}
 \,  d\lebesgue{\trzmatk{\nbk}} 
}{\delta\volume{\trmballi{\dimensionk{\nbk}}}}
-\projgradk{\nbk} \rate{\mat} }

}
.
\end{array}\end{equation}
\obsolete{
where 
$ \contrmatkdeltaZ{\nbk}{\delta}{\momega} = \vect{\testmatk{1}, \dots, \testmatk{\nbk-1}, \contrmatkdeltaZk{\nbk}{\delta}{\momega}{\nbk}  ,\testmatk{\nbk+1}, \dots, \testmatk{\kk} }$,
with $ \contrmatkdeltaZk{\nbk}{\delta}{\momega}{\nbk}  = \matk{\nbk} + {\delta} (\cmatk{\nbk} - \matk{\nbk}) /{\radiusk{\nbk}} + \delta \momega. $
}


It follows from Stokes' theorem that \eqref{earlylipschitzconstantMO} reduces to
\begin{equation}\label{computationlipschitzconstantMO}
\begin{array}{l}
\dualnorm{ \expectation{\estgradratek{\nbk}{\mat}{\trzmat}{\offset} -\projgradk{\nbk} \rate{\mat}   } }  
\\ \quad
\refereq{\eqref{stokes}}{=}

\dualNorm{


\Expectation{
\frac{ \int_{\trmballi{\dimensionk{\nbk}}} \delta \projgradk{\nbk}\rate{\contrmatkdeltaZ{\nbk}{\delta}{\momega}} 
\, d\lebesgue{\momega}}{\delta\volume{\trmballi{\dimensionk{\nbk}}}}
-\projgradk{\nbk} \rate{\mat}}

}
\\ \quad
\obsolete{
=

\dualNorm{


\Expectation{
\frac{ \int_{\trmballi{\dimensionk{\nbk}}} \left[ \projgradk{\nbk}\rate{\contrmatkdeltaZ{\nbk}{\delta}{\momega}} 
-\projgradk{\nbk} \rate{\mat}\right]\, d\lebesgue{\momega}}{\volume{\trmballi{\dimensionk{\nbk}}}}
}

}
\\ \quad
}
\leq  

\bigexpectation{
\frac{1}{\volume{\trmballi{\dimensionk{\nbk}}}} \int_{\trmballi{\dimensionk{\nbk}}} \dualnorm{ \projgradk{\nbk}\rate{\contrmatkdeltaZ{\nbk}{\delta}{\momega}} 
-\projgradk{\nbk} \rate{\mat} } \, d\lebesgue{\momega}
}
\\ \quad


\obsolete{
\refereq{\eqref{smoothness}}{\leq}

\frac{ 
\gradlipschitz\int_{\trmballi{\dimensionk{\nbk}}}
 \frobeniusNorm{ \twitchk{\nbk}{\matk{\nbk}}{\delta\momega} - \matk{\nbk} } \, d\lebesgue{\momega}
}{\Volume{\trmballi{\dimensionk{\nbk}}}}

+
\gradlipschitz \Expectation{
\sum_{\altnbk\neq\nbk}    \frobeniusnorm{\testmatk{\altnbk}-\matk{\altnbk}}
}
\\  \quad
\refereq{\eqref{linearperturbator}}{\leq}

\gradlipschitz\left(1+
\frac{ 
\int_{\trmballi{\dimensionk{\nbk}}}
 \frobeniusnorm{  \momega} \, d\lebesgue{\momega}
}{\Volume{\trmballi{\dimensionk{\nbk}}}} 
\right) \delta
+
2 \gradlipschitz (\kk-1)  \,  \delta
\\  \quad
=

\gradlipschitz\big(1+ \frac{\mmk{\nbk}^2-1}{\mmk{\nbk}^2} \big) \delta
+
2 \gradlipschitz (\kk-1)  \,  \delta
\\ \quad
\leq
2\kk\gradlipschitz\,\delta
}

\refereq{\eqref{lipschitzkl}}{\leq}

\frac{ 
\int_{\trmballi{\dimensionk{\nbk}}}\lipschitzkl{\nbk}{\nbk}
 \, \frobeniusnorm{ \contrmatkdeltaZk{\nbk}{\delta}{\momega}{\nbk} - \matk{\nbk} } \, d\lebesgue{\momega}
}{\volume{\trmballi{\dimensionk{\nbk}}}}

+
\sum_{\altnbk\neq\nbk}  \lipschitzkl{\nbk}{\altnbk} \expectation{ \frobeniusnorm{\testmatk{\altnbk}-\matk{\altnbk}}
}
\\  \quad
\refereq{\eqref{linearperturbator}}{\leq}

\lipschitzkl{\nbk}{\nbk}\bigg(1+
\frac{ 
\int_{\trmballi{\dimensionk{\nbk}}}
 \frobeniusnorm{  \momega} \, d\lebesgue{\momega}
}{\volume{\trmballi{\dimensionk{\nbk}}}}
\bigg) \delta

+

2\sum_{\altnbk\neq\nbk} \lipschitzkl{\nbk}{\altnbk} \Expectation{  \frobeniusnorm{\trzmatk{\altnbk}}} \delta
\\ \quad
\obsolete{
\refereq{\eqref{integrationresult}}{=}
\lipschitzkl{\nbk}{\nbk}

\left(\frac{2 \mmk{\nbk}+1}{\mmk{\nbk}+1}\right)  
\delta 
+

\sum_{\altnbk\neq\nbk}  \lipschitzkl{\nbk}{\altnbk}\Expectation{  \frobeniusnorm{\testmatk{\altnbk}-\matk{\altnbk}}}
\\
\leq   
\lipschitzkl{\nbk}{\nbk}
\left(\frac{2 \dimensionk{\nbk}}{\mmk{\nbk}^2}\right)  
\delta
+
\sum_{\altnbk\neq\nbk}  \lipschitzkl{\nbk}{\altnbk}\Expectation{  \frobeniusnorm{\twitchk{\altnbk}{\delta\matk{\altnbk}}{\trzmatk{\altnbk}} 
-\matk{\altnbk}}}
\\
\refereq{\eqref{perturbatorlipschitz}}{\leq}
}
\leq

\lipschitzkl{\nbk}{\nbk}\big(\frac{2 \mmk{\nbk}+1}{\mmk{\nbk}+1}\big)  \delta + 2 \sum_{\altnbk\neq\nbk}  \lipschitzkl{\nbk}{\altnbk}  \delta

\,\leq\,

{2\kk\meanlipschitzk{\nbk}}\delta


,  
\end{array}
\end{equation}
and we recover \eqref{lipschitzconstantMO}.

Then \eqref{trboundgradientestimateMO} is immediate from the definition of $\estgradratek{\nbk}{\mat}{\trzmat}{\offset}$ and the fact that
$
\dualnorm{ \trzmatk{\altnbk}}\leq {1}/{2}
$ 
 for all $\altnbk$. 
\end{proof}


\subsection{Analysis of the \ac{MXL0} algorithm}
\label{appendix:MXL0}


Let $\optMat$ denote the solution set of \eqref{eq:trproblem}. Given any~$\optmat\in\optMat$, we consider, for analysis purposes, the Lyapunov function
\begin{equation} \label{lyapunov}
\textstyle
\lyapunov{\optmat}{\dualmat} = \sum_{\nbk=1}^{\kk}\fenchel{\optmatk{\nbk}}{\dualmatk{\nbk} } ,
\end{equation}


where 

$\fenchelcoupling$ is the Fenchel coupling defined in
~\eqref{fenchelkMO}.

If 
$
\filtrationn{\itr-1} 
=
( \dualmatn{1},\zmatn{1},\dots,\dualmatn{\itr-1},\zmatn{\itr-1} )
$
denotes  the history of \ac{MXL0} up to step $\itr-1$,

the gradient estimator \eqref{estgradratekO} decomposes into
\begin{equation}\label{estimatordecomposition}
\estgradkn{\nbk}{\itr}= \projgradk{\nbk}\rate{\matn{\itr}} + \biaskn{\nbk}{\itr} + \devmatkn{\nbk}{\itr} ,
\end{equation}
where $\biaskn{\nbk}{\itr}  =  \expectation{  \estgradkn{\nbk}{\itr} \cond \filtrationn{\itr-1}   } - \projgradk{\nbk}\rate{\matn{\itr}}$ is the systematic error on $\estgradkn{\nbk}{\itr}$, 
bounded by
\begin{equation} \label{biasbound}
\dualnorm{ \biaskn{\nbk}{\itr} }
\refereq{\eqref{lipschitzconstantMO}}{\leq} 
{2\kk\meanlipschitzk{\nbk}}\deltan{\itr} 
,
\end{equation}
 and $\devmatkn{\nbk}{\itr}$ is the random deviation of $\estgradkn{\nbk}{\itr}$ from its expected value $ \expectation{ \estgradkn{\nbk}{\itr} \cond \filtrationn{\itr-1}   } $, so that $ \expectation{  \devmatkn{\nbk}{\itr} \cond \filtrationn{\itr-1}   }=0 $, and
\begin{equation} \label{earlydeviationbound} 
\nocolsep
\begin{array}{rcl}
\dualnorm{\devmatkn{\nbk}{\itr} } 

\obsolete{
&\leq& 
\dualnorm{\estgradkn{\nbk}{\itr}} + \dualnorm{\expectation{ \estgradkn{\nbk}{\itr}\cond \filtrationn{\itr-1}   } }  
\\
}

&\leq&
\dualnorm{\estgradkn{\nbk}{\itr}} + \expectation{\dualnorm{ \estgradkn{\nbk}{\itr}   } \cond \filtrationn{\itr-1}}  .


\end{array}
\end{equation}
In our analysis we consider the 


following random sequence:
\begin{equation} \label{MDSn}
\textstyle
\MDSn{\itr}= \stepsizen{\itr} \sum_{\nbk=1}^{\kk}   \inner{ \devmatkn{\nbk}{\itr}}{\matkn{\nbk}{\itr}-\optmatk{\nbk}} 
.
\end{equation}

Since $ \modulus{\inner{ \devmatkn{\nbk}{\itr}}{\matkn{\nbk}{\itr}{\,-\,}\optmatk{\nbk}}}{\,\leq\,}\dualnorm{ \devmatkn{\nbk}{\itr}}\norm{\matkn{\nbk}{\itr}{\,-\,}\optmatk{\nbk}} {\,\leq\,} 2 \dualnorm{ \devmatkn{\nbk}{\itr}}$, one has
\newcommand{\martingaledifference}{(\refeq{martingaledifferenceboth}a)}
\newcommand{\modulusmartingaledifference}{(\refeq{martingaledifferenceboth}b)}
\begin{equation}
\label{martingaledifferenceboth}
\textstyle
\text{a)}\quad 
\expectation{\MDSn{\itr}   \cond \filtrationn{\itr-1}   }
= 0 ,
\qquad
\text{b)}\quad
\modulus{\MDSn{\itr}} \leq 2\stepsizen{\itr} \sum_{\nbk=1}^{\kk}  \dualnorm{  \devmatkn{\nbk}{\itr}}
.
\end{equation}
\obsolete{
\begin{align}
\label{martingaledifference}
& \textstyle
\expectation{\MDSn{\itr}   \cond \filtrationn{\itr-1}   }
= 0 ,
\\
\label{modulusmartingaledifference}
& \textstyle
\modulus{\MDSn{\itr}} \leq 2\stepsizen{\itr} \sum_{\nbk=1}^{\kk}  \dualnorm{  \devmatkn{\nbk}{\itr}},
\end{align}
}


\obsolete{
\begin{lemma}\label{lemma:azuma}
 If $\stepsizen{\itr}=\cststepsize$ and $\dualnorm{\estgradkn{\nbk}{\itr}}\leq\vboundk{\nbk}$ for $\nbk=1,\dots,\kk$ and for $\itr=1,\dots,T$, then 
 \begin{equation} \label{azumabis}
\textstyle
\Proba{\frac{\sum_{\itr=1}^{T}  \MDSn{\itr}  }{ T\zmargin\,\cststepsize  }  \leq \zmargin }
\geq 
1-\Exponential{-\frac{T\zmargin^2}{32     \left( \sum_{\nbk=1}^{\kk}   \vboundk{\nbk}  \right)^2 }}
.
\end{equation}

\end{lemma}
\begin{proof}
By assumption, we find from \eqref{earlydeviationbound} and \\martingaledifference{} 
that  
$
\modulus{\MDSn{\itr}} 


\leq
4\cststepsize \sum_{\nbk=1}^{\kk}   \vboundk{\nbk}
$ for $\itr=1,\dots,T$.

Since $\{\MDSn{\itr}\}$ is the bounded difference sequence of the martingale $\sum_{\itr=1}^{T} \MDSn{\itr}$, it follows from Azuma's inequality that, for  any $\zmargin>0$,
\begin{equation} \label{standardazuma}
\begin{array}{c}
\Proba{\sum_{\itr=1}^{T}  \MDSn{\itr}   > T\zmargin\,\cststepsize }
 \leq 
\Exponential{-\frac{(T\cststepsize\zmargin)^2}{2   T   \left(4\cststepsize \sum_{\nbk=1}^{\kk}   \vboundk{\nbk}  \right)^2 }}
\end{array}
\end{equation}

which is equivalent to \eqref{azumabis}.

\end{proof}

}


\begin{lemma}\label{lemma:globaldescentargument}
\renewcommand{\dimensionk}[1]{\maxdimension}
\renewcommand{\meansqdimension}{\maxdimension}
\renewcommand{\meandimension}{\maxdimension}
Run \ac{MXL0}/\ac{MXL+} for $\itr$ iterations under \eqref{deltacondition}.
\begin{enumerate}[(i),ref=\roman*,wide,labelwidth=!,labelindent=5pt]
\item \label{lemma:globaldescentargumenti}
 With any step-size and query radius policy $\vect{\stepsizen{\itr},\deltan{\itr}}$,
\begin{equation} \label{descentargumenttwo} 
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunov{\optmat}{\dualmatn{\itr}} - \stepsizen{\itr} \left[\optrate-\rate{\matn{\itr}}\right]
+  \MDSn{\itr}
\qquad
\\
\hfill 
+ 4\kk^2 \meanlipschitz \stepsizen{\itr}\deltan{\itr}  + \frac{\stepsizen{\itr}^2}{2\strongly} \sum_{\nbk=1}^{\kk}   \dualnorm{\estgradkn{\nbk}{\itr}}^2
\end{array}
\end{equation}
holds for~$\optmat\in\optMat$, where 


the sequence $\MDSn{\itr} $   is defined as in \eqref{MDSn}.

\item \label{lemma:globaldescentargumentii}
With decreasing policy $\vect{\stepsizen{\itr},\deltan{\itr}}=\vect{\cststepsize\,\itr^{-\alpha},\cstdelta\,\itr^{-\beta}}$, such that $\alpha,\beta\geq0$ and $\cststepsize,\cstdelta>0$,

\begin{equation} \label{expectationyergodicaverageidentity} 
\begin{array}{l}
\optrate -\bigexpectation{\rate{ \meanmatn{\itr}}}
 \leq
\frac{\lyapunov{\optmat}{\dualmatn{1}}}{\cststepsize\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} } 
+ \frac{4\kk^2\meanlipschitz \cstdelta\sum_{\altitr=1}^{\itr} \altitr^{-\alpha-\beta} }{\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} }  
\qquad\qquad
\\
\hfill 
+ \frac{ \cststepsize\sum_{\altitr=1}^{\itr}  \altitr^{-2\alpha} \sum_{\nbk=1}^{\kk}   \dualnorm{\estgradkn{\nbk}{\altitr}}^2}{2\strongly\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} }
.
\end{array}
\end{equation}


\item \label{lemma:globaldescentargumentiii}
With constant policy $\vect{\stepsizen{\itr},\deltan{\itr}}{\,=\,}\vect{\cststepsize,\cstdelta}$, such that $\cststepsize,\cstdelta>0$,
\begin{equation} \label{standardtroptrateboundmeanexpectation} 
\textstyle
\optrate -\bigexpectation{ \rate{ \meanmatn{T}} }
 \leq
\frac{\lyapunov{\optmat}{\dualmatn{1}}}{T \cststepsize } 

+ 4\kk^2\meanlipschitz\cstdelta  
+ \frac{\cststepsize\sum\nolimits_{\itr=1}^{T}  \sum\nolimits_{\nbk=1}^{\kk}   \dualnorm{\estgradkn{\nbk}{\itr}}^2}{2\strongly T}
\end{equation}
for any $T\geq 1$.

Further, if  there exists $\vbound > 0  $ such that  $\dualnorm{\estgradkn{\nbk}{\itr}}\leq\dimensionk{\nbk}\vbound$ for $\nbk=1,\dots,\kk$ and $\itr=1,\dots,T$, then 
 \begin{equation} \label{standardazumabis}
\textstyle
\bigproba{\frac{ 1}{ T\cststepsize  } \sum_{\itr=1}^{T}  \MDSn{\itr}  \leq \zmargin }
\geq 

1-\exponential{-\frac{T\zmargin^2}{32 \vbound^2 \meandimension^2 }}
.
\end{equation}

\end{enumerate}
\end{lemma}
\begin{proof}[Proof of \cref{lemma:globaldescentargument}]
\renewcommand{\dimensionk}[1]{\maxdimension}
\renewcommand{\meansqdimension}{\maxdimension}
\renewcommand{\meandimension}{\maxdimension}

\eqref{lemma:globaldescentargumenti}  If~$\optmat\in\optMat$, the concavity of $\ratefunction$ gives
\begin{equation}\label{concavityone}
\textstyle
\sum_{\nbk=1}^{\kk}\inner{ \projgradk{\nbk}\rate{\mat}  }{\matk{\nbk}-\optmatk{\nbk}} 


\leq
\rate{\mat}-\optrate
, 
\quad \forall\mat\in\compactset.
\end{equation}


It follows from  \cref{lemma:fenchel} that 
\begin{equation} \label{earlydescentargumenttwo} 
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \refereq{\eqref{MXL}}{=} 
 \sum_{\nbk=1}^{\kk}\fenchel{\optmatk{\nbk}}{\dualmatkn{\nbk}{\itr} + \stepsizen{\itr} \estgradkn{\nbk}{\itr}}
\\
\quad \refereq{\eqref{fenchelsmooth}}{\leq}    
\lyapunov{\optmat}{\dualmatn{\itr}} +\sum_{\nbk=1}^{\kk}\Big[ \stepsizen{\itr}  \inner{  \estgradkn{\nbk}{\itr}}{\matkn{\nbk}{\itr}-\optmatk{\nbk}}  + \frac{\stepsizen{\itr}^2}{2\strongly} \dualnorm{\estgradkn{\nbk}{\itr}}^2
\Big]

\\
\quad \refereq{\eqref{estimatordecomposition}}{=}   
\lyapunov{\optmat}{\dualmatn{\itr}} + \stepsizen{\itr}  \sum_{\nbk=1}^{\kk}\inner{ \projgradk{\nbk}\rate{\matn{\itr}}  }{\matkn{\nbk}{\itr}-\optmatk{\nbk}}  +  \MDSn{\itr} 
\\
\hfill 
+ \sum_{\nbk=1}^{\kk}  \Big[\stepsizen{\itr}  \inner{   \biaskn{\nbk}{\itr}  }{\matkn{\nbk}{\itr}-\optmatk{\nbk}}  + \frac{\stepsizen{\itr}^2}{2\strongly} \dualnorm{\estgradkn{\nbk}{\itr}}^2\Big]
,
\end{array}
\end{equation}


Besides, \eqref{biasbound} gives
$
\modulus{ \inner{   \biaskn{\nbk}{\itr}  }{\matkn{\nbk}{\itr}-\optmatk{\nbk}} }


\leq
4\kk\meanlipschitzk{\nbk}\deltan{\itr} 
$,


which combined with \eqref{concavityone} and \eqref{earlydescentargumenttwo} yields Inequality \eqref{descentargumenttwo}.


\eqref{lemma:globaldescentargumentii}
By telescoping \eqref{descentargumenttwo} $\itr-1$ times, dividing by $\sum_{\altitr=1}^{\itr} \stepsizen{t} $, and using 
$\lyapunov{\optmat}{\dualmatn{n+1}}\geq 0$, 
we find
\begin{equation} \label{ergodicaverageidentity} 
\begin{array}{l}
\optrate - \frac{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} \rate{\matn{\altitr}}}{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} }
 \leq
\frac{\lyapunov{\optmat}{\dualmatn{1}}}{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} } + \frac{\sum_{\altitr=1}^{\itr}  \MDSn{\altitr} }{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} }
\qquad\qquad\quad
\\
\hfill 
+ 4\kk^2\meanlipschitz\frac{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr}\deltan{\altitr} }{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} }  
+ \frac{1}{2\strongly}\frac{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr}^2 \sum_{\nbk=1}^{\kk}   \dualnorm{\estgradkn{\nbk}{\altitr}}^2}{\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} }
.
\end{array}
\end{equation}
By concavity of $\ratefunction$, the time average of the estimates satisfies

\begin{equation}\label{concavitymean}
\textstyle
\rate{ \meanmatn{\itr}}
\geq
\big(\frac{
1
}{
\sum_{\altitr=1}^{\itr} \stepsizen{\altitr} 
}\big)
\sum_{\altitr=1}^{\itr} \stepsizen{\altitr}   \rate{\matn{\altitr}}   

.
\end{equation}
Introducing  the suggested policies in \eqref{ergodicaverageidentity} and using \eqref{concavitymean} gives
\begin{equation} \label{readyergodicaverageidentity} 
\begin{array}{l}
\optrate - \rate{ \meanmatn{\itr}}
 \leq
\frac{\lyapunov{\optmat}{\dualmatn{1}}}{\cststepsize\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} } + \frac{\sum_{\altitr=1}^{\itr}  \MDSn{\altitr} }{\cststepsize \sum_{\altitr=1}^{\itr} \altitr^{-\alpha} }
\qquad\qquad\qquad\quad
\\
\hfill 
+ 4\kk^2\meanlipschitz\frac{ \cstdelta\sum_{\altitr=1}^{\itr} \altitr^{-\alpha-\beta} }{\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} }  
+ \frac{\cststepsize}{2\strongly}\frac{ \sum_{\altitr=1}^{\itr}  \altitr^{-2\alpha} \sum_{\nbk=1}^{\kk}   \dualnorm{\estgradkn{\nbk}{\altitr}}^2}{\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} }
.
\end{array}
\end{equation}
\obsolete{
Applying $\itr$ times \martingaledifference{} 
gives
\begin{equation} \label{nullexpectationofsum} 
\begin{array}{r}
 \Expectation{ \sum_{\altitr=1}^{\itr}  \MDSn{\altitr}} 
=
\Expectation{ \Expectation{ \sum_{\altitr=1}^{\itr}  \MDSn{\altitr} \cond \filtrationn{0}  }} 
\ \ \\ \hfill
 =
\Expectation{ \Expectation{ \sum_{\altitr=2}^{\itr}  \MDSn{\altitr} \cond \filtrationn{1}  } }
 = \hdots =
\Expectation{ \Expectation{   \MDSn{\itr} \cond \filtrationn{\itr-1}  } } = 0.
\end{array} 
\end{equation}
}
Since \martingaledifference{} 
lends $\{\MDSn{\itr}\}$ the quality of a martingale difference sequence, $\expectation{ \sum_{\altitr=1}^{\itr}  \MDSn{\altitr}}=0$, and \eqref{expectationyergodicaverageidentity} follows by expectation of \eqref{readyergodicaverageidentity}. 


\eqref{lemma:globaldescentargumentiii}
Setting $\alpha=\beta=0$ in \eqref{expectationyergodicaverageidentity}  gives us \eqref{standardtroptrateboundmeanexpectation}.

By using the bounds $\vboundk{1},\dots,\vboundk{\kk}  $ in combination with \eqref{earlydeviationbound} and \modulusmartingaledifference{}, 
we find that
$
\modulus{\MDSn{\itr}} 


\leq


4\vbound\meandimension\cststepsize 
$ for $\itr=1,\dots,T$, and the martingale difference sequence $\{\MDSn{\itr}\}$ is bounded.

It follows from Azuma's inequality that
$

\textstyle
\proba{\sum_{\itr=1}^{T}  \MDSn{\itr}   > T\zmargin\,\cststepsize }
 \leq 

\brackexponential{-\frac{(T\cststepsize\zmargin)^2}{2   T   (4\vbound\meandimension\cststepsize)^2 }} 

$ 

 for  any $\zmargin>0$,
which is equivalent to \eqref{standardazumabis}.

\end{proof}

\showMXLzerolastiterate{
\cref{thm:lasttrMXL,thm:trMXLiinew} follow from \cref{lemma:bias,lemma:globaldescentargument}.


\begin{proof}[Proof of \cref{thm:lasttrMXL}]

Following the line of thought of the proof of \cite[Theorem 5.1]{BLM18}, we first show there one can find a solution $\optmat\in\optMat$ such that
\begin{equation} \label{liminfassumption}
\textstyle
\liminf_{\itr\to\infty} \Lyapunov{\optmat}{\dualmatn{\itr}} = 0
\quad
\as \, .
\end{equation}
Next, we see that $\{\lyapunov{\optmat}{\dualmatn{\itr}}\}$ converges almost surely (\as{}) towards a finite quantity which, in view of \eqref{liminfassumption}, can only be~$0$. 


 \As{} convergence of $\{\matn{\itr}\}$ towards $\optmat$ can then be inferred from \cref{lemma:fenchel}-\eqref{fenchelstronglyconvex}.


The assumption of  non-increasing $\{\deltan{\itr}\}$, together with \reflasttrMXLi{} and \reflasttrMXLii{}, implies $\deltan{\itr}\downarrow 0$ which, in view of \eqref{perturbatorbound}, secures \as{} convergence of $\{\testmatn{\itr}\}$ as well.

First observe that \eqref{liminfassumption} holds if, almost surely, there exists a subsequence of $\{\matn{\itr}\}$ that converges towards a solution~$\optmat\in\optMat$.


Suppose this condition not to hold, and let $\limitpoints$ denote the set of the limit points of all  subsequences of $\{\matn{\itr}\}$. 


Then, almost surely, we have $\optMat\cap \limitpoints=\emptyset$ and, since $\limitpoints$ is closed 
by construction and $\ratefunction$ is continuous and  convex, 
$ \varrho \defeq \optrate - \max_{\mat\in \limitpoints}{\rate{\mat}}>0$.

\obsolete{
\footnotetext{Indeed, suppose there is  a sequence $\{\compactmatn{\altitr}\}$ in $\limitpoints$ converging to $\compactmatn{\infty}\notin \limitpoints$. For any be any sequence of positive numbers $\{\epsilon_\altitr\}$ with $\epsilon_\altitr\downarrow 0$, one can find $\{\matn{\itr_\altitr}\}$, subsequence of $\{\matn{\itr}\}$, such that $\norm{\matn{\itr_\altitr}-\compactmatn{\altitr}}<\epsilon_\altitr$ for all $\altitr$. Hence, $\matn{\itr_\altitr}\to\compactmatn{\infty}$ and we reach the contradiction $\compactmatn{\infty} \in \limitpoints$.}
}


Telescoping \eqref{descentargumenttwo}  in  \cref{lemma:globaldescentargument}\eqref{lemma:globaldescentargumenti} and using
 \eqref{trboundgradientestimateMO}, yields


\begin{equation} \label{adabsurdumlyapunovdescentbound} 
\begin{array}{l}
\hspace{-0mm}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunov{\optmat}{\dualmatn{1}} - \sum_{\altitr=1}^{\itr} \stepsizen{\altitr} \left[\optrate-\rate{\matn{\altitr}}\right]
\quad \  \\ 
\hfill 
{+}  \sum_{\altitr=1}^{\itr}\MDSn{\altitr}  {+\,} 4\kk^2 \meanlipschitz \sum_{\altitr{=}1}^{\itr} \stepsizen{\altitr}\deltan{\altitr}  
{+}\frac{\kk(\optrate\maxdimension)^2}{2^{2\kk{+}1}\strongly} \sum_{\altitr{=}1}^{\itr} \frac{\stepsizen{\altitr}^2}{\deltan{\altitr}^2} 
,
\end{array}
\end{equation}
where $\{\MDSn{\itr}\}$ is the difference sequence of a martingale  with respect to the filtration $\{\filtrationn{\itr}\}$.


In view of \reflasttrMXLii{} and \reflasttrMXLiii{},  the last two terms in the second member of \eqref{adabsurdumlyapunovdescentbound} converge as $\itr\to\infty$. As for the third term, since
\begin{equation}   \label{sumMDSbound}
\textstyle 
\sum_{\altitr=1}^{\infty}  \bigexpectation{\MDSn{\altitr}^2\cond \filtrationn{\altitr-1}  } 

\leq 
\frac{4\kk(\optrate\maxdimension)^2}{2^{2\kk}}   \sum_{\altitr=1}^{\infty}  \frac{ \stepsizen{\altitr}^2 }{\deltan{\altitr}^2}        
 \refereq{\reflasttrMXLiii{}}{<} 
 \infty ,
\end{equation}
\cite[Theorem 2.18]{hall80} applies with parameter $p=2$, and it follows that $\sum_{\altitr=1}^{\itr} \MDSn{\altitr}$ converges \as{} as $\itr\to\infty$. 
Finally, one can find a subsequence $\{\matn{\itr_\altitr}\}$ that converges to a point of $\limitpoints$ and thus satisfies $  \optrate - \rate{\matn{\itr_\altitr}} >  \varrho/2 $ for $\altitr$ large enough. It follows from \reflasttrMXLi{} that the second term  $\sum_{\altitr=1}^{\infty} \stepsizen{\itr} [   \rate{\matn{\itr}} - \rate{\optmat} ] \to-\infty$.

All in all we find that $\Lyapunov{\optmat}{\dualmatn{\itr}}\to-\infty$ \as{}, which is in contradiction with the nonnegativity of $\lyapunovfunction$. We infer that \eqref{liminfassumption} is true.


It remains to show that $\{\lyapunov{\optmat}{\dualmatn{\itr}}\}$ is almost surely convergent.


To do so we rely on
Doob's  convergence theorem for supermartingales \cite[Theorem 2.5]{hall80}.
Recalling \eqref{descentargumenttwo}, and using \eqref{trboundgradientestimateMO} and $\rate{\matn{\itr}} - \rate{\optmat}  \leq 0$, we find
\begin{equation}\label{nottightlyapunovdescentbound}
\begin{array}{l} 
\hspace{-1mm}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 { \,\leq\,}
\lyapunov{\optmat}{\dualmatn{\itr}}
{\,+\,}\MDSn{\itr} 
{\,+\,} 4\kk^2\meanlipschitz\stepsizen{\itr}\deltan{\itr}   {\,+\,} \frac{  \kk ( \optrate    \maxdimension\stepsizen{\itr})^2}{2^{2\kk{+}1}\strongly \deltan{\itr}^2 }
.
\end{array}
\end{equation}
Consider $\supermartn{\itr}=  \sum_{\altitr=\itr+1}^{\infty} [  4\kk^2\meanlipschitz\stepsizen{\altitr}\deltan{\altitr}   + {  \kk ( \optrate    \maxdimension\stepsizen{\altitr})^2}/({2^{2\kk{+}1}\strongly \deltan{\altitr}^2 })
] + \lyapunov{\optmat}{\dualmatn{\itr+1}} $. 
Under assumptions \reflasttrMXLii{} and \reflasttrMXLiii{}, $\supermartn{0}$ is  finite by construction.
We infer from \martingaledifference{} 
and \eqref{nottightlyapunovdescentbound} that $\expectation{\supermartn{\itr}\cond \filtrationn{\itr-1} } \leq \supermartn{\itr-1}$ for     $\itr\geq 1$,
and $\{\supermartn{\itr}\}$ is a supermartingale with respect to $\{ \filtrationn{\itr}\}$, thus satisfying $\Expectation{\supermartn{\itr} } \leq \supermartn{0} <\infty$.
Hence, $\{\supermartn{\itr}\}$ is uniformly $L^1$-bounded and Doob's theorem applies.  It follows that $\{\supermartn{\itr}\}$, and consequently $\{\lyapunov{\optmat}{\dualmatn{\itr}}\}$, are almost surely convergent, which completes the proof.

\end{proof}


}{ 
\cref{thm:trMXLiinew} is a consequence of \cref{lemma:bias,lemma:globaldescentargument}.
}

\begin{proof}[Proof of \cref{thm:trMXLiinew}]

\renewcommand{\dimensionk}[1]{\maxdimension}
\renewcommand{\meansqdimension}{\maxdimension}
\renewcommand{\meandimension}{\maxdimension}


By considering \cref{lemma:globaldescentargument}\eqref{lemma:globaldescentargumentiii} with the upper bounds $(\dimensionk{\nbk}\vbound)={  \dimensionk{\nbk}}  \optrate/({2^{\kk-1}\cstdelta})$ supplied by \eqref{trboundgradientestimateMO}, we find

\begin{equation} \label{basictroptrateboundmeanexpectation} 
\textstyle
\optrate -\Expectation{ \rate{ \meanmatn{T}} }
\refereq{\eqref{standardtroptrateboundmeanexpectation}}{\leq}


\frac{\kk\log\maxmm}{T \cststepsize } + 4\kk^2\meanlipschitz\cstdelta  + \frac{\kk   (\optrate\meansqdimension )^2 \cststepsize}{\strongly  2^{2\kk-1}  \cstdelta^2}
,
\end{equation} 
where  we have used $\lyapunov{\optmat}{\dualmatn{1}} \leq \kk\log\maxmm  $, and
 \begin{equation} 
 \label{basicazumabis}
\textstyle
\proba{\frac{1 }{ T\cststepsize  } \sum_{\itr=1}^{T}  \MDSn{\itr}  \leq \zmargin }
\refereq{\eqref{standardazumabis}}{\geq}
1-\exponential{-\frac{2^{2\kk-5} T\zmargin^2\cstdelta^2}{(\optrate \kk \meandimension)^2 }  }
.
\end{equation}
The right member of \eqref{basictroptrateboundmeanexpectation} is convex in $\vect{\cststepsize,\cstdelta}$ and minimized for the policy $\vect{\cststepsize,\cstdelta}=\vect{\stepsize\,T^{- 3/4},\delta\, T^{- 1 / 4}}$, where
\obsolete{
$$ a = \kk\log\maxmm, \ b = 4\kk^2\meanlipschitz  , \ c= \frac{\kk  (\optrate \meansqdimension)^2  }{\strongly  2^{2\kk-1}  } $$
$$
\sqrt{ \frac{2}{b\sqrt{c}}  } = \sqrt{ \frac{\sqrt{ \strongly  2^{2\kk-3}  } }{\meanlipschitz   \optrate \sqrt{ \kk^5   }\meansqdimension}  }  = \frac{1}{\sqrt{\meanlipschitz   \optrate}} \left(\frac{\strongly  2^{2\kk-3}}{\kk^5 \meansqdimension^2}\right)^{1/4}
$$

$$ \sqrt{ \frac{b\sqrt{c}}{2}  } = \sqrt{ \frac{\meanlipschitz   \optrate \sqrt{ \kk^5   }\meansqdimension}{\sqrt{ \strongly  2^{2\kk-3}  } }  } = \sqrt{\meanlipschitz   \optrate} \left(\frac{\kk^5 \meansqdimension^2}{\strongly  2^{2\kk-3}}\right)^{1/4}   $$

$$  f(\cststepsize,\cstdelta) =  \frac{a}{T \cststepsize } + b \cstdelta  +c \frac{\cststepsize}{  \cstdelta^2} $$
$$  -  \frac{a}{T \cststepsize^2} +c \frac{1}{  \cstdelta^2} =0 \Leftrightarrow \cststepsize = \sqrt{\frac{a}{cT}} \cstdelta  $$
$$   b  - 2 c \frac{\cststepsize}{  \cstdelta^3} = 0 \Leftrightarrow \cststepsize = \frac{b}{2c} \cstdelta^3  $$
$$ \Rightarrow  \cststepsize = \frac{b}{2c} \left(\sqrt{\frac{cT}{a}}\cststepsize\right)^3= \sqrt{ \frac{2c}{b} \left(\sqrt{\frac{a}{cT}}\right)^3 } $$
$$ \Rightarrow \cststepsize = \sqrt{ \frac{2}{b\sqrt{c}}  } \left(\frac a T\right)^{3/4}$$
$$ \Rightarrow \cstdelta =   \sqrt{\frac{cT}{a}} \cststepsize =  \sqrt{\frac{cT}{a}} \sqrt{ \frac{2}{b\sqrt{c}}  } \left(\frac a T\right)^{3/4} $$
$$ \Rightarrow \cstdelta =  \sqrt{ \frac{2\sqrt{c}}{b}  } \left(\frac a T\right)^{1/4}  $$
$$
\begin{array}{rl}
   f(\cststepsize,\cstdelta) 
   &=  
   \frac{a}{T \sqrt{ \frac{2}{b\sqrt{c}}  } \left(\frac a T\right)^{3/4} } + b \sqrt{ \frac{2\sqrt{c}}{b}  } \left(\frac a T\right)^{1/4}  +c \frac{\sqrt{ \frac{2}{b\sqrt{c}}  } \left(\frac a T\right)^{3/4}}{  \left(\sqrt{ \frac{2\sqrt{c}}{b}  } \left(\frac a T\right)^{1/4}\right)^2} 
\\   &=  
   \sqrt{ \frac{b\sqrt{c}}{2}  }\left(\frac a T\right)^{1/4} +  2 \sqrt{ \frac{b\sqrt{c}}{2}  } \left(\frac a T\right)^{1/4}  + \sqrt{ \frac{b\sqrt{c}}{2}  }  \left(\frac a T\right)^{1/4}
\\ &=
4 \sqrt{ \frac{b\sqrt{c}}{2}  } \left(\frac a T\right)^{1/4} .
\end{array}
$$

------------

$$ \Rightarrow \cststepsize 


=\sqrt{ \frac{\sqrtstrongly  2^{\kk}}{\meanlipschitz   \optrate \kk \meansqdimension}} \left(\frac{ \log\maxmm}{2}\right)^{3/4} T^{-3/4}
$$
$$ \Rightarrow \cstdelta 


=  2 \sqrt{\frac{\meanlipschitz   \optrate\kk^3 \meansqdimension}{\strongly  2^{\kk}}}   \left(\frac{\log\maxmm}{2}\right)^{1/4}  T^{-1/4}
$$
$$
\begin{array}{rl}
 \Rightarrow  f(\cststepsize,\cstdelta) 
 &=
8   \sqrt{ \frac{\meanlipschitz   \optrate \kk^3 \meansqdimension}{\strongly  2^{\kk}}}  \left(\frac{\log\maxmm}{2T}\right)^{1/4} .
\end{array}
$$

---------

\begin{equation} \label{optbasictroptrateboundmeanexpectation} 
\textstyle
\optrate -\Expectation{ \rate{ \meanmatn{T}} }
\leq
\left[
\frac{\kk\log\maxmm}{\stepsize} + 4\kk^2\meanlipschitz\, \delta  + \left(\frac{\kk   \meansqdimension^2  (\optrate)^2 }{\strongly  2^{2\kk-1}   }\right) \frac{\stepsize}{\delta^2 }
\right]  T^{- 1/4}
,
\end{equation}

}

\begin{equation}
 \textstyle
\stepsize 
=
\sqrt{ \frac{\sqrtstrongly  2^{\kk}}{\meanlipschitz   \optrate \kk \meansqdimension}} \left(\frac{ \log\maxmm}{2}\right)^{3/4} 
, \quad
\delta 
=
2 \sqrt{\frac{\meanlipschitz   \optrate\kk^3 \meansqdimension}{\strongly  2^{\kk}}}   \left(\frac{\log\maxmm}{2}\right)^{1/4}
.
\end{equation}
We find \eqref{troptrateboundmeanexpectation} by substituting $\cststepsize$ and $\cstdelta$ in \eqref{basictroptrateboundmeanexpectation} with the suggestion $\vect{\cststepsize,\cstdelta}=\vect{\stepsize\,T^{- 3/4},\delta\, T^{- 1 / 4}}$. Then, \eqref{troptrateboundmeaninterval} follows from \eqref{troptrateboundmeanexpectation} and \eqref{basicazumabis} after setting $ \cstdelta=\delta\, T^{- 1 / 4}$ in the right member of \eqref{basicazumabis}. 
Claims \eqref{thm:trMXLiifirst} and \eqref{thm:trMXLiisecond} have been shown.

\obsolete{ 
\begin{equation} 
\textstyle
\Proba{\frac{\sum_{\itr=1}^{T}  \MDSn{\itr}  }{ T\cststepsize  }  \leq \zmargin }
\refereq{\eqref{standardazumabis}}{\geq}
1-\Exponential{-\left[\frac{2^{2\kk-5} \delta^2}{\optrate^2 \kk^2 \meandimension^2 }\right]  \sqrt{T}\zmargin^2 }
.
\end{equation}
}

\end{proof}


\subsection{Analysis of the \ac{MXL+} algorithm}
\label{appendix:MXLzeroplus}

The $\magnitude{\delta}$ bound for the bias in \cref{lemma:bias} still holds when the \ac{SPSA}plus{} gradient estimator is used.
The offset in \eqref{estgradratekMO} allows us,  however, to derive an $\magnitude{1/\delta}$ bound for the norm, in place of the harmful $\magnitude{1/\delta}$ bound  inherent with \ac{SPSA}{}.


\obsolete{
For this, observe that the sequence generated by \eqref{MXL} satisfies
\begin{equation}\label{BIBO} \begin{array}{rcl}
\norm{\matn{\itr} -\matn{\itr-1} }


&\refereq{\globalnorm{}}{=}&
\sum_{\nbk=1}^{\kk} \norm{\matkn{\nbk}{\itr}-\matkn{\nbk}{\itr-1}} 
\\
&\refereq{\eqref{DAlipschitz}}{\leq}&
\sum_{\nbk=1}^{\kk} \oneoverstrongly  \dualnorm{ \stepsizen{\itr} \estgradkn{\nbk}{\itr-1} }
\\
&\refereq{\globaldualnorm{}}{=}&


\overstrongly{\kk  \stepsizen{\itr}} \dualnorm{ \estgradn{\itr-1}}
.
\end{array}
\end{equation}
 
}


\begin{lemma}
\label{lemma:norm}


If \ac{MXL+} is implemented under \eqref{deltacondition} and \eqref{generalfirstcondition}-\eqref{generalsecondcondition}, then $\dualnorm{\estgradkn{\nbk}{\itr}}$ is uniformly bounded 
for $\nbk=1,\dots,\kk$.

In particular, if $\vect{\stepsizen{\itr},\deltan{\itr}}=\vect{\stepsize \, \itr^{-\alpha},\delta\, \itr^{-\beta}}$ with 
\begin{equation}\textstyle 
\label{oldcondition}

\textup{(a)}\quad 0 \leq \beta \leq \alpha,
\qquad\quad

\textup{(b)} \quad \maxdimension \Lipschitz\kk \, \stepsize < 2 \strongly \, \delta ,
\end{equation}

then there is $\normbound{\alpha}{\beta}{\stepsize}{\delta}
{\,<\,}\infty$  such that  
$

\dualnorm{\estgradkn{\nbk}{\itr}}
{\,\leq\,} 

\frac{\dimensionk{\nbk}}{2}
\,\normbound{\alpha}{\beta}{\stepsize}{\delta}


$ 
holds for all $\itr$ and for $\nbk=1,\dots,\kk$ and, when $\beta=0$, \begin{equation} \label{normboundtwo}
\textstyle


\normbound{\alpha}{0}{\stepsize}{\delta}
=
\Big(  \frac{  \twotwitchFlipschitz \coef{\alpha}    \strongly}{\sqrt{\maxdimension}  } \Big) \left( \frac{2\strongly}{\maxdimension \Lipschitz\kk  } -  \frac{\stepsize  }{\delta} \right)^{-1}


.
\end{equation}


\end{lemma}


\begin{proof}[Proof of \cref{lemma:norm}]

With the convention $\offsetn{0}=  \rate{\matn{1}}$, we have, for $\nbk=1,\dots,\kk$,
\begin{equation}
\label{firstsecondmomentcomputation}
\nocolsep
\begin{array}{c}
\dualnorm{\estgradkn{\nbk}{1}}

 \refereq{\!\!\!\!\eqref{estgradratekMO}\!\!\!\!}{\leq}  
\frac{\dimensionk{\nbk}}{\deltan{1}} \modulus{  \rate{ \testmatn{1}} - \rate{\matn{1}} } \dualnorm{\zmatkn{\nbk}{1}}
\qquad\qquad\qquad\\\hfill


  \refereq{\eqref{lipschitz}}{\leq} 
\frac{\dimensionk{\nbk} \Lipschitz}{2\deltan{1}} \norm{  {\testmatn{1}}  - {\matn{1}}} 

 \refereq{\eqref{perturbatorbound}}{\leq} 
\mutehalftwitchFlipschitz \dimensionk{\nbk} \Lipschitz   \kk\sqrt{\maxdimension}  
,
\end{array}
\end{equation}

and it follows from \globaldualnorm{} that


$
\dualnorm{\estgradn{1}}
\leq \mutehalftwitchFlipschitz\maxdimension \Lipschitz \kk\sqrt{\maxdimension}   
$.


For $\itr\geq 2$,
\begin{equation}
\label{earlysecondmomentcomputation}
\nocolsep
\begin{array}{l}
\dualnorm{\estgradkn{\nbk}{\itr}}
 \refereq{\eqref{estgradratekMO}}{\leq}  
\frac{\dimensionk{\nbk}}{\deltan{1}} \modulus{  \rate{ \testmatn{\itr}} - \rate{ \testmatn{\itr-1}} } \dualnorm{\zmatkn{\nbk}{\itr}}
\\ \qquad \ 


\obsolete{
\leq
\frac{\dimensionk{\nbk}}{2\deltan{\itr}} \Big| [  \rate{ \testmatn{\itr}} - \rate{ \matn{\itr}} ]
\\ \hfill
+ [\rate{ \matn{\itr}} -\rate{ \matn{\itr-1}}] - [\rate{ \testmatn{\itr-1}}- \rate{ \matn{\itr-1}} ]\Big|
\\ \qquad \ 
}
\leq   
\frac{\dimensionk{\nbk}}{2\deltan{\itr}} \big[ \modulus{ \rate{ \testmatn{\itr}} - \rate{ \matn{\itr}} } 
+ \modulus{\rate{ \matn{\itr}} -\rate{ \matn{\itr-1}} } 
\\  \hfill
+ \modulus{\rate{ \testmatn{\itr-1}}- \rate{ \matn{\itr-1}} }\big]
\\ \qquad \ 
  \refereq{\eqref{lipschitz}}{\leq} 
\frac{\dimensionk{\nbk}}{2\deltan{\itr}} \big[\Lipschitz \norm{\testmatn{\itr} -  \matn{\itr} } +\Lipschitz \norm{\matn{\itr}-\matn{\itr-1}}
\\ \hfill
 +\Lipschitz \norm{ \testmatn{\itr-1}-  \matn{\itr-1} }\big]
\\ \qquad \ 
  \refereq{\eqref{perturbatorbound}}{\leq} 
\frac{\dimensionk{\nbk}\Lipschitz}{2\deltan{\itr}} \big[ \twitchFlipschitz \kk\sqrt{\maxdimension} (\deltan{\itr}+\deltan{\itr-1})+  \sum_{\nbk=1}^{\kk} \norm{\matkn{\nbk}{\itr}-\matkn{\nbk}{\itr-1}}  \big]
\\ \qquad \ 
 \refereq{\eqref{DAlipschitz}}{\leq} 
\frac{\dimensionk{\nbk}\Lipschitz}{2\deltan{\itr}} \big[\twitchFlipschitz \kk\sqrt{\maxdimension}  (\deltan{\itr}+\deltan{\itr-1})+ \overstrongly{\kk \stepsizen{\itr}} \dualnorm{ \estgradn{\itr-1} } \big]


\obsolete{
\\ \
 \refereq{\globaldualnorm{}}{\leq} 
\dimensionk{\nbk}\frac{1}{2}\Lipschitz\kk\sqrt{\maxdimension}  \twitchFlipschitz\left(1+\frac{\deltan{\itr-1}}{\deltan{\itr}}\right) 
\\ 
+ 
\frac{\dimensionk{\nbk}\Lipschitz\kk  \stepsizen{\itr}}{2\strongly\deltan{\itr}} \max_{\altnbk\in\{1,\dots,\kk\}}\dualnorm{ \estgradkn{\altnbk}{\itr-1} } 
}
,
\end{array}
\end{equation}

so that


$\textstyle
\dualnorm{\estgradn{\itr}}
\leq
\frac{\maxdimension \Lipschitz}{2\deltan{\itr}} [\twitchFlipschitz \kk\sqrt{\maxdimension}  (\deltan{\itr}{+}\deltan{\itr{-}1}) {+} \overstrongly{\kk \stepsizen{\itr}} \dualnorm{ \estgradn{\itr{-}1} } ] 
.$


With the convention $\deltan{0}=0$, we find, by induction on $\itr$,
\begin{equation}
\label{onesecondmomentcomputation}
\begin{array}{l}

\dualnorm{\estgradkn{\nbk}{\itr}}

 
 {\,\leq\,}
\mutehalftwitchFlipschitz \Lipschitz\kk\dimensionk{\nbk}\!\sqrt{\maxdimension}  
 \sum\nolimits_{\altitr=1}^{\itr}
\big( \frac{\maxdimension \Lipschitz\kk  }{2\strongly} \big)^{\itr{-}\altitr}  \prod\nolimits_{\altaltitr=\altitr+1}^{\itr}  \frac{\stepsizen{\altaltitr-1}}{\deltan{\altaltitr}}  \big(1{+}\frac{\deltan{\altitr-1}}{\deltan{\altitr}}\big)  
.
\end{array}
\end{equation}


Condition \eqref{generalsecondcondition} tells us that ${\deltan{\itr-1}}/{\deltan{\itr}}$ is uniformly bounded by a finite constant, say, $c<\infty$, while \eqref{generalfirstcondition} rewrites as
\begin{equation}\textstyle
q \defeq \frac{{\maxdimension} \Lipschitz\kk }{2\strongly} \, \big( \sup_{\itr\geq 2} \frac{\stepsizen{\itr-1}}{\deltan{\itr} }  \big) <1 .
\end{equation}
Using $\frac{\stepsizen{\itr-1}}{\deltan{\itr}}\leq \frac{ 2 \strongly q}{\maxdimension \Lipschitz\kk}$ and $\frac{\deltan{\itr-1}}{\deltan{\itr}}\leq c$ in \eqref{onesecondmomentcomputation}, we find, for $\itr\geq 2$,
\begin{equation}
\label{newsecondmomentcomputation}
\begin{array}{l}
\frac{\dualnorm{\estgradkn{\nbk}{\itr}}}{\mutehalftwitchFlipschitz \Lipschitz\kk\dimensionk{\nbk}\sqrt{\maxdimension} }
\leq 

 \sum_{\altitr=1}^{\itr}q^{\itr-\altitr} \left(1+c\right)  


= 
(1+c)\frac{1-q^{\itr}}{1-q}
\leq
\frac{1+c}{1-q}
.


\end{array}
\end{equation}


Under the policies $\stepsizen{\itr}=\stepsize \, \itr^{-\alpha}$  and $\deltan{\itr}=\delta\, \itr^{-\beta}$, \eqref{onesecondmomentcomputation} becomes
\begin{equation} \label{twosecondmomentcomputation}
\begin{array}{l}
\dualnorm{\estgradkn{\nbk}{\itr}}


 \leq
\mutehalftwitchFlipschitz\coef{\alpha}\dimensionk{\nbk} \Lipschitz 
\kk\sqrt{\maxdimension}  \sum\nolimits_{\altitr=1}^{\itr}\left( \frac{\stepsize\maxdimension \Lipschitz\kk  }{2\delta\strongly} \right)^{\itr-\altitr} \left( \frac{\itr}{\altitr}\right)^\beta \left[    \frac{ \factorial{(\itr-1)}}{ \factorial{(\altitr-1)}} \right]^{\beta-\alpha} 

,
\end{array}
\end{equation}
where $\coef{\alpha}=1+2^\alpha$. Under  Condition \oldsecondcondition{} 


the last factor is no larger than $1$, and we 
obtain the uniform bound with

\begin{equation}\label{normbound}  
\textstyle 
\normbound{\alpha}{\beta}{\stepsize}{\delta}
=
 \twitchFlipschitz\Lipschitz (1+2^\alpha)\kk\sqrt{\maxdimension}   \sum_{\altitr=1}^{\infty}\big[ \frac{\stepsize\maxdimension \Lipschitz\kk  }{2\delta\strongly} \big]^{\itr-\altitr} \big( \frac{\itr}{\altitr}\big)^\beta,
\end{equation} 
which is finite on condition that \oldfirstcondition{} holds. 
For $\beta=0$,
 \eqref{normbound} 
reduces to a geometric series and \eqref{normboundtwo} follows directly.


\end{proof}


  

We are now able to show \cref{thm:lasttrMXLMO} and \cref{timecomplexity:trMXLMO}. Again, the Lyapunov function \eqref{lyapunov} and \cref{lemma:globaldescentargument} are used.

\showMXLzerolastiterate{
\begin{proof}[Proof of \cref{thm:lasttrMXLMO}]

Proceed as in the proof of \cref{thm:lasttrMXL}, now with assumptions \trconditionstepsize{}, \trconditionsquared{} and \eqref{trconditionbias} in place of \reflasttrMXLi{}, \reflasttrMXLii{}, \reflasttrMXLiii{}.
Because the conditions of \cref{lemma:norm} are met, there exists $ \cstnormbound <\infty$ such that $  \dualnorm{\estgradkn{\nbk}{\itr}}< \cstnormbound$ for all $k$, so that \eqref{adabsurdumlyapunovdescentbound} and \eqref{nottightlyapunovdescentbound} respectively become, for some~$\optmat\in\optMat$,
\begin{equation} \label{adabsurdumlyapunovdescentboundplus} 
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunov{\optmat}{\dualmatn{1}} - \sum_{\altitr=1}^{\itr} \stepsizen{\altitr} \left[\optrate-\rate{\matn{\altitr}}\right]
\quad
\\
\hfill 
+  \sum_{\altitr=1}^{\itr}\MDSn{\altitr}  + 4\kk^2 \meanlipschitz \sum_{\altitr=1}^{\itr} \stepsizen{\altitr}\deltan{\altitr}  +\frac{\kk   \cstnormbound^2}{2\strongly} \sum_{\altitr=1}^{\itr} \stepsizen{\altitr}^2 
,
\end{array}
\end{equation}
with

$
\sum_{\altitr=1}^{\infty}  \Expectation{\MDSn{\altitr}^2\cond \filtrationn{\altitr-1}  } 

\leq   
\left(4\kk  \cstnormbound\right)^2  \sum_{\altitr=1}^{\infty}   \stepsizen{\altitr}^2   
 
 <
 \infty 
$, 
and
\begin{equation}\label{nottightlyapunovdescentboundplus}
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunov{\optmat}{\dualmatn{\itr}}+  \MDSn{\itr} 
+ 4\kk^2\meanlipschitz\stepsizen{\itr}\deltan{\itr}   + \frac{\kk   \cstnormbound^2}{2\strongly} \stepsizen{\itr}^2
.
\end{array}
\end{equation}
Thus, $\supermartn{\itr}=\lyapunov{\optmat}{\dualmatn{\itr+1}}  +  \sum_{\altitr=\itr+1}^{\infty} [  4\kk^2\meanlipschitz\stepsizen{\altitr}\deltan{\altitr}   + \oneoverstrongly\kk   \cstnormbound^2\stepsizen{\altitr}^2/2 ]$ now defines the supermartingale with respect to $\{ \filtrationn{\itr}\}$.

\end{proof}

}{

\begin{proof}[Proof of \cref{thm:lasttrMXLMO}]
Following the line of thought of the proof of \cite[Theorem 5.1]{BLM18}, we first show that
\begin{equation} \label{liminfassumption}
\textstyle
\liminf_{\itr\to\infty} \Lyapunov{\optmat}{\dualmatn{\itr}} =0
\quad
\as \, .
\end{equation}
Next, we see that $\{\lyapunov{\optmat}{\dualmatn{\itr}}\}$ converges almost surely (\as{}) towards a finite quantity which, in view of \eqref{liminfassumption}, can only be $0$. \As{} convergence of $\{\matn{\itr}\}$ can then be inferred from \cref{lemma:fenchel}-\eqref{fenchelstronglyconvex}.


The assumption of  non-increasing $\{\deltan{\itr}\}$, together with \trconditionstepsize{} and \eqref{trconditionbias}, implies $\deltan{\itr}\downarrow 0$ which, in view of \eqref{perturbatorbound}, secures \as{} convergence of $\{\testmatn{\itr}\}$ as well.

First observe that \eqref{liminfassumption} holds if, almost surely, there exists a subsequence of $\{\matn{\itr}\}$ that converges towards $\optmat$.


Suppose this condition not to hold, and let $\limitpoints$ denote the set of the limit points of all  subsequences of $\{\matn{\itr}\}$. 


Then, almost surely, we have $\optmat\notin \limitpoints$ and, since $\limitpoints$ is closed 
by construction and $\ratefunction$ is continuous and strictly convex, 
$ \varrho \defeq \rate{\optmat} - \max_{\mat\in \limitpoints}{\rate{\mat}}>0$.
\obsolete{
we can write
\begin{equation}\label{compactset}\begin{array}{c}
\max_{\mat\in \limitpoints}{\rate{\mat}} = \rate{\optmat} - \varrho, \textup{ with }\varrho>0 \ \as{} \, .
\end{array}\end{equation}
}

\obsolete{
\footnotetext{Indeed, suppose there is  a sequence $\{\compactmatn{\altitr}\}$ in $\limitpoints$ converging to $\compactmatn{\infty}\notin \limitpoints$. For any be any sequence of positive numbers $\{\epsilon_\altitr\}$ with $\epsilon_\altitr\downarrow 0$, one can find $\{\matn{\itr_\altitr}\}$, subsequence of $\{\matn{\itr}\}$, such that $\norm{\matn{\itr_\altitr}-\compactmatn{\altitr}}<\epsilon_\altitr$ for all $\altitr$. Hence, $\matn{\itr_\altitr}\to\compactmatn{\infty}$ and we reach the contradiction $\compactmatn{\infty} \in \limitpoints$.}
}


Because the conditions of \cref{lemma:norm} are met, there exists $ \cstnormbound <\infty$ such that $  \dualnorm{\estgradkn{\nbk}{\itr}}< \cstnormbound$ for all $k$.

By telescoping \eqref{descentargumenttwo}  in  \cref{lemma:globaldescentargument}\eqref{lemma:globaldescentargumenti}, we find
\begin{equation} \label{adabsurdumlyapunovdescentboundplus} 
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunov{\optmat}{\dualmatn{1}} - \sum_{\altitr=1}^{\itr} \stepsizen{\altitr} \left[\optrate-\rate{\matn{\altitr}}\right]
\quad\
\\
\hfill 
+  \sum_{\altitr=1}^{\itr}\MDSn{\altitr}  + 4\kk^2 \meanlipschitz \sum_{\altitr=1}^{\itr} \stepsizen{\altitr}\deltan{\altitr}  +\frac{\kk   \cstnormbound^2}{2\strongly} \sum_{\altitr=1}^{\itr} \stepsizen{\altitr}^2 
,
\end{array}
\end{equation}
where $\{\MDSn{\itr}\}$ is the difference sequence of a martingale  with respect to the filtration $\{\filtrationn{\itr}\}$.


\obsolete{

If we decompose $\estgradkn{\nbk}{\itr}$ as in \eqref{estimatordecomposition} and define $\MDSn{\itr}$ as in \eqref{MDSn}
, then it follows from \eqref{earlydeviationbound} that
\begin{equation} \label{modulusMDSn}
\textstyle
\modulus{\MDSn{\itr}} 
\leq 
2\stepsizen{\itr} \sum_{\nbk=1}^{\kk}  \dualnorm{  \devmatkn{\nbk}{\itr}} 
\leq 
4\kk   \cstnormbound \, \stepsizen{\itr}
.
\end{equation}

By telescoping \eqref{descentargumenttwo}, we find

\begin{equation}\label{adabsurdumlyapunovdescentboundplus}
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
\leq
\lyapunov{\optmat}{\dualmatn{1}} - \sum_{\altitr=1}^{\itr} \stepsizen{\altitr} \left[\optrate-\rate{\matn{\altitr}}\right]
\qquad
\\
\hfill 
+  \sum_{\altitr=1}^{\itr}  \MDSn{\altitr} 
+ 4\kk^2\meanlipschitz \sum_{\altitr=1}^{\itr} \stepsizen{\altitr}\deltan{\altitr}   +   \frac{ \kk \cstnormbound^2}{2\strongly}\sum_{\altitr=1}^{\itr} \stepsizen{\altitr}^2 
,
\end{array}
\end{equation}  
where $\MDSn{\altitr}= \stepsizen{\altitr} \sum_{\nbk=1}^{\kk}   \inner{ \devmatkn{\nbk}{\altitr}}{\matkn{\nbk}{\altitr}-\optmatk{\nbk}} $
satisfies \martingaledifference{} 
and \eqref{modulusMDSn}, so that $\{\MDSn{\itr}\}$ is the difference sequence of a martingale  with respect to the filtration $\{\filtrationn{\itr}\}$. 


}


In view of assumptions \trconditionsquared{} and \eqref{trconditionbias},  the last two terms in the second member of \eqref{adabsurdumlyapunovdescentboundplus} converge as $\itr\to\infty$. As for the third term, since
\begin{equation}\label{sumMDSboundplus}
\textstyle
\sum_{\altitr=1}^{\infty}  \Expectation{\MDSn{\altitr}^2\cond \filtrationn{\altitr-1}  } 

\leq   
\left(4\kk  \cstnormbound\right)^2  \sum_{\altitr=1}^{\infty}   \stepsizen{\altitr}^2   
 \refereq{\trconditionsquared}{<} \infty ,
\end{equation}
\cite[Theorem 2.18]{hall80} applies with parameter $p=2$, and it follows that $\sum_{\altitr=1}^{\itr} \MDSn{\altitr}$ converges \as{} as $\itr\to\infty$. 
Finally, one can find a subsequence $\{\matn{\itr_\altitr}\}$ that converges to a point of $\limitpoints$ and thus satisfies $  \rate{\optmat} - \rate{\matn{\itr_\altitr}} >  \varrho/2 $ for $\altitr$ large enough. It follows from \trconditionstepsize{} that the second term  $\sum_{\altitr=1}^{\infty} \stepsizen{\itr} [   \rate{\matn{\itr}} - \rate{\optmat} ] \to-\infty$.

All in all we find that $\Lyapunov{\optmat}{\dualmatn{\itr}}\to-\infty$ \as{}, which is in contradiction with the nonnegativity of $\lyapunovfunction$. We infer that \eqref{liminfassumption} is true.


It remains to show that $\{\lyapunov{\optmat}{\dualmatn{\itr}}\}$ is almost surely convergent.


To do so we rely on
Doob's  convergence theorem for supermartingales \cite[Theorem 2.5]{hall80}.
Recalling \eqref{descentargumenttwo}, and using $  \dualnorm{\estgradkn{\nbk}{\itr}}^2< \cstnormbound$ and $\rate{\matn{\itr}} - \rate{\optmat}  \leq 0$, we find
\begin{equation}\label{nottightlyapunovdescentboundplus}
\begin{array}{l}
\lyapunov{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunov{\optmat}{\dualmatn{\itr}}+  \MDSn{\itr} 
+ 4\kk^2\meanlipschitz\stepsizen{\itr}\deltan{\itr}   + \frac{\kk   \cstnormbound^2}{2\strongly} \stepsizen{\itr}^2
.
\end{array}
\end{equation}
Let $\supermartn{\itr}=\lyapunov{\optmat}{\dualmatn{\itr+1}}  +  \sum_{\altitr=\itr+1}^{\infty} [  4\kk^2\meanlipschitz\stepsizen{\altitr}\deltan{\altitr}   + \oneoverstrongly\kk   \cstnormbound^2\stepsizen{\altitr}^2/2 ]$. 
Note that, under assumptions \trconditionsquared{} and \eqref{trconditionbias}, $\supermartn{0}$ is  finite by construction.
We infer from \\martingaledifference{} 
and \eqref{nottightlyapunovdescentboundplus} that $\expectation{\supermartn{\itr}\cond \filtrationn{\itr-1} } \leq \supermartn{\itr-1}$ for     $\itr\geq 1$,
\obsolete{
\begin{equation} \label{supermartingale}

\expectation{\supermartn{\itr}\cond \filtrationn{\itr-1} } \leq \supermartn{\itr-1} \quad( \itr\geq 1)

\end{equation}
}
and $\{\supermartn{\itr}\}$ is a supermartingale with respect to $\{ \filtrationn{\itr}\}$, thus satisfying $\Expectation{\supermartn{\itr} } \leq \supermartn{0} <\infty$.
\obsolete{
Under assumptions \trconditionsquared{} and \eqref{trconditionbias}, we find, for $\itr\geq2$,
\begin{equation}
\nocolsep
\begin{array}{rcl}
\Expectation{\supermartn{\itr} } 
&=&
 \Expectation{\cdots\Expectation{\Expectation{\supermartn{\itr}\cond \filtrationn{\itr-1} }\cond \filtrationn{n-2} }\cdots\cond \filtrationn{0} } 
\\&\leq& 
 \supermartn{0} 
\\ &=&
\lyapunov{\optmat}{\dualmatn{1}}  + 4\kk^2\meanlipschitz \sum_{\altitr=1}^{\infty} \stepsizen{\altitr}\deltan{\altitr}   + \frac{\kk   \cstnormbound^2}{2\strongly} \sum_{\altitr=1}^{\infty}  \stepsizen{\altitr}^2
\\ &<&
\infty
.
\end{array}
\end{equation}
}
Hence, $\{\supermartn{\itr}\}$ is uniformly $L^1$-bounded and Doob's theorem applies.  It follows that $\{\supermartn{\itr}\}$, and consequently $\{\lyapunov{\optmat}{\dualmatn{\itr}}\}$, are almost surely convergent, which completes the proof.

\end{proof}

}


\begin{proof}[Proof of \cref{timecomplexity:trMXLMO}]

\eqref{thm:trMXLMOi}
\obsolete{
Since  under our assumptions \cref{lemma:norm} applies, \eqref{threesecondmomentcomputation} gives us the bound

\begin{equation}\label{totalnormbound}
\textstyle
\sum_{\nbk=1}^{\kk}   \dualnorm{\estgradkn{\nbk}{\itr}}^2
\refereq{\eqref{threesecondmomentcomputation}}{\leq}
\frac{\kk}{4} \maxdimension^2 \, 
 [\normbound{\alpha}{\beta}{\stepsize}{\delta}]^2
 ,
\end{equation}
where $\normbound{\alpha}{\beta}{\stepsize}{\delta}$ is given by \eqref{normbound}.

By combining \eqref{totalnormbound} with \eqref{expectationyergodicaverageidentity} in \cref{lemma:globaldescentargument}\eqref{lemma:globaldescentargumentii}, we find, for $\vect{\stepsizen{\itr},\deltan{\itr}}=\vect{\cststepsize\,\itr^{-\alpha},\cstdelta\,\itr^{-\beta}}$,
}


By combining 
the uniform bound in \cref{lemma:norm}
with \eqref{expectationyergodicaverageidentity} in \cref{lemma:globaldescentargument}\eqref{lemma:globaldescentargumentii} and using $\lyapunov{\optmat}{\dualmatn{1}} \leq \kk\log\maxmm  $, we find, for the  policy $\vect{\stepsizen{\itr},\deltan{\itr}}=\vect{\cststepsize\,\itr^{-\alpha},\cstdelta\,\itr^{-\beta}}$,
\begin{equation}\label{ergodicaverageidentitythree}
\begin{array}{l}
\optrate  -\bigexpectation{ \rate{ \meanmatn{\itr}}}
\leq
\frac{
 \kk\log\maxmm
}{
\stepsize\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} 
} 
+ 4\kk^2\meanlipschitz\delta\frac{
\sum_{\altitr=1}^{\itr}\altitr^{-\alpha-\beta} 
}{
\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} 
}
\qquad \quad\\\hfill
  + \frac{\kk \maxdimension^2[\normbound{\alpha}{\beta}{\stepsize}{\delta}]^2 \stepsize}{8\strongly} \frac{
 \sum_{\altitr=1}^{\itr} \altitr^{-2\alpha}  
}{
\sum_{\altitr=1}^{\itr} \altitr^{-\alpha} 
} 
,
\end{array}
\end{equation}

where $\normbound{\alpha}{\beta}{\stepsize}{\delta}$ is given by \eqref{normbound}.

The above upper bound is minimized for $\alpha=\beta=1/2$, in which case we find \eqref{asymptoticrate}.


 \eqref{thm:trMXLMOiinew}
 
 \renewcommand{\dimensionk}[1]{\maxdimension}
\renewcommand{\meansqdimension}{\maxdimension}
\renewcommand{\meandimension}{\maxdimension}

Using  \cref{lemma:globaldescentargument}\eqref{lemma:globaldescentargumentiii}  under $\vect{\cststepsize,\cstdelta}=\vect{\stepsize/\sqrt{T},\delta/\sqrt{T}}$ and with the 
bounds  

$\vbound= \frac{1}{2}
\,\normbound{0}{0}{\cststepsize}{\cstdelta} $, given by \cref{lemma:norm}, 
yields

\begin{equation} \label{ergodicaverageidentityconstant} 
\textstyle
\optrate -\bigexpectation{ \rate{ \meanmatn{T}} }
 \refereq{\eqref{standardtroptrateboundmeanexpectation}}{\leq}

 \frac{\kk\log\maxmm}{\stepsize\sqrt{T} } 
+ \frac{4\kk^2\meanlipschitz\delta  }{\sqrt{T}}
+ \frac{  \kk \dimensionk{\nbk}^2  [
\,\normbound{0}{0}{\frac{\stepsize}{\sqrt{T}}}{\frac{\delta}{\sqrt{T}}}]^2\stepsize }{8\strongly\sqrt{T} }

\end{equation}
where $
\textstyle
\normbound{0}{0}{\cststepsize}{\cstdelta}
=
\big(  \frac{ \fourtwitchFlipschitz     \strongly}{\sqrt{\maxdimension}  } \big) \big( \frac{2\strongly}{\maxdimension \Lipschitz\kk  } -  \frac{\stepsize  }{\delta} \big)^{-1} 
$,
and
 \begin{equation} 
 \label{basicazumabissecond}
\textstyle
\Bigproba{\frac{\sum_{\itr=1}^{T}  \MDSn{\itr}  }{ \sqrt{T}\,\stepsize  }  \leq \zmargin }
\refereq{\eqref{standardazumabis}}{\geq}
1-\Bigexponential{-\frac{T\zmargin^2}{8   \kk^2 \meandimension^2  [  
\,\normbound{0}{0}{\frac{\stepsize}{\sqrt{T}}}{\frac{\delta}{\sqrt{T}}}  ]^2 }}
.
\end{equation}   
We find \eqref{trsimplerateboundmeanexpectation}  after substituting $\normbound{0}{0}{\cststepsize}{\cstdelta}$ with its actual value in \eqref{ergodicaverageidentityconstant}. Then,   \eqref{trsimplerateboundmeaninterval} follows from \eqref{trsimplerateboundmeanexpectation} and \eqref{basicazumabissecond}.
\end{proof} 

The proof of Corollary \ref{convergenceratres:trMXLMO} relies on the following lemma.


\begin{lemma}\label{lemma:optimization}
Let $\Gamma = \{ (\stepsize,\delta)\in\Realplus\times\Realplus : \stepsize< h \delta \}$ and consider the function $\genericfunction:\Gamma \mapsto\Real$ defined by
\begin{equation} \label{newresidualfunction}
\textstyle


\generic{\stepsize,\delta} = \frac{a}{\stepsize} + 2 b \delta + c \stepsize \, \big( h - \frac{ \stepsize }{\delta }\big)^{-2} + d\, \big( h - \frac{ \stepsize }{\delta }\big)^{-1},
\end{equation}

\obsolete{
\begin{equation} 
\textstyle
\mom{\stepsize}{\delta} = 
\left( h - \frac{ \stepsize }{\delta }\right)^{-1}
,
\end{equation}
}

where $a,b,c,h>0 $ and $d\geq 0$ are given parameters. 
 
\begin{enumerate}[(i),ref=\roman*,wide,labelwidth=!,labelindent=5pt]
 \item \label{lemma:optimizationi} 
At the point $(\stepsize^*,\delta^*)\in\Gamma$, where
\begin{equation} \label{earlyoptimalpolicyMO}
\textstyle
\stepsize^* {\,=\,}


{h}\, \bigg[{\sqrt{\frac c a}+ {\sqrt{{\sqrt{\frac c a}} \Big(\frac{ 2  b h  }{2\sqrt{ac}+d } \Big) }}}\bigg]^{-1}
,
\ \ \
\delta^* {\,=\,}


\sqrt{\sqrt{\frac{a}{c}}\Big(\frac{2\sqrt{ac}+d }{  2  b h    }\Big)}
,
\end{equation}
the value of $f$ is given by
\begin{equation} \label{boundfMO}
\textstyle

\generic{\stepsize^*,\delta^*}
 =


\frac{2\sqrt{ac}+d}{h} +2 \sqrt{ 2b\sqrt{\frac{a}{c}} \Big( \frac{2\sqrt{ac}+d}{h} \Big)  }

.
\end{equation}
Under the constraint $\delta/\sqrt{\itr}<\radius$, where $\radius>0$, \eqref{boundfMO} holds for 
\begin{equation} \label{conditionondeltaMO}
\textstyle
\itr >

 \sqrt{\frac a c}\,\Big(\frac{2\sqrt{ac}+d}{2bh}\Big)\, \radius^{-2} .
\end{equation}


\item \label{lemma:optimizationii}
For any $\errortolerance{\,>\,}0$, $\generic{\stepsize^*,\delta^*}/\sqrt{\itr}\leq\errortolerance$ holds for $\itr\geq T$ if $T{\,=\,} [\generic{\stepsize^*,\delta^*}/\errortolerance]^{2}$.
\obsolete{
\begin{equation} \label{optimaltimeMO}
\nocolsep
\begin{array}{c} 


T= \left[ \frac{2\sqrt{ac}+d}{h} +2 \sqrt{ 2b\sqrt{\frac{a}{c}} \left[ \frac{2\sqrt{ac}+d}{h} \right]  } \right]^2 \errortolerance^{-2}
.
\end{array}
\end{equation}.
}
The constraint $\delta^*{/}\sqrt{T}{\,<\,}\radius$ 
then rewrites as
\begin{equation} \label{newconditionondeltaMO}
\textstyle


\errortolerance < \bigg(4b + \sqrt{2({b}/{h}) \sqrt{{c}/{a}} \, ( 2\sqrt{ac}+d) } \bigg) \, r
.
\end{equation}
\end{enumerate}
\end{lemma}

\begin{proof}  Verification of all the claims is straightforward.
\end{proof}


\obsolete{

\begin{proof}
\eqref{lemma:optimizationi} 
 Rewrite \eqref{newresidualfunction} as $f(\stepsize,\delta)=g(\stepsize,\delta,\mom{\stepsize}{\delta})$, where
$g(\stepsize,\delta,\mome) = {a}/{\stepsize} + 2 b \delta + c \stepsize \mome^{2}
+  d  \mome
$.
\obsolete{
\begin{equation} \label{rewrittenresidualfunction}
g(\stepsize,\delta,\mome) = \frac{a}{\stepsize} + 2 b \delta + c \stepsize \mome^{2}
+  d  \mome.
\end{equation}
}
Function $g$ is convex and its coordinate minima with respect to direction $\stepsize$ lie at the points $(\tilde\stepsize(\mome),\delta,\mome)$ such that $\tilde\stepsize(\mome) = \mome^{-1} \sqrt{a/c}$. Under the constraint $\mome=\mom{\tilde\stepsize(\mome)}{\delta}$, which rewrites as $\delta=\tilde\delta(\mome) \defeq \tilde\stepsize(\mome)/(h-\mome^{-1}) =  (h\mome-1)^{-1}\sqrt{a/c}\, $, we find 
\begin{equation}
\textstyle
g(\tilde\stepsize(\mome),\tilde\delta(\mome),\mome) 
=


 (2\sqrt{ac}+d)\mome  + \frac{ 2 b \sqrt{a/c} }{h\mome-1} 
,
\end{equation}
which takes its minimal value for
\begin{equation}\textstyle
\mome^* =

\frac 1 h \left( 1+ \sqrt{ \sqrt{\frac{a}{c}}\frac{ 2  bh  }{2\sqrt{ac}+d } } \right)  
.
\end{equation}
\obsolete{
\begin{equation}
g(\tilde\stepsize(\mome^*),\tilde\delta(\mome^*),\mome^*) 
= 
  \frac{2\sqrt{ac}+d}{h} +2 \sqrt{ 2b\sqrt{\frac{a}{c}} \left[ \frac{2\sqrt{ac}+d}{h} \right]  }    
\end{equation}
}

Setting $\stepsize^*=\tilde\stepsize(\mome^*)$ and $\delta^*=\tilde\delta(\mome^*)$ yields \eqref{earlyoptimalpolicyMO} and \eqref{boundfMO}.

The additional constraint $\delta/\sqrt{\itr}<\radius$ is satisfied by \eqref{earlyoptimalpolicyMO} for as long as \eqref{conditionondeltaMO}
holds.


\obsolete{

\begin{equation} 
\itr^{-\frac 1 2} =  \frac{e \generic{\stepsize^*,\delta^*}}{ \sqrt{2\sqrt{ac}+d} \left[\sqrt{2\sqrt{ac}+d}  + 2 \sqrt{ 2b\sqrt{\frac a c} } \right] }  
.
\end{equation}

\begin{equation} 
\begin{array}{l}
\stepsize^* =  

 \frac{e^2  \sqrt{\frac a c} \generic{\stepsize^*,\delta^*}}{ 
2\sqrt{ac}+d
+
 4b\sqrt{e} 
+
\sqrt{2\sqrt{ac}+d}   \left[  \sqrt{  2  b e \sqrt{\frac c a}  }  + 2 \sqrt{ 2b\sqrt{\frac a c} }\right]
}  
,
\\
\delta^* =  \frac{\sqrt{e}}{4b +\sqrt{ 2  b  \sqrt{\frac c a}(2\sqrt{ac}+d)}  }  \,  \generic{\stepsize^*,\delta^*}
,
\end{array}  
\end{equation}

\begin{equation} 
\begin{array}{l}
\stepsize^* =
 \frac{ e }{  \sqrt{ \sqrt{\frac c a} \left(\frac{2\sqrt{ac}+d }{ 2  b e  } \right) }+1 }
\,\delta^*,
\\
\delta^*  \left[ \sqrt{\frac c a} \left(\frac{ 2  b e  }{2\sqrt{ac}+d } \right) \right]^{\frac 1 2} = \itr^{-\frac 1 2} 
,
\end{array}  
\end{equation}

}


Claim \eqref{lemma:optimizationii} follows from \eqref{earlyoptimalpolicyMO} and \eqref{boundfMO} after setting  $\generic{\stepsize^*,\delta^*}=\sqrt{T}\, \errortolerance$.
\obsolete{
Set $\generic{\stepsize^*,\delta^*}=\sqrt{T}\, \errortolerance$ in \eqref{boundfMO}. 
We get \eqref{optimaltimeMO} by solving the result for $T$ as a function of $\errortolerance$, and the claim follows.
Besides, by combining \eqref{earlyoptimalpolicyMO} with \eqref{optimaltimeMO}, we find
\begin{equation} \label{optimalpolicyMO}
\begin{array}{c}
\frac{\delta^*}{\sqrt{T}} = 


\frac{ \sqrt[4]{{a}/{c}} }{\sqrt{2b(2\sqrt{ac}+d)/h} +4b \sqrt[4]{{a}/{c}} } \,  \errortolerance
,
\end{array}
\end{equation}
and the constraint $\delta^*/\sqrt{T}<\radius$ rewrites as \eqref{newconditionondeltaMO}.

}


\end{proof}
 

}


\begin{proof}[Proof of Corollary \ref{convergenceratres:trMXLMO}]

\eqref{cr:trMXLMOi}
To derive $\stepsize$ and $\delta$  in \eqref{cr:trMXLMOi} it suffices to apply \cref{lemma:optimization}\eqref{lemma:optimizationi} to the expression for $\Bcoefficient{\stepsize}{\delta}$ given in  \cref{timecomplexity:trMXLMO}\eqref{thm:trMXLMOiifirst}. The convergence rate of $\expectation{ \rate{ \meanmatn{T}} }$ follows from \eqref{troptrateboundmeanexpectation} and \eqref{boundfMO}, while the condition on $T$ is a translation of \eqref{conditionondeltaMO} into the present setting, where the restriction $\delta/\sqrt{\altitr}<\radiusk{\nbk}$ for all $\nbk$ applies, with $\radiusk{\nbk}$ given by \eqref{radius}. 

\eqref{cr:trMXLMOii}
Recall \cref{timecomplexity:trMXLMO}\eqref{thm:trMXLMOiisecond}.  The second part of \eqref{troptrateboundmeaninterval} rewrites as $1-\errorproba$ for
$ \textstyle

 \zmargin  
 = 

16 \halftwitchFlipschitz  \strongly    \left[ \frac{2\strongly}{ \Lipschitz\kk (\maxmm^2-1) } -  \frac{\stepsize  }{\delta} \right]^{-1}  \sqrt{2\,\logarithm{\frac 1 \errorproba}\kk^2(\maxmm^2-1) / T}      
 .   
$
Observe that $\Bcoefficient{\stepsize}{\delta}+\zmargin\sqrt{T}$ is an instance of the function $\generic{\stepsize,\delta}$ defined in \eqref{newresidualfunction}. \cref{lemma:optimization}\eqref{lemma:optimizationii} gives us a condition on $T$ for $\Bcoefficient{\stepsize}{\delta}/\sqrt{\ceil T}+\zmargin\leq \errortolerance$ to be true which, in view of \eqref{troptrateboundmeaninterval}, is also sufficient for \eqref{standardtroptrateboundmeaninterval} to hold.
After computations we find 

the value of $T$ in Table \ref{table:convergenceratres:trMXLMO}\ref{cr:trMXLMOii} 
with the restriction on $\errortolerance$:

\begin{multline*}
\txs

\errortolerance 
\refereq{\!\eqref{newconditionondeltaMO}\!}{{\,<\,}}


2^{\frac{9}{4}}\meanlipschitz 
	\bracks*{\renrmlzdcsteps{\errorproba}
	\sqrt{\halftwitchFlipschitz \Lipschitz / \meanlipschitz}  {+} \frac{2^{\frac 3 4}  }{ \sqrt[4]{\log(1/\errorproba)}  [\maxmm^2-1]} }
	\\
	\times \sqrt{\frac{ \sqrt{\log(1/\errorproba)} \kk^4 [\maxmm{+}1][\maxmm^2{-}1]}{\maxmm}}.
\qedhere
\end{multline*}
\end{proof}


\subsection{Analysis of the \randomMXLzeroplus{} algorithm}
\label{appendix:randomMXLzeroplus}


Lemmas \ref{lemma:bias} and \ref{lemma:norm} still apply in the asynchronous setting. 
Instead of \eqref{lyapunov} we use the Lyapunov function
\begin{equation} \label{randomlyapunov}
\textstyle
\lyapunovprob{\prob}{\optmat}{\dualmat} = \sum_{\nbk=1}^{\kk} \frac{1}{\probk{\nbk}}\fenchel{\optmatk{\nbk}}{\dualmatk{\nbk} } ,
\end{equation}
where $\optmat\in\optMat$ is a solution.

Proceeding as for the derivation of \eqref{earlydescentargumenttwo}    in  \cref{lemma:globaldescentargument}, we find, for the algorithm \eqref{randomMXL},
\begin{equation} \label{randomdescentargumenttwo} 
\begin{array}{l}
 \lyapunovprob{\prob}{\optmat}{\dualmatn{\itr+1}}
 \leq
\lyapunovprob{\prob}{\optmat}{\dualmatn{\itr}} 
-\stepsizen{\itr} \left[\optrate-\rate{\matn{\itr}} \right] 
\qquad  \quad 
\\
\hfill 
+ 4\kk^2\meanlipschitz \stepsizen{\itr}\deltan{\itr} 
+  \randomMDSn{\itr}
+\sum_{\nbk=1}^{\kk} \frac{\stepsizen{\itr}^2}{2\strongly} \dualnorm{\estgradkn{\nbk}{\itr}}^2
,
\end{array}
\end{equation}
with the random sequence $\{\randomMDSn{\itr} \}$   now given by
\begin{equation}\begin{array}{c} \label{randomMDSn}
\randomMDSn{\itr} 
= 
 \stepsizen{\itr}\sum_{\nbk\in\Updatingn{\itr}} \inner{ \devmatkn{\nbk}{\itr} }{\matkn{\nbk}{\itr}-\optmatk{\nbk}}  \qquad \qquad \qquad \qquad \quad
\\
\hfill 
+ \sum_{\nbk=1}^{\kk}  \frac{\indicator{\Updatingn{\itr}}{\nbk}-\probk{\nbk}}{\probk{\nbk}} \, \big[ \stepsizen{\itr} \inner{  \estgradkn{\nbk}{\itr} }{\matkn{\nbk}{\itr}-\optmatk{\nbk}} + \frac{\stepsizen{\itr}^2}{2} \dualnorm{\estgradkn{\nbk}{\itr}}^2  \big]
.
\end{array}
\end{equation}

It is easily seen that $\expectation{\randomMDSn{\itr}   \cond \filtrationn{n-1}   }= 0 $, and
\begin{equation} \label{randommodulusMDSn}
\begin{array}{l}
\nocolsep
\modulus{\randomMDSn{\itr}} 
\leq  
 2\stepsizen{\itr}\sum_{\nbk=1}^{\kk}  \dualnorm{ \devmatkn{\nbk}{\itr} }
\qquad\qquad\qquad\qquad\qquad\qquad\\ \hfill 
+ \sum_{\nbk=1}^{\kk} \max\big(1,\frac{1}{\probk{\nbk}}-1\big) \, \big[ 2\stepsizen{\itr} \dualnorm{  \estgradkn{\nbk}{\itr} } + \frac{\stepsizen{\itr}^2}{2} \dualnorm{\estgradkn{\nbk}{\itr}}^2  \big].
\end{array} 
\end{equation}

Compare \eqref{randomdescentargumenttwo},\eqref{randommodulusMDSn} with \eqref{descentargumenttwo},\modulusmartingaledifference{}. 
By reproducing the rationale behind the proof of \cref{lemma:globaldescentargument}, we obtain an asynchronous 

counterpart to \cref{lemma:globaldescentargument}, where \eqref{expectationyergodicaverageidentity} and \eqref{standardtroptrateboundmeanexpectation} now hold with $\lyapunovprobfunction{\prob} $ in place of $ \lyapunovfunction $, and \eqref{standardazumabis} becomes

\obsolete{
\begin{equation}
\begin{array}{l}
\nocolsep
\modulus{\randomMDSn{\itr}} 
\leq
2\cststepsize\sum_{\nbk=1}^{\kk}  \dualnorm{ \devmatkn{\nbk}{\itr} }
\hfill
\\
\quad
+ \sum_{\nbk=1}^{\kk} \max\left(1,\frac{1}{\probk{\nbk}}-1\right) \left[ 2\cststepsize \dualnorm{  \estgradkn{\nbk}{\itr} } + \frac{\cststepsize^2}{2} \dualnorm{\estgradkn{\nbk}{\itr}}^2  \right].
\\
\leq
4\vbound\cststepsize\kk\meandimension
\hfill
\\
\quad
+  \sum_{\nbk=1}^{\kk} \max\left(1,\frac{1}{\probk{\nbk}}-1\right) \left[ 2\vbound\cststepsize \dimensionk{\nbk} + \frac{\vbound^2\cststepsize^2}{2} \dimensionk{\nbk}^2  \right].
\\
=
2 (2+ \probdist{\prob}) \cststepsize\kk\maxdimension\vbound
+  \frac{\cststepsize^2\probdist{\prob}}{2} \kk\maxdimension^2 \vbound^2 .
\\
=
2 [(2+ \probdist{\prob}) \cststepsize\kk\maxdimension\vbound
+  \frac{\cststepsize^2\probdist{\prob}}{4} \kk\maxdimension^2 \vbound^2 ].
\end{array}
\end{equation}
}

\begin{equation} \label{randomstandardazuma}
\begin{array}{c}
\Bigproba{\frac{\sum_{\itr=1}^{T}  \randomMDSn{\itr}  }{ T\cststepsize  }   \geq \zeta   }
 
\leq 


\Bigexponential{-\frac{T\zeta^2}{    8\kk^2\maxdimension^2     \left[ (1+\frac{\probdist{\prob}}2)    \normbound{0}{0}{\cststepsize}{\cstdelta} + \frac{\probdist{\prob}}{8} \cststepsize      \maxdimension \, [\normbound{0}{0}{\cststepsize}{\cstdelta}]^2  \right]^2  }}
 ,
\end{array}
\end{equation}
where $\probdist{\prob}$ is defined as in \cref{timecomplexity:randomtrMXLMO}. 
\begin{proof}[Proof of \cref{timecomplexity:randomtrMXLMO}]
Proceed as in the proof of \cref{timecomplexity:trMXLMO}.

\end{proof}


\obsolete{
$\normbound{0}{0}{\cststepsize}{\cstdelta} =   \frac{  \fourtwitchFlipschitz    \strongly}{\sqrt{\maxdimension}  }  \left( \frac{2\strongly}{\maxdimension \Lipschitz\kk  } -  \frac{\cststepsize  }{\cstdelta} \right)^{-1}$

\begin{equation} \label{randomstandardazuma}
\begin{array}{c}
\Proba{\frac{\sum_{\itr=1}^{T}  \randomMDSn{\itr}  }{ T\cststepsize  }   \geq \zeta   }
 \hspace{55mm}
 \\ 
 \hfill
\leq 
\Exponential{-  {\scriptstyle  \left[   \frac{ \halftwitchFlipschitz(1+\frac{\probdist{\prob}}{2}) \strongly   }{\big( \frac{2\strongly}{(\maxmm^2-1) \Lipschitz\kk  } -  \frac{\cststepsize  }{\cstdelta} \big)}  +     \frac{  \squaredhalftwitchFlipschitz     \strongly \probdist{\prob}      \sqrt{\maxmm^2-1}  \cststepsize }{\big( \frac{2\strongly}{(\maxmm^2-1) \Lipschitz\kk  } -  \frac{\cststepsize  }{\cstdelta} \big)^{2}}  \right]^{-2}  } \frac{T\zeta^2}{    2^9 \kk^2 (\maxmm^2-1)      }  }
 \\ 
 \hfill
\leq 
\Exponential{-  {\scriptstyle \frac{\big( \frac{2\strongly}{(\maxmm^2-1) \Lipschitz\kk  } -  \frac{\cststepsize  }{\cstdelta} \big)^{2}}{ \left[ \halftwitchFlipschitz    \forcestrongly+\halftwitchFlipschitz \frac{\probdist{\prob}}{2} \strongly    +     \frac{  \squaredhalftwitchFlipschitz     \strongly \probdist{\prob}      \sqrt{\maxmm^2-1}  \cststepsize }{\big( \frac{2\strongly}{(\maxmm^2-1) \Lipschitz\kk  } -  \frac{\cststepsize  }{\cstdelta} \big)}  \right]^{2}  } } \frac{T\zeta^2}{    2^9 \kk^2 (\maxmm^2-1)      }  }
 ,
\end{array}
\end{equation}
where $\probdist{\prob}=\frac 1 \kk\sum_{\nbk=1}^{\kk}   \max(1,\frac{1}{\probk{\nbk}}-1) $.
}


\begin{proof}[Proof of Corollary \ref{convergenceratres:randomtrMXLMO}]

First observe that  we have $\probdist{\prob}=\kk-1$ if $\kk\geq2$. The rest of the proof bases on the conclusions of \cref{timecomplexity:randomtrMXLMO} 
and follows the exact lines of the proof of Corollary \ref{convergenceratres:trMXLMO}, now using $\Bcoefficientprob{\prob}{\stepsize}{\delta}$ and $\Ccoefficientprob{\prob}{\stepsize}{\delta}$. Note that Corollary \ref{convergenceratres:randomtrMXLMO}\ref{cr:randomtrMXLMOii}

holds with the following restriction on $\errortolerance$:
\begin{multline*}

\errortolerance 
{\refereq{\eqref{newconditionondeltaMO}}{{\,<\,}}}


2^{3} \meanlipschitz
	\bracks*{ \renrmlzdcstepsprob{\prob}{\errorproba}
	\sqrt{\renrmlzdstuff{\errorproba}  \sqrthalftwitchFlipschitz  \sqrtstrongly     \squaredhalftwitchFlipschitz \strongly    \Lipschitz / \meanlipschitz } + \big[{\powlogarithm{{1/ \errorproba}}{\frac 3 8} \kk^{\frac{3}{4}}\dimension}\big]^{-1} }
	\\
	\times \sqrt{ \frac{\powlogarithm{1/\errorproba}{\frac 3 4}  \kk^{\frac{11}{4}}[\maxmm+1][\maxmm^2{-}1] }{\maxmm} }
.
\qedhere
\end{multline*}
\end{proof}
{"config": "arxiv", "file": "2006.05445/Appendix.tex"}