text:
\begin{document}
\bibliographystyle{harvard}

\title{Central Limit Theorem and convergence to stable laws in Mallows
distance}
\author{Oliver Johnson and Richard Samworth \\
Statistical Laboratory,
University of Cambridge, \\
Wilberforce Road, Cambridge, CB3 0WB, UK. }
\date{\today}
\maketitle

Running Title: CLT and stable convergence in Mallows distance

Keywords: Central Limit Theorem, Mallows distance, probability metric,
stable law, Wasserstein distance

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{condition}{Condition}
\newtheorem{main}{Theorem}
\newtheorem{assumption}[theorem]{Assumption}
\setlength{\parskip}{\parsep}

\def \outlineby #1#2#3{\vbox{\hrule\hbox{\vrule\kern #1
\vbox{\kern #2 #3\kern #2}\kern #1\vrule}\hrule}}
\def \endbox {\outlineby{4pt}{4pt}{}}
\newenvironment{proof}
{\noindent{\bf Proof\ }}{{\hfill \endbox
}\par\vskip2\parsep}
\newenvironment{pfof}[2]{\removelastskip\vspace{6pt}\noindent
 {\it Proof  #1.}~\rm#2}{\par\vspace{6pt}}

\hfuzz20pt

\newcommand{\Section}[1]{\setcounter{equation}{0} \section{#1}}
\newcommand{\var}{{\rm{Var\,}}}
\newcommand{\cov}{{\rm{Cov\,}}}
\newcommand{\tends}{\rightarrow \infty}
\newcommand{\C}{{\mathcal{C}}}
\newcommand{\ep}{{\mathbb {E}}}
\newcommand{\pr}{{\mathbb {P}}}
\newcommand{\sgn}{{\rm{sgn}}}
\newcommand{\re}{{\mathbb {R}}}
\newcommand{\I}{\mathbbm{1}}
\newcommand{\vc}[1]{{\bf {#1}}}
\newcommand{\conpr}{\buildrel{\pr}\over\longrightarrow}
\newcommand{\cond}{\stackrel{d}{\rightarrow}}
\newcommand{\condo}{\stackrel{d^{\circ}}{\rightarrow}}
\newcommand{\q}{{\cal{Q}}}
\newcommand{\blah}[1]{}

\begin{abstract}
We give a new proof of the classical Central Limit Theorem, in
the Mallows ($L^r$-Wasserstein) distance. Our proof is elementary in the
sense that it does not require complex analysis, but rather makes use of
a simple subadditive inequality related to this metric. The key is to
analyse the case where equality holds. We provide some results concerning
rates of convergence. We also consider convergence to stable distributions,
and obtain a bound on the rate of such convergence.
\end{abstract}

\section{Introduction and main results} \label{sec:intro}

The spirit of the Central  Limit Theorem, that  normalised sums of
independent random variables converge to a normal distribution, can be
understood  in   different  senses,  according   to  the distance
used.
For example, in addition to the standard Central Limit Theorem
in the sense of weak convergence, we
mention the proofs in \citeasnoun{prohorov} of $L^1$ convergence of densities,
in \citeasnoun{gnedenko} of $L^{\infty}$ convergence
of densities, in \citeasnoun{barron} of convergence in
relative entropy and in \citeasnoun{shimizu} and
\citeasnoun{johnson5} of convergence in Fisher information.

In this  paper we consider the Central
Limit Theorem with respect to the Mallows distance and
prove convergence to stable laws in the infinite
variance setting. We study the rates of convergence in both cases.

\begin{definition} \label{def:mallows}
For any $r > 0$, we define the
Mallows  $r$-distance between
probability distribution functions  $F_X$ and $F_Y$  as
$$ d_r(F_X,F_Y)  = \left(  \inf_{(X,Y)} \ep |  X - Y  |^r \right)^{1/r},$$
where the  infimum is  taken over pairs $(X,Y)$
whose marginal distribution functions are $F_X$ and
$F_Y$ respectively, and may be infinite.
Where it causes no confusion, we write $d_r(X,Y)$ for $d_r(F_X,F_Y)$.
\end{definition}

Define
$\mathcal{F}_r$ to be the set of distribution functions $F$ such
that $\int |x|^r dF(x) < \infty$. \citeasnoun{bickel} show that
for $r \geq 1$, $d_r$ is a metric on $\mathcal{F}_r$.
If $r < 1$, then $d_r^r$ is a metric on
$\mathcal{F}_r$. In considering stable
convergence, we shall also be concerned with the case where the absolute
$r$th moments are not finite.

Throughout the paper, we write $Z_{\mu,\sigma^2}$ for a $N(\mu,\sigma^2)$
random variable, $Z_{\sigma^2}$ for a $N(0,\sigma^2)$ random variable,
and $\Phi_{\mu,\sigma^2}$ and $\Phi_{\sigma^2}$ for their respective
distribution functions.
We establish the following main theorems:

\begin{theorem} \label{thm:main}
Let $X_1, X_2, \ldots $ be independent and identically distributed random
variables with mean zero and finite variance $\sigma^2 > 0$, and let
$S_n = (X_1 + \ldots + X_n)/\sqrt{n}$.  Then
$$ \lim_{n \tends} d_2(S_n, Z_{\sigma^2}) = 0.$$
\end{theorem}

Moreover, Theorem \ref{thm:mainr} shows that for any $r \geq 2$,
if $d_r(X_i, Z_{\sigma^2}) < \infty$,
then $ \lim_{n \tends} d_r(S_n, Z_{\sigma^2}) = 0.$
Theorem \ref{thm:main}
implies the standard Central Limit Theorem in the sense
of weak convergence \cite[Lemma 8.3]{bickel}.

\begin{theorem} \label{thm:mainstab} Fix $\alpha \in (0,2)$,
and let $X_1, X_2, \ldots $ be independent random
variables (where $\ep X_i =0$, if $\alpha > 1$), and
$S_n = (X_1 + \ldots + X_n)/n^{1/\alpha}$.  If there exists an
$\alpha$-stable random variable $Y$ such that
$\sup_i d_{\beta}(X_i, Y) < \infty$ for some $\beta \in (\alpha,2]$,
then $\lim_{n \tends} d_{\beta}(S_n, Y) = 0$. In fact
$$d_{\beta}(S_n, Y) \leq \frac{2^{1/\beta}}{n^{1/\alpha}}
\left( \sum_{i=1}^n d^{\beta}_{\beta}(X_i,Y) \right)^{1/\beta},$$
so in the identically distributed
case the rate of convergence is $O(n^{1/\beta - 1/\alpha})$.
\end{theorem}

See also Rachev and R{\"u}schendorf (1992,1994), who obtain
similar results using different techniques in the case of identically
distributed $X_i$  and strictly symmetric $Y$.
In Lemma \ref{lem:dsna} we exhibit a large class ${\cal C}_K$ of
distribution functions $F_X$
for which $d_{\beta}(X,Y) \leq K$,
so the theorem can be applied.

Theorem \ref{thm:main} follows by understanding the subadditivity of
$d_2^2(S_n, Z_{\sigma^2})$ (see Equation (\ref{eq:sub})). We consider
the powers-of-two subsequence $T_k = S_{2^k}$, and
use R\'{e}nyi's method, introduced in
\citeasnoun{renyi2} to provide a proof of convergence to equilibrium of Markov
chains; see also \citeasnoun{kendall}. This technique was also
used in \citeasnoun{csiszar2} to show
convergence to Haar measure for convolutions of measures on compact groups,
and in \citeasnoun{shimizu} to show convergence of Fisher information
in the Central Limit
Theorem. The method has four stages:

\begin{enumerate}
\item{Consider independent and identically distributed random variables $X_1$
and $X_2$ with mean $\mu$ and variance $\sigma^2 > 0$, and write $D(X)$ for
$d_2^2(X, Z_{\mu,\sigma^2})$.
In Proposition \ref{prop:iff}, we observe that
\begin{equation} \label{eq:subadd}
D \left( \frac{ X_1 + X_2}{\sqrt{2}} \right) \leq D(X_1),
\end{equation}
with equality if and only if $X_1,X_2 \sim Z_{\mu,\sigma^2}$.
Hence $D(T_k)$ is decreasing and bounded below, so converges to some $D$.}
\item{In Proposition \ref{prop:rich}, we use a compactness argument
to show that there exists a strictly increasing sequence $k_r$ and a random
variable $T$ such that
$$ \lim_{r \tends} D(T_{k_r}) = D(T).$$
Further,
$$\lim_{r \tends} D(T_{k_r+1}) = \lim_{r \tends} D \left(
\frac{T_{k_r} + T_{k_r}'}{\sqrt{2}} \right) =
D \left( \frac{T + T'}{\sqrt{2}} \right),$$
where the $T'_{k_r}$ and $T'$ are independent copies of $T_{k_r}$ and $T$
respectively.}
\item{We combine these two results: since $D(T_{k_r})$ and
$D(T_{k_r +1})$ are both subsequences of the convergent subsequence $D(T_k)$,
they must have a common limit. That is,
$$ D = D(T) = D \left( \frac{ T + T'}{\sqrt{2}} \right),$$
so by the condition for equality in Proposition \ref{prop:iff}, we
deduce that $T \sim N(0,\sigma^2)$ and $D =0$.}
\item{Proposition \ref{prop:iff} implies the standard subadditive relation
$$ (m+n) D(S_{m+n}) \leq m D(S_m) + n D(S_n).$$
Now Theorem 6.6.1 of  \citeasnoun{hille}
implies that $D(S_n)$ converges to $\inf_n D(S_n) = 0$.}
\end{enumerate}

The proof of Theorem \ref{thm:mainstab} is given in Section \ref{sec:stable}.

\section{Subadditivity of Mallows distance}

The Mallows distance and related metrics originated
with a transportation problem posed by Monge in 1781
\cite[pp.329--330]{rachev2,dudley}.
Kantorovich generalised this problem, and
considered the distance obtained by minimising $\ep c(X,Y)$, for a
general metric $c$ (known as the cost function), over all joint
distributions of pairs
$(X,Y)$ with fixed marginals.  This distance is also known
as the Wasserstein metric. \citeasnoun{rachev2} reviews
applications to differential geometry,
infinite-dimensional linear programming and information theory,
among many others.
\citeasnoun{mallows}
focused on the metric which we have called $d_2$, while $d_1$
is sometimes called the Gini index.

In Lemma \ref{lem:covvalue} below,  we review  the existence and
uniqueness of the construction which
attains the infimum in Definition \ref{def:mallows}, using the concept
of a quasi-monotone function.

\begin{definition}
A function $k: \re^2 \rightarrow \re$
induces a signed measure $\mu_k$ on $\re^2$ given by
$$ \mu_k \left\{ (x, x'] \times (y,y'] \right\}
= k(x,y) + k(x',y') - k(x,y') - k(x',y).$$
We say that $k$ is quasi-monotone if $\mu_k$ is a non-negative measure.
\end{definition}

The function $k(x,y) = -|x-y|^r$ is quasi-monotone for $r \geq 1$,
and if $r > 1$ then the measure $\mu_k$ is absolutely
continuous, with a density
which is  positive Lebesgue almost everywhere.
\citeasnoun[Corollary 2.1]{tchen} gives  the following
result, a two-dimensional version of integration by parts.

\begin{lemma} \label{lem:intprt}
Let $k(x,y)$ be a quasi-monotone function and
let $H_1(x,y)$ and $H_2(x,y)$ be distribution
functions with the same marginals, where $H_1(x,y) \leq H_2(x,y)$
for all $x,y$. Suppose there exists an $H_1$- and $H_2$- integrable
function $g(x,y)$, bounded on compact sets, such that
$k(x^B,y^B) \leq g(x,y)$, where $x^B = (-B) \vee x \wedge B$.
Then
$$ \int k(x,y) dH_2(x,y) - \int k(x,y) dH_1(x,y)
= \int \left\{ H^{-}_2(x,y) - H^{-}_1(x,y) \right\} d\mu_k(x,y).$$
Here $H^{-}_i(x,y) = \pr( X < x, Y < y)$, where $(X,Y)$ have joint
distribution function $H_i$.
\end{lemma}

\begin{lemma} \label{lem:covvalue}
For $r \geq 1$, consider the joint
distribution of pairs $(X,Y)$ where $X$ and $Y$ have fixed marginals
$F_X$ and $F_Y$, both in $\mathcal{F}_r$. Then
\begin{equation} \label{eq:covmax} \ep |X-Y|^r \geq \ep |X^* - Y^*|^r,
\end{equation}
where $X^* = F_X^{-1}(U)$, $Y^* = F_Y^{-1}(U)$ and $U \sim U(0,1)$.
For $r > 1$, equality is attained only if $(X,Y) \sim (X^*,Y^*)$.
\end{lemma}
\begin{proof} Observe, as in
\citeasnoun{frechet}, that if the random variables $X,Y$ have fixed
marginals $F_X$ and $F_Y$, then
\begin{equation} \label{eq:kupper}
\pr (X \leq x, Y \leq y) \leq H_+(x,y),\end{equation}
where $H_+(x,y) = \min(F_X(x),
F_Y(y))$. This bound is achieved by taking $U \sim
U(0,1)$ and setting $X^* = F_X^{-1}(U), Y^* = F_Y^{-1}(U)$.

Thus, by Lemma \ref{lem:intprt}, with $k(x,y) = -|x-y|^r$, for $r \geq 1$,
and taking $H_1(x,y) = \pr(X \leq x, Y \leq y)$ and $H_2 = H_+$, we
deduce that
$$ \ep |X-Y|^r - \ep |X^*-Y^*|^r = \int \left\{ H_+(x,y) - H_1(x,y) \right\}
d\mu_k(x,y) \geq 0,$$
so $(X^*,Y^*)$ achieves the infimum in the definition of the Wasserstein
distance.

Finally, since taking $r >1$ implies that
the measure $\mu_k$ has a strictly positive density with respect to Lebesgue
measure,
we can only have equality in (\ref{eq:covmax}) if $\pr(X \leq x, Y \leq y)
= \min \{ F_X(x), F_Y(y) \}$ Lebesgue almost everywhere.
But the joint distribution function is right-continuous,
so this condition determines the value of $\pr(X \leq x, Y \leq y)$
everywhere.
\end{proof}

Using the construction in Lemma \ref{lem:covvalue}, \citeasnoun{bickel}
establish that if
$X_1$ and $X_2$ are independent and $Y_1$ and $Y_2$ are independent, then
\begin{equation} \label{eq:sub}
d_2^2(X_1 + X_2, Y_1 + Y_2) \leq d_2^2(X_1, Y_1) + d_2^2(X_2, Y_2).
\end{equation}

Similar subadditive expressions arise  in the proof of convergence of
Fisher information  in \citeasnoun{johnson5}. By  focusing on the
case $r=2$ in Definition \ref{def:mallows}, and by using the theory
of $L^2$ spaces and projections,  we establish parallels with the
Fisher information argument.

We prove Equation (\ref{eq:sub}) below, and further consider the
case of equality in this relation.
\citeasnoun[p.504]{major2} gives an equivalent construction to that
given in Lemma \ref{lem:covvalue}.
If  $F_Y$ is a continuous distribution function, then $F_Y(Y) \sim U(0,1)$,
so we generate $Y^* \sim F_Y$ and take $X^* = F_X^{-1} \circ F_Y(Y^*)$.
Recall that if $\ep X = \mu$ and $\var X = \sigma^2$, we
write $D(X)$ for $d_2^2(X,Z_{\mu,\sigma^2})$.

\begin{proposition} \label{prop:iff} If $X_1$, $X_2$ are independent,
with finite
variances $\sigma_1^2, \sigma_2^2 > 0$, then for any $t \in (0,1)$,
$$ D \left( \sqrt{t} X_1 + \sqrt{1-t} X_2 \right) \leq
t D(X_1) + (1-t) D(X_2), $$
with equality if and only if
$X_1$ and $X_2$ are normal.\end{proposition}
\begin{proof} We consider bounding $D(X_1 + X_2)$ for independent $X_1$
and $X_2$ with mean zero, since the general result follows on
translation and rescaling.

We generate independent $Y_i^* \sim N(0,\sigma^2_i)$, and
take $X_i^* = F_{X_i}^{-1}\circ \Phi_{\sigma^2_i}(Y_i^*) = h_i(Y_i^*)$, say,
for  $i=1,2$.
Further, writing $\sigma^2 = \sigma_1^2 + \sigma^2_2$,
we define $Y^* = Y^*_1 + Y_2^*$ and set
$X^* = F_{X_1 + X_2}^{-1} \circ \Phi_{\sigma^2}(Y^*_1 + Y^*_2) =
h(Y_1^* + Y_2^*)$, say. Then
\begin{eqnarray*}
d_2^2( X_1 + X_2, Y_1 + Y_2) & = & \ep ( X^* - Y^*)^2 \\
& \leq & \ep (X_1^* + X_2^* - Y_1^* - Y_2^*)^2 \\
& = & \ep (X_1^* - Y_1^*)^2 + \ep (X_2^* - Y_2^*)^2 \\
& = & d_2^2(X_1, Y_1) + d_2^2(X_2, Y_2). \end{eqnarray*}

Equality holds if and only if
$(X_1^* + X_2^*,Y_1^* + Y_2^*)$ has the same distribution as $(X^*,Y^*)$.
By our construction of $Y^* = Y_1^* + Y_2^*$, this means that
$(X_1^*+ X_2^*, Y_1^* + Y_2^*)$ has the same distribution as
$(X^*,Y^*_1+Y_2^*)$, so
$\pr \{ X_1^* + X_2^* = h(Y^*_1 + Y^*_2) \} = \pr \{
X^* = h(Y^*_1+Y_2^*) \} = 1$.
Thus, if equality holds, then
\begin{equation} \label{eq:linear}
h_1(Y_1^*) + h_2(Y_2^*) = h(Y_1^* + Y_2^*) \mbox{ almost surely}.
\end{equation}
\citeasnoun{brown} and \citeasnoun{johnson5},
showed that equality holds in Equation (\ref{eq:linear})
if and only if $h, h_1, h_2$ are linear. In particular, Proposition 2.1 of
\cite{johnson5} implies that there exist
constants $a_i$ and $b_i$ such that
\begin{eqnarray} \label{eq:brown}
\lefteqn{\ep \{ h(Y^*_1 + Y^*_2) - h_1(Y^*_1) - h_2(Y^*_2)\}^2} \nonumber \\
& \geq &  \frac{2\sigma_1^2 \sigma_2^2}{(\sigma_1^2 + \sigma_2^2)^2}
\left[ \ep \{h_1(Y^*_1) - a_1 Y^*_1 - b_1 \}^2 +
\ep \{ h_2(Y^*_2) - a_2 Y^*_2 - b_2 \}^2 \right]. \end{eqnarray}
Hence, if Equation (\ref{eq:linear})
holds, then $h_i(u) = a_i u + b_i$ almost everywhere. Since $Y_i^*$ and
$X_i^*$ have the same mean and variance, it follows that $a_i=1$, $b_i=0$.
Hence $h_1(u) = h_2(u) = u$ and $X_i^* = Y_i^*$.
\end{proof}

Recall that $T_k = S_{2^k}$, where $S_n = (X_1 + \ldots + X_n)/\sqrt{n}$
is a normalised sum of independent and identically distributed
 random variables of mean zero and finite
variance $\sigma^2$.

\begin{proposition} \label{prop:rich}
There exists a strictly increasing sequence $(k_r) \in
\mathbb{N}$ and a random variable $T$ such that
\[
\lim_{r \rightarrow \infty} D(T_{k_r}) = D(T).
\]
If $T_{k_r}'$ and $T'$ are independent copies of $T_{k_r}$ and $T$
respectively, then
\[
\lim_{r \rightarrow \infty} D(T_{k_r+1}) =
\lim_{r \rightarrow \infty} D\biggl(\frac{T_{k_r} + T_{k_r}'}{\sqrt{2}}\biggr)
= D\biggl(\frac{T + T'}{\sqrt{2}}\biggr).
\]
\end{proposition}
\begin{proof}
Since $\var(T_k) = 1$ for all $k$, the sequence $(T_k)$ is tight.
Therefore, by Prohorov's theorem, there exists a strictly increasing
sequence $(k_r)$ and a random variable $T$ such that
\begin{equation}
\label{weak}
T_{k_r} \stackrel{d}{\rightarrow} T
\end{equation}
as $r \rightarrow \infty$.  Moreover, the
proof of Lemma~5.2 of \citeasnoun{brown} shows that the sequence $(T_{k_r}^2)$
is uniformly integrable.
But this, combined with Equation (\ref{weak})
implies that $\lim_{r \tends} d_2(T_{k_r},T) = 0$
\cite[Lemma 8.3(b)]{bickel}.  Hence
\[
D(T_{k_r}) = d_2^2(T_{k_r},Z_{\sigma^2}) \leq \{d_2(T_{k_r},T) +
d_2(T,Z_{\sigma^2})\}^2 \rightarrow d_2^2(T,Z_{\sigma^2}) = D(T)
\]
as $r \rightarrow \infty$.  Similarly, $d_2^2(T,Z_{\sigma^2}) \leq
\{d_2(T,T_{k_r}) + d_2(T_{k_r},Z_{\sigma^2})\}^2$, yielding the
opposite inequality.  This proves the first part of the proposition.

For the second part, it suffices to observe that $T_{k_r} + T_{k_r}'
\stackrel{d}{\rightarrow} T + T'$ as $r \rightarrow \infty$, and
$\ep (T_{k_r} + T_{k_r}')^2 \rightarrow \ep(T + T')^2 $,
and then use the same argument as in the first part of the proposition.
\end{proof}

Combining Propositions \ref{prop:iff} and \ref{prop:rich}, as described
in Section \ref{sec:intro}, the proof of Theorem \ref{thm:main} is now
complete.

\section{Convergence of $d_r$ for general $r$}

The subadditive inequality (\ref{eq:sub}) arises in part
from a moment inequality; that is, if
$X_1$ and $X_2$ are independent with mean zero,
then $\ep |X_1 + X_2|^r \leq \ep |X_1|^r + \ep |X_2|^r$, for $r=2$. Similar
results imply that for $r \geq 2$, we have
$\lim_{n \tends} d_r(S_n, Z_{\sigma^2}) = 0$.
First, we prove the following lemma:

\begin{lemma} \label{lem:rsub}
Consider independent random variables $V_1, V_2, \ldots$ and
$W_1, W_2, \ldots$, where for some $r \geq 2$ and for all $i$,
$\ep |V_i|^r < \infty$ and $\ep |W_i|^r < \infty$.
Then for any $m$, there exists
a constant $c(r)$ such that
\begin{eqnarray*}
\lefteqn{d_r^r \left( V_1 + \ldots + V_m, W_1 + \ldots + W_m \right) }\\
& \leq & c(r) \biggl\{ \sum_{i=1}^m d_r^r(V_i, W_i) +
\biggl( \sum_{i=1}^m d_2^2(V_i, W_i) \biggr)^{r/2} \biggr\}.
\end{eqnarray*}
\end{lemma}
\begin{proof}
We consider independent $U_i \sim U(0,1)$, and set
$V_i^* = F_{V}^{-1}(U_i)$ and $W_i^* = F_{W}^{-1}(U_i)$. Then
\begin{eqnarray*}
\lefteqn{d_r^r(V_1 + \ldots + V_m, W_1 + \ldots + W_m) } \\
& \leq & \ep \left| \sum_{i=1}^m (V_i^* - W_i^*) \right|^r \nonumber \\
& \leq & c(r) \biggl\{ \sum_{i=1}^m \ep \left| V_i^* - W_i^* \right|^r
+ \biggl( \sum_{i=1}^m \ep \left| V_i^* - W_i^* \right|^2 \biggr)^{r/2}
\biggr\} \end{eqnarray*}
as required. This final line is an application of Rosenthal's inequality
\cite[Theorem 2.9]{petrov} to the sequence $(V_i^* - W_i^*)$.
\end{proof}

Using Lemma \ref{lem:rsub}, we establish the following theorem.

\begin{theorem} \label{thm:mainr}
Let $X_1, X_2, \ldots $ be
independent and identically distributed random variables
with mean zero, variance $\sigma^2 > 0$ and
$\ep |X_1|^r < \infty$ for some $r \geq 2$. If
$S_n = (X_1 + \ldots + X_n)/\sqrt{n}$, then
$$ \lim_{n \tends} d_r(S_n, Z_{\sigma^2}) = 0.$$
\end{theorem}
\begin{proof}
Theorem \ref{thm:main} covers
the case of $r=2$, so need only consider $r >2$.
We use a scaled version of
Lemma \ref{lem:rsub} twice. First, we use $V_i = X_i$,
$W_i \sim N(0, \sigma^2)$ and $m = n$, in order to deduce that, by monotonicity
of the $r$-norms:
\begin{eqnarray*}
 d_r^r \left( S_n, Z_{\sigma^2} \right)
& \leq &
c(r) \left\{ n^{1 - r/2} d_r^r(X_1, Z_{\sigma^2})
+ d_2^2(X_1, Z_{\sigma^2})^{r/2} \right\} \\
& \leq & c(r) \left( n^{1 - r/2} +1 \right) d_r^r(X_1, Z_{\sigma^2}),
\end{eqnarray*}
so that $d_r^r \left( S_n, Z_{\sigma^2} \right)$ is uniformly bounded in $n$,
by $K$, say.
Then, for general $n$, define $N = \lceil \sqrt{n} \rceil$, take
$m = \lceil n/N \rceil$,
and $u = n - (m-1)N \leq N$. In Lemma \ref{lem:rsub}, take
\begin{eqnarray*}
V_i & = & X_{(i-1)N + 1} + \ldots + X_{i N},
\mbox{ for $i = 1, \ldots, m-1$} \\
V_m & = & X_{(m-1)N + 1} + \ldots + X_{n},
\end{eqnarray*}
and $W_i \sim N(0, N \sigma^2)$ for $i = 1, \ldots, m-1$,
$W_m \sim N(0, u \sigma^2)$ independently.

Now the uniform bound above gives, on rescaling,
$$d_{r}^r(V_i,W_i) = N^{r/2} d_r^r(S_N, Z_{\sigma^2})
\leq N^{r/2} K \mbox{ for $i = 1, \ldots m-1$} $$ and
$d_r^r(V_m,W_m) = u^{r/2} d_r^r(S_u, Z_{\sigma^2}) \leq N^{r/2} K$.
Further $d_{2}^2(V_i,W_i) = N d_2^2(S_N, Z_{\sigma^2})$
 for $i = 1, \ldots m-1$ and
$d_2^2(V_m,W_m) = u d_2^2(S_u, Z_{\sigma^2}) \leq N d_2^2(S_1, Z_{\sigma^2})$.
Hence, using Lemma \ref{lem:rsub} again, we obtain
\begin{eqnarray*}
\lefteqn{d_r^r \left( S_{n}, Z_{\sigma^2} \right) } \nonumber \\
& = & \frac{1}{n^{r/2}}
d_r^r \left( V_1 + \ldots + V_m, W_1 + \ldots + W_m \right) \nonumber \\
& \leq &
\frac{c(r)}{n^{r/2}} \left\{ \sum_{i=1}^m d_r^r(V_i, W_i) +
\left( \sum_{i=1}^m d_2^2(V_i, W_i) \right)^{r/2} \right\} \nonumber \\
& \leq &
c(r) \left\{ m K \frac{N^{r/2}}{n^{r/2}} +
\left( \frac{N(m-1)}{n} d_2^2(S_N, Z_{\sigma^2}) + \frac{N}{n}
d_2^2(S_1, Z_{\sigma^2}) \right)^{r/2} \right\} \nonumber \\
& \leq &
c(r) \left\{ \frac{m K}{(m-1)^{r/2}} +
\left( d_2^2(S_N, Z_{\sigma^2}) + \frac{1}{m-1}
d_2^2(S_1, Z_{\sigma^2}) \right)^{r/2} \right\}.
\label{eq:toconv}
\end{eqnarray*}
This
converges to zero since $\lim_{n \tends} d_2(S_N, Z_{\sigma^2}) = 0$.
\end{proof}

\section{Strengthening subadditivity}

Under certain conditions, we obtain a rate for the convergence in
Theorem \ref{thm:main}.
Equation (\ref{eq:subadd})  shows that
$D(T_{k})$  is decreasing.  Since  $D(T_{k})$ is  bounded
below, the difference  sequence $D(T_k) - D(T_{k+1})$
converges  to zero,  As in  \citeasnoun{johnson5}  we examine
this difference sequence, to show  that its convergence
implies  convergence of $D(T_{k})$ to zero.

Further, in the  spirit of \citeasnoun{johnson5},
we hope  that if the difference
sequence  is small,  then  equality  `nearly'  holds in Equation
(\ref{eq:linear}),  and so  the
functions $h,  h_1, h_2$ are `nearly'  linear.
This implies that if $\cov(X,Y)$ is
close to its  maximum, then $X$ is be close to  $h(Y)$ in the $L^2$ sense.

Following \citeasnoun{delbarrio},
we define a new distance quantity
$ D^*(X) = \inf_{m,s^2}
d_2^2(X, Z_{m,s^2}). $
Notice that $D(X) = 2 \sigma^2 - 2 \sigma k \leq 2 \sigma^2$, where
$k = \int_0^1 F_X^{-1}(x) \Phi^{-1}(x) dx$.
This follows since $F_X^{-1}$ and $\Phi^{-1}$ are increasing functions, so
$k \geq 0$ by Chebyshev's rearrangement lemma.
Using results of \citeasnoun{delbarrio}, it follows that
$$ D^*(X) = \sigma^2 - k^2 = D(X) - \frac{D(X)^2}{4 \sigma^2},$$
and convergence of $D(S_n)$ to zero is
equivalent to convergence of $D^*(S_n)$ to zero.

\begin{proposition} \label{prop:double}
Let $X_1$ and $X_2$ be independent and identically distributed
random variables with mean $\mu$, variance $\sigma^2 > 0$ and
densities (with respect to Lebesgue measure).
Defining $g(u) =  \Phi_{\mu,\sigma^2}^{-1} \circ
F_{(X_1 + X_2)/\sqrt{2}}(u)$, if the
derivative $g'(u) \geq c$ for all $u$ then
$$ D \left( \frac{ X_1 + X_2}{\sqrt{2}} \right)
\leq \left( 1 - \frac{c}{2} \right) D(X_1) + \frac{c D(X_1)^2}{8 \sigma^2}
\leq
\left( 1 - \frac{c}{4} \right) D(X_1).$$
\end{proposition}
\begin{proof} As before, translation invariance allows us to take $\ep X_i
=0$.
For random variables $X,Y$,
we    consider      the     difference     term     Equation
(\ref{eq:kupper}) and write $g(u) = F_Y^{-1} \circ F_X(u)$, and $h(u)
= g^{-1}(u)$. The function $k(x,y) = -\{ x - h(y) \}^2$ is
quasi-monotone and induces the measure $d\mu_k(x,y) = 2 h'(y) dx dy$. Taking
$H_1(x,y) = \pr(X \leq x, Y \leq y)$ and $H_2(x,y) = \min \{ F_X(x),
F_Y(y) \}$ in
Lemma \ref{lem:intprt} implies that
$$ \ep \{X - h(Y) \}^2 = 2 \int h'(y) \left\{ H_2(x,y) - H_1(x,y) \right\}
dx dy,$$
since $\ep \{X^* - h(Y^*) \}^2 = 0$. By assumption $h'(y) \leq 1/c$,
so
$$ \ep \{ X - h(Y) \}^2 \leq \frac{2}{c} \left\{ \cov(X^*, Y^*) -
\cov(X,Y) \right)\}.$$

Again take $Y_1^*,Y_2^*$ independent $N(0,\sigma^2)$ and set
$X_i^* = F_{X_i}^{-1} \circ F_{Y_i}(Y_i^*) = h_i(Y_i^*)$. Then define
$Y^* = Y_1^* + Y_2^*$ and take $X^* = F_{X_1 + X_2}^{-1} \circ F_{Y_1 + Y_2}
(Y^*)$. Then there exist $a$ and $b$ such that
\begin{eqnarray*}
\lefteqn{d_2^2(X_1, Y_1) + d_2^2(X_2, Y_2) - d_2^2(X_1 + X_2, Y_1 + Y_2)} \\
& = & \ep(X_1^* + X_2^* - Y_1^* - Y_2^*)^2 - \ep(X^* - Y^*)^2 \\
& = & 2 \cov(X^*,Y^*) - 2 \cov(X_1^* + X_2^*,Y_1^* + Y_2^*) \\
& \geq & c \ep \{ X_1^* + X_2^* - h(Y^*_1 + Y^*_2) \}^2 \\
& = & c \ep \{h_1(Y_1^*) + h_2(Y_2^*) - h(Y_1^* + Y_2^*)\}^2 \\
& \geq & c \ep \{ h_1(Y_1^*) - a Y_1^* - b \}^2 \geq c D^*(X_1),
\end{eqnarray*}
where the penultimate inequality follows by Equation (\ref{eq:brown}).
Recall that $D(X) \leq 2 \sigma^2$, so that
$D^*(X) = D(X) - D(X)^2/(4 \sigma^2)
\geq D(X)/2$. The result follows on rescaling.
\end{proof}

We briefly discuss the strength of the condition imposed. If
 $X$ has mean zero, distribution function $F_X$ and continuous
density $f_X$, define the scale invariant quantity
$$ \C(X) = \inf_{u} (\Phi_{\sigma^2}^{-1} \circ F_X)'(u)
= \inf_{p \in (0,1)} \frac{ f_X(F_{X}^{-1}(p))}
{ \phi_{\sigma^2}( \Phi_{\sigma^2}^{-1}(p))}
= \inf_{p \in (0,1)} \sigma \frac{ f_X(F_{X}^{-1}(p))}
{ \phi( \Phi^{-1}(p))}.$$
We want to understand when $\C(X) > 0$.

\begin{example} If $X \sim U(0,1)$, then
$\C(X) = 1/\sqrt{12 \sup_x \phi(x)} = \sqrt{\pi/6}.$
\end{example}

\begin{lemma} If $X$ has mean zero and variance $\sigma^2$ then
$\C(X)^2 \leq \sigma^2/(\sigma^2 + {\rm median}(X)^2)$. \end{lemma}
\begin{proof}
By the Mean Value Inequality, for all $p$
$$ |\Phi_{\sigma^2}^{-1}(p)| = | \Phi_{\sigma^2}^{-1}(p) -
\Phi_{\sigma^2}^{-1}(1/2) |
\geq \C(X) | F_X^{-1}(p) - F_X^{-1}(1/2) |,$$
so that
\begin{align*}
\sigma^2 + F^{-1}_X(1/2)^2 & =  \int_0^1 F_X^{-1}(p)^2 dp +
F^{-1}_X(1/2)^2
=  \int_0^1 \{ F_X^{-1}(p) - F^{-1}_X(1/2) \}^2 dp  \\
& \leq  \frac{1}{\C(X)^2} \int_0^1 \Phi_{\sigma^2}^{-1}(p)^2 dp
=  \frac{\sigma^2}{\C(X)^2}.
\end{align*}
\end{proof}

In general we are concerned with the rate at which $f_X(x) \rightarrow
0$ at the edges of the support.

\begin{lemma}
If for some $\epsilon > 0$,
\begin{equation} \label{eq:denspow2}
f_X(F_X^{-1}(p)) \simeq c (1-p)^{1 - \epsilon}
\mbox{ as $p \rightarrow 1$}\end{equation} then
$\lim_{p \rightarrow 1} f_X(F_X^{-1}(p))/\phi(\Phi^{-1}(p)) =
\infty$.
Correspondingly if
\begin{equation} \label{eq:denspow} f_X(F_X^{-1}(p)) \simeq c p^{1 - \epsilon}
\mbox{ as $p \rightarrow 0$} \end{equation} then
$ \lim_{p \rightarrow 0} f_X(F_X^{-1}(p))/\phi(\Phi^{-1}(p)) =
\infty.$
\end{lemma}
\begin{proof}
Simply note that by the Mills ratio
\cite[p.850]{shorack} as $x \rightarrow \infty$,
$\Phi(x) \sim \phi(x)/ x$, so that as $p \rightarrow 1$,
$\phi(\Phi^{-1}(p)) \sim (1-p) \Phi^{-1}(p)
\sim (1-p) \sqrt{-2 \log (1-p)}$.
\end{proof}

\begin{example} \mbox{   } \; \;

\begin{enumerate}
\item{The density of the $n$-fold convolution of $U(0,1)$
random variables is given by $f_X(x) =
x^{n-1}/(n-1)!$ for $0 < x < 1$, hence $F_X^{-1}(p)
= (n! p)^{1/n}$, and
$f_X(F_X^{-1}(p)) = n/(n!)^{1/n} p^{(n-1)/n}$, so that
Equation (\ref{eq:denspow}) holds.}
\item{For an ${\rm Exp}(1)$ random variable, $f_X(F_X^{-1}(p)) = 1- p$, so that
Equation (\ref{eq:denspow2}) fails and $\C(X) = 0$.}
\end{enumerate}
\end{example}

To obtain bounds on $D(S_n)$ as $n \tends$, we need to control
the  sequence $\C(S_n)$.  Motivated  by properties  of the  (seemingly
related)  Poincar\'{e}  constant,  we  conjecture  that  $\C(  (X_1  +
X_2)/\sqrt{2}) \geq \C(X_1)$ for independent and identically distributed $X_i$.
If this is true and $\C(X) = c$ then $\C(S_n) \geq c$ for all $n$.

Assuming that $\C(S_n) \geq c$ for all $n$, note that $D(T_k) \leq
(1 - c/4)^k D(X_1) \leq (1 - c/4)^k (2 \sigma^2)$.  Now
$$ D(T_{k+1}) \leq D(T_k) (1 -c/2) \left\{ 1 + \frac{ c D(T_k)}{8\sigma^2
(1-c/2)} \right\},$$
so
$$\prod_{k=0}^{\infty}
\left\{ 1 + \frac{c D(T_k)}{ 8\sigma^2 (1-c/2)} \right\}
 \leq \exp \left\{ \sum_{k=0}^{\infty} \frac{c D(T_k)}{8 \sigma^2(1-c/2)}
\right\}
\leq \exp \left( \frac{1}{1-c/2} \right).$$
We deduce that
$$ D(T_{k})  \leq D(X_1) \exp \left( \frac{1}{1-c/2} \right)
\left( 1- c/2 \right)^k ,$$ or
$D(S_n) = O(n^t)$, where $t = \log_2(1-c/2).$

\begin{remark} In general, convergence of $d_4(S_n, Z_{\sigma^2})$ cannot
occur at a rate faster than $O(1/n)$. This follows because
$\ep S_n^4 = 3 \sigma^4 + \gamma(X_1)/n$,
where $\gamma(X)$, the excess kurtosis, is defined by $\gamma(X) = \ep X^4
- 3( \ep X^2)^2$ (when $\ep X =0$). Thus by Minkowski's inequality,
\begin{eqnarray*}
d_4(S_n,Z_{\sigma^2}) & \geq & \left| (\ep S_n^4)^{1/4} -
(\ep Z_{\sigma^2}^4)^{1/4} \right| \\
& = & 3^{1/4} \sigma \left|
\left(1 + \frac{\gamma(X)}{n} \right)^{1/4} - 1 \right|
= \frac{3^{1/4} \sigma |\gamma(X)|}{4 n} + O\left( \frac{1}{n^2} \right).
\end{eqnarray*}
\end{remark}

Motivated  by  this remark, and by analogy with the rates discovered in
\citeasnoun{johnson5},
we conjecture  that the true rate of convergence
is $D(S_n)  = O(1/n)$.  To obtain  this, we would need to control
$1-\C(S_n)$.

\section{Convergence to stable distributions} \label{sec:stable}

We now consider convergence to other stable
distributions. \citeasnoun{gnedenko} review
classical results of this kind. We say that $Y$ is $\alpha$-stable
if, when $Y_1, \ldots Y_n$ are independent copies of $Y$, we have
$ (Y_1 + \ldots + Y_n - b_n)/n^{1/\alpha} \sim Y$ for some sequence $(b_n)$.
Note that $\alpha$-stable variables only exist for $0 < \alpha
\leq 2$; we assume for the rest of this Section that $\alpha < 2$.

\begin{definition} \label{def:dna}
If $X$ has a distribution function of the form
\begin{eqnarray*}
F_X(x) & = & \frac{c_1 + b_X(x)}{|x|^{\alpha}} \mbox{ for $x < 0$} \\
1 - F_X(x) & = & \frac{c_2 + b_X(x)}{x^{\alpha}} \mbox{ for $x \geq 0$}
\end{eqnarray*}
where $b_X(x) \rightarrow 0$ as $x \rightarrow \pm \infty$, then we say that
$X$ is in the domain of normal attraction of some stable $Y$ with tail
parameters $c_1,c_2$.
\end{definition}

Theorem 5 of Section 35 of \cite{gnedenko} shows that if $F_X$ is
of this form, there exist a sequence $(a_n)$ and
an $\alpha$-stable distribution function $F_Y$,
determined by the parameters $\alpha$, $c_1$, $c_2$, such that
\begin{equation} \label{eq:stabconv} \frac{ X_1 + \ldots + X_n -
a_n}{n^{1/\alpha}}
\stackrel{d}{\rightarrow} F_Y.\end{equation}

Although Equation (\ref{eq:stabconv})
is obviously very similar to the standard Central Limit Theorem,
one important distinguishing feature is that both $\ep |X|^{\alpha}$
and $\ep |Y|^{\alpha}$ are infinite for $0 < \alpha < 2$.

We use the following moment bounds from
\citeasnoun{vonbahr2}. If $X_1, X_2, \ldots$ are independent, then
\begin{eqnarray}
\ep | X_1 + \ldots + X_n |^r & \leq & \sum_{i=1}^n \ep |X_i|^r
\quad \mbox{for $0 < r \leq 1$} \label{eq:vb1} \\
\ep | X_1 + \ldots + X_n |^r & \leq & 2 \sum_{i=1}^n \ep |X_i|^r
\quad \parbox{1.2in}{when $\ep X_i =0$,
for $1 < r \leq 2$.}
\label{eq:vb2}
\end{eqnarray}

Now, using ideas of \citeasnoun{stout}, we show that for a subset of the
domain of normal attraction, $d_{\beta}(X,Y) < \infty$, for some
$\beta > \alpha$.

\begin{definition} \label{def:dsna}
We say that a random variable is in the
domain of strong normal attraction of $Y$
if the function $b_X(x)$ from Definition \ref{def:dna} satisfies
$$ b_X(x) \leq \frac{C}{|x|^{\gamma}},$$
for some constant $C$ and some $\gamma > 0$. \end{definition}

\citeasnoun{cramer} shows that such random variables have an
Edgeworth-style expansion, and thus
convergence to $Y$ occurs. However, his proof requires some
involved analysis and use of characteristic functions. See also
\citeasnoun{mijnheer} and \citeasnoun{mijnheer2}, which use
bounds based on the quantile transformation described above.

We can regard Definition \ref{def:dsna} as being
analogous to requiring
a bounded $(2+\delta)$th moment in the Central Limit Theorem,
which allows an explicit rate of convergence (via
the Berry-Ess\'{e}en theorem).
We now show the relevance of Definition \ref{def:dsna} to the problem of stable
convergence.

\begin{lemma} \label{lem:dsna}
If $X$ is in the domain of strong normal attraction of
an $\alpha$-stable random variable $Y$,
then $d_{\beta}(X,Y) < \infty$ for some $\beta > \alpha$. \end{lemma}
\begin{proof}
We show that Major's construction always gives a joint distribution
$(X^*,W^*)$ with $\ep |X^* - W^*|^{\beta} < \infty$, and hence
$d_{\beta}(X,W) < \infty$.
Following \citeasnoun{stout}, define a random variable
$W$ by
\begin{eqnarray*}
\pr(W \geq x) & = &
c_2 x^{-\alpha} \mbox{  if $x > (2c_2)^{1/\alpha}$.} \\
\pr(W \leq x) & = &  c_1 |x|^{-\alpha}  \mbox{
if $x < -(2c_1)^{1/\alpha}$.} \\
\pr(W \in [-(2c_1)^{1/\alpha}, (2c_2)^{1/\alpha}]) & = & 0.
\end{eqnarray*}
Then for $w > 1/2$, $F_W^{-1}(w) = \{ c_2/(1-w) \}^{1/\alpha}$, and so for
$x \geq 0$,
$$ x - F_W^{-1} (F_X(x)) = x \left\{ 1 - \left( \frac{c_2}{c_2 + b_X(x)}
\right)^{1/\alpha} \right\}.$$
Now, since $b_X(x) \rightarrow 0$, there exists $K$ such that
if $x \geq K$ then $b_X(x) \geq - c_2/2$.

By the Mean Value Inequality, if $t \geq -1/2$, then
$$ \left| 1 - (1 + t)^{-1/\alpha} \right| \leq \frac{ |t| 2^{1+1/\alpha}}{
\alpha},$$
so that for $x \geq K$
$$ \left| x - F_W^{-1} F_X(x) \right|
\leq \frac{2^{1 + 1/\alpha} x |b_X(x)|}{\alpha c_2}.$$
Thus, if $X$ is in the strong domain of attraction, then
$$ \int_{|x| \geq K} \left| x - F_W^{-1} F_X(x) \right|^{\beta}
dF_X(x) \leq \left(  \frac{2^{1 + 1/\alpha} C}{\alpha c_2} \right)^{\beta}
\int_{|x| \geq K} |x|^{\beta(1- \gamma)}  dF_X(x).$$

Hence $d_{\beta}(X,W)$ is finite for all $\beta$ if
$\gamma \geq 1$ and for $\beta < \alpha/(1- \gamma)$, if $\gamma < 1$.
Moreover,
\citeasnoun[Equation (2.2)]{mijnheer2} shows that if $Y$ is $\alpha$-stable,
then as $x \tends$,
$$ \pr(Y \geq x) = \frac{c_2}{x^{\alpha}} +
O \left( \frac{1}{x^{2\alpha}} \right).$$
and so $Y$ is in its own domain of strong normal attraction.
Thus using the construction above, $d_{\beta}(Y,W)$ is finite for all
$\beta$ if $\alpha \geq 1$ and for $\beta < \alpha/(1-\alpha)$ otherwise.

Recall that the triangle inequality holds, for $d_{\beta}$ or
$d_{\beta}^{\beta}$, according as $\beta \geq 1$ or $\beta < 1$.
Hence $d_{\beta}(X,Y)$ is finite for all $\beta$ if
$\min(\alpha,\gamma) \geq 1$ and for
$\beta < \alpha/(1 - \min(\alpha,\gamma))$ otherwise.
\end{proof}

Note that for random variables $X_i$ in the same strong domain of normal
attraction,
$d_{\beta}(X_i,Y)$ may be bounded in terms of the function $b_{X_i}(x)$.
In particular
if there exist $C,\gamma$ such that $b_{X_i}(x) \leq C/|x|^{\gamma}$
then $\sup_i d_{\beta}(X_i,Y) < \infty$,
so the hypothesis of Theorem \ref{thm:mainstab} is satisfied.

\begin{proof}{\bf of Theorem \ref{thm:mainstab}}
We use the bounds provided by Equations (\ref{eq:vb1}) and
(\ref{eq:vb2}). We consider independent pairs $(X_i^*,Y_i^*)$ having the joint
distribution that achieves the infimum in Definition \ref{def:mallows}.
Then by rescaling we have that
\begin{eqnarray*}
d_{\beta}^{\beta}(S_n, Y)
& \leq & \frac{1}{n^{\beta/\alpha}} d_{\beta}^{\beta}(X_1 + \ldots
+ X_n, Y_1 + \ldots + Y_n)  \\
& \leq & \frac{1}{n^{\beta/\alpha}}
\ep \biggl| \sum_{i=1}^n (X_i^* - Y_i^*) \biggr|^{\beta}
\leq  \frac{2}{n^{\beta/\alpha}}
\sum_{i=1}^n  \ep \left| X_i^* - Y_i^* \right|^{\beta}.
\end{eqnarray*}
We deduce that in the case of identical variables,
$d_{\beta}(S_n,Y)$ (and hence
$d_{\alpha}(S_n,Y)$) converges at rate $O(n^{1/\beta - 1/\alpha})$.
\end{proof}

We now combine Theorem \ref{thm:mainstab} and Lemma \ref{lem:dsna}, to
obtain a rate of convergence for identical variables.
Note that Theorem \ref{thm:mainstab}
requires us to take $\beta \leq 2$. Overall then
we deduce that $d_{\alpha}(S_n,Y)$ converges at rate $O(n^{-t})$, where
\begin{enumerate}
\item{if $\min(\alpha, \gamma) \geq 1$, we take $\beta =2$, and hence
$t = 1/\alpha - 1/2$;}
\item{if $\min(\alpha,\gamma) < 1$, we may take
$\beta = \min[ \alpha/\{1 - \min(\alpha,\gamma) + \epsilon\}, 2]$
for any $\epsilon >0$, and then
$t = \min(1/\alpha - 1/2, 1 - \epsilon, \gamma/\alpha-\epsilon) $.}
\end{enumerate}

Theorem \ref{thm:mainr} implies that
if $d_r(S_n, Z_{\sigma^2})$ ever becomes finite, then it tends to zero,
the counterpart of the following result.

\begin{theorem} \label{thm:stablex}
Fix $\alpha \in (0,2)$, let $X_1, X_2, \ldots $ be
independent random
variables (where $\ep X_i =0$, if $\alpha > 1$), and let
$S_n = (X_1 + \ldots + X_n)/n^{1/\alpha}$.
Suppose there exists an $\alpha$-stable random variable $Y$ and
$Y_1, Y_2, \ldots$ having the same distribution as $Y$, and satisfying
\begin{equation} \label{eq:linde}
\frac{1}{n} \sum_{i=1}^n \ep \{ |X_i - Y_i|^{\alpha} \I( |X_i - Y_i|
> b) \} \rightarrow 0 \mbox{ as $b \tends$.}\end{equation}
If $\alpha \neq 1$ then $\lim_{n \tends} d_{\alpha}(S_n, Y) = 0$,
and if $\alpha = 1$ then there exists a sequence
$c_n = n^{-1} \sum_{i=1}^n \ep(X_i - Y_i)$ such that
$\lim_{n \tends} d_{\alpha}(S_n -c_n, Y) = 0$.
\end{theorem}
\begin{proof}(Suggested by an anonymous referee).
Fix $\epsilon  > 0$. Suppose first that $1 \leq \alpha < 2$ and let
$d_i = \ep(X_i - Y_i)$. Note that $d_i=0$ if $\alpha > 1$.
Let $b > 0$ and define
\begin{eqnarray*}
U_i & = & (X_i - Y_i) \I( |X_i - Y_i| \leq b) -
\ep \{ (X_i - Y_i) \I( |X_i - Y_i| \leq b) \} \\
V_i & = & (X_i - Y_i) \I( |X_i - Y_i| > b) -
\ep \{ (X_i - Y_i) \I( |X_i - Y_i| > b) \}.
\end{eqnarray*}
Then by Equation (\ref{eq:vb2}),
\begin{align*}
d^{\alpha}_{\alpha}(S_n - c_n,Y)
& \leq  \frac{1}{n} \ep \biggl| \sum_{i=1}^n (X_i - Y_i - d_i)
\biggr|^{\alpha}
=  \frac{1}{n} \ep \biggl| \sum_{i=1}^n U_i + \sum_{i=1}^n V_i
\biggr|^{\alpha} \\
& \leq  \frac{2^{\alpha-1}}{n} \ep \biggl| \sum_{i=1}^n U_i \biggr|^{\alpha}
+ \frac{2^{\alpha-1}}{n} \ep \biggl| \sum_{i=1}^n V_i \biggr|^{\alpha} \\
& \leq  \frac{2^{\alpha-1}}{n} \biggl\{ \ep \biggl( \sum_{i=1}^n U_i \biggr)^2
\biggr\}^{\alpha/2} +
\frac{2^{\alpha}}{n} \sum_{i=1}^n \ep | V_i |^{\alpha} \\
& \leq  \frac{2^{\alpha-1}}{n}
\biggl( \sum_{i=1}^n \ep U_i^2 \biggr)^{\alpha/2} +
 \frac{2^{2 \alpha -1}}{n} \sum_{i=1}^n
\ep \{ |X_i - Y_i|^{\alpha} \I( |X_i - Y_i| > b) \} \\
& \qquad \qquad + \frac{2^{2\alpha-1}}{n} \sum_{i=1}^n
\left[ \ep \left\{ |X_i - Y_i| \I( |X_i - Y_i| > b) \right\}
\right]^{\alpha} \\
& \leq  \frac{2^{\alpha-1} b^{\alpha}}{n^{1-\alpha/2}}
+ \frac{2^{2 \alpha}}{n} \sum_{i=1}^n
\ep \{ |X_i - Y_i|^{\alpha} \I( |X_i - Y_i| > b) \}
\end{align*}
The result follows on
choosing $b$ sufficiently large to control the second term, and then
$n$ sufficiently large to control the first.

For $0 < \alpha < 1$, take $U_i$ as before, take
$V_i =  (X_i - Y_i) \I( |X_i - Y_i| > b)$ and
$a_i = \ep \{ (X_i - Y_i) \I( |X_i - Y_i| \leq b) \}$. Now using
Equation (\ref{eq:vb1}),
\begin{eqnarray*}
d^{\alpha}_{\alpha}(S_n, Y)
& \leq &
\frac{1}{n} \ep \biggl| \sum_{i=1}^n U_i + \sum_{i=1}^n V_i + \sum_{i=1}^n a_i
\biggr|^{\alpha} \\
& \leq &
\frac{1}{n} \ep \biggl| \sum_{i=1}^n U_i \biggr|^{\alpha}
+ \frac{1}{n} \ep \biggl| \sum_{i=1}^n V_i \biggr|^{\alpha}
+ \frac{1}{n} \biggl| \sum_{i=1}^n a_i \biggr|^{\alpha}  \\
& \leq &
\frac{1}{n} \biggl\{ \ep \biggl( \sum_{i=1}^n U_i \biggr)^2
\biggr\}^{\alpha/2}
+ \frac{1}{n} \sum_{i=1}^n \ep |V_i|^{\alpha}
+ \frac{b^{\alpha}}{n^{1-\alpha}},
\end{eqnarray*}
so again since $b$ is arbitrary, the result follows.
\end{proof}

Note when $X_1, X_2, \ldots$ are identically distributed, the Lindeberg
condition (\ref{eq:linde}) reduces to the requirement that $d_{\alpha}(X_1,Y)
< \infty$.

\setlength{\parskip}{0pt}


text:
{\bf Problem.} The pages of a book are numbered $1_{}^{}$ through $n_{}^{}$. When the page numbers of the book were added, one of the page numbers was mistakenly added twice, resulting in an incorrect sum of $1986_{}^{}$. What was the number of the page that was added twice?
{\bf Level.} Level 4
{\bf Type.} Algebra
{\bf Solution.} If all the page numbers were added just once, the sum would be \[1 + 2 + \dots + n = \frac{n(n+1)}{2}.\]But one of the page numbers was added twice, so the interval of possible values for the incorrect sum is $\left[\tfrac{n(n+1)}{2} + 1, \tfrac{n(n+1)}{2} + n\right].$ We are given that the incorrect sum is $1986,$ so we must have \[\frac{n(n+1)}{2} + 1 \le 1986 \le \frac{n(n+1)}{2} + n.\]We look for the value of $n$ which satisfies this inequality chain. We have $\tfrac{n(n+1)}{2} \approx 1986 \approx 2000,$ so $n(n+1) \approx n^2 \approx 4000,$ and $n \approx \sqrt{4000} \approx 63.$ For $n = 63,$ we have $\tfrac{n(n+1)}{2} = 2016,$ which is too large. For $n=62,$ we have $\tfrac{n(n+1)}{2} = 1953,$ which works, because \[1953 + 1 \le 1986 \le 1953 + 62.\]Then, the page number that was added twice must be \[1986 - 1953 = \boxed{33}.\]

set_name: MATH


TITLE: Derivative of $x^a$
QUESTION [3 upvotes]: How to calculate the derivative of function $f$ such, that:
$f(x)=x^a$, where $x>0$ and $a\in \Bbb R$.
Do you know any formula for $(x+h)^a$?

REPLY [6 votes]: For $a$ an integer one can prove that $f'(x)=ax^{a-1}$ by induction. In the general case we can use the chain rule:
$$
f(x)=e^{a\log x}
$$
so
$$
f'(x)=e^{a\log x}\cdot a\cdot \frac{1}{x}=ax^{a-1}
$$
Of course $f$ is defined only for $x>0$ if $a$ is not supposed to be an integer, but an arbitrary real number.

REPLY [3 votes]: Yes. You can show it very easily what it is starting from the definition. Let's make the example when $a$ is an integer (as a hint) (you know what the definition of the derivative is?).
$$
f'(y)=\lim_{x\to y} \frac{x^a-y^a}{x-y}=\frac{(x-y)(x^{a-1}+ax^{a-2}+...)}{x-y}=ax^{a-1}
$$
I skipped some steps, but I think you can try to reproduce them as an exercise. If is not clear let us know, and we can help you more.

REPLY [2 votes]: Try logarithmic differentiation:  if $f(x) = x^a$, then $\ln f(x) = a \ln x$, whence
$(1 / f(x)) f'(x) = a / x$.  Thus $f'(x) = af(x) / x = ax^a /x = ax^{a - 1}$, just as if $a$ were an integer.
I can't, off the top of my head, quote a formula for $(x + h)^a$, but I'm pretty sure something along those lines is known.  Might be a challenge to do the algebra required in computing the derivative, to wit $((x + h)^a - x^a) / h$, when $a$ is not a postivie integer.
Hope this helps.  Cheers,
and as always,
Fiat Lux!!!


TITLE: Find the sum of the following series: $ \frac{1}{1 \cdot 2}\,+\,\frac{1}{2 \cdot 3}\,+\,\frac{1}{3 \cdot 4} +\cdots\,+\frac{1}{100 \cdot 101}$
QUESTION [3 upvotes]: Find the sum of the following series
  $$ \frac{1}{1 \cdot 2}\,+\,\frac{1}{2 \cdot 3}\,+\,\frac{1}{3 \cdot 4} +\cdots\,+\frac{1}{100 \cdot 101}$$

My Attempt:
$$\frac{1}{2 \cdot 3} =\frac{1}{2}-\frac{1}{3}.$$
So we can write question as:
$$\frac{1}{1}-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\frac{1}{4}+\cdots+\frac{1}{99}-\frac{1}{100}+\frac{1}{100}-\frac{1}{101}\\
=\frac{1}{1}-\frac{1}{101}\\
=\frac{100}{101}.$$
Am i right?

REPLY [0 votes]: _Sum up of everybody else's comments: _Yes, it is correct. The only thing I'd say is that as Theophile said, you need to make your prove more convincing, and back up every single hole in. A proof is never at an optimal proving state, but you can maximise this, by filling in every single statement you make with a law or rule, or in other cases, another statement. In the end, all the loose bits would be tied up, and your proof will be complete.


TITLE: A 4x4 homogeneous matrix for a 90 degree rotation about Y axis?
QUESTION [1 upvotes]: According to my book

Rotations through an angle $\theta$ about the $x$, $y$, and $z$ axes are performed using the following transformation matrices.

For example,
$$    R_x(\theta) = \left[
\begin{matrix}
1& 0 & 0 \\\
0& \cos\theta &-\sin\theta\\\
0& \sin\theta &\cos\theta
\end{matrix}\right]
$$
Ry0= | cos0 0 sin0 0|
     | 0 1 0 0|
     | -sin0 0 cos0 0|
     | 0 0 0 1|

Rz0= | cos0 -sin0 0 0 |
     | sin0 cos0 0  0|
     | 0 0 1 0|
     | 0 0 0 1|

And I just need to put the angle in it no matter which rotate about axis?
After that, how can I get a $4\times 4$ matrix?
Thank you

REPLY [0 votes]: Let the rotation axis be a line through a fixed point $(x_0,y_0,z_0,1)^T$ and an infinite point (direction of the line) $(a,b,c,0)^T$, without loss of generality, we assume $a^2+b^2+c^2=1$.  Use right-handed rule for rotation, then a general homogeneous rotation with angle $\theta$ can be obtained as:
$$
\boldsymbol{R}^{3D}\left(x_0,y_0,z_0,a,b,c,\theta\right)=\mathscr{C}_1+\left(\sin\theta\cdot\mathscr{A}_2- \left(1-\cos\theta\right)\cdot\mathscr{O}_3\right)\cdot \mathscr{T}_4
$$
where:
$$\mathscr{C}_1=
\left[\begin{array}{*{20}{c}}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&2-\cos\theta
\end{array}\right]$$
$$\mathscr{A}_2  =  {\begin{array}{c}
\underbrace{
\begin{array}{c}
 {{\left[ {\begin{array}{*{20}{c}}
{\color{blue}0}&{\color{blue}-c}&{\color{blue}b}&0\\
{\color{blue}c}&{\color{blue}0}&{\color{blue}-a}&0\\
{\color{blue}-b}&{\color{blue}a}&{\color{blue}0}&0\\
0&0&0&0
\end{array}} \right]}}
\end{array}
} \\ \text{Antisymmetric matrix}
\end{array}}
$$
$$
\quad\mathscr{O}_3= \begin{array}{c}
\underbrace{  {I - {\left[ {\begin{array}{*{20}{c}}
a\\
b\\
c\\
0
\end{array}} \right] \cdot \left[ {\begin{array}{*{20}{c}}
a&b&c&0
\end{array}} \right]}} }\\
\text{Orthographic parallel projection} \end{array} $$
$$ \mathscr{T}_4=\begin{array}{c}
\underbrace{\left[ {\begin{array}{*{20}{c}}
1&0&0&{ - {x_0}}\\
0&1&0&{ - {y_0}}\\
0&0&1&{ - {z_0}}\\
0&0&0&1
\end{array}}  \right]}\\ \text{Translation}\end{array}$$
The L-C formulation of homogeneous 3D rotation is similar to Rodrigues' but they are not the same in essence. Details are available here:
A submission on homogeneous rotation to arXiv.org
For your case, substitute $x_0=y_0=z_0=0$, $a=b=0$,  $c=1$ and $\theta=\dfrac{\pi}{2}$ into the L-C formulation then you can obtain the desired homogeneous rotation matrix.


TITLE: Lagrangian in rotating reference frame
QUESTION [5 upvotes]: I have a homework question I am working on, and I'm stuck on the last term in this proof. The problem states:
Question: Consider a primed set of axes coincident in origin with an inertial set of axes but rotating with respect to the inertial frame with fixed angular velocity $\omega_0$. If a system of mass points is subject to forces derived from a conservative potential $V$ depending only on the distance to the origin, show that the Lagrangian for the system in terms of coordinates relative to the primed set can be written as
$$\mathcal{L} = T' + \omega \cdot L' + \frac{1}{2} \omega \cdot I' \cdot \omega_0 - V$$
where primes indicate the quantities evaluated relative to the primsed set of axes.
Important Notes: Here $L'$ is the angular momentum in the rotating frame and $V$ is the potential in the non-rotating frame.
Attempt at Solution:
We know that the Lagrangian is given by
$$\mathcal{L} = T_{tot} - V_{tot}$$
I will proceed by only considering one particle (this is a rigid body problem, thus if we prove this is true for one particle it is true for a distribution of particles). The kinetic energy is equal to,
$$T_{tot} = T_{rot}+T_{space}$$
where "space" refers to the space coordinates in the inertial frame. We get $T_{space}$ by the following manipulation:
$$T_{space} = T_s = \frac{1}{2}mv\cdot v = \frac{1}{2}m v \cdot (\omega \times r)$$
$$\text{by triple product property } = \frac{1}{2}m \omega \cdot (r \times v)$$
$$=\frac{1}{2}\omega \cdot m(r \times v) = \frac{1}{2} \omega \cdot L$$
$$L = I \cdot \omega$$
$$T_s = \frac{1}{2} \omega \cdot I \cdot \omega$$
Thus I obtain one of the four terms. Now I consider the kinetic energy and potential energy in the rotating reference frame. The problem wants me to leave the kinetic energy in the reference frame in terms of $T'$, so I already get that term (now I have 2/4 terms). The final thing to consider is the potential energy in the rotating reference frame.
$$\mathcal{L} = T' - V' + \frac{1}{2} \omega \cdot I \cdot \omega$$
We know that in a rotating reference frame, the effective force is given by
$$F_{eff} = F - 2m(\omega \times v_{rot}) - m\omega \times (\omega \times r')$$
Integrating both sides we get
$$V' = V - \int 2m(\omega \times v_{rot}) dr - \int m\omega \times (\omega \times r) dr$$
This is where I start getting confused (hopefully I'm thinking of this step correctly). $\omega$ is constant, but $v_r$ shouldn't be since there are forces acting on the particle. Therefore, we would expect the velocity to change. So I don't know how to integrate this first term. I could try putting the velocity in terms of the angular momentum (which should be a constant because it is a conservative force), but then I get a natural log in my answer, which of course isn't right.
The second term I think I can integrate. In cylindrical coordinates, if we define $\vec{\omega} = \omega \hat{z}$ then $\omega \times (\omega \times r) = -\omega^2 r$. Integrating I get $-\frac{1}{2} m \omega^2 r^2$ I'm not really sure what to even do with this term.
Any help where I am going wrong would be much appreciated! Thanks.

REPLY [2 votes]: There are three mistakes that prevented you from arriving at the correct lagrangian.
(1) The correct form for a CM lagrangian should be $L = T_{total} - V_{total}$ instead of $L = T_{total} + V_{total}$ I think this is just a typo since later on you did use the correct lagrangian.
(2)It is not valid to assume that $T = T_{space} + T_{rot}$ since energy is not additive in this manner.
(3) There is no need to introduce $V'$. Since the origin is fixed, and since the potential is conservative, $V = V' $
Here is a hint for a correct derivation: Express the velocity of the particle in the rotating frame as a function of the velocity in fixed frame and $\omega_0$. Then plug this velocity into the standard $T = \frac{1}{2}mv^2$ formula. Expand the right hand side and you will get a three term expression that matches what you are asked for. Try it!


TITLE: Is infinite boolean algebra atomless?
QUESTION [1 upvotes]: I got two questions:
1) Does there exist an infinite Boolean algebra which contains an atom?
I answered yes.
2) Does there exist an infinite Boolean algebra B such that for every b contained in B there is an atom a contained in B with a is smaller or equal than b?
I answered no.
I just cannot figure out what's the difference between these two questions.
Can someone help please?

REPLY [1 votes]: Edit: I see from the comments that $b$ in part 2 is restricted so that it can't be the least element of $B$. That's fairly important information, and changes my answer.
One hint will apply to both parts equally well. The most familiar form of a Boolean Algebra is the power set of a set. Consider the power set of an infinite set to answer both of your questions.
Added: Your example--letting $B$ be the power set of the natural numbers--works as an example for both. As you pointed out, its atoms are precisely the singleton subsets of the natural numbers. Hence, $B$ has an atom--in fact, infinitely-many, but it has at least one, which is what matters--and so the answer to Question 1 is "yes." On the other hand, given any non-least element $b$ of $B$ (that is, any non-empty subset of the natural numbers), there is at least one atom less than or equal to it--for example, the singleton containing only the least element of $b$.  Hence, the answer to Question 2 is also "yes."


TITLE: Could an inverse of (weak) Morse inequality exists in some special case?
QUESTION [2 upvotes]: Could an inverse Morse inequality hold in some sense? More precisely I wish the following result to be true:

Problem
  $M$ is a smooth simply connected compact manifold, $dim(M)=n$, $f$ is a morse function on $M$, the number of critical points with $k$-th morse index of $f$ is $m_k$ $0\leq k\leq n$,the standard morse inequality(weak form) said,
  $$rank(H^k(M)\leq m_k)$$
  I wish, for some function $g$ is there some inequality hold for all $M$,$$rank(H^k(M))\geq g(m_1,...,m_n)?$$

Motivation
The Motivation why I need this type of result is due to I need to find if there is a manifold $M$ which is simply connected, compact, the cohomology ring of $M$ is isomorphism to $\mathbb {CP}^3$ but $M$ is not (topology) homomorphism to $\mathbb{CP^3}$. If I have this type of result, then thanks to the CW-structure of topology manifold I reduce this question to complicated calculate but can be finished in finite times.
Attempt
I follow the analytic proof of Witten on the Morse inequality and wish to find a analytic explain of the difference of Morse index and rank of cohomology group.
In the analytic proof, Witten consider the chain homotopy of the following Witten defamation from,
$$(\Omega^*(M),d):0
 \stackrel{d}{\to} \Omega^0(M)\stackrel{d}{\to} \Omega^1(M)\stackrel{d}{\to} ...\stackrel{d}{\to} \Omega^{dim(M)}(M)\stackrel{d}{\to} 0$$
to,
$$(\Omega^*(M),d_{Tf}):0\stackrel{d_{Tf}}{\to} \Omega^0(M)\stackrel{d_{Tf}}{\to}\Omega^1(M)\stackrel{d_{Tf}}{\to} ...\stackrel{d_{Tf}}{\to} \Omega^{dim(M)}(M)\stackrel{d_{Tf}}{\to} 0$$
Where $d_{Tf}=e^{-Tf}de^{Tf}$.
Then the first observation is Dirac operator $D=d+d^*$ have a induced defamation operator $D_{Tf}=d_{Tf}+d^*_{Tf}$. And for all $T\in [0,\infty]$ we can prove a hodge split result for $D_{Tf}$.
The second observation is on the local of critical point, when $T\to \infty$, $D_{Tf}$ coverage to the solution of harmonic oscillator.
The third observation is

Witten stable lemma For any $c > 0$, there exists $T_0 > 0$ such that when $T\geq  T_0$, the number of eigenvalues in $[0,c]$ of $D_{Tf}|_{\Omega^i(M)}$, $0\leq i \leq n$, equals to $m_i$.

For any integer $i$ such that $0 \leq i\leq n$,let
$$F^{[0,c]}_{Tf,i}\subset \Omega^*(M)$$
denote the $m_i$ dimensional vector space generated by the eigenspaces of $D_{Tf}|_{\Omega^i(M)}$, associated with eigenvalues in $[0,c ]$ .
On the other hand, there is a natural restriction map from $(\Omega(M),d_{Tf})$ to $(F_{Tf}^{[0,c]},d_{Tf})$, and the hodge decomposition theorem still hold then we get the weak Morse inequality, and moreover due to the proof the analytic meaning of $m_i-\beta_i$ seems to be the term vanish at infinity, but how to compute this term rigorously and find it?
I will appreciate for any advice and comments!

REPLY [3 votes]: There are some weak things that one can say using elementary linear algebra (rank + nullity theorem). Eg $dim(H^k(M)) \geq m_k -(m_{k-1} + m_{k+1})$.
With regard to your motivating problem: There are certainly (smooth) manifolds homotopy equivalent to $CP^3$ that are not homeomorphic to $CP^3$. You can find a comprehensive discussion in Chapter 14C of Wall's book, Surgery on Compact Manifolds.  Wall does the PL case, but in this dimension, the PL and smooth classifications are equivalent; it's also not hard to compare the PL and topological classifications.
Wall's proof is not constructive, but leans on transversality via Sullivan's analysis of the homotopy type of the space $G/PL$. If you need an actual construction, I would bet you can extract one out of the literature of the time. There is a nice exposition that gives explicit constructions for fake $CP^5$ and $CP^6$. Even better might be Montgomery-Yang, Differentiable actions on homotopy seven spheres which I think gives constructions for fake $CP^3$s.


TITLE: Why isn't quantum entanglement just a lack of information?
QUESTION [3 upvotes]: From this question and answer from joshphysics, I didn't understand one thing, even after reading the comments:
Why should assume that entangled electrons will only "decide" their state after observation?
Isn't it just a lack of information? For instance, knowing that we have a black and white marble and picking one afterwards with your eyes closed, doesn't mean that the marble "decides" to be white or black after the observation, i.e. there is no entanglement.
Therefore, I do not know what makes the states of the electrons so special.

REPLY [0 votes]: Apologies to SE for the fact that I am reusing parts of an answer I wrote earlier, but to answer the core question of why you can't assume the system has a particular state before measurement I think this is the easiest example to think of.
Consider two entangled quantum systems which are described by three properties, A, B and C each which can take a value of up or down.
The two systems can be entangled such that if you measure the same property on both systems then you will get the same result 100% of the time, and each case occurs 50% of the time. That is to say both systems give up 50% of the time or both systems give down 50% of the time, but you will never get a result where one systems gives up and the other down. Just to reiterate is is only when you measure the same property, ie: both A, both B or both C.
But here is the problem if you measure different properties then you will get the same direction 25% of the time and opposite directions 75% of the time. For example if I measure A on one system and it gives a result of up, then when I measure B on the other system I will get up 25% of the time and down 75% of the time.
There is no way of pre-assigning up or down so that they are different 75% or the time. If you think through it the best you can do is different 2/3 times by excluding cases where A, B and C are all the same. The only other way around this is to assume that measuring one system instantaneously affects the other but these systems are arbitrary far apart and space like separated so who measures first is relative to your reference frame.
The simplest solution is conceding your ability to assign a value before measurement.


text:
\section{Low-rank matrix recovery under a generative network prior}\label{sec:SpikedRes}
We are now ready to formulate our main theoretical result
for the spiked random matrix models. Its analysis will be based on
the following assumptions on the weights of the network.

\begin{assumption}\label{hyp:randW}
	The generative network $G$ defined in \eqref{eq:Gx}, has weights $W_i \in \R^{n_i \times n_{i-1}}$ with i.i.d. entries from $\mathcal{N}(0,1/n_i)$ and satisfying the expansivity  condition with constant $\eps >0$:
	\begin{equation*}
	n_{i+1} \geq c \eps^{-2} \log(1/\eps) n_{i} \log n_{i}
	\end{equation*}
	for all $i$ and a universal constant $c > 0$.
\end{assumption}

We remark that no assumption on the layer-wise independence of the weight matrices is required.

Due to the non-smoothness of the Relu activation functions, the generative network $G$ and the loss function $f$ are not differentiable everywhere. Therefore, following \cite{HHHV18}, we resort to some concepts from nonsmooth analysis \footnote{The reader is referred to \cite{clason2017nonsmooth} for more details.}. Since $f$ is continuous and piecewise smooth, at every point $x \in \R^k$,  $f$  has a \textit{Clarke subdifferential} given by:
\begin{equation}\label{eq:subdiff}
\pa f(x) = \text{conv} \{ v_1, v_2, \dots, v_T \}
\end{equation}
where conv denotes the convex hull of the vectors $v_1, \dots, v_T$, gradients of the $T$ smooth functions adjoint at $x$.
In particular at a point where $f$ is differentiable $\pa f(x) = \{\nabla f(x) \}$. The terms subgradients will be used for the vectors $v_x \in \pa f(x)$.

The next theorem will demonstrate the favorable optimization geometry of the minimization problem \eqref{eq:minM} for the spiked matrix models \eqref{eq:wishart_Y} and \eqref{eq:wigner_Y}.
We will show that provided that the noise scales linearly with the latent dimension $k$, outside 0 and two small Euclidean balls around $\xstar$ and a negative multiple of $\xstar$,
the subgradient $v_x$ give a descent direction
for the function $f(x)$. We let
$\mathcal{B}(x,r)$ denotes
the Euclidean ball of radius $r$ around $x$, and $D_v f(x)$ denotes the (normalized) one-sided directional derivative of $f$ in direction $v$: $D_{v} f(x) = \lim_{t \to 0} \frac{f(x + t v) - f(x)}{t \|v\|_2}$.

\begin{thm}[Global Landscape Analysis]\label{thm:main_rand}
	Let Assumption \ref{hyp:randW} be satisfied with $\eps \leq K_1 d^{-96}$, consider the minimization problem \eqref{eq:minM} and assume that the noise variance ${\omega}$ satisfies ${\omega} \leq K_2 \|\xstar\|_2^2 2^{-d}/d^{44}$ where:
	\begin{itemize}
		\item for the \textbf{Spiked Wishart Model} \eqref{eq:wishart_Y}  take $M~=\Sigma_N-\sigma^2 I_n$ with $\Sigma_N = Y^\T Y/N$ and:
		\[
		{\omega} :={(\|\ystar\|_2^2 + \sigma^2)}  \max \Bigg\{\sqrt{\frac{113 k \log (3\, n_1^d n_2^{d-1} \dots n_{d-1}^2 n) }{N}}, \frac{52 k \log (3\, n_1^d n_2^{d-1} \dots n_{d-1}^2 n) }{N} \Bigg\};
		\]

		\item for the \textbf{Spiked Wigner Model} \eqref{eq:wigner_Y}  take $M = Y$ and:
		\[
		{\omega} := {\nu} \sqrt{  \frac{30 k \log (3\, n_1^d n_2^{d-1} \dots n_{d-1}^2 n)  }{n}}.
		\]
	\end{itemize}

	Then for $\gamma_\eps > 0$ depending polynomially on $\eps$,
	with probability at least  $1 - 2e^{- k \log n} - \sum_{i=1}^d 8 n_i e^{- \gamma_\eps n_{i-1}}$
	the following holds.

	For all $x \in \R^k$:
	\begin{itemize}
		\item if $x \notin \mathcal{B}(\xstar, r_+)~\cup~\mathcal{B}(-\rho_d \xstar, r_-)~\cup~\{0\}$ and $v_x \in \pa f(x)$:
		\[
		D_{-v_x} f(x) < 0
		\]
		where
		\[
		r_+ = K_3 (d^{14} {\eps^{1/2}} + 2^d d^{10} \omega  \|\xstar\|_2^{-2})  \|\xstar\|_2,
		\]
		and
		\[
		r_- =  K_4 (d^{12} {\eps}^{1/4} + 2^{d/2} d^{10} \omega^{1/2} \|\xstar\|_2^{-1})   \|\xstar\|_2
		\]
		\item if $x \in \mathcal{B}(0,  \|\xstar\|_2/16 \pi) \backslash \{0\}$  and $v_x \in \pa f(x)$ then \[\langle x, v_x\rangle < 0\]
		while if $x = 0$ and $v \in \mathcal{S}^{k-1}$ then
		\[
		D_{-v} f(0) = 0
		\]
	\end{itemize}
	Here $K_1, \dots, K_4$  are universal constants and $0< \rho_d \leq 1$ depends only on the depth $d$ and converges to 1 as $d \to \infty$.
\end{thm}

According to the theorem the subgradients of $f$ are direction of strict descent for any nonzero point outside the two Euclidean balls around $\xstar$ and $-\xstar$. Furthermore, there are no other spurious critical points or non-escapable saddles apart from the local maximum $x = 0$.

For small enough $\eps > 0$, the size of the two neighborhoods around $\xstar$ and $-\xstar$ is a function of the control parameter $\omega$.
This quantity is analogous to the effective SNR $\sigma^2 \sqrt{s \log(n)/N}$
which governs sharp transitions in Sparse PCA \cite{amini2008high}.
In particular, for the Wishart model (structured PCA problem), in the interesting regime $k \log(n) \lesssim N$ and at fixed depth $d$, the size of the ball around $\xstar$ shrinks at the optimal rate $\sqrt{k \log(n)/N}$, implying that a number of samples $N$ proportional to $k$ is sufficient for a consistent estimate. In the same fashion, for the Wigner model the size of the noise $\nu$
it is required to be inversely proportional to the optimal rate $\sqrt{k/n}$.

We note that the quantity $2^d$ in the hypothesis and conclusions of the theorem, is an artifact of the scaling of the network and it should not be taken as requiring exponentially small noise. Indeed under the assumptions on the weights
specified above, these matrices have spectral norm approximately 1, while the application of the Relu function zeros out approximately half of the entries of its argument leading to an ``effective'' operator norm of approximately $1/2$. The other polynomial dependence on the depth $d$ are likely not optimal and optimizing the proof for superior dependence on $d$ would not drastically alter the fundamental theoretical advance. As we show in the numerical experiments the bounds are quite conservative and the actual dependence on the depth is much better in practice.

Having analyzed the behavior of the loss $f$ outside the two balls around $x$ and $-\rho_d \xstar$, the next proposition
will describe the local properties of these two neighborhoods.

\begin{comment}
\begin{figure}
\centering
\includegraphics[width=0.6\linewidth]{imgs/loss_surf3}
\caption{ Loss surface $ \frac{1}{4} \|G(x)G(x)^\T - Y\|^2_F$ of a network $G$ with ReLU
activation functions, latent dimension $k = 2$, $n_1 = 250$ nodes in hidden layer and space dimension $n = 1500$ and with random Gaussian weights in each layer. The matrix $Y$ is from a spiked Wishart model with $N = 100$ and $\sigma = 1$,  and the exact latent vector is $\xstar = [1,0]$. As predicted by our theory, the surface
has a critical point near $- \xstar$, a global minimum at $\xstar$ and a local maximum at 0.} \label{fig:losssurf3}
\end{figure}

In Figure \ref{fig:losssurf3} we plot the landscape geometry of \eqref{eq:minM} for the Wishart model $\sigma = 1$ and $N = 100$, and in case of a 2 layer random network with latent dimension $k = 2$, hidden dimension
$h_1 = 250$ and output dimension $n = 1500$. The point $\xstar = [1,0]$ is a global minimum, and as predicted by our theory, $x = 0$ is local maximum and there is a local minimum in the vicinity of $-\xstar$. Note moreover that in this regime $N << n$ and
PCA fails.
\end{comment}

\begin{prop}\label{prop:rand_localmin}
	Let the assumptions of Theorem  \ref{thm:main_rand} be satisfied.

	A. For any $x \in \mathcal{B}(\xstar, r_+)$ and $y \in \mathcal{B}(- \rho_d \, \xstar, r_-)$ it holds that:
	\[
	f(x) < f(y)
	\]

	B. In addition, for $K_5$ and $K_6$ positive absolute constants:
	\begin{itemize}
		\item for the \textbf{Spiked Wishart Model}, for all $x \in \mathcal{B}(\xstar, r_+)$:
		\[
		\| G(x) - \ystar\|_2	\leq K_5 \Big(d^4 {\eps^{1/2}} +  \frac{\omega}{\| \ystar\|_2^2 } \Big) d^{10} \|\ystar\|_2,
		\]

		\item  for the \textbf{Spiked Wigner Model}, for all $x \in \mathcal{B}(\xstar, r_+)$:
		\[
		\| G(x) - \ystar\|_2	\leq K_6 \Big(d^4 {\eps^{1/2}} + \frac{\omega}{\| \ystar\|_2^2 } \Big) d^{10} \|\ystar\|_2,
		\]

	\end{itemize}

\end{prop}

The previous results imply that, for $\eps$ small enough and under the assumptions on the noise level $\omega$, any point $x$ in the benign neighborhood $\mathcal{B}(\xstar, r_+)$ has reconstruction error $\| G(x) - \ystar\|$ which scales optimally according to \eqref{eq:ws_scaling} or \eqref{eq:wg_scaling}.

\subsection{Proofs outline and techniques}

The bulk of the analysis will be based on deterministic conditions on
the weights of the network.
In particular we leverage a set of techinical results
recently introduced by \cite{hand2017global}.

For $W \in \R^{n \times k}$ and $x \in \R^k$, define the operator $W_{+,x} := \diag(W x > 0) W$ such that $\relu(W x) = W_{+,x} x$.  Moreover let $W_{1,+,x} = (W_1)_{+,x} = \diag(W_1 x > 0) W_1$, and for $ 2 \leq i \leq d$:
\[
W_{i,+,x} = \diag(W_i, \Pi_{j=i-1}^{1} W_{j,+,x}  x > 0)W_i,
\]
where $\Pi_{i=d}^{1} W_{i} = W_d W_{d-1} \dots W_1$.
Finally we let $\Lambda_x=~\Pi_{j=d}^{1} W_{j,+,x} $
and note that $G(x) = \Lambda_x x$.

\begin{definition}[Weight Distribution Condition \citep{hand2017global}]\label{def:WDC}
	We say that $W \in \R^{n \times k}$ satisfies the \textbf{Weight Distribution Condition (WDC)} with constant $\epsilon > 0$ if for all $x_1, x_2 \in \R^k$:
	\[
	\| W_{+,x_1}^\T W_{+,x_2} - Q_{x_1,x_2}\|_2 \leq \eps,
	\]
	where
	\[
	Q_{x_1,x_2} = \frac{\pi - \theta_{x_1,x_2}}{2 \pi} I_k + \frac{\sin \theta_{x_1,x_2}}{2 \pi} M_{\hat{x}_2\leftrightarrow \hat{x}_2}
	\]
	and $\theta_{x_1,x_2} = \angle (x_1,x_2)$, $\hat{x}_1 = x_1/\|x_1\|_2$, $\hat{x}_2 = x_2/\|x_2\|_2$, $I_k$ is the $k\times k$ identity matrix and $M_{\hat{x}_1\leftrightarrow \hat{x}_2}$ is the matrix that sends $\hat{x}_1 \mapsto \hat{x}_2$, $\hat{x}_2 \mapsto \hat{x}_1$, and with kernel span$(\{x_1,x_2\})^\perp$.
\end{definition}

Note that $Q_{x_1,x_2}$ is the expected value of $W_{+,x_1}^\T W_{+,x_2}$ when $W$ has rows $w_i \sim \mathcal{N}(0,I_k/n)$ and if $x_1 = x_2$ then $Q_{x_1,y_2}$ is an isometry up to the scaling factor $1/2$.
This condition ensures that the angle between two
vectors in the latent space is approximately preserved at the output layer and in turn guarantees the invertibility of the network. Under the Assumption \ref{hyp:randW}, \cite{hand2017global} shows that the WDC holds with high probability for all layers of the generative network $G$.

\begin{comment}
With these tools at our disposal we can now describe the landscape of the minimization problem \eqref{eq:minM} in a deterministic settings.
\begin{thm}\label{thm:dir_deriv}

Consider a generative network $G: \R^k \to \R^n$ as in \eqref{eq:Gx} and
the minimization problem \eqref{eq:minM} with unknown nonzero $\xstar$ and symmetric $H$.
Fix $\eps > 0$ such that $K_1 d^{16} \sqrt{\eps} \leq 1$ and let $d \geq 2$.
Suppose that $G$ satisfies the WDC with constant $\eps$ and assume that:
\begin{equation}\label{eq:noise}
\|\Lambda_x^\T H \Lambda_x \|_2 \leq \frac{\omega}{2^d}  \qquad \text{for all}\; x \in \R^k,
\end{equation}
with $2^d d^{12} w \leq K_2 \| \xstar \|^2$ and $K_2 < 1$.

Then for all $x \in \R^k$:
\begin{itemize}
\item if $x \notin \mathcal{B}(\xstar, r_+)~\cup~\mathcal{B}(-\rho_d \xstar, r_-)~\cup~\{0\}$ and \\$v_x \in \pa f(x)$:
\[
D_{-v_x} f(x) < 0
\]
where
$$r_+ = K_3 (d^4 {\eps^{1/2}} + 2^d \omega  \|\xstar\|_2^{-2}) d^{10} \|\xstar\|_2,
$$
and
$$r_- =  K_4 (d^2 {\eps}^{1/4} + 2^{d/2} \omega^{1/2} \|\xstar\|_2^{-1}) d^{10}  \|\xstar\|$$
\item if $x \in \mathcal{B}(0,  \|\xstar\|_2/16 \pi) \backslash \{0\}$  and $v_x \in \pa f(x)$ then $$\langle x, v_x\rangle < 0$$
while if $x = 0$ and $v \in \mathcal{S}^{k-1}$ then
$$D_{-v} f(0) = 0$$
\end{itemize}
Here $\rho_d$ is a positive number that converges to 1 as $d \to \infty$ and $K_1, \dots, K_4$.
\end{thm}

The deterministic version of Proposition \ref{prop:rand_localmin}.

\begin{prop}\label{prop:local_min}
Under the assumptions of Theorem \ref{thm:dir_deriv}, for any $\phi_d \in [\rho_d, 1]$, it holds that:
\begin{equation}\label{eq:localmin}
f(x) < f(y)
\end{equation}
for all $x \in \mathcal{B}(\phi_d \xstar, \varrho \|\xstar\| d^{-12})$ and $y \in \mathcal{B}(- \phi_d \xstar, \varrho  \|\xstar\| d^{-12})$ where $\varrho<1$ is a universal constant.
\end{prop}
\end{comment}

Next we observe that at a differentiable point the gradient of $f$, defined in \eqref{eq:minM}, is given by:
\begin{equation}\label{eq:gradx}
\nabla f(x) = \Lambda_x^\T [\Lambda_x x x^\T \Lambda_x^\T - M ] \Lambda_x x.
\end{equation}
Using the WDC, then, we demonstrate that $\nabla_x f(x)$ concentrates up to the noise level around a direction $h_x \in \R^k$ which is a continuous function of nonzero $x$ and $\xstar$.

Furthermore using the characterization \eqref{eq:subdiff} of the Clarke subdifferential,
we show that this concentration extends also at non-differentiable points for subgradients.

A direct analysis then shows that any directional derivative of $f$ at zero is zero and
that $h_x$ is small in a neighborhood
of $\xstar$ and its negative multiple $-\rho_d \xstar$. This in turn guarantees the existence of a descent direction in the complement of these sets.

Similarly, we use the WDC to show
that up to noise level, the loss function $f$ concentrates around:
\[
f_E(x) = \frac{1}{4} \Big( \frac{1}{2^{2d}} \|x\|^4_2 +  \frac{1}{2^{2d}} \|\xstar\|^4_2  - 2 \langle x, \tilde{h}_x\rangle^2 \Big).
\]
where $\htilde_{x,\xstar}$ is  continuous for nonzero $x$ and $\xstar$.
Directly analyzing the properties of $f_E$ in a neighborhood of $\xstar$ and $-\rho_d \xstar$ allows to derive the first point of Proposition \ref{prop:rand_localmin}. The last part of Proposition \ref{prop:rand_localmin} follows by noticing that the generator $G$ is locally Lipschitz.

Finally we extend a technique of \cite{HHHV18} to control
the noise term: in our case a Gaussian Orthogonal matrix $\mathcal{H}$ for the spiked Wigner model \eqref{eq:wigner_Y}, and the differene between the empirical and the population covariance $\Sigma_N - \Sigma$ for the spiked Wishart model.
The analysis is based on a counting argument on the subspaces spanned by a depth $d$ generative networks, which leads to the sought rate-optimal bounds.

config: arxiv


text:
\subsection{Heuristics for the MNL-MNL model}\label{sec:heuristic}

In this section, we provide heuristics for Problem \eqref{def:opt_problem} when both consumers and suppliers follow a general MNL model.
Formally, each consumer follows the model described in \eqref{eq:mnl_system}. On the other hand, each supplier $j\in V$ has a public score $u_{ji}$ for each $i\in N\cup\{0\}$, where $0$ is the outside option. Then, the choice model for supplier $j\in V$ corresponds to
\begin{equation}\label{eq:supplier_unif_system}
q_{ji}(A)= \frac{u_{ji}}{u_{j0}+\sum_{k\in A}u_{jk}}\cdot\one_{\{i\in A\cup\{0\}\}}, \qquad  A\subseteq N.
\end{equation}
Note that, the MNL-Uniform model described in Section \ref{sec:related_work} corresponds to $u_{ji} = 1$ for all $j\in V,\ i\in N$.

The main heuristics discussed in this section rely on the upper bound obtained in the following result.
\begin{lemma}\label{lemma:mnl_mnl_bound}
For every assortment family $S=(S_1,\ldots,S_n)$, we have
\begin{equation}\label{eq:mnl_supplier_bound}
\EE[\Ma_S]\leq \sum_{j\in V}r_j\cdot\frac{\sum_{i\in N}u_{ji}p_{ij}(S)\one_{\{j\in S_i\}}}{u_{j0}+\sum_{i\in N}u_{ji}p_{ij}(S)\one_{\{j\in S_i\}}}.
\end{equation}
\end{lemma}
\begin{proof}

For each $j\in V$, the demand function of the MNL model is $Q_j(A)= u_{j,A}/(u_{j0}+u_{j,A})$, where $u_{j,A} = \sum_{k\in A}u_{jk}$. Therefore, for any assortment family $S=(S_1,\ldots,S_n)$, Expression \eqref{eq:identity1} corresponds to
\[
\EE[\Ma_S] =  \sum_{j\in V}r_j\EE\left[Q_j(A^S_j)\right] = \sum_{j\in V}r_j\EE\left[\frac{u_{j,A^S_j} }{u_{j0}+u_{j,A^S_j} }\right],
\]
where $A^S_j$ denotes the random set of consumers that selected supplier $j$ under assortment family $S$. Observe that, for each $j\in V$, the demand function is concave on $u_{j,A^S_j}$. By using Jensen's inequality, we obtain
\[
\EE[\Ma_S] \leq  \sum_{j\in V}r_j\cdot\frac{\EE\left[u_{j,A^S_j}\right]}{u_{j0}+\EE\left[u_{j,A^S_j}\right]}.
\]
Finally, the result follows by noting that
\[
\EE\left[u_{j,A^S_j} \right] = \sum_{i\in N}u_{ji}\EE[\one_{\{i\in A^S_j\}}] = \sum_{i\in N}u_{ji}p_{ij}(S_i)\one_{\{j\in S_i\}}.
\]
\end{proof}

\begin{observation}
If suppliers follow the Uniform model, i.e. $u_{ji} = 1$ for all $i\in N, \ j\in V$, then Inequality \eqref{eq:mnl_supplier_bound} corresponds to
\[
\EE[\Ma_S]\leq \sum_{j\in V}r_j\cdot\frac{\eta_j(S)}{u_{j0}+\eta_j(S)},
\]
where $\eta_j(S) = \sum_{i\in N}p_{ij}(S_i)\one_{\{j\in S_i\}}$.
\end{observation}

In the following, our approach is similar to the one in Sections \ref{sec:mnl_unconstrained} and \ref{sec:mnl_card}. We will construct appropriate relaxations to obtain fractional assortments and then we use the corresponding randomized rounding techniques. The main difference with the previous Algorithms \ref{alg:lp_unconstrained} and \ref{alg:cardinality} is the objective function; instead of $\min\{1,z_j\}$, we use $z_j/(z_j + u_{j0})$.
First, let us study the unconstrained setting. Consider the following concave problem:
\begin{align}\label{eq:mnlmnl_concave_unconstrained}
\max_{y,w,z} &\quad \sum_{j\in V} r_j\cdot\frac{z_j}{z_j+u_{j0}}   \\
s.t. &\quad  z_j= \sum_{i\in N}u_{ji}v_{ij}y_{ij}, \hspace{4em} \forall \ j\in V, \notag\\
&\quad w_i+\sum_{j\in V}v_{ij}y_{ij} = 1, \qquad \forall \ i \in N, \notag\\
&\quad 0 \leq y_{ij} \leq w_i, \hspace{4.8em} \forall \ i\in N, \ j\in V. \notag
\end{align}
Note that the objective function is coordinate-wise concave, therefore \eqref{eq:mnlmnl_concave_unconstrained} is tractable. Denote by $\OPT_{\eqref{eq:mnlmnl_concave_unconstrained}}$ the optimal value of \eqref{eq:mnlmnl_concave_unconstrained}. Note that any feasible solution for Problem \eqref{def:opt_problem} defines a feasible solution for \eqref{eq:mnlmnl_concave_unconstrained}. More importantly, Lemma \ref{lemma:mnl_mnl_bound} implies that $\OPT\leq \OPT_{\eqref{eq:mnlmnl_concave_unconstrained}}$.

The main algorithm for the unconstrained case is given in Algorithm \ref{alg:mnl_concave_unconstrained}.
\begin{algorithm}
\caption{Algorithm for the MNL-MNL model}\label{alg:mnl_concave_unconstrained}
\begin{algorithmic}[1]
\Require  Set of consumers $N$, set of suppliers $V$, scores $[v_{ij}]_{i\in N,j\in V}$, scores $[u_{j0}]_{j\in V}$ and revenues $r_1,\ldots,r_m\in\RR_+$.
\Ensure Assortment family $(S_1,\ldots, S_n)$.
\State Solve \eqref{eq:mnlmnl_concave_unconstrained} and let $(y^*,w^*,z^*)$ be its optimal solution. Let  $x_{ij} = y^*_{ij}/w^*_i$ for all $i\in N, \ j\in V$.
\State Obtain $\hat{x}\in\{0,1\}^{N\times V}$ by independent randomized rounding from $x$, i.e., independently for all $i\in N, \ j\in V$ assign $\hat{x}_{ij} = 1$ with probability $x_{ij}$ and zero with probability $1-x_{ij}$.
\State Set $S_i = \{j\in V: \ \hat{x}_{ij} = 1\}$ for all $i\in N$.
\end{algorithmic}
\end{algorithm}

For the cardinality constrained setting, our heuristic uses the cardinality constrained version of relaxation \eqref{eq:mnlmnl_concave_unconstrained}. Formally, consider the following concave problem:
\begin{align}\label{eq:mnl_concave_card}
\max_{y,w,z} &\quad \sum_{j\in V} r_j\cdot\frac{z_j}{z_j+u_{j0}}   \\
s.t. &\quad  z_j= \sum_{i\in N}u_{ji}v_{ij}y_{ij}, \hspace{4em} \forall \ j\in V, \notag\\
&\quad w_i+\sum_{j\in V}v_{ij}y_{ij} = 1, \qquad \forall \ i \in N, \notag\\
&\quad \sum_{j\in V}y_{ij} \leq K_iw_i, \hspace{2em} \qquad \forall \ i \in N, \notag\\
&\quad 0 \leq y_{ij} \leq w_i, \hspace{4.8em} \forall \ i\in N, \ j\in V. \notag
\end{align}
Note that any feasible solution for Problem \eqref{def:opt_problem} under cardinality constraints defines a feasible solution for \eqref{eq:mnl_concave_card}. More importantly, Lemma \ref{lemma:mnl_mnl_bound} implies that $\OPT\leq \OPT_{\eqref{eq:mnl_concave_card}}$.
The main procedure is given in Algorithm \ref{alg:mnl_mnl_cardinality}.
\begin{algorithm}
\caption{Algorithm for the MNL-MNL model under Cardinality Constraints}\label{alg:mnl_mnl_cardinality}
\begin{algorithmic}[1]
\Require  Set of consumers $N$, set of suppliers $V$, scores $[v_{ij}]_{i\in N,j\in V}$, scores $[u_{ji}]_{j\in V,i\in N\cup\{0\}}$, revenues $r_1,\ldots,r_m\in\RR_+$ and budget vector $(K_1,\ldots,K_n)\in\ZZ^n_+$.
\Ensure Assortment family $(S_1,\ldots, S_n)$ such that $|S_i|\leq K_i$ for all $i\in N$.
\State Solve \eqref{eq:mnl_concave_card} and let $(y^*,w^*,z^*)$ be its optimal solution. Let  $x_{ij} = y^*_{ij}/w^*_i$ for all $i\in N, \ j\in V$.
\State Independently for all $i\in N$, obtain $\hat{x}_i\in\{0,1\}^{V}$ by doing dependent rounding with input $x_i\in[0,1]^V$.
\State Set $S_i = \{j\in V: \ \hat{x}_{ij} = 1\}$ for all $i\in N$.
\end{algorithmic}
\end{algorithm}

To empirically solve \eqref{eq:mnlmnl_concave_unconstrained} and \eqref{eq:mnl_concave_card}, we can easily adapt the conic reformulation given in Appendix \ref{sec:conic_relaxation}.