# Fully lifted random duality theory

Mihailo Stojnic 111e-mail<EMAIL_ADDRESS>
Abstract

We study a generic class of _random optimization problems_ (rops) and their
typical behavior. The foundational aspects of the random duality theory (RDT),
associated with rops, were discussed in [59], where it was shown that one can
often infer rops’ behavior even without actually solving them. Moreover, [59]
uncovered that various quantities relevant to rops (including, for example,
their typical objective values) can be determined (in a large dimensional
context) even completely analytically. The key observation was that the
_strong deterministic duality_ implies the, so-called, _strong random duality_
and therefore the full exactness of the analytical RDT characterizations.
Here, we attack precisely those scenarios where the strong deterministic
duality is not necessarily present and connect them to the recent progress
made in studying bilinearly indexed (bli) random processes in [62, 61]. In
particular, utilizing a fully lifted (fl) interpolating comparison mechanism
introduced in [62], we establish corresponding _fully lifted_ RDT (fl RDT). We
then rely on a stationarized fl interpolation realization introduced in [61]
to obtain complete _statitionarized_ fl RDT (sfl RDT). A few well known
problems are then discussed as illustrations of a wide range of practical
applications implied by the generality of the considered rops.

Index Terms: Random optimization/feasibility problems; Fully lifted random
duality theory.

##  1 Introduction

In this paper we study a generic class of random linearly constrained
optimization problems. For a given function $f({\bf
x}):{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ and a given set
${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$, we consider

$\displaystyle\min_{{\bf x}\in{\mathcal{X}}}$ $\displaystyle f({\bf x})$
subject to $\displaystyle A{\bf x}=0$ (1) $\displaystyle B{\bf x}\leq 0,$

where $A\in{\mathbb{R}}^{m_{1}\times n}$ is an $m_{1}\times n$ matrix and
$B\in{\mathbb{R}}^{m_{2}\times n}$ is an $m_{2}\times n$ matrix. To facilitate
the exposition, unless stated otherwise, we consider only the scenarios where
the objective can be computed, i.e., where it exists and is bounded.

The program in (1) is a classical optimization problem that has been studied
throughout rather vast literature over the last century (see, e.g., [11, 43,
37, 33, 34, 7, 9, 8] and references therein). Various aspects of these types
of problems are often of interest. For example, within the standard
optimization theory treatments (e.g., [11, 43, 37, 33, 34, 7, 9, 8]), when
facing problem (1), most often, the primary goal is simply finding the minimal
value of $f({\bf x})$ (and, if possible the ${\bf x}$’s that achieve it). The
secondary goal is usually to do so in a computationally as efficient way as
possible. If, say, $f({\bf x})$ and ${\mathcal{X}}$ are such that they allow
for the solving process to be done in polynomial time, one usually, from an
algorithmic point of view, considers the above problem as solvable.

Our interest in this paper is slightly different from this classical approach
and it relates to a somewhat different aspect of these problems. In
particular, we don’t necessarily look to find solutions of (1) or even to find
its objective’s optimal value. Instead, we look at a special, random, class of
problems from (1), and consider whether or not their analytical
characterization is possible without actually solving them. For small $n$ (say
$n=2$ or $n=3$), any given instance of (1) is typically solvable even fully
analytically. We, however, consider large $n$ _linear_ regime, i.e. the regime
where $\alpha_{1}=\lim_{n\rightarrow\infty}\frac{m_{1}}{n}$ and
$\alpha_{2}=\lim_{n\rightarrow\infty}\frac{m_{2}}{n}$ and both $\alpha_{1}$
and $\alpha_{2}$ remain constants as $n$ grows. Solving (1) analytically in
such a regime is in general very hard. Things, however, change if one moves to
random mediums and views $A$ and $B$ as random matrices. These scenarios are
precisely the ones initially considered in [59, 49, 48, 51, 52] where the
foundational principles of the so-called (_non-lifted_) random duality theory
(RDT) were introduced. Relying on these principles, [59, 49, 48, 51, 52]
proved the existence of the so-called strong (_non-lifted_) random duality for
a subclass of problems given in (1) where the strong deterministic duality
holds. This then turned out to be completely sufficient to enable a full
analytical characterization of the behavior of (1) even without actually
solving it.

It soon became clear though that, despite their vast generality, the results
of [59, 49, 48, 51, 52] might not ultimately be strong enough to handle more
generic instances of (1). A long line of work then followed attempting to
improve on [59, 49, 48, 51, 52]. In particular, [56, 58, 60, 54, 57] moved
things to another level and introduced a _partially lifted_ upgrade, as a way
of attacking the scenarios where the non-lifted RDT is not at its full power.
We here proceed along the same lines and move things even further by
establishing _fully lifted_ (fl) RDT. To do so, we first recognize a
connection between the random linearly constrained optimization programs
considered here and the recent progress made in studying bilinearly indexed
(bli) random processes in [62, 61]. Recognition of such a connection allows us
to ultimately introduce the fl RDT and its a complete _stationarized_ variant,
sfl RDT.

In sections that follow, we slowly introduce all the needed ingredients to
eventually establish the sfl RDT. Before proceeding with such a presentation,
we mention, right here at the beginning, that our exposition does not rely on
using any of the algorithmic or analytical results known for any specific
(deterministic) instance of (1). This basically means that the reader is not
really required to have any background in the optimization theory beyond a few
classical concept that will be rather obvious from the presentation itself.
Moreover, as it will become clear throughout the presentation, any such
concepts will be fairly general and in no way tailored particularly for the
classes of problems that we study here.

##  2 Random linearly constrained programs

As emphasized above, our focus is on random linearly constrained optimization
program (1). To be more specific, we assume that all elements of matrices
$A\in{\mathbb{R}}^{m_{1}\times n}$ and $B\in{\mathbb{R}}^{m_{2}\times n}$ are
i.i.d. standard normals and for a given set
${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$ and function $f({\bf x})$ consider

$\displaystyle\xi(f,{\mathcal{X}})=\min_{{\bf x}}$ $\displaystyle f({\bf x})$
subject to $\displaystyle A{\bf x}=0$ (2) $\displaystyle B{\bf x}\leq 0$
$\displaystyle{\bf x}\in{\mathcal{X}}.$

To facilitate writing, we assume throughout the paper that the objective of
the above program exists and is either deterministically bounded (i.e.,
bounded for any particular realization of $A$ and $B$) or that it is bounded
with overwhelming probability over the randomness of $A$ and $B$ (under
overwhelming probability, we always assume a probability that goes to $1$ as
$n\rightarrow\infty$). Moreover, to make the presentation less cumbersome, we
also assume boundedness (again, either in deterministic or random sense) of
all the functions of all the optimizing quantities that appear in the
derivations below. With these assumptions in place, we proceed by transforming
(2)

$\displaystyle\xi(f,{\mathcal{X}})$ $\displaystyle=$ $\displaystyle\min_{{\bf
x}\in{\mathcal{X}}}\max_{\lambda\geq 0,\nu}\left(f({\bf x})+\nu^{T}A{\bf
x}+\lambda^{T}B{\bf x}\right)=\min_{{\bf x}\in{\mathcal{X}}}\max_{\lambda\geq
0,\nu}\left(f({\bf
x})+\begin{bmatrix}\nu^{T}\lambda^{T}\end{bmatrix}\begin{bmatrix}A\\\
B\end{bmatrix}{\bf x}\right)$ (3) $\displaystyle=$ $\displaystyle\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf x}\right),$

where $\nu\in{\mathbb{R}}^{m_{1}},$ and $\lambda\in{\mathbb{R}}^{m}_{2},$ are
column vectors, $G\in{\mathbb{R}}^{m\times n},$ is a matrix comprised of
i.i.d. standard normals, $m=m_{1}+m_{2},$ and
${\mathcal{Y}}\subseteq{\mathbb{R}}^{m}$ is comprised of ${\bf
y}\in{\mathbb{R}}^{m}$ such that ${\bf y}_{i}\geq 0,m_{1}+1\leq i\leq
m_{1}+m_{2}$. After recognizing that ${\bf y}^{T}G{\bf x}$ is a bli process,
we are in position to utilize recent results [62, 61] (related to such
processes) to characterize $\xi(f,{\mathcal{X}})$.

###  2.1 Fully lifted interpolation

To be able to effectively use the results of [62, 61], we first, for
$r\in{\mathbb{N}}$ and $k\in\\{1,2,\dots,r+1\\}$, introduce function

$\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)={\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{\beta|s|\sqrt{n}{\bf
m}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{1}}\left(Z^{{\bf
m}_{1}}\right)\right)^{\frac{{\bf m}_{2}}{{\bf
m}_{1}}}\right)\right)^{\frac{{\bf m}_{3}}{{\bf
m}_{2}}}\dots\right)^{\frac{{\bf m}_{r}}{{\bf m}_{r-1}}}\right),$ (4)

where ${\mathcal{X}}=\\{{\bf x}^{(1)},{\bf x}^{(2)},\dots,{\bf x}^{(l)}\\}$
and ${\mathcal{Y}}=\\{{\bf y}^{(1)},{\bf y}^{(2)},\dots,{\bf y}^{(l)}\\}$ for
some $l\in{\mathbb{N}}$ and where

$\displaystyle Z$ $\displaystyle\triangleq$
$\displaystyle\sum_{i_{1}=1}^{l}\left(\sum_{i_{2}=1}^{l}e^{\beta
D_{0}^{(i_{1},i_{2})}}\right)^{s}$ $\displaystyle D_{0}^{(i_{1},i_{2})}$
$\displaystyle\triangleq$ $\displaystyle f({\bf x}^{(i_{1})})+\sqrt{t}({\bf
y}^{(i_{2})})^{T}G{\bf x}^{(i_{1})}+\sqrt{1-t}\|{\bf x}^{(i_{1})}\|_{2}({\bf
y}^{(i_{2})})^{T}\left(\sum_{k=1}^{r+1}b_{k}{\bf u}^{(2,k)}\right)$ (5)
$\displaystyle+\sqrt{t}\|{\bf x}^{(i_{1})}\|_{2}\|{\bf
y}^{(i_{2})}\|_{2}\left(\sum_{k=1}^{r+1}a_{k}u^{(4,k)}\right)+\sqrt{1-t}\|{\bf
y}^{(i_{2})}\|_{2}\left(\sum_{k=1}^{r+1}c_{k}{\bf h}^{(k)}\right)^{T}{\bf
x}^{(i_{1})},$

and

$\displaystyle a_{k}$ $\displaystyle\triangleq\hskip 7.22743pta_{k}({\bf
p},{\bf q})$ $\displaystyle\triangleq\hskip 7.22743pt\sqrt{{\bf p}_{k-1}{\bf
q}_{k-1}-{\bf p}_{k}{\bf q}_{k}}$ $\displaystyle b_{k}$
$\displaystyle\triangleq\hskip 7.22743ptb_{k}({\bf p},{\bf q})$
$\displaystyle\triangleq\hskip 7.22743pt\sqrt{{\bf p}_{k-1}-{\bf p}_{k}}$
$\displaystyle c_{k}$ $\displaystyle\triangleq\hskip 7.22743ptc_{k}({\bf
p},{\bf q})$ $\displaystyle\triangleq\hskip 7.22743pt\sqrt{{\bf q}_{k-1}-{\bf
q}_{k}},$ (6)

with vectors ${\bf m}=[{\bf m}_{0},{\bf m}_{1},{\bf m}_{2},...,{\bf
m}_{r},{\bf m}_{r+1}]$, ${\bf p}=[{\bf p}_{0},{\bf p}_{1},...,{\bf p}_{r},{\bf
p}_{r+1}]$, and ${\bf q}=[{\bf q}_{0},{\bf q}_{1},{\bf q}_{2},\dots,{\bf
q}_{r},{\bf q}_{r+1}]$ being such that ${\bf m}_{0}=1$, ${\bf m}_{r+1}=0$,

$\displaystyle 1\geq{\bf p}_{0}\geq{\bf p}_{1}\geq{\bf p}_{2}\geq\dots\geq{\bf
p}_{r}\geq{\bf p}_{r+1}$ $\displaystyle=$ $\displaystyle 0$ $\displaystyle
1\geq{\bf q}_{0}\geq{\bf q}_{1}\geq{\bf q}_{2}\geq\dots\geq{\bf q}_{r}\geq{\bf
q}_{r+1}$ $\displaystyle=$ $\displaystyle 0,$ (7)

and ${\mathcal{U}}_{k}\triangleq[u^{(4,k)},{\bf u}^{(2,k)},{\bf h}^{(k)}]$
being such that the components of $u^{(4,k)}\in{\mathbb{R}}$, ${\bf
u}^{(2,k)}\in{\mathbb{R}}^{m}$, and ${\bf h}^{(k)}\in{\mathbb{R}}^{n}$ are
i.i.d. standard normals.

The above function $\psi(\cdot)$ is in fact directly connected to
$\xi(f,{\mathcal{X}})$. For example, if say $a_{k}=0$, then
${\mathbb{E}}_{A,B}\xi(f,{\mathcal{X}})={\mathbb{E}}_{G}\xi(f,{\mathcal{X}})=-\sqrt{n}\lim_{\beta\rightarrow\infty}\psi(f,{\cal
X},{\cal Y},{\bf p},{\bf q},{\bf m},\beta,-1,1)=-\sqrt{n}\psi(f,{\cal X},{\cal
Y},{\bf p},{\bf q},{\bf m},\infty,-1,1)$. While, in the contexts of our
interest in this paper, one has that generically $a_{k}\neq 0$, it is still
fairly clear that the connection is rather strong and that studying and
understanding some of the properties of $\psi(\cdot)$ is likely to be very
useful. The following fundamental result from [62] is of key interest in that
regard.

######  Theorem 1.

([62]) Let

$\displaystyle\zeta_{r}\triangleq{\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{1}}\left(Z^{\frac{{\bf
m}_{1}}{{\bf m}_{0}}}\right)\right)^{\frac{{\bf m}_{2}}{{\bf
m}_{1}}}\right)\right)^{\frac{{\bf m}_{3}}{{\bf
m}_{2}}}\dots\right)^{\frac{{\bf m}_{r}}{{\bf m}_{r-1}}},r\geq 1.$ (8)

One then has

$\displaystyle\zeta_{k}={\mathbb{E}}_{{\mathcal{U}}_{k}}\left(\zeta_{k-1}\right)^{\frac{{\bf
m}_{k}}{{\bf m}_{k-1}}},k\geq
2,\quad\mbox{and}\quad\zeta_{1}={\mathbb{E}}_{{\mathcal{U}}_{1}}\left(Z^{\frac{{\bf
m}_{1}}{{\bf m}_{0}}}\right),$ (9)

with $\zeta_{0}=Z$ set for the completeness. Moreover, consider the operators

$\displaystyle\Phi_{{\mathcal{U}}_{k}}$ $\displaystyle\triangleq$
$\displaystyle{\mathbb{E}}_{{\mathcal{U}}_{k}}\frac{\zeta_{k-1}^{\frac{{\bf
m}_{k}}{{\bf m}_{k-1}}}}{\zeta_{k}},$ (10)

and set

$\displaystyle\gamma_{0}(i_{1},i_{2})$ $\displaystyle=$
$\displaystyle\frac{(C^{(i_{1})})^{s}}{Z}\frac{A^{(i_{1},i_{2})}}{C^{(i_{1})}}$
$\displaystyle\gamma_{01}^{(r)}$ $\displaystyle=$
$\displaystyle\prod_{k=r}^{1}\Phi_{{\mathcal{U}}_{k}}(\gamma_{0}(i_{1},i_{2}))$
$\displaystyle\gamma_{02}^{(r)}$ $\displaystyle=$
$\displaystyle\prod_{k=r}^{1}\Phi_{{\mathcal{U}}_{k}}(\gamma_{0}(i_{1},i_{2})\times\gamma_{0}(i_{1},p_{2}))$
$\displaystyle\gamma_{k_{1}+1}^{(r)}$ $\displaystyle=$
$\displaystyle\prod_{k=r}^{k_{1}+1}\Phi_{{\mathcal{U}}_{k}}\left(\prod_{k=k_{1}}^{1}\Phi_{{\mathcal{U}}_{k}}\gamma_{0}(i_{1},i_{2})\times\prod_{k=k_{1}}^{1}\Phi_{{\mathcal{U}}_{k}}\gamma_{0}(p_{1},p_{2})\right).$
(11)

Let also

$\displaystyle\phi_{k_{1}}^{(r)}$ $\displaystyle=$ $\displaystyle-s({\bf
m}_{k_{1}-1}-{\bf m}_{k_{1}})$
$\displaystyle\times{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle({\bf
p}_{k_{1}-1}\|{\bf x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}-({\bf
x}^{(p_{1})})^{T}{\bf x}^{(i_{1})})({\bf q}_{k_{1}-1}\|{\bf
y}^{(i_{2})}\|_{2}\|{\bf y}^{(p_{2})}\|_{2}-({\bf y}^{(p_{2})})^{T}{\bf
y}^{(i_{2})})\rangle_{\gamma_{k_{1}}^{(r)}}$ $\displaystyle\phi_{01}^{(r)}$
$\displaystyle=$ $\displaystyle(1-{\bf p}_{0})(1-{\bf
q}_{0}){\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}^{2}\|{\bf
y}^{(i_{2})}\|_{2}^{2}\rangle_{\gamma_{01}^{(r)}}$
$\displaystyle\phi_{02}^{(r)}$ $\displaystyle=$ $\displaystyle(s-1)(1-{\bf
p}_{0}){\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\left\langle\|{\bf
x}^{(i_{1})}\|_{2}^{2}\left({\bf q}_{0}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}-({\bf y}^{(p_{2})})^{T}{\bf
y}^{(i_{2})}\right)\right\rangle_{\gamma_{02}^{(r)}}.$ (12)

Then

$\displaystyle\frac{d\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)}{dt}$ $\displaystyle=$
$\displaystyle\frac{\mbox{sign}(s)\beta}{2\sqrt{n}}\left(\left(\sum_{k_{1}=1}^{r+1}\phi_{k_{1}}^{(r)}\right)+\phi_{01}^{(r)}+\phi_{02}^{(r)}\right).$
(13)

It particular, choosing ${\bf p}_{0}={\bf q}_{0}=1$, one also has

$\displaystyle\frac{d\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)}{dt}$ $\displaystyle=$
$\displaystyle\frac{\mbox{sign}(s)\beta}{2\sqrt{n}}\sum_{k_{1}=1}^{r+1}\phi_{k_{1}}^{(r)}.$
(14)

###### Proof.

Follows immediately after trivial modifications of the proof presented in
[62]. ∎

Now, given that

$\displaystyle\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,1)=\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,0)+\int_{0}^{1}\frac{d\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)}{dt}dt,$ (15)

the result of Theorem 1 extends the above mentioned connection between
$\xi(f,{\mathcal{X}})$ and $\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\infty,-1,1)$ so that now $\xi(f,{\mathcal{X}})$ is directly connected to
$\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf m},\infty,-1,0)$ as well.
Still, two obstacles remain to be able to fully utilize this connection: i)
handling the above mentioned $a_{k}\neq 0$ scenario; and ii) the integration
in (15). We discuss both of them in the next section.

###  2.2 Stationarization

Let $\psi_{1}$ be the following function

$\displaystyle\psi_{1}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf m},\beta,s,t)$
$\displaystyle=$
$\displaystyle-\frac{\mbox{sign}(s)s\beta}{2\sqrt{n}}\sum_{k=1}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k}^{(r)}}$ (16) $\displaystyle-{\bf
p}_{k}{\bf q}_{k}{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k+1}^{(r)}}\Bigg{.}\Bigg{)}{\bf m}_{k}$
$\displaystyle+\psi(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf m},\beta,s,t),$

and consider the following system of equations

$\displaystyle\frac{d\psi_{1}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)}{d{\bf p}_{k_{1}}}$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle\frac{d\psi_{1}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)}{d{\bf q}_{k_{1}}}$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle\frac{d\psi_{1}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)}{d{\bf m}_{k_{1}}}$ $\displaystyle=$ $\displaystyle 0,$ (17)

where $k_{1}\in\\{1,2,\dots,r\\}$ and ${\bf p}_{0}(t)={\bf q}_{0}(t)={\bf
m}_{0}(t)=1$. The following theorem is critically important.

######  Theorem 2.

([61]) Assume completely stationirized fully lifted random duality theory
frame (_complete sfl RDT frame_) of [61] with $n\rightarrow\infty$ and
$\bar{{\bf p}}(t)$, $\bar{{\bf q}}(t)$, and $\bar{{\bf m}}(t)$ as solutions of
system (2.2). For $\bar{{\bf p}}_{0}(t)=\bar{{\bf q}}_{0}(t)=1$, $\bar{{\bf
p}}_{r+1}(t)=\bar{{\bf q}}_{r+1}(t)=\bar{{\bf m}}_{r+1}(t)=0$, and ${\bf
m}_{1}(t)\rightarrow{\bf m}_{0}(t)=1$ one then has that
$\frac{d\psi_{1}(f,{\cal X},{\cal Y},\bar{{\bf p}}(t),\bar{{\bf
q}}(t),\bar{{\bf m}}(t),\beta,s,t)}{dt}=0$ and

$\displaystyle\lim_{n\rightarrow\infty}\psi_{1}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(t),\bar{{\bf q}}(t),\bar{{\bf m}}(t),\beta,s,t)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\psi_{1}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(0),\bar{{\bf q}}(0),\bar{{\bf m}}(0),\beta,s,0)$ (18) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\psi_{1}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\beta,s,1).$

Finally, the operational version of the above theorem is the following
practically relevant corollary.

######  Corollary 1.

([61]) Assume the setup of Theorem 2. Then

$\displaystyle\lim_{n\rightarrow\infty}\psi_{1}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(0),\bar{{\bf q}}(0),\bar{{\bf m}}(0),\beta,s,0)$
$\displaystyle=\lim_{n\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\mbox{sign}(s)s\beta}{2\sqrt{n}}\sum_{k=1}^{r+1}\Bigg{(}\Bigg{.}\bar{{\bf
p}}_{k-1}(0)\bar{{\bf q}}_{k-1}(0)$
$\displaystyle\times{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k}^{(r)}}$ $\displaystyle-\bar{{\bf
p}}_{k}(0)\bar{{\bf
q}}_{k}(0){\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k+1}^{(r)}}\Bigg{.}\Bigg{)}\bar{{\bf
m}}_{k}(0)$ $\displaystyle+\psi(f,{\cal X},{\cal Y},\bar{{\bf p}}(0),\bar{{\bf
q}}(0),\bar{{\bf m}}(0),\beta,s,0)\Bigg{.}\Bigg{)},$ (19)

with $\gamma$’s evaluated at $t=0$, and

$\displaystyle\lim_{n\rightarrow\infty}\psi_{1}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\beta,s,1)$
$\displaystyle=\lim_{n\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\mbox{sign}(s)s\beta}{2\sqrt{n}}\sum_{k=1}^{r+1}\Bigg{(}\Bigg{.}\bar{{\bf
p}}_{k-1}(1)\bar{{\bf q}}_{k-1}(1)$
$\displaystyle\times{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k}^{(r)}}$ $\displaystyle-\bar{{\bf
p}}_{k}(1)\bar{{\bf
q}}_{k}(1){\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k+1}^{(r)}}\Bigg{.}\Bigg{)}\bar{{\bf
m}}_{k}(1)$ $\displaystyle+\psi(f,{\cal X},{\cal Y},\bar{{\bf p}}(1),\bar{{\bf
q}}(1),\bar{{\bf m}}(1),\beta,s,1)\Bigg{.}\Bigg{)},$ (20)

with $\gamma$’s evaluated at $t=1$. Moreover, let

$\psi_{S}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s,t)={\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{\beta|s|\sqrt{n}{\bf
m}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{1}}\left(Z_{S}^{{\bf
m}_{1}}\right)\right)^{\frac{{\bf m}_{2}}{{\bf
m}_{1}}}\right)\right)^{\frac{{\bf m}_{3}}{{\bf
m}_{2}}}\dots\right)^{\frac{{\bf m}_{r}}{{\bf m}_{r-1}}}\right),$ (21)

where, analogously to (4) and (2.1),

$Z_{S}\triangleq\sum_{i_{1}=1}^{l}\left(\sum_{i_{2}=1}^{l}e^{\beta
D_{0,S}^{(i_{1},i_{2})}}\right)^{s},$ (22)

and

$\displaystyle D_{0,S}^{(i_{1},i_{2})}$ $\displaystyle\triangleq$
$\displaystyle f({\bf x}^{(i_{1})})+\sqrt{t}({\bf y}^{(i_{2})})^{T}G{\bf
x}^{(i_{1})}+\sqrt{1-t}\|{\bf x}^{(i_{1})}\|_{2}({\bf
y}^{(i_{2})})^{T}\left(\sum_{k=1}^{r+1}b_{k}{\bf u}^{(2,k)}\right)$ (23)
$\displaystyle+\sqrt{1-t}\|{\bf
y}^{(i_{2})}\|_{2}\left(\sum_{k=1}^{r+1}c_{k}{\bf h}^{(k)}\right)^{T}{\bf
x}^{(i_{1})}.$

Then

$\displaystyle\lim_{n\rightarrow\infty}\psi_{S}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\beta,s,1)$
$\displaystyle=\lim_{n\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\mbox{sign}(s)s\beta}{2\sqrt{n}}\sum_{k=1}^{r+1}\Bigg{(}\Bigg{.}\bar{{\bf
p}}_{k-1}(0)\bar{{\bf q}}_{k-1}(0)$
$\displaystyle\times{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k}^{(r)}}$ $\displaystyle-\bar{{\bf
p}}_{k}(0)\bar{{\bf
q}}_{k}(0){\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\langle\|{\bf
x}^{(i_{1})}\|_{2}\|{\bf x}^{(p_{1})}\|_{2}\|{\bf y}^{(i_{2})}\|_{2}\|{\bf
y}^{(p_{2})}\|_{2}\rangle_{\gamma_{k+1}^{(r)}}\Bigg{.}\Bigg{)}\bar{{\bf
m}}_{k}(0)$ $\displaystyle+\psi_{S}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(0),\bar{{\bf q}}(0),\bar{{\bf m}}(0),\beta,s,0)\Bigg{.}\Bigg{)},$

with $\gamma$’s evaluated at $t=0$.

###### Proof.

Follows through the same steps as Corollary 1 of [61] by disregarding its unit
norm specializations and instead relying on general $\psi(\cdot)$ from (16). ∎

##  3 Practical utilization

In this section we show how the above machinery can be practically utilized.
To that end, we first observe

$\displaystyle\lim_{n\rightarrow\infty}\psi_{S}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\infty,-1,1)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\max_{{\bf
x}\in{\mathcal{X}}}\left(-\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf x}\right)\right)}{\sqrt{n}}$ (25) $\displaystyle=$
$\displaystyle-\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf x}\right)}{\sqrt{n}}$ $\displaystyle=$
$\displaystyle-\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\xi(f,{\mathcal{X}})}{\sqrt{n}},$

where the first equality follows from the definition of $\psi_{S}(f,{\cal
X},{\cal Y},\bar{{\bf p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\infty,-1,1)$
from (21)-(23) and the last equality follows from (3). Under the boundedness
assumption, one can, at $t=0$, relying on both the $\gamma$’s decoupling over
${\bf x}$ and ${\bf y}$ and the decoupling over the components of ${\bf x}$
and ${\bf y}$, discretize over possible values for $\|{\bf x}\|_{2}$ and
$\|{\bf y}\|_{2}$. That means that all of the above discussion can be repeated
by taking fixed (and ultimately optimal) values $\bar{x}=\|{\bf x}\|_{2}$ and
$\bar{y}=\|{\bf y}\|_{2}$ which, in return, enables the following, more
convenient form of (1),

$\displaystyle\lim_{\beta,n\rightarrow\infty}\psi_{S}(f,{\cal X},{\cal
Y},\bar{{\bf p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\beta,s,1)$
$\displaystyle=$
$\displaystyle\lim_{\beta,n\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\mbox{sign}(s)s\beta}{2\sqrt{n}}\bar{x}^{2}\bar{y}^{2}$
(26) $\displaystyle\times\sum_{k=1}^{r+1}\Bigg{(}\Bigg{.}\bar{{\bf
p}}_{k-1}(0)\bar{{\bf q}}_{k-1}(0)-\bar{{\bf p}}_{k}(0)\bar{{\bf
q}}_{k}(0)\Bigg{.}\Bigg{)}\bar{{\bf m}}_{k}(0)$
$\displaystyle+\psi_{S}(f,{\mathcal{X}}_{\bar{x}},{\mathcal{Y}}_{\bar{y}},\bar{{\bf
p}}(0),\bar{{\bf q}}(0),\bar{{\bf m}}(0),\beta,s,0)\Bigg{.}\Bigg{)},$

where $\bar{{\bf p}}(0)$, $\bar{{\bf q}}(0)$, and $\bar{{\bf m}}(0)$ are
evaluated from (2.2) for $\bar{x}=\|{\bf x}\|_{2}$ and $\bar{y}=\|{\bf
y}\|_{2}$ and

$\displaystyle{\mathcal{X}}_{x}$ $\displaystyle\triangleq$
$\displaystyle\\{{\bf x}|\|{\bf x}\|_{2}=x,{\bf x}\in{\mathcal{X}}\\}$
$\displaystyle{\mathcal{Y}}_{y}$ $\displaystyle\triangleq$
$\displaystyle\\{{\bf y}|\|{\bf y}\|_{2}=y,{\bf y}\in{\mathcal{Y}}\\}.$ (27)

Keeping in mind that $\bar{{\bf m}}_{1}(0)\rightarrow 1$ and

$\displaystyle\psi_{S}(f,{\cal X},{\cal Y},\bar{{\bf p}}(0),\bar{{\bf
q}}(0),\bar{{\bf m}}(0),\beta,s,0)=\psi(f,{\cal X},{\cal Y},\bar{{\bf
p}}(0),\bar{{\bf q}}(0),\bar{{\bf m}}(0),\beta,s,0),$ (28)

one then has that (1) and (1) imply that (26) can be rewritten for $s=-1$ as

$\displaystyle\lim_{n\rightarrow\infty}\psi_{S}(f,{\cal X},{\cal Y},\bar{{\bf
p}}(1),\bar{{\bf q}}(1),\bar{{\bf m}}(1),\infty,-1,1)$ $\displaystyle=$
$\displaystyle\lim_{\beta,n\rightarrow\infty}\Bigg{(}\Bigg{.}\psi_{1}(f,{\mathcal{X}}_{\bar{x}},{\mathcal{Y}}_{\bar{x}},\bar{{\bf
p}},\bar{{\bf q}},\bar{{\bf m}},\beta,-1,0)\Bigg{.}\Bigg{)},$ (29)

where, $\bar{{\bf p}}_{0}=\bar{{\bf q}}_{0}=\bar{{\bf m}}_{0}=1$, $\bar{{\bf
m}}_{1}\rightarrow 1$, and, similarly to (2.2), for
$k_{1}\in\\{1,2,\dots,r\\}$, $\bar{{\bf p}},\bar{{\bf q}}$, and $\bar{{\bf
m}}$ are the solutions to the following system of equations

$\displaystyle\frac{d\psi_{1}(f,{\mathcal{X}}_{\bar{x}},{\mathcal{Y}}_{\bar{y}},{\bf
p},{\bf q},{\bf m},\beta,-1,0)}{d{\bf p}_{k_{1}}}$ $\displaystyle=$
$\displaystyle 0,$
$\displaystyle\frac{d\psi_{1}(f,{\mathcal{X}}_{\bar{x}},{\mathcal{Y}}_{\bar{y}},{\bf
p},{\bf q},{\bf m},\beta,-1,0)}{d{\bf q}_{k_{1}}}$ $\displaystyle=$
$\displaystyle 0,$
$\displaystyle\frac{d\psi_{1}(f,{\mathcal{X}}_{\bar{x}},{\mathcal{Y}}_{\bar{y}},{\bf
p},{\bf q},{\bf m},\beta,-1,0)}{d{\bf m}_{k_{1}}}$ $\displaystyle=$
$\displaystyle 0.$ (30)

Since ${\bf m}_{1}\rightarrow 1$, we can integrate out the most inner
expectation of $\psi(\cdot)$ over ${\bf x}$ to obtain

$\displaystyle\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},\beta,s,0)$ $\displaystyle=$
$\displaystyle\Bigg{(}\Bigg{.}-\frac{\beta x^{2}y^{2}}{2\sqrt{n}}\left(1-{\bf
p}_{1}{\bf q}_{1}\right)-\frac{\beta
x^{2}y^{2}}{2\sqrt{n}}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf p}_{k-1}{\bf
q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf m}_{k}$
$\displaystyle+\frac{\beta x^{2}y^{2}}{2\sqrt{n}}\left(1-{\bf
q}_{1}\right)+\psi_{S,2}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{x},{\bf p},{\bf
q},{\bf m},\beta,-1)\Bigg{.}\Bigg{)},$

where, similarly to (21),

$\psi_{S,2}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s)={\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{\beta|s|\sqrt{n}{\bf
m}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(Z_{S,2}^{{\bf
m}_{1}}\right)\right)^{\frac{{\bf m}_{2}}{{\bf
m}_{1}}}\right)\right)^{\frac{{\bf m}_{3}}{{\bf
m}_{2}}}\dots\right)^{\frac{{\bf m}_{r}}{{\bf m}_{r-1}}}\right),$ (32)

and, analogously to (4) and (2.1) (or (22) and (23)),

$Z_{S,2}\triangleq\sum_{x\in{\mathcal{X}}}\left(\sum_{{\bf
y}\in{\mathcal{Y}}}e^{\beta D_{0,S,2}^{({\bf x},{\bf y})}}\right)^{s},\\\ $

but

$\displaystyle D_{0,S,2}^{({\bf x},{\bf y})}$ $\displaystyle\triangleq$
$\displaystyle f({\bf x})+\|{\bf x}\|_{2}{\bf
y}^{T}\left(\sum_{k=1}^{r+1}b_{k}{\bf u}^{(2,k)}\right)+\|{\bf
y}\|_{2}\left(\sum_{k=2}^{r+1}c_{k}{\bf h}^{(k)}\right)^{T}{\bf x}.$ (33)

A ground state regime rescaling, $\beta\rightarrow\bar{\beta}\sqrt{n}$, (where
($\bar{\beta}\rightarrow\infty$)) gives $\bar{\beta}\bar{{\bf
m}}_{k}=\bar{{\bf c}}_{k}$ ($\bar{\beta}{\bf m}_{k}={\bf c}_{k}$) for $k>1$
and $\bar{{\bf c}}_{1}\rightarrow\bar{{\bf m}}_{1}\rightarrow 1$ (or ${\bf
c}_{1}\rightarrow{\bf m}_{1}\rightarrow 1$) with $\bar{{\bf c}}_{k}$ (or ${\bf
c}_{k}$) remaining constants as $\bar{\beta}$ grows. We then have

$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1,0)$ $\displaystyle=$
$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\bar{\beta}x^{2}y^{2}}{2}\left(1-{\bf
p}_{1}{\bf
q}_{1}\right)-\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf c}_{k}$
$\displaystyle+\frac{\bar{\beta}x^{2}y^{2}}{2}\left(1-{\bf
q}_{1}\right)+\psi_{S,2}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},\beta,-1)\Bigg{.}\Bigg{)}.$

One now also observes

$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\frac{\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1,0)}{d{\bf q}_{1}}$ $\displaystyle=$
$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\bar{\beta}x^{2}y^{2}}{2}\left(1-{\bf
p}_{1}\right)+O(1)\Bigg{.}\Bigg{)}=0,$

which ensures

$\displaystyle\bar{{\bf p}}_{1}=1-\frac{c_{x}}{\bar{\beta}}\rightarrow 1,$
(36)

where $c_{x}$ remains constant as $\bar{\beta}$ grows. One now also has

$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\psi_{S,2}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1)$ $\displaystyle=$
$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\psi_{S,3}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1).$

where

$\displaystyle\psi_{S,3}(f,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
m},\beta,s)={\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{\beta|s|\sqrt{n}{\bf
m}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(Z_{S,3}^{{\bf
m}_{1}}\right)\right)^{\frac{{\bf m}_{2}}{{\bf
m}_{1}}}\right)\right)^{\frac{{\bf m}_{3}}{{\bf
m}_{2}}}\dots\right)^{\frac{{\bf m}_{r}}{{\bf m}_{r-1}}}\right),$ (38)

and, analogously to (4) and (2.1),

$\displaystyle Z_{S,3}$ $\displaystyle\triangleq$ $\displaystyle e^{\beta
D_{0,S,3}}$ $\displaystyle D_{0,S,3}$ $\displaystyle\triangleq$
$\displaystyle\max_{{\bf x}\in{\mathcal{X}},\|{\bf x}\|_{2}=x}s\max_{{\bf
y}\in{\mathcal{Y}},\|{\bf
y}\|_{2}=y}\left(f_{S}+y\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}+x{\bf y}^{T}\left(\sum_{k=1}^{r+1}b_{k}{\bf
u}^{(2,k)}\right)\right),$

where $a_{k}\triangleq a_{k}({\bf p},{\bf q})$, $b_{k}\triangleq b_{k}({\bf
p},{\bf q})$, and $c_{k}\triangleq c_{k}({\bf p},{\bf q})$ are as in (2.1).
Since $\bar{{\bf p}}_{1}=1-\frac{c_{x}}{\beta}\rightarrow 1$, one has
$b_{1}=\sqrt{1-\bar{{\bf p}}_{1}}=\sqrt{\frac{c_{x}}{\beta}}\rightarrow 0$.
Let $\bar{{\bf y}}$ be the solution of the above optimization. Then one can
assume that $\bar{{\bf y}}$ depends only on those $k$ where $b_{k}=O(1)$. That
also means that one can write

$\displaystyle\lim_{\beta\rightarrow\infty}\psi_{S,3}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1)$ $\displaystyle=$
$\displaystyle\lim_{\beta\rightarrow\infty}\left(\frac{\beta^{2}x^{2}b_{1}^{2}\|\bar{{\bf
y}}\|_{2}^{2}}{2\beta\sqrt{n}}+\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},x,y)\right)$ $\displaystyle=$
$\displaystyle\lim_{\beta\rightarrow\infty}\left(\frac{\bar{\beta}x^{2}y^{2}(1-{\bf
p}_{1})}{2}+\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},x,y)\right),$

where

$\displaystyle\psi_{S,\infty}(f_{S},{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
c},x,y)={\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{n{\bf
c}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{1}}\left(Z_{S,\infty}^{{\bf
c}_{2}}\right)\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right)\right)^{\frac{{\bf c}_{4}}{{\bf
c}_{3}}}\dots\right)^{\frac{{\bf c}_{r}}{{\bf c}_{r-1}}}\right)$

and, analogously to (4) and (2.1),

$\displaystyle Z_{S,\infty}$ $\displaystyle\triangleq$ $\displaystyle
e^{D_{0,S,\infty}}$ $\displaystyle D_{0,S,\infty}$ $\displaystyle\triangleq$
$\displaystyle\max_{{\bf x}\in{\mathcal{X}},\|{\bf x}\|_{2}=x}-\max_{{\bf
y}\in{\mathcal{Y}},\|{\bf
y}\|_{2}=y}\left(f_{S}+y\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}^{(i_{1})}+x({\bf
y}^{(i_{2})})^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf u}^{(2,k)}\right)\right)$
$\displaystyle=$ $\displaystyle-\min_{{\bf x}\in{\mathcal{X}},\|{\bf
x}\|_{2}=x}\max_{{\bf y}\in{\mathcal{Y}},\|{\bf
y}\|_{2}=y}\left(f_{S}+y\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}^{(i_{1})}+x({\bf
y}^{(i_{2})})^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf u}^{(2,k)}\right)\right),$

where, as above and as in (2.1), $a_{k}\triangleq a_{k}({\bf p},{\bf q})$,
$b_{k}\triangleq b_{k}({\bf p},{\bf q})$, and $c_{k}\triangleq c_{k}({\bf
p},{\bf q})$. Combining (3), (3), and (3), we find

$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1,0)$
$\displaystyle=\lim_{\bar{\beta}\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\bar{\beta}x^{2}y^{2}}{2}\left(1-{\bf
p}_{1}{\bf
q}_{1}\right)-\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf c}_{k}$
$\displaystyle\quad+\frac{\bar{\beta}x^{2}y^{2}(1-{\bf
q}_{1})}{2}+\frac{\bar{\beta}x^{2}y^{2}(1-{\bf
p}_{1})}{2}+\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},x,y)\Bigg{.}\Bigg{)}.$

One now also observes

$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\frac{\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1,0)}{d{\bf p}_{1}}$ $\displaystyle=$
$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\bar{\beta}x^{2}y^{2}}{2}\left(1-{\bf
q}_{1}\right)+O(1)\Bigg{.}\Bigg{)}=0,$

which ensures

$\displaystyle\bar{{\bf q}}_{1}=1-\frac{c_{y}}{\bar{\beta}}\rightarrow 1,$
(44)

where $c_{y}$ remains constant as $\bar{\beta}$ grows. Combining (36), (3),
and (44), we find

$\displaystyle\lim_{\bar{\beta}\rightarrow\infty}\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf m},\beta,-1,0)$
$\displaystyle=\lim_{\bar{\beta}\rightarrow\infty}\Bigg{(}\Bigg{.}-\frac{\bar{\beta}x^{2}y^{2}}{2}\left(1-{\bf
p}_{1}{\bf
q}_{1}\right)-\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf c}_{k}$
$\displaystyle\quad+\frac{\bar{\beta}x^{2}y^{2}(1-{\bf
q}_{1})}{2}+\frac{\bar{\beta}x^{2}y^{2}(1-{\bf
p}_{1})}{2}+\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},x,y)\Bigg{.}\Bigg{)}$
$\displaystyle=-\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}+\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},x,y),$

and

$-\lim_{\bar{\beta}\rightarrow\infty}\psi_{1}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf
p},{\bf q},{\bf
m},\beta,-1,0)=\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},x,y).$ (46)

After adding an outer optimization over $x$ and $y$, we obtain

$\displaystyle-\lim_{\beta,n\rightarrow\infty}\psi_{1}(f,{\mathcal{X}}_{\bar{x}},{\mathcal{Y}}_{\bar{y}},\bar{{\bf
p}},\bar{{\bf q}},\bar{{\bf m}},\beta,-1,0)$ $\displaystyle=$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\Bigg{(}\Bigg{.}\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}\bar{{\bf
p}}_{k-1}\bar{{\bf q}}_{k-1}-\bar{{\bf p}}_{k}\bar{{\bf
q}}_{k}\Bigg{.}\Bigg{)}{\bf c}_{k}$ (47)
$\displaystyle-\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},\bar{{\bf
p}},\bar{{\bf q}},\bar{{\bf m}},x,y)\Bigg{.}\Bigg{)},$

where $\bar{{\bf p}},\bar{{\bf q}}$, and $\bar{{\bf m}}$ are the solutions to
the system of equations (3) evaluated for ${\mathcal{X}}_{x}$ and
${\mathcal{Y}}_{y}$ with $x$ and $y$ being the running parameters of the above
optimization. A combination of (25), (29), and (47) finally gives

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\xi(f,{\mathcal{X}})}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\left(\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(f,{\mathcal{X}}_{x},{\mathcal{Y}}_{y},{\bf p},{\bf
q},{\bf m},x,y)\right).$

The above results are summarized in the following theorem.

######  Theorem 3.

Assume large $n$ regime and
$\lim_{n\rightarrow\infty}\frac{m_{1}}{n}=\alpha_{1}$ and
$\lim_{n\rightarrow\infty}\frac{m_{2}}{n}=\alpha_{2}$, where $\alpha_{1}$ and
$\alpha_{2}$ are constants (i.e., independent of $n$). Let matrices
$A\in{\mathbb{R}}^{m_{1}\times n}$ and $B\in{\mathbb{R}}^{m_{2}\times n}$ be
comprised of i.i.d. standard normal elements. For a given function $f({\bf
x}):R^{n}\rightarrow R$, let $\xi(f,{\mathcal{X}})$ be the objective value of
the optimization problem in (2). Assume complete sfl RDT frame from [61] and
that $f({\bf x})$ is such that $|\xi(f,{\mathcal{X}})|<\infty$ with
overwhelming probability. Set

$\displaystyle\psi_{rp}$ $\displaystyle\triangleq\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf
x}\right)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{random
primal}})}$ $\displaystyle\psi_{rd}({\bf p},{\bf q},{\bf c},x,y)$
$\displaystyle\triangleq\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(f({\bf x}),{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
c},x,y)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{fl
random dual}})}.$

Let $\hat{{\bf p}}\triangleq\hat{{\bf p}}(x,y)$, $\hat{{\bf
q}}\triangleq\hat{{\bf q}}(x,y)$, and $\hat{{\bf c}}\triangleq\hat{{\bf
c}}(x,y)$ be the solutions of the following system

$\displaystyle\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},x,y)}{d{\bf
p}}=0,\quad\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},x,y)}{d{\bf
q}}=0,\quad\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},x,y)}{d{\bf c}}=0.$ (50)

Then,

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\psi_{rd}(\hat{{\bf
p}}(x,y),\hat{{\bf q}}(x,y),\hat{{\bf
c}}(x,y),x,y)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{strong
sfl random duality}})},$

where $\psi_{S,\infty}(\cdot)$ is as in (3).

###### Proof.

Follows from previous discussion after recognizing that $\psi_{1}(\cdot)$ in
(2.2) evaluated for $t=0$ and fixed $x$ and $y$, such that $\|{\bf x}\|_{2}=x$
and $\|{\bf y}\|_{2}=y$, is precisely $\psi_{rd}(\cdot)$. ∎

Since the random primal concentrates, one can then write various corresponding
probabilistic variants of (3). We, however, skip such exercises and, instead,
note that the above theorem essentially connects $\psi_{rp}$ and $\psi_{rd}$.
That basically means that if, say ${\mathcal{X}}$ and ${\mathcal{Y}}$ are such
that their elements are of fixed norms the above theorem holds for fixed $x$
and $y$, i.e., it holds without the optimization over $x$ and $y$ in (3).
Various further generalizations and applications are possible as well. We
below discuss a few interesting ones and defer a more complete discussion to
separate papers that treat various specific problems in details.

###  3.1 Non-homogeneous linear constraints

The mechanism presented in the previous section is very powerful tool to
characterize behavior of random linearly constrained optimization programs. It
is also very generic and can be extended in many directions. As mentioned
above, such extensions are typically problem specific and we defer studying
them in details to separate papers. We do, however, mention here that all the
tools that we use in those papers are conceptually already contained in what
we presented above.

The example that we discuss below is a rather small modification of the above
generic model and is provided to give a bit of a hint as to how relatively
easily the whole framework can be massaged to fit various other scenarios. As
it will be clear soon, all these modifications could have already been
included in our original setup, albeit, at the expense of having a tone of
tiny details overwhelm the presentation. In order to preserve the lightness of
the exposition and to facilitate writing and reading, we opted to start with
the simplest possible example and then build from there.

It is not that difficult to see that the set of linear constraints in (1) is
scaling invariant (basically homogeneous). For any ${\bf x}$ that satisfies
linear constraints of (1), $c{\bf x}$ does so as well as long as $c\geq 0$.
Instead of homogeneous linear constraints one, usually, has the following,
more general variant,

$\displaystyle\min_{{\bf x}}$ $\displaystyle f({\bf x})$ subject to
$\displaystyle A{\bf x}={\bf a}$ (52) $\displaystyle B{\bf x}\leq{\bf b}$
$\displaystyle{\bf x}\in{\mathcal{X}},$

where ${\bf a}\in{\mathbb{R}}^{m_{1}}$ and ${\bf b}\in{\mathbb{R}}^{m_{2}}$.
Vectors ${\bf a}$ and ${\bf b}$ can be random, deterministic (fixed), or a
mixture of both. All possible scenarios can easily be handled by the above
machinery. For the concreteness, we below sketch how the presented results
adapt if ${\bf a}$ and ${\bf b}$ are deterministic. Almost the entire
derivation presented in the previous section can be repeated line by line. In
particular, one starts by defining the optimal value of the objective in (52)
as

$\displaystyle\xi_{nh}(f,{\mathcal{X}})=\min_{{\bf x}}$ $\displaystyle f({\bf
x})$ subject to $\displaystyle A{\bf x}={\bf a}$ (53) $\displaystyle B{\bf
x}\leq{\bf b}$ $\displaystyle{\bf x}\in{\mathcal{X}},$

and then writes the follwoing analogue to (3)

$\displaystyle\xi_{nh}(f,{\mathcal{X}})$ $\displaystyle=$
$\displaystyle\min_{{\bf x}\in{\mathcal{X}}}\max_{\lambda\geq 0,\nu}f({\bf
x})+\nu^{T}A{\bf x}+\lambda^{T}B{\bf x}+\nu^{T}{\bf a}+\lambda^{T}{\bf b}$
(54) $\displaystyle=$ $\displaystyle\min_{{\bf x}\in{\mathcal{X}}}\max_{{\bf
y}\in{\mathcal{Y}}}f({\bf x})+{\bf y}^{T}G{\bf x}+{\bf y}^{T}{\bf g},$

where ${\bf g}=\begin{bmatrix}{\bf a}^{T}&{\bf b}^{T}\end{bmatrix}^{T}$. One
can then repeat the entire derivation from the previous section with very
minimal and rather obvious modifications and obtain the following corollary of
Theorem 3.

######  Corollary 2.

Assume the setup of Theorem 3 and sfl RDT frame of [61]. Set

$\displaystyle\psi_{rp}^{(nh)}$ $\displaystyle\triangleq\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf x}+{\bf y}^{T}{\bf g}\right)$ $\displaystyle\psi_{rd}^{(nh)}({\bf
p},{\bf q},{\bf c},x,y)$
$\displaystyle\triangleq\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(f({\bf x})+{\bf y}^{T}{\bf g},{\cal X},{\cal Y},{\bf
p},{\bf q},{\bf c},x,y).$

Let $\hat{{\bf p}}\triangleq\hat{{\bf p}}(x,y)$, $\hat{{\bf
q}}\triangleq\hat{{\bf q}}(x,y)$, and $\hat{{\bf c}}\triangleq\hat{{\bf
c}}(x,y)$ be the solutions of the following system

$\displaystyle\frac{d\psi_{rd}^{(nh)}({\bf p},{\bf q},{\bf c},x,y)}{d{\bf
p}}=0,\quad\frac{d\psi_{rd}^{(nh)}({\bf p},{\bf q},{\bf c},x,y)}{d{\bf
q}}=0,\quad\frac{d\psi_{rd}^{(nh)}({\bf p},{\bf q},{\bf c},x,y)}{d{\bf c}}=0.$
(56)

Then,

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}^{(nh)}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\psi_{rd}^{(nh)}(\hat{{\bf
p}}(x,y),\hat{{\bf q}}(x,y),\hat{{\bf c}}(x,y),x,y),$

where $\psi_{S,\infty}^{(nh)}(\cdot)$ is as in (3).

###### Proof.

Follows by repeating all the steps needed to show Theorem 3, with $f({\bf x})$
replaced by $f({\bf x})+{\bf y}^{T}{\bf g}$. ∎

###  3.2 A couple of well known examples

Besides further generalizations, various applications are possible as well.
Along the same lines, we, below, show how the above discussion directly
relates to several well known problems.

####  3.2.1 Random feasibility problems

As recognized in [53, 60, 58, 55], the above machinery can be used to study
not only random _optimization_ problems (rops), but also random _feasibility_
problems (rfps). If one, for example, takes $f({\bf x})=0$, then positivity
and non-positivity of the objective value in (54) ensure infeasibility and
feasibility of (52), respectively. For the concreteness, consider the
following feasibility problem (basically the non-homogenous feasibility
analogue to (1))

find $\displaystyle{\bf x}$ subject to $\displaystyle A{\bf x}={\bf a}$ (58)
$\displaystyle B{\bf x}\leq{\bf b}$ $\displaystyle{\bf x}\in{\mathcal{X}}.$

Clearly, randomness of any of $A$, $B$, ${\bf a}$, and ${\bf b}$ transforms
(58) into a random feasibility problem (rfp) which can then be studied through
the machineries of previous sections. First, one can start with (53) (the
nonhomogeneous variant of (2)) with a generic $f({\bf x})$ and arrive to (54)
(the nonhomogeneous variant of (3)). Specializing (54) to the scenario where
$f({\bf x})=0$ gives

$\displaystyle\xi_{feas}^{(0)}(f,{\mathcal{X}})=\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left({\bf
y}^{T}\begin{bmatrix}A\\\ B\end{bmatrix}{\bf x}+{\bf y}^{T}\begin{bmatrix}{\bf
a}\\\ {\bf b}\end{bmatrix}\right),$ (59)

where we recall that set ${\mathcal{Y}}$ is a collection of ${\bf y}$ such
that ${\bf y}_{i}\geq 0,m_{1}+1\leq i\leq m_{1}+m_{2}$. The observations made
earlier in the corresponding homogenous case apply here as well. In
particular, if there is an ${\bf x}$ such that $A{\bf x}={\bf a}$ and $B{\bf
x}\leq{\bf b}$, i.e., such that (58) is feasible, then the inner maximization
in (59) makes $\xi_{feas}^{(0)}(f,{\mathcal{X}})=0$. On the other hand,
nonexistence of such an ${\bf x}$ ensures that at least one of the equations
in system $A{\bf x}={\bf a}$ or at least one of the inequalities in $B{\bf
x}\leq{\bf x}$ is not satisfied and the inner maximization can trivially make
$\xi_{feas}^{(0)}(f,{\mathcal{X}})=\infty$. The insensitiveness with respect
to ${\bf y}$ scaling observed in homogenous scenario also applies. That means
that, from the feasibility point of view,
$\xi_{feas}^{(0)}(f,{\mathcal{X}})=\infty$ and
$\xi_{feas}^{(0)}(f,{\mathcal{X}})>0$ are equivalent, which allows restricting
to $\|{\bf y}\|_{2}=1$ and ultimately ensures boundedness of
$\xi_{feas}^{(0)}(f,{\mathcal{X}})$. Clearly, determining the objective of

$\displaystyle\xi_{feas}(f,{\mathcal{X}})$ $\displaystyle=$
$\displaystyle\min_{{\bf x}\in{\mathcal{X}}}\max_{{\bf
y}\in{\mathcal{Y}},\|{\bf y}\|_{2}=1}\left({\bf y}^{T}\begin{bmatrix}A\\\
B\end{bmatrix}{\bf x}+{\bf y}^{T}\begin{bmatrix}{\bf a}\\\ {\bf
b}\end{bmatrix}\right)$ (60) $\displaystyle=$ $\displaystyle\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}_{1}}\left({\bf y}^{T}G{\bf
x}+{\bf y}^{T}{\bf g}\right),$

is then critically important in characterizing the rfps from (58). For the
completeness, we, of course, recall that, as stated in (3),
${\mathcal{Y}}_{y}\triangleq\\{{\bf y}|\hskip 2.168pt\|{\bf y}\|_{2}=y,{\bf
y}\in{\mathcal{Y}}\\}$, and consequently ${\mathcal{Y}}_{1}\triangleq\\{{\bf
y}|\hskip 2.168pt\|{\bf y}\|_{2}=1,{\bf y}\in{\mathcal{Y}}\\}$.

####  3.2.2 Perceptrons

Handling random _feasibility_ problems (rfps) was also recognized in [53, 60,
58, 55] as tightly connected to studying the so-called perceptrons – the most
fundamental components of any known neural network or machine learning
systems. Various properties of perceptrons, either taken individually or as
parts of larger network systems, are of interest and the above machinery can
be utilized to thoroughly analyze all of them. Such a complete and detailed
studying is problem specific though. As is by now a standard practice
throughout the paper, in order to preserve the generic nature of the presented
considerations, we refrain from the discussions related to particular
examples. Instead, we defer specific, detail oriented, analyses to separate
papers. Nonetheless, to provide a bit of concreteness and a small prelude to
more complex discussions, we below make an exception and briefly highlight the
so-called classifying/memorizing perceptrons’ ability as an example of the the
above machinery’s utilization.

If, in (60), one chooses ${\mathcal{X}}$ as any subset of ${\mathbb{S}}^{n}$
(the $n$-dimensional unit sphere) and $m_{1}=0$ and $m_{2}=m$ (which implies
${\mathcal{Y}}_{1}={\mathbb{S}}_{+}^{m}$, where ${\mathbb{S}}_{+}^{m}$ is the
positive orthant portion of the $m$-dimensional unit sphere), then
$\xi_{feas}(f,{\mathcal{X}})=\xi_{perc}(f,{\mathcal{X}})$ can be viewed as an
objective associated with the classical, so-called, generic perceptrons. Its
role is of great importance in establishing the so-called _capacity_ of the
perceptrons when used as storage memories or classifiers. In particular, one
can define such capacity as

$\displaystyle\alpha$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{m_{1}+m_{2}}{n}=\lim_{n\rightarrow\infty}\frac{m}{n}$
$\displaystyle C_{perp}$ $\displaystyle\triangleq$
$\displaystyle\max\\{\alpha|\hskip
5.78172pt\xi_{feas}(f,{\mathcal{X}})=\xi_{feas}(f,{\mathcal{X}})>0\\}.$ (61)

Many versions of such perceptrons are of interest and have been studied
throughout the literature over the last several decades. Below we select a few
well known ones.

####  3.2.3 Spherical perceptron

Choosing additionally ${\mathcal{X}}={\mathbb{S}}^{n}$ in (60), one obtains
the associated objective of the generic _spherical_ perceptrons. A further
particular choice, ${\bf g}={\bf b}=-\kappa$ with $\kappa\geq 0$, produces the
so-called positive (universal threshold) spherical perceptrons scenario (see,
e.g., [53, 60, 58, 26, 25, 44, 16, 39, 68, 67, 14, 30, 2, 66, 46, 47, 65]), On
the other hand, the choice $\kappa\leq 0$, produces the corresponding negative
counterparts (see, e.g., [60, 58, 65, 64, 21, 20, 23, 40, 22, 24]). One then
finds

$\displaystyle C^{(sph)}_{perp}$ $\displaystyle=$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\xi^{(sph)}_{feas}\left(f,{\mathbb{S}}^{n}\right)>0\right\\}.$ (62)

In case of the positive spherical perceptrons, $C^{(sph)}_{perp}$ was
determined in [16, 39, 68, 67] for $\kappa=0$ through combinatorial geometric
considerations and, decades later, through several different mathematical
techniques and for any $\kappa\geq 0$ (see, [53, 60, 46, 47, 65]). On the
other hand, the negative case, turned out to be much harder. Talagrand in [65,
64] conjectured an upper bound which was proven as fully rigorous in [53].
Moreover, [58] lowered the upper bound showing that it is not tight but rather
strict. In a separate paper, we will present in full details all the
underlying technicalities and practical results that one obtains utilizing the
above machinery and how they ultimately compare to those of [53, 58]. Also,
various other aspects of spherical perceptrons (see, e.g., [60]) are of
interests and their full detailed treatment is deferred to separate papers as
well.

####  3.2.4 Binary perceptron

Choosing ${\mathcal{X}}=\\{-\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}}\\}^{n}$ in
(60) (i.e., choosing ${\mathcal{X}}$ as the corners of the unit norm
hypercube), one obtains the associated objective of the generic _binary_
perceptrons. A further particularization, ${\bf g}={\bf b}=-\kappa$ with
$\kappa\geq 0$ or $\kappa<0$, produces their positive or negative (universal
threshold) variants (see, e.g., [53, 26, 25, 55, 32, 27, 31, 17, 10, 38]). One
then finds

$\displaystyle C^{(bin)}_{perp}$ $\displaystyle=$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\xi^{(bin)}_{feas}\left(f,\left\\{-\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}}\right\\}^{n}\right)>0\right\\}.$
(63)

For $\kappa=0$, utilizing statistical physics based replica theory, [26, 25]
gave some initial rough (replica symmetric) $C^{(bin)}_{perp}$ estimates,
while [32] established a more refined prediction $C^{(bin)}_{perp}\approx
0.833$. A substantial progress, towards establishing the [32]’s replica
predictions as fully rigorous lower bounds, was made in [17], and later on
strengthened in [38] (see, also, [10] for related small density results and
[69] for the capacity’s sharp threshold existence).

####  3.2.5 Compressed sensing phase transitions

In [18] and a bit later on in [49, 19, 6] the so-called _weak_ compressed
sensing phase transitions (PT) were established. In particular, [49] (and a
bit earlier, [50]) established that set ${\mathcal{X}}$ of the following form
plays a critical role

${\mathbb{S}}_{weak}^{n}=\left\\{{\bf x}|\hskip 3.61371pt\sum_{i=1}^{n-k}|{\bf
x}_{i}|\leq\sum_{i=n-k+1}^{n}{\bf x}_{i},{\bf x}\in{\mathbb{S}}^{n}\right\\}.$
(64)

where $k\leq m_{1}$ and $\beta=\lim_{n\rightarrow\infty}\frac{k}{n}$ is a
constant independent of $n$. Choosing ${\bf g}=0$, $m_{1}=m$, and $m_{2}=0$ in
(60) and setting
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}=\lim_{n\rightarrow\infty}\frac{m_{1}}{n}$,
[49] determined, for any given $\beta$, the critical weak $\ell_{1}$
compressed sensing $\alpha$ phase transition

$\displaystyle\alpha^{(PT,weak)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\xi_{feas}^{(weak)}(f,{\mathbb{S}}_{weak}^{n})>0\right\\}.$ (65)

Moreover, [18] also established lower bounds on the substantially more
challenging, so-called, strong and sectional $\ell_{1}$ phase transitions.
[49] established corresponding alternative ones and [56] lifted and improved
over both [49] and [18] bounds. For example, for sectional PTs, [56, 49]
established that set ${\mathcal{X}}$ of the following form

${\mathbb{S}}_{sec}^{n}=\left\\{{\bf x}|\hskip 3.61371pt\sum_{i=1}^{n-k}|{\bf
x}_{i}|\leq\sum_{i=n-k+1}^{n}|{\bf x}_{i}|,{\bf
x}\in{\mathbb{S}}^{n}\right\\},$ (66)

plays a critical role in determining sectional $\ell_{1}$ compressed sensing
$\alpha$ phase transition

$\displaystyle\alpha^{(PT,sec)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\xi_{feas}^{(sec)}(f,{\mathbb{S}}_{sec}^{n})>0\right\\}.$ (67)

The above examples are very few illustrative ones provided to give a hint as
to how wide the range of applications of our results actually is. Further
studying of the above presented machinery in the context of each of these
applications is therefore of great interest and will be explored in separate
papers.

##  4 Summary of the fully lifted (fl) RDT formalism

Since the introduced machinery is a very powerful mathematical engine, we find
it useful to formalize its main steps in a neat way to make it more
approachable and easier to use. As the discussion from Sections 2 and 3
revealed, there are four essential steps that are the foundational components
of the entire formalism. The last three of them are clearly visible in Theorem
3 and relate to the concepts of random primal/dual and strong sfl random
duality. The first one basically incorporates algebraic characterizations of
the underlying problems that (if possible) transform them into forms on which
fl RDT is applicable. Clearly, this step is directly preceding all the other
three. A clear summary of all the four steps (precisely in the order how they
should be done) that ensure proper application of all the fl RDT concepts is
highlighted below.

Fully lifted RDT – summary of the main concepts [62, 61] __ 1. Algebraic
characterization and creation of (fully lifted) random primal __ 2.
Determining fully lifted random dual __ 3. Handling fully lifted random dual
__ 4. Ensuring strong fully lifted random duality.__

The above, of course, in a way, resembles the main principles of the plain
(non-lifted) RDT itself from [59, 49, 48, 51, 52] and the corresponding ones
of the (partially) lifted RDT from, e.g., [56, 58, 60, 54, 57]. We below
emphasize the connections and differences among all three.

###  4.1 Connections between _fully_ lifted, _partially_ lifted, and _non_
-lifted RDTs

In scenarios where $f({\bf x})$ and ${\mathcal{X}}$ are such that the strong
deterministic duality holds, i.e. such that (3) can be further rewritten as

$\displaystyle\xi(f,{\mathcal{X}})$ $\displaystyle=$ $\displaystyle\min_{{\bf
x}\in{\mathcal{X}}}\max_{\lambda\geq 0,\nu}\left(f({\bf x})+\nu^{T}A{\bf
x}+\lambda^{T}B{\bf x}\right)=\min_{{\bf x}\in{\mathcal{X}}}\max_{\lambda\geq
0,\nu}\left(f({\bf
x})+\begin{bmatrix}\nu^{T}\lambda^{T}\end{bmatrix}\begin{bmatrix}A\\\
B\end{bmatrix}{\bf x}\right)$ (68) $\displaystyle=$ $\displaystyle\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf x}\right),$ $\displaystyle=$ $\displaystyle\max_{{\bf
y}\in{\mathcal{Y}}}\min_{{\bf x}\in{\mathcal{X}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf x}\right),$

then [59, 49, 48, 51, 52] established the plain (non-lifted) RDT that can be
summarized in the following _non-lifted_ corollary of Theorem 3.

######  Corollary 3.

(Strong deterministic duality $\implies$ strong (non-lifted) random duality
[59, 49, 48, 51, 52]) Assume the setup of Theorem 3 and that $f({\bf x})$ and
${\mathcal{X}}$ are such that the strong deterministic duality from (68)
holds. Then for $r=2$, $\hat{{\bf c}}\rightarrow[1,1,0,0]$, $\hat{{\bf
p}}\rightarrow[1,1,0,0]$, and $\hat{{\bf q}}\rightarrow[1,1,0,0]$

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\psi_{rd}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},x,y)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{strong
non-lifted random duality}})},$

where $\psi_{S,\infty}(\cdot)$ is as in (3).

###### Proof.

Shown in [59, 49, 48, 51, 52], together with corresponding concentrating and
probabilistic statements. ∎

In a less technical language, [59, 49, 48, 51, 52] essentially established
that the strong deterministic duality actually implies strong non-lifted
random duality. In other words, sfl RDT simplifies to non-lifted RDT when the
strong deterministic duality is in place. On the other hand, when the strong
deterministic duality is not in place, then things need to be carefully
reconsidered. A long line of work [56, 58, 60, 54, 57] made a substantial
progress in that direction and established the following _partially lifted_
corollary of Theorem 3.

######  Corollary 4.

(Partially lifted RDT [56, 58, 60, 54, 57]) Assume the setup of Theorem 3.
Then for $r=2$, $\hat{{\bf c}}\rightarrow[1,1,{\bf c}_{2},0]$, $\hat{{\bf
p}}\rightarrow[1,1,0,0]$, and $\hat{{\bf q}}\rightarrow[1,1,0,0]$

$\displaystyle\psi_{rp}$ $\displaystyle\triangleq\min_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x})+{\bf
y}^{T}G{\bf
x}\right)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{random
primal}})}$ $\displaystyle\psi_{rd}(\hat{{\bf p}},\hat{{\bf q}},{\bf c},x,y)$
$\displaystyle=\frac{x^{2}y^{2}}{2}{\bf c}_{2}-\psi_{S,\infty}(f({\bf
x}),{\cal X},{\cal Y},\hat{{\bf p}},\hat{{\bf q}},{\bf
c},x,y)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{partially
lifted random dual}})}.$

Let $\hat{{\bf c}}=\hat{{\bf c}}(x,y)$ be the solution of the following system

$\displaystyle\frac{d\psi_{rd}(\hat{{\bf p}},\hat{{\bf q}},{\bf c},x,y)}{d{\bf
c}}=0.$ (71)

Then,

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}}{\sqrt{n}}$
$\displaystyle\geq$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\psi_{rd}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}}(x,y),x,y)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{partially
lifted random duality}})},$

where $\psi_{S,\infty}(\cdot)$ is as in (3).

###### Proof.

Shown in [56, 58, 60, 54, 57], together with corresponding concentrating and
probabilistic statements. ∎

Speaking a bit less technically, [56, 58, 60, 54, 57] established that the
partially lifted RDT produces valid lower bounds, which sometimes (say, when
the strong deterministic duality holds) are tight. Finally, carefully looking
at the above corollary (and, ultimately, the results of, e.g., [56, 58, 60,
54, 57]), one observes that the partial lifting of [56, 58, 60, 54, 57]
corresponds to a partial variant of the second level of fully lifted RDT.

##  5 Conclusion

A class of famous linearly constrained optimization problems is considered and
their behavior in a random medium is studied. These types of problems were
initially considered in [59, 49, 48, 51, 52] where foundational principles of
(non-lifted) random duality theory (RDT) were established. In particular, for
a subclass of problems where the strong deterministic duality holds, [59, 49,
48, 51, 52] proved the existence of the so-called strong (non-lifted) random
duality which then was sufficient to analytically fully characterize the
behavior of the underlying problems, even without actually solving them.

A long line of work, [56, 58, 60, 54, 57], went further and introduced a
partially lifted upgrade as a way of attacking scenarios where the non-lifted
RDT is not at its full power. Here, we further upgrade partially lifted RDT to
the _fully lifted_ (fl) one. In particular, we first recognize a connection
between the random linearly constrained optimization programs of interest here
and the recent progress made in studying bilinearly indexed random processes
in [62, 61]. As a result of such a connection, we are then able to introduce
the ultimate level of fully lifted (fl) RDT and its a complete stationarized
variant, sfl RDT.

The whole machinery is presented in a generic way and is consequently a very
powerful generic mathematical engine that can be applied in a plethora of
different scenarios. To give a hint at the range of potential applications, we
first showed that in addition to handling the random _optimization_ problems
(rops), it can also be equally successfully used in handling random
_feasibility_ problems (rfps). As concrete examples of applications, we
selected a few well known feasibility problems related to modern topics in
machine learning/neural networks and compressed sensing. These include the so-
called _spherical_ perceptrons (see, e.g., [53, 60, 58, 26, 25, 44, 16, 39,
68, 67, 14, 30, 2, 66, 46, 47]), _binary_ perceptrons (see, e.g., [53, 26, 25,
55, 32, 27, 31]), and the _sectional_ compressed sensing $\ell_{1}$ phase
transitions (see, e.g., [49, 56]).

The introduced methodology also allows various extensions and generalizations.
For example, all those discussed in [62, 61], including the ones related to
the so-called Hopfield models (see, e.g., [29, 41, 28, 42, 45, 3, 5, 63, 57]),
asymmetric Little models (see, e.g., [12, 36, 4, 13, 1, 54]) and many others,
are immediately applicable here. Moreover, many further generalizations and
applications beyond those discussed in [62, 61] are possible as well. Studying
such extensions, however, is often problem specific and requires a few
technical modifications. We will present many interesting results obtained in
these directions in separate papers.

Finally we should mention that the considered statistical context assumes the
standard Gaussianity of the primal models. These assumptions make the
presentation less cumbersome and clearer to follow. However, all presented
results can be adapted to hold for way more general statistical ensembles. The
central limit theorem and, in particular, its Lindeberg variant [35], can be
incorporated to show this. A particularly elegant approach in this regard can
be found in [15].

## References

  * [1] D. J. Amit, H. Gutfreund, and H. Sompolinsky.  Phys. Rev. A, 32:1007, 1985.
  * [2] P. Baldi and S. Venkatesh.  Number od stable points for spin-glasses and neural networks of higher orders.  Phys. Rev. Letters, 58(9):913–916, Mar. 1987.
  * [3] A. Barra, G. Genovese, and F. Guerra.  The replica symmetric approximation of the analogical neural network.  J. Stat. Physics, July 2010.
  * [4] A. Barra, G. Genovese, and F. Guerra.  Equlibrium statistical mechanics of bipartite spin systems.  Journal of Physics A: Mathematical and Theoeretical, 44(245002), 2011.
  * [5] A. Barra, G. Genovese, F. Guerra, and D. Tantari.  How glassy are neural networks.  J. Stat. Mechanics: Thery and Experiment, July 2012.
  * [6] M. Bayati and A. Montanari.  The dynamics of message passing on dense graphs, with applications to compressed sensing.  IEEE Transactions on Information Theory, 57(2), 2011.
  * [7] A. Ben-Tal and A. Nemirovski.  Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications.  Society for Industrial and Applied Mathematics, 2001.
  * [8] D. P. Bertsekas.  Nonlinear Programming.  Athena Scientific, second edition, 1999.
  * [9] D. Bertsimas and J. N. Tsitsiklis.  Introduction to Linear Optimization.  Athena Scientific, 1997.
  * [10] E. Bolthausen, S. Nakajima, N. Sun, and C. Xu.  Gardner formula for Ising perceptron models at small densities.  Proceedings of Thirty Fifth Conference on Learning Theory, PMLR, 178:1787–1911, 2022.
  * [11] S. Boyd and L. Vandenberghe.  Convex Optimization.  Cambridge University Press, 2003.
  * [12] R. Brunetti, G. Parisi, and F. Ritort.  Asymmetric Little spin glas model.  Physical Review B, 46(9), September 1992.
  * [13] S. Cabasino, E. Marinari, P. Paolucci, and G. Parisi.  Eigenstates and limit cycles in the SK model.  Journal of Physics A: Mathematical and General, 21:4201, 1988.
  * [14] S. H. Cameron.  Tech-report 60-600.  Proceedings of the bionics symposium, pages 197–212, 1960.  Wright air development division, Dayton, Ohio.
  * [15] S. Chatterjee.  A generalization of the Lindenberg principle.  The Annals of Probability, 34(6):2061–2076.
  * [16] T. Cover.  Geomretrical and statistical properties of systems of linear inequalities with applications in pattern recognition.  IEEE Transactions on Electronic Computers, (EC-14):326–334, 1965\.
  * [17] J. Ding and N. Sun.  Capacity lower bound for the Ising perceptron.  STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 816–827, 2019.
  * [18] D. Donoho.  High-dimensional centrally symmetric polytopes with neighborlines proportional to dimension.  Disc. Comput. Geometry, 35(4):617–652, 2006.
  * [19] D. Donoho, A. Maleki, and A. Montanari.  Message-passing algorithms for compressed sensing.  Proc. National Academy of Sciences, 106(45):18914–18919, Nov. 2009\.
  * [20] S. Franz, S. Hwang, and P. Urbani.  Jamming in multilayer supervised learning models.  Phys. Rev. Lett., 123(16):160602, 2019.
  * [21] S. Franz and G. Parisi.  The simplest model of jamming.  Journal of Physics A: Mathematical and Theoretical, 49(14):145001, 2016.
  * [22] S. Franz, G. Parisi, M. Sevelev, P. Urbani, and F. Zamponi.  Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems.  SciPost Physics, 2:019, 2017.
  * [23] S. Franz, A. Sclocchi, and P. Urbani.  Critical jammed phase of the linear perceptron.  Phys. Rev. Lett., 123(11):115702, 2019.
  * [24] S. Franz, A. Sclocchi, and P. Urbani.  Surfing on minima of isostatic landscapes: avalanches and unjamming transition.  SciPost Physics, 9:12, 2020.
  * [25] E. Gardner.  The space of interactions in neural networks models.  J. Phys. A: Math. Gen., 21:257–270, 1988.
  * [26] E. Gardner and B. Derrida.  Optimal storage properties of neural networks models.  J. Phys. A: Math. Gen., 21:271–284, 1988.
  * [27] H. Gutfreund and Y. Stein.  Capacity of neural networks with discrete synaptic couplings.  J. Physics A: Math. Gen, 23:2613, 1990.
  * [28] D. O. Hebb.  Organization of behavior.  New York: Wiley, 1949.
  * [29] J. J. Hopfield.  Neural networks and physical systems with emergent collective computational abilities.  Proc. Nat. Acad. Science, 79:2554, 1982.
  * [30] R. D. Joseph.  The number of orthants in $n$-space instersected by an $s$-dimensional subspace.  Tech. memo 8, project PARA, 1960.  Cornel aeronautical lab., Buffalo, N.Y.
  * [31] J. H. Kim and J. R. Roche.  Covering cubes by random half cubes with applications to biniary neural networks.  Journal of Computer and System Sciences, 56:223–252, 1998.
  * [32] W. Krauth and M. Mezard.  Storage capacity of memory networks with binary couplings.  J. Phys. France, 50:3057–3066, 1989.
  * [33] H. W. Kuhn.  Nonlinear programming. A historical view.  In R. W. Cottle and C. E. Lemke, editors, Nonlinear Programming, volume 9 of SIAM-AMS Proceedings. American Mathematical Society, 1976.
  * [34] H. W. Kuhn and A. W. Tucker.  Nonlinear programming.  In J. Neyman, editor, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 481–492. University of California Press, 1951.
  * [35] J. W. Lindeberg.  Eine neue herleitung des exponentialgesetzes in der wahrscheinlichkeitsrechnung.  Math. Z., 15:211–225, 1922.
  * [36] W. A. Little.  The existence of persistent states in the brain.  Math. Biosci., 19(1-2):101–120, 1974.
  * [37] D. G. Luenberger.  Linear and Nonlinear Programming.  Addison-Wesley, second edition, 1984.
  * [38] S. Nakajima and N. Sun.  Sharp threshold sequence and universality for Ising perceptron models.  Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 638–674, 2023.
  * [39] R. O.Winder.  Threshold logic.  Ph. D. dissertation, Princetoin University, 1962.
  * [40] G. Parisi, P. Urbani, and F. Zamponi.  Theory of Simple Glasses: Exact Solutions in Infinite Dimensions.  Cambridge University Press, 2020.
  * [41] L. Pastur and A. Figotin.  On the theory of disordered spin systems.  Theory Math. Phys., 35(403-414), 1978.
  * [42] L. Pastur, M. Shcherbina, and B. Tirozzi.  The replica-symmetric solution without the replica trick for the Hopfield model.  Journal of Statistical Physics, 74(5/6), 1994.
  * [43] R. T. Rockafellar.  Convex Analysis.  Princeton University Press, 1970.
  * [44] L. Schlafli.  Gesammelte Mathematische AbhandLungen I.  Basel, Switzerland: Verlag Birkhauser, 1950.
  * [45] M. Shcherbina and B. Tirozzi.  The free energy of a class of Hopfield models.  Journal of Statistical Physics, 72(1/2), 1993.
  * [46] M. Shcherbina and B. Tirozzi.  On the volume of the intrersection of a sphere with random half spaces.  C. R. Acad. Sci. Paris. Ser I, (334):803–806, 2002.
  * [47] M. Shcherbina and B. Tirozzi.  Rigorous solution of the Gardner problem.  Comm. on Math. Physics, (234):383–422, 2003.
  * [48] M. Stojnic.  Upper-bounding $\ell_{1}$-optimization weak thresholds.  available online at http://arxiv.org/abs/1303.7289.
  * [49] M. Stojnic.  Various thresholds for $\ell_{1}$-optimization in compressed sensing.  available online at http://arxiv.org/abs/0907.3666.
  * [50] M. Stojnic.  A simple performance analysis of $\ell_{1}$-optimization in compressed sensing.  ICASSP, International Conference on Acoustics, Signal and Speech Processing, April 2009.
  * [51] M. Stojnic.  Block-length dependent thresholds for $\ell_{2}/\ell_{1}$-optimization in block-sparse compressed sensing.  ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing, pages 3918–3921, 14-19 March 2010.  Dallas, TX.
  * [52] M. Stojnic.  $\ell_{1}$ optimization and its various thresholds in compressed sensing.  ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing, pages 3910–3913, 14-19 March 2010.  Dallas, TX.
  * [53] M. Stojnic.  Another look at the Gardner problem.  2013\.  available online at http://arxiv.org/abs/1306.3979.
  * [54] M. Stojnic.  Asymmetric Little model and its ground state energies.  2013\.  available online at http://arxiv.org/abs/1306.3978.
  * [55] M. Stojnic.  Discrete perceptrons.  2013\.  available online at http://arxiv.org/abs/1303.4375.
  * [56] M. Stojnic.  Lifting $\ell_{1}$-optimization strong and sectional thresholds.  2013\.  available online at http://arxiv.org/abs/1306.3770.
  * [57] M. Stojnic.  Lifting/lowering Hopfield models ground state energies.  2013\.  available online at http://arxiv.org/abs/1306.3975.
  * [58] M. Stojnic.  Negative spherical perceptron.  2013\.  available online at http://arxiv.org/abs/1306.3980.
  * [59] M. Stojnic.  Regularly random duality.  2013\.  available online at http://arxiv.org/abs/1303.7295.
  * [60] M. Stojnic.  Spherical perceptron as a storage memory with limited errors.  2013\.  available online at http://arxiv.org/abs/1306.3809.
  * [61] M. Stojnic.  Bilinearly indexed random processes – _stationarization_ of fully lifted interpolation.  2023\.  available online at arxiv.
  * [62] M. Stojnic.  Fully lifted interpolating comparisons of bilinearly indexed random processes.  2023\.  available online at arxiv.
  * [63] M. Talagrand.  Rigorous results for the Hopfield model with many patterns.  Prob. theory and related fields, 110:177–276, 1998.
  * [64] M. Talagrand.  Mean field models and spin glasse: Volume II.  A series of modern surveys in mathematics 55, Springer-Verlag, Berlin Heidelberg, 2011.
  * [65] M. Talagrand.  Mean field models and spin glasses: Volume I.  A series of modern surveys in mathematics 54, Springer-Verlag, Berlin Heidelberg, 2011.
  * [66] S. Venkatesh.  Epsilon capacity of neural networks.  Proc. Conf. on Neural Networks for Computing, Snowbird, UT, 1986\.
  * [67] J. G. Wendel.  A problem in geometric probablity.  Mathematics Scandinavia, 11:109–111, 1962.
  * [68] R. O. Winder.  Single stage threshold logic.  Switching circuit theory and logical design, pages 321–332, Sep. 1961.  AIEE Special publications S-134.
  * [69] C. Xu.  Sharp threshold for the Ising perceptron model.  Ann. Probab., 43(5):2399–2415, 2021.