On the Optimization Landscape of Maximum Mean Discrepancy

Itai Alon Amir Globerson Ami Wiesel Hebrew University of Jerusalem Tel Aviv
University Hebrew University of Jerusalem

###### Abstract

Generative models have been successfully used for generating realistic
signals. Because the likelihood function is typically intractable in most of
these models, the common practice is to use “implicit” models that avoid
likelihood calculation. However, it is hard to obtain theoretical guarantees
for such models. In particular, it is not understood when they can globally
optimize their non-convex objectives. Here we provide such an analysis for the
case of Maximum Mean Discrepancy (MMD) learning of generative models. We prove
several optimality results, including for a Gaussian distribution with low
rank covariance (where likelihood is inapplicable) and a mixture of Gaussians.
Our analysis shows that that the MMD optimization landscape is benign in these
cases, and therefore gradient based methods will globally minimize the MMD
objective.

##  1 Introduction

Generative models are parameterized distributions that are trained to match
the distribution of observed data. Although generative modeling approaches
have achieved impressive results, little is known about theoretical properties
of training such models. In particular, when does training converge to a good
approximation of the underlying distribution, and how many samples are
required for such an approximation.

Due to its practical importance, the problem of generative modeling has
received considerable attention. Most generative methods model the data via a
distribution $P(x;\theta)$ that depends on a parameter $\theta$ to be
estimated from observed data. A key approach in this context is maximum
likelihood estimation (MLE), which maximizes $\log{P(x;\theta)}$ with respect
to the parameter. However, in more complex models it is typically hard to
calculate the probability of a given point, and thus MLE is not directly
applicable. Another route that has turned out to be very effective is via
“implicit” models. These do not use likelihood directly, but rather generate a
sample from the model distribution (since sampling is typically easy) and use
some divergence measure to compare the generated and real sample.

There are many instances of implicit models, including Generative Adversarial
Networks (GAN, [Goodfellow et al., 2014]), Wassertsein GAN [Gulrajani et al.,
2017], and Maximum Mean Discrepancy (MMD) based methods which we focus on
here. All of these employ a function that takes as input two samples and
return a scalar that reflects the “statistical distance” between these. For
example in GANs this is calculated as the minimum loss of a classifier trained
to discriminate between the samples.

MMD is essentially a measure of similarity between two distributions [Gretton
et al., 2012, Sutherland et al., 2017, Wang et al., 2018]. It measures
similarity by considering a set of functions $f(x)$ (specified by a kernel),
and checking how different their expected values are for the two
distributions. MMD has several nice properties, including the fact that it is
zero if and only if the two distributions are equal, that it does not require
min-max optimization and that it can be calculated from samples and does not
require explicit likelihood calculations. MMD is also closely related to WGAN
[Gulrajani et al., 2017], where the functions $f(x)$ are optimized over.

Despite their widespread use, little is known about the theoretical properties
of MMD based learning of generative models, and in particular its optimization
properties. In this paper, we provide a study of MMD learning for an important
instance of generative models. We begin with Gaussian distributions, which
already introduce non-convexity into the MMD optimization problem. We then
continue to the more challenging case of mixtures of Gaussian distributions,
which capture the multimodal structure that is key to complex generative
models. From a theoretical perspectives these models are interesting, since
they are generally intractable for maximum-likelihood, but are efficiently
learnable under certain conditions [Daskalakis et al., 2017] which we also
focus on here. Finally, Gaussian mixtures are already challenging for GAN
models [Farnia et al., 2020], further motivating a theoretical understanding
of when they can be learned effectively.

Our contribution: We analyze the landscape of MMD optimization for the setting
of population loss of possibly singular multivariate Gaussians and mixture of
two symmetric Gaussians. We show that in these cases, the landscape is benign,
implying that gradient descent will converge to a global optimum. We support
our theoretical findings with empirical evaluation.

###  1.1 Related Work

MMDs are an instance of Integral Probability Metrics (IPM) [Müller, 1997]
which measure distance between distributions via the difference of expected
values of certain functions. MMD was originally used in the field of machine
learning for two sample tests, and much work was devoted to the power of these
tests [Gretton et al., 2012].

With the growing interest in neural based generators, it became clear that
MMDs can also be used for learning such models. This is due to the fact that
MMDs can work directly on samples, and do not require likelihood computations.
Many different modeling schemes involving MMD have been introduced, including
Moment Matching Networks [Li et al., 2015, Dziugaite et al., 2015] and MMD-
GANs [Li et al., 2017], as well as variational autoencoders [Rustamov, 2019].
Some MMD based approaches also allow some learning of the kernel parameters to
provide better flexibility with respect to the generating distribution [Li et
al., 2017, Li et al., 2015, Bińkowski et al., 2018, Dziugaite et al., 2015,
Sutherland et al., 2017, Wang et al., 2018].

MMDs have been well studied from a statistical perspective. Namely, the number
of samples needed for an MMD generative modeling method in order to
approximate the true underlying parameters. In this context, there are two
relevant sample sizes: those sampled from the true distribution and those
sampled from the model. Such analyzes for dependence between the number of
samples used and the ability of the MMD metric to recover the true
distribution see [Tolstikhin et al., 2016, Ji and Liang, 2018].

Optimization of MMD measures has been recently studied in several works [Arbel
et al., 2019, Mroueh and Nguyen, 2021] where gradient flow formalisms for MMD
were studied towards the goal of improved regularization and stability of the
optimization. However, they do not study optimization of specific parameteric
models as we do here, and do not provide related landscape results.

Since we consider learning Gaussian mixtures, our work is also related to the
long line of work on parameter estimation in mixture models. It is known that
learning a mixture of $k$ Gaussians can be done in time polynomial in the
dimension and exponential in $k$ [Moitra and Valiant, 2010]. Thus, the $k=2$
case which we study here is tractable (using variants of moment matching
techniques), which motivates the question of whether it can be learned using
MMD GANs. Furthermore, it was also shown that EM can efficiently learn the
parameters in this case [Daskalakis et al., 2017]. The landscape of the
likelihood function in this case was also explored in [Jin et al., 2016],
where it was shown to have bad local minima for mixtures of three or more
Gaussians.

Our main focus in this work is the optimization landscape of MMD. The question
of optimization guarantees for “implicit” generative models is important due
to the many practical applications of optimizing these model. However, not
many results have been obtained. In [Feizi et al., 2017] it was shown that a
Gaussian with unknown full-rank covariance is globally optimizable using a
quadratic version of a WGAN (see Section 3.2). In [Li et al., 2018] it was
shown that GAN optimization can fail to find the right model because of
instabilities related to discriminator optimization. There has also been study
of the ascent-descent algorithms which underlie GAN optimization [Daskalakis
and Panageas, 2018], but mostly showing convergence to local optima. Finally,
[Lei et al., 2020] study WGAN optimization for a one hidden layer generative
model. Their setting is related to our unknown covariance result (because if
one ignores the non-linearity in their case, their model is a Gaussian with
unknown covariance). However, our main challenge is the low-rank of the
covariance, whereas in their case it is full rank (see Theorem 3 in [Lei et
al., 2020] which requires $k=d$).

##  2 Problem Setup

Let $P_{\theta}(x)$ denote a distribution on a random variable $X$, which is
defined via a parameter vector $\theta$. For example $P_{\theta}(x)$ could be
a Gaussian distribution with mean $\theta$. We consider the parameter
estimation problem where data is generated i.i.d from some $P_{\theta^{*}}$
and our goal is to recover $\theta^{*}$ from these observation. We let $Y$
denote the data generated from $P_{\theta^{*}}$.

We assume access to a generator that allows us to draw a synthetic dataset of
i.i.d samples $X\sim P_{\theta}$ for any given $\theta$. Thus, we would like
to find a $\theta$ such that $X\sim P_{\theta}$ is as close as possible to
$Y$.

As mentioned above, MMD is often used to measure the distance between the
generated sample $X$ and the “true” sample $Y$, as a function of $\theta$. Our
goal here is to understand the optimization landscape of this problem. To
simplify analysis, we focus on the population case, where the size of both the
$X$ and $Y$ samples goes to infinity. In this case, the MMD distance is given
by the following:111More precisely, MMD is formally defined as the squared
root of the formula in (1).

$\text{MMD}(\theta,\theta^{*})=\operatorname*{\mathbb{E}}_{X,X^{\prime}\overset{i.i.d.}{\sim}P_{\theta}}[k(X,X^{\prime})]\\\
+\operatorname*{\mathbb{E}}_{Y,Y^{\prime}\overset{i.i.d.}{\sim}P_{\theta^{*}}}[k(Y,Y^{\prime})]-2\operatorname*{\mathbb{E}}_{\begin{subarray}{c}X\sim
P_{\theta}\\\ Y\sim P_{\theta^{*}}\\\ i.i.d.\end{subarray}}[k(X,Y)]$ (1)

where $k$ is a characteristic kernel function (over reproducing kernel Hilbert
space). For simplicity, we focus on the Gaussian RBF kernel:

$k(x,y)=e^{-\frac{1}{2\sigma^{2}}\left\|x-y\right\|^{2}}$ (2)

where $x,y\in\mathbb{R}^{d}$ and $\sigma^{2}$ is a width hyperparameter. The
MMD optimization problem is: $\min_{\theta}\text{MMD}(\theta,\theta^{*})$. It
is the landscape of this problem that we would like to understand.
Specifically, we would like to understand when optimization methods are
expected to converge to $\theta=\theta^{*}$ and not get stuck at local optima.

The statistical properties of MMD are well understood. Due to the
characteristic kernel, MMD is a distance function, i.e., $\theta^{*}=\theta$
if and only if $\text{MMD}=0$. To enjoy these statistical benefits in large
scale, MMD must be numerically minimized using first order descent methods.
Unfortunately, the loss is usually non-convex, and it is not clear whether its
optimization is tractable. It is well known that gradient descent with a
random initialization and sufficiently small constant step size almost surely
converges to a local minimizer [Lee et al., 2016, Jin et al., 2017, Sun et
al., 2015]. Formally, convergence requires the “strict saddle property”
defined below. Thus, to ensure convergence to $\theta^{*}$ we need to prove
that MMD satsifies the property and that all of its local minimizers are
indeed equivalent to $\theta^{*}$.

######  Definition 1 ([Lee et al., 2016]).

A function $f(\theta)$ satisfies the “strict saddle property” if each critical
point $\theta$ of $f$ is either a local minimizer, or a “strict saddle”, i.e,
its Hessian $\nabla^{2}f(\theta)$ has at least one strictly negative
eigenvalue.

The next subsections provide this analysis for three fundamental estimation
models.

##  3 Theoretical Results

We next consider three parameter estimation problems, and show that MMD has a
benign landscape for those. Namely, the MMD objective has no local minima and
all its saddle-points are strict. This implies that gradient based methods can
find a global optimum [Lee et al., 2016]. We focus on the cases of Gaussian
with an unknown mean (Sec. 3.1), Gaussian with unknown low-rank covariance
(Sec. 3.2) and a mixture of Gaussians with unknown means (Sec. 3.3).

###  3.1 Gaussian with Unknown Mean

We begin with probably the simplest parameter estimation problem, namely a
Gaussian distribution with unknown mean and a known covariance matrix. This
problem is trivially solved by MLE. The negative log likelihood is strongly
convex and its global minimum, the sample mean, can be efficiently found using
GD. The following theorem states that the landscape of MMD is also benign in
this case and can be minimized to identify the true mean.

######  Theorem 1.

Let $P_{\mu}=\mathcal{N}(\mu,\Sigma)$ with an unknown $\mu^{*}$ parameter. The
function $\text{MMD}(\mu^{*},\mu)$ is given by:

$\frac{2}{\sqrt{\left\lvert
2\frac{1}{\sigma^{2}}\Sigma+I\right\rvert}}\left(1-e^{-\frac{1}{2}\frac{1}{\sigma^{2}}(\mu-\mu^{*})^{T}(2\frac{1}{\sigma^{2}}\Sigma+I)^{-1}(\mu-\mu^{*})}\right)~{}.$
(3)

It is a quasi-convex function of $\mu$, and has a single stationary point at
$\mu=\mu^{*}$, which is the global minimum.

###### Proof.

We rely on the following integral (see Supplementary Material, Lemma 4):

$\int_{\mathbb{R}^{d}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\left\|z\right\|^{2}}\cdot\mathcal{N}(z;\mu,\Sigma)dz\\\
=\left\lvert\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{-\frac{1}{2}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\mu^{T}(\frac{1}{\sigma^{2}}\Sigma+I)^{-1}\mu}$
(4)

We compute each expectation in (1) separately. If
$X,X^{\prime}\sim\mathcal{N}(\mu,\Sigma),Y,Y^{\prime}\sim\mathcal{N}(\mu^{*},\Sigma)$
are independent, then $X-Y\sim\mathcal{N}(\mu-\mu^{*},2\Sigma)$, and
$X-X^{\prime}$, $Y-Y^{\prime}\sim\mathcal{N}(0,2\Sigma)$. Using (4) we have
that $\operatorname*{\mathbb{E}}[k(X,Y)]$ is equal to:

$\frac{1}{\left\lvert
2\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}(\mu-\mu^{*})^{T}(2\frac{1}{\sigma^{2}}\Sigma+I)^{-1}(\mu-\mu^{*})}$
(5)

and:
$\operatorname*{\mathbb{E}}[k(X,X^{\prime})]=\operatorname*{\mathbb{E}}[k(Y,Y^{\prime})]=\frac{1}{\left\lvert
2\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{\frac{1}{2}}}$. We sum the
expectations to get the final MMD expression. To prove quasi-convexity it
suffices to observe that a negative definite quadratic form is concave and
thus also quasi-concave. Composition with a non-decreasing function preserves
quasi-convexity, and taking the negative again yields a quasi-convex function.
∎

The theorem implies that standard descent methods on MMD can easily find the
unknown Gaussian mean just like MLE. Note however that MLE is strongly convex
whereas MMD is quasi-convex as illustrated in Figure 1. The gradient vanishes
if we initialize the algorithm too far from the true $\mu^{*}$ and the
optimization is much harder. On the other hand, MMD has a width hyperparameter
that can be used to widen the convex region of the landscape. For example, if
we know a priori that $\mu^{*}$ is within a ball of radius $r$ around the
initial point, then choosing a width $\sigma^{2}\geq 2r$ ensures a strongly
convex objective where GD converges linearly.

Figure 1: MMD loss of Gaussian over $\mathbb{R}$ with unknown mean. Different
widths $\sigma^{2}$ and $\mu^{*}=0$.

###  3.2 Gaussian with Unknown Covariance

Our second model is a zero mean multivariate normal with an unknown singular
covariance matrix. This is a more challenging setting which is more
representative of modern deep learning problems where an MLE does not exist.
Even in the near-singular case, GD on the MLE loss is very slow, because the
problem is ill conditioned. The standard adversarial GAN also fails in this
task [Cho and Suh, 2019]. For WGAN, it has been shown that its global optimum
is correct (e.g., see [Feizi et al., 2017, Cho and Suh, 2019] for two results
in this flavor). However, it was not shown that this optimum can be found
using gradient descent, and in fact [Feizi et al., 2017] (Theorem 5) points to
a failure of optimization in this case.

The following theorem states that the landscape of MMD in this model is
benign. The constant $\epsilon$ determines the level of covariance non-
singularity, and results also hold for $\epsilon=0$. We consider the case of
rank one, since it captures the most “extreme” low-rank scenario.

######  Theorem 2.

Consider the parametric model:

$P_{a}=\mathcal{N}(0,a{a}^{T}+\varepsilon^{2}I)$ (6)

with an unknown $a\in\mathbb{R}^{d}$ parameter. Assume training data is
generated from $P_{a^{*}}$. The MMD objective is

$\text{MMD}({a^{*}},a)=\\\
\frac{1}{\left\lvert\frac{1}{\sigma^{2}}(2aa^{T}+2\varepsilon^{2}I)+I\right\rvert^{\frac{1}{2}}}+\frac{1}{\left\lvert\frac{1}{\sigma^{2}}(2a^{*}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{\frac{1}{2}}}\\\
-\frac{2}{\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+a^{*}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{\frac{1}{2}}}$
(7)

It has global minima in $\pm a^{*}$, a maximum in $a=0$, and the rest of the
stationary points are (if the radius exists)

$\left\\{a\ :\begin{array}[]{l}a^{T}a^{*}=0\\\
\left\|a\right\|^{2}=\frac{(2\varepsilon^{2}+\sigma^{2})\left((\left\|a^{*}\right\|^{2}+2\varepsilon^{2}+\sigma^{2})^{\frac{1}{3}}-(2\varepsilon^{2}+\sigma^{2})^{\frac{1}{3}}\right)}{2(2\varepsilon^{2}+\sigma^{2})^{\frac{1}{3}}-(\left\|a^{*}\right\|^{2}+2\varepsilon^{2}+\sigma^{2})^{\frac{1}{3}}}\end{array}\right\\}$
(8)

and are all strict saddles.

###### Proof.

The derivation of (7) is straight forward using (4) for each expectation.

To simplify the landscape analysis, we rotate the space and assume w.l.o.g
that $a^{*}=e_{1}$ is the first unit vector with $\left\|a^{*}\right\|^{2}=1$.
Denoting $c:=2\varepsilon^{2}+\sigma^{2}$, Lemma 5 in the Supplementary
Material provides the gradient:

$0=\nabla\text{MMD}(P_{a^{*}},P_{a})\propto-\left\lvert
2aa^{T}+cI\right\rvert^{-\frac{3}{2}}a\\\ +\left\lvert
aa^{T}+{a^{*}}{a^{*}}^{T}+cI\right\rvert^{-\frac{3}{2}}(1+c)({a^{*}}{a^{*}}^{T}+cI)^{-1}a$
(9)

Rearranging and isolating $a$ yields

$({a^{*}}{a^{*}}^{T}+cI)^{-1}a=\frac{\left\lvert
aa^{T}+{a^{*}}{a^{*}}^{T}+cI\right\rvert^{\frac{3}{2}}}{\left\lvert
2aa^{T}+cI\right\rvert^{\frac{3}{2}}}(1+c)^{-1}a$ (10)

The critical points are all the solutions to this linear system. These are the
eigenvectors of $({a^{*}}{a^{*}}^{T}+cI)^{-1}$. Using Woodbury’s identity:

$\left(a^{*}{a^{*}}^{T}+cI\right)^{-1}=c^{-1}I-c^{-1}(1+c)^{-1}{a^{*}}{a^{*}}^{T}$

It easy to see that one solution is $a=t\cdot a^{*}$. Together with equation
(10) one can conclude that $t=\pm 1$. Moreover, $a=\pm a^{*}$ yields a zero
loss, and because MMD is non-negative we also conclude that these are global
minima. The origin $a=0$ is a trivial solution, and by placing zero in the
Hessian (Lemma 6) it is clearly a maxima. All the other $d-1$ eigenvectors are
in the orthogonal hyperplane of $a^{*}$. Plugging $a\perp a^{*}$ into (10) we
get after some algebra:

$c^{-1}a=\frac{\left((\left\|a\right\|^{2}+c)(1+c)\right)^{\frac{3}{2}}}{\left((2\left\|a\right\|^{2}+c)c\right)^{\frac{3}{2}}}(1+c)^{-1}a$
(11)

For $a\neq 0$ this leads to

$\left\|a\right\|^{2}=\frac{c\left((1+c)^{\frac{1}{3}}-c^{\frac{1}{3}}\right)}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}$
(12)

In the Supplementary Material we prove that (12) ensures
${a^{*}}^{T}Ha^{*}<0$. Thus, $a^{*}$ is a descent direction and the orthogonal
stationary points are not minima. ∎

The theorem proves that the landscape of MMD with unknown covariance is
benign. Figure 2 illustrates this in a one dimensional setting. As before, it
can be seen that there are no bad local minima, yet the gradient vanishes as
we move further from $a^{*}$.222This happens for the case $\sigma^{2}=0.1$ for
larger $a$ values. If we assume that the true parameters lie within a ball of
known radius then it is easy to bound
$\left\|\nabla^{2}\text{MMD}(a)\right\|_{2}^{2}$ from above and use the
results in [Lee et al., 2016] to prove convergence of GD to $a^{*}$ (see
Supplementary).

Figure 2: MMD loss of Gaussian over $\mathbb{R}$ with unknown covariance,
different widths $\sigma^{2}$ and $a^{*}=1$.

###  3.3 Mixture of Two Gaussians with Unknown Mean

We next study Gaussian mixture models with symmetric unknown means. MLE
optimization in general GMMs is known to be non-convex and NP-hard [Aloise et
al., 2009]. Three component GMMs can be hard even for MLE with infinitely many
samples [Jin et al., 2016]. The symmetric case is much easier and can be
optimized efficiently using an Expectation Maximization algorithm [Daskalakis
et al., 2017]. In terms of likelihood-free estimators, GANs are known to fail
in GMMs and special purpose discriminators are required [Farnia et al., 2020].
Remarkably, the following theorem shows that landscape of MMD is benign in
this case.

######  Theorem 3.

Consider the following family of distributions where $x\in\mathbb{R}^{d}$

$p(x)=0.5\cdot\mathcal{N}(x;\mu,\Sigma)+0.5\cdot\mathcal{N}(x;-\mu,\Sigma)$
(13)

Let $\mu^{*}\neq 0$ be an unknown parameter and $\Sigma\in\mathbb{R}^{d\times
d}$ a known covariance matrix. Then,

$\text{MMD}(P_{\mu^{*}},P_{\mu})=\\\
\frac{1}{2}\frac{\sigma^{d}}{\sqrt{\left\lvert
2\Sigma+\sigma^{2}I\right\rvert}}\Big{[}e^{-\frac{1}{2}(2\mu)^{T}(2\Sigma+\sigma^{2}I)^{-1}(2\mu)}+1\\\
+e^{-\frac{1}{2}(2\mu^{*})^{T}(2\Sigma+\sigma^{2}I)^{-1}(2\mu^{*})}+1\\\
-2\cdot
e^{-\frac{1}{2}(\mu-\mu^{*})^{T}(2\Sigma+\sigma^{2}I)^{-1}(\mu-\mu^{*})}\\\
-2\cdot
e^{-\frac{1}{2}(\mu+\mu^{*})^{T}(2\Sigma+\sigma^{2}I)^{-1}(\mu+\mu^{*})}\Big{]}$
(14)

The function $\text{MMD}(P_{\mu^{*}},P_{\mu})$ has global minima in
$\pm\mu^{*}$, a global maximum in $0$, and the other stationary points are

$\left\\{\mu:\begin{array}[]{l}\mu^{T}(2\Sigma+\sigma^{2}I)^{-1}\mu^{*}=0\\\
\mu^{T}(2\Sigma+\sigma^{2}I)^{-1}\mu={\mu^{*}}^{T}(2\Sigma+\sigma^{2}I)^{-1}\mu^{*}\end{array}\right\\}$
(15)

and are all strict saddles.

###### Proof.

By defining $\mu:=\Sigma^{-\frac{1}{2}}\mu$, we can consider w.l.o.g the case
of $\Sigma=I$. Define $c=2+\sigma^{2}$. To analyze the landscape, we
differentiate MMD and compare to zero:

$0=\nabla\text{MMD}(P_{\mu^{*}},P_{\mu})\propto
e^{-\frac{1}{2}c^{-1}\left\|\mu-\mu^{*}\right\|^{2}}(\mu-\mu^{*})\\\
+e^{-\frac{1}{2}c^{-1}\left\|\mu+\mu^{*}\right\|^{2}}(\mu+\mu^{*})-2e^{-\frac{1}{2}c^{-1}\left\|2\mu\right\|^{2}}\mu$
(16)

which holds when either (A) $\mu=t\cdot\mu^{*}$ for some $t\in\mathbb{R}$; or
(B) when the coefficients vanish.

In case (A), denoting
$\alpha=e^{-\frac{1}{2}c^{-1}\left\|\mu^{*}\right\|^{2}}$, the derivative as a
function of $t$ is given by

$\nabla\text{MMD}(P_{\mu^{*}},P_{t\cdot\mu^{*}})\propto\\\
(t-1)\cdot\alpha^{(t-1)^{2}}+(t+1)\cdot\alpha^{(t+1)^{2}}-2t\cdot\alpha^{4t^{2}}$
(17)

which is zero in $t\in\\{-1,0,1\\}$, where by exploration of ascent and
descent areas $\pm 1$ are minima, and $0$ is a local maximum: $g(t)<0$ for
$t\in(-\infty,-1)\cup(0,1)$, $g(t)>0$ for $t\in(-1,0)\cup(1,\infty)$ and
$g(t)=0$ for $t\in\\{-1,0,1\\}$.

In case (B), the coefficients vanish when

$\displaystyle\left\|\mu-\mu^{*}\right\|^{2}=\left\|\mu+\mu^{*}\right\|^{2}$
$\displaystyle\left\|\mu-\mu^{*}\right\|^{2}+\left\|\mu+\mu^{*}\right\|^{2}=4\left\|\mu^{*}\right\|^{2}$
(18)

Thus,

$\mu^{T}\mu^{*}=0,\qquad\left\|\mu^{*}\right\|^{2}=\left\|\mu\right\|^{2}$
(19)

To characterize $\mu$ in this case, we compute the Hessian and plugging (19)
yields:

$H=2\left(e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}-e^{-2c^{-1}\left\|\mu^{*}\right\|^{2}}\right)c^{-1}I\\\
-2e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}c^{-2}[\mu\mu^{T}+\mu^{*}{\mu^{*}}^{T}]\\\
+8e^{-2c^{-1}\left\|\mu^{*}\right\|^{2}}c^{-2}\mu\mu^{T}$ (20)

Then, it is easy to see that $\mu^{*}$ is an eigenvector and its corresponding
eigenvalue is negative. The full details are available in the Supplementary
Material. ∎

The benign landscape of MMD in a symmetric GMM is illustrated in Figure 3. As
before, MMD suffers from vanishing gradient far from the origin. With poor
width choices, there are also troubling deflection points which have small yet
non-zero gradients. If we restrict the attention to a ball around the origin
and tune the width parameter accordingly, then we can upper bound the Hessian
and use the results of [Lee et al., 2016] to prove convergence.

Figure 3: MMD loss of GMM over $\mathbb{R}$ with different widths $\sigma^{2}$
and $\mu^{*}=25$. Note that in $\sigma^{2}=10^{1}$ around $\mu=\pm 8.5$ there
are inflection points. The derivatives at these points are small but non-zero.

##  4 Experiments

The results above show that MMD is expected to converge globally for the three
distributions we consider. As mentioned earlier, MLE optimization also has
such guarantees (except for the singular covariance case). However, no such
results are available for WGAN. Here we report empirical evaluations that are
in line with these observations. In all cases we denote by
$y_{1},\ldots,y_{m}$ the sample from the true distribution (with parameters
$\theta^{*}$).

We consider the following approaches to learning the generative models we
analyzed:

  * •

MMD: This is the standard implementation of the MMD approach. Here, at each
iteration a “fake” sample $x_{1},\ldots,x_{n}$ is generated from the current
parameter estimate $\theta$ and the following finite-sample version of the MMD
loss (see (1)) is optimized:333The bandwidth is chosen via holdout from range
of powers of ten.

$\text{MMD}_{m,n}=\frac{1}{n\cdot(n-1)}\sum_{i\neq j}k(x_{i},x_{j})\\\
+\frac{1}{m\cdot(m-1)}\sum_{i\neq j}k(y_{i},y_{j})-\frac{2}{n\cdot
m}\sum_{i,j}k(x_{i},y_{j})$ (21)

  * •

One-Sided MMD (OSMMD): Because we consider Gaussian distributions it is
possible to take the limit of $m\to\infty$ and compute the integrals in closed
form (this is essentially what we do in the analysis of the landscape). Thus,
OSMDD is defined as in (21) but with $n=\infty$ via an analytically computed
expectation.

  * •

Maximum Likelihood Estimation (MLE): Here we maximize the standard log-
likelihood function.

  * •

Wasserstein GAN (WGAN): This is the standard WGAN implementation where
generator parameters and discriminator parameters are trained via gradient
descent-ascent. The discriminator is structured as linear in the Gaussian mean
experiment and as a two layers with ReLU activation function in the other
experiments. The hidden dimension is chosen to be the lowest power of two
which is greater than the problem dimension.

Implementation details: All experiments run on Pytorch using Adam with
learning rate $10^{-1}$. All the algorithms use a full batch of real samples.
MMD and WGAN use $n=m$ fake samples which are independently generated in each
epoch.

###  4.1 Gaussian with Unknown Mean

We first consider the estimation of an unknown mean as in Sections 3.1 and
3.3. In each simulation, we compute the distance
$\left\|\mu-\mu^{*}\right\|/d$ and report the number of times this distance is
less than $0.02$.

Figure 4: Success rate in a Gaussian model with unknown mean as a function of
$m$. OSMMD and MLE coincide.

Figure 5: Success rate in a 2-GMM model with unknown mean as a function of
$m$. OSMMD and MLE coincide.

Results are shown in Figure 4. As expected, MLE easily succeeds to recover the
unknown parameter. Among the implicit likelihood-free generators, MMD
significantly outperforms WGAN, apparently because of optimization failure of
the latter. OSMMD coincides with MLE and suggests that the gap to optimality
can be eliminated by increasing $n$. Similar results and conclusions are
provided in Figure 5 for a symmetric GMM with unknown mean.

###  4.2 Gaussian with Unknown Covariance

We next consider the estimation of an unknown near-singular covariance
$a^{*}{a^{*}}^{T}+\varepsilon^{2}I$. This is more representative of deep
neural nets which model low-dimensional data manifolds. Furthermore, for the
case $\epsilon=0$ the MLE estimator does not exist, and thus it is of
particular interest to understand other estimators.

In the figures, we measure the accuracy of a parameter estimation method as
the fraction of cases where $\|aa^{T}-{a^{*}}{a^{*}}^{T}\|/d\leq\gamma$ where
$\gamma$ is a threshold and $\gamma=0.5\cdot 10^{-1}$ for the single Gaussian
case and $\gamma=1\cdot 10^{-1}$ for the GMM.

We begin by verifying the intuition that MLE’s success depends on the
singularity parameter $\varepsilon$. In Figure 6 we compare the performance of
MMD and MLE as parameter of $\varepsilon$. Theoretically, MLE does not exist
for $\varepsilon=0$ and the graph clearly shows that it fails to recover the
unknown covariance also in the near-singular case. Both algorithms use the
same number of iterations and learning rate.

Figure 7 shows the performance of the baselines for the covariance estimation
problem with zero mean. MLE fails in all the experiments due to the small
$\varepsilon=1\cdot 10^{-5}$. OSMMD is significantly better than all the
methods, and the more realistic MMD is second best. WGAN performs worse than
the MMD baselines and also requires significant hyperparameter tuning.

We next consider the case of unknown covariance, but with a mixture of two
Gaussians. Namely the model:

$p(x)=0.5\sum_{z\in\\{-1,+1\\}}\mathcal{N}(x;z\mu,a^{*}{a^{*}}^{T}+\varepsilon^{2}I)$

where $\mu$ and $\varepsilon$ are known. Figure 8 shows the results for this
case, and the qualitative behavior is similar to that of a single Gaussian. We
note that for WGAN we explored a wide range of parameter settings (step sizes,
initialization, optimization algorithms and architectures), and yet its
performance could not be improved beyond that reported.

Figure 6: MLE vs MMD as a function of $\varepsilon$ for covariance estimation.
See Equation (6).

Figure 7: Success rate in a Gaussian model with unknown covariance as a
function of $m$.

Figure 8: Success rate in a 2-GMM model with unknown covariance as a function
of $m$.

###  4.3 Linear Unmixing

We conclude the experiments with a more challenging linear unmixing setting
involving continuous hidden variables [Bioucas-Dias et al., 2012, Nascimento
and Dias, 2005]. Accurate evaluation of the likelihood function in such models
involves a high dimensional integration, and MLE is usually computationally
expensive. The underlying model is:

$\displaystyle x_{i}$ $\displaystyle=Ab_{i}+w_{i}\ ,\
b_{i}={\mathcal{D}}{\rm{irichlet}}(1_{r})$ $\displaystyle w_{i}$
$\displaystyle={\mathcal{N}}(0,\sigma_{w}^{2}I)\quad i=1,\cdots n$ (22)

where $x_{i}$ are the length $d$ observed vectors, $A$ is a $d\times r$
unknown deterministic matrix to be recovered, $b_{i}$ are hidden random
vectors within the $r$ dimensional simplex and $w_{i}$ are length $d$ noise
vectors. Using matrix notation, this is a variant of non-negative matrix
factorization (NMF): $X=AB+W$ where $X=[x_{1},\cdots,x_{n}]$,
$B=[b_{1},\cdots,b_{n}]$ and $W=[w_{1},\cdots,w_{n}]$. The goal is to estimate
$A$ given $X$.

Linear unmixing is common in hyperspectral imaging where each sample is a
pixel and the columns of $A$ represent different materials. Direct computation
of MLE is difficult but there are many heuristics and approximations [Bioucas-
Dias et al., 2012]. For our purposes, we only compare the general purpose MMD
and WGAN. We experimented with different hyperparameter settings (learning
rate, bandwidth, and number of layers in the discriminator) and report the
results of the best in each model. Dimensions were $d=10$, $r=3$ and $n=100$.
Both algorithms are initialized using the popular Vertex Component Analysis
(VCA) algorithm [Nascimento and Dias, 2005]444https://github.com/Laadr/VCA and
perform $5000$ epochs. The accuracy of an estimate $A$ with respect to a true
$A^{*}$ is defined using:

$d(A,A^{*})=\min_{\pi\in\Pi}\sum_{i}\|a_{i}-a^{*}_{\pi_{i}}\|^{2}$ (23)

where $\Pi$ is the set of all the permutations of $(1,\cdots,r)$ since it is
impossible to identify the order of the columns in $A$. Results are provided
in Table 1 and show a clear advantage for MMD over WGAN. Additional
experiments (not shown) also suggest that MMD is less sensitive to
hyperparameter tuning than WGAN, but both require a clever initialization such
as VCA and perform poorly otherwise.

$\sigma_{w}^{2}$ | 0.001 | 0.01 | 0.1
---|---|---|---
WGAN | 0.60 (0.20) | 0.61 (0.19) | 0.61 (0.16)
MMD | 0.46 (0.19) | 0.46 (0.17) | 0.50 (0.18)
Table 1: Accuracy in linear unmixing with different noise variances.

##  5 Conclusions

Deep learning approaches typically result in non-convex optimization problems.
There are clearly cases where this can lead to bad local optima and therefore
failure of the learning method. On the other hand, in practice useful models
are often learned. Thus, a key challenge for theoretical work is to
characterize when such methods are expected to work. Clearly this is a
technical challenge, due to the non-convexity of the optimization landscape,
and indeed not many such results have been proven to date.

Here we focus on models that we believe to be building blocks of more complex
cases. One case is Gaussians with low-rank covariance, which captures the
structure of low dimensional manifolds that are often present in real data.
The other is mixtures of Gaussians which capture the common case of multi-
modal structure. For these cases, we show that MMD can be globally optimized
despite its non-convexity. Interestingly, MMD also offers an advantage over
MLE in the covariance learning case.

One challenge with our theoretical results is that in some cases gradients
will vanish as the parameter diverges. An interesting approach to ameliorate
this is to choose a bandwidth where gradients are sufficiently large. This
will result in a method closer to MMD-GAN, and it will be very interesting to
explore its theoretical properties.

Another avenue for future research is to study the effect of the “fake” sample
size on both the optimization landscape and the sample complexity. Our
empirical evaluation suggests that MMD performs well for finite samples
(though not as well as the infinite fake sample; namely OSMMD). It should be
possible to analyze this via Morse theory [Mei et al., 2018] which we leave
for future work.

#### Acknowledgments

This research was partially supported by ISF grant 2672/21. Also thank to
Nerya Granot who supply the VCA code.

## References

  * [Aloise et al., 2009] Aloise, D., Deshpande, A., Hansen, P., and Popat, P. (2009).  Np-hardness of euclidean sum-of-squares clustering.  Machine learning, 75(2):245–248.
  * [Arbel et al., 2019] Arbel, M., Korba, A., SALIM, A., and Gretton, A. (2019).  Maximum mean discrepancy gradient flow.  32\.
  * [Bińkowski et al., 2018] Bińkowski, M., Sutherland, D. J., Arbel, M., and Gretton, A. (2018).  Demystifying mmd gans.  arXiv preprint arXiv:1801.01401.
  * [Bioucas-Dias et al., 2012] Bioucas-Dias, J. M., Plaza, A., Dobigeon, N., Parente, M., Du, Q., Gader, P., and Chanussot, J. (2012).  Hyperspectral unmixing overview: Geometrical, statistical, and sparse regression-based approaches.  IEEE journal of selected topics in applied earth observations and remote sensing, 5(2):354–379.
  * [Cho and Suh, 2019] Cho, J. and Suh, C. (2019).  Wasserstein gan can perform pca.  In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 895–901. IEEE.
  * [Daskalakis and Panageas, 2018] Daskalakis, C. and Panageas, I. (2018).  The limit points of (optimistic) gradient descent in min-max optimization.  In 32nd Annual Conference on Neural Information Processing Systems (NIPS).
  * [Daskalakis et al., 2017] Daskalakis, C., Tzamos, C., and Zampetakis, M. (2017).  Ten steps of em suffice for mixtures of two gaussians.  In Conference on Learning Theory, pages 704–710. PMLR.
  * [Dziugaite et al., 2015] Dziugaite, G. K., Roy, D. M., and Ghahramani, Z. (2015).  Training generative neural networks via maximum mean discrepancy optimization.  arXiv preprint arXiv:1505.03906.
  * [Farnia et al., 2020] Farnia, F., Wang, W., Das, S., and Jadbabaie, A. (2020).  Gat-gmm: Generative adversarial training for gaussian mixture models.  arXiv preprint arXiv:2006.10293.
  * [Feizi et al., 2017] Feizi, S., Farnia, F., Ginart, T., and Tse, D. (2017).  Understanding gans: the lqg setting.  arXiv preprint arXiv:1710.10793.
  * [Goodfellow et al., 2014] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014).  Generative adversarial nets.  Advances in Neural Information Processing Systems, 27:2672–2680.
  * [Gretton et al., 2012] Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. (2012).  A kernel two-sample test.  The Journal of Machine Learning Research, 13(1):723–773.
  * [Gulrajani et al., 2017] Gulrajani, I., Ahmed, F., Arjovsky, M., Dumoulin, V., and Courville, A. (2017).  Improved training of wasserstein gans.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5769–5779.
  * [Ji and Liang, 2018] Ji, K. and Liang, Y. (2018).  Minimax estimation of neural net distance.  arXiv preprint arXiv:1811.01054.
  * [Jin et al., 2017] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. (2017).  How to escape saddle points efficiently.  In International Conference on Machine Learning, pages 1724–1732. PMLR.
  * [Jin et al., 2016] Jin, C., Zhang, Y., Balakrishnan, S., Wainwright, M. J., and Jordan, M. I. (2016).  Local maxima in the likelihood of gaussian mixture models: Structural results and algorithmic consequences.  Advances in neural information processing systems, 29:4116–4124.
  * [Lee et al., 2016] Lee, J. D., Simchowitz, M., Jordan, M. I., and Recht, B. (2016).  Gradient descent only converges to minimizers.  In Conference on learning theory, pages 1246–1257. PMLR.
  * [Lei et al., 2020] Lei, Q., Lee, J., Dimakis, A., and Daskalakis, C. (2020).  SGD learns one-layer networks in wgans.  In International Conference on Machine Learning, pages 5799–5808. PMLR.
  * [Li et al., 2017] Li, C.-L., Chang, W.-C., Cheng, Y., Yang, Y., and Póczos, B. (2017).  Mmd GAN: Towards deeper understanding of moment matching network.  arXiv preprint arXiv:1705.08584.
  * [Li et al., 2018] Li, J., Madry, A., Peebles, J., and Schmidt, L. (2018).  On the limitations of first-order approximation in GAN dynamics.  In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3005–3013. PMLR.
  * [Li et al., 2015] Li, Y., Swersky, K., and Zemel, R. (2015).  Generative moment matching networks.  In International Conference on Machine Learning, pages 1718–1727. PMLR.
  * [Mei et al., 2018] Mei, S., Bai, Y., and Montanari, A. (2018).  The landscape of empirical risk for nonconvex losses.  The Annals of Statistics, 46(6A):2747–2774.
  * [Moitra and Valiant, 2010] Moitra, A. and Valiant, G. (2010).  Settling the polynomial learnability of mixtures of gaussians.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 93–102. IEEE.
  * [Mroueh and Nguyen, 2021] Mroueh, Y. and Nguyen, T. (2021).  On the convergence of gradient descent in gans: Mmd gan as a gradient flow.  In International Conference on Artificial Intelligence and Statistics, pages 1720–1728. PMLR.
  * [Müller, 1997] Müller, A. (1997).  Integral probability metrics and their generating classes of functions.  Advances in Applied Probability, 29(2):429–443.
  * [Nascimento and Dias, 2005] Nascimento, J. M. and Dias, J. M. (2005).  Vertex component analysis: A fast algorithm to unmix hyperspectral data.  IEEE transactions on Geoscience and Remote Sensing, 43(4):898–910.
  * [Rustamov, 2019] Rustamov, R. M. (2019).  Closed-form expressions for maximum mean discrepancy with applications to wasserstein auto-encoders.  arXiv preprint arXiv:1901.03227.
  * [Sun et al., 2015] Sun, J., Qu, Q., and Wright, J. (2015).  When are nonconvex problems not scary?  arXiv preprint arXiv:1510.06096.
  * [Sutherland et al., 2017] Sutherland, D. J., Tung, H.-Y., Strathmann, H., De, S., Ramdas, A., Smola, A. J., and Gretton, A. (2017).  Generative models and model criticism via optimized maximum mean discrepancy.  In ICLR.
  * [Tolstikhin et al., 2016] Tolstikhin, I. O., Sriperumbudur, B. K., and Schölkopf, B. (2016).  Minimax estimation of maximum mean discrepancy with radial kernels.  Advances in Neural Information Processing Systems, 29:1930–1938.
  * [Wang et al., 2018] Wang, W., Sun, Y., and Halgamuge, S. (2018).  Improving mmd-gan training with repulsive loss function.  arXiv preprint arXiv:1812.09916.

Supplementary Materials

##  1 PROOFS OF MAIN RESULTS

###  1.1 End of Proof of Theorem 2

###### Proof.

Computing the Hessian (Lemma 6) and dropping positive constants:

$H=\nabla^{2}\text{MMD}(a)\propto(2\left\|a\right\|^{2}+c)^{-\frac{3}{2}}c^{-\frac{3}{2}}\left(6\left(2\left\|a\right\|^{2}+c\right)^{-1}aa^{T}-I\right)\\\
+(\left\|a\right\|^{2}+c)^{-\frac{3}{2}}(1+c)^{-\frac{1}{2}}\Bigg{(}({e_{1}}{e_{1}}^{T}+cI)^{-1}-3c^{-1}(\left\|a\right\|^{2}+c)^{-1}aa^{T}\Bigg{)}$
(24)

Finally we show that (12) ensures that $a^{*}$ is a descent direction:

$\displaystyle{a^{*}}^{T}Ha^{*}$
$\displaystyle\propto-(2\left\|a\right\|^{2}+c)^{-\frac{3}{2}}c^{-\frac{3}{2}}+(\left\|a\right\|^{2}+c)^{-\frac{3}{2}}(1+c)^{-\frac{3}{2}}$
(25)
$\displaystyle=-\left(2\frac{c\left((1+c)^{\frac{1}{3}}-c^{\frac{1}{3}}\right)}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}+c\right)^{-\frac{3}{2}}c^{-\frac{3}{2}}+\left(\frac{c\left((1+c)^{\frac{1}{3}}-c^{\frac{1}{3}}\right)}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}+c\right)^{-\frac{3}{2}}(1+c)^{-\frac{3}{2}}$
$\displaystyle\propto-\left(2\frac{\left((1+c)^{\frac{1}{3}}-c^{\frac{1}{3}}\right)}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}+1\right)^{-\frac{3}{2}}c^{-\frac{3}{2}}+\left(\frac{\left((1+c)^{\frac{1}{3}}-c^{\frac{1}{3}}\right)}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}+1\right)^{-\frac{3}{2}}(1+c)^{-\frac{3}{2}}$
$\displaystyle=-\left(\frac{(1+c)^{\frac{1}{3}}}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}\right)^{-\frac{3}{2}}c^{-\frac{3}{2}}+\left(\frac{c^{\frac{1}{3}}}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}\right)^{-\frac{3}{2}}(1+c)^{-\frac{3}{2}}$
$\displaystyle=-\left(\frac{(1+c)^{\frac{1}{3}}}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}\right)^{-\frac{3}{2}}c^{-\frac{3}{2}}+\left(\frac{c^{\frac{1}{3}}}{2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}}\right)^{-\frac{3}{2}}(1+c)^{-\frac{3}{2}}$
$\displaystyle=\frac{c^{-\frac{1}{2}}(1+c)^{-\frac{3}{2}}-(1+c)^{-\frac{1}{2}}c^{-\frac{3}{2}}}{\left(2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}\right)^{-\frac{3}{2}}}=\frac{(c(1+c)^{3})^{-\frac{1}{2}}-((1+c)c^{3})^{-\frac{1}{2}}}{\left(2c^{\frac{1}{3}}-(1+c)^{\frac{1}{3}}\right)^{-\frac{3}{2}}}<0$

∎

###  1.2 End of Proof of Theorem 3

###### Proof.

In case (B), $\left\|\mu-\mu^{*}\right\|^{2}=\left\|\mu+\mu^{*}\right\|^{2}$,
and by plugging in the equation again:

$\left\|\mu-\mu^{*}\right\|^{2}+\left\|\mu+\mu^{*}\right\|^{2}=4\left\|\mu^{*}\right\|^{2}$
(26)

which means

$\mu^{T}\mu^{*}=0,\qquad\left\|\mu^{*}\right\|^{2}=\left\|\mu\right\|^{2}$
(27)

To characterize $\mu$ in this case, we compute the Hessian:

$H=\nabla^{2}\text{MMD}(P_{\mu^{*}},P_{\mu})=e^{-\frac{1}{2}c^{-1}\left\|\mu-\mu^{*}\right\|^{2}}c^{-1}I-e^{-\frac{1}{2}c^{-1}\left\|\mu-\mu^{*}\right\|^{2}}c^{-2}(\mu-\mu^{*})(\mu-\mu^{*})^{T}\\\
+e^{-\frac{1}{2}c^{-1}\left\|\mu+\mu^{*}\right\|^{2}}c^{-1}I-e^{-\frac{1}{2}c^{-1}\left\|\mu+\mu^{*}\right\|^{2}}c^{-2}(\mu+\mu^{*})(\mu+\mu^{*})^{T}-2e^{-2c^{-1}\left\|\mu\right\|^{2}}c^{-1}I+8e^{-2c^{-1}\left\|\mu\right\|^{2}}c^{-2}\mu\mu^{T}$
(28)

Using (27) yields:

$H=2\left(e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}-e^{-2c^{-1}\left\|\mu^{*}\right\|^{2}}\right)c^{-1}I-2e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}c^{-2}[\mu\mu^{T}+\mu^{*}{\mu^{*}}^{T}]+8e^{-2c^{-1}\left\|\mu^{*}\right\|^{2}}c^{-2}\mu\mu^{T}$
(29)

Then, its easy to see that $\mu^{*}$ is an eigenvector and its corresponding
eigenvalue is negative:

$\displaystyle\mu^{*}H\mu^{*}$
$\displaystyle=2\left(e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}-e^{-2c^{-1}\left\|\mu^{*}\right\|^{2}}\right)c^{-1}\left\|\mu^{*}\right\|^{2}-2e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}c^{-2}\left\|\mu^{*}\right\|^{4}$
(30)
$\displaystyle=2e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}\left(1-e^{-c^{-1}\left\|\mu^{*}\right\|^{2}}-c^{-1}\left\|\mu^{*}\right\|^{2}\right)c^{-1}\left\|\mu^{*}\right\|^{2}<0$
(31)

Which holds by Taylor and $\mu^{*}\neq 0$. ∎

##  2 LEMMAS

######  Lemma 4.

Let $\mu\in\mathbb{R}^{d}$ and $\Sigma\in\mathbb{R}^{d\times d}$ a positive
definite matrix, then:

$\int_{\mathbb{R}^{d}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\left\|z\right\|^{2}}\cdot\mathcal{N}(z;\mu,\Sigma)dz=\left\lvert\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{-\frac{1}{2}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\mu^{T}(\frac{1}{\sigma^{2}}\Sigma+I)^{-1}\mu}$
(32)

###  2.1 Proof of Lemma 4

###### Proof.

$\displaystyle\int_{\mathbb{R}^{d}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\left\|z\right\|^{2}}\cdot\mathcal{N}(z;\mu,\Sigma)dz$
$\displaystyle=\int_{\mathbb{R}^{d}}\frac{1}{\sqrt{(2\pi)^{d}}}\frac{1}{\left\lvert\Sigma\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\left\|z\right\|^{2}}e^{-\frac{1}{2}(z-\mu)^{T}\Sigma^{-1}(z-\mu)}dz$
$\displaystyle=\frac{1}{\left\lvert\Sigma\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\mu^{T}\Sigma^{-1}\mu}\cdot\int_{\mathbb{R}^{d}}\frac{1}{\sqrt{(2\pi)^{d}}}e^{-\frac{1}{2}[z^{T}(\Sigma^{-1}+\frac{1}{\sigma^{2}}I)z-2\frac{1}{\sigma^{2}}\mu^{T}\Sigma^{-1}z]}dz$
$\displaystyle\overset{*}{=}\frac{1}{\left\lvert\Sigma\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\mu^{T}\Sigma^{-1}\mu}\cdot\frac{1}{\left\lvert\Sigma^{-1}+\frac{1}{\sigma^{2}}I\right\rvert^{\frac{1}{2}}}e^{+\frac{1}{2}\mu^{T}\Sigma^{-1}(\Sigma^{-1}+\frac{1}{\sigma^{2}}I)^{-1}\Sigma^{-1}\mu}$
$\displaystyle=\frac{1}{\left\lvert\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\mu^{T}[\Sigma^{-1}-\Sigma^{-1}(\Sigma^{-1}+\frac{1}{\sigma^{2}}I)^{-1}\Sigma^{-1}]\mu}$
$\displaystyle\overset{**}{=}\frac{1}{\left\lvert\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\mu^{T}(\Sigma+\sigma^{2}I)^{-1}\mu}=\frac{1}{\left\lvert\frac{1}{\sigma^{2}}\Sigma+I\right\rvert^{\frac{1}{2}}}e^{-\frac{1}{2}\frac{1}{\sigma^{2}}\mu^{T}(\frac{1}{\sigma^{2}}\Sigma+I)^{-1}\mu}$

$(*)$ Integral over pdf of normal variable with
$(\Sigma^{-1}+\frac{1}{\sigma^{2}}I)^{-1}\Sigma^{-1}\mu$ mean and
$(\Sigma^{-1}+\frac{1}{\sigma^{2}}I)$ covariance.
$(**)$ Woodbury matrix identity. ∎

######  Lemma 5.

$\nabla_{a}\text{MMD}(P_{a^{*}},P_{a})=-2\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\left(\frac{1}{\sigma^{2}}\right)^{d}(2\varepsilon^{2}+\sigma^{2})^{d-1}a\\\
+2\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\left(\frac{1}{\sigma^{2}}\right)^{d}(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a$
(33)

###### Proof.

By differentiating each term of equation 7 separately:

$\displaystyle\nabla_{a}\left[\frac{1}{\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{\frac{1}{2}}}\right]$
$\displaystyle=-\frac{1}{2}\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\nabla_{a}\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert$
$\displaystyle\overset{*}{=}-\frac{1}{2}\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\left(\frac{1}{\sigma^{2}}\right)^{d}(2\varepsilon^{2}+\sigma^{2})^{d}(\varepsilon^{2}+\frac{\sigma^{2}}{2})^{-1}\nabla_{a}[a^{T}a]$
$\displaystyle=-\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\left(\frac{1}{\sigma^{2}}\right)^{d}(2\varepsilon^{2}+\sigma^{2})^{d}(\varepsilon^{2}+\frac{\sigma^{2}}{2})^{-1}a$
$\displaystyle=-2\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\left(\frac{1}{\sigma^{2}}\right)^{d}(2\varepsilon^{2}+\sigma^{2})^{d-1}a$

$(*)$ using Sylvester’s determinant theorem:

$\displaystyle\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert$
$\displaystyle=\left(\frac{2}{\sigma^{2}}\right)^{d}\left\lvert
aa^{T}+(\varepsilon^{2}+\frac{\sigma^{2}}{2})I\right\rvert$
$\displaystyle=\left(\frac{2}{\sigma^{2}}\right)^{d}\left\lvert(\varepsilon^{2}+\frac{\sigma^{2}}{2})I\right\rvert\left\lvert
1+a^{T}(\varepsilon^{2}+\frac{\sigma^{2}}{2})^{-1}a\right\rvert$
$\displaystyle=\left(\frac{1}{\sigma^{2}}\right)^{d}(2\varepsilon^{2}+\sigma^{2})^{d}(1+a^{T}(\varepsilon^{2}+\frac{\sigma^{2}}{2})^{-1}a)$

$\displaystyle\nabla_{a}\left[-2\frac{1}{\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{\frac{1}{2}}}\right]$
$\displaystyle=\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\nabla_{a}\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert$
$\displaystyle\overset{*}{=}\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\left(\frac{1}{\sigma^{2}}\right)^{d}(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}\nabla_{a}a^{T}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a$
$\displaystyle=2\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\cdot\left(\frac{1}{\sigma^{2}}\right)^{d}(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a$

$(*)$ using Sylvester’s determinant theorem (and $a^{*}=e_{1}$):

$\displaystyle\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert$
$\displaystyle=\left(\frac{1}{\sigma^{2}}\right)^{d}\left\lvert
aa^{T}+({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)\right\rvert$
$\displaystyle=\left(\frac{1}{\sigma^{2}}\right)^{d}\left\lvert{a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert\left\lvert
1+a^{T}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a\right\rvert$
$\displaystyle=\left(\frac{1}{\sigma^{2}}\right)^{d}(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}(1+a^{T}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a)$

∎

######  Lemma 6.

$\displaystyle\nabla^{2}\text{MMD}(a)$
$\displaystyle=2\sigma^{-d}(2\varepsilon^{2}+\sigma^{2})^{d-1}\left\lvert
2aa^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-\frac{3}{2}}\left(6(2\varepsilon^{2}+\sigma^{2})^{d-1}\left\lvert
2aa^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-1}aa^{T}-I\right)$
$\displaystyle\quad+2\sigma^{-d}(2\varepsilon^{2}+\sigma^{2})^{d-1}(1+2\varepsilon^{2}+\sigma^{2})\left\lvert
aa^{T}+{a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-\frac{3}{2}}\Bigg{(}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}$
$\displaystyle\quad\quad-3(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}\left\lvert
aa^{T}+{a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-1}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}aa^{T}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}\Bigg{)}$

###### Proof.

By derive the equation of lemma 5: First term: we set aside the constant
$2\sigma^{-2d}(2\varepsilon^{2}+\sigma^{2})^{d-1}$ for simplicity.

$\displaystyle\nabla\left[-\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}a\right]$
$\displaystyle=-a\nabla\left[\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\right]^{T}-\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\nabla\left[a\right]$
$\displaystyle=\frac{3}{2}\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{5}{2}}a\nabla\left[\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert\right]^{T}-\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}I$
$\displaystyle\overset{*}{=}6\left(\frac{1}{\sigma^{2}}\right)^{d}(2\varepsilon^{2}+\sigma^{2})^{d-1}\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{5}{2}}aa^{T}-\left\lvert\frac{2}{\sigma^{2}}(aa^{T}+\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}I$
$\displaystyle=\sigma^{3d}\left\lvert
2aa^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-\frac{3}{2}}\left(6(2\varepsilon^{2}+\sigma^{2})^{d-1}\left\lvert
2aa^{T}+(\varepsilon^{2}+\sigma^{2})I\right\rvert^{-1}aa^{T}-I\right)$

$(*)$ As we found in lemma 5. Second term: we set aside the constant
$2\left(\frac{1}{\sigma^{2}}\right)^{d}(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}$
for simplicity.

$\displaystyle\nabla\left[\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a\right]$
$\displaystyle=({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a\nabla\left[\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}\right]^{T}$
$\displaystyle\qquad\qquad+\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}\nabla\left[a\right]$
$\displaystyle=-\frac{3}{2}\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{5}{2}}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}a\nabla\left[\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert\right]^{T}$
$\displaystyle\qquad\qquad+\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}$
$\displaystyle\overset{*}{=}-3\left(\frac{1}{\sigma^{2}}\right)^{d}(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{5}{2}}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}aa^{T}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}$
$\displaystyle\qquad\qquad+\left\lvert\frac{1}{\sigma^{2}}(aa^{T}+{a^{*}}{a^{*}}^{T}+2\varepsilon^{2}I)+I\right\rvert^{-\frac{3}{2}}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}$
$\displaystyle=\sigma^{3d}\left\lvert
aa^{T}+{a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-\frac{3}{2}}\Bigg{[}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}-3(1+2\varepsilon^{2}+\sigma^{2})(2\varepsilon^{2}+\sigma^{2})^{d-1}$
$\displaystyle\qquad\qquad\cdot\left\lvert
aa^{T}+{a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I\right\rvert^{-1}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}aa^{T}({a^{*}}{a^{*}}^{T}+(2\varepsilon^{2}+\sigma^{2})I)^{-1}\qquad\quad\Bigg{]}$

$(*)$ As we found in lemma 5. ∎

##  3 EXPERIMENTS

###  3.1 Graphs Parameters

In the following tables we describe the parameters which were used in the
experiments:

Table 2: Experiments Details - Gaussian with Unknown Mean Loss | Learning rate | Iterations | Bandwidth | Fakes ratio | Repeats
---|---|---|---|---|---
MMD | $10^{-1}$ | 500 | $10^{1}$ | 1 | 800
OSMMD | $10^{-1}$ | 500 | $10^{1}$ |  | 100
MLE | $10^{-1}$ | 500 |  |  | 100
WGAN | $10^{-2}$ | 1000 |  | 1 | 500
Table 3: Experiments Details - GMM with Unknown Mean Loss | Learning rate | Iterations | Bandwidth | Fakes ratio | Repeats
---|---|---|---|---|---
MMD | $10^{-1}$ | 1000 | $10^{1}$ | 1 | 700
OSMMD | $10^{-1}$ | 1000 | $10^{1}$ |  | 100
MLE | $10^{-1}$ | 1000 |  |  | 100
WGAN | $10^{-1}$ | 1000 |  | 1 | 1000
Table 4: Experiments Details - Gaussian with Unknown Covariance Loss | Learning rate | Iterations | Bandwidth | Fakes ratio | Repeats
---|---|---|---|---|---
MMD | $10^{-1}$ | 1000 | $10^{2}$ | 1 | 800
OSMMD | $10^{-1}$ | 1000 | $10^{1}$ |  | 100
MLE | $10^{-1}$ | 1000 |  |  | 100
WGAN | $10^{-1}$ | 1000 |  | 1 | 800
Table 5: Experiments Details - GMM with Unknown Covariance Loss | Learning rate | Iterations | Bandwidth | Fakes ratio | Repeats
---|---|---|---|---|---
MMD | $10^{-2}$ | 1000 | $10^{1}$ | 1 | 200
OSMMD | $10^{-1}$ | 1000 | $10^{1}$ |  | 200
MLE | $10^{-1}$ | 1000 |  |  | 200
WGAN | $10^{-2}$ | 1000 |  | 1 | 200
Table 6: Experiments Details - Gaussian with Unknown Covariance, Epsilon Comparing Loss | Learning rate | Iterations | Bandwidth | Fakes ratio | Repeats
---|---|---|---|---|---
OSMMD | $10^{1}$ | 5000 | $10^{4}$ |  | 100
MLE | $10^{-1}$ | 10000 |  |  | 100

###  3.2 Linear Unmixing

For each noise variance we initialized in VCA, and the following setups with
256 fake sampling each iteration and over 5000 iterations: For each noise we
run the following setups:

Table 7: MMD and WGAN setups

Loss | Learning rate | Bandwidth
---|---|---
MMD 1 | $10^{-2}$ | $10^{-2}$
MMD 2 | $10^{-2}$ | $10^{-1}$
MMD 3 | $10^{-2}$ | $10^{0}$
MMD 4 | $10^{-1}$ | $10^{-2}$
MMD 5 | $10^{-1}$ | $10^{-1}$
MMD 6 | $10^{-1}$ | $10^{0}$

Loss | Learning rate | Layers
---|---|---
WGAN 1 | $10^{-3}$ | 2
WGAN 2 | $10^{-2}$ | 2
WGAN 3 | $10^{-1}$ | 2
WGAN 4 | $10^{-3}$ | 3
WGAN 5 | $10^{-2}$ | 3
WGAN 6 | $10^{-1}$ | 3

Final results of experiments (each averaged over $50$ trials) were:

Table 8: Linear Unmixing results Loss | Random | VCA |  |  |  |
---|---|---|---|---|---|---
| MMD 1 | MMD 2 | MMD 3 | MMD 4 | MMD 5 | MMD 6
| WGAN 1 | WGAN 2 | WGAN 3 | WGAN 4 | WGAN 5 | WGAN 6
0.01 |  7.68 (0.72) |  0.77 (0.23) |  |  |  |
|  0.36 (0.19) |  0.43 (0.14) |  0.55 (0.17) |  0.56 (0.21) |  0.46 (0.17) |  0.60 (0.19)
|  0.60 (0.23) |  0.74 (0.22) |  6.38 (15.23) |  0.61 (0.25) |  0.68 (0.20) |  2.58 (1.82)
0.1 |  7.60 (0.62) |  0.97 (0.73) |  |  |  |
|  1.00 (1.11) |  0.56 (0.24) |  0.63 (0.20) |  5.92 (10.25) |  0.61 (0.26) |  0.67 (0.21)
|  0.69 (0.46) |  1.36 (0.86) |  9.03 (18.59) |  0.72 (0.61) |  0.87 (0.58) |  3.64 (2.62)
1.0 |  7.46 (0.66) |  4.67 (1.13) |  |  |  |
|  4.68 (1.13) |  4.89 (1.02) |  4.09 (0.81) |  4.95 (1.51) |  22.95 (1.74 ) |  4.15 (0.80)
|  3.77 (0.89) |  3.56 (0.88) |  13.96 (18.04) |  3.70 (0.90) |  3.42 (0.92) |  4.76 (1.98)


# Topological and Algebraic Genericity and Spaceability for an extended chain
of sequence spaces

M. Axarlis, I. Deliyanni, Th. Loukidou, V. Nestoridis, K. Papanikos, N.
Tziotziou

###### Abstract

We examine topological and algebraic genericity and spaceability for any pair
$(X,Y)$, $X\subset Y$, $X\neq Y$ belonging to an extended chain of sequence
spaces which contains the $\ell^{p}$ spaces, $0<p\leq\infty$.

Dedicated to the memory of Professor Dimitris Gatzouras

##  1 Introduction

In [7], [4], the chain of spaces $\cap_{p>\alpha}\ell^{p}\;(\alpha\geq 0)$,
$\ell^{p}\;(0<p<+\infty)$, $c_{0}$, $\ell^{\infty}$ was considered and, for
any pair $(X,Y)$ with $X,Y,\;X\subsetneqq Y$ belonging to this chain,
topological and algebraic genericity and spaceability were investigated,
extending previous results. We recall the definitions. Given a pair of vector
spaces $(X,Y)$ as above, we say that we have topological genericity if $X$ is
contained in an $F_{\sigma}$ \- meager subset of $Y$, equivalently if
$Y\setminus X$ is residual in $Y$. This is always the case and then a question
that arises naturally is whether $X$ is indeed equal to an $F_{\sigma}$ subset
of $Y$ or not. Furthermore, we say that we have algebraic genericity for the
pair $(X,Y)$, if there exists a vector subspace $F$ of $Y$, dense in $Y$, such
that $F$ is contained in $(Y\setminus X)\cup\\{0\\}$. Finally, we have
spaceability if $(Y\setminus X)\cup\\{0\\}$ contains a closed infinite
dimensional subspace of $Y$.

In the present paper we extend the above chain by adding the space
$A^{\infty}({\mathbb{D}})$ which is contained in $\cap_{p>0}\ell^{p}$ and the
spaces $H({\mathbb{D}})\subset{\mathbb{C}}^{{\mathbb{N}}_{0}}$ which contain
$\ell^{\infty}$. The spaces $A^{\infty}({\mathbb{D}})$ and $H({\mathbb{D}})$
are spaces of holomorphic functions on the open unit disc $D$ of the complex
plane ${\mathbb{C}}$, but they can also be seen as sequence spaces via the
identification of any holomorphic function on ${\mathbb{D}}$ with the sequence
of its Taylor coefficients. More precisely, for
$f=\sum\limits_{n=0}^{\infty}a_{n}z^{n}$, we have that $f$ belongs to
$A^{\infty}({\mathbb{D}})$ if and only if, for every $k=1,2,\ldots$, it holds
that $n^{k}a_{n}\rightarrow 0$ as $n\rightarrow+\infty$, while $f$ belongs to
$H({\mathbb{D}})$ if and only if $\lim\sup\sqrt[n]{|a_{n}|}\leq 1.$

For $X\subsetneqq Y$ belonging to this extended chain of spaces, we examine
topological and algebraic genericity and spaceability, completing thus the
results of [7] and [4]. We also mention the remarkable papers [6] and [8]
which are related to this work.

For algebraic genericity and spaceability we refer the reader to [5] and [1].
For topological genericity we refer to [3].

This work was completed by the students and the instructors in the frame of an
advanced undergraduate course in Analysis at the Department of Mathematics of
the National and Kapodistrian University of Athens in Greece.

##  2 Topological Genericity

We begin with the following

######  Proposition 2.1.

Let $\mathbb{C}^{\mathbb{N}_{0}}$ be the set of sequences
$(a_{n})_{n=0}^{\infty}$ with $a_{n}\in\mathbb{C},n=0,1,2,\dots$, endowed with
the usual operations, pointwise addition, scalar multiplication $+,\cdot$. Let
$X,Y$ be two $F$-spaces which are vector subspaces of
$\mathbb{C}^{\mathbb{N}_{0}}$. We assume that convergence of a sequence
$a^{m}=\left(a_{n}^{m}\right)_{n=0}^{\infty}$ in either $X$ or $Y$ implies
pointwise convergence, that is, if $a^{m}\xrightarrow{m\to\infty}a$ in $X$ or
$Y$, then $a^{m}_{n}\xrightarrow{m\to\infty}a_{n}$ for all $n=0,1,2,\dots$ If
$X\subset Y$ then the inclusion map $I:X\rightarrow Y,\,I(\alpha)=\alpha$, is
continuous.

###### Proof.

This follows immediately from the closed graph theorem.
Indeed, let $(a^{m},I(a^{m}))=\left(a^{m},a^{m}\right)\in$ Gr($I$) such that
$\left(a^{m},a^{m}\right)\xrightarrow{m\longrightarrow\infty}\left(a,b\right)$.
It suffices to show that $a=b$. From our assumption, $a^{m}\rightarrow a$ in
$X$. It follows that $a_{n}^{m}\rightarrow a_{n}$ as $m\rightarrow\infty$ for
every $n$. Similarly from the convergence in $Y$, we have that
$a_{n}^{m}\rightarrow b_{n}$ as $m\rightarrow\infty$ for every $n=0,1,2,\dots$
It follows that $a=b$. ∎

######  Proposition 2.2.

If, in addition to the assumptions of Proposition 2.1., $X$ is different from
$Y$, then $X$ is included in an $F_{\sigma}$ meager subset of $Y$.

###### Proof.

This follows from Proposition $2.1.$ and a theorem of Banach which is a
version of the open mapping theorem ([9], Theorem 2.11), since the inclusion
map $I:X\rightarrow Y,\,I(a)=a$, is linear, continuous and not surjective. ∎

The above find application when $X,Y$ are among the spaces $\ell^{p}\text{ for
}0<p<\infty,\,\,\bigcap_{p>\alpha}\ell^{p}\text{ for
}0\leq\alpha<\infty,\,\,c_{0}\,\,\text{and}\,\,\ell^{\infty}$ ([7] and [4]).
In the present paper, we extend this chain by adding the spaces
$A^{\infty}(\mathbb{D})\subset\bigcap_{p>0}\ell^{p}$ and $\ell^{\infty}\subset
H(\mathbb{D})\subset\mathbb{C}^{\mathbb{N}_{0}}$, where $\mathbb{D}$ is the
open unit disc in $\mathbb{C}$.

Let us first recall the definitions.

######  Definition 2.3.

Let $H(\mathbb{D})$ be the set of all holomorphic functions on the open unit
disc $\mathbb{D}$ and endow this space with the topology of uniform
convergence on compact subsets of $\mathbb{D}$.
We consider $H(\mathbb{D})$ as a sequence space, by identifying every function
$f(z)=\sum_{n=0}^{\infty}a_{n}z^{n}$ with the sequence
$a=(a_{n})_{n=0}^{\infty}$ of its Taylor coefficients. It is well known that
$f\in H(\mathbb{D})$ if and only if
$\limsup_{n}\left\\{\sqrt[n]{|a_{n}|}\right\\}\leq 1$.

######  Definition 2.4.

Let $A^{\infty}(\mathbb{D})$ be the set of holomorphic functions $f$ on the
open unit disc $\mathbb{D}$ such that $f$ and all its derivatives $f^{(l)}$
can be continuously extended on the closed unit disc $\overline{\mathbb{D}}$.
We endow $A^{\infty}(\mathbb{D})$ with the natural metric
$d(f,g)=\sum_{i=0}^{\infty}\frac{1}{2^{i}}\frac{\|f^{(i)}-g^{(i)}\|_{\infty}}{1+\|f^{(i)}-g^{(i)}\|_{\infty}}$.
As before, we identify every $f\in A^{\infty}(\mathbb{D})$ with the sequence
$a=(a_{n})_{n=0}^{\infty}$ of its Taylor coefficients. It is easy to see that
$f\in A^{\infty}(\mathbb{D})$ if and only if
$n^{k}a_{n}\xrightarrow{n\to\infty}0$ for every $k$ in $\mathbb{N}_{0}.$

######  Proposition 2.5.

Convergence in $H(\mathbb{D})$ implies pointwise convergence.

###### Proof.

Let $f_{m}(z)=\sum_{n=0}^{\infty}a_{n}^{m}z^{n}$ be a sequence in
$H(\mathbb{D})$ that converges to $f(z)=\sum_{n=0}^{\infty}a_{n}z^{n}$ in
$H(\mathbb{D})$.
It suffices to show that for every $n\in\mathbb{N}_{0}$ we have
$a_{n}^{m}\xrightarrow{m\rightarrow\infty}a_{n}$.
By the Weierstrass theorem we have that, for every $n\in\mathbb{N}_{0}$,
$f_{m}^{(n)}$ converges uniformly to $f^{(n)}$ as $m\to\infty$ on each compact
subset of $\mathbb{D}$. Thus, in particular, for every $n\in\mathbb{N}_{0}$,

$a_{n}^{m}=\frac{f_{m}^{(n)}(0)}{n!}\xrightarrow{m\rightarrow\infty}\frac{f^{(n)}(0)}{n!}=a_{n}$

∎

######  Proposition 2.6.

Convergence in $A^{\infty}(\mathbb{D})$ implies pointwise convergence.

###### Proof.

It is obvious that convergence in $A^{\infty}(\mathbb{D})$ implies uniform
convergence in $\overline{\mathbb{D}}$ which implies convergence in
$H(\mathbb{D})$. Thus, by Proposition 2.5, we have pointwise convergence. ∎

######  Remark 2.7.

It is obvious that convergence in either $\ell^{\infty}$ or
$\mathbb{C}^{\mathbb{N}_{0}}$ implies pointwise convergence.

######  Proposition 2.8.

The inclusion $A^{\infty}(\mathbb{D})\subset\bigcap_{p>0}\ell^{p}$ holds, and
it is strict.

###### Proof.

Let $f(z)=\sum_{n=0}^{\infty}a_{n}z^{n}\,\in A^{\infty}(\mathbb{D})$ , i.e.
$\sum_{n=0}^{\infty}n^{k}|a_{n}|<\infty$ for all $k\geq 0$ and let $p>0$.
Let $k\in{\mathbb{N}}$ be such that $kp>1$.
We have $n^{k}|a_{n}|\to 0$ so there exists $N>1$ such that $n^{k}|a_{n}|<1$
for every $n\geq N$.
Thus
$\sum_{n=0}^{\infty}|a_{n}|^{p}\leq\sum_{n=0}^{N-1}|a_{n}|^{p}+\sum_{n=N}^{\infty}\left(\frac{1}{n^{k}}\right)^{p}<\infty$
since $kp>1$.
We now show that the inclusion is strict:
Consider the sequence $y=(y_{s})$ where

$\displaystyle
y_{s}=\left\\{\begin{array}[]{rcl}\sqrt{\frac{1}{s}}&&\mbox{if}\;s=2^{k}\;{\hbox{for
some k}}\in\mathbb{N}\\\ 0&&\mbox{otherwise}\end{array}\right.$

In other words, $y_{2^{k}}=\sqrt{\frac{1}{2^{k}}}$ and $y_{s}=0$ elsewhere.
Then $2^{k}y_{2^{k}}=2^{k/2}\rightarrow\infty$ so $y\notin A^{\infty}(D)$.
On the other hand, $y\in\bigcap_{p>0}\ell^{p}$ since
$\sum_{s=0}^{\infty}|y_{s}|^{p}=\sum_{n=1}^{\infty}\left|1/\sqrt{2}\right|^{np}<\infty$.

∎

Next we prove a slightly stronger fact that will be used later.

######  Remark 2.9.

For every infinite subset $A$ of ${\mathbb{N}_{0}}$ we can find a sequence
$y\in\bigcap_{p>0}\ell^{p}\smallsetminus A^{\infty}(\mathbb{D})$ which is
supported in $A$.

###### Proof.

Let $A=\\{l_{1},l_{2},\dots\\}$ where $l_{1}<l_{2}<\dots$ . We choose
$k_{1}<k_{2}<\ldots$ such that, for every $n\in{\mathbb{N}},$ $l_{k_{n}}\geq
2^{n}$.
We define $y=(y_{s})$ by $y_{l_{k_{n}}}=\sqrt{1/l_{k_{n}}}$ and $y_{s}=0$
otherwise.
Then $l_{k_{n}}y_{l_{k_{n}}}=\sqrt{l_{k_{n}}}\geq 2^{n/2}\to\infty$ so
$y\notin A^{\infty}(\mathbb{D})$, while for every $p>0$ we have:

$\displaystyle\sum_{s=0}^{\infty}|y_{s}|^{p}\leq\sum_{n=1}^{\infty}|2^{-{n/2}}|^{p}<\infty$

so $y\in\bigcap_{p>0}\ell^{p}$. ∎

######  Proposition 2.10.

The inclusion $\ell^{\infty}\subset H(\mathbb{D})$ holds and it is strict.

###### Proof.

Let $a=(a_{n})_{n}\in\ell^{\infty}$. Then

$\lim\sup\sqrt[n]{|a_{n}|}\leq\lim\sqrt[n]{||a||_{\infty}}\leq 1.$

So $a\in H(\mathbb{D})$, which implies $\ell^{\infty}\subset H(\mathbb{D})$.
Since $\text{limsup}\sqrt[n]{n}=1$ it follows that the sequence $(n)_{n}$ is
in $H(\mathbb{D})$, but not in $\ell^{\infty}$.
So $\ell^{\infty}\varsubsetneq H(\mathbb{D})$. ∎

######  Proposition 2.11.

The inclusion $H(\mathbb{D})\subset\mathbb{C}^{\mathbb{N}_{0}}$ holds and it
is strict.

###### Proof.

It is obvious that $H(\mathbb{D})\subset\mathbb{C}^{\mathbb{N}_{0}}$.
Since $\text{limsup}\sqrt[n]{n^{n+1}}=+\infty$ it follows that
$\left(n^{n+1}\right)_{n}\notin H(\mathbb{D})$. Therefore,
$H(\mathbb{D})\varsubsetneq\mathbb{C}^{\mathbb{N}_{0}}$. ∎

######  Theorem 2.12.

Consider the chain of spaces

$A^{\infty}(\mathbb{D})\varsubsetneq\bigcap_{p>0}\ell^{p}\varsubsetneq\ell^{a}\varsubsetneq\bigcap_{q>a}\ell^{q}\varsubsetneq\ell^{b}\varsubsetneq\bigcap_{p>b}\ell^{p}\varsubsetneq
c_{0}\varsubsetneq\ell^{\infty}\varsubsetneq
H(\mathbb{D})\varsubsetneq\mathbb{C}^{{\mathbb{N}}_{0}}$

where $a<b$.
If $X\varsubsetneq Y$ are two spaces from this chain then $X$ is contained in
an $F_{\sigma}$ meager subset of $Y$.

###### Proof.

This follows by a combination of Propositions 2.2, 2.5, 2.6 and 2.7. ∎

##  3 A Constructive Approach

In the previous section we showed that if $X\varsubsetneq Y$ are spaces as in
theorem 2.12 then X is contained in an $F_{\sigma}$ meager subset of Y.
In this section we examine whether X is itself an $F_{\sigma}$ meager subset
of Y. Our method will be constructive. At the same time we obtain a new proof
of theorem 2.12 without using Banach’s theorem.

######  Proposition 3.1.

Let $X=A^{\infty}(\mathbb{D})$ and $Y$ be a space from the chain of theorem
2.12 such that $X\varsubsetneq Y$. Then $X$ is an $F_{\sigma\delta}$ subset of
$Y$.

###### Proof.

For $k\in{\mathbb{N}}_{0}$, $M\in{\mathbb{N}},$ let
$F_{M}^{k}=\left\\{a=(a_{n})\in Y\ |\ n^{k}|a_{n}|\leq M\ \forall
n\in{\mathbb{N}}_{0}\right\\}$. It is clear that
$X=A^{\infty}(\mathbb{D})=\bigcap_{k=0}^{\infty}\bigcup_{M=1}^{\infty}F_{M}^{k}\subset\bigcup_{M=1}^{\infty}F_{M}^{1}$
and it remains to show that the sets $F_{M}^{k}$ are closed in $Y$. Indeed,
fix $k$ and $M$ and let $(a^{m})$ be a sequence in $F_{M}^{k}$, such that
$a^{m}\xrightarrow{m\to\infty}a$ in $Y$ and thus
$a^{m}_{n}\xrightarrow{m\to\infty}a_{n}$ for all $n\in\mathbb{N}_{0}$. Then
for all $n\in\mathbb{N}$ $n^{k}|a_{n}^{m}|\leq M$ and by taking the limit as
$m$ goes to $\infty$ we have $n^{k}|a_{n}|\leq M$ which implies that $a\in
F_{M}^{k}$. This completes the proof.

∎

######  Remark 3.2.

The proof of 3.1 can be used to give a new proof of the fact that
$A^{\infty}(\mathbb{D})$ is contained in an $F_{\sigma}$ meager subset of $Y$.
It suffices to show that $\bigcup_{M=1}^{\infty}F_{M}^{1}$ has empty interior
in $Y$. Indeed, it is obvious that $\bigcup_{M=1}^{\infty}F_{M}^{1}$ is a
vector subspace of $Y$. To see that it is a proper subspace, notice that the
sequence $y=(y_{n})$ of Proposition 2.8 is in $\bigcap_{p>0}\ell^{p}\subset Y$
and $y\notin\bigcup_{M=1}^{\infty}F_{M}^{1}$ because $(ny_{n})$ is not
bounded. It follows that $\bigcup_{M=1}^{\infty}F_{M}^{1}$ has empty interior
in $Y$.
We mention that all cases of Theorem 2.12 can be derived by the method of
section 3 without using Banach’s Theorem. We will not insist on this point.

######  Proposition 3.3.

Let $X=\ell^{p}$ for $p>0$ and $Y$ be a space from the chain of theorem 2.12
such that $X\varsubsetneq Y$. Then $X$ is an $F_{\sigma}$ meager subset of
$Y$.

###### Proof.

It suffices to write
$\ell^{p}=\bigcup_{M=1}^{\infty}\\{a=(a_{n})_{n=0}^{\infty}\in Y\ |\
\sum_{n=0}^{N}|a_{n}|^{p}\leq M\ \forall N\in{\mathbb{N}}\\}$ as in [7]. Thus,
the set $\ell^{p}$, being a proper vector subspace of $Y$ has empty interior
in $Y$ and is equal to a countable union of closed sets in $Y$.

∎

######  Proposition 3.4.

Let $X=\bigcap_{p>c}\ell^{p}$ for $c\geq 0$ and $Y$ be a space from the chain
of theorem 2.12 such that $X\varsubsetneq Y$. Then $X$ is an
$F_{\sigma\delta}$ subset of $Y$.

###### Proof.

Let $p_{n}=c+\frac{1}{n}$. We have
$\bigcap_{p>c}\ell^{p}=\bigcap_{n=1}^{\infty}\ell^{p_{n}}$. Since $\ell^{p}$
is $F_{σ}$ in $Y$, it follows that $X$ is $F_{σδ}$ in $Y$. ∎

######  Remark 3.5.

Obviously $c_{0}$ is closed in $\ell^{\infty}$.

######  Proposition 3.6.

Let $X=c_{0}$ and $Y=H(\mathbb{D})$ or $\mathbb{C}^{\mathbb{N}_{0}}$. Then $X$
is $F_{\sigma\delta}$ in $Y$.

###### Proof.

$X=\bigcap_{k=1}^{\infty}\bigcup_{n=1}^{\infty}F_{n}^{k}$ where
$F_{n}^{k}=\\{a=(a_{s})\in Y:|a_{s}|\leq\frac{1}{k}\ \forall s\geq n\\}$.
$F_{n}^{k}$ are closed in $Y$. Indeed, fix $n,k\in\mathbb{N}$.
Let $a^{m},\ m=1,2,\dots$ be a sequence in $F_{n}^{k}$, such that
$a^{m}\xrightarrow{m\to\infty}a$ in $Y$. According to proposition 2.5 and
remark 2.7 we have $a^{m}_{n}\xrightarrow{m\to\infty}a_{n}$, for all
$n\in\mathbb{N}_{0}$. Then, for all $s\geq n,\ |a_{s}^{m}|\leq\frac{1}{k}$ and
by taking the limit as $m$ goes to $\infty$ we have, for all $s\geq n,\
|a_{s}|\leq\frac{1}{k}$ which implies that $a\in F_{n}^{k}$. ∎

######  Proposition 3.7.

Let $X=\ell^{\infty}$ and $Y$ be a space from the chain of theorem 2.12 such
that $X\varsubsetneq Y$. Then $X$ is an $F_{\sigma}$ subset of $Y$.

###### Proof.

Let $F_{M}=\left\\{a=(a_{n})\ \in Y\ :\ |a_{n}|\leq M\;{\rm
for\;all\;}n\in\mathbb{N}_{0}\right\\}$. Obviously
$X=\bigcup_{M=1}^{\infty}F_{M}$. We will show that each set $F_{M}$ is closed
in Y.
Indeed, let $a^{m}$ be a sequence in $F_{M}$ such that
$a^{m}\xrightarrow{m\rightarrow\infty}a,$ for some $a\in Y$. Convergence in
$Y$ implies pointwise convergence, that is
$a_{n}^{m}\xrightarrow{m\rightarrow\infty}a_{n}$ for every
$n\in\mathbb{N}_{0}$. Since $|a^{m}_{n}|\leq M$ for all $n\in{\mathbb{N}}_{0}$
and $m\in{\mathbb{N}}$, it follows that $|a_{n}|\leq M$ for all
$n\in{\mathbb{N}}_{0}$. Thus, $a\in F_{M}$. ∎

######  Proposition 3.8.

Let $X=H(\mathbb{D})$ and $Y=\mathbb{C}^{\mathbb{N}_{0}}$. Then $X$ is an
$F_{\sigma\delta}$ subset of $Y$.

###### Proof.

$X=H(\mathbb{D})=\bigcap_{j=1}^{\infty}\bigcup_{k=1}^{\infty}F_{k}^{j}$, where
$F_{k}^{j}=\left\\{a=(a_{n})\in\mathbb{C}^{\mathbb{N}_{0}}\ |\
\sqrt[n]{|a_{n}|}\leq 1+\frac{1}{j}\ \forall n\geq k\right\\}$.
$F_{k}^{j}$ are closed in $Y$. Indeed, fix $j,k\in\mathbb{N}$.
Let $a^{m},\ m=1,2,\dots$ be a sequence in $F_{k}^{j}$ such that
$a^{m}\xrightarrow{m\to\infty}a$ in $Y$, so that
$a^{m}_{n}\xrightarrow{m\to\infty}a_{n}$ for all $n\in\mathbb{N}_{0}$. Then
for all $n\geq k,\ \sqrt[n]{|a_{n}^{m}|}\leq 1+\frac{1}{j}$ and by taking the
limit as $m$ goes to $\infty$ we have for all $n\geq k,\ \sqrt[n]{|a_{n}|}\leq
1+\frac{1}{j}$ which implies that $a\in F_{k}^{j}$. ∎

######  Remark 3.9.

The proof of Proposition 3.8 gives that
$X=H(D)\subseteq\bigcup_{k=1}^{\infty}F_{k}^{1}\subseteq
Y={\mathbb{C}}^{{\mathbb{N}}_{0}}$ where the set
$\bigcup_{k=1}^{\infty}F_{k}^{1}$ is an $F_{\sigma}$-meager subset of $Y$. In
other words, $Y\setminus X$ contains the complement of
$\bigcup_{k=1}^{\infty}F_{k}^{1}$ which is a $G_{\delta}$-dense subset of $Y$.
We mention that $Y\setminus X$ also contains the set of sequences $(a_{n})$
with the property that the power series $\sum_{n=0}^{\infty}a_{n}z^{n}$ has 0
radius of convergence or where $\sum_{n=0}^{\infty}a_{n}z^{n}$ is a universal
power series of Seleznev. It is known that these two last sets are
$G_{\delta}$-dense subsets of $Y={\mathbb{C}}^{{\mathbb{N}}_{0}}$ ([3]). A
series $\sum_{n=0}^{\infty}a_{n}z^{n}$ is a universal power series of Seleznev
if its partial sums approximate uniformly every polynomial on any compact set
$K\subset{\mathbb{C}}\setminus\\{0\\}$ with connected complement.

######  Remark 3.10.

In the cases where we show that $X$ is an $F_{σδ}$ in $Y$, we believe that
this result can not be improved, that is $X$ is not an $F_{σ}$ subset of $Y$.
This is true in particular in the case where $X=\bigcap_{p>a}\ell_{p}$ and $Y$
is equal to either $\ell^{b}$ or $\bigcap_{q>b}\ell_{q}$ for some
$0<a<b<\infty$ as shown by Gregoriades in [6].

##  4 Algebraic Genericity

In continuation to the previous project [7] we examine whether there is
algebraic genericity for a couple of spaces $(X,Y)$, where $X\subsetneq Y$ are
spaces belonging to the chain of Theorem 2.12.

We recall the definition:

######  Definition 4.1.

Let $X,Y$ be F-spaces, with $X\subset Y$ and $X\neq Y$. We say that we have
algebraic genericity for the couple $(X,Y)$ if there is a vector subspace $F$
of $Y$ dense in $Y$, such that $F\smallsetminus\\{0\\}\subset Y\smallsetminus
X$

The main result is that if $X$ and $Y$ are two spaces belonging to the chain
of theorem 2.12 then we have algebraic genericity for the couple $(X,Y)$. Here
we deal with the case $Y\neq\ell^{\infty}$. When $Y=\ell^{\infty}$ the proof,
due to Papathanasiou [8], follows a different method since $\ell^{\infty}$ is
non separable.

######  Lemma 4.2.

Let $X,Y$ be F-spaces, such that:

  1. 1.

$c_{00}\subset X\subset Y\subset\mathbb{C}^{\mathbb{N}_{0}}$, $X\neq Y$

  2. 2.

If $A\subset\mathbb{N}_{0}$ is infinite, there exists $y\in Y\smallsetminus X$
supported in $A$.

  3. 3.

$c_{00}$ is dense in $Y$

  4. 4.

For every $a\in X$ and $A\subset\mathbb{N}_{0}$ the product $a\chi_{A}$
belongs to $X$.

Then we have algebraic genericity for the pair $(X,Y)$

###### Proof.

Since $c_{00}$ is dense in Y it follows that
$c_{00}\cap(\mathbb{Q}+i\mathbb{Q})^{\mathbb{N}_{0}}$ is dense in Y.
Let $\\{x_{j}:j\in\mathbb{N}\\}$ be an enumeration of
$c_{00}\cap(\mathbb{Q}+i\mathbb{Q})^{\mathbb{N}_{0}}$ and let
$(A_{j})_{j\in\mathbb{N}}$ be a sequence of pairwise disjoint infinite subsets
of $\mathbb{N}$. By condition 2, for every $j\in{\mathbb{N}}$ there exists
$y_{j}\in Y\smallsetminus X$, $y_{j}$ supported in $A_{j}$.
Since $Y$ is a topological vector space, for every $j\in{\mathbb{N}}$, there
exists $c_{j}\in\mathbb{C}\smallsetminus\\{0\\}$ such that $c_{j}y_{j}\in
B_{Y}(0,\frac{1}{j})$. Let $f_{j}=x_{j}+c_{j}y_{j}\,\,\text{for every}\,\,j$.
From $d_{Y}(f_{j},x_{j})<\frac{1}{j}$ and the fact that Y does not have
isolated points it follows that $\\{f_{j}:j\in\mathbb{N}\\}$ is dense in Y.
Also, $f_{j}\notin X$ because $y_{j}\notin X$. This proves that
$F=\left<f_{1},f_{2},\dots\right>$ is dense in $Y$.
It suffices to show that $F\cap X=\\{0\\}$.
Suppose that there exists $\sum_{j=1}^{M}t_{j}f_{j}\in
X\smallsetminus\\{0\\}$, $t_{j}\in\mathbb{C}$. Since
$x_{1},x_{2}\dots,x_{M}\in c_{00}$ there exist $N$ such that $x_{j}(n)=0$ for
all $j=1,2,\dots,M$ and $n\geq N$. Let $j_{0}\in\\{1,2,\dots,M\\}$ be such
that $t_{j_{0}}\neq 0$.
Then from assumption 4 we have that
$\sum_{j=1}^{M}t_{j}f_{j}\chi_{A_{j_{0}}\cap[N,\infty)}\in X$

$\sum_{j=1}^{M}t_{j}f_{j}\chi_{A_{j_{0}}\cap[N,\infty)}=t_{j_{0}}y_{j_{0}}\chi_{A_{j_{0}}\cap[N,\infty)}=t_{j_{0}}y_{j_{0}}\chi_{[N,\infty)}=t_{j_{0}}y_{j_{0}}-t_{j_{0}}y_{j_{0}}\chi_{[1,N)}\in
X$

Since $t_{j_{0}}y_{j_{0}}\chi_{[1,N)}\in c_{00}\subset X$, $X$ is a vector
space and $t_{j_{0}}\neq 0$ it follows that $y_{j_{0}}\in X$, which is a
contradiction.

∎

######  Remark 4.3.

Using the terminology of [2] (Definition 2.1), the assumptions of our lemma
4.2 imply that $Y\setminus X$ is stronger than $c_{00}$. Thus, one can also
use Theorem 2.2 of [2] to obtain the result of the previous lemma. We mention
that although Theorem 2.2 of [2] is stated for Banach spaces, it can easily be
generalized to F-spaces.

######  Proposition 4.4.

If $X,Y$ are spaces from the chain of theorem 2.12 such that $X\subsetneq Y$,
and $Y\neq\ell^{\infty}$ then conditions 1,2,3,4 of Lemma 4.2 are satisfied.

###### Proof.

Let $X,Y$ be spaces from the chain of theorem 2.12 such that $X\subset Y$,
$X\neq Y$. It is obvious that condition 1 holds. We now prove that condition 2
holds. Let $X=\ell^{p},\bigcap_{p>a}\ell^{p},c_{0}$ or $\ell^{\infty}$. Since
the inclusion $X\subset Y$ is strict, we can choose $a\in Y\smallsetminus X$.
Let $A$ be an infinite subset of $\mathbb{N}$. We can spread out the elements
$a_{n}$ in such a way that the support of $a$ is contained in $A$. To be more
precise, let $A=\\{i_{1},\dots,i_{k},\dots\\}$ be an enumeration of $A$ such
that $i_{k}<i_{k+1}$ for all $k\in\mathbb{N}$. Set:

$\displaystyle b_{n}=\begin{cases}a_{k},\;n=i_{k},\,\,k\in\mathbb{N}\\\
0,\;n\notin A\end{cases}$

Then, $y=(b_{n})_{n}\in Y\smallsetminus X$ and has support in $A$. This proves
that condition 2 holds for these spaces.
If $X=A^{\infty}(\mathbb{D})$ then condition 2 follows from remark 2.9.
If $X=H(\mathbb{D})$ then we construct a sequence supported in
$A=\\{l_{1}<l_{2}<l_{3}<\cdots\\}$ :

$\displaystyle c_{n}=\left\\{\begin{array}[]{rcl}n^{n}&\mbox{if}&n=l_{k}\text{
for some k}\\\ 0&\mbox{otherwise}\end{array}\right.$

Then, $(c_{n})_{n}\in Y\smallsetminus X$ and has support in $A$.

We now prove that condition 3 holds.
If $Y=\ell^{p},c_{0},\mathbb{C}^{\mathbb{N}_{0}}$ then it is obvious that
$c_{00}$ is dense in $Y$.
Let $Y=\bigcap_{p>a}\ell^{p}$.
The fact that the inclusion map among the $\ell^{p}$ spaces is continuous and
$c_{00}$ is dense in each one of the spaces $\ell^{p}$ allows us to have
control over any finite set of $\ell^{p}$ spaces. This proves that $c_{00}$ is
dense in $\bigcap_{p>a}\ell^{p}$.
Let $Y=H(\mathbb{D})$. Every $a\in c_{00}$ can be identified with a complex
polynomial. It is well known that every holomorphic $f\in H(\mathbb{D})$ can
be approached by polynomials, uniformly on the compact subsets of
$\mathbb{D}$. It follows that $c_{00}$ is dense in $Y$.

We now prove that condition 4 holds.
Let $A$ be a subset of $\mathbb{N}_{0}$ and $a=(a_{n})_{n}\in X$. Then
$|a_{n}\chi_{A}|\leq|a_{n}|$ for all $n\in\mathbb{N}_{0}$ and from this
inequality condition 4 is obvious for the spaces
$\ell^{p},\bigcap_{q>a}\ell^{q},0\leq a<\infty,c_{0}$. If $(a_{n})_{n}\in
H(\mathbb{D})$, equivalently
$\limsup_{n}\left\\{\sqrt[n]{|a_{n}|}\right\\}\leq 1$, then
$\limsup_{n}\left\\{\sqrt[n]{\left|a_{n}\chi_{A}\right|}\right\\}\leq 1$,
which proves that $a\chi_{A}\in H(\mathbb{D})$. Similarly, if $(a_{n})_{n}\in
A^{\infty}(\mathbb{D})$, equivalently $n^{k}a_{n}\xrightarrow{n\to\infty}0$
for every $k\in\mathbb{N}$, then $n^{k}a_{n}\chi_{A}\xrightarrow{n\to\infty}0$
for every $k\in\mathbb{N}$, which implies that $a\chi_{A}\in
A^{\infty}(\mathbb{D})$. ∎

######  Theorem 4.5.

If $X,Y$ are spaces from the chain of Theorem 2.12 with $X\subsetneq Y$ and
$Y\neq\ell^{\infty}$, then we have algebraic genericity for the couple
$(X,Y)$.

###### Proof.

It follows from Lemma 4.2 and Proposition 4.4. ∎

If $Y=\ell^{\infty}$ then $X\subset c_{0}$. According to Papathanasiou [8]
there exists a vector subspace $F$ of $\ell^{\infty}$ dense in $\ell^{\infty}$
such that $F\smallsetminus\\{0\\}\subset\ell^{\infty}\smallsetminus
c_{0}\subset\ell^{\infty}\smallsetminus X$. Thus, we have algebraic genericity
for the couple $(X,\ell^{\infty})$. Combining this with theorem 4.5 we obtain:

######  Theorem 4.6.

Let $(X,Y)$ be spaces from the chain of Theorem 2.12 with $X\subset Y$ and
$X\neq Y$. Then we have algebraic genericity for the couple $(X,Y)$.

##  5 Spaceability

In the last section we examine whether there is spaceability for a couple of
spaces $(X,Y)$, where $X,Y$ are spaces in the chain of Theorem 2.12.

Let us first recall the definition:

######  Definition 5.1.

Let $X,Y$ be $F$ spaces, with $X\subset Y$ and $X\neq Y$. We say that we have
spaceability for the couple $(X,Y)$ if there exists a closed infinite
dimensional subspace $F$ of $Y$ such that $F\smallsetminus\\{0\\}\subset
Y\smallsetminus X$.

The main result is that if $X$ and $Y$ are two spaces of the chain of Theorem
2.12 such that $X\subsetneq Y$ then we have spaceability for the couple
$(X,Y)$.

######  Lemma 5.2.

Let $X,Y$ be F spaces such that:

  1. 1.

$X\subsetneq Y\subset\mathbb{C}^{\mathbb{N}_{0}}$

  2. 2.

If $A\subset\mathbb{N}_{0}$ is infinite then there exists $y\in
Y\smallsetminus X$ supported in $A$.

  3. 3.

Convergence in $Y$ implies pointwise convergence.

  4. 4.

For every $a\in X$ and $A\subset\mathbb{N}$ the product $a\chi_{A}$ belongs to
$X$.

Then we have spaceability for the pair $(X,Y)$.

###### Proof.

Let $(A_{j})_{j\in\mathbb{N}}$ be a sequence of pairwise disjoint infinite
subsets of $\mathbb{N}$. By condition 2, for every $j$ there exists $y_{j}\in
Y\smallsetminus X$ supported in $A_{j}$.
Consider $F=\overline{\left<y_{j}|j\in\mathbb{N}\right>}$.
It is obvious that $F$ is a closed linear subspace of $Y$. Since the sets
$A_{j}$ are disjoint, it follows that $F$ is infinite dimensional.
It remains to show that if $f\in F,\ f\neq 0$ then $f\notin X$.
Indeed, there exists a sequence
$f^{m}\in\left<\\{y_{j}|j\in\mathbb{N}\\}\right>$ such that
$f^{m}\xrightarrow{m\to\infty}f$ in $Y$ and by condition 3 we have
$f^{m}(i)\xrightarrow{m\to\infty}f(i)$ for all $i\in\mathbb{N}_{0}$. For every
$m$ we can write $f^{m}=c_{1}^{m}y_{1}+c_{2}^{m}y_{2}+c_{3}^{m}y_{3}+\dots$
where finitely many of $c_{j}^{m}$ are non zero, i.e. for every $m$ the set
$\\{j\in\mathbb{N}\ |\ c_{j}^{m}\neq 0\\}$ is finite.
But $f\neq 0$, so there exists $i_{0}\in\mathbb{N}$ such that $f(i_{0})\neq
0$. If $i_{0}\notin\bigcup_{j}A_{j}$ then $f^{m}(i_{0})=0$ for all $m$, so
$f(i_{0})=\lim_{m}f^{m}(i_{0})=0$, which is a contradiction.
Hence, $i_{0}\in A_{j_{0}}$ for some $j_{0}\in\mathbb{N}$.
Since $A_{1},A_{2},\dots$ are pairwise disjoint, we have
$f^{m}(i)=c_{j_{0}}^{m}y_{j_{0}}(i)$ for all $i\in A_{j_{0}}$.
If $y_{j_{0}}(i_{0})=0$ then $f^{m}(i_{0})=0$ for all $m$, which is a
contradiction as above, so $y_{j_{0}}(i_{0})\neq 0$.
Let
$c_{j_{0}}=\lim_{m}c_{j_{0}}^{m}=\lim_{m}\frac{f^{m}(i_{0})}{y_{j_{0}}(i_{0})}=\frac{f(i_{0})}{y_{j_{0}}(i_{0})}\neq
0$.
Then for all $i\in A_{j_{0}}$ we have

$f(i)=\lim_{m}f^{m}(i)=\lim_{m}c_{j_{0}}^{m}y_{j_{0}}(i)=c_{j_{0}}y_{j_{0}}(i)$

thus
$f\chi_{A_{j_{0}}}=c_{j_{0}}y_{j_{0}}\chi_{A_{j_{0}}}=c_{j_{0}}y_{j_{0}}\notin
X$ and by condition 4 we have $f\notin X$ as needed.

∎

######  Theorem 5.3.

Let $(X,Y)$ be spaces from the chain of Theorem 2.12 with $X\subsetneq Y$.
Then we have spaceability for the couple $(X,Y)$.

###### Proof.

It suffices to see that conditions 1-4 of Lemma 5.2 hold for any pair of
spaces $X,Y$ from the chain of theorem 2.12 with $X\subsetneq Y.$
Conditions 2 and 4 have been proved in Proposition 4.4.
Condition 3 has been proved in Section 2. ∎

## References

  * [1] R.M. Aron, L. Bernal-González, D. Pellegrino, J.B. Seoane-Sepúlveda, Lineability: The Search for Linearity in Mathematics, Monographs and Research Notes in Mathematics, Chapman and Hall/CRC, 2015
  * [2] R.M. Aron, F.J. García-Pacheco, D. Pérez-García, J.B. Seoane-Sepúlveda, On dense-lineability of sets of functions on ${\mathbb{R}}$, Topology 48: 149-156, 2009
  * [3] F. Bayart, K.G. Grosse-Erdmann, V. Nestoridis and C. Papadimitropoulos, Abstract theory of universal series and applications, Proc. Lond. Math. Soc. (3), 96(2): 417-463, 2008
  * [4] L. Bernal-González and V. Nestoridis, Topological and algebraic genericity in chains of sequence spaces and fuction spaces, Bull. Hellenic Math. Soc. 65: 9-16, 2021
  * [5] L. Bernal-González, D. Pellegrino and J.B. Seoane-Sepúlveda, Linear subsets of nonlinear sets in topological vector spaces, Bull. Amer. Math. Soc. (N.S.), 51(1): 71-130, 2014
  * [6] V. Gregoriades, Intersections of $\ell^{p}$ spaces in the Borel hierarchy, J. Math. Anal. Appl. 498, Issue 1, 124922, 2021, see also arXiv: 2008.12996
  * [7] V. Nestoridis, A project about chains of spaces regarding topological and algebraic genericity and spaceability, arXiv: 2005.01023, 2020
  * [8] D. Papathanasiou, Dense lineabity and algebrability of $\ell^{\infty}\setminus c_{0}$, Proc. Amer. Math. Soc. (to appear), see also  arXiv: 2102.03199
  * [9] W. Rudin, Functional Analysis, McGraw-Hill

Keywords and phrases: Topological genericity, algebraic genericiy,
spaceability, Baire’s theorem, $\ell^{p}$ spaces.

2010 MSC: Primary 15A03; Secondary 46E10, 46E15.

Department of Mathematics, University of Athens, Panepistimioupolis 157-84,
Athens, Greece.

E-mail Addresses<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>