# Image closure of symmetric wide-matrix varieties

Jan Draisma, Rob H. Eggermont, Azhar Farooq, and Leandro Meier

###### Abstract.

Let $X$ be an affine scheme of $k\times{\mathbb{N}}$-matrices and $Y$ be an
affine scheme of ${\mathbb{N}}\times\cdots\times{\mathbb{N}}$-dimensional
tensors. The group $\operatorname{Sym}({\mathbb{N}})$ acts naturally on both
$X$ and $Y$ and on their coordinate rings. We show that the Zariski closure of
the image of a $\operatorname{Sym}({\mathbb{N}})$-equivariant morphism of
schemes from $X$ to $Y$ is defined by finitely many
$\operatorname{Sym}({\mathbb{N}})$-orbits in the coordinate ring of $Y$.
Moreover, we prove that the closure of the image of this map is
$\operatorname{Sym}({\mathbb{N}})$-Noetherian, that is, every descending chain
of $\operatorname{Sym}({\mathbb{N}})$-stable closed subsets stabilizes.

JD was partially supported by Vici grant 639.033.514 from the Netherlands
Organisation for Scientific Research (NWO) and Project Grant 200021_191981
from the Swiss National Science Foundation (SNF). AF was supported by Vici
grant 639.033.514. RE was supported by Veni grant 016.Veni.192.113 from NWO

##  1\. Introduction

In recent years, many finiteness properties of rings with countably many
variables and infinite dimensional varieties have been studied, especially of
those acted upon by the infinite symmetric group. A number of fundamental
results have been established, but still many have yet to be discovered.

Most of these results build on the theorem from [Coh67, Coh87], rediscovered
in [AH07, HS12], that the polynomial ring in $k\times{\mathbb{N}}$ variables
is $\operatorname{Sym}({\mathbb{N}})$-Noetherian with the natural action of
the symmetric group $\operatorname{Sym}({\mathbb{N}})$. This implies that the
space of $k\times{\mathbb{N}}$-matrices equipped with the induced action of
$\operatorname{Sym}({\mathbb{N}})$ is topologically
$\operatorname{Sym}({\mathbb{N}})$-Noetherian. However, already the space of
${\mathbb{N}}\times{\mathbb{N}}$-matrices equipped with the natural action of
$\operatorname{Sym}({\mathbb{N}})$, or even with the action of
$\operatorname{Sym}({\mathbb{N}})\times\operatorname{Sym}({\mathbb{N}})$, is
not equivariantly Noetherian, and it gets only worse for higher-dimensional
tensors. This is problematic, because many varieties of relevance to
applications, such as the $k$-factor model [Dra10] and hierarchical models
[HS12] naturally live in matrix or tensor spaces and are preserved by (copies
of) the symmetric group.

Hence it is interesting to find $\operatorname{Sym}({\mathbb{N}})$-stable
subvarieties of ${\mathbb{N}}\times{\mathbb{N}}$-matrices, or
${\mathbb{N}}\times\cdots\times{\mathbb{N}}$-tensors, that are defined by
finitely many orbits of equations and equivariantly Noetherian. In this paper
we study such subvarieties that arise as image closures of
$\operatorname{Sym}({\mathbb{N}})$-equivariant maps from the space of
$k\times{\mathbb{N}}$-matrices, and we show that these are always defined,
set-theoretically, by finitely many $\operatorname{Sym}({\mathbb{N}})$-orbits
of equations, as well as themselves topologically
$\operatorname{Sym}({\mathbb{N}})$-Noetherian.

###  1.1. Main Theorem

All algebras and schemes are defined over a Noetherian ring $K$. All schemes
are affine schemes and we will usually drop the adjective affine. Let
$\mathbf{FI}$ denotes the category of finite sets with injective maps. An
important insight from [CEF15] is that functors from $\mathbf{FI}$ are the
right language for studying structures with increasing numbers of variables
acted upon by increasing symmetric groups.

An $\mathbf{FI}$-algebra over $K$ is a covariant functor from $\mathbf{FI}$ to
the category of algebras over $K$. An $\mathbf{FI}$-ideal $I$ of an
$\mathbf{FI}$-algebra $A$ assigns to each finite set $S$ an ideal $I(S)$ of
$A(S)$, in such a manner that the algebra homomorphism $A(\pi):A(S)\to A(T)$
corresponding to any $\pi\in\operatorname{Hom}\nolimits_{\mathbf{FI}}(S,T)$
maps $I(S)$ into $I(T)$. An $\mathbf{FI^{op}}$-scheme over $K$ is a
contravariant functor from $\mathbf{FI}$ to the category of schemes over $K$.
A closed subscheme $Z$ of an $\mathbf{FI^{op}}$-scheme $X$ is a subfunctor of
$X$ such that, for each finite set $S$, $Z(S)$ is a closed subscheme of
$X(S)$. Morphisms of $\mathbf{FI}$-algebras are natural transformations of
functors. Morphisms of $\mathbf{FI^{op}}$-schemes are defined dually.

We say that an $\mathbf{FI}$-algebra $A$ is finitely generated in width at
most $1$ if $A$ is generated by $A(\emptyset)$ and $A(\\{1\\})$, and both of
these are finitely generated. This is equivalent to the statement that $A$ can
be realised as a quotient (in the category of $\mathbf{FI}$-algebras over $K$)
of an algebra of the form

$S\mapsto K[x_{ij}\mid i\in[k],j\in S];$

see [DEF22, Lemma 2.6.8]. Geometetrically, $\operatorname{Spec}(A)$ is then an
$\mathbf{FI^{op}}$-subscheme over $K$ of the scheme that sends $S$ to $k\times
S$-matrices.

######  Theorem 1.1.1 (Main Theorem).

Let $\varphi$ be a morphism of $\mathbf{FI}$-algebras $B\rightarrow A$, where
$A$ and $B$ both are finitely generated $\mathbf{FI}$-algebras over a
Noetherian ring $K$. Suppose, moreover, that $A$ is generated in width at most
$1$. Then the Zariski closure $\overline{\operatorname{Im}(\varphi^{*})}$ of
the image of $\operatorname{Spec}(A)$ under the dual map $\varphi^{*}$ is
defined, as a set, by finitely many elements in $B$. Equivalently, there exist
a finitely generated $\mathbf{FI}$-ideal $I$ in $B$ such that the radical of
$I$ is equal to the radical of the kernel ${\rm Ker}\,\varphi$.
Moreover, $\overline{\operatorname{Im}(\varphi^{*})}$ is topologically
Noetherian, that is, it satisfies the descending chain condition on reduced
closed subschemes.

An immediate consequence of the Main Theorem is the following.

######  Corollary 1.1.2.

For any $\operatorname{Sym}({\mathbb{N}})$-equivariant morphism $\varphi$ of
$K$-schemes from the scheme of $k\times{\mathbb{N}}$-matrices to the scheme of
${\mathbb{N}}\times\cdots\times{\mathbb{N}}$-tensors, the image closure
$\overline{\operatorname{Im}(\varphi)}$ of $\varphi$ is defined, set-
theoretically, by finitely many $\operatorname{Sym}({\mathbb{N}})$-orbits of
equations. Furthermore, it is topologically
$\operatorname{Sym}({\mathbb{N}})$-Noetherian: any descending chain

$\overline{\operatorname{im}(\varphi)}\supseteq X_{1}\supseteq
X_{2}\supseteq\ldots$

of reduced, closed subschemes stabilises. $\square$

We do not know whether $\ker\varphi$ itself is necessarily finitely generated.

######  Conjecture 1.1.3.

Let $\varphi$ be the $\mathbf{FI}$-algebra homomorphism defined in the Main
Theorem 1.1.1. Then the $\mathbf{FI}$-ideal ${\rm Ker}\,\varphi$ is finitely
generated.

A particular case of the above conjecture was stated in [[]Conjecture
5.10]aschenbrenner-hillar:finitesymmetric and proved in [Dra+13] when
generators of the $\mathbf{FI}$-algebra $B$ are mapped under $\varphi$ to
monomials in $A$.

On the other hand, in the setting of the Main Theorem, there are examples
where $\overline{\operatorname{Im}(\varphi^{*})}$ is not scheme-theoretically
Noetherian, i.e., has an infinite strictly descending chain of closed (but
non-reduced) $\mathbf{FI^{op}}$-subschemes: in [DKK, Theorem 43] it is proved
that the cone over the Grassmannian of $2\times S$-spaces, with
$S\in\mathbf{FI}$, has this bad behaviour in characteristic $2$ (but not in
characteristic zero due to the existence of Reynolds operators, see [Dra10]).

###  1.2. Relations to existing literature

Motivation for this work comes from finiteness questions about chains of
$\operatorname{Sym}$-invariant ideals that arise in commutative algebra and
adjacent areas. These questions concern the behaviour of homological
invariants [Bie+20, Le+20, Le+21, LN22], bivariate Hilbert series recording
both degree and number of variables [KLS17, NR17], and irreducible components
of $\mathbf{FI^{op}}$-varieties [NS, NS22, DEF22]. Some of these developments
were inspired by challenging questions in algebraic statistics [AH07, DSS06,
Dra10, BD11], and similar techniques have been applied in discrete geometry
[KVR22] and real-algebraic geometry [KR22]. The most efficient framework, in
our opinion, to study such questions is that of $\mathbf{FI}$-algebras and
$\mathbf{FI^{op}}$-schemes, [NR19, DEF22].

To illustrate the strength of our Main Theorem, we explain how it immediately
implies the main result in [Dra10].

######  Example 1.2.1.

In [DSS06] the question was raised whether the ideal of polynomial relations
among the entries of a matrix of the form $\Sigma=AA^{T}+D$, with $A$ running
through ${\mathbb{R}}^{n\times k}$ and $D$ running through the (positive-
definite) diagonal matrices, is generated by a finite number of
$\operatorname{Sym}([n])$-orbits for $n\to\infty$. The set of all such
matrices is the Gaussian $k$-factor model. This question remains open to this
date. However, in [BD11] an affirmative answer was given for $k=2$, and in
[Dra10] an affirmative answer for a set-theoretical version was established
for arbitrary $k$. The latter also follows from the Main Theorem, because the
map that sends the matrix entry $\sigma_{ij}$ to the entry
$\sum_{l=1}^{k}a_{il}a_{jl}+\delta_{ij}\cdot d_{ii}$ is a homomorphism from
the $\mathbf{FI}$-algebra $S\mapsto{\mathbb{R}}[\sigma_{ij}\mid i,j\in S]$ to
the $\mathbf{FI}$-algebra $S\mapsto{\mathbb{R}}[a_{il},d_{ii}\mid l\in[k],i\in
S]$, and the latter is generated in width $\leq 1$.

In the example, as in the rest of the paper, $[k]$ stands for
$\\{1,\ldots,k\\}$, and in particular $[0]=\emptyset$.

###  1.3. Organisation of this paper

In Section 2 we recall elementary properties of finitely generated
$\mathbf{FI}$-algebras. Section 3 contains basic results about topological
Noetherianity. Section 4 is devoted to the reduction of the Main Theorem 1.1.1
to the case of free $\mathbf{FI}$-algebras. In Section 5 we prove our Main
Theorem. To this end we prove that image of the map $\varphi^{*}$ lies in the
closed subscheme of $\operatorname{Spec}(B)$ defined by off-diagonal
$(l+1)\times(l+1)$-subdeterminants of flattnings, see Lemma 5.2.5. This
subscheme is defined by finitely many equations (Lemma 5.2.4) and is contained
in the image of a topologically Noetherian space, see Proposition 5.2.10 and
Lemma 5.2.8.

A result of potentially independent interest is the following tensor
completion result: a tensor labelled by the tuples in $S\times\cdots\times S$
in which no entry appears more than once (an off-diagonal tensor) and of which
all the meaningful $(l+1)\times(l+1)$-subdeterminants of flattenings are zero,
can be completed to a full tensor (including the diagonal) of some bounded
rank; see 5.2.10.

##  2\. Preliminaries

In this section we recall definitions and fundamental results about
$\mathbf{FI}$-algebras and $\mathbf{FI^{op}}$-schemes. For more details about
them see [NR19, DEF22].

###  2.1. $\mathbf{FI}$-algebras and $\mathbf{FI^{op}}$-schemes

The following notion was introduced in [CEF15].

######  Definition 2.1.1.

The category $\mathbf{FI}$ (for Finite sets with Injections) has as objects
finite sets and for finite sets $S$ and $T$ the set
$\operatorname{Hom}\nolimits_{\mathbf{FI}}(S,T)$ is the set of injections from
$S$ to $T$. $\mathbf{FI^{op}}$ denotes its opposite category.

Let $K$ be a commutative ring with $1$. All $K$-algebras $A$ are required to
be commutative, have a $1$, and the homomorphism $K\to A$ is required to send
$1$ to $1$. Homomorphisms of $K$-algebras are unital ring homomorphisms $A\to
B$ compatible with the homomorphisms from $K$ into them.

######  Definition 2.1.2.

An $\mathbf{FI}$-algebra $A$ over $K$ is a covariant functor from
$\mathbf{FI}$ to the category of algebras over $K$. Dually, $A$ gives rise to
a contravariant functor $X$ from $\mathbf{FI}$ to the category of affine
schemes over $K$. We call such a functor an $\mathbf{FI^{op}}$-scheme over
$K$.

A morphism $A\to B$ of $\mathbf{FI}$-algebras over $K$ is a natural
transformation of functors from $A$ to $B$: it consists of a $K$-algebra
homomorphism $\varphi_{S}:A(S)\to B(S)$ for all finite sets $S$ such that for
all $S,T\in\mathbf{FI}$ and for each injection $\pi$ from $S$ to $T$, the
following diagram commutes.

$\textstyle{A(S)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{S}}$$\scriptstyle{A(\pi)}$$\textstyle{B(S)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{B(\pi)}$$\textstyle{A(T)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{T}}$$\textstyle{B(T).}$

Morphisms of $\mathbf{FI^{op}}$-schemes are defined dually. We often leave out
the subscript $S$ in $\varphi_{S}$, and often just write $\pi$ instead of
$A(\varphi)$ when $A$ is clear from the context.

###  2.2. $\mathbf{FI}$-algebras finitely generated in width $\leq d$

$\mathbf{FI}$-algebras that are finitely generated in width at most $d$ are
the main characters of this paper. By a subalgebra $B$ of an
$\mathbf{FI}$-algebra $A$ over $K$ we mean an $\mathbf{FI}$-algebra $B$ over
$K$ such that for each finite set $S$, $B(S)$ is a subalgebra of $A(S)$, and
for each injection $\sigma:S\rightarrow T$, $B(\sigma)$ is the restriction of
$A(\sigma)$ to $B(S)$.

######  Definition 2.2.1.

An $\mathbf{FI}$-algebra $A$ over $K$ is said to be finitely generated if
there is a finite set $D\subset\bigsqcup_{S\in\mathbf{FI}}A(S)$ which is not
contained in any proper subalgebra of $A$. If such $D$ exists, we say that $A$
is generated by $D$.

######  Definition 2.2.2.

Let $A$ be an $\mathbf{FI}$-algebra over $K$. For $S\in\mathbf{FI}$ and $f\in
A(S)$, we call the minimal $n$ such that $f$ lies in $A(\pi)A([n])$ for some
injective map $\pi:[n]\rightarrow S$, the width of $f$, denoted $w(f)$.

######  Definition 2.2.3.

An $\mathbf{FI}$-algebra $A$ over $K$ is generated in width $\leq d$ if there
exists a collection $(f_{i}\in A(S_{i}))_{i\in I}$ of elements of width $\leq
d$ that generates $A$.

######  Definition 2.2.4.

An $\mathbf{FI}$-algebras $A$ over $K$ is said to be finitely generated in
width $\leq d$ if $A$ is finitely generated and generated in width $\leq d$.

######  Remark 2.2.5.

It is straightforward to see that this is equivalent to the condition that $A$
is generated by a finite collection of elements $f_{i}\in A(S_{i})$ of width
$\leq d$.

The following $\mathbf{FI}$-algebra $B_{d}$ is a building block for
$\mathbf{FI}$-algebras that are finitely generated in width $\leq d$.

######  Definition 2.2.6.

For a non-negative integer $d$, denote by $B_{d}$ the $\mathbf{FI}$-algebra
over a ring $K$ that maps a finite set $S$ to a $K$-algebra

$\displaystyle B_{d}(S)=K[y_{i_{1},i_{2},...,i_{d}}:i_{1},i_{2},...,i_{d}\in
S\,\,\text{and}\,\,i_{j}\neq i_{l}\,\,\text{when}\,\,j\neq l]$

and for an injection $\sigma:S\rightarrow T$, the $K$-algebra homomorphism
$B_{d}(\sigma)$ is determined by
$B_{d}(\sigma)(y_{i_{1},i_{2},...,i_{d}}):=y_{\sigma(i_{1}),\sigma(i_{2}),...,\sigma(i_{d})}$.
It is easy to see that $B_{d}$ is generated by the single element
$y_{1,2,...,d}\in B_{d}([d])$, of width $d$.

######  Remark 2.2.7.

  1. (1)

We think of the elements of $\operatorname{Spec}B_{d}$ as $S\times
S\times...\times S$-tensors of which only the entries outside the big diagonal
$\\{(i_{1},i_{2},...,i_{d}):\exists\,\,j<l,i_{j}=i_{l}\\}$ are given. We call
these tensors “off-diagonal tensors”.

  2. (2)

It is easy to show that the tensor product of such algebras is again finitely
generated in width at most the largest of the relevant $d$.

  3. (3)

For fixed non-negative integers $d,k_{0},k_{1},k_{2},...,k_{d}$,
$B[k_{0},k_{1},k_{2},...,k_{d}]$ denotes the $\mathbf{FI}$-algebra
$\bigotimes_{i=0}^{d}B_{i}^{\otimes k_{i}}$, which is finitely generated in
width at most $d$.

######  Definition 2.2.8.

An $\mathbf{FI^{op}}$-scheme of finite type over $K$ is the spectrum of a
finitely generated $\mathbf{FI}$-algebra over $K$.

######  Definition 2.2.9.

A width-$d$ $\mathbf{FI^{op}}$-scheme over $K$ is the spectrum of an
$\mathbf{FI}$-algebra over $K$ that is generated in width $\leq d$.

######  Definition 2.2.10.

A width-$d$ $\mathbf{FI^{op}}$-scheme of finite type over $K$ is the spectrum
of an $\mathbf{FI}$-algebra over $K$ that is finitely generated in width $\leq
d$.

We record the following lemmas for the later use.

######  Lemma 2.2.11.

Let $A$ be an $\mathbf{FI}$-algebra. Then any homomorphism
$\varphi:B_{d}\rightarrow A$ of $\mathbf{FI}$-algebras is completely
determined by the image of $y_{1,2,...,d}\in B_{d}([d])$. Moreover, $B_{d}$
has the following universal property: if $a\in A([d])$ is any element of $A$,
then there exists a unique homomorphism $\varphi:B_{d}\rightarrow A$ such that
$\varphi(y_{1,2,...,d})=a$.

###### Proof.

Let $y_{i_{1},i_{2},...,i_{d}}$ be a variable in $B_{d}(S)$ where
$i_{1},i_{2},...,i_{d}\in S$. Let $\sigma:[d]\rightarrow S$ be the injection
that sends $j$ to $i_{j}$. Then we have

$\varphi(y_{i_{1},i_{2},...,i_{d}})=\varphi(B_{d}(\sigma)y_{1,2,...,d})=A(\sigma)\varphi(y_{1,2,...,d}).$

Thus the image of $y_{1,2,...,d}$ completely determines the map $\varphi$.

To prove the last statement, for $i_{1},\ldots,i_{d}\in S$ distinct, define
$\varphi(y_{i_{1},i_{2},...,i_{d}}):=A(\sigma)a$, where $\sigma:[d]\to S$ is
the map that sends $j$ to $i_{j}$, and extend this to a homomorphism
$B_{d}(S)\to A(S)$ in the unique manner. A straightforward computation shows
that this does, indeed, define an $\mathbf{FI}$-algebra homomorphism $B\to A$
with $\varphi(y_{1,\ldots,d})=a$. ∎

######  Remark 2.2.12.

Lemma 2.2.11 implies that the $\mathbf{FI}$-algebra
$B[k_{0},k_{1},k_{2},...,k_{d}]$ has the same universal property when $a$ is
replaced by a tuple in $\prod_{e=0}^{d}A([e])^{k_{e}}$.

######  Lemma 2.2.13.

Let $A$ be an $\mathbf{FI}$-algebra that is finitely generated in width at
most $d$. Then there exists a surjective homomorphism
$\varphi:B[k_{0},k_{1},k_{2},...,k_{d}]\rightarrow A$ for some non-negative
integers $k_{0},k_{1},k_{2},...,k_{d}$.

###### Proof.

Let $k_{i}$ be the number of generators of width $i$. Assume
$h_{1}^{(i)},h_{2}^{(i)},...,h_{k_{i}}^{(i)}\in A([i])$ are generators of
width $i$. Consider the unique $\mathbf{FI}$-algebra homomorphism
$\varphi_{i}:B_{i}^{\otimes k_{i}}\rightarrow A$ that sends
$y_{1,2,...,i}^{(l)}\in B_{i}([i])^{\otimes k_{i}}$ to $h_{l}^{(i)}$ for
$l=1,2,...,k_{i}$. Then $\varphi$ is surjective by construction. Then the
tensor map $\bigotimes_{i=0}^{d}:B[k_{0},k_{1},k_{2},...,k_{d}]\rightarrow A$
is the required surjective morphism. ∎

######  Remark 2.2.14.

Dually, $\operatorname{Spec}(A)$ embeds in a finite product of affine spaces
of off-diagonal tensors.

###  2.3. Shifting

The idea of shifing an $\mathbf{FI}$-structure over a finite set goes back to
[CEF15]. It has also been used effectively in [DEF22].

######  Definition 2.3.1.

Let $T_{0}$ be a finite set. Then
$\operatorname{Sh}_{T_{0}}:\mathbf{FI}\to\mathbf{FI}$ is the functor that
sends a finite set $T$ to the disjoint union $T_{0}\sqcup T$ and an injection
$\sigma:T\rightarrow S$ to $\operatorname{Sh}_{T_{0}}\sigma:T_{0}\sqcup T\to
T_{0}\sqcup S$ that is the identity on $T_{0}$ and equal to $\sigma$ on $T$.
For an $\mathbf{FI}$-algebra $A$ over $K$ we write
$\operatorname{Sh}_{T_{0}}A:=A\circ\operatorname{Sh}_{T_{0}}$ and for the
$\mathbf{FI^{op}}$-scheme $X=\operatorname{Spec}(A)$ over $K$ we write
$\operatorname{Sh}_{T_{0}}X:=X\circ\operatorname{Sh}_{T_{0}}=\operatorname{Spec}(\operatorname{Sh}_{T_{0}}A)$.

######  Remark 2.3.2.

If $A$ is finitely generated in width at most $d$, then so is
$\operatorname{Sh}_{T_{0}}A$; and hence, if $X$ is a width $\leq d$
$\mathbf{FI^{op}}$-scheme of finite type over $K$, then so is
$\operatorname{Sh}_{T_{0}}X$.

Furthermore, for a homomorphism $\varphi:A\to B$ of $\mathbf{FI}$-algebras
over $K$, we write $\operatorname{Sh}_{T_{0}}\varphi$ for the morphism
$\operatorname{Sh}_{T_{0}}A\to\operatorname{Sh}_{T_{0}}B$ that sends $T$ to
$\varphi(T_{0}\sqcup T)$, and similarly for morphisms of
$\mathbf{FI^{op}}$-schemes. A straightforward check shows that
$\operatorname{Sh}_{T_{0}}$ is a covariant functor from $\mathbf{FI}$-algebras
over $K$ into itself and from $\mathbf{FI^{op}}$-schemes over $K$ into itself.

######  Lemma 2.3.3.

For a fixed finite set $T_{0}$,
$\operatorname{Sh}_{T_{0}}B[k_{0},k_{1},k_{2},...,k_{d}]$ is isomorphic to
$B[k^{\prime}_{0},k^{\prime}_{1},k^{\prime}_{2},...,k^{\prime}_{d-1},k_{d}]$
for some non-negative integers
$k_{0}^{\prime},k_{1}^{\prime},...,k_{d-1}^{\prime}$.

###### Proof.

We have $\operatorname{Sh}_{T_{0}}(A\otimes
C)\cong(\operatorname{Sh}_{T_{0}}A)\otimes(\operatorname{Sh}_{T_{0}}C)$, for
any $\mathbf{FI}$-algebras $A$ and $C$. So it suffices to show that $B_{d}$ is
isomorphic to $B[k_{0}^{\prime},k_{1}^{\prime},...,k_{d-1}^{\prime},1]$. Note
that

$\displaystyle\operatorname{Sh}_{T_{0}}B_{d}(T)=K[y_{i_{1},i_{2},...,i_{d}}:i_{1},i_{2},...,i_{d}\in
T_{0}\sqcup T\,\,\text{and}\,\,i_{l}\neq i_{m}\,\,\text{when}\,\,l\neq m]$
$\displaystyle\cong\left(\bigotimes_{e=0}^{d-1}B_{e}(T)^{\otimes\binom{d}{e}\times|T_{0}|\times(|T_{0}|-1)\times...\times(|T_{0}|-d+e+1)}\right)\otimes(B_{d}(T)),$

where the exponent counts the number of ways of filling $d-e$ of the $d$ index
positions with elements of $T_{0}$. Thus $\operatorname{Sh}_{T_{0}}B_{d}\cong
B[k^{\prime}_{0},k^{\prime}_{1},k^{\prime}_{2},...,k^{\prime}_{d-1},1]$. ∎

##  3\. Noetherianity

###  3.1. Noetherianity for $\mathbf{FI}$-algebras and
$\mathbf{FI^{op}}$-schemes

######  Definition 3.1.1.

Given an $\mathbf{FI}$-algebra $A$ over $K$, we define its direct limit
$\overrightarrow{A}=\underrightarrow{\lim}\,A([n])$ using the direct system
$(A([n]),A(i_{m,n}))$, where $m\leq n$ and $i_{m,n}:[m]\rightarrow[n]$ is the
natural inclusion map.
Dually, given an $\mathbf{FI^{op}}$-scheme $X$ over $K$, we define its inverse
limit $\overleftarrow{X}=\underleftarrow{\lim}\,X([n])$ using the inverse
system $(X([n]),X(i_{m,n}))$, where $m\leq n$ and $i_{m,n}:[m]\rightarrow[n]$
is the natural inclusion map.

If $A$ be an $\mathbf{FI}$-algebra, then there is an induced action of the
group $\operatorname{Sym}(\infty)=\bigcup_{n\geq 1}\operatorname{Sym}(n)$,
where $\operatorname{Sym}(n)$ denotes the symmetric group on $n$ letters and
is naturally embedded into $\operatorname{Sym}(n+1)$ as the stabilizer of
$\\{n+1\\}$, on the direct limit $\overrightarrow{A}$. An
$\mathbf{FI}$-algebra is called Noetherian if it satisfies the ascending chain
condition on $\mathbf{FI}$-ideals. It is well known that if an
$\mathbf{FI}$-algebra $A$ is Noetherian then its direct limit
$\overrightarrow{A}$ is $\operatorname{Sym}(\infty)$-Noetherian, i.e.,it
satisfies the ascending chain condition on $\operatorname{Sym}(\infty)$ stable
ideals.
Duall, an $\mathbf{FI^{op}}$-scheme $X$ is called Noetherian if it satisfies
the descending chain condition on closed $\mathbf{FI}$-subschemes, and
topologically Noetherian if it satisfies the descending chain condition on
closed and reduced $\mathbf{FI}$-subschemes. Again the inverse limit
$\overleftarrow{X}$ of a topologically Noetherian $\mathbf{FI^{op}}$-scheme
$X$ is topologically $\operatorname{Sym}(\infty)$-Noetherian i.e. it satisfies
the descending chain condition on $\operatorname{Sym}(\infty)$ stable closed
reduced subschemes. To save words, from now on, we will just use the word
“closed subset” to mean “reduced subscheme”.

######  Example 3.1.2.

The direct limit of the $\mathbf{FI}$-algebra $B_{1}^{\otimes k}$ is
(isomorphic with) the polynomial ring $K[x_{i,j}:i\in[k],j\in{\mathbb{N}}]$
with the following induced action: $\sigma(x_{i,j})=x_{i,\sigma(j)}$ where
$\sigma\in\operatorname{Sym}(\infty)$.
The inverse limit of the $\mathbf{FI^{op}}$-scheme
$\operatorname{Spec}B_{1}^{\otimes k}$ is the space of
$k\times{\mathbb{N}}$-matrices where $\operatorname{Sym}(\infty)$ acts by
permuting columns of such matrices.

######  Theorem 3.1.3.

[AH07, Coh67, Coh87, HS12] Every $\mathbf{FI}$-algebra $A$ over a Noetherian
ring $K$ that is finitely generated in width $\leq 1$ is Noetherian, i.e., if
$I_{1}\subseteq I_{2}\subseteq\cdots$ is an ascending chain of ideals in $A$,
then $I_{n}=I_{n+1}$ for all $n\gg 0$.

######  Remark 3.1.4.

In fact, $A$ is Noetherian in a stronger sense: any finitely generated
$A$-module satisfies the ascending chain condition on submodules [NR19,
Theorem 6.15].
It is easy to see that if an $\mathbf{FI}$-algebra $A$ is Noetherian, then the
$\mathbf{FI^{op}}$-scheme $X$ defined by $A$ is topologically Noetherian.

######  Example 3.1.5.

The $\mathbf{FI}$-algebra $B_{1}^{\otimes k}$ over a Noetherian ring $K$ is
Noetherian because it is finitely generated in width at most 1. So the
polynomial ring $K[x_{i,j}:i\in[k],j\in{\mathbb{N}}]$ is
$\operatorname{Sym}(\infty)$-Noetherian.
Dually, the $\mathbf{FI^{op}}$-scheme $\operatorname{Spec}B_{1}^{\otimes k}$
over a Noetherian ring $K$ is topologically Noetherian. Thus its inverse
limit, the space of $k\times{\mathbb{N}}$-matrices, is
$\operatorname{Sym}(\infty)$-Noetherian.

For the (easy) proofs of the following lemmas we refer to [DK14, Section 5].

######  Lemma 3.1.6.

Let $X$ be an $\mathbf{FI^{op}}$-scheme that is topologically Noetherian. Then
any closed subset of $X$ is topologically Noetherian with respect to the
induced topology.

######  Lemma 3.1.7.

Let $X$ and $Y$ be topologically Noetherian $\mathbf{FI^{op}}$-schemes. Then
the disjoint union $X\sqcup Y$ defined by $X\sqcup Y(S)=X(S)\sqcup Y(S)$ is
topologically Noetherian with respect to the disjoint union topology.

######  Lemma 3.1.8.

Let $\psi$ be a homomorphism of $\mathbf{FI^{op}}$-schemes from $X$ to $Y$ and
$X$ is topologically Noetherian. Then $\operatorname{Im}(\psi)$ is
topologically Noetherian with respect to the topology induced from $Y$.

##  4\. Reduction to the Case of Free FI-algebras

This section is devoted to the reduction of our main theorem to the case of
free $\mathbf{FI}$-algebras.

###  4.1. Making $B$ free

Here we introduce the following useful notations. Let $A$ be an
$\mathbf{FI}$-algebra. By $f\in A$ we mean that there exists $S\in\mathbf{FI}$
such that $f\in A(S)$. Similarly, by $p\in\operatorname{Spec}A$ we mean that
there exists $T\in\mathbf{FI}$ such that $p\in\operatorname{Spec}A(T)$. By
$f(p)=0$ we mean that for all $\sigma:S\rightarrow T$ injections, $(\sigma
f)(p)=0$.

######  Proposition 4.1.1.

Let $\pi:C\rightarrow B$ and $\varphi:B\rightarrow A$ be homomorphisms of
$FI$-algebras, where $\pi$ is surjective. If the image closure
$\overline{\operatorname{Im}(\pi^{*}\circ\varphi^{*})}$ of
$\pi^{*}\circ\varphi^{*}:\operatorname{Spec}A\rightarrow\operatorname{Spec}C$
is defined by finitely many elements in $C$, then the image closure
$\overline{\operatorname{Im}(\varphi^{*})}$ of
$\varphi^{*}:\operatorname{Spec}A\rightarrow\operatorname{Spec}B$ is also
defined by finitely many elements in $B$. If, moreover,
$\overline{\operatorname{Im}(\pi^{*}\circ\varphi^{*})}$ is topologically
Noetherian, then $\overline{\operatorname{Im}(\varphi^{*})}$ is also
topologically Noetherian.

###### Proof.

Suppose $f_{1},f_{2},...,f_{m}\in C$ define the image closure
$\overline{\operatorname{Im}(\pi^{*}\circ\varphi^{*})}$. We claim that their
images $\pi f_{1},\pi f_{2},...,\pi f_{m}\in B$ define the image closure
$\overline{\operatorname{Im}(\varphi^{*})}$. First note that
$\overline{\operatorname{Im}(\pi^{*}\circ\varphi^{*})}=\pi^{*}(\overline{\operatorname{Im}(\varphi^{*}))}$
as $\pi^{*}$ is a closed embedding. Let
$p\in\overline{\operatorname{Im}(\varphi^{*})}$, then $\pi
f_{i}(p)=f_{i}(\pi^{*}p)=0$. Thus for all $i=1,2,...,m$ we have that $\pi
f_{i}$ vanishes on $\overline{\operatorname{Im}(\varphi^{*})}$.

Conversely, pick $p\in\operatorname{Spec}B$ such that $p$ is in the closed
subset defined by $\pi f_{1},\pi f_{2},...,\pi f_{m}$, then $\pi^{*}p$ lies in
the variety defined by $f_{1},f_{2},...,f_{m}$, that is, by our supposition,
$\pi^{*}p\in\overline{\operatorname{Im}(\pi^{*}\circ\varphi^{*})}$. Now let
$g$ be an element of ${\rm Ker}\,(\varphi)$. By the surjectivity of $\pi$,
there exists $g^{\prime}\in C$ such that $\pi g^{\prime}=g$, which implies
that $g^{\prime}\in{\rm Ker}\,(\varphi\circ\pi)$. Hence $g^{\prime}$ vanishes
on $\pi^{*}(p)$. So $g(p)=\pi g^{\prime}(p)=g^{\prime}(\pi^{*}(p))=0$. Hence
$p\in\overline{\operatorname{Im}(\varphi^{*})}$.

The last statement is straight forward. Every descending chain of closed
subsets in $\overline{\operatorname{Im}(\varphi^{*})}$ maps under $\pi^{*}$ to
a descending chain of closed subsets in
$\overline{\operatorname{Im}(\pi^{*}\circ\varphi^{*})}$ because $\pi^{*}$ is a
closed embedding. The latter chain stabilizes and, and when it does, so does
the former chain. This completes the proof. ∎

######  Remark 4.1.2.

Let $B$ be an $\mathbf{FI}$-algebra that is finitely generated in width at
most $d$ and $\varphi:B\rightarrow A$ be a homorphism of
$\mathbf{FI}$-algebras. Then, by Lemma 2.2.13, there exists a surjective map
$\pi$ from $B[k_{0},k_{1},...,k_{d}]$ to $B$. Thus Proposition 4.1.1 implies
that it suffices to prove the main theorem for the $\mathbf{FI}$-algebra
$B[k_{0},k_{1},...,k_{d}]$ instead of $B$, i.e. without loss of generality, in
the main theorem, we can assume that $B$ is free.

###  4.2. Making $A$ free, as well

######  Proposition 4.2.1.

Let $\varphi:B\rightarrow A$, $\psi:B\rightarrow A^{\prime}$ and
$\pi:A^{\prime}\rightarrow A$ be homomorphisms of finitely generated
$\mathbf{FI}$-algebras such that $\pi\circ\psi=\varphi$. If the closure
$\overline{\operatorname{Im}(\psi^{*})}$ of the image of $\psi^{*}$ is
topologically Noetherian, then the closure
$\overline{\operatorname{Im}(\varphi^{*})}$ of the image of $\varphi^{*}$ is
also topologically Noetherian. If, moreover,
$\overline{\operatorname{Im}(\psi^{*})}$ is defined by finitely many elements
in $B$, then $\overline{\operatorname{Im}(\varphi^{*})}$ is also defined by
finitely many elements in $B$.

###### Proof.

The first statement is a straight-forward implication of the fact that a
closed subspace of a topologically Noetherian space is topologically
Noetherian. Since ${\rm Ker}\,(\psi)$ is contained in ${\rm Ker}\,(\varphi)$,
we have

$\displaystyle\overline{\operatorname{Im}(\varphi^{*})}=V_{\operatorname{Spec}B}({\rm
Ker}\,(\varphi))=V_{\operatorname{Spec}B}({\rm Ker}\,(\pi\circ\psi))$

is a closed subset of $V_{\operatorname{Spec}B}({\rm
Ker}\,(\psi))=\overline{\operatorname{Im}(\psi^{*})}$. The latter is
topologically Noetherian, hence so is the former.

For the last statement, observe that
$\overline{\operatorname{Im}(\varphi^{*})}$, being a closed subset of a
topologically Noetherian space $\overline{\operatorname{Im}(\psi^{*})}$, is
defined by finitely many elements in the coordinate ring
$K[\overline{\operatorname{Im}(\psi^{*})}]=B/I$, where
$I=I(\overline{\operatorname{Im}(\psi^{*})})$ is an ideal generated by
finitely many elements in $B$. This implies that
$\overline{\operatorname{Im}(\varphi^{*})}$ is defined by finitely many
elements in $B$. ∎

######  Remark 4.2.2.

Let $A$ be an $\mathbf{FI}$-algebra that is finitely generated in width at
most $1$ and let $\varphi:B[k_{0},k_{1},...,k_{d}]\rightarrow A$ be a
morphism. Then by Lemma 2.2.13 there is a surjective map
$\pi:B[k^{\prime}_{0},k^{\prime}_{1}]\rightarrow A$. By universality of
$B[k_{0},k_{1},...,k_{d}]$ (see Remark 2.2.12), there exists (not necessarily
unique) map $\psi:B[k_{0},k_{1},...,k_{d}]\rightarrow
B[k^{\prime}_{0},k^{\prime}_{1}]$ such that $\varphi=\pi\circ\psi$. Thus
Proposition 4.2.1 implies that it suffices to prove the main theorem for
$B[k^{\prime}_{0},k^{\prime}_{1}]$ instead of $A$ i.e. without lost of
generality, in the main theorem, we can assume that $A$ is free.

##  5\. Proof of the Main Theorem

###  5.1. Flattening

For a more detailed description of flattening see [DK14].

######  Definition 5.1.1.

Let $V=\bigotimes_{j=1}^{n}V_{j}$ be a tensor product of vector spaces $V_{j}$
over a field $L$. Then for each $i\in[n]$, there is a natural isomorphism

$\displaystyle\flat_{i}:V\rightarrow\left(\bigotimes_{j\neq
i}V_{j}\right)\otimes V_{i}.$

For a $t\in V$ the image $\flat_{i}(t)$ is a $2$-tensor called a flattening of
$t$.

A tensor has rank $1$ if it can be written as a tensor product of vectors
$v_{i}\in V_{i}$. A tensor $t$ has rank $l$ if $l$ is the minimum number of
rank 1 tensors that sum to $t$. For $2$-tensors, the tensor rank is equal to
the ordinary matrix rank.

######  Remark 5.1.2.

Flattening does not increase the rank of a tensor, i.e. $rk(\flat_{i}(t))\leq
rk(t)$.

###  5.2. Tensors

Define an $\mathbf{FI}$-algebra $C_{d}$ over a ring $K$ that sends a finite
set $S$ to the $K$-algebra,

$\displaystyle C_{d}(S)=K[y_{i_{1},i_{2},...,i_{d}}:i_{1},i_{2},...,i_{d}\in
S],$

and an injection $\sigma:S\rightarrow T$ to $C_{d}(\sigma):C_{d}(S)\rightarrow
C_{d}(T)$ maps $y_{i_{1},i_{2},...,i_{d}}$ to
$y_{\sigma(i_{1}),\sigma(i_{2}),...,\sigma(i_{d})}$.

######  Remark 5.2.1.

For a finite set $S$, $\operatorname{Spec}C_{d}(S)$ is the set of $S\times
S\times...\times S$-tensors, now including entries on the big diagonal.

There is a natural inclusion $\iota:B_{d}\rightarrow C_{d}$. Dually, we have
the projection map
$\iota^{*}:\operatorname{Spec}C_{d}\rightarrow\operatorname{Spec}B_{d}$. For a
tensor $t\in\operatorname{Spec}C_{d}(S)$ we think of the flattening
$\flat_{i}(t)$ as a matrix whose rows and columns are labeled by tuples in
$S^{[d]\setminus\\{i\\}}$ and elements in $S$ respectively.

######  Definition 5.2.2.

A tuple $(x_{i})_{i\in[d]}$ in $S^{d}$ is called a distinct value tuple if
$x_{i}\neq x_{j}$ when $i\neq j$. Denote by $DS^{d}$ the set of distinct value
tuples in $S^{d}$.

######  Definition 5.2.3.

An off-diagonal $l\times l$ sub-matrix of $\flat_{i}(t)$ is a $u_{1}\times
u_{2}$-sub-matrix where $u_{1}\subset DS^{d-1}$, $u_{2}\subset S$ such that
$u_{1}\times u_{2}\subset DS^{d}$ and $|u_{1}|=|u_{2}|=l$ . By an off-diagonal
$l\times l$-sub-determinant of $\flat_{i}(t)$, we mean the determinant of an
off-diagonal $l\times l$-sub-matrix of $\flat_{i}(t)$ .

Fix non-negative integers $l$ and $d$. Let $Z_{d,l}$ be the subset of
$\operatorname{Spec}B_{d}$ defined as follows: for all $S\in\mathbf{FI}$,
$Z_{d,l}(S)$ is the variety defined by all off-diagonal
$(l+1)\times(l+1)$-sub-determinants of $\flat_{i}(y),$ for all $i\in[d]$ and
$y\in\operatorname{Spec}B_{d}(S)$. The following lemma shows that $Z_{d,l}$ is
defined by finitely many equations in $B_{d}$.

######  Lemma 5.2.4.

The subset $Z_{d,l}$ of $\operatorname{Spec}B_{d}$ is defined by finitely many
equations in $B_{d}$.

###### Proof.

Let $S$ be a finite set, let $y\in\operatorname{Spec}B_{d}\left(S\right)$ and
$i\in\left[d\right]$ be arbitrary. Let $h$ be an arbitrary off-diagonal
$\left(l+1\right)\times\left(l+1\right)$-subdeterminant of the flattening
$\flat_{i}\left(y\right)$. The subdeterminant $h$ is given by indices
$i_{1},\dots,i_{l+1}\in S$ and distinct value tuples
$\alpha_{1},\dots,\alpha_{l+1}\in DS^{d-1}$ such that none of the indices
$i_{j}$ occur in any of the $\alpha_{k}$ and such that all the $\alpha_{k}$
are distinct.
Let $S^{\prime}$ be the subset of $S$ consisting of all the entries of the
$i_{j}$ and $\alpha_{k}$. Then
$|S^{\prime}|\leq\left(d-1\right)\cdot\left(l+1\right)+l+1=d\cdot\left(l+1\right)$.
Set $n=|S^{\prime}|$ and choose a bijection
$\rho\colon\left[n\right]\rightarrow S^{\prime}$. Define
$\alpha^{\prime}_{j}=\rho^{-1}\circ\alpha_{j}$ and
$i^{\prime}_{j}=\rho^{-1}(i_{j})$ for all $j\in\left[l+1\right]$, where we
consider the $\alpha_{j}$ as maps from $\left[d-1\right]$ to $S^{\prime}$.
Then $h=B_{d}\left(\rho\right)h^{\prime}$, where $h^{\prime}$ is the off-
diagonal subdeterminant of the flattening
$\flat_{i}\left(\left(y_{\beta}\right)_{\beta\in
D\left[n\right]^{d-1}}\right)$ given by columns
$i^{\prime}_{1},\dots,i^{\prime}_{l+1}$ and rows
$\alpha^{\prime}_{1},\dots,\alpha^{\prime}_{l+1}$. Since $n$ can take on at
most $d\cdot\left(l+1\right)$ values, this construction yields finitely many
polynomials $h^{\prime}$. These polynomials define $Z_{d,l}$. ∎

######  Lemma 5.2.5.

Let $\varphi:B_{d}\rightarrow B_{1}^{\otimes k}$ be an $\mathbf{FI}$-algebra
homomorphism. Then $\overline{\operatorname{Im}(\varphi^{*})}\subset Z_{d,l}$
for some $l$.

###### Proof.

By Lemma 2.2.11, the map $\varphi$ is determined by the image of
$y_{1,2,...,d}\in B_{d}([d])$. First we suppose that $y_{1,2,...,d}\in
B_{d}([d])$ is mapped under $\varphi$ to a monomial
$M=\prod_{i\in[k],j\in[d]}x_{i,j}^{\alpha_{i,j}}\in B_{1}^{\otimes k}([d])$.
Dually, $a=(a_{i,j})_{i\in[k],j\in S}\in\operatorname{Spec}B_{1}(S)^{\otimes
k}$ is mapped to the projection (via $\iota^{*}$) of the following tensor:

$\displaystyle(a_{j_{1},j_{2},...,j_{d}}=\prod_{i=1}^{k}a_{i,j_{1}}^{\alpha_{i,1}}\cdot\prod_{i=1}^{k}a_{i,j_{2}}^{\alpha_{i,2}}\cdots\prod_{i=1}^{k}a_{i,j_{d}}^{\alpha_{i,d}})_{j_{1},j_{2},...,j_{d}\in
S}$
$\displaystyle=\bigotimes_{j=1}^{d}(\prod_{i=1}^{k}a_{i,s}^{\alpha_{i,j}})_{s\in
S}\in\operatorname{Spec}B_{d}(S),$

that is, $\varphi^{*}(a)$ is the projection of a rank $\leq 1$ tensor. Thus
$\operatorname{Im}(\varphi^{*})$ is contained in the projection of rank $\leq
1$ tensors.

Now, if $y_{1,2,...d}\in B_{d}([d])$ is mapped under $\varphi$ to
$f=\sum_{c=1}^{l}M_{c}$ which is a sum of, say $l$, monomials in the variables
$x_{i,j}$ where $1\leq i\leq k$ and $1\leq j\leq d$, then the subadditivity of
tensor rank implies that $\operatorname{Im}(\varphi^{*})$ lies in the
projection $i^{*}$ of tensors having rank at most $l$. Since flattening does
not increase rank, this implies $\operatorname{Im}(\varphi^{*})\subset
Z_{d,l}$. Hence $\overline{\operatorname{Im}(\varphi^{*})}\subset Z_{d,l}$. ∎

######  Remark 5.2.6.

Let $\varphi:B[k_{0},k_{1},...,k_{d}]\rightarrow B_{1}^{\otimes k}$ be an
$\mathbf{FI}$-algebra homomorphism. By universality of
$B[k_{0},k_{1},...,k_{d}]$,
$\varphi=\bigotimes_{e=0}^{d}(\bigotimes_{i=1}^{k_{e}}\varphi_{e,i})$ where,
$\varphi_{e,i}:B_{e}\rightarrow B_{1}^{\otimes k}$ for all $e$ and for all
$i$, and $\operatorname{Im}(\varphi_{e,i}^{*})\subset Z_{e,l_{e,i}}$ for some
$l_{e,i}$. Let $l$ be the maximum of the set $\\{l_{e,i}:0\leq e\leq
d\,\,\text{and}\,\,0\leq i\leq k_{e}\\}$. Then
$\operatorname{Im}(\varphi^{*})\subset\prod_{e=0}^{d}Z_{e,l}^{k_{e}}$.

For a commutative ring $R$ with $1$, and a prime ideal
$p\in\operatorname{Spec}R$, $\kappa(p)$ denotes the fraction field of the
integral domain $R/p$.

######  Lemma 5.2.7.

Let $Y$ be a subset of $\operatorname{Spec}C_{d}$. Suppose that there exists
$N\in{\mathbb{Z}}_{\geq 0}$ such that for all $S$, for all $p\in Y(S)$, the
tensor rank of $p$ over the field $\kappa(p)$ is at most $N$. Then there exist
an $\mathbf{FI}$-algebra $A$ that is finitely generated in width at most $1$
and a map
$\varphi_{N}^{*}:\operatorname{Spec}A\rightarrow\operatorname{Spec}C_{d}$ such
that $Y\subset\operatorname{Im}(\varphi_{N}^{*})$.

In this lemma, $Y(S)$ is an arbitrary subset of $\operatorname{Spec}(C(S))$,
in such a manner that for any
$\pi\in\operatorname{Hom}\nolimits_{\mathbf{FI}}(S,T)$, the map $C(\pi)^{*}$
maps $Y(T)$ into $Y(S)$.

###### Proof.

Define a homomorphism of $\mathbf{FI}$-algebras $\varphi_{N}:C_{d}\rightarrow
A=C_{1}^{\otimes[N]\times[d]}$ by sending $y_{i_{1},i_{2},...,i_{d}}$ to
$\sum_{j=1}^{N}x_{j,1,i_{1}}x_{j,2,i_{2}}\cdots x_{j,d,i_{d}}$. By assumption,
for each $S$ and for every
$p=(p_{i_{1},i_{2},...,i_{d}})_{i_{1},i_{2},...,i_{d}\in S}\in Y(S)$, there
exists $(q_{j,l,i_{l}})_{(j,l,i_{l})\in[N]\times[d]\times
S}\in\operatorname{Spec}C_{1}^{\otimes[N]\times[d]}(S)(\kappa(p))$ such that
$p_{i_{1},i_{2},...,i_{d}}=\sum_{j=1}^{N}q_{j,1,i_{1}}q_{j,2,i_{2}}\cdots
q_{j,d,i_{d}}$. Hence $Y\subset\operatorname{Im}(\varphi_{N}^{*})$. ∎

######  Lemma 5.2.8.

Let $Z$ be a subset of $\operatorname{Spec}B_{d}$. Suppose that there exists
$N\in{\mathbb{Z}}_{\geq 0}$ such that for all $S\in\mathbf{FI}$ and for all
$p\in Z(S)$ there exists $\tilde{p}\in\operatorname{Spec}C_{d}(S)$ such that
the tensor rank of $\tilde{p}$ over the field $\kappa(\tilde{p})$ is at most
$N$ and $\iota^{*}(\tilde{p})=p$ where $\iota:B_{d}\rightarrow C_{d}$ is the
inclusion map. Then there exists a map $\psi:B_{d}\rightarrow A$ such that
$Z\subset\operatorname{Im}(\psi^{*})$, where $A$ is an $\mathbf{FI}$-algebra
that is finitely generated in width at most 1.

######  Remark 5.2.9.

The condition on the off-diagonal tensor $p$ is that it can be completed to a
(full) tensor $\tilde{p}$ of rank $\leq N$, where $N$ does not depend on $p$
or $S$.

###### Proof.

Define $Y:=\\{\tilde{p}\in(i^{*})^{-1}(Z):\,\,\text{tensor rank
of}\,\,\tilde{p}\,\,\text{over}\,\,\kappa(\tilde{p})\leq N\\}$. By Lemma
5.2.7, $Y\subset\operatorname{Im}(\varphi_{N}^{*})$ and by construction,
$Z=i^{*}(Y)$. Then $\psi=\varphi_{N}\circ i$ is the required map such that
$Z\subset\operatorname{Im}(\psi^{*})$. ∎

######  Proposition 5.2.10.

Let $Z_{d,l}$ be the subset of $\operatorname{Spec}B_{d}$ defined above, by
the vanishing of off-diagonal $(l+1)\times(l+1)$-subdeterminants of
flattenings. Then there exists $N\in{\mathbb{Z}}_{\geq 0}$ such that for all
$S\in\mathbf{FI}$ and for all $p\in Z_{d,l}(S)$ there exists
$\tilde{p}\in\operatorname{Spec}C_{d}(S)$ such that the tensor rank of
$\tilde{p}$ over the field $\kappa(\tilde{p})$ is at most $N$ and
$\iota^{*}(\tilde{p})=p$ where $\iota:B_{d}\rightarrow C_{d}$ is the inclusion
map.

###### Proof.

We will prove this by a double induction: an outer induction on $d$ and an
inner induction on $l$. For $d=0$ and $d=1$, we have $B_{d}=C_{d}$ and every
element of $\operatorname{Spec}C_{d}(S)$ has tensor rank at most 1, regardless
of $l$. Assume the proposition is true for $\leq d-1$. When $l=0$ note that
$Z_{d,0}$ contains only a zero tensor. Take $N=0$ and we are done. Fix $l>0$
and assume the proposition is true for all smaller values. Write
$Z_{d,l}(S)=Z_{d,l-1}(S)\cup(Z_{d,l}(S)\setminus Z_{d,l-1}(S))$. By the inner
induction hypothesis, there exists $N_{0}$ such that for every $p\in
Z_{d,l-1}(S)$ there exists $\tilde{p}\in\operatorname{Spec}C_{d}(S)$ such that
the tensor rank of $\tilde{p}$ over the field $\kappa(\tilde{p})$ is at most
$N_{0}$ and $i^{*}(\tilde{p})=p$.

Now take $p\in Z_{d,l}([n])\setminus Z_{d,l-1}([n])$. This implies that there
exist $i_{0}\in[d]$ such that there is an $l\times l$-sub-determinant $h$ of
$\flat_{i_{0}}(p)$ which is non-zero. The sub-determinant $h$ involves at most
$\leq l(d-1)+l=l\cdot d$ indices. Split $[n]$ into $S\sqcup T$ such that $S$
consists of indices that appear in $h$ and $T=[n]\setminus S$; i.e., T is the
set of indices that do not appear in $h$. For each fixed subset $I\subset[d]$
and fixed distinct value tuple $\alpha\in DS^{[d]\setminus I}$, consider the
off-diagonal tensor $p_{\alpha}=(p_{\alpha,\beta})_{\beta\in DT^{I}}$. We
regard $p_{\alpha}$ as an element of $\operatorname{Spec}B_{|I|}(T)$.

Case 1: If $I\neq[d]$, then the outer induction hypothesis applies to
$p_{\alpha}$. Indeed, flattening $\flat_{i}(p_{\alpha})$ for $i\in I$ yields a
sub-matrix of $\flat_{i}(p)$ and by the induction hypothesis,
$p_{\alpha}=i^{*}(q_{\alpha})$, where
$q_{\alpha}\in\operatorname{Spec}C_{|I|}(T)$ has rank $\leq N_{\alpha}$.

Case 2: If $I=[d]$, then we want to find
$q_{\emptyset}\in\operatorname{Spec}C_{d}(T)$ such that
$p_{\emptyset}=i^{*}(q_{\emptyset})$ and the tensor rank of $q_{\emptyset}$
over the field $\kappa(p)$ is at most some $N_{\emptyset}$. Then we will have
$p=i^{*}(\sum_{I,\alpha}(q_{\alpha}\,\,\text{padded with zeros}))$ such that
the tensor rank of $p$ over the field $\kappa(p)$ is at most
$N_{1}=\sum_{\alpha}N_{\alpha}$. Without loss of generality, assume that
$i_{0}=d$. We have an off-diagonal $l\times l$-sub-matrix $M$ of the matrix
$\flat_{d}(p)$ such that $\operatorname{det}(M)=h\neq 0$. Define
$q_{\emptyset}$ as follows:

$\displaystyle q_{\emptyset}=\sum_{j\in u_{2}\,\,\text{and}\,\,\alpha\in
u_{1}}(M^{-1})_{j,\alpha}q_{\\{j\\}}\otimes q_{\alpha}=\sum_{j\in
u_{2}}q_{\\{j\\}}\otimes(\sum_{\alpha\in u_{1}}(M^{-1})_{j,\alpha}\cdot
q_{\alpha}).$

where $rk(q_{\\{j\\}})\leq N_{\\{j\\}}$ and $rk(\sum_{\alpha\in
u_{1}}(M^{-1})_{j,\alpha}\cdot q_{\alpha})\leq 1$. Hence
$rk(q_{\emptyset})\leq N_{\emptyset}:=\sum_{j\in u_{2}}N_{\\{j\\}}$.

Notations used in Figure 1: Rows and columns of the matrix are labeled by
tuples in $(S\sqcup T)^{d-1}$ and elements in $S\sqcup T$ respectively. $M$ is
a $u_{1}\times u_{2}$-submatrix where $u_{1}\subset DS^{d-1}$, $u_{2}\subset
S$ such that $u_{1}\times u_{2}\subset DS^{d}$ and $|u_{1}|=|u_{2}|=l$.

We want to show that $i^{*}(q_{\emptyset})=p_{\emptyset}$. Straightforward
computations (from linear algebra) show that the matrix in the Figure 1 has
rank $=l$. In particular, all off diagonal $(l+1)\times(l+1)$-sub-determinants
in positions $(u_{1}\cup\\{\alpha\\})\times(u_{2}\cup\\{i\\})$ are zero where
$\alpha\in DT^{d-1}$ and $i\in T$. The same holds, by assumption for $p$.
Hence, since $M$ is invertible and for all $j\in u_{2}$,
$i^{*}(q_{\\{j\\}})=p_{\\{j\\}}$ and for all $\alpha\in u_{1}$,
$i^{*}(q_{\alpha})=p_{\alpha}$, we find that
$(p_{\emptyset})_{\alpha,i}=(q_{\emptyset})_{\alpha,i}$, for all $\alpha\in
DT^{d-1}$ and for all $i\in T$ such that $(\alpha,i)\in DT^{d}$. Hence
$i^{*}(q_{\emptyset})=p_{\emptyset}$. $N=max\\{N_{0},N_{1}\\}$ is the required
$N$. This completes the proof.

Figure 1. Flattening

∎

Recall from Remark 2.2.7 that for any nonnegative integers
$e,k_{0},k_{1},...,k_{e}$,
$B[k_{0},k_{1},...,k_{e}]$ denotes the following $\mathbf{FI}$-algebra
$\bigotimes_{i=0}^{e}B_{i}^{\otimes k_{i}}$.

######  Lemma 5.2.11.

For any morphism $\varphi:B=B[k_{0},k_{1},...,k_{e}]\to A=B_{1}^{\otimes k}$
there exist a closed subset $Z\subset\operatorname{Spec}B$ defined by finitely
many equations in $B$, an $\mathbf{FI}$-algebra $A^{\prime}$ that is finitely
generated in width at most $1$, and a morphism $\psi:B\to A^{\prime}$ such
that $\overline{\operatorname{Im}(\varphi^{*})}\subset
Z\subset\operatorname{Im}(\psi^{*})$.

###### Proof.

We will prove this by an induction on the number of $\mathbf{FI}$-algebras
appearing in the tensor product $B=B[k_{0},k_{1},...,k_{e}]$.

For the base case, suppose that $B=B_{d}$ for some nonnegative integer $d$.
Then by Lemma 5.2.5, there exists a positive integer $l$ such that
$\overline{\operatorname{Im}(\varphi^{*})}$ is a closed subset of $Z_{d,l}$.
By Lemma 5.2.4, $Z_{d,l}$ is defined by finitely many equations in $B_{d}$. We
take $Z=Z_{d,l}$. By Proposition 5.2.10 and Lemma 5.2.8, there exists a
homomorphism $\psi:B_{d}\rightarrow A^{\prime}$ of $\mathbf{FI}$-algebras such
that $Z=Z_{d,l}$ is contained in the image
$\psi^{*}(\operatorname{Spec}A^{\prime})$, where $A^{\prime}$ is an
$\mathbf{FI}$-algebra that is finitely generated in width at most 1.

Now suppose that $B=B_{d_{1}}\otimes B_{d_{2}}\otimes\cdots\otimes B_{d_{n}}$.
Here $d_{i}$’s are not necessarily distinct. We write $B=C\otimes B_{d_{n}}$
where $C=B_{d_{1}}\otimes B_{d_{2}}\otimes\cdots\otimes B_{d_{n-1}}$. We think
of $C$ and $B_{d_{n}}$ as subalgebras of $B$ via the natural inclusions.
Denote by $\varphi_{1}$ and $\varphi_{2}$ the restrictions of the map
$\varphi:B\to A$ to $C$ and $B_{d_{n}}$ respectively. Then by the induction
hypothesis, there exist closed subsets $Z_{1}\subset\operatorname{spec}C$ and
$Z_{2}\subset\operatorname{Spec}B_{d_{n}}$ defined by finitely many equations
in $C$ and in $B_{d_{n}}$ respectively, $\mathbf{FI}$-algebras $A_{1}$ and
$A_{2}$ both are finitely generated in width at most $1$, and homomorphisms
$\psi_{1}:C\to A_{1}$, $\psi_{2}:B_{d_{n}}\to A_{2}$ such that

$\overline{\operatorname{Im}(\varphi_{1}^{*})}\subset
Z_{1}\subset\operatorname{Im}(\psi_{1}^{*})$ and
$\overline{\operatorname{Im}(\varphi_{2}^{*})}\subset
Z_{2}\subset\operatorname{Im}(\psi_{2}^{*})$.

We now have

$\overline{\operatorname{Im}(\varphi^{*})}\subseteq\overline{\operatorname{Im}(\varphi_{1}^{*})}\times\overline{\operatorname{Im}(\varphi_{2}^{*})}\text{
and
}\operatorname{Im}(\psi_{1}^{*})\times\operatorname{Im}(\psi_{2}^{*})=\operatorname{Im}((\psi_{1}\otimes\psi_{2})^{*}),$

where $\psi_{1}\otimes\psi_{2}$ is the $\mathbf{FI}$-algebra homomorphism
$C\otimes B_{d_{n}}\to A_{1}\otimes A_{2}$ obtained as the tensor product of
$\psi_{1}$ and $\psi_{2}$.

Note that the $\mathbf{FI}$-algebra $A_{1}\otimes A_{2}$, being the tensor
product of $\mathbf{FI}$-algebras that are finitely generated in width at most
$1$, is itself also finitely generated in width at most $1$. Further, the
product $Z:=Z_{1}\times Z_{2}$ is defined by union of the finite sets of
equations defining $Z_{1}$ and $Z_{2}$. Thus this $Z$, and
$A^{\prime}:=A_{1}\otimes A_{2}$, and $\psi:=\psi_{1}\otimes\psi_{2}$ have the
required property $\overline{\operatorname{Im}(\varphi^{*})}\subset
Z\subset\operatorname{Im}(\psi^{*})$. ∎

###### Proof of the Main Theorem.

Recall from Section 4 that without loss of generality we can assume that both
$\mathbf{FI}$-algebras $B$ and $A$ are free, that is,
$B=B[k_{0},k_{1},...,k_{e}]$ and $A=B_{1}^{\otimes k}$ for some nonnegative
integers $k,k_{0},k_{1},...,k_{e}$.

From Lemma 5.2.11, $\overline{\operatorname{Im}(\varphi^{*})}$ is contained in
a closed subset $Z\subset\operatorname{Spec}B$ which is defined by finitely
many equations in $B$, moreover, $Z$ is contained in the image
$\operatorname{Im}(\psi^{*})$ of a width-one $\mathbf{FI^{op}}$-scheme of
finite type. Recall from Remark 3.1.4 that width-one
$\mathbf{FI^{op}}$-schemes of finite type are topologically Noetherian and
from Lemma 3.1.8 that the image of a topologically Noetherian space is
topologically Noetherian. By Lemma 3.1.6, the subset $Z$, being a subset of
the topologically Noetherian space $\operatorname{Im}(\psi^{*})$, is
topologically Noetherian. Thus $\overline{\operatorname{Im}(\varphi^{*})}$ is
topologically Noetherian being a closed subset of $Z$ and defined by finitely
many equations in the coordinate ring of $Z$. Since $Z$ is defined by finitely
many equations in $B$, this implies that
$\overline{\operatorname{Im}(\varphi^{*})}$ is defined by finitely many
equation in $B$. This completes the proof. ∎

## References

  * [AH07] Matthias Aschenbrenner and Christopher J. Hillar  “Finite generation of symmetric ideals”  In _Trans. Amer. Math. Soc._ 359.11, 2007, pp. 5171–5192  DOI: 10.1090/S0002-9947-07-04116-5
  * [BD11] Andries E. Brouwer and Jan Draisma  “Equivariant Gröbner bases and the Gaussian two-factor model”  In _Math. Comput._ , 2011, pp. 1123–1133  DOI: 10.1090/S0025-5718-2010-02415-9
  * [Bie+20] Jennifer Biermann et al.  “Betti numbers of symmetric shifted ideals”  In _Journal of Algebra_ 560 Elsevier BV, 2020, pp. 312–342  DOI: 10.1016/j.jalgebra.2020.04.037
  * [CEF15] Thomas Church, Jordan S. Ellenberg and Benson Farb  “FI-modules and stability for representations of symmetric groups”  In _Duke Mathematical Journal_ 164.9 Duke University Press, 2015  DOI: 10.1215/00127094-3120274
  * [Coh67] D.. Cohen  “On the laws of a metabelian variety”  In _J. Algebra_ 5, 1967, pp. 267–273  DOI: 10.1016/0021-8693(67)90039-7
  * [Coh87] Daniel E. Cohen  “Closure relations. Buchberger’s algorithm, and polynomials in infinitely many variables”  In _Computation theory and logic_ 270, Lecture Notes in Comput. Sci.  Springer, Berlin, 1987, pp. 78–87  DOI: 10.1007/3-540-18170-9“˙156
  * [DEF22] Jan Draisma, Rob Eggermont and Azhar Farooq  “Components of symmetric wide-matrix varieties”  In _J. Reine Angew. Math._ 793, 2022, pp. 143–184  DOI: 10.1515/crelle-2022-0064
  * [DK14] Jan Draisma and Jochen Kuttler  “Bounded-rank tensors are defined in bounded degree”  In _Duke Mathematical Journal_ 163.1 Duke University Press, 2014  DOI: 10.1215/00127094-2405170
  * [DKK] Jan Draisma, Alexei Krasilnikov and Robert Krone  “$\mathbf{FI}$-Algebras, $\mathbf{OI}$-Algebras, $S_{\infty}$-ALGEBRAS: examples and counterexamples” Manuscript in preparation
  * [Dra+13] Jan Draisma, Rob H. Eggermont, Robert Krone and Anton Leykin  “Noetherianity for infinite-dimensional toric varieties”  arXiv, 2013  URL: https://arxiv.org/abs/1306.0828
  * [Dra10] Jan Draisma  “Finiteness for the $k$-factor model and chirality varieties”  In _Adv. Math._ 223.1, 2010, pp. 243–256  DOI: 10.1016/j.aim.2009.08.008
  * [DSS06] Mathias Drton, Bernd Sturmfels and Seth Sullivant  “Algebraic factor analysis: tetrads, pentads and beyond”  In _Probability Theory and Related Fields_ 138.3-4 Springer ScienceBusiness Media LLC, 2006, pp. 463–493  DOI: 10.1007/s00440-006-0033-2
  * [HS12] Christopher J. Hillar and Seth Sullivant  “Finite Gröbner bases in infinite dimensional polynomial rings and applications”  In _Adv. Math._ 229.1, 2012, pp. 1–25  DOI: 10.1016/j.aim.2011.08.009
  * [KLS17] Robert Krone, Anton Leykin and Andrew Snowden  “Hilbert series of symmetric ideals in infinite polynomial rings via formal languages”  In _J. Algebra_ 485, 2017, pp. 353–362  DOI: 10.1016/j.jalgebra.2017.05.014
  * [KR22] Mario Kummer and Cordian Riener  “Equivariant algebraic and semi-algebraic geometry of infinite affine space”  arXiv, 2022  DOI: 10.48550/ARXIV.2203.11921
  * [KVR22] Thomas Kahle, Dinh Van Le and Tim Römer  “Invariant chains in algebra and discrete geometry”  In _SIAM J. Discrete Math._ 36.2, 2022, pp. 975–999  DOI: 10.1137/20M1385652
  * [Le+20] Dinh Le, Uwe Nagel, Hop D. Nguyen and Tim Römer  “Codimension and projective dimension up to symmetry”  In _Math. Nachr._ 293.2, 2020, pp. 346–362  DOI: 10.1002/mana.201800413
  * [Le+21] Dinh Van Le, Uwe Nagel, Hop D. Nguyen and Tim Römer  “Castelnuovo-Mumford regularity up to symmetry”  In _Int. Math. Res. Not._ 2021.14, 2021, pp. 11010–11049  DOI: 10.1093/imrn/rnz382
  * [LN22] Dinh Van Le and Hop D. Nguyen  “On regularity and projective dimension up to symmetry”, 2022  arXiv:2206.15141 [math.AC]
  * [NR17] Uwe Nagel and Tim Römer  “Equivariant Hilbert series in non-noetherian polynomial rings”  In _Journal of Algebra_ 486, 2017, pp. 204–245  DOI: https://doi.org/10.1016/j.jalgebra.2017.05.011
  * [NR19] Uwe Nagel and Tim Römer  “FI- and OI-modules with varying coefficients”  In _Journal of Algebra_ 535 Elsevier BV, 2019, pp. 286–322
  * [NS] Rohit Nagpal and Andrew Snowden  “Symmetric subvarieties of infinite affine space” Preprint, arXiv:2011.09009
  * [NS22] Rohit Nagpal and Andrew Snowden  “Symmetric ideals of the infinite polynomial ring” Preprint, arXiv:2107.13027, 2022


# Recurrent machines for likelihood-free inference

Arthur Pesah
KTH Royal Institute of Technology
Stockholm, Sweden
&Antoine Wehenkel11footnotemark: 1
University of Liège
Liège, Belgium
&Gilles Louppe
University of Liège
Liège, Belgium
Both authors contributed equally to this work.

###### Abstract

Likelihood-free inference is concerned with the estimation of the parameters
of a non-differentiable stochastic simulator that best reproduce real
observations. In the absence of a likelihood function, most of the existing
inference methods optimize the simulator parameters through a handcrafted
iterative procedure that tries to make the simulated data more similar to the
observations. In this work, we explore whether meta-learning can be used in
the likelihood-free context, for learning automatically from data an iterative
optimization procedure that would solve likelihood-free inference problems. We
design a recurrent inference machine that learns a sequence of parameter
updates leading to good parameter estimates, without ever specifying some
explicit notion of divergence between the simulated data and the real data
distributions. We demonstrate our approach on toy simulators, showing
promising results both in terms of performance and robustness.

##  1 Introduction

Modern science often relies on the modeling of complex data generation process
by means of computer simulators. While the forward generation of observables
is often straightforward and well-motivated, inverting generation processes is
usually very difficult. In particular, scientific simulators are often
stochastic and give rise to intractable likelihood functions that prevent the
use of classical inference algorithms. The importance and prevalence of this
problem has recently motivated the development of so-called likelihood-free
inference methods (LFI) which do not make use of the likelihood function for
estimating model parameters. LFI methods (e.g., Louppe and Cranmer,, 2017;
Beaumont et al.,, 2002; Gutmann and Corander,, 2016) are often based on
handcrafted iterative optimization procedures, where a sequence of updates are
performed to make the simulated data more similar to the observations.

Driven by the promises of learning to learn, meta-learning has shown that
automatically learning neural optimizers from data is possible, achieving
results close to the state-of-the-art for the task of training neural networks
(Andrychowicz et al.,, 2016) or solving inverse problems (Putzky and Welling,,
2017) when the gradient of the objective function is available. Meanwhile,
(Chen et al.,, 2016) have shown that meta-learning is also capable of learning
neural optimizers that rely at each step on the value of the objective
function only, without requiring access to its gradient.

In this work, we push the limits of the meta-learning framework further by
showing that it can be used even when no explicit objective value is available
at each step. More specifically, we focus on likelihood-free inference
problems and build a recurrent inference machine that learns an iterative
procedure for updating simulator parameters such that they converge (in
distance) towards nominal parameter values known at training. In particular,
the inference machine is never given access to an explicit objective function
that would estimate some divergence between the synthetic distribution and the
real data distribution. Rather, both the optimization procedure and the
implicit objective to minimize are learned end-to-end from artificial
problems.

##  2 Problem statement

The goal of likelihood-free inference is the estimation of the parameters of a
stochastic generative process with an unknown or intractable likelihood
function. Formally, given a set of observations
$X^{r}=\\{\bm{x}^{r}_{1},...,\bm{x}^{r}_{M^{r}}\\}$ drawn i.i.d. from the real
data distribution $p_{r}(\bm{x})$, we are interested in finding the model
parameters

$\bm{\theta}^{*}=\operatorname*{arg\,min}_{\theta}\rho(p_{r}(\bm{x}),p(\bm{x}|\bm{\theta}))$

that minimize some discrepancy $\rho$ between the real data distribution
$p_{r}(\bm{x})$ and the implicit distribution $p(\bm{x}|\bm{\theta})$ of the
simulated data.

In this work, instead of defining one objective point $\bm{\theta}^{*}$, we
target a probability distribution over the $\bm{\theta}$ space. Formally, our
goal is to find the optimal parameter $\bm{\psi}^{*}$ of a parametric proposal
distribution $q(\bm{\theta}|\bm{\psi})$ on $\bm{\theta}$, leading to the
following optimization problem

$\bm{\psi}^{*}=\operatorname*{arg\,min}_{\bm{\psi}}\rho(p_{r}(\bm{x}),p(\bm{x}|\bm{\psi}))\quad\text{where}\quad
p(\bm{x}|\bm{\psi})=\int
q(\bm{\theta}|\bm{\psi})p(\bm{x}|\bm{\theta})\bm{d\theta}.$

The proposal distribution provides two advantages: i) it leads to a
variational formulation of the optimization problem that does not rely on the
usage of the gradient of the function to be optimized (Staines and Barber,,
2012), ii) by sampling $B$ points from this distribution,
$\bm{\theta}_{1},...,\bm{\theta}_{B}\sim q(\bm{\theta}|\bm{\psi})$, we get
distinct parameters that we can give to the simulator. Then, by comparing the
generated observations $X_{i}=(\bm{x_{i,1}},...,\bm{x_{i,M}})$ to the real
ones $X^{r}$ for each $\bm{\theta}_{i}$, it is possible to figure out what the
optimal update of $\bm{\psi}$ is.

Because the likelihood function $p(\bm{x}|\bm{\theta})$ cannot be evaluated,
strategies must be found to use only simulated data in order to estimate
$\bm{\psi}^{*}$. Current methods for likelihood-free inference typically rely
on a handcrafted iterative update procedure where at each time step
$t\in[1,T]$ the next estimate $\bm{\psi}_{t+1}$ is determined by comparing the
simulated data produced from $p(\bm{x}|\bm{\psi})$ at the current parameter
estimate $\bm{\psi}_{t}$ with the real observations $X^{r}$. In this work, our
goal is to investigate whether meta-learning can be used for learning a
parametrized update function $f_{\bm{\phi}}$ such that

$\bm{\bm{\psi}}_{t+1}=\bm{\psi}_{t}+f_{\bm{\phi}}((\bm{\psi}_{1},\ldots,\bm{\psi}_{t}),X^{r}),\quad\text{with}\quad\bm{\psi}_{t}\to\bm{\psi}^{*}\quad\text{as}\quad
t\to\infty.$

##  3 Recurrent machines for likelihood-free inference

Figure 1: Recurrent machine for likelihood-free inference. All three encoders
are fully-connected (fc) neural networks. The RNN is a GRU (Cho et al.,, 2014)
with fully-connected pre-processing and post-processing layers.

In this work, we define $f_{\bm{\phi}}$ as a recurrent neural network (RNN)
whose architecture is given in Figure 1. At each time step $t$, the RNN takes
as input the current proposal parameters $\bm{\psi}_{t}$, a memory state
$s_{t}$, some information about the real observations and those generated with
$\bm{\psi}_{t}$, and produces as output the parameter update
$\Delta_{\bm{\psi}_{t+1}}$ and $s_{t+1}$. Observations $(x_{j})_{j\leq M}$ are
ingested through data encoder architectured as a feedforward neural network
that takes as input each $x_{j}$ independently, transforms each of them into a
$d$-dimensional vector, and aggregates them through an averaging of those
vectors over $j$. It should therefore be able to compute any moment (and more
general feature averages) of the distribution. If the moments are learned,
they can be used to infer the parameters of the distribution by the method of
matching moments, whose principle is to check compatibility between the
generated data and the observed data by looking at these moments (Ravuri et
al.,, 2018). This also means that moments can capture the relevant information
of a set of samples about a parameter of interest.

In our architecture, we use three encoders. The first one is for the real
observations $(\bm{x}^{r}_{j})_{j\leq M^{r}}$. The second one is for the
generated observations at time $t$. We consider a sampling of $B$ parameters
$(\bm{\theta}^{(t)}_{i})_{i\leq B}$, and for each $\bm{\theta}^{(t)}_{i}$, the
corresponding observations $(\bm{x}_{i,j}^{(t)})_{j\leq M}$. These two
encoders share their weights, because the way true and generated data are
summarized should be the same in order to be able to compare them. The last
encoder takes the results of the first two as well as the log-likelihood value
$\nabla_{\psi}\log q(\bm{\theta}^{(t)}_{i}|\bm{\psi}_{t})$, as motivated by
Wierstra et al., (2014) and which represents the direction to follow to move
the proposal distributions toward $\bm{\theta}^{(t)}_{i}$.

The loss used at training should encourage the network to generate updates
$\Delta_{\bm{\psi}_{t}}$ of the proposal which yield to a final proposal
$q(\bm{\theta}|\bm{\psi}_{T}$) that is close to a delta-function at
$\bm{\theta}^{*}$. The total loss of the RNN is expressed in a way similar to
(Andrychowicz et al.,, 2016), i.e. as a weighted sum of a local loss evaluated
for each $\bm{\psi}_{t}$,

$\mathscr{L}(\bm{\psi}_{T},\bm{\theta}^{*})=\sum_{t=1}^{T}w_{t}\ell(\bm{\psi}_{t},\bm{\theta}^{*}),$

where $\ell$ is a loss comparing the proposal parameters $\bm{\psi}_{t}$ with
the real parameter $\bm{\theta}^{*}$, $w_{t}$ is a weight given to the loss at
time $t$ (for instance $w_{t}=1$ for all $t$, or $w_{t}=\mathds{1}_{t=T})$.
The choice of the weighting and the loss functions are discussed in the
experiments section.

We call the architecture ALFI (Automatic Likelihood-Free Inference).

##  4 Experiments

To illustrate our method and compare it with a simple baseline, we performed
experiments on three toy simulators, whose likelihood is known and
consequently for which the maximum likelihood estimator (MLE) can be computed.
The results for the simplest simulator is shown below and results for the two
other toy problems are provided in Appendix C. We also tested our architecture
on a simulator from particle physics, whose exact likelihood function is
intractable. For this last experiment we assess the model performance by
comparing the data generated at the end of the iterative process with the real
observations. The full description of each simulator is given in Appendix B.

###  4.1 Illustrative example

As an illustrative example, we implemented a simulator that generates samples
from a Poisson distribution $\mathscr{P}(\lambda=e^{\theta})$. The goal is to
estimate the parameter $\theta$ corresponding to real samples of this
distribution.

#### Results

The box plot of Figure 2 compares the performance of our model with the MLE.
For our model (ALFI), the root mean-squared error (RMSE) is computed between
the mean of the final proposal parametrized by $\psi_{T}$ and the true value
of the parameters: $\textrm{RMSE}=||\theta^{*}-\mathbb{E}_{\theta\sim
q(\theta|\psi_{T})}[\theta]||_{2}$. We observe that our model achieves similar
performance as the MLE whereas it is not given any explicit function to
minimize during testing.

The left part of Figure 2 shows the evolution of the average and the standard
deviation of the RMSE along the iterative procedure over all test problems. It
can be observed from this plot that our model quickly converges to a proposal
distribution with an expected value close to $\theta^{*}$.

Figure 2: Results for the Poisson simulator. (Left) We observe that the RMSE
decreases quickly during the 15 first iterations. (Right) ALFI and MLE results
are very similar.

Figure 3: (Left) Evolution of the error between the true and predicted
parameters for the Weinberg simulator, averaged over several $\theta^{*}$.
(Right) Histogram of the real VS. generated data with the inferred parameters,
for 3 different $\bm{\theta}^{*}$. The vectors on top of each figure represent
the real parameters $[\theta^{*}_{0},\theta^{*}_{1}]$ (left) and the inferred
ones $[\hat{\theta}_{0},\hat{\theta}_{1}]$

###  4.2 (Simplified) particle physics simulation

We also tested our model on a simplified simulator from particle physics,
called Weinberg and introduced as a likelihood-free inference benchmark in
(Louppe and Cranmer,, 2017). This benchmark comes with two parameters (the
beam energy and the Fermi constant) and one observable (the cosine of the
scattering angle).

#### Results

Figure 3 (left) presents the evolution of the error between the real and the
predicted parameters along 15 iterations. We see that it has learned an
iterative procedure and converges after 10 iterations. Figure 3 (right)
compares the distributions of the simulated data $p(x|\bm{\psi}_{T})$ and the
real data $p_{r}(x)$. We can see that ALFI has managed to infer parameters
that simulate a realistic distribution.

###  4.3 Robustness of the model

In order to evaluate the robustness of the learned optimization procedure, we
tested the model on a number of iterations $T_{\textrm{test}}$ greater than
the number $T_{\textrm{train}}$ used during training. On the Poisson and the
multivariate simulators (Appendix B.3), we observed that increasing the number
of iterations improves the performance of ALFI. Therefore, our model seems to
learn an update rule $\bm{\Delta}_{\psi}$ that is not tied to the specific
number of updates used a training, but rather generalizes to a larger horizon.
Those results are shown in Appendix C.

##  5 Conclusions and future works

In this work, we provide a proof-of-concept of a meta-learning architecture
designed to solve likelihood-free inference problems. We applied our model on
toy simulators and achieved results competitive with maximum likelihood
estimation. We finally applied it on a simple particle physics simulator, and
showed that it can infer parameters corresponding to samples close to the real
ones.

As for future work, we see two paths worth of exploration. First, getting a
better understanding of the optimization procedure learned by ALFI: can we
interpret the representation learned by each data encoder? Could an update
model learned for a simulator be transferred to another simulator? Is the
learned procedure comparable to other existing methods? Secondly, evaluating
our model on more complex simulators and comparing it to state-of-the-art LFI
methods: since our approach is intensive in the number of simulator calls,
moderating this complexity would be a necessary step to scale our method to
slower simulators.

## References

  * Andrychowicz et al., (2016) Andrychowicz, M., Denil, M., Gomez, S., Hoffman, M. W., Pfau, D., Schaul, T., and de Freitas, N. (2016).  Learning to learn by gradient descent by gradient descent.  In Advances in Neural Information Processing Systems, pages 3981–3989.
  * Beaumont et al., (2002) Beaumont, M. A., Zhang, W., and Balding, D. J. (2002).  Approximate bayesian computation in population genetics.  Genetics, 162(4):2025–2035.
  * Chen et al., (2016) Chen, Y., Hoffman, M. W., Colmenarejo, S. G., Denil, M., Lillicrap, T. P., Botvinick, M., and de Freitas, N. (2016).  Learning to learn without gradient descent by gradient descent.  arXiv preprint arXiv:1611.03824.
  * Cho et al., (2014) Cho, K., van Merriënboer, B., Gülçehre, Ç., Bahdanau, D., Bougares, F., Schwenk, H., and Bengio, Y. (2014).  Learning phrase representations using rnn encoder–decoder for statistical machine translation.  Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP).
  * Gutmann and Corander, (2016) Gutmann, M. U. and Corander, J. (2016).  Bayesian optimization for likelihood-free inference of simulator-based statistical models.  The Journal of Machine Learning Research, 17(1):4256–4302.
  * Kingma and Ba, (2014) Kingma, D. P. and Ba, J. (2014).  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * Louppe and Cranmer, (2017) Louppe, G. and Cranmer, K. (2017).  Adversarial variational optimization of non-differentiable simulators.  arXiv preprint arXiv:1707.07113.
  * Putzky and Welling, (2017) Putzky, P. and Welling, M. (2017).  Recurrent inference machines for solving inverse problems.  arXiv preprint arXiv:1706.04008.
  * Ravuri et al., (2018) Ravuri, S., Mohamed, S., Rosca, M., and Vinyals, O. (2018).  Learning implicit generative models with the method of learned moments.  arXiv preprint arXiv:1806.11006.
  * Staines and Barber, (2012) Staines, J. and Barber, D. (2012).  Variational optimization.  arXiv preprint arXiv:1212.4507.
  * Wierstra et al., (2014) Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J., and Schmidhuber, J. (2014).  Natural evolution strategies.  Journal of Machine Learning Research, 15:949–980.

## Appendix

##  Appendix A Experimental setup

#### Optimizer

To train our architecture, we used the ADAM optimizer (Kingma and Ba,, 2014).

#### Proposal distribution

For all the experiments, we defined $q(\bm{\theta}|\bm{\psi})$ as a
multivariate Gaussian distribution
$\mathscr{N}(\bm{\mu},\operatorname{diag}(\bm{\sigma}))$ with parameters
$\bm{\psi}\in\mathbb{R}^{d}$ where $d$ denotes the size of the parameter space
and
$\bm{\psi}_{i}=[\bm{\mu},\bm{\sigma}]\quad\text{where}\quad\bm{\mu},\bm{\sigma}\in\mathbb{R}^{d}$.
For each experiment the initial proposal $\bm{\psi}_{1}$ is made of a random
mean vector $\bm{\mu}_{1}$ drawn with the same distribution as the parameters
$\bm{\theta}^{*}$ of the different problems of the training set. The variance
vector $\bm{\sigma}_{1}$ always starts at
$\bm{\sigma}_{1}=[e^{0.5},...,e^{0.5}]$.

#### Partial loss function

For the partial loss $\ell(\bm{\psi}_{t},\bm{\theta}^{*})$ at time t, we tried
two distinct functions: the mean-squared error between the mean of
$\bm{\psi}_{t}$ and $\bm{\theta}^{*}$,
$\ell(\bm{\psi}_{t},\bm{\theta}^{*})=||\mathbb{E}_{\bm{z}\sim
q(\bm{\theta}|\bm{\psi})}[\bm{z}]-\bm{\theta}^{*}||^{2}_{2}$ and the negative-
log-likelihood of the proposal evaluated on $\bm{\theta}^{*}$,
$\ell(\bm{\psi}_{t},\bm{\theta}^{*})=-\log(q(\bm{\theta}^{*}|\bm{\psi}))$. The
later loss has the advantage of taking more the variance of the proposal into
account and lead to better performance experimentally. Therefore, we decided
to use the likelihood loss function for all the subsequent experiments.

#### Weighting function

The choice of the weighting function $w_{t}$ determines the exploration-
exploitation trade-off of our iterative algorithm. We tested three weighting
schemes:

  * •

$w_{t}=\mathds{1}_{t=T}$: only $\bm{\psi}_{T}$, the final proposal
distribution on the parameters, is taken into account in the total loss
function. It means that the algorithm can freely explore the parameter-space
during $T-1$ iterations.

  * •

$w_{t}=1$ for all $t$: all the parameters’ estimates found during the
iterative process are taken into account with the same weight. It encourages
the algorithm to converge as fast as possible to a good parameter.

  * •

$w_{t}=\frac{e^{\beta x}-1}{e^{\beta}-1}$: compromise between the two previous
weightings. The first steps are given a low weight, encouraging exploration,
while the last steps have a high weight to ensure convergence by the end.

Among those three weighting schemes, the exponential one gave the best
performance and we decided to use it for all the subsequent experiments.

#### Marginalization

To avoid overfitting, the initial value of the mean of the proposal parameters
is taken randomly. Thus to compute the performance of our model at test time,
$\bm{\psi}_{1}$ is marginalized out. To do so, we draw 500 $\bm{\psi}_{1}$
values and take the average outputs $\bm{\psi}_{T}$.

#### Hyperparameters

We provide below a list of all the hyperparameters of ALFI, along with a
description if necessary:

  * •

Number of epochs

  * •

Number of iterations $T$

  * •

Number of $\bm{\theta}^{*}$ for meta-training: size of the meta-dataset

  * •

Distribution of the $\bm{\theta}^{*}$: how the $\bm{\theta}^{*}$ used in the
meta-training are generated

  * •

Meta batch-size: number of $\bm{\theta}^{*}$ that we use to compute the
gradient that we backpropagate in our networks.

  * •

Batch size for $\bm{\theta}$: number of $\bm{\theta}$ that we generate from
$q(\bm{\theta}|\bm{\psi}_{t})$ at each time $t$

  * •

Batch size for $\bm{x}$: number of $\bm{x}$ that we generate from each
$\bm{\theta}$ generated from $\bm{\psi}_{t}$ at time $t$

  * •

Learning rate

  * •

Clipping: we force our model to follow an iterative procedure by clipping each
component of the output $\bm{\Delta}_{\psi}$ of the RNN between two values.

##  Appendix B Simulators

###  B.1 Linear Regression

#### Forward generation

The data generated by this procedure follow a linear law in 2 dimensions, the
unknown parameters of the simulator represents the slope and the offset of
this line. Formally, let $X=[x,1,y]$ denote an observation generated by
$\theta$, where $x,y\in\mathbb{R}$. Then X satisfies the constraint
$y-n=\tan(\theta_{0})x+\theta_{1}$ with $n\sim\mathscr{N}(0,0.1)$ and the
value of $x$ being drawn uniformly between $-1$ and $1$.

#### Hyperparameters

  * •

Number of epochs: $300$

  * •

Number of iterations $T$: $15$

  * •

Number of $\bm{\theta}^{*}$ for meta-training: $10000$

  * •

Distribution of the $\bm{\theta}^{*}$: uniformly in
$[0,\frac{\pi}{2}]\times[-1,1]$

  * •

Meta batch-size: $16$

  * •

Batch size for $\bm{\theta}$: $20$

  * •

Batch size for $\bm{x}$: $20$

  * •

Learning rate: $1e-3$

  * •

Clipping: $[-0.25,0.25]$

###  B.2 Poisson distribution

#### Forward generation

The forward generation process is a simple Poisson distribution which depends
on the mean parameter $\lambda\in\mathbb{R}^{+}$ of the distribution. To make
the parametrisation real we define
$\bm{\theta}=\theta=\log(\lambda)\in\mathbb{R}$. The generation of an
observation $x$ conditionally to the parameter value $\theta$ is done by
sampling $x$ from $\mathscr{P}(\lambda=e^{\theta})$.

#### Hyperparameters

  * •

Number of epochs: $300$

  * •

Number of iterations $T$: $15$

  * •

Number of $\theta^{*}$ for meta-training: $10000$

  * •

Distribution of the $\theta^{*}$: uniformly in $\left[0.2,7.0\right]$

  * •

Meta batch-size: $16$

  * •

Batch size for $\theta$: $20$

  * •

Batch size for $x$: $20$

  * •

Learning rate: $1e-3$

  * •

Clipping: $[-0.5,0.5]$

###  B.3 Multivariate Distribution

#### Forward generation

The forward generation process for
$\bm{\theta}=[\theta^{(0)},\theta^{(1)},\theta^{(2)}]$ can be described as
follow:

  1. 1.

Draw independently $z^{(0)}\sim\mathscr{N}(\theta^{(0)},1)$,
$z^{(1)}\sim\mathscr{N}(3,e^{\frac{\theta^{(1)}}{3}})$,
$z^{(2)}\sim\text{GMM}\left(\frac{1}{2}\mathscr{N}(-2,0.5),\frac{1}{2}\mathscr{N}(2,1)\right)$,
$z^{(3)}\sim\mathscr{U}(-5,\theta^{(2)})$, $z^{(4)}\sim\text{Exp}(0.5)$

  2. 2.

Compute $\bm{x}=R\bm{z}$ with
$\bm{z}=\left[z^{(0)},z^{(1)},z^{(2)},z^{(3)},z^{(4)}\right]^{T}$ where
$R\in\mathbb{R}^{5\times 5}$ is a positive semi-definite matrix.

#### Hyperparameters

  * •

Number of epochs: $300$

  * •

Number of iterations $T$: $15$

  * •

Number of $\bm{\theta}^{*}$ for meta-training: $10000$

  * •

Distribution of the $\bm{\theta}^{*}$: uniformly in $\left[-3,3\right]^{3}$

  * •

Meta batch-size: $16$

  * •

Batch size for $\bm{\theta}$: $20$

  * •

Batch size for $\bm{x}$: $20$

  * •

Learning rate: $1e-3$

  * •

Clipping: $[-0.2,0.2]$

###  B.4 Weinberg Simulator

Introduced in (Louppe and Cranmer,, 2017), Weinberg is a simplified simulator
from particle physics of electron-positron collisions resulting in muon-
antimuon pairs ($e^{+}e^{-}\rightarrow\mu^{+}\mu^{-}$).

#### Forward generation

The simulator takes two parameters, the Fermi constant $G^{f}$ and the beam
energy $E^{\textrm{beam}}$, and produces the one-dimensional observable
$x=\cos(A)$, where $A$ is the angle of the outgoing muon with respect to the
originally incoming electron.

#### Hyperparameters

To generate our training dataset we draw $10^{3}$ parameters
$[\theta_{0},\theta_{1}]$ uniformly in the square $[40,50]\times[0.5,1.5]$. We
enforce our model to follow an iterative procedure by clipping the step
$\Delta_{\psi}$ output between $-0.2$ and $0.2$.

  * •

Number of epochs: $130$

  * •

Number of iterations $T$: $15$

  * •

Number of $\bm{\theta}^{*}$ for meta-training: $1000$

  * •

Distribution of the $\bm{\theta}^{*}$: uniformly in the
$[40,50]\times[0.5,1.5]$

  * •

Meta batch-size: $16$

  * •

Batch size for $\bm{\theta}$: $8$

  * •

Batch size for $x$: $64$

  * •

Learning rate: $2e-4$

  * •

Clipping: $[-0.2,0.2]$

##  Appendix C Supplementary results

###  C.1 Poisson simulator

To check that the procedure learned by our model is robust and really
meaningful, we took a number of steps at test time $T_{\textrm{test}}=30$
greater than $T_{\textrm{train}}=15$. We see on Figure 5 that the performance
are slightly better than for $T_{\textrm{test}}=15$, which shows that our
model is robust to the number of iterations.

Figure 4: This plot shows that ALFI tested with a number of steps
$T_{\textrm{test}}=30$ gives even better result than for
$T_{\textrm{train}}=15$, in particular the upper whisker is smaller for ALFI
than for MLE.

Figure 5: Results for the multivariate simulator. (Left) The RMSE quickly
decreases during the 15 first iterations and continues to slightly decrease
afterward. (Right) The performance of our model.

###  C.2 Multivariate Distribution

This simulator is a combination of canonical distributions, aimed at showing
that our architecture has enough capacity to learn an optimization procedure
valid for parameters with very different impact on the samples. We also took a
number of steps at test time $T_{\textrm{test}}=30$ greater than
$T_{\textrm{train}}=15$. It can be observed from the left part of Figure 5
that the RMSE doesn’t increase after the iteration 15 which shows that the
learned procedure hasn’t overfitted on the number of steps. This figure also
shows that the procedure converges in both mean and variance.

It shows that the architecture has enough capacity to learn an update
procedure which eventually converges to a value close to the MLE, even in the
case where the parameters have very different effects on the generated data.

###  C.3 Linear Regression

Figure 6 presents the results for the linear regression simulator. We also
took a number of steps at test time $T_{\textrm{test}}=30$ greater than
$T_{\textrm{train}}=15$. It can be observed from the boxplot that, in average,
ALFI has performance comparable with the MLE. However, we can notice the
difficulty to estimate precisely the value of parameters for few cases.

The left sub-figure shows that the RMSE quickly converges in 15 iterations and
then is stable with a slight variance reduction during the 10 last iteration.

Figure 6: Results for the Linear Regression simulator. (Left) Fast convergence
to a small average RMSE. (Right) ALFI gives numerous outliers but for the
other points the performance of ALFI is comparable to the MLE.