# An Augmented Lagrangian Approach for Problems With Random Matrix Composite
Structure

Dan Greenstein  Faculty of Data and Decision Sciences, Technion - Israel
Institute of Technology, Haifa 3200, Israel. Email:
<EMAIL_ADDRESS>Nadav Hallak  Faculty of Data and Decision
Sciences, Technion - Israel Institute of Technology, Haifa 3200, Israel.
Email<EMAIL_ADDRESS>
###### Abstract

We consider the minimization of a sum of a smooth function with a nonsmooth
composite function, where the composition is applied on a random linear
mapping. This random composite model encompasses many problems, and can
especially capture realistic scenarios in which the data is sampled during the
optimization process. We propose and analyze a method that combines the
classical Augmented Lagrangian framework with a sampling mechanism and
adaptive update of the penalty parameter. We show that every accumulation
point of the sequence produced by our algorithm is almost surely a critical
point.

##  1 Introduction

###  1.1 Problem formulation

This thesis addresses the nonconvex non-smooth composite model with a random
linear operator $M\in\mathbb{R}^{n\times n}$ given by

$\min\limits_{x\in\mathbb{R}^{n}}h(x)+P(\mathbb{E}[M]x),$ (1.1)

where:

  1. 1.

$M:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is a random linear map with
distribution $\pi$.

  2. 2.

$h:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a twice continuously differentiable
function.

  3. 3.

$P:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{\infty\\}$ is proper, lower semi-
continuous function.

Unfortunately, finding the global optimum in a general nonconvex problem is an
NP hard problem. Therefore, we look for a point that satisfies a necessary
optimality condition - criticality. The set of critical points of a function
$\psi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is

$\operatorname{Crit}{\psi}=\\{x\in\mathbb{R}^{n}\;|\;0\in\partial\psi(x)\\}.$

Throughout the paper, we will address problem (1.1) via the Augmented
Lagrangian (AL) framework (e.g. Bertsekas [3], Chapter 3, section 2.1). To
that end, we first restate problem (1.1) as follows:

$\displaystyle\min\limits_{x\in\mathbb{R}^{n}}h(x)+P(y)$ (1.2)
$\displaystyle\mathbb{E}[M]x=y.$

The Augmented Lagrangian of (1.2) is

$\mathcal{L}_{\beta}(x,y,z)=h(x)+P(y)-\langle z,\mathbb{E}[M]x\rangle+\langle
z,y\rangle+\dfrac{\beta}{2}\|\mathbb{E}[M]x-y\|^{2}.$ (1.3)

Our consideration of the Augmented Lagrangian of (1.2) is motivated by the
fact that $(x,y,z)\in\operatorname{Crit}{\mathcal{L}_{\beta}}\Rightarrow(x,y)$
is a critical point of (1.2) (see Bolte et al. [6], Proposition 3.1).

We use Algorithm 1 to seek a critical point of (1.3). The algorithm

  1. 1.

Maintains a sequence of unbiased estimators of $\mathbb{E}[M]$, with
decreasing variance.

  2. 2.

Performs alternating directions update.

  3. 3.

Updates the penalty parameter as needed.

An implicit assumption of our model is that $P$ is prox-tractable - meaning,
that $prox_{\tau P}$ is easy to compute. The proximal operator will be
discussed in Section 2.1.

We state our blanket assumptions regarding the random linear operation $M$
below.

######  Assumption 1.

  1. The random linear operator $M$ satisfies that

  2. 1.

$\mathbb{E}[M]$ is a surjective linear map;

  3. 2.

$Var[M]$ is bounded.

Note that the second part in 1 is fundamental in the analysis of behavior of
random variables.

###  1.2 Motivation

The structure of model (1.1) is exceedingly versatile. Even when we restrict
ourselves to the simplified case in which $M$ is deterministic and $M=I$ ($I$
being the identity mapping), we retrieve the highly versatile composite
optimization model. In the composite optimization model, the function $h$ can
encode the differentiable components of many loss functions, while $P$ can
encode non-smooth components, regularization, and sets of constraints that
define a closed subspace. When, $M$ is a random linear mapping, we can encode
constraints and regularization which are random and are learned online, during
the algorithm’s runtime.

We consider some applications of the model (1.1):

  1. 1.

Inverse Reinforcement Learning:

The MDP model for Reinforcement Learning (RL) is a tuple $\mathcal{M}=\langle
S,A,T,R,\gamma\rangle$, where $S$ is the state space, $A$ is the action space,
$T:S\times A\rightarrow Prob(S)$ is a mapping defining the probability of
transitioning to a state conditioned on the current state and the action taken
in it, $R$ is the reward function, and $\gamma\in[0,1]$ is the discount
factor. Assuming the first state is sampled randomly, RL attempts to find a
policy $\pi$ maximizing

$\mathbb{E}[\sum\limits_{t=0}^{\infty}\gamma^{t}R(s_{t},\pi(s_{t}))].$

In many applications of RL, the true reward function is not known or hard to
determine. Therefore, when a demonstration of the desirable policy or behavior
is available, it might be desirable to learn the demonstrated policy instead.
For an extensive survey of Inverse Reinforcement Learning (IRL), see Arora and
Doshi [1].

We consider a deterministic setting, as in Leibovich et al. [20] – we have a
set of desirable outcomes $\\{y_{1},\ldots,y_{M}\\}\in\mathcal{Y}$ and a
bijective mapping from the set of actions $\mathcal{X}$ to the set of outcomes
$\mathcal{F}:\mathcal{X}\rightarrow\mathcal{Y}$. The mapping $\mathcal{F}$ is
not known in advance, but $\mathcal{F}(x)$ can be observed at any
$x\in\mathcal{X}$. The inverse mapping
$\mathcal{F}^{-1}:\mathcal{Y}\rightarrow\mathcal{X}$ is the mapping from
outcomes to initial actions – that is, action $\mathcal{F}^{-1}(y)$ needs to
be taken to reach state $y$. We wish to minimize the distance between the true
inverse mapping $\mathcal{F}^{-1}$, and a parametric approximation
$\mathcal{G}_{\theta}$, where $\theta\in\Theta$ is a parameter vector.
Formally,

$\min\limits_{\theta\in\Theta}\dfrac{1}{N}\sum\limits_{i=1}^{N}\mathcal{L}(\mathcal{G}_{\theta}(y_{i}),\mathcal{F}^{-1}(y_{i})),$

where $\mathcal{L}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ is some
loss function, such as the error between inputs in absolute value.

Assume that for every $y\in\\{y_{1},\ldots,y_{N}\\}$, the probability of
drawing $\mathcal{F}^{-1}$ from $\mathcal{X}$ using uniform sampling is
positive, and that $\mathcal{G}_{\theta}$ is linear with respect to $\theta$.
Additionally, assume that $\mathcal{L}(x,y)=\tilde{\mathcal{L}}(x-y)$ for some
function $\tilde{\mathcal{L}}$. Note that the last requirement is not very
restrictive - any loss function that is based on the error term fulfills this
requirement.

We can generate i.i.d samples of $\mathcal{F}^{-1}(y)$ for
$y\in\\{y_{1},\ldots,y_{M}\\}$ using uniform sampling from $\mathcal{X}$ and
rejection sampling - we throw away samples $x\in\mathcal{X}$ where
$\mathcal{F}(x)\notin\\{y_{1},\ldots,y_{N}\\}$. We denote our approximation of
$\mathcal{F}^{-1}$ by $\tilde{\mathcal{F}}^{-1}$.

We can match the IRL problem to (1.1) by setting

$M=\begin{pmatrix}\mbox{diag}\left(\mathcal{G}(y_{1}),\ldots,\mathcal{G}_{y_{N}}\right)&\mbox{diag}\left(\tilde{\mathcal{F}}^{-1}(y_{1}),\ldots,\tilde{\mathcal{F}}^{-1}(y_{N})\right)\\\
0&I\end{pmatrix},$

$h\equiv 0$, $\theta$ such that the dimension of $\theta$ is $2N$. Informally,
we will want $\theta_{N+1}=\theta_{N+2}=\ldots=\theta_{2N}=-1$. Formally, we
will enforce it by introducing a $\delta_{\mathcal{C}}$ component to $P$.
$\delta_{\mathcal{C}}$ is defined as

$\delta_{\mathcal{C}}(u)=\begin{cases}\infty,&u\notin\mathcal{C}\\\
0,&\text{otherwise}\end{cases}.$

We define $P$ as

$P(u)=\dfrac{1}{N}\sum\limits_{i=1}^{N}\tilde{\mathcal{L}}(u_{i})+\delta_{u_{N+1}=\ldots=u_{2N}=-1}(u).$

Then,

$P(M\theta)=\dfrac{1}{N}\sum\limits_{i=1}^{N}\mathcal{L}(\mathcal{G}_{\theta}(y_{i}),\tilde{\mathcal{F}}^{-1}(y_{i})).$

  2. 2.

Image Deconvolution:

Image deconvolution is a fundamental problem in the field of image processing
(see Jansson [18], Campisi and Egiazarian [12]). We observe an image from some
source, such as a telescope, camera, microscope or ultrasound. The observation
process is never perfect - the observed image is susceptible to blur, noise,
and other sources of image degradation. The image deconvolution process aims
at recovering the original image from the degraded observation. The discrete
linear space invariant (LSI) model of the degradation for a 2-D image is given
by

$g(x)=(f*h)(x)+n(x)=\sum\limits_{s\in S_{h}}h(x-s)f(x)+n(x),$

where the operator $(*)$ denotes convolution, $x=(x_{1},x_{2})$ is the
observed pixel location, $g$ is the observed image, $h$ is the blur operator,
$S_{h}\subset\mathbb{R}^{2}$ is the state space of the blur, $f$ is the real
image, and $n$ is noise, usually modeled as white gaussian noise.

This can also be written in a vector-matrix formulation as

$g=Hf+n.$

In applications in which the blur $H$ is unknown, the problem is known as
blind image deconvolution.

In many applications of blind image deconvolution, such as microscopy, remote
sensing, medical ultrasound, optical telescope systems or photography, the
blur can be estimated from experiments (see Campisi and Egiazarian [12,
Section 1.3, A priori blur identification methods] and Fergus et al. [15]).
Then, non-blind methods can be used to estimate the original image.

One such method is the Tikhonov filtering - least squares with Tikhonov
regularization (see Tikhonov [25])

$\hat{f}=\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{f}\|\mathbb{E}[H]f-g\|^{2}+\|\Gamma f\|^{2},$ (1.4)

where $\Gamma$ is a Tikhonov regularization matrix, usually chosen to be
$\lambda I$ for some $\lambda>0$.

We can capture (1.4) using (1.1) by choosing $h(f)=\|\Gamma f\|^{2}$, $M=H$,
and $P(u)=\|u-g\|^{2}$.

  3. 3.

Maximum Singular Value of the Expectation of a Random Matrix:

Finding the maximum singular value of a matrix is a fundamental subroutine in
many algorithms, the best known of which are algorithms for the principal
component analysis (PCA) problem. When the matrix is sampled, the retrieval
the maximum singular value of the expectation of the matrix and its matching
vector is often desired instead. Such subroutines are implicitly used in this
paper, in Algorithm 3 and Algorithm 5 – we evaluate the minimum singular value
of the positive semidefinite matrices $\\{(M^{t+1})^{T}M^{t+1}\\}_{t\geq 0}$,
which can be implemented by first finding the maximum eigenvalue
$\lambda_{max}((M^{t+1})^{T}M^{t+1})$, and then finding the maximum eigenvalue
of $\lambda_{max}((M^{t+1})^{T}M^{t+1})I-(M^{t+1})^{T}M^{t+1}$.

The problem of finding the maximum singular value of the expectation of a
random matrix is also considered on its own, for example in Garber et al. [16,
Section 3], where the problem is considered in a stochastic bandits setting.

Given a sequence of i.i.d random matrices $\\{A_{t}\\}_{t\geq 0}$, an
eigenvector of the maximum eigenvalue of the expectation matrix is given by

$\displaystyle\mathop{\mbox{\rm argmax}}\limits_{x\neq
0}\dfrac{\|\mathbb{E}[A]x\|^{2}}{\|x\|^{2}}.$

Equivalently, since the $\ln(\cdot)$ function is strictly monotonically
increasing, we can find a vector matching the maximum singular value by

$\displaystyle\mathop{\mbox{\rm
argmax}}\limits_{x}\ln\left(\dfrac{\|\mathbb{E}[A]x\|^{2}}{\|x\|^{2}}\right).$

Using the properties of $\ln()$ and transitioning into a minimization problem,
this is equivalent to

$\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{x}\ln\left(\|x\|^{2}\right)-\ln\left(\|\mathbb{E}[A]x\|^{2}\right).$

This problem can be modeled in by (1.1) by choosing

$h(x)=\ln\left(\|x\|^{2}\right),$ $P(y)=-\ln(\|y\|^{2})$

and

$M=A.$

###  1.3 Literature

Previous research on composite methods can be divided into the two categories
- the convex and the nonconvex case. The convex case is not the focus of this
paper, and we refer the interested reader to a survey by Sabach and Teboulle
[24].

Research on nonconvex composite minimization is sparse. All previous works
that we have found assume that the mapping is deterministic - which is not
assumed in this work. Additionally, all previous works assume that the
gradient of the mapping is surjective (which, in the linear mapping case,
means that $MM^{T}$ is full rank) - in this work, the surjectivity assumption
is only made on $\mathbb{E}[M]$, while a specific sample $M$ might not be
surjective.

The work by Li and Pong [21] is the first reference we have found to the
composite linear model in nonconvex optimization, and many proof techniques in
this paper were inspired by it. The approach proposed by the authors hinges on
the surjectivity of the linear mapping, and the assumption that the penalty
parameter was chosen to be sufficiently large - we require similar conditions
on the penalty parameter to reached eventually, but adaptively update the
penalty parameter instead of assuming that it is chosen to be sufficiently
large. The authors prove subsequence convergence in the general case, and
convergence of the whole sequence, as well as its boundedness, under
additional assumptions. The model studied in Li and Pong [21] is
deterministic, and therefore does not capture the model we study.

In Boţ and Nguyen [8], the authors extend the work by Li and Pong [21].
Focusing on linear mappings, and using similar assumptions, they show a
convergence rate to a critical point for the case in which the Kurdyka-
Lojasiewicz (KL) assumption holds true.

Bolte et al. [6] studied a comprehensive class of problems which essentially
can capture most known deterministic models. The key element, which is the
source for the challenges of this problem, is the nonsmooth nonconvex
composite function with a general operator, which in our case is replaced with
a random linear operator. Their approach the authors used utilized two main
tools to overcome the challenges originating from the composite structure:

  1. 1.

They assumed the existence of an information zone, a subspace in which the
Jacobian of the possibly non-linear operator is essentially surjective, note
that this generalizes the surjectiveness of the linear operators in Boţ and
Nguyen [8] and Li and Pong [21].

  2. 2.

They used an adaptive penalty to ensure that the algorithm reaches the
information zone.

We borrow the idea of an adaptive penalty parameter in case it is not possible
to predetermine it in Section 3. The approach proposed by Bolte et al. [6] is
mainly limited by the surjectivity assumption (termed in a more general manner
as uniform regularity) on the Jacobian. This is expressed by the fact that the
method uses the uniform regularity constant to control the penalty parameter
although it is hard to determine it in non trivial cases. Moreover, the
uniform regularity limits the variety of operators that can be used. The model
studied in Bolte et al. [6] is fully deterministic, and therefore does not
capture the model we study.

Cohen et al. [13] also focuses on nonlinear mappings. The authors require more
restrictive on $P$ (it is required to be continuously differentiable with a
Lipschitz continuous gradient), and derive an algorithm that is much simpler
than the one outlined in Bolte et al. [6].

###  1.4 Contributions

Our contributions revolve the stochasticity of the linear mapping $M$:

  1. 1.

We establish convergence results for randomized mappings, under the assumption
that $Var[M]$ is bounded. To the best of our knowledge, this is the first time
such results appear in this literature.

  2. 2.

Using the additional assumption that each matrix entry $M^{t}_{i,j}$ has Sub-
Gaussian distribution, we improve the sample complexity of the algorithm
considerably. The class of Sub-Gaussian distributions includes bounded random
variables, among others.

  3. 3.

Using the assumption that $\nabla^{2}h(x)$ is lower bounded by some known
constant, we simplify the adaptive update of the penalty parameter.

##  2 Mathematical Preliminaries

###  2.1 Notation and Basic Definitions

Overall we use the common notation from linear Algebra, matrix analysis, and
convex/nonconvex analysis. In particular, the proximal operator of $\tau P$
for $\tau>0$ is defined as:

$u^{+}\in\displaystyle\mathop{\mbox{\rm argmin}}\limits_{y}\tau
P(y)+\dfrac{1}{2}\|y-u\|^{2}.$

In all our uses of the proximal operator, we will assume that it is well
defined - that is, that the minimizer exists. Note, however, that there might
be more than one minimizer - in that case, we will require that our proximal
operator will return one minimizer in the set of minimizers.

The subdifferential operators are defined as in Rockafellar and Wets [22]. We
denote $z\xrightarrow{f}x$ if $z\rightarrow x$ and $f(z)\rightarrow f(x)$. The
domain of a proper extended real valued function
$f:\mathbb{R}^{m}\rightarrow\mathbb{R}\cup\\{\infty\\}$ is defined as
$dom(f)\equiv\\{x:f(x)<\infty\\}$. Then the subdifferential set of $f$ at
point $x\in dom(f)$, $\partial f(x)$, is defined as

$\partial f(x)\equiv\\{v\in\mathbb{R}^{m}:\exists
x^{t}\xrightarrow{f}x,v^{t}\rightarrow v,\limsup_{z\rightarrow
x^{t}}\dfrac{f(z)-f(x^{t})-\langle v^{t},z-x^{t}\rangle}{\|z-x^{t}\|}\geq
0\;for\;each\;t\\}.$

For a twice continuously differentiable function
$\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the Bregman distance
$D_{\phi}:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is defined
as:

$D_{\phi}(x_{1},x_{2}):=\phi(x_{1})-\phi(x_{2})-\langle\nabla\phi(x_{2}),x_{1}-x_{2}\rangle.$

We denote the index range $\\{1,\ldots,n\\}$ by $[n]$.

Unless stated otherwise, the notation $\|x\|$ will refer to the $\ell_{2}$
norm when applied to a vector $x\in\mathbb{R}^{n}$, and $\|X\|$ will refer to
the $\ell_{2}$ induced norm $\|X\|_{2,2}$ when applied to
$X\in\mathbb{R}^{m\times n}$. The only vector norm that will be used in
practice is $\ell_{2}$. The results regarding matrix norms will always be
stated with regards to the induced norm $\|X\|_{2,2}$, but the entry-wise
$\ell_{1}$ norm $\|X\|_{1,1}$ will be used in the body of proofs.

###  2.2 Properties of the linear map

One of the blanket assumptions of our model is that $\mathbb{E}(M)$ is a
surjective linear map, a property we state formally below.

######  Definition 2.1.

A map $F$ is surjective if for every $y\in\mathbb{R}^{m}$, there exists
$x\in\mathbb{R}^{n}$, such that $F(x)=y$. Similarly, a map
$G:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is injective if for every
$y_{1}\neq y_{2}\in\mathbb{R}^{m}$, $G(y_{1})\neq G(y_{2})$. For $m<n$, a
linear map $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ can be surjective if
its row span is $m$, but cannot be injective (equivalently,
$\mbox{rank}(F)=m$). Similarly, $G:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$
can be injective if its column span is $m$, but cannot be surjective
(equivalently, $\mbox{rank}(G)=m$).

For the sake of simplicity, we will assume that $M$ is a bijective map from
$\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ such that $\mathbb{E}(M)$ has full
rank. This assumption actually does not incur any lose of generality compared
to the case in which $M$ is a surjective map from $\mathbb{R}^{n}$ to
$\mathbb{R}^{m}$ ($m<n$); We justify this statement below.

The key reason for the above is that one can always extend the surjective
mapping $M$ to a mapping $M^{\prime}$ that is surjective and injective almost
surely, to attain an equivalent problem, using the following procedure:

  1. 1.

Generate $n-m$ independent identically distributed random vectors
$\\{v_{i}\\}_{i=1}^{n-m}$, so that each vector is sampled uniformly from the
unit sphere ($\\{v\in\mathbb{R}^{n}\;|\;\|v\|=1\\}$).

  2. 2.

For each sampled matrix $M^{t}\sim\pi$:

    1. (a)

Concatenate $\\{v_{i}\\}_{i=1}^{n-m}$ to the rows of $M^{t}$ to generate a
square matrix $M^{\prime}_{t}$.

Since the additional vectors are only sampled once, and are attached to each
random mapping $M^{t}$, the extended expected mapping $\mathbb{E}[M^{\prime}]$
will contain the added rows $\\{v_{i}\\}_{i=1}^{n-m}$, too. We will now
formally establish that $\mathbb{E}[M^{\prime}]$ has full rank almost surely.

######  Lemma 2.1.

Let $\\{M_{t}\\}_{t\geq 0}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ be random
linear maps sampled i.i.d from distribution $\pi$, such that
$\mathbb{E}[M]\equiv\mathbb{E}[M_{0}]$ exists, and $\mathbb{E}[M]$ is
surjective. Let $\\{v_{i}\\}_{i=1}^{n-m}$ be i.i.d random vectors sampled
uniformly from the unit sphere $\\{v\in\mathbb{R}^{n}:\|v\|_{2}=1\\}$. Define
$M^{{}^{\prime}}_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ as $M_{i}$ with
$\\{v_{j}\\}_{j=1}^{i}$ concatenated as the last $i$ rows.

Then $\mathbb{E}[M^{\prime}]:=\mathbb{E}[M^{{}^{\prime}}_{n-m}]$ exists, and
$\mathbb{E}[M^{\prime}]$ has full rank almost surely.

###### Proof.

We will see that $dim(span(\mathbb{E}[M^{\prime}]))=n$ by induction. First, we
note that

$dim(span(\mathbb{E}[M]))=m.$

Since $span(\mathbb{E}[M])$ is an $m$-dimensional subspace of
$\mathbb{R}^{n}$, it’s Lebesgue measure is $0$; see Rudin [23, Theorem 2.20
(e) and Determinants 2.23]. Thus, for

$v_{1}\sim Unif(\\{v\in\mathbb{R}^{n}:\|v\|=1\\}),$

it follows that

$Prob(v_{1}\in span(\mathbb{E}[M]))=0,$

and therefore

$Prob(dim(span(\mathbb{E}[M^{\prime}_{1}]))=m+1)=1.$

Next, we assume that $Prob(dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i)=1$ for
$i<n-m$, and show that
$Prob(dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1)=1$.

Note that the event $dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i$ is contained
the event $dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1$ – that is, it is
impossible that the event $dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1$
occurs if $dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i$ does not. Using this
insight we can deduce that

$\displaystyle Prob(dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1)$
$\displaystyle=Prob\left(\\{dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1\\}\cap\\{dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i\\}\right).$

By the definition of conditional probability, it then follows that

$\displaystyle
Prob(\\{dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1\\}\cap\\{dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i\\})$
$\displaystyle=Prob(dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1\;|\;dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i)$
$\displaystyle\cdot Prob(dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i).$

By the induction assumption,
$Prob(dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i)=1$. Therefore

$\displaystyle Prob(dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1)$
$\displaystyle=Prob(dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1\;|\;dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i).$

As we have argued for the base case of the induction, the Lebesgue measure of
the span of $\mathbb{E}([M^{\prime}_{i}])$ is $0$, and therefore, since

$v_{i+1}\sim Unif(\\{v\in\mathbb{R}^{n}:\|v\|=1\\}),$

it follows that

$Prob(v_{i+1}\in span(\mathbb{E}[M^{\prime}_{i}]))=0.$

Consequently,

$Prob(dim(span(\mathbb{E}[M^{\prime}_{i+1}]))=m+i+1\;|\;dim(span(\mathbb{E}[M^{\prime}_{i}]))=m+i)=1.$

Hence, for $M^{\prime}_{n-m}$,
$Prob(dim(span(\mathbb{E}[M^{\prime}_{n-m}]))=n)=1$. We denote
$M^{\prime}_{n-m}$ by $M^{\prime}$. Since the dimension of the span of
$M^{\prime}$ is $n$ almost surely, it follows that

$Prob(rank(\mathbb{E}[M^{\prime}])=n)=1.$

$\Box$

To utilize 2.1, we can extend $P:\mathbb{R}^{m}\rightarrow\mathbb{R}$ to
$P^{\prime}:\mathbb{R}^{n}\rightarrow\mathbb{R}$, by ignoring the last $n-m$
indices. That is

$P^{\prime}(u_{1},\ldots,u_{m},u_{m+1},\ldots,u_{n})=P(u_{1},\ldots,u_{m}).$

Note that the first $m$ cells of $\mathbb{E}[M^{\prime}]x$ are equal to
$\mathbb{E}[M]x$, independently of our choice of random vectors
$\\{v_{i}\\}_{i=1}^{n-m}$. Therefore, for every choice of vectors
$\\{v_{i}\\}_{i=1}^{n-m}$ and every $x\in\mathbb{R}^{n}$,

$h(x)+P(\mathbb{E}[M]x)=h(x)+P^{\prime}(\mathbb{E}[M^{\prime}]x).$

Considering the above discussion, we make the following assumption throughout
this paper without restating it.

######  Assumption 2 (blanket assumption).

The expectation $\mathbb{E}[M]$ has full rank, meaning that there is a scalar
$\sigma>0$, such that $\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])=\sigma$.

We adopt the following notation with regards to linear mappings: given a
symmetric linear mapping $T$, we use $\|\cdot\|_{T}^{2}$ to denote the induced
quadratic form of $T$, that is $\|\cdot\|_{T}^{2}=\langle x,Tx\rangle$. Given
a matrix $T\in\mathbb{R}^{n\times n}$, we denote the matrix $T\cdot T$ as
$T^{2}$.

Additionally, whenever we refer to a sequence $\\{M^{i}\\}_{i>0}$ of matrices,
we assume that these are independent and identically distributed matrices,
where $M^{i}\sim\pi$; note that $M\sim\pi$ shares the same distribution as the
matrices in the sequence.

###  2.3 Lipschitz and Empirical Lipschitz Constants

The Lipschitz constant is a powerful tool in analysis of optimization
algorithms, often used to determine the step size in gradient based
algorithms, or the penalty parameter in AL based algorithms. However, the
reliance on the Lipschitz constant has three significant downsides:

  1. 1.

The Lipschitz constant does not always exist ;

  2. 2.

Even if it exists, the Lipschitz constant is not always known ;

  3. 3.

The global Lipschitz constant might be significantly larger than the actual
differences in function values in a sequence generated by an optimization
algorithm.

To address these disadvantages, we introduce the empirical Lipschitz constant.

Given a function $F:\mathbb{R}^{k}\rightarrow\mathbb{R}^{l}$, and a sequence
$\\{x_{t}\\}_{t\geq 0}$, we define an empirical Lipschitz constant (eLip) of
$F$ with respect to the sequence $\\{x_{t}\\}_{t\geq 0}$ in the following
manner.

######  Definition 2.2 (empirical Lipschitz constant).

Let $F:\mathbb{R}^{k}\rightarrow\mathbb{R}^{l}$, and $\\{x_{t}\\}_{t\geq 0}$.
The empirical Lipschitz constant (eLip) of $F$ with respect to the sequence
$\\{x_{t}\\}_{t\geq 0}$ is defined by

$L^{e}_{F}(\\{x_{t}\\}_{t\geq 0})=\begin{cases}\displaystyle\mathop{\mbox{\rm
sup}}\limits_{t\geq 0,x_{t+1}\neq
x_{t}}\dfrac{\|F(x_{t+1})-F(x_{t})\|}{\|x_{t+1}-x_{t}\|},&\exists
t\;\text{such that $x_{t+1}\neq x_{t}$},\\\ 0,&\text{otherwise}.\end{cases}.$

Comparing 2.2 with the definition of the (global) Lipschitz constant of $F$,

$L_{F}=\displaystyle\mathop{\mbox{\rm sup}}\limits_{y\neq
x}\dfrac{\|F(x)-F(y)\|}{\|x-y\|},$

immediately yields the following result.

######  Lemma 2.2.

Let $F:\mathbb{R}^{k}\rightarrow\mathbb{R}^{l}$. For every sequence
$\\{x_{t}\\}_{t\geq 0}$ it holds that

$L^{e}_{F}(\\{x_{t}\\}_{t\geq 0})\leq L_{F}.$

###### Proof.

If for every $t$, $x_{t+1}=x_{t}$, then $L^{e}_{F}(\\{x_{t}\\}_{t\geq 0})=0$.
Since $L_{F}\geq 0$, the result trivially holds true.

Otherwise, there exists $t$ such that $x_{t+1}\neq x_{t}$. Since for every
$x_{t+1}\neq x_{t}$,

$\dfrac{\|F(x_{t+1})-F(x_{t})\|}{\|x_{t+1}-x_{t}\|}\leq\displaystyle\mathop{\mbox{\rm
sup}}\limits_{y\neq x}\dfrac{\|F(x)-F(y)\|}{\|x-y\|},$

it follows that

$L^{e}_{F}(\\{x_{t}\\}_{t\geq 0})=\displaystyle\mathop{\mbox{\rm
sup}}\limits_{t\geq 0,x_{t+1}\neq
x_{t}}\dfrac{\|F(x_{t+1})-F(x_{t})\|}{\|x_{t+1}-x_{t}\|}\leq\displaystyle\mathop{\mbox{\rm
sup}}\limits_{y\neq x}\dfrac{\|F(x)-F(y)\|}{\|x-y\|}=L_{F}.$

$\Box$

In our analysis, the eLip constant will be used in conjunction with an
adaptive penalty scheme to create a sufficient decrease in the updates of the
primal variables.

##  3 Iterative Sampling Alternating Directions Method

We are now ready to describe the Iterative Sampling Alternating Directions
(ISAD) method for composite-Linear problems meta-algorithm, whose pseudo-code
is given in Algorithm 1. Roughly speaking, at each iteration the algorithm
begins by sampling the matrix followed by an update of its average. The method
then performs two alternating minimization steps of the Augmented Lagrangian
with respect to the matrix estimator – we first update the $y$ variable, and
then update the $x$ variable. Afterwards, the method updates the dual variable
$z$ with respect to the new values of $x$ and $y$, the previous value of $z$,
and the matrix estimator. Finally, the penalty parameter is tuned using the
subprocedure of the Adaptive Penalty Oracle (APO).

The meta-algorithm provides two degrees of freedom to its implementation: the
choice of the convex function $\phi$, and the implementation of the APO. The
required characteristics of the APO are introduced in 3.1. We will consider
two implementations of the meta-algorithm: (i) an implementation for the case
in which $\nabla^{2}h(x)$ has a known lower and upper bounds (cf. Section 5);
(ii) an implementation for the general case (cf. Section 6). Section 4 will
include probability bounds that will be used in Section 5, Section 6 and
Section 7. The convergence of the meta algorithm will be proven in Section 7.

The meta algorithm uses several parameters. The parameters $x_{0}$ and $z_{0}$
are the initial values of the variables $x$ and $z$, respectively. The
parameter $\beta_{0}$ is the initial value of the penalty parameter $\beta$.
The sequence $\\{\theta_{t}\\}_{t>0}$ determines the amount of samples of the
matrix $M$ that are collected by round $t$, that is, at round $t+1$, we sample
$\theta_{t+1}-\theta_{t}$ matrices. Finally, $\phi$ is the basis for the
Bregman distance factor $D_{\phi}$ which is utilized in the update of $x$.

Input: ${\bf x}_{0}\in\mathbb{R}^{n}$, ${\bf z}_{0}\in\mathbb{R}^{n}$,
$\beta_{0}>0,\\{\theta_{t}\\}_{t>0}$,
$\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ where $\phi\in C^{2}$ and convex.

1

2for  _$t=0,1,2,\ldots$_ do

3
$sample\;(\theta_{t+1}-\theta_{t})\;matrices\;\\{M^{i}\\}_{i=\theta_{t}+1}^{\theta_{t+1}}$;

4
$\bar{M}^{t+1}=\dfrac{\theta_{t}}{\theta_{t+1}}\bar{M}^{t}+\dfrac{1}{\theta_{t+1}}\sum\limits_{i=\theta_{t}+1}^{\theta_{t+1}}M^{i}\;$

5 $y_{t+1}\in\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{y}\\{P(y)+\langle{z_{t}},y\rangle+\dfrac{\beta_{t}}{2}\|{\bar{M}^{t+1}x_{t}-y}\|^{2}\\}$
;

6

7
$x_{t+1}\in\operatorname{Crit}\limits_{x}\\{h(x)-\langle{z_{t}},\bar{M^{t}}x\rangle+\dfrac{\beta_{t}}{2}\|{\bar{M}^{t+1}x-y_{t+1}}\|^{2}+D_{\phi}(x,x_{t})\\}$;

8

9 $z_{t+1}=z_{t}-\beta_{t}(\bar{M}^{t+1}x_{t+1}-y_{t+1})$

$\beta_{t+1}\leftarrow APO(\bar{M}^{t+1},\beta_{t})$ // Additional arguments
may be provided, depending on the implementation

10

11 end for

Algorithm 1 Meta-ISAD

We provide the following guarantee for Algorithm 1, (stated briefly and
informally):

######  Theorem 3.1.

Let $\theta_{t}$ be chosen according to the sampling regime in 4.3, and let
$\\{x_{t},y_{t},z_{t}\\}_{t>0}$ be the sequence generated by Algorithm 1. Then
for every cluster point $(x^{*},y^{*},z^{*})$ of
$\\{x_{t},y_{t},z_{t}\\}_{t>0}$, $x^{*}$ is a critical point of (1.1) almost
surely.

The formal statement of the theorem and its proof can be found in Theorem 7.2.

The following 3 on the sequence generated by any implementation of Algorithm 1
will be part of our blanket assumptions throughout our analysis of Algorithm
1. This assumption is common in the analysis of Augmented Lagrangian methods
applied to nonconvex nonsmooth problems – see Bolte et al. [5], Bolte et al.
[4], Boţ and Nguyen [8], Cohen et al. [13] and Hallak and Teboulle [17]. In Li
and Pong [21] and Yang et al. [27], the boundedness of the sequence is not
assumed, but coerciveness that implies boundedness in their studied model is
assumed instead.

######  Assumption 3.

The sequence $\\{x_{t},y_{t},z_{t}\\}_{t>0}$ generated by Algorithm 1 is
bounded.

The rest of this section will focus on the properties that are required from
our APO, which will be formally defined in 3.1. Informally, we require that
the number of updates to the value of the adaptive penalty $\beta$ will be
finite, and that after a finite number of iterations, the $x$ update will
induce decrease in function value.

We define two functions that will be used extensively during the analysis of
the algorithm. The first is the Augmented Lagrangian with respect to a matrix
$A$, which we denote by $\mathcal{L}_{\beta_{t}}(x,y,z;A)$:

$\mathcal{L}_{\beta}(x,y,z;A):=h(x)+P(y)-\langle
z,Ax-y\rangle+\dfrac{\beta}{2}\|Ax-y\|^{2}.$ (3.1)

The second is a shorthand for the function whose critical points we are
searching for during the $x$ update:

$g^{t+1}(x)=h(x)-\langle
z_{t},\bar{M}^{t}x\rangle+\dfrac{\beta_{t}}{2}\|\bar{M}^{t+1}x-y_{t+1}\|^{2}+D_{\phi}(x,x_{t}).$
(3.2)

Note that $g^{t+1}(x)$ is equal
$\mathcal{L}_{\beta_{t}}(x,y_{t+1},z_{t})+D_{\phi}(x,x_{t})$ up to constant
factors that do not depend on $x$.

######  Remark 3.1.

Note that
$\mathbb{E}(\mathcal{L}_{\beta}(x,y,z;\bar{M}))\neq\mathcal{L}_{\beta}(x,y,z;\mathbb{E}(M))$,
and more specifically,

$\mathbb{E}[\mathcal{L}_{\beta}(x,y,z;\bar{M})]-\mathcal{L}_{\beta}(x,y,z;\mathbb{E}[M])=\dfrac{\beta}{2}\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x\|^{2}]=\dfrac{\beta}{2}\mathbb{E}[\|\delta(\bar{M},M)x\|^{2}].$

To see this:

$\displaystyle\mathbb{E}[\mathcal{L}_{\beta}(x,y,z;\bar{M})]$
$\displaystyle=\mathbb{E}[h(x)+P(y)-\langle
z,\bar{M}x-y\rangle+\dfrac{\beta}{2}\|\bar{M}x-y\|^{2}]$
$\displaystyle=h(x)+P(y)-\langle
z,\mathbb{E}[M]x-y\rangle+\dfrac{\beta}{2}\mathbb{E}[\|\bar{M}x-y\|^{2}].$

Moreover,

$\displaystyle\mathbb{E}[\|\bar{M}x-y\|^{2}]$
$\displaystyle=\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x+\mathbb{E}[M]x-y\|^{2}]$
$\displaystyle=\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x\|^{2}+2\langle\bar{M}x-\mathbb{E}[M]x,\mathbb{E}[M]x-y\rangle+\|\mathbb{E}[M]x-y\|^{2}]$
$\displaystyle=\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x\|^{2}]+2\mathbb{E}[\langle\bar{M}x-\mathbb{E}[M]x,\mathbb{E}[M]x-y\rangle]+\mathbb{E}[\|\mathbb{E}[M]x-y\|^{2}]$
$\displaystyle=\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x\|^{2}]+\|\mathbb{E}[M]x-y\|^{2}.$

Therefore,

$\displaystyle\mathbb{E}[\mathcal{L}_{\beta}(x,y,z;\bar{M})]$
$\displaystyle=h(x)+P(y)-\langle
z,\mathbb{E}[M]x-y\rangle+\dfrac{\beta}{2}\mathbb{E}[\|\bar{M}x-y\|^{2}]$
$\displaystyle=h(x)+P(y)-\langle
z,\mathbb{E}[M]x-y\rangle+\dfrac{\beta}{2}(\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x\|^{2}]+\|\mathbb{E}[M]x-y\|^{2}).$

Since

$\mathcal{L}_{\beta}(x,y,z;\mathbb{E}[M])=h(x)+P(y)-\langle
z,\mathbb{E}[M]x-y\rangle+\dfrac{\beta}{2}\|\mathbb{E}[M]x-y\|^{2},$

it follows that

$\mathbb{E}[\mathcal{L}_{\beta}(x,y,z;\bar{M})]-\mathcal{L}_{\beta}(x,y,z;\mathbb{E}[M])=\dfrac{\beta}{2}\mathbb{E}[\|\bar{M}x-\mathbb{E}[M]x\|^{2}]=\dfrac{\beta}{2}\mathbb{E}[\|\delta(\bar{M},M)x\|^{2}].$

With definition (3.2) at hand, we can formulate our requirements from the APO
in a clear and compact manner.

######  Definition 3.1 (APO).

An APO is a function that returns a scalar penalty parameter $\beta>0$, that
satisfies, when invoked by Algorithm 1, that for any sequence
$\\{x_{t},y_{t},z_{t}\\}_{t>0}$ generated by Algorithm 1 with the
corresponding sequence of functions $\\{g^{t}\\}_{t\geq 1}$ defined by the
formula in (3.2) that there exists an index $K_{stable}>0$ such that:

  1. 1.

Stability: $\beta_{k}=\beta_{K_{stable}}$ for all $k>K_{stable}$.

  2. 2.

Sufficient decrease: There exists $\rho>0$ such that for all $k>K_{stable}$

$g^{k+1}(x_{k+1})-g^{k+1}(x_{k})\leq-\dfrac{\rho}{2}\|x_{k+1}-x_{k}\|^{2},$

and

$\rho>\dfrac{8}{\beta_{k}\sigma}\left(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\right),$

where $L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ and
$L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ are empirical Lipschitz constants
defined in 2.2.

######  Remark 3.2.

Note that the first part of 3.1 does not mean that the last update occurs on
the $K_{stable}$ index – it might have occurred beforehand.

An APO that satisfies 3.1 exists - Algorithm 5 implements such oracle for the
general case, while Algorithm 3 implements the oracle under the assumption
that the hessian of $\nabla^{2}h$ is bounded, and $\phi$ is chosen
accordingly.

##  4 The Sampling Mechanism

In this section, we will discuss the properties of the sampling mechanism that
will be used throughout the rest of this work. We introduce 4, which will not
be mandatory, but will greatly improve the performance of our sampling
mechanism. Next, we define the component-wise error of the matrix estimator,
which will be used extensively throughout the remaining sections. Afterwards,
we prove that the sum of the squared norms of the estimator errors is finite,
a fact that will be used in Section 7 to prove the convergence of Algorithm 1.
Finally, we will see that the lowest singular value of the matrix estimator
and the lowest singular value of the real matrix are within a multiplicative
error of each other almost surely given a sufficient amount of samples; this
fact will be used in Section 5 and Section 6 to prove that the algorithms
therein implement the meta algorithm Algorithm 1.

We begin with the definition and properties of Sub-Gaussian random variables;
All the definitions, properties and theorems cited in this context are taken
from Vershynin [26, Chapters 2.5-2.6]. Theorem 4.1, presented below,
establishes equivalence between the five properties. A random variable
matching any of these properties is called Sub-Gaussian. Since the properties
are equivalent, the choice of the property for the definition of Sub-Gaussian
random variables is arbitrary. Out of mathematical convenience, we will use
the fourth property for the actual definition.

######  Theorem 4.1 (Vershynin [26, Proposition 2.5.2]).

Let $X$ be a random variable. Then the following properties are equivalent;
the positive parameters $\\{K_{i}\\}_{i\in[5]}$ appearing in these properties
differ from each other by at most an absolute constant factor.

  1. 1.

The tails of $X$ satisfy

$Prob\left(\left|X\right|\geq
t\right)\leq\exp{\left(-\dfrac{t^{2}}{K_{1}}\right)}\;\forall t\geq 0.$

  2. 2.

The moments of $X$ satisfy

$\|X\|_{\mathcal{L}_{p}}=\left(\mathbb{E}\left[\left|X\right|^{p}\right]\right)^{1/p}\leq
K_{2}\sqrt{p}\;\;\forall p\geq 1.$

  3. 3.

The Moment Generating Function (MGF) of $X^{2}$ satisfies

$\mathbb{E}\left[\exp{\left(\lambda^{2}X^{2}\right)}\right]\leq\exp{\left(K_{3}^{2}\lambda^{2}\right)}\;\;\forall\lambda\;\;s.t.\;\;|\lambda|\leq\dfrac{1}{K_{3}}.$

  4. 4.

The MGF of $X^{2}$ is bounded at some point, namely

$\mathbb{E}\left[\exp{\left(\dfrac{X^{2}}{K_{4}}\right)}\right]\leq 2.$

Moreover, if $\mathbb{E}[X]=0$, then properties $1-4$ are also equivalent to
the following one.

  1. 5.

The MGF of $X$ satisfies

$\mathbb{E}\left[\exp{\left(\lambda
X\right)}\right]\leq\exp{\left(K_{5}^{2}\lambda^{2}\right)}\;\;\forall\lambda\in\mathbb{R}.$

For mathematical convenience, we use the fourth characterization in Theorem
4.1 to define a Sub-Gaussian random variable.

######  Definition 4.1 (Sub-Gaussian random variable).

Let $X$ be a random variable. If there exists $K>0$ such that the MGF of $X$
satisfies

$\mathbb{E}[\exp{X^{2}/K}]\leq 2.$

Then $X$ is called a Sub-Gaussian random variable, and its norm is given by

$\|X\|_{\psi_{2}}=\displaystyle\mathop{\mbox{\rm
inf}}\\{t>0\;:\;\mathbb{E}[\exp{X^{2}/t^{2}}]\leq 2\\},$

where the notation $\|\cdot\|_{\psi_{2}}$ refers to the fact that it is an
Orlicz norm for the function

$\psi_{2}(u)=\exp\\{u^{2}\\}-1;$

see Vershynin [26, Section 2.7.1] for additional details.

Useful properties of Sub-Gaussian RVs are listed in Remark 4.1.

######  Remark 4.1 (Sub-Gaussians useful properties).

The following properties holds true:

  1. 1.

If $Prob\left(X^{2}>0\right)>0$, then $\|X\|_{\psi_{2}}>0$. On the other hand,
if $X=0$ almost surely, then $\|X\|_{\psi_{2}}=0$.

  2. 2.

For a random variable $X$, $\|X\|_{\psi_{2}}<\infty$ if and only if $X$ is
Sub-Gaussian.

  3. 3.

If a random variable $Y$ is bounded almost surely, i.e., there exists
$a\in\mathbb{R}_{+}$ such that $Prob\left(|Y|\leq a\right)=1$, then there
exists $K>0$ such that

$\mathbb{E}[\exp{Y^{2}/K}]\leq 2.$

Therefore, it follows that $Y$ is Sub-Gaussian.

  4. 4.

If $X$ is a Sub-Gaussian random variable, then $X-\mathbb{E}[X]$ is also Sub-
Gaussian.

With the definitions of Sub Gaussian random variables at hand, we can now
state the optional assumption 4. While this assumption is not mandatory, it
allows for a significant improvement in our sampling mechanism.

######  Assumption 4.

For any $(i,j)\in[n]$ and any $t\geq 0$, the random variable $M^{t}_{i,j}$
sampled by Algorithm 1 is Sub-Gaussian.

It should be emphasized that 4 is very general. Any random variable whose tail
distribution can be bounded by a Gaussian random variable (up to a constant)
is Sub-Gaussian. This includes all bounded random variables, such as Bernoulli
and Rademacher distributed random variables, and the Gaussian distribution.

Our analysis and results will be mostly given in terms of the component-wise
deviation matrix given by the difference between the estimator and the
expected value of its corresponding random matrix variable. We call this
matrix the error of the matrix estimator, and denote it by

$\delta(\bar{M},M):=\bar{M}-\mathbb{E}[M],$ (4.1)

where $\bar{M}$ is the estimator of the random variable matrix $M$. The
definition in (4.1) will almost always be given with respect to a sequence
sampled by Algorithm 1, and therefore, we will use the abbreviation

$\delta_{t}:=\delta(\bar{M}^{t},M)=\bar{M}^{t}-\mathbb{E}[M],$ (4.2)

where we assume that the couple $(\bar{M}^{t},M)$ is known from context; note
that $\delta_{t}$ is a random variable until realized.

To establish the essential properties of the random variable $\delta_{t}$, we
will utilize the notion of infinitely often (i.o.) occurring event, which is
defined below.

######  Definition 4.2 (infinitely often (i.o.)).

Let $A_{1},A_{2},...$ be a sequence of events in some probability space. Then
the probability that infinitely many of them occur is denoted by

$Prob\left(A_{n}\;i.o.\right)\equiv
Prob\left(\limsup_{n\to\infty}A_{n}\right)\equiv
Prob\left(\bigcap\limits_{n=1}^{\infty}\bigcup\limits_{k=n}^{\infty}A_{k}\right).$

We use $i.o.$ occuring events in our analysis to prove that

$Prob\left(\sum\limits_{t=1}^{\infty}\|\delta_{t}\|^{2}<\infty\right)=1.$

To that end, we will use the fact that for every $\epsilon>0$

$\sum\limits_{t=1}^{\infty}\dfrac{1}{t^{1+0.5\cdot\epsilon}}<\infty.$

Choose an arbitrary $\epsilon>0$. Suppose that there are at most a finite
amount of indices $t$ such that
$\|\delta_{t}\|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}$. Then there exists a
final index $K$, such that for all $t\geq K+1$,
$\|\delta_{t}\|\leq\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}$. Since the image of
$\|\delta_{t}\|$ is contained in $\mathbb{R}$, it follows that
$\sum\limits_{t=1}^{K}\|\delta_{t}\|^{2}<\infty$. Since for every $t\geq K+1$,
$\|\delta_{t}\|\leq\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}$, it follows that

$\sum\limits_{t=1}^{\infty}\|\delta_{t}\|^{2}=\sum\limits_{t=1}^{K}\|\delta_{t}\|^{2}+\sum\limits_{t=K+1}^{\infty}\|\delta_{t}\|^{2}<\infty.$

Consider the event
$A_{t}\equiv\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)$.
We can deduce from our discussion above that

$Prob\left(\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\;i.o.\right)=0\Rightarrow
Prob\left(\sum\limits_{t=1}^{\infty}\|\delta_{t}\|^{2}<\infty\right)=1.$

This suggests that we should pick $\\{\theta_{t}\\}_{t>0}$ so that

$Prob\left(\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right);i.o.\right)=0$

holds true. To that end, we first discuss some well known results in
probability.

The first result is the General Hoeffding’s inequality.

######  Theorem 4.2 (Vershynin [26, Theorem 2.6.2, General Hoeffding’s
Inequality]).

Let $X_{1},X_{2},\ldots,X_{m}$ be independent, zero mean, Sub-Gaussian random
variables. Then, for every $k\geq 0$, we have

$Prob\left(\left|\sum_{i=1}^{m}X_{i}\right|>k\right)\leq
2\exp{\left(-\dfrac{ck^{2}}{\sum_{i=1}^{m}\|X_{i}\|_{\psi_{2}}^{2}}\right)}.$

For completeness, we also present the better known case of Hoeffding’s
inequality for bounded random variables.

######  Theorem 4.3 (Boucheron et al. [9, Theorem 2.8, Hoeffding’s
Inequality]).

Let $X_{1},X_{2},\ldots$ be a sequence of independent random variables, such
that for all $i\geq 1$, $\infty<a\leq X_{i}\leq b<\infty$ almost surely. Then
for every $k>0$

$Prob\left(\left|\dfrac{1}{m}\sum_{i=1}^{m}X_{i}-\mathbb{E}[X_{i}]\right|>k\right)\leq
2\exp{\left(-\dfrac{2mk^{2}}{(b-a)^{2}}\right)}.$

As we discussed above, bounded random variables are Sub-Gaussian, so the
General Hoeffding’s inequality is indeed a generalization.

The second result is the Borel-Cantelli Theorem.

######  Theorem 4.4 (Borovkov [7, Theorem 11.1.1, Borel-Cantelli Theorem]).

Let $\\{A_{i}\\}_{i=1}^{\infty}$ be an infinite sequence of events defined
over a given probability space, and denote by
$A=\bigcap\limits_{n=1}^{\infty}\bigcup\limits_{k=n}^{\infty}A_{k}$ the event
that infinitely many events of the sequence $\\{A_{i}\\}_{i=1}^{\infty}$
occur. If

$\sum_{i=1}^{\infty}Prob\left(A_{i}\right)<\infty,$

then

$Prob\left(A\right)=0.$

As we stated previously, the sampling rate regime, expressed by the sequence
$\\{\theta_{t}\\}_{t\geq 0}$, is chosen to guarantee that

$Prob\left(\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\;i.o.\right)=0.$

In the general case, $\theta_{t}$ should be proportional to $t^{2+\epsilon}$,
where $\epsilon>0$ is arbitrarily small – this is described by 4.1. When the
elements of the sampled matrix are Sub-Gaussian, we derive a looser sampling
rate proportional to $t^{1+\epsilon}$ (once again, $\epsilon>0$ is arbitrarily
small) – as stated in 4.2. Both lemmas are based on the Borel-Cantelli
Theorem. 4.1 additionally uses Chebyshev’s inequality, while 4.2 uses Theorem
4.2.

######  Lemma 4.1.

Let $\\{M^{t}\\}_{t>0}$ be a sequence of i.i.d random matrices with
distribution $M^{i}\sim\pi$ sampled by Algorithm 1 with $\epsilon>0$ and
$\theta_{t}=t^{2+\epsilon}$. Then,

$Prob\left(\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\epsilon}}\right)\;i.o.\right)=0.$

###### Proof.

Recall that

$\delta_{t}=\bar{M}^{t}-\mathbb{E}[M],$ (4.3)

meaning that $\mathbb{E}[\delta_{t}]=0$.

Hence, by definition of the variance and the unbiasedness of the estimator,

$Var[[\delta_{t}]_{i,j}]=\mathbb{E}[[\delta_{t}]_{i,j}^{2}]-\mathbb{E}[[\delta_{t}]_{i,j}]^{2}=\mathbb{E}[[\delta_{t}]_{i,j}^{2}].$

Consequently, using (4.3) and the fact that
$\mathbb{E}[[\delta_{t}]_{i,j}]=0$, we have that

$Var[[\delta_{t}]_{i,j}]=\mathbb{E}[[\delta_{t}]_{i,j}^{2}]=\mathbb{E}[(\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j})^{2}].$

Thus, by the definition of $\bar{M}^{t}$

$\displaystyle
Var[[\delta_{t}]_{i,j}]=\mathbb{E}[(\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j})^{2}]=\mathbb{E}\left[\left(\dfrac{1}{\theta_{t}}\sum_{k=1}^{\theta_{t}}M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)^{2}\right].$

Expanding the right hand term

$Var[[\delta_{t}]_{i,j}]=\mathbb{E}\left[\dfrac{1}{\theta_{t}^{2}}\left(\sum_{k=1}^{\theta_{t}}\left(M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)^{2}+2\sum_{k=1}^{\theta_{t}}\sum_{l=1}^{k-1}\left(M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)\cdot\left(M^{l}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)\right)\right].$
(4.4)

By the assumption that the matrix sequence $\\{M^{t}\\}_{t=1}^{\infty}$ is
i.i.d, we have that for every $k\neq l$

$\mathbb{E}\left[\left(M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)\cdot\left(M^{l}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)\right]=\mathbb{E}\left[M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right]\cdot\mathbb{E}\left[M^{l}_{i,j}-[\mathbb{E}[M]]_{i,j}\right].$

Furthermore, noting that
$\mathbb{E}\left[M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right]=0$ for all $k$, we
can restate (4.4) as follows:

$Var[[\delta_{t}]_{i,j}]=\mathbb{E}\left[\dfrac{1}{\theta_{t}^{2}}\sum_{k=1}^{\theta_{t}}\left(M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)^{2}\right].$
(4.5)

By the linearity of expectation, (4.5) can be reformulated as

$Var[[\delta_{t}]_{i,j}]=\dfrac{1}{\theta_{t}^{2}}\sum_{k=1}^{\theta_{t}}\mathbb{E}\left[\left(M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)^{2}\right].$
(4.6)

By definition,

$Var[M^{k}_{i,j}]=\mathbb{E}\left[\left(M^{k}_{i,j}-[\mathbb{E}[M]]_{i,j}\right)^{2}\right].$
(4.7)

Using (4.7), we can restate (4.6) as

$Var[[\delta_{t}]_{i,j}]=\dfrac{1}{\theta_{t}^{2}}\sum_{k=1}^{\theta_{t}}Var[M^{k}_{i,j}].$
(4.8)

The result in (4.8) can be further refined using the fact that the matrices
$\\{M\\}_{i=1}^{\infty}$ are sampled independently from the same distribution,
and so for every $k\geq 0$,

$Var[M^{k}_{i,j}]=Var[M^{0}_{i,j}].$

Denoting $M=M^{0}$, we obtain

$Var[[\delta_{t}]_{i,j}]=\dfrac{1}{\theta_{t}^{2}}\sum_{k=1}^{\theta_{t}}Var[M_{i,j}]=\dfrac{1}{\theta_{t}}Var[M_{i,j}].$
(4.9)

Subsequently, using Chebyshev’s inequality we have that

$Prob(|[\delta_{t}]_{i,j}|>\eta)\leq\dfrac{Var[|[\delta_{t}]_{i,j}|]}{\eta^{2}}=\dfrac{Var[M_{i,j}]}{\theta_{t}\eta^{2}}.$

Thus, choosing $\theta_{t}=t^{2+\epsilon}$,
$\eta=\dfrac{1}{t^{0.5+0.25\epsilon}}$, and applying Chebyshev’s inequality
yields

$Prob\left(|[\delta_{t}]_{i,j}|>\dfrac{1}{t^{0.5+0.25\epsilon}}\right)\leq\dfrac{Var[M_{i,j}]}{t^{1+0.5\epsilon}}.$
(4.10)

Consider the element-wise matrix norm
$\|\delta_{t}\|_{1,1}=\sum_{i=1}^{n}\sum_{j=1}^{n}|[\delta_{t}]_{i,j}|$. If
$\|\delta_{t}\|_{1,1}>\dfrac{n^{2}}{t^{0.5+0.25\epsilon}}$, then by the
pigeonhole principle, at least one of the events
$|[\delta_{t}]_{i,j}|>\dfrac{1}{t^{0.5+0.25\epsilon}}$ occurred. Therefore,

$Prob\left(\|\delta_{t}\|_{1,1}>\dfrac{n^{2}}{t^{0.5+0.25\epsilon}}\right)\leq
Prob\left(\bigcup_{i,j}\left\\{|[\delta_{t}]_{i,j}|>\dfrac{1}{t^{0.5+0.25\epsilon}}\right\\}\right).$

Consequently, using the union bound together with (4.10) implies that

$Prob\left(\|\delta_{t}\|_{1,1}>\dfrac{n^{2}}{t^{0.5+0.25\epsilon}}\right)\leq\dfrac{1}{t^{1+0.5\epsilon}}\sum_{i=1}^{n}\sum_{j=1}^{n}Var[M_{i,j}].$

By the equivalence between norms in $\mathbb{R}^{n\times n}$, there exist
$a,A>0$, such that

$a\cdot\|\delta_{t}\|_{1,1}\leq\|\delta_{t}\|_{2,2}\leq
A\cdot\|\delta_{t}\|_{1,1},$

where $\|\delta_{t}\|_{2,2}$ is the induced $\ell_{2}$ norm on the matrix
$\delta_{t}$; see Fabian et al. [14, Definition 1.30] for the definition of
equivalence of norms, and Fabian et al. [14, Proposition 1.36] for the
equivalence of norms in finite dimensional vector spaces. Since we use
$\|\delta_{t}\|=\|\delta_{t}\|_{2,2}$ by default (see the discussion of norm
notation in Section 2.1), it follows that

$Prob\left(\|\delta_{t}\|>\dfrac{a\cdot
n^{2}}{t^{0.5+0.25\epsilon}}\right)\leq\dfrac{1}{t^{1+0.5\epsilon}}\sum_{i=1}^{n}\sum_{j=1}^{n}Var[M_{i,j}].$

Finally, setting $r=\sum_{i=1}^{n}\sum_{j=1}^{n}Var[M_{i,j}]$ and using the
fact that $\sum_{i=1}^{n}\sum_{j=1}^{n}Var[M_{i,j}]$ is finite (cf. 1), we
conclude that

$\sum_{t=1}^{\infty}Prob\left(\|\delta_{t}\|>\dfrac{a\cdot
n^{2}}{t^{0.5+0.25\epsilon}}\right)\leq\sum_{t=1}^{\infty}\dfrac{r}{t^{1+0.5\epsilon}}<\infty,$

and subsequently, the lemma follows from Theorem 4.4. $\Box$

######  Lemma 4.2.

Let $\\{M^{t}\\}_{t>0}$ be a sequence of i.i.d random matrices with
distribution $M^{i}\sim\pi$ sampled during the execution of Algorithm 1 with
$\theta_{t}=t^{1+\epsilon}$ for some $\epsilon>0$. Assume that for every
$i,j\in[n]$ and every $t\geq 0$, $M^{t}_{i,j}$ is Sub-Gaussian. Then,

$Prob\left(\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\;i.o.\right)=0.$

###### Proof.

Since $M^{t}_{i,j}$ is Sub-Gaussian, $M^{t}_{i,j}-\mathbb{E}[M]_{i,j}$ and
$\dfrac{1}{\theta_{t}}(M^{t}_{i,j}-\mathbb{E}[M]_{i,j})$ are also Sub-Gaussian
(cf. Remark 4.1, Part 4). Recall that

$\delta_{t}=\bar{M}^{t}-\mathbb{E}[M]=\sum_{l=1}^{\theta_{t}}\dfrac{1}{\theta_{t}}(M^{l}-\mathbb{E}[M]),$

where $\bar{M}^{t}=\dfrac{1}{\theta_{t}}\sum\limits_{l=1}^{\theta_{t}}M^{l}$
is the estimator of $M$. Hence,

$\displaystyle
Prob\left(\left|[\delta_{t}]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)$
$\displaystyle=Prob\left(\left|\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)$
$\displaystyle=Prob\left(\left|\sum_{l=1}^{\theta_{t}}\dfrac{1}{\theta_{t}}(M^{l}_{i,j}-\mathbb{E}[M]_{i,j})\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right).$

If $Prob\left([\delta_{t}]_{i,j}\neq 0\right)=0$, then the inequality

$Prob\left(\left|[\delta_{t}]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
2\exp\left(-C\cdot t^{0.5\epsilon}\right)$ (4.11)

holds trivially for any $C>0$.

Otherwise, if $Prob\left([\delta_{t}]_{i,j}\neq 0\right)>0$ then by Remark 4.1
$\|\dfrac{1}{\theta_{t}}(M^{l}_{i,j}-\mathbb{E}[M]_{i,j})\|_{\psi_{2}}>0$, and
we have by the General Hoeffding’s Inequality (cf. Theorem 4.2) with
$m=\theta_{t}$ and $k=\dfrac{1}{t^{0.5+0.25\epsilon}}$ that

$\displaystyle
Prob\left(\left|[\delta_{t}]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)$
$\displaystyle=Prob\left(\left|\sum_{l=1}^{\theta_{t}}\dfrac{1}{\theta_{t}}(M^{l}_{i,j}-\mathbb{E}[M]_{i,j})\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)$
$\displaystyle\leq
2\exp\left(-\dfrac{c\cdot\dfrac{1}{t^{1+0.5\epsilon}}}{\sum_{l=1}^{\theta_{t}}\|\dfrac{1}{\theta_{t}}(M^{l}_{i,j}-\mathbb{E}[M]_{i,j})\|_{\psi_{2}}^{2}}\right).$

Using the fact that $\\{M^{l}\\}_{l\geq 0}$ are i.i.d and the norm property
$\|\lambda\xi\|=|\lambda|\|\xi\|$, it follows that

$\displaystyle
Prob\left(\left|[\delta_{t}]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)$
$\displaystyle\leq
2\exp\left(-\dfrac{c\cdot\dfrac{1}{t^{1+0.5\epsilon}}}{\sum_{l=1}^{\theta_{t}}\|\dfrac{1}{\theta_{t}}(M^{l}_{i,j}-\mathbb{E}[M]_{i,j})\|_{\psi_{2}}^{2}}\right)$
$\displaystyle=2\exp\left(-\dfrac{c\cdot\dfrac{1}{t^{1+0.5\epsilon}}}{\theta_{t}\cdot\dfrac{1}{\theta_{t}^{2}}\|M^{0}_{i,j}-\mathbb{E}[M]_{i,j}\|_{\psi_{2}}^{2}}\right).$

Denoting

$C=\dfrac{c}{\|M^{0}_{i,j}-\mathbb{E}[M]_{i,j}\|_{\psi_{2}}^{2}}$

and rearranging the elements we obtain that

$Prob\left(\left|[\delta_{t}]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
2\exp\left(-C\cdot\dfrac{\theta_{t}}{t^{1+0.5\epsilon}}\right).$

By the choice of $\theta_{t}$ we then have that

$Prob\left(\left|[\delta_{t}]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
2\exp\left(-C\cdot t^{0.5\epsilon}\right).$ (4.12)

Thus, whether $Prob\left([\delta_{t}]_{i,j}\neq 0\right)=0$ or
$Prob\left([\delta_{t}]_{i,j}\neq 0\right)>0$, there exists a constant $C>0$,
such that

$Prob\left(\left|\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
2\exp\left(-C\cdot t^{0.5\epsilon}\right).$ (4.13)

Consider the entry-wise $\ell_{1}$ norm of
$\delta_{t}=\bar{M}^{t}-\mathbb{E}[M]$,

$\|\delta_{t}\|_{1,1}=\sum_{i=1}^{n}\sum_{j=1}^{n}\left|\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j}\right|.$

Note that for the event

$\|\delta_{t}\|_{1,1}>\dfrac{n^{2}}{t^{0.5+0.25\cdot\epsilon}}$

to occur, by the pigeonhole principle there has to be at least one pair of
indices ${i,j}$ such that
$\left|\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}$.
Therefore,

$Prob\left(\|\delta_{t}\|_{1,1}>\dfrac{n^{2}}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
Prob\left(\bigcup_{i,j}\left\\{\left|\bar{M}^{t}_{i,j}-\mathbb{E}[M]_{i,j}\right|>\dfrac{1}{t^{0.5+0.25\cdot\epsilon}}\right\\}\right).$

Using the union bound, it follows that

$Prob\left(\|\delta_{t}\|_{1,1}>\dfrac{n^{2}}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
2n^{2}\exp\left(-Ct^{0.5\epsilon}\right).$

As stated in 4.1, by the equivalence between norms in $\mathbb{R}^{n\times
n}$, there exist $a,A>0$, such that

$a\cdot\|\delta_{t}\|_{1,1}\leq\|\delta_{t}\|_{2,2}\leq
A\cdot\|\delta_{t}\|_{1,1}.$

Since we use $\|\delta_{t}\|=\|\delta_{t}\|_{2,2}$ by default (see the
discussion of norm notation in Section 2.1), it follows that

$Prob\left(\|\delta_{t}\|>\dfrac{a\cdot
n^{2}}{t^{0.5+0.25\cdot\epsilon}}\right)\leq
2n^{2}\exp\left(-Ct^{0.5\epsilon}\right).$

Summing over $t$

$\sum_{t=1}^{\infty}Prob\left(\|\delta_{t}\|>\dfrac{a\cdot
n^{2}}{t^{0.5+0.25\cdot\epsilon}}\right)\leq\sum_{t=1}^{\infty}2n^{2}\cdot\exp\left(-Ct^{0.5\epsilon}\right)<\infty,$

and the result follows from Theorem 4.4. $\Box$

Note that in both lemmas, $\epsilon$ can be chosen to be arbitrarily small. If
the sampling mechanism generates matrices $\\{M^{i}\\}_{i=1}^{\infty}$ of a
Sub-Gaussian distribution as stated in the conditions of 4.2, we can choose
$\theta_{t}=t^{1+\epsilon}$ so that $\theta_{t}$ is arbitrarily close to being
linear in $t$.

The next claim states a technical result on the convergence of
$\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})$ to
$\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])$. It will be used in Section 5
and Section 6.

######  Lemma 4.3.

Let $\\{\bar{M}^{t}\\}_{t>0}$ be a sequence of unbiased estimators of $M$,
such that $\bar{M}^{t}\xrightarrow{t\to\infty}\mathbb{E}[M]$ almost surely.
For any $\epsilon\in(0,1)$, with probability 1, there exists $K>0$ such that

$(1-\epsilon)\sigma\leq\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq(1+\epsilon)\sigma,\qquad\forall
k>K,$

and

$(1-\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\sigma\leq(1+\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}}),\qquad\forall
k>K,$

where $\sigma=\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])$, as defined in 2.

###### Proof.

We use the following identity for the smallest eigenvalue of $A^{T}A$, where
$A$ is some arbitrary matrix:

$\lambda_{min}(A^{T}A)=\min\limits_{\|v\|=1}v^{T}A^{T}Av=\min\limits_{\|v\|=1}\|Av\|^{2}.$

Define the vector sequence $\\{u_{k}\\}_{k=1}^{\infty}$ and the vector $w$ as

$u_{k}\in\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{\|v\|=1}{\|\bar{M}^{k}v\|^{2}}$ (4.14)

and

$w\in\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{\|v\|=1}{\|\mathbb{E}[M]v\|^{2}}.$ (4.15)

By our choice of $u_{k}$ in (4.14),

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}=\|\bar{M}^{k}u_{k}\|.$

Applying the facts that $u_{k}$ is the minimizer, and $w$ is a feasible
solution to (4.14), we obtain that

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}=\|\bar{M}^{k}u_{k}\|\leq\|\bar{M}^{k}w\|.$
(4.16)

Next, we bound $\|\bar{M}^{k}w\|$ in terms of $\sigma$ and the matrix
estimation error. Recall that by (4.1)

$\delta(\bar{M}^{t},M):=\bar{M}^{t}-\mathbb{E}[M].$

By the triangle inequality, $\|a+b\|\geq\|a\|-\|b\|$, and
$\|a+b\|\leq\|a\|+\|b\|$. Therefore, using the estimation error
$\delta(\bar{M}^{k},M)$ for every $q\in\mathbb{R}^{n}$

$\|\bar{M}^{k}q\|=\|\mathbb{E}[M]q+\delta(\bar{M}^{k},M)q\|\leq\|\mathbb{E}[M]q\|+\|\delta(\bar{M}^{k},M)q\|,$
(4.17)

and

$\|\bar{M}^{k}q\|=\|\mathbb{E}[M]q+\delta(\bar{M}^{k},M)q\|\geq\|\mathbb{E}[M]q\|-\|\delta(\bar{M}^{k},M)q\|.$
(4.18)

Using $\bar{M}^{t}=\mathbb{E}[M]+\delta(\bar{M}^{t},M)$, in addition to the
inequalities we’ve established in (4.16), (4.17), we have

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\leq\|\bar{M}^{k}w\|=\|\mathbb{E}[M]w+\delta(\bar{M}^{t},M)w\|\leq\|\mathbb{E}[M]w\|+\|\delta(\bar{M}^{t},M)w\|.$

By our choice of $w$ in (4.18), it holds that

$\|\mathbb{E}[M]w\|=\sqrt{\sigma}.$

Hence,

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\leq\sqrt{\sigma}+\|\delta(\bar{M}^{t},M)w\|.$

Next, we bound the term $\|\delta(\bar{M}^{t},M)w\|$. Using the induced norm
inequality,

$\|\delta(\bar{M}^{t},M)w\|_{2}\leq\|\delta(\bar{M}^{t},M)\|_{2,2}\|w\|_{2}.$

Because $\|w\|_{2}=1$, it follows that

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\leq\sqrt{\sigma}+\|\delta(\bar{M}^{t},M)\|_{2,2}.$

To bound $\|\delta(\bar{M}^{t},M)\|_{2,2}$, note that since
$\bar{M}^{t}\xrightarrow{t\to\infty}\mathbb{E}[M]$ almost surely, there exists
with probability $1$ an iteration $K_{1}>0$, such that

$\|\delta(\bar{M}^{k},M)\|_{2,2}\leq(\sqrt{1+\epsilon}-1)\sqrt{\sigma}\qquad\forall
k>K_{1}.$

Therefore, for all sufficiently large $k$,

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\leq\sqrt{\sigma}+\|\delta(\bar{M}^{t},M)\|_{2,2}\leq\sqrt{(1+\epsilon)\sigma}.$

Since both sides of the inequality are non-negative, we can square them, and
get

$\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})\leq(1+\epsilon)\sigma.$ (4.19)

For the other direction, we once again use the fact that by (4.14)

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}=\|\bar{M}^{k}u_{k}\|.$
(4.20)

Utilizing the equality $\bar{M}^{t}=\mathbb{E}[M]+\delta(\bar{M}^{t},M)$ and
the inequalities established at (4.20), (4.18), we derive

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\geq\|\mathbb{E}[M]u_{k}\|-\|\delta(\bar{M}^{k},M)u_{k}\|.$

Since $u_{k}$ is a feasible solution to (4.15), and $w$ is the minimizer,

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\geq\|\mathbb{E}[M]u_{k}\|-\|\delta(\bar{M}^{k},M)u_{k}\|\geq\|\mathbb{E}[M]w\|-\|\delta(\bar{M}^{k},M)u_{k}\|.$

Utilizing the fact that by (4.15), $\|\mathbb{E}[M]w\|=\sqrt{\sigma}$,

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\geq\sqrt{\sigma}-\|\delta(\bar{M}^{k},M)u_{k}\|.$

To further refine the lower bound of
$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}$, we use the induced norm
inequality, and the fact that $\|u_{k}\|=1$, to derive that

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\geq\sqrt{\sigma}-\|\delta(\bar{M}^{k},M)u_{k}\|\geq\sqrt{\sigma}-\|\delta(\bar{M}^{k},M)\|_{2,2}\|u_{k}\|_{2}=\sqrt{\sigma}-\|\delta(\bar{M}^{k},M)\|_{2,2}.$
(4.21)

Since $\bar{M}^{t}\xrightarrow{t\to\infty}\mathbb{E}[M]$ almost surely, there
exists with probability $1$ an iteration $K_{2}>0$, such that

$\|\delta(\bar{M}^{k},M)\|_{2,2}\leq(1-\sqrt{1-\epsilon})\sqrt{\sigma}\qquad\forall
k>K_{2}.$

Applying this bound to (4.21), for all sufficiently large $k$,

$\sqrt{\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})}\geq\sqrt{\sigma}-\|\delta(\bar{M}^{k},M)\|_{2,2}\geq\sqrt{(1-\epsilon)\sigma},$

and therefore

$\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})\geq(1-\epsilon)\sigma.$

Combining with (4.19), we conclude that for all $k>\max\\{K_{1},K_{2}\\}$,

$(1-\epsilon)\sigma\leq\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})\leq(1+\epsilon)\sigma,$
(4.22)

which concludes the first part of the proof.

To see that

$(1-\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\sigma\leq(1+\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}}),$

for all sufficiently large $k$, we choose $0<\epsilon^{\prime}<1$ such that
$\dfrac{1}{1+\epsilon^{\prime}}>1-\epsilon$, and
$\dfrac{1}{1-\epsilon^{\prime}}<1+\epsilon$. By the first part of the proof,
there exists $K_{3}>0$ such that

$(1-\epsilon^{\prime})\sigma\leq\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq(1+\epsilon^{\prime})\sigma\qquad\forall
k>K_{3}.$

Combining with our choice of $\epsilon^{\prime}$,

$(1-\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\dfrac{1}{1+\epsilon^{\prime}}\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\sigma,$

and

$\sigma\leq\dfrac{1}{1-\epsilon^{\prime}}\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq(1+\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}}).$

We conclude that

$(1-\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\sigma\leq(1+\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}}).$

Combining with (4.22), we conclude that for all
$k>\max\\{K_{1},K_{2},K_{3}\\}$,

$(1-\epsilon)\sigma\leq\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})\leq(1+\epsilon)\sigma$

and

$(1-\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\sigma\leq(1+\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})$

hold true, which concludes the proof. $\Box$

From here onwards, we will assume that $\\{\theta_{t}\\}_{t\geq 0}$ is chosen
according to the sampling regime that is defined below:

######  Definition 4.3 (Sampling Regime).

Let $\epsilon>0$ be an arbitrary positive constant. If 4 holds, we choose
$\theta_{t}=t^{1+\epsilon}$. Otherwise, we choose $\theta_{t}=t^{2+\epsilon}$.

######  Remark 4.2.

The sampling regime can be changed by a constant nonnegative factor, that is,
we may choose $\theta_{t}=at^{1+\epsilon}$ or $\theta_{t}=at^{2+\epsilon}$
depending on 4, where $a>0$. For simplicity, we assume that $a=1$.

To summarize the results in this section, we conclude that given $\theta_{t}$
samples gathered until the $t$-th iteration, that is, at round $t+1$ we sample
$\theta_{t+1}-\theta_{t}$ times,

$Prob\left(\|\delta_{t}\|>O\left(\dfrac{1}{t^{0.5+0.25\epsilon}}\right)\;i.o\right)=0,$

and therefore

$Prob\left(\sum_{t=1}^{\infty}\|\delta_{t}\|^{2}<\infty\right)=1.$

Furthermore, for every $\epsilon>0$, there exists almost surely an iteration
$K>0$, such that for any $k>K$ it holds that

$(1-\epsilon)\sigma\leq\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq(1+\epsilon)\sigma$

and

$(1-\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}})\leq\sigma\leq(1+\epsilon)\lambda_{min}((\bar{M^{k}})^{T}\bar{M^{k}}).$

##  5 ISAD for Problems with Bounded Hessian

The meta-algorithm we introduced in Algorithm 1 contains two components that
can be chosen by the implementor – an APO with the requirements in 3.1 and a
convex function $\phi$. In this section we show that for functions with a
bounded hessian (cf. 5) we can use a simple pair of APO and function $\phi$.
The APO and our choice of $\phi$ are described by Algorithm 3 and Equation
5.1.

Accordingly, in this section we make the following additional assumption.

######  Assumption 5.

For every $x\in\mathbb{R}^{n}$, it holds that

$-\gamma I\preceq\nabla^{2}h(x)\preceq\gamma I.$

5 is satisfied by a broad class of objective functions, such as the
prototypical examples we list below.

  1. 1.

Quadratic functions,

$h(x)=x^{t}Qx+b^{T}x+c,$

where $Q\in\mathbb{R}^{n\times n}$, $b\in\mathbb{R}^{n}$ and $c\in\mathbb{R}$.

  2. 2.

The distance function (see e.g., Beck [2, Example 5.5])

$h(x)=\dfrac{1}{2}\cdot d_{C}(x)^{2},$

where $C$ is a compact set, and $d:\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$ is
the Euclidean distance of the input vector from $C$ defined as

$d_{C}(x)=\left\|x-\displaystyle\mathop{\mbox{\rm argmin}}\limits_{y\in
C}\left\\{\left\|y-x\right\|\right\\}\right\|.$

  3. 3.

A binary logistic regression objective function. Given $n$ tuples
$\\{(y_{i},x_{i})\\}_{i=1}^{n}$, where $y_{i}$ is an independent binary
observation, and $x_{i}$ is the observation’s feature vector. The goal is to
maximize the likelihood of the observations, which can be cast as minimizing
the minus log likelihood (see Boyd et al. [10, Chapter 7]) given by

$\displaystyle
l(\theta)=-\sum\limits_{i=1}^{n}y_{i}\ln\left(\dfrac{\exp\\{x_{i}^{T}\theta\\}}{1+\exp\\{x_{i}^{T}\theta\\}}\right)+\left(1-y_{i}\right)\ln\left(\dfrac{1}{1+\exp\\{x_{i}^{T}\theta\\}}\right).$

We show in A.1, placed in the appendix, that the second derivative of
$l(\theta)$ is bounded with respect to $\theta$.

We also assume that the meta-algorithm (cf. Algorithm 1) is implemented with
the function

$\phi(x)=\dfrac{\gamma}{2}\|x\|^{2}-h(x),$ (5.1)

and with the APO given in Algorithm 3.

######  Remark 5.1.

Our choice for $\phi$, given in (5.1), is convex, because

$0\preceq\nabla^{2}\phi(x)=\gamma I-\nabla^{2}h(x)\preceq 2\gamma I.$

The following lemma discusses the properties of the $x$ update given that 5
holds true and $\phi$ is chosen as in (5.1). The lemma will not affect the
remainder of the analysis. Rather, it would provide motivation for the
analysis of the simplified case, where 5 holds true.

######  Lemma 5.1.

Suppose that 5 holds true, and that $\phi$ is chosen as in (5.1). Then,

  1. 1.

$g^{t+1}$ is $\dfrac{\gamma}{2}$–strongly convex and
$\dfrac{\gamma+\beta_{t}\lambda_{max}((\bar{M}^{t+1})^{T}\bar{M}^{t+1})}{2}$
smooth.

  2. 2.

The $x$ update is equivalent to

$x_{t+1}=\displaystyle\mathop{\mbox{\rm argmin}}\limits_{x}g^{t+1}(x).$

  3. 3.

The closed-form solution for the $x$ update is given by

$x_{t+1}=\left(\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}+\gamma
I\right)^{-1}\left(\left(\bar{M}^{t}\right)^{T}z_{t}+\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}y_{t+1}+\gamma
x_{t}-\nabla h\left(x_{t}\right)\right).$

###### Proof.

First, recall that the $x$ update as defined in Algorithm 1 is

$x_{t+1}\in\operatorname{Crit}\limits_{x}\\{g^{t+1}(x)=h(x)-\langle{z_{t}},\bar{M^{t}}x\rangle+\dfrac{\beta_{t}}{2}\|{\bar{M}^{t+1}x-y_{t+1}}\|^{2}+D_{\phi}(x,x_{t})\\}.$

To prove all three parts, we show that $g^{t+1}$ is a quadratic function

$g^{t+1}(x)=\dfrac{1}{2}\langle x,Ax\rangle+\langle b,x\rangle+c,$ (5.2)

such that $A$ is positive definite.

We start by restating $D_{\phi}(x,x_{t})$ for our particular choice of $\phi$

$\displaystyle D_{\phi}(x,x_{t})$
$\displaystyle=\dfrac{\gamma}{2}\|x\|^{2}-h(x)-\dfrac{\gamma}{2}\|x_{t}\|^{2}+h(x_{t})-\langle\gamma
x_{t}-\nabla h(x_{t}),x-x_{t}\rangle$
$\displaystyle=\dfrac{\gamma}{2}\|x\|^{2}-\gamma
x^{T}x_{t}-\dfrac{\gamma}{2}\|x_{t}\|^{2}+\gamma\|x_{t}\|^{2}-h(x)+h(x_{t})+\langle\nabla
h(x_{t}),x-x_{t}\rangle$ $\displaystyle=\dfrac{\gamma}{2}\|x\|^{2}-\gamma
x^{T}x_{t}+\dfrac{\gamma}{2}\|x_{t}\|^{2}-h(x)+h(x_{t})+\langle\nabla
h(x_{t}),x-x_{t}\rangle$
$\displaystyle=\dfrac{\gamma}{2}\|x-x_{t}\|^{2}-h(x)+h(x_{t})+\langle\nabla
h(x_{t}),x-x_{t}\rangle.$

Applying to the definition of $g^{t+1}(x)$,

$\displaystyle g^{t+1}(x)$ $\displaystyle=h(x)-\langle
z_{t},\bar{M}^{t}x\rangle+\dfrac{\beta_{t+1}}{2}\|\bar{M}^{t+1}x-y_{t+1}\|^{2}+D_{\phi}(x,x_{t})$
$\displaystyle=h(x)-\langle
z_{t},\bar{M}^{t}x\rangle+\dfrac{\beta_{t}}{2}\|\bar{M}^{t+1}x-y_{t+1}\|^{2}+\dfrac{\gamma}{2}\|x-x_{t}\|^{2}-h(x)+h(x_{t})+\langle\nabla
h(x_{t}),x-x_{t}\rangle$ $\displaystyle=-\langle
z_{t},\bar{M}^{t}x\rangle+\dfrac{\beta_{t+1}}{2}\|\bar{M}^{t+1}x-y_{t+1}\|^{2}+\dfrac{\gamma}{2}\|x-x_{t}\|^{2}+h(x_{t})+\langle\nabla
h(x_{t}),x-x_{t}\rangle.$

Rearranging,

$\displaystyle g^{t+1}(x)$ $\displaystyle=\dfrac{1}{2}\left\langle
x,\left(\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}+\gamma
I\right)x\right\rangle$ $\displaystyle+\left\langle\nabla
h(x_{t})-\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}y_{t+1}-\left(\bar{M}^{t+1}\right)^{T}z_{t}-\gamma
x_{t},x\right\rangle$
$\displaystyle+\dfrac{\beta_{t+1}}{2}\|y_{t+1}\|^{2}+\dfrac{\gamma}{2}\|x_{t}\|^{2}+h(x_{t})-\left\langle\nabla
h(x_{t}),x_{t}\right\rangle.$

We denote $A,b,c$ by

$A=\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}+\gamma I,$ $b=\nabla
h(x_{t})-\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}y_{t+1}-\left(\bar{M}^{t+1}\right)^{T}z_{t}-\gamma
x_{t},$

and

$c=\dfrac{\beta_{t+1}}{2}\|y_{t+1}\|^{2}+\dfrac{\gamma}{2}\|x_{t}\|^{2}+h(x_{t})-\left\langle\nabla
h(x_{t}),x_{t}\right\rangle,$

to derive the required form of $g^{t+1}$ from (5.2). Note that $A$ is indeed
positive definite.

The first part follows from the fact that the

$\gamma I\preceq\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}+\gamma
I\preceq\left(\gamma+\beta_{t+1}\lambda_{max}\left(\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}\right)\right)I.$

The second part of the lemma follows directly from the fact that $g^{t+1}$ is
a strongly convex function, and therefore its critical point set is a
singleton.

The third of the proof follows from the closed form solution for minimization
of strongly convex quadratic functions,

$x^{*}=-A^{-1}b.$

$\Box$

The results of 5.1 provide two methods to calculate the $x$ updates. The first
is to use a gradient based algorithms, which converge exponentially fast to
the critical point, since $g^{t+1}$ is both strongly convex and smooth (see
Bubeck et al. [11, Theorem 3.10]). The second is to calculate the closed form
solution directly, at the cost of inverting
$\beta_{t+1}\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}+\gamma I$.

Algorithm 2 implements the meta algorthim (cf. Algorithm 1) for the case in
which $\nabla^{2}h(x)$ is bounded, and Algorithm 3 implements its
corresponding APO.

The APO utilized in Algorithm 2 is denoted by $\mathrm{APO}_{\mathrm{B}}$ to
mark that it is designated for functions with a bounded hessian.

Input: ${\bf x}_{0}\in\mathbb{R}^{n}$, ${\bf z}_{0}\in\mathbb{R}^{n}$,
$\beta_{0}>0,\\{\theta_{t}\\}_{t>0}$, $\epsilon>0$

1

2for  _$t=0,1,2,\ldots$_ do

3
$sample\;(\theta_{t+1}-\theta_{t})\;matrices\;\\{M^{i}\\}_{i=\theta_{t}+1}^{\theta_{t+1}}$;

4
$\bar{M}^{t+1}=\dfrac{\theta_{t}}{\theta_{t+1}}\bar{M}^{t}+\dfrac{1}{\theta_{t+1}}\sum\limits_{i=\theta_{t}+1}^{\theta_{t+1}}M^{i}\;$

5 $y_{t+1}\in\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{y}\\{P(y)+\langle{z_{t}},y\rangle+\dfrac{\beta_{t}}{2}\|{\bar{M}^{t+1}x_{t}-y}\|^{2}\\}$
;

6

7 $x_{t+1}\in\displaystyle\mathop{\mbox{\rm argmin}}\limits_{x}\\{-\langle
z_{t},\bar{M}^{t}x\rangle+\dfrac{\beta_{t}}{2}\|\bar{M}^{t+1}x-y_{t+1}\|^{2}+\dfrac{\gamma}{2}\|x-x_{t}\|^{2}+\langle\nabla
h(x_{t}),x-x_{t}\rangle\\}$;

8

9 $z_{t+1}=z_{t}-\beta_{t}(\bar{M}^{t+1}x_{t+1}-y_{t+1})$;

10

11
$\beta_{t+1}\leftarrow\mathrm{APO}_{\mathrm{B}}(\beta_{t},\bar{M}^{t+1},\gamma,\epsilon)$
;

12

13 end for

Algorithm 2 ISAD - Bounded Hessian

Input: $\beta\in\mathbb{R}$, $M\in\mathbb{R}^{n\times n}$, $\gamma>0$,
$\epsilon>0$.

1

2$\tilde{\sigma}=\lambda_{min}(M^{T}M)$ ;

3 if  _$\tilde{\sigma}==0$_ then

4 return $\beta$

5 if  _$\dfrac{(1+0.5\epsilon)\cdot 24\gamma}{\tilde{\sigma}\beta}
<\tilde{\sigma}\beta+\gamma<\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}\beta}$_ then

6 return $\beta$

7 else

8
$\beta=\dfrac{-\gamma+\sqrt{\gamma^{2}+(1+\epsilon)96\gamma}}{2\tilde{\sigma}}$
;

// Positive solution to $\tilde{\sigma}\beta+\gamma=\dfrac{(1+\epsilon)\cdot
24\gamma}{\tilde{\sigma}\beta}$

9 return $\beta$

10 end if

Algorithm 3 Bounded Hessian APO: $\mathrm{APO}_{\mathrm{B}}$

Next, we prove that Algorithm 3 satisfies the requirements outlined in 3.1,
and therefore, that Algorithm 2 implements the meta algorithm Algorithm 1.

######  Lemma 5.2.

Suppose that 5 holds true, and let $\\{x_{t},y_{t},z_{t}\\}_{t\geq 0}$ be the
sequence generated by Algorithm 2. Then,

$L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq 2\gamma\text{ and
}L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq\gamma,$

where $L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ and $L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ are the empirical Lipschitz constants of
$\nabla\phi$ and $\nabla h+\nabla\phi$ with respect to the sequence
$\\{x_{t}\\}_{t\geq 0}$.

###### Proof.

By the fact that

$0\preceq\nabla^{2}\phi(x)=\gamma I-\nabla^{2}h(x)\preceq 2\gamma I,$

The Lipschitzs constant of $\nabla\phi$, denoted by $L_{\nabla\phi}$,
satisfies that $L_{\nabla\phi}\leq 2\gamma$. Since

$h(x)+\phi(x)=\dfrac{\gamma}{2}\|x\|^{2},$

it follows that

$\nabla^{2}(h+\phi)(x)=\gamma I,$

and therefore

$L_{\nabla h+\nabla\phi}\leq\gamma.$

Thus, invoking 2.2, it follows that

$L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq 2\gamma\text{ and
}L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq\gamma.$

$\Box$

Using the previous lemma, we will prove that Algorithm 3 fulfills the APO
requirements outlined in 3.1.

######  Theorem 5.1.

Suppose that 5 holds. Then, Algorithm 3 fulfills the APO requirements outlined
in 3.1.

###### Proof.

Our goal is to show that there exists an index $K_{stable}$ such that

  1. 1.

For all $k>K_{stable}$, $\beta_{k}=\beta_{K_{stable}}$;

  2. 2.

Let $\\{x_{t}\\}_{t\geq 0}$ be the sequence generated by Algorithm 3. There
exists $\rho>0$ such that for all $k>K_{stable}$

$g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\leq-\dfrac{\rho}{2}\|x_{t+1}-x_{t}\|^{2},$

and

$\rho>\dfrac{8}{\beta_{k}\sigma}\left(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\right).$

For the duration of this proof, we extend the notation in Algorithm 3 in the
following manner: at the end of iteration $k$, $\tilde{\sigma}_{k}$ and
$\beta_{k}$ are the values of $\tilde{\sigma}$ and $\beta$ respectively; Note
that $\tilde{\sigma}_{k}=\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})$, and
that by 2,

$\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])=\sigma>0.$

By 4.3, there exists with probability 1 an index $J>0$, such that for all
$k>J$, with parameter value of 0.5, it holds that

$0<0.5\sigma<\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})=\tilde{\sigma}_{k}.$

Without loss of generality, we shall assume throughout the rest of the proof
that $J=0$, and therefore that the condition $\tilde{\sigma}_{k}==0$ is always
false.

From 4.3 we have that for every $0<\epsilon^{\prime}<1$, there exists almost
surely $K_{1}>0$, such that for all $k>K_{1}$:

$\displaystyle(1-\epsilon^{\prime})\tilde{\sigma_{k}}$
$\displaystyle\leq\sigma\leq(1+\epsilon^{\prime})\tilde{\sigma_{k}}$

and

$\displaystyle(1-\epsilon^{\prime})\sigma$
$\displaystyle\leq\tilde{\sigma}_{k}\leq(1+\epsilon^{\prime})\sigma.$

Assume in contradiction that the number of updates of $\beta$ is infinite,
which translates, due to the update mechanism of Algorithm 3, to the
assumption that there is an infinite number of iterations is which either
$\tilde{\sigma}\beta+\gamma\leq\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}\beta}$ or
$\tilde{\sigma}\beta+\gamma\geq\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}\beta}$.

Let $\\{t_{i}\\}_{i\geq 0}\subseteq\\{k\\}_{k>K_{1}}$ be a sequence of indices
at which $\beta$ is updated after the $K_{1}$ iteration. By the update rule of
$\beta$,

$\tilde{\sigma}_{t_{i}}\beta_{t_{i}}+\gamma=\dfrac{(1+\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}}},\qquad\forall i\geq 0.$

Consider the $t_{i}+j$ iteration where $i\geq 0$, and $j\geq 1$ satisfies that

$\beta_{t_{i}+j-1}=\beta_{t_{i}};$ (5.3)

note that $j$ is well-defined since the condition
$\beta_{t_{i}+j-1}=\beta_{t_{i}}$ holds as a tautology for $j=1$.

For this $j$, by (5.3) and the fact that $\beta$ is updated at the $t_{i}$
iteration, $\beta_{t_{i}+j-1}$ satisfies that

$\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma=\dfrac{(1+\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}.$ (5.4)

Since $t_{i}>K_{1}$,

$(1-\epsilon^{\prime})\sigma<\tilde{\sigma}_{t_{i}}<(1+\epsilon^{\prime})\sigma,$
$(1-\epsilon^{\prime})\sigma<\tilde{\sigma}_{t_{i}+j}<(1+\epsilon^{\prime})\sigma.$

Therefore, it follows that

$\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}<\dfrac{\tilde{\sigma}_{t_{i}}}{\tilde{\sigma}_{t_{i}+j}}<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}$

and

$\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}<\dfrac{\tilde{\sigma}_{t_{i}+j}}{\tilde{\sigma}_{t_{i}}}<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}.$

Subsequently, rewriting the leftmost side of the condition

$\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}\beta}<\tilde{\sigma}\beta+\gamma<\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}\beta}$

yields

$\displaystyle\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}}$
$\displaystyle=\dfrac{\tilde{\sigma}_{t_{i}}}{\tilde{\sigma}_{t_{i}+j}}\cdot\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}$ (5.5)
$\displaystyle<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}$
$\displaystyle=\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot\dfrac{1+0.5\epsilon}{1+\epsilon}\cdot\dfrac{(1+\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}$
$\displaystyle=\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot\dfrac{1+0.5\epsilon}{1+\epsilon}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma).$

Additionally, by developing the expression
$\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}+\gamma$, we obtain that

$\displaystyle\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle=\dfrac{\tilde{\sigma}_{t_{i}+j}}{\tilde{\sigma}_{t_{i}}}\cdot\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle>\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle>\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma)$

and

$\displaystyle\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle=\dfrac{\tilde{\sigma}_{t_{i}+j}}{\tilde{\sigma}_{t_{i}}}\cdot\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma).$

Therefore,

$\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma)<\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}+\gamma<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma).$
(5.6)

Rewriting the expression $\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}}$ in a similar manner, we
have that

$\displaystyle\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}}$
$\displaystyle=\dfrac{\tilde{\sigma}_{t_{i}}}{\tilde{\sigma}_{t_{i}+j}}\cdot\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}$ (5.7)
$\displaystyle>\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}$
$\displaystyle=\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot\dfrac{1+2\epsilon}{1+\epsilon}\cdot\dfrac{(1+\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}}$
$\displaystyle=\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot\dfrac{1+2\epsilon}{1+\epsilon}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma).$

Now, for a sufficiently small $\epsilon^{\prime}$ the following relations hold
true:

  1. 1.

$1<\dfrac{1+0.5\epsilon}{(1+\epsilon^{\prime})^{2}}<\dfrac{1+0.5\epsilon}{1+\epsilon^{\prime}}$,

  2. 2.

$\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}(1+0.5\epsilon)<\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}(1+\epsilon)$,

  3. 3.

$\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}(1+\epsilon)<\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}(1+2\epsilon)$.

Combining (5.5), (5.6), (5.7), and using the above relations, we obtain that

$\displaystyle\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}}$
$\displaystyle<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot\dfrac{1+0.5\epsilon}{1+\epsilon}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma)$
$\displaystyle<\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma)$
$\displaystyle<\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}+\gamma$
$\displaystyle<\dfrac{1+\epsilon^{\prime}}{1-\epsilon^{\prime}}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma)$
$\displaystyle<\dfrac{1-\epsilon^{\prime}}{1+\epsilon^{\prime}}\cdot\dfrac{1+2\epsilon}{1+\epsilon}\cdot(\tilde{\sigma}_{t_{i}}\beta_{t_{i}+j-1}+\gamma)$
$\displaystyle<\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}},$

which boils down to

$\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}}<\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}+\gamma<\dfrac{(1+2\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{t_{i}+j}\beta_{t_{i}+j-1}}.$ (5.8)

Hence, by the update criteria of $\beta$, the penalty $\beta$ does not update
at the $t_{i}+j$ iteration. In particular for $i=0$, since $j=1$ satisfies
(5.3), we can deduce by induction that for all $j\geq 1$ there is no $\beta$
update in the $t_{0}+j$ iteration. Therefore, $\beta$ does not update after
the $t_{0}>K_{1}$ iteration thus contradicting the assumption that $\beta$ is
updated infinitely many times and proving the first part of the lemma.

Denote the index of the last $\beta$ update, whose existence is established in
the first part, by $K_{2}$. To prove the second part, first recall that by 5.2
it holds that

$L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq
0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq 3\gamma,$

and that $g^{t+1}$ is strongly convex, where we denote its strong convexity
constant by $\rho_{t+1}$. By the strong convexity inequality for $g^{t+1}(x)$,

$g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\leq\nabla
g^{t+1}(x_{t+1})^{T}(x_{t+1}-x_{t})-\dfrac{\rho_{t+1}}{2}\|x_{t+1}-x_{t}\|^{2}.$

Since $x_{t+1}$ minimizes $g^{t+1}(x)$, $\nabla g^{t+1}(x_{t+1})=0$, and hence

$g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\leq-\dfrac{\rho_{t+1}}{2}\|x_{t+1}-x_{t}\|^{2}.$

Considering the above, it is sufficient to show that for
$K_{stable}=\max\\{K_{1},K_{2}\\}$,

$\rho_{k}>\dfrac{24\gamma}{\sigma\beta_{k}}\qquad\forall k>K_{stable}.$

By the definition of $g^{k}$, we have that

$\nabla^{2}g^{k}(x)=\beta_{k}(\bar{M}^{k})^{T}\bar{M}^{k}+\gamma I,$

and therefore, $g^{k}$ is
$\beta_{k}\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})+\gamma=\beta_{k}\tilde{\sigma}_{k}+\gamma$
strongly convex.

Since $K_{stable}\geq K_{1}$, for all $k>K_{stable}$ we have that

$\displaystyle(1-\epsilon^{\prime})\tilde{\sigma_{k}}$
$\displaystyle\leq\sigma\leq(1+\epsilon^{\prime})\tilde{\sigma_{k}}$

and

$\displaystyle(1-\epsilon^{\prime})\sigma$
$\displaystyle\leq\tilde{\sigma}_{k}\leq(1+\epsilon^{\prime})\sigma.$

Furthermore, let us choose again an $\epsilon^{\prime}>0$ sufficiently small
such that

$1<\dfrac{1+0.5\epsilon}{1+\epsilon^{\prime}}.$

For all $k>K_{stable}$,

$\displaystyle\dfrac{8}{\beta_{k}\sigma}\left(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\right)$ $\displaystyle\leq\dfrac{24\gamma}{\sigma\beta_{k}}$
$\displaystyle<\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{(1+\epsilon^{\prime})\sigma\beta_{k}}$
$\displaystyle<\dfrac{(1+0.5\epsilon)\cdot
24\gamma}{\tilde{\sigma}_{k}\beta_{k}}$
$\displaystyle<\tilde{\sigma}_{k}\beta_{k}+\gamma,$

where the first inequality follows from $L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\leq 3\gamma$, the second from
$1<\dfrac{1+0.5\epsilon}{1+\epsilon^{\prime}}$, the third from
$\tilde{\sigma}_{k}\leq(1+\epsilon^{\prime})\sigma$, and the fourth since the
inequality in line 4 of Algorithm 3 holds for all $k>K_{stable}\geq K_{2}$.
Since $\tilde{\sigma}_{k}\beta_{k}+\gamma$ is the strong convexity constant of
$g^{k}$, this concludes the proof. $\Box$

##  6 Algorithm Implementation For the General Case

Section 5 provides an explicit algorithmic infrastructure in which the meta-
algorithm sub-procedure’s requirements are satisfied, under the standard
assumption that the hessian of the function $h$ is bounded. In this section,
we introduce a more universal implementation of the meta-algorithm, described
in Algorithm 4, and its sub-procedures, that do not require the boundedness of
the hessian. This generality comes at the price of the technical complexity of
the schematics of the adaptive penalty oracle given in Algorithm 5, and the
subsequent related analysis.

Input: ${\bf x}_{0}\in\mathbb{R}^{n}$, ${\bf z}_{0}\in\mathbb{R}^{n}$,
$\beta_{0}>0,\\{\theta_{t}\\}_{t>0}$, $\epsilon>0$,
$\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ where $\phi\in C^{2}$ and convex.

1

2Set $\zeta_{0},\xi_{0}\leftarrow 0$;

3

4for  _$t=0,1,2,\ldots$_ do

5
$sample\;(\theta_{t+1}-\theta_{t})\;matrices\;\\{M^{i}\\}_{i=\theta_{t}+1}^{\theta_{t+1}}$;

6
$\bar{M}^{t+1}=\dfrac{\theta_{t}}{\theta_{t+1}}\bar{M}^{t}+\dfrac{1}{\theta_{t+1}}\sum\limits_{i=\theta_{t}+1}^{\theta_{t+1}}M^{i}\;$

7 $y_{t+1}\in\displaystyle\mathop{\mbox{\rm
argmin}}\limits_{y}\\{P(y)+\langle{z_{t}},y\rangle+\dfrac{\beta_{t}}{2}\|{\bar{M}^{t+1}x_{t}-y}\|^{2}\\}$
;

8

9
$x_{t+1}\in\operatorname{Crit}\limits_{x}\\{h(x)-\langle{z_{t}},\bar{M^{t}}x\rangle+\dfrac{\beta_{t}}{2}\|{\bar{M}^{t+1}x-y_{t+1}}\|^{2}+D_{\phi}(x,x_{t})\\}$;

10

11 $z_{t+1}=z_{t}-\beta_{t}(\bar{M}^{t+1}x_{t+1}-y_{t+1})$

12 $\beta_{t+1},\zeta_{t+1},\xi_{t+1}\leftarrow
General\;APO(x_{t+1},x_{t},\beta_{t},\zeta_{t},\xi_{t},,\epsilon,\bar{M}^{t+1},\phi,h)$

13 end for

Algorithm 4 ISAD - General Case

Input: ${\bf x}_{t+1}\in\mathbb{R}^{n}$, ${\bf x}_{t}\in\mathbb{R}^{n}$,
$\beta>0,\zeta_{t},\xi_{t}$, $\epsilon>0$ $\bar{M}^{t+1}$, $\phi$, $h$, where
$\bar{M}^{t+1}$, $\phi$ and $h$ satisfy our previous assumptions (and are
termed accordingly).

1

2if  _$x_{t+1}==x_{t}$_ then

3 $\zeta_{t+1}=\zeta_{t}$;

4 $\xi_{t+1}=\xi_{t}$

5 else

6 $\zeta_{t+1}=\max\\{\zeta_{t},\dfrac{\|\nabla
h(x_{t+1})+\nabla\phi(x_{t+1})-\nabla
h(x_{t})-\nabla\phi(x_{t})\|^{2}}{\|x_{t+1}-x_{t}\|^{2}}\\}$

7
$\xi_{t+1}=\max\\{\xi_{t},\dfrac{\|\nabla\phi(x_{t+1})-\nabla\phi(x_{t})\|^{2}}{\|x_{t+1}-x_{t}\|^{2}}\\}$

8 end if

9

10Set $\tilde{\sigma}=\lambda_{min}((\bar{M}^{t+1})^{T}\bar{M}^{t+1})$;

11

12if  _$\tilde{\sigma}==0$_ then

13 return $\beta,\zeta_{t+1},\xi_{t+1}$

14

15Set
$\rho_{t}=-\dfrac{2\left(g(x_{t+1})-g(x_{t})\right)}{\|x_{t+1}-x_{t}\|^{2}}$;

16

17if  _$\dfrac{1}{4}\rho_{t}
>\dfrac{8(\zeta_{t+1}+\xi_{t+1}+\epsilon)}{\beta\tilde{\sigma}}$_ then

18 return $\beta,\zeta_{t+1},\xi_{t+1}$

19 else

20 return $2\beta,\zeta_{t+1},\xi_{t+1}$

21 end if

22

Algorithm 5 General APO

######  Remark 6.1 (a technical note on the $\beta$ update).

Note that $\beta$ is updated at $t\geq 0$ only if

$\tilde{\sigma}\neq 0\text{ and
}\dfrac{1}{4}\rho_{t}\leq\dfrac{8(\zeta_{t+1}+\xi_{t+1}+\epsilon)}{\beta\tilde{\sigma}},$

and that if $\beta$ was updated $\kappa$ times, then
$\beta=2^{\kappa}\beta_{0}$ where $\beta_{0}$ is the initial value of $\beta$.

In Theorem 6.1 we establish that Algorithm 4, and its adaptive penalty oracle
procedure Algorithm 5, satisfy the requirements outlined in 3.1. The proof
builds on the boundedness of the generated sequence (cf. 3) to guarantee that
all the continuous elements, mainly the derivatives of $h$ and $\phi$, are
bounded as-well, which implies that the corresponding empirical Lipschitz
constants are bounded. From this point, the analysis takes a similar turn,
with the necessary adjustments, to that taken in the proof of Theorem 5.1 in
the previous section – showing that $\beta$ is updated finitely many times. We
move onward to formally state and prove Theorem 6.1.

######  Theorem 6.1.

Let $\\{x_{t},y_{t},z_{t}\\}_{t\geq 0}$ be the sequence generated by Algorithm
4, and let $\\{\beta_{t}\\}_{t\geq 0}$ be the sequence of adaptive penalties
generated. Then $\\{x_{t},y_{t},z_{t},\beta_{t}\\}_{t\geq 0}$ fulfill 3.1.

###### Proof.

Our goal is to show that there exists an index $K_{stable}>0$ such that

  1. 1.

For all $k>K_{stable}$, $\beta_{k}=\beta_{K_{stable}}$.

  2. 2.

Let $\\{x_{t}\\}_{t\geq 0}$ be the sequence generated by Algorithm 1. There
exists $\rho>0$ such that for all $k>K_{stable}$

$g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\leq-\dfrac{\rho}{2}\|x_{t+1}-x_{t}\|^{2},$

and

$\rho>\dfrac{8}{\beta_{k}\sigma}\left(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\right).$

As a starting point, first recall that 2 states that

$\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])=\sigma>0,$

by 3, there exists $D>0$, such that $\max\limits_{t\geq
1}\\{\max\\{\|x_{t}\|,\|y_{t}\|,\|z_{t}\|\\}\\}\leq D$, and that, by 4.3,
there exists with probability 1 an index $J>0$ such that,

$0<0.5\sigma<\tilde{\sigma}=\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k}),\qquad\forall
k>J.$

Without loss of generality, we shall assume throughout the rest of the proof
that $J=0$, and therefore, that the condition $\tilde{\sigma}_{k}==0$
appearing in Algorithm 5 is always false.

To show that that the number of $\beta$ updates is finite, it is sufficient to
show that the condition

$\dfrac{1}{4}\rho_{t}>\dfrac{8(\zeta_{t+1}+\xi_{t+1}+\epsilon)}{\beta_{t}\tilde{\sigma}_{t}}$

is violated at most a finite number of times.

We prove that $\lambda_{min}\left(\nabla^{2}h(x)+\nabla^{2}\phi(x)\right)$ is
lower bounded over $\mathcal{B}[0,D]$, a fact that will be used in the proof
shortly. Note that both $h$ and $\phi$ are twice continuously differentiable,
and therefore their hessians $\nabla^{2}h(x)$ and $\nabla^{2}\phi(x)$ are
continuous. It follows that the functions $\lambda_{min}(\nabla^{2}h(x))$,
$\lambda_{max}(\nabla^{2}h(x))$, $\lambda_{min}(\nabla^{2}\phi(x))$,
$\lambda_{max}(\nabla^{2}\phi(x))$ are all continuous in the ball
$\mathcal{B}[0,D]$ (see Kato [19, Theorem 6.8]). Since the ball
$\mathcal{B}[0,D]$ is compact, by using Weierstrass’ Extreme Value Theorem,
the following maximum and minimum values exist

$\lambda^{h+\phi}_{min}=\min\limits_{x\in
B(0,D)}\lambda_{min}(\nabla^{2}\phi(x)+\nabla^{2}h(x))\text{ and
}\lambda^{h+\phi}_{max}=\max\limits_{x\in
B(0,D)}\lambda_{max}(\nabla^{2}\phi(x)+\nabla^{2}h(x)),$
$\lambda^{\phi}_{min}=\min\limits_{x\in
B(0,D)}\lambda_{min}(\nabla^{2}\phi(x))\text{ and
}\lambda^{\phi}_{max}=\max\limits_{x\in
B(0,D)}\lambda_{max}(\nabla^{2}\phi(x)).$

To continue the proof, we define two expressions that are utilized in the
analysis. The first is the minimal eigenvalue of the hessian of $g$ at
iteration $t>0$ within $\mathcal{B}[0,D]$,

$\alpha_{t}=\min\limits_{x\in\mathcal{B}[0,D]}\lambda_{min}\left(\nabla^{2}g^{t}(x)\right),\qquad\forall
t>0.$

The second partially acts as a counter for the number of times $\beta$ was
updated starting from some iteration $k>J$,

$\kappa_{\beta_{k}}=\begin{cases}0,&\beta_{k}\geq\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\sigma},\\\
\left\lceil\log_{2}\left(\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\beta_{k}\sigma}\right)\right\rceil,&\text{otherwise}.\end{cases}$

Obviously, for any $\beta_{k}$ there are two complementing possibilities:
either $\beta$ is updated less than $\kappa_{\beta_{k}}$ times after the $k$
iteration, or it is updated at least $\kappa_{\beta_{k}}$ times after
iteration $k$. In this context, we make the following a-priori assumption, to
be proven later. There exists $C>0$ such that:

  1. 1.

It holds that

$\dfrac{8(\zeta_{t+1}+\xi_{t+1}+\epsilon)}{\beta_{t}\tilde{\sigma}_{t}}<C,\qquad\forall
t>J.$ (6.1)

  2. 2.

If $\beta$ is updated at least $\kappa_{\beta_{k}}$ times after iteration $k$,
in which case let $\tau_{\kappa,\beta_{k}}$ be the iteration of the
$\kappa_{\beta_{k}}$ update after $k$, then for all
$t\geq\tau_{\kappa,\beta_{k}}$

$\alpha_{t}>4C.$ (6.2)

We will show that the number of $\beta$ updates is finite assuming (6.1) and
(6.2), and then show that these assumptions indeed hold true.

If $\beta$ is updated less than $\kappa_{\beta_{k}}$ many times after
iteration $k$, the first part of 3.1 trivially holds true. Otherwise, by
(6.2), there exists $\tau_{\kappa,\beta_{k}}\geq 0$, such that for all
$t>\tau_{\kappa,\beta_{k}}$ and $x\in\mathcal{B}[0,D]$, $\nabla^{2}g^{t}(x)$
is a positive definite matrix, meaning that $g^{t}(x)$ is
$\alpha_{t}$-strongly convex within $\mathcal{B}[0,D]$. Since
$x_{t},x_{t+1}\in\mathcal{B}[0,D]$ for all $t$, by the strong convexity
inequality

$g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\leq\nabla
g^{t+1}(x_{t+1})^{T}\left(x_{t+1}-x_{t}\right)-\dfrac{\alpha_{t+1}}{2}\|x_{t+1}-x_{t}\|^{2}\qquad\forall
t>\tau_{\kappa,\beta_{k}}.$

From the update rule of $x_{t+1}$, which defined as the minimizer of
$g^{t+1}(x)$, we have that $\nabla g^{t+1}(x_{t+1})=0$, and hence,

$g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\leq-\dfrac{\alpha_{t+1}}{2}\|x_{t+1}-x_{t}\|^{2}\qquad\forall
t>\tau_{\kappa,\beta_{k}}.$

By the update of $\rho_{t+1}$ in line 11 of Algorithm 5,

$\rho_{t+1}=-\dfrac{2\left(g^{t+1}(x_{t+1})-g^{t+1}(x_{t})\right)}{\|x_{t+1}-x_{t}\|^{2}}\geq\alpha_{t+1}.$

Thus, if $\alpha_{t}>4C$ for all $t\geq\tau$, then $\rho_{t}>4C$, and the
condition

$\dfrac{1}{4}\rho_{t}>\dfrac{8(\zeta_{t+1}+\xi_{t+1}+\epsilon)}{\beta_{t}\tilde{\sigma}_{t}}$

is no longer violated. Therefore, the first part of the requirements in 3.1 is
fulfilled. That is, under the a-priori assumption above, we established the
stability of $\beta$ meaning that it is updated finitely many times.

We now move to prove that the a-priori assumptions indeed hold true, starting
with (6.2), assuming that the first a-priori assumption (6.1) holds true.

First, we bound $\lambda_{min}\left(\nabla^{2}g^{t+1}(x)\right)$ by the
minimal eigenvalues of its components,

$\lambda_{min}\left(\nabla^{2}g^{t+1}(x)\right)\geq\lambda_{min}\left(\nabla^{2}h(x)+\nabla^{2}\phi(x)\right)+\beta_{t}\lambda_{min}\left(\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}\right),$
(6.3)

where we used the fact that the hessian of $g^{t+1}$ is given by

$\nabla^{2}g^{t+1}(x)=\nabla^{2}h(x)+\nabla^{2}\phi(x)+\beta_{t}\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}.$

For $\lambda_{min}\left(\nabla^{2}h(x)+\nabla^{2}\phi(x)\right)$ in (6.3) we
already have the lower bound $\lambda^{h+\phi}_{min}$.

To lower bound
$\lambda_{min}\left(\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}\right)$, we
use 4.3, which states that for every $0<\epsilon^{\prime}<1$ there exists
almost surely $K>0$ such that for all $k>K$

$(1-\epsilon^{\prime})\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])=(1-\epsilon^{\prime})\sigma\leq\tilde{\sigma}_{k}\leq(1+\epsilon^{\prime})\sigma=(1+\epsilon^{\prime})\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M]).$

We arbitrarily choose $\epsilon^{\prime}=0.25$, and derive that

$\lambda_{min}\left(\left(\bar{M}^{t+1}\right)^{T}\bar{M}^{t+1}\right)>0.75\sigma\qquad\forall
t>K.$

Combining the two lower bounds, for all $t>K$,

$\lambda_{min}\left(\nabla^{2}g^{t+1}(x)\right)\geq\lambda^{h+\phi}_{min}+0.75\sigma\beta_{t}.$

Consequently, if

$\beta_{t}\geq\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\sigma},$

then $\alpha_{t+1}\geq 5C>4C$, and (6.2) holds true with
$\kappa_{\beta_{t}}=0$; note that the choice of the scalar $5$ is arbitrary,
any scalar strictly greater than $4$ would suffice.

Otherwise, $\beta_{t}<\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\sigma}$ and

$\kappa_{\beta_{t}}=\left\lceil\log_{2}\left(\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\beta_{t}\sigma}\right)\right\rceil.$

If $\beta$ is updated at least $\kappa_{\beta_{t}}$ times after iteration $t$
(otherwise $\beta$ is updated a finite number of times), let
$\tau_{\kappa,\beta_{t}}$ be the iteration of the $\kappa_{\beta_{t}}$ update
of $\beta$ starting from iteration $t$. By the choices of $\kappa_{\beta_{t}}$
and $\tau_{\kappa,\beta_{t}}$ and the update rule for $\beta$ (see Remark
6.1),

$\beta_{\tau_{\kappa,\beta_{t}}}=2^{\kappa_{\beta_{t}}}\beta_{t},$

and therefore

$\displaystyle\log_{2}\left(\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\beta_{\tau_{\kappa,\beta_{t}}}\sigma}\right)$
$\displaystyle=\log_{2}\left(\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\cdot
2^{\kappa_{\beta_{t}}}\beta_{t}\sigma}\right)$
$\displaystyle=\log_{2}\left(\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\beta_{t}\sigma}\right)-\log_{2}\left(2^{\kappa_{\beta_{t}}}\right)$
$\displaystyle=\log_{2}\left(\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\beta_{t}\sigma}\right)-\kappa_{\beta_{t}}$
$\displaystyle\leq 0,$

where the last inequality follows from the definition of $\kappa_{\beta_{t}}$.
Hence, it follows that

$\beta_{\tau_{\kappa,\beta_{t}}}\geq\dfrac{5C-\lambda^{h+\phi}_{min}}{0.75\sigma},$

and for all $k>\tau_{\kappa,\beta_{t}}$, and all $x\in\mathcal{B}[0,D]$,

$\lambda_{min}\left(\nabla^{2}g^{k}(x)\right)\geq\lambda^{h+\phi}_{min}+0.75\sigma\beta_{k}\geq
5C>4C.$

Thus, assuming (6.1),

$\alpha_{k}>4C\qquad\forall k>\tau_{\kappa,\beta_{t}},$

proving that (6.2) holds true.

All that remains is to prove that (6.1) holds true, that is, that there exits
$C>0$ such that

$\dfrac{8(\zeta_{t+1}+\xi_{t+1}+\epsilon)}{\beta_{t}\tilde{\sigma}_{t}}<C.$

To lower bound $\beta_{t}$, note that the sequence $\\{\beta_{t}\\}_{t\geq 0}$
is nondecreasing. Therefore,

$\beta_{t}\geq\beta_{0}.$ (6.4)

By the choice of $J$, the lower bound for $\tilde{\sigma}_{k}$ follows from

$\tilde{\sigma}_{k}>0.5\sigma\qquad\forall k>J.$ (6.5)

By the update rule of $\zeta$, $\xi$ and the definition of the empirical
lipschitz constant (2.2), $L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq
0})=\displaystyle\mathop{\mbox{\rm sup}}\limits_{t\geq 0}\zeta_{t}$ and
$L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})=\displaystyle\mathop{\mbox{\rm
sup}}\limits_{t\geq 0}\xi_{t}$. Therefore, for all $t$,

$\zeta_{t}\leq L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ (6.6)

and

$\xi_{t}\leq L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0}).$ (6.7)

Using (6.6) and (6.7), it is sufficient to bound $L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ and
$L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$.

The Lipschitz constants of the restrictions of $\nabla h+\nabla\phi$ and
$\nabla\phi$ to the ball $\mathcal{B}[0,D]$ are bounded by
$L^{D}_{\nabla\phi}=\max\\{|\lambda^{\phi}_{min}|,|\lambda^{h+\phi}_{max}|\\}$
and $L^{D}_{\nabla\phi+\nabla
h}=\max\\{|\lambda^{h+\phi}_{min}|,|\lambda^{h+\phi}_{max}|\\}$, respectively.

If there is no $t$ such that $x_{t}\neq x_{t+1}$, then $L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})=L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})=0$, and therefore $L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq
L^{D}_{\nabla\phi+\nabla h}$ and $L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\leq L^{D}_{\nabla\phi}$.

Otherwise, since $x_{t}\in\mathcal{B}(0,D)$ for every $t\geq 0$,

$\displaystyle L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$
$\displaystyle=\displaystyle\mathop{\mbox{\rm sup}}\limits_{t\geq
0,x_{t+1}\neq x_{t}}\dfrac{\|\nabla h(x_{t+1})+\nabla\phi(x_{t+1})-\nabla
h(x_{t})-\nabla\phi(x_{t})\|}{\|x_{t+1}-x_{t}\|}$
$\displaystyle\leq\displaystyle\mathop{\mbox{\rm
sup}}_{x,y\in\mathcal{B}(0,D),x\neq y}\dfrac{\|\nabla
h(x)+\nabla\phi(x)-\nabla h(y)-\nabla\phi(y)\|}{\|x-y\|}$
$\displaystyle=L^{D}_{\nabla\phi+\nabla h}$
$\displaystyle\leq\max\\{|\lambda^{h+\phi}_{min}|,|\lambda^{h+\phi}_{max}|\\}$
$\displaystyle<\infty,$

and in a similar manner, $L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\leq\max\\{|\lambda^{\phi}_{min}|,|\lambda^{\phi}_{max}|\\}<\infty$. We
deduce that whether there exists $t$ such that $x_{t+1}\neq x_{t}$ or not,

$\zeta_{t}\leq L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq
L^{D}_{\nabla\phi+\nabla h}<\infty$

and

$\xi_{t}\leq L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\leq
L^{D}_{\nabla\phi}<\infty.$

Combining the above with (6.4) and (6.5), it follows that (6.1) holds true
with

$C=\dfrac{8\left(L^{D}_{\nabla\phi+\nabla
h}+L^{D}_{\nabla\phi}+\epsilon\right)}{0.5\sigma\beta_{0}}.$ (6.8)

To summarize the first part of the proof, we have shown that the first
a-priori assumption holds true with $C$ given in (6.8), which implies that the
second a-priori assumption holds true with the same $C$, and subsequently,
that the number of $\beta$ updates is finite, concluding that the first part
of 3.1 holds true.

Now we establish the second part of 3.1, stating the iterates of
$\\{x_{k}\\}_{k\geq K}$ satisfy a sufficient decrease property from some
iteration $K>0$ onward.

Denote the index of the last $\beta$ update by $\tilde{K}$ whose existence is
guaranteed by the first part of 3.1 we just proved. To underscore the fact
that $\beta$ is no longer updated, we denote $\bar{\beta}=\beta_{\tilde{K}}$,
and replace $\beta_{k}$ with $\bar{\beta}$ in the remainder of the proof.

Since the if statement in line 12 of Algorithm 5 holds true for all
$k>\tilde{K}$, we can rearrange it into the following statement that holds for
all $k>\tilde{K}$,

$\dfrac{1}{4}\cdot\rho_{k}\cdot\bar{\beta}\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})>8(\zeta_{k+1}+\xi_{t+1}+\epsilon).$
(6.9)

As before, let $K>0$ such that almost surely for all $k>K$:

$(1-\epsilon^{\prime})\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M])=(1-\epsilon^{\prime})\sigma\leq\tilde{\sigma}_{k}\leq(1+\epsilon^{\prime})\sigma=(1+\epsilon^{\prime})\lambda_{min}(\mathbb{E}[M]^{T}\mathbb{E}[M]).$

Choosing $\epsilon^{\prime}=0.25$ (the choice $0.25$ is arbitrary, any scalar
in $(0,1)$ would do), yields that

$\lambda_{min}((\bar{M}^{k})^{T}\bar{M}^{k})<1.25\sigma$

holds almost surely. Thus, combining the latter with (6.9), we derive that

$\dfrac{5}{16}\cdot\rho_{k}>\dfrac{8(\zeta_{k+1}+\xi_{t+1}+\epsilon)}{\bar{\beta}\sigma}$

holds almost surely for all $k>\max\\{K,\tilde{K}\\}$. Rearranging the terms,
it follows that

$\dfrac{5}{16}\cdot\rho_{k}-\dfrac{8(\zeta_{k+1}+\xi_{t+1}+\epsilon)}{\bar{\beta}\sigma}>0.$
(6.10)

Since (6.10) holds true for all $k>\max\\{K,\tilde{K}\\}$, by taking $\liminf$
we obtain that

$\liminf\dfrac{5}{16}\cdot\rho_{k}-\dfrac{8(\zeta_{k+1}+\xi_{t+1}+\epsilon)}{\bar{\beta}\sigma}\geq
0.$

By the update rule of $\zeta$ and $\xi$, and the definition of empirical
Lipschitz constant, the limits

$\lim\limits_{k\to\infty}\zeta_{k}=L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})\text{ and
}\lim\limits_{k\to\infty}\xi_{k}=L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$

exist (recall that the sequence is bounded).

Utilizing the facts that $\lim\limits_{k\to\infty}\zeta_{k}=L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ and
$\lim\limits_{k\to\infty}\xi_{k}=L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$,
we then deduce the relation

$\liminf\dfrac{5}{16}\cdot\rho_{k}\geq\dfrac{8(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})+\epsilon)}{\bar{\beta}\sigma}.$ (6.11)

Decreasing the right hand side by $\dfrac{\epsilon}{\bar{\beta}\sigma}>0$ and
multiplying the left hand side by $\dfrac{16}{5}$, results in

$\liminf\limits_{k\to\infty}\rho_{k}>\dfrac{8(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0}))}{\bar{\beta}\sigma}.$ (6.12)

Denote $\rho_{inf}=\liminf\limits_{k\to\infty}\rho_{k}.$ By the definition of
the limit, for every $\epsilon^{\prime\prime}>0$, there exists $\bar{K}>0$,
such that for all $k>\bar{K}$, it holds that
$\rho_{k}>(1-\epsilon^{\prime\prime})\rho_{inf}.$ Additionally, due to the
strict inequality in (6.12), for a sufficiently small
$\epsilon^{\prime\prime}>0$, it holds that

$(1-\epsilon^{\prime\prime})\rho_{inf}>\dfrac{8(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0}))}{\bar{\beta}\sigma}.$

Choosing such $\epsilon^{\prime\prime}$, for every
$k>K_{stable}=\max\\{K,\tilde{K},\bar{K}\\}$, it holds almost surely that

$\rho_{k}>(1-\epsilon^{\prime\prime})\rho_{inf}>\dfrac{8}{\bar{\beta}\sigma}\left(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\right).$

Hence, the second part of the theorem holds for
$\rho=(1-\epsilon^{\prime\prime})\rho_{inf},$ which concludes the proof of the
theorem.

$\Box$

##  7 Meta Algorithm Convergence

In this section, we prove the convergence of the meta algorithm Algorithm 1.
The proof is split into two milestones. In Theorem 7.1, we prove that if the
size of the algorithm steps converges to zero, then every accumulation point
of the algorithm is a critical point. In Theorem 7.2 we prove that the size of
the algorithm steps does indeed converge to zero.

Before proving Theorem 7.1, another lemma will be needed:

######  Lemma 7.1.

Let $\\{x_{t},y_{t},z_{t}\\}_{t>0}$ be the sequence generated by Algorithm 1.
Then for any $t\geq 0$,

  1. 1.

$0\in\partial P(y_{t+1})+z_{t+1}+\beta_{t}\bar{M}^{t+1}(x_{t+1}-x_{t})$

  2. 2.

$\nabla
h(x_{t+1})-(\bar{M}^{t+1})^{T}z_{t+1}=-\nabla\phi(x_{t+1})+\nabla\phi(x_{t})$

  3. 3.

$\bar{M}^{t+1}x_{t+1}-y_{t+1}=\dfrac{1}{\beta_{t}}(z_{t}-z_{t+1})$

###### Proof.

First, we note the following two equations, which follow directly from the
criticality conditions for the update steps for $y_{t+1}$ and $x_{t+1}$:

$0\in\partial P(y_{t+1})+z_{t}-\beta_{t}(\bar{M}^{t+1}x_{t}-y_{t+1})$ (7.1)

and:

$0=\nabla
h(x_{t+1})-(\bar{M}^{t+1})^{T}z_{t}+\beta_{t}(\bar{M}^{t+1})^{T}(\bar{M}^{t+1}x_{t+1}-y_{t+1})+\nabla\phi(x_{t+1})-\nabla\phi(x_{t}).$
(7.2)

The first part follows from applying the update rule of $z_{t+1}$ to (7.1),
and the second part follows from applying the update rule of $z_{t+1}$ to
(7.2). The third part follows directly from the update rule of $z_{t+1}$.
$\Box$

In the purpose of establishing the convergence guarantee for Algorithm 1
stated by Theorem 7.2, we prove a cornerstone result that will be plugged in
the analysis. Since it plays its role inside the proof, it assumes that the
distance between consecutive decision variables converges to zero; this
presumption is established as a part of the proof of Theorem 7.2.

######  Theorem 7.1.

Let $\\{x_{t},y_{t},z_{t}\\}_{t>0}$ be the sequence generated by Algorithm 1.
Assume that
$\lim_{t\rightarrow\infty}\|x_{t+1}-x_{t}\|^{2}+\|y_{t+1}-y_{t}\|^{2}+\|z_{t+1}-z_{t}\|^{2}=0$,
that the sequence is bounded, and that $(x^{*},y^{*},z^{*})$ is an
accumulation point of the sequence. Then the following holds almost-surely:

  1. 1.

$-z^{*}\in\partial P(y^{*})$,

  2. 2.

$\nabla h(x^{*})=\mathbb{E}[M]^{T}z^{*}$,

  3. 3.

$\mathbb{E}[M]x^{*}=y^{*}$.

###### Proof.

By the definition of $\beta$ in 3.1, there exists an index $K_{stable}$, such
that $\beta_{k}=\beta_{K_{stable}}$ for all $k>K_{stable}$.

Let $\\{x_{t_{i}},y_{t_{i}},z_{t_{i}}\\}_{i\geq 1}$ be a subsequence
converging to the accumulation point $(x^{*},y^{*},z^{*})$, and for
convenience, set $\bar{\beta}=\beta_{K_{stable}}$ and assume without loss of
generality that $t_{1}>K_{stable}$, meaning that $\beta_{t_{i}}=\bar{\beta}$
for any $i\geq 1$.

The first part of the theorem requires a lengthy technical result to prove,
and so we start with the second and the third parts.

For the second part, we note that by the second part of 7.1, for the $t_{i}$
element of the subsequence:

$\nabla
h(x_{t_{i}})-(\bar{M}^{t_{i}})^{T}z_{t_{i}}=-\nabla\phi(x_{t_{i}})+\nabla\phi(x_{t_{i}-1}).$
(7.3)

By the convergence of the subsequence
$\\{x_{t_{i}},y_{t_{i}},z_{t_{i}}\\}_{i\geq 0}$ to $(x^{*},y^{*},z^{*})$ and
the assumption that
$\lim_{t\rightarrow\infty}\|x_{t+1}-x_{t}\|^{2}+\|y_{t+1}-y_{t}\|^{2}+\|z_{t+1}-z_{t}\|^{2}=0$,
it holds that $x_{t_{i}-1}\xrightarrow{i\to\infty}x^{*}$. Consequently,
utilizing the fact that $\phi$ is continuously differentiable, it follows that
$\nabla\phi(x_{t_{i}}),\nabla\phi(x_{t_{i}-1})\xrightarrow{i\to\infty}\nabla\phi(x^{*})$,
and therefore, by taking $i\to\infty$ we obtain that

$-\nabla\phi(x_{t_{i}})+\nabla\phi(x_{t_{i}-1})\xrightarrow{i\to\infty}0.$
(7.4)

Additionally, by the strong law of large numbers (see Borovkov [7, Theorem
11.3.1]),

$\bar{M}^{t_{i}}\xrightarrow{i\to\infty}\mathbb{E}[M].$ (7.5)

Combining (7.3), (7.4), and (7.5), yields the second part of the lemma

$\nabla h(x^{*})=\mathbb{E}[M]^{T}z^{*}.$

To see the correctness of the third part of the lemma, we note that by the
third part of 7.1, for the $t_{i}$ element of the subsequence we have that

$\bar{M}^{t_{i}}x_{t_{i}}-y_{t_{i}}=\dfrac{1}{\beta_{t_{i}}}(z_{t_{i}-1}-z_{t_{i}}).$

Recall that our subsequence satisfies that $\beta_{t_{i}}=\bar{\beta}$.
Therefore, for all $i\geq 1$,

$\bar{M}^{t_{i}}x_{t_{i}}-y_{t_{i}}=\dfrac{1}{\bar{\beta}}(z_{t_{i}-1}-z_{t_{i}}).$

By our assumption that $\lim_{t\rightarrow\infty}\|z_{t+1}-z_{t}\|^{2}=0$, we
thus obtain by taking $i\to\infty$ that

$\mathbb{E}[M]x^{*}=y^{*},$

which concludes the proof of the third part.

To prove the first part of the theorem, we will need to establish that

$\lim\limits_{i\to\infty}P(y_{t_{i}})=P(y^{*}).$ (7.6)

We will a priori assume that (7.6) holds, utilize it to prove the first part
of the theorem, and only then establish that (7.6) indeed holds true.

Note that by the first part of 7.1, for the $t_{i}$ element of the
subsequence,

$0\in\partial
P(y_{t_{i}})+z_{t_{i}}+\beta_{t_{i}}\bar{M}^{t+1}(x_{t_{i}}-x_{t_{i}-1}).$

Recall that for $t$ such that $t>K_{stable}$, $\beta_{t}=\bar{\beta}$, and
that $t_{1}>K_{stable}$. Therefore, for all $i\geq 1$,

$0\in\partial
P(y_{t_{i}})+z_{t_{i}}+\bar{\beta}\bar{M}^{t+1}(x_{t_{i}}-x_{t_{i}-1}).$

Since $\lim\limits_{i\to\infty}y_{t_{i}}=y^{*}$ and
$\lim\limits_{i\to\infty}P(y_{t_{i}})=P(y^{*})$ by our assumption, from
Rockafellar and Wets [22, Proposition 8.7] we have that

$\limsup\limits_{i\to\infty}\partial P(y_{t_{i}})\subset\partial P(y^{*}).$

Taking $i\to\infty$, using the fact that $\limsup\limits_{i\to\infty}\partial
P(y_{t_{i}})\subset\partial P(y^{*})$ and the assumption
$\lim_{t\rightarrow\infty}\|x_{t+1}-x_{t}\|^{2}=0$, we conclude that

$-z^{*}\in\partial P(y^{*}),$

which establishes the first part of the theorem – given that (7.6) holds true.

All that remains is to prove the correctness of (7.6). To that end, it is
sufficient to show that: (i) $\liminf\limits_{i\to\infty}P(y_{t_{i}})\geq
P(y^{*})$, and (ii) $\limsup\limits_{i\to\infty}P(y_{t_{i}})\leq P(y^{*})$,
hold true.

The first relation

$\liminf\limits_{i\to\infty}P(y_{t_{i}})\geq P(y^{*})$ (7.7)

follows immediately from the lower semicontinuity of $P$.

By the convergence of the subsequence
$\\{x_{t_{i}},y_{t_{i}},z_{t_{i}}\\}_{i\geq 0}$, and our assumption that
$\lim_{t\rightarrow\infty}\|x_{t+1}-x_{t}\|^{2}+\|y_{t+1}-y_{t}\|^{2}+\|z_{t+1}-z_{t}\|^{2}=0$,
it follows that

$x_{t_{i}-1}\xrightarrow{i\to\infty}x^{*}\text{ and
}z_{t_{i}-1}\xrightarrow{i\to\infty}z^{*}.$

To establish that $\limsup\limits_{i\to\infty}P(y_{t_{i}})\leq P(y^{*})$ holds
true, first note that since all the components of
$\mathcal{L}_{\bar{\beta}}(x,y,z;M)$ other than $P(y)$ are continuous and
$\\{(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1},\bar{M}^{t_{i}})\\}\xrightarrow{i\to\infty}(x^{*},y^{*},z^{*},\mathbb{E}[M])$,
it is sufficient to show that

$\limsup\limits_{i\to\infty}\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1};\bar{M}^{t_{i}})\leq\mathcal{L}_{\bar{\beta}}(x^{*},y^{*},z^{*};\mathbb{E}[M]):=\mathcal{L}_{\bar{\beta}}(x^{*},y^{*},z^{*}).$

To prove the above, we will show that the sequence
$\\{\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1};\bar{M}^{t_{i}})\\}_{i\geq
0}$ is bounded. Then, we will show that the limit of every convergent
subsequence is bounded by $\mathcal{L}_{\bar{\beta}}(x^{*},y^{*},z^{*})$.

Since $P$ is proper, there exists $\tilde{y}$ such that $P(\tilde{y})<\infty$.
By 3, the sequence $\\{x_{t},y_{t},z_{t}\\}_{t\geq 0}$ is bounded, and as we
stated previously, all the components of $\mathcal{L}_{\bar{\beta}}(x,y,z;M)$
except $P(y)$ are continuous. Subsequently, it follows that

$\displaystyle\mathop{\mbox{\rm inf}}\limits_{i\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1};\bar{M}^{t_{i}})-P(y_{t_{i}})\\}\text{
and }\displaystyle\mathop{\mbox{\rm inf}}\limits_{i\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},\tilde{y},z_{t_{i}-1};\bar{M}^{t_{i}})-P(\tilde{y})\\},$
$\displaystyle\mathop{\mbox{\rm sup}}\limits_{i\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1};\bar{M}^{t_{i}})-P(y_{t_{i}})\\}\text{
and }\displaystyle\mathop{\mbox{\rm sup}}\limits_{i\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},\tilde{y},z_{t_{i}-1};\bar{M}^{t_{i}})-P(\tilde{y})\\},$

exist and are finite.

By the definition of the update of $y$, $y_{t_{i}}$ is a minimizer of
$\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y,z_{t_{i}-1};\bar{M}^{t_{i}})$. Hence,

$\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1})\leq\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},\tilde{y},z_{t_{i}-1}).$

Moreover, by the definition of supremum and infimum,

$\displaystyle\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1})$
$\displaystyle=\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1})-P(y_{t_{i}})+P(y_{t_{i}})$
$\displaystyle\geq P(y_{t_{i}})+\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}$

and

$\displaystyle\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},\tilde{y},z_{t_{i}-1})$
$\displaystyle=\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},\tilde{y},z_{t_{i}-1})-P(\tilde{y})+P(\tilde{y})$
$\displaystyle\leq P(\tilde{y})+\displaystyle\mathop{\mbox{\rm
sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}.$

Combining the inequalities above, we get

$P(y_{t_{i}})+\displaystyle\mathop{\mbox{\rm inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}\leq
P(\tilde{y})+\displaystyle\mathop{\mbox{\rm sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}.$

Rearranging the terms, we obtain that

$P(y_{t_{i}})\leq P(\tilde{y})+\displaystyle\mathop{\mbox{\rm
sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}-\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}$

for all $i\geq 1$.

Taking the limit, and using the fact that

$P(\tilde{y})+\displaystyle\mathop{\mbox{\rm sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}-\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}$

is a sum comprising 3 finite elements, non of which depend on $i$, yields

$\displaystyle\liminf\limits_{i\geq 1}P(y_{t_{i}})$
$\displaystyle\leq\liminf\limits_{i\geq
1}\\{P(\tilde{y})+\displaystyle\mathop{\mbox{\rm sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}-\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}\\}$
$\displaystyle=P(\tilde{y})+\displaystyle\mathop{\mbox{\rm sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}-\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}.$

Combining the latter with (7.7) then results with

$P(y^{*})\leq P(\tilde{y})+\displaystyle\mathop{\mbox{\rm sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}-\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}.$

Recalling once again that

$P(\tilde{y})+\displaystyle\mathop{\mbox{\rm sup}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},\tilde{y},z_{t_{j}-1};\bar{M}^{t_{j}})-P(\tilde{y})\\}-\displaystyle\mathop{\mbox{\rm
inf}}\limits_{j\geq
1}\\{\mathcal{L}_{\bar{\beta}}(x_{t_{j}-1},y_{t_{j}},z_{t_{j}-1};\bar{M}^{t_{j}})-P(y_{t_{j}})\\}$

is a constant, it immediately follows that

$P(y^{*})<\infty.$

Therefore,

$\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y^{*},z_{t_{i}-1};\bar{M}^{t_{i}})<\infty.$

Since $y_{t_{i}}$ is the minimizer of
$\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y,z_{t_{i}-1};\bar{M}^{t_{i}})$,

$\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1};\bar{M}^{t_{i}})<\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y^{*},z_{t_{i}-1};\bar{M}^{t_{i}})<\infty$

for all $i$.

Taking the limit, we obtain that

$\limsup\limits_{i\to\infty}\mathcal{L}_{\bar{\beta}}(x_{t_{i}-1},y_{t_{i}},z_{t_{i}-1};\bar{M}^{t_{i}})\leq\mathcal{L}_{\bar{\beta}}(x^{*},y^{*},z^{*};\mathbb{E}[M])=\mathcal{L}_{\bar{\beta}}(x^{*},y^{*},z^{*}).$

Since all the elements of $\mathcal{L}_{\bar{\beta}}(x,y,z;M)$ other than $P$
are continuous, we have that

$\limsup\limits_{i\to\infty}P(y_{t_{i}})\leq P(y^{*}).$

Combining this with (7.7) we can finally conclude that

$\lim\limits_{i\to\infty}P(y_{t_{i}})=P(y^{*}).$

$\Box$

Theorem 7.1 essentially provides us the guarantee that any accumulation point
of the meta algorithm Algorithm 1 is almost surely a critical point of
Equation 1.1. All that remains is to show that the assumption
$\lim\limits_{t\to\infty}\|x_{t+1}-x_{t}\|^{2}+\|y_{t+1}-y_{t}\|^{2}+\|z_{t+1}-z_{t}\|^{2}=0$
indeed holds true under our blanket assumptions on the model. We do so in the
proof process of our main result stated by Theorem 7.2.

######  Theorem 7.2.

Suppose that 1 and 3 hold true. Let $\theta_{t}$ be chosen according to the
sampling regime in 4.3, and let $\\{x_{t},y_{t},z_{t}\\}_{t>0}$ be the
sequence generated by Algorithm 1. Then for every cluster point
$(x^{*},y^{*},z^{*})$ of $\\{x_{t},y_{t},z_{t}\\}_{t>0}$, $x^{*}$ is a
critical point of (1.1) almost surely.

###### Proof.

Before initiating the proof process, let us recall a few definitions and
facts.

By 3.1, we have the following guarantees on the sequence
$\\{\beta_{t}\\}_{t\geq 0}$: There exists an index $K_{stable}$ such that

  1. 1.

$\beta$ stability: For all $k>K_{stable}$, $\beta_{k}=\beta_{K_{stable}}$; for
convenience we denote it by $\bar{\beta}=\beta_{K_{stable}}$.

  2. 2.

Sufficient decrease: There exists $\rho>0$ such that for all $k>K_{stable}$

$g^{k+1}(x_{k+1})-g^{k+1}(x_{k})\leq-\dfrac{\rho}{2}\|x_{k+1}-x_{k}\|^{2},$

and

$\rho>\dfrac{8}{\beta_{k}\sigma}\left(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\right),$

where $L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ and
$L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ are the empirical Lipschitz
constants defined in 2.2.

Our analysis will focus on the iterations executed after reaching stability,
i.e., $t\geq K_{stable}$. To underscore the fact that $\\{\beta_{t}\\}_{t\geq
0}$ is constant we will replace $\beta_{t}$ with $\bar{\beta}$ throughout this
proof. For the sake of ease of reading, we will also use the notation

$\mu:=L^{e}_{\nabla h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0}),$ (7.8)

and

$\nu:=L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0}).$ (7.9)

We begin the proof with outlining its main steps. The proof consists of 4
milestones:

  1. 1.

Bounding $\|z_{t+1}-z_{t}\|^{2}$ via the relation

$\displaystyle\|z_{t+1}$ $\displaystyle-z_{t}\|^{2}$ (7.10)
$\displaystyle\leq$
$\displaystyle\dfrac{4\mu}{\sigma}\|x_{t+1}-x_{t}\|^{2}+\dfrac{4\nu}{\sigma}\|x_{t}-x_{t-1}\|^{2}+\dfrac{2}{\sigma}(\|\delta_{t+1}^{T}z_{t+1}\|+\|\delta_{t}^{T}z_{t}\|)^{2}.$

  2. 2.

Showing that

$\lim\limits_{t\to\infty}\|x_{t+1}-x_{t}\|^{2}=0\;\Rightarrow\;\lim\limits_{t\to\infty}\|x_{t+1}-x_{t}\|^{2}+\|y_{t+1}-y_{t}\|^{2}+\|z_{t+1}-z_{t}\|^{2}=0.$
(7.11)

  3. 3.

Showing that there exists a sequence of scalar random variables
$\\{d_{t}\\}_{t\geq 0}$ such that

$\sum\limits_{t=0}^{\infty}d_{t+1}<\infty$ (7.12)

almost surely, satisfying that

$\displaystyle\mathcal{L}_{\bar{\beta}}(x_{t+1},y_{t+1},z_{t+1};\bar{M}^{t+1})-\mathcal{L}_{\bar{\beta}}(x_{t},y_{t},z_{t};\bar{M}^{t})$
(7.13) $\displaystyle\leq\dfrac{4}{\sigma\bar{\beta}}(L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\|x_{t+1}-x_{t}\|^{2}+L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq
0})\|x_{t}-x_{t-1}\|^{2})-\dfrac{\rho}{2}\|x_{t+1}-x_{t}\|^{2}+d_{t+1}.$

  4. 4.

Showing that there exist random variables $C_{1},C_{2}$, such that $C_{1}<0$,
$C_{2}<\infty$ almost surely, and

$\mathcal{L}_{\beta_{t+1}}(x_{t+1},y_{t+1},z_{t+1};\bar{M}^{t+1})\leq\sum\limits_{i=K_{stable}+1}^{t-1}C_{1}\|x_{i+1}-x_{i}\|^{2}+\sum\limits_{i=K_{stable}+1}^{t}d_{t+1}+C_{2}.$
(7.14)

Assuming that (7.11), (7.12) and (7.14) hold true, the proof of the theorem is
quite straightforward, and therefore, we start from the end under the premise
of these four milestones.

Main proof assuming the four milestones.
Consider an accumulation point $(x^{*},y^{*},z^{*})$ of
$\\{x_{t},y_{t},z_{t}\\}_{t>0}$, and its convergent subsequence
$\\{x_{t_{i}},y_{t_{i}},z_{t_{i}}\\}_{i\geq 0}$. We note the following facts:

  1. 1.

$\mathcal{L}_{\bar{\beta}}(\cdot,\cdot,\cdot;A)$ is continuous in its last
argument.

  2. 2.

$\bar{M}^{t}\xrightarrow{t\to\infty}\mathbb{E}[M]$.

  3. 3.

$\mathcal{L}_{\bar{\beta}}$ is lower semicontinuous.

  4. 4.

$P$ is proper, and therefore $\mathcal{L}_{\bar{\beta}}$ is proper.

Using these facts, and the notation
$\mathcal{L}_{\bar{\beta}}(\cdot,\cdot,\cdot,\mathbb{E}[M])=\mathcal{L}_{\bar{\beta}}$,
the following inequalities hold true with respect to the accumulation point
$(x^{*},y^{*},z^{*})$ and the convergent subsequence
$\\{x_{t_{i}},y_{t_{i}},z_{t_{i}}\\}_{i\geq 0}$,

$\liminf_{i\to\infty}\mathcal{L}_{\bar{\beta}}(x_{t_{i}},y_{t_{i}},z_{t_{i}};\bar{M^{t_{i}}})\geq\mathcal{L}_{\bar{\beta}}(x^{*},y^{*},z^{*})>-\infty.$
(7.15)

Combining (7.15) with (7.14), we deduce that there exists a sequence of random
variables $\\{d_{t}\\}_{t\geq 0}$ such that

$\sum\limits_{i=K_{stable}+1}^{\infty}C_{1}\|x_{i+1}-x_{i}\|^{2}+\sum\limits_{i=K_{stable}+1}^{\infty}d_{t+1}+C_{2}>-\infty,$

which implies, by (7.12) stating that

$\sum\limits_{i=K_{stable}+1}^{\infty}d_{t+1}<\infty\quad\text{ almost
surely,}$

that

$\sum\limits_{i=K_{stable}+1}^{\infty}C_{1}\|x_{i+1}-x_{i}\|^{2}+C_{2}>-\infty\quad\text{
almost surely}.$

Since $C_{1}<0$ and $C_{2}<\infty$, it follows that

$\lim\limits_{t\to\infty}\|x_{t+1}-x_{t}\|^{2}=0\quad\text{ almost surely}.$

Finally, by (7.11), it follows that

$\lim\limits_{t\to\infty}\|x_{t+1}-x_{t}\|^{2}+\|y_{t+1}-y_{t}\|^{2}+\|z_{t+1}-z_{t}\|^{2}=0,$

which readily implies the required by invoking Theorem 7.1.

The remainder of the proof shall focus on proving that (7.11), (7.12) and
(7.14) hold true; we will prove all the milestones mentioned above in order of
appearance.

Milestone 1: Proving Relation (7.10).
Let $t>K_{stable}$. We note that due to 2,
$\mathbb{E}[M]^{T}\mathbb{E}[M]-\sigma I\succeq 0$, and in particular, for any
$t\geq 1$

$\langle z_{t+1}-z_{t},(\mathbb{E}[M]^{T}\mathbb{E}[M]-\sigma
I)z_{t+1}-z_{t}\rangle\geq 0,$

which is the same as

$\sigma\|z_{t+1}-z_{t}\|^{2}\leq\|\mathbb{E}[M]^{T}(z_{t+1}-z_{t})\|^{2}.$

Hence, by adding the same elements on both sides of the relation, we obtain

$\sqrt{\sigma}\|z_{t+1}-z_{t}\|-\|\delta_{t+1}^{T}z_{t+1}\|-\|\delta_{t}^{T}z_{t}\|\leq\|\mathbb{E}[M]^{T}(z_{t+1}-z_{t})\|-\|\delta_{t+1}^{T}z_{t+1}\|-\|\delta_{t}^{T}z_{t}\|.$
(7.16)

By the triangle inequality $\|a+b\|\geq\|a\|-\|b\|$, and the definition of
$\delta_{t}$,

$\displaystyle\|\mathbb{E}[M]^{T}(z_{t+1}-z_{t})\|$
$\displaystyle-\|\delta_{t+1}^{T}z_{t+1}\|-\|\delta_{t}^{T}z_{t}\|$
$\displaystyle\leq$
$\displaystyle\|\mathbb{E}[M]^{T}(z_{t+1}-z_{t})+\delta_{t+1}^{T}z_{t+1}+\delta_{t}^{T}z_{t}\|$
(7.17) $\displaystyle=$
$\displaystyle\|(\bar{M}^{t+1})^{T}z_{t+1}-(\bar{M}^{t})^{T}z_{t}\|.$

Note that by the second part of 7.1,

$(\bar{M}^{t+1})^{T}z_{t+1}=\nabla
h(x_{t+1})+\nabla\phi(x_{t+1})-\nabla\phi(x_{t}).$

Consequently,

$\displaystyle\|(\bar{M}^{t+1})^{T}z_{t+1}-(\bar{M}^{t})^{T}z_{t}\|^{2}$
$\displaystyle=\|\nabla h(x_{t+1})-\nabla
h(x_{t})+(\nabla\phi(x_{t+1})-\nabla\phi(x_{t}))-(\nabla\phi(x_{t})-\nabla\phi(x_{t-1}))\|^{2}.$

Using the inequality $\|a+b\|^{2}\leq 2\|a\|^{2}+2\|b\|^{2}$,

$\displaystyle\|(\bar{M}^{t+1})^{T}z_{t+1}-(\bar{M}^{t})^{T}z_{t}\|^{2}$
(7.18) $\displaystyle\leq 2\|\nabla h(x_{t+1})-\nabla
h(x_{t})+(\nabla\phi(x_{t+1})-\nabla\phi(x_{t}))\|^{2}+2\|\nabla\phi(x_{t})-\nabla\phi(x_{t-1})\|^{2}.$

Recall that by (7.8) and (7.9), $\mu=L^{e}_{\nabla
h+\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$ and
$\nu=L^{e}_{\nabla\phi}(\\{x_{t}\\}_{t\geq 0})$. By the definition of the
empirical Lipschitz constant in 2.2, we have that

$\|\nabla\phi(x_{t})-\nabla\phi(x_{t-1})\|^{2}\leq\nu\|x_{t}-x_{t-1}\|^{2}$
(7.19)

and

$\|\nabla h(x_{t+1})-\nabla
h(x_{t})+(\nabla\phi(x_{t+1})-\nabla\phi(x_{t}))\|^{2}\leq\mu\|x_{t+1}-x_{t}\|^{2}.$
(7.20)

Applying (7.19) and (7.20) to (7.18):

$\|(\bar{M}^{t+1})^{T}z_{t+1}-(\bar{M}^{t})^{T}z_{t}\|^{2}\leq
2\mu\|x_{t+1}-x_{t}\|^{2}+2\nu\|x_{t}-x_{t-1}\|^{2}.$ (7.21)

Using inequalities (7.16), (7), establishes that

$\sigma\|z_{t+1}-z_{t}\|^{2}\leq(\|(\bar{M}^{t+1})^{T}z_{t+1}-(\bar{M}^{t})^{T}z_{t}\|+\|\delta_{t+1}^{T}z_{t+1}\|+\|\delta_{t}^{T}z_{t}\|)^{2}.$
(7.22)

Using (7.22), (7.21) and the inequality $(a+b)^{2}\leq 2a^{2}+2b^{2}$,

$\sigma\|z_{t+1}-z_{t}\|^{2}\leq
4\mu\|x_{t+1}-x_{t}\|^{2}+4\nu\|x_{t}-x_{t-1}\|^{2}+2(\|\delta_{t+1}^{T}z_{t+1}\|+\|\delta_{t}^{T}z_{t}\|)^{2}$
(7.23)

This concludes the proof of the first milestone (7.10).

Milestone 2: Proving the implication (7.11).
First note that by the third part of 7.1,
$\bar{M}^{t+1}x_{t+1}-y_{t+1}=\dfrac{1}{\bar{\beta}}(z_{t}-z_{t+1})$, and
therefore

$y_{t+1}-y_{t}=\bar{M}^{t+1}x_{t+1}-\bar{M}^{t}x_{t}+\dfrac{1}{\bar{\beta}}(z_{t+1}-z_{t})-\dfrac{1}{\bar{\beta}}(z_{t}-z_{t-1}).$
(7.24)

Since $\bar{M}^{t+1}x_{t+1}=(\mathbb{E}[M]+\delta_{t+1})x_{t+1}$ and
$\bar{M}^{t}x_{t}=(\mathbb{E}[M]+\delta_{t})x_{t}$ (from the definition of
$\delta_{t}$), by the triangle inequality

$\|\mathbb{E}[M](x_{t+1}-x_{t})\|+\|\delta_{t+1}x_{t+1}\|+\|\delta_{t}x_{t}\|\geq\|\bar{M}^{t+1}x_{t+1}-\bar{M}^{t}x_{t}\|.$
(7.25)

Plugging (7.25) to (7.24) we obtain that