On Representing (Anti)Symmetric Functions
Authors: Marcus Hutter
Venue:  (2021)
Keywords: Neural network
approximation
universality
Slater determinant
Vandermonde matrix
equivariance
symmetry
anti-symmetry
symmetric polynomials
polarized basis
multilayer perceptron
continuity
smoothness

Abstract: Permutation-invariant, -equivariant, and -covariant functions and anti-symmetric functions are important in quantum physics, computer vision, and other disciplines. Applications often require most or all of the following properties: (a) a large class of such functions can be approximated, e.g. all continuous function (b) only the (anti)symmetric functions can be represented (c) a fast algorithm for computing the approximation (d) the representation itself is continuous or differentiable (e) the architecture is suitable for learning the function from data (Anti)symmetric neural networks have recently been developed and applied with great success. A few theoretical approximation results have been proven, but many questions are still open, especially for particles in more than one dimension and the anti-symmetric case, which this work focuses on. More concretely, we derive natural polynomial approximations in the symmetric case, and approximations based on a single generalized Slater determinant in the anti-symmetric case. Unlike some previous super-exponential and discontinuous approximations, these seem a more promising basis for future tighter bounds.

Under review as a conference paper at ICLR 2021
ON REPRESENTING (ANTI)S FUNCTIONS
Anonymous authors Paper under double-bling blind review
ABSTRACT
cermutation-nvariian -equivariant, and -covariant functions and anti-symmetric functions are important in quantum physics, computer vision, and other disci- plines. (Amti)symmetrii neural networks have recently been developed and ap- plied with great success. A few theoretical approximation results have been proven, but many questions are still open, especially for particles in more than More dimension and the anti-symmetric casc, which this work focusses concretely, we derive natural polynomial approximations in the symmetric case, and approximations based symmetric case. Unlike some previous super-exponential and discontinuous ap- proximations, these seem more promising basis for future tighter bounds. In the supplementary we also provide a complete and explicit universality proof of the Equivariant MultiLayer Perceptron, which implies universality of symmetric MLPs and the FermiNet.
single generalized Slater determinant in the anti-
INTRODUCTION
Neural Networks (NN), or more precisely, Multi-Layer Perceptrons (MLP), are universal function approximators [Pin99] in the sense that every (say) continuous function can be approximated ar- bitrarily well by a sufficiently large NN. The true power of NN though stems from the fact that they apparently have bias towards functions we care about and that they can be trained by local gradient-descent or variations thereof.
For many problems we have additional information about the function, e.g. symmetries under which the function of interest is invariant or covariant. Here we consider functions that are covariant" @ under permutations Of particular interest are functions that are invarian equivariant or anti- symmetric 3 under permutations.
Definition ((Antissymmetric and equivariant functions) A function & 2 + Rn N variables is called symmetric iff ((I1, R..) = ((Fa(1); ... In(n)) for all I1, In E X for all permutations म E Sn. where S, == { : {1 n) + {1 : n) A x is bijection) is called the symmetric group and {1 : n) is short for {1,...,m). Similarly, function th : Xm - TR. is called anti-symmetric (AS) iff (b,1,...,,I = ((x)))(xx(1).-- (.(()))),,,, where (TT) = +1 is the parity or sign of permutation x. A function yp X - X is called equivariant under permutations iff (x)) (x((()x)), where x (I., ..., en) and Sz(21 ...,.... In) = (Ia(1): xx(m)).
Of course (amtirsymmetric functions are also just functions, hence NN of sufficient capacity can also represent (amti)symmetric functions, and if trained on an (anti)symmetric target could converge to an (anti)symmetric function. But NNs that can represent only (amti)symmetric functions are de- sirable for multiple reasons. Equivariant MLP (EMLP) are the basis for constructing symmetric functions by simply summing the output of the last layer, and for anti-symmetric (AS) functions by
"In full generality, function f X y is covariant under group operations g E G. if f(R)) (z)) BY (f()), where R X + X' and Ry" )' + y are representations of group (clement) G.
"The symmetric group S., is the group all permutations=iiicccionss
{1,..., n + (1,..., n). intiuutationinvvriia functions are also called 'totally symmetric functions' or simply 'sym-
a ný =ldentity.
metric function'.
@ General y and X. often y = X and Rt = Rt also called coveriant.
Ry = 11 for even/odd permutations.

---

Under review as a conference paper at ICLR 2021
multiplying with Vandermonde determinants or by computing their generalized Slater determinant (GSD) defined later.
The most prominent application is in quantum physics which represents systems of identical (fermions) bosons with (anti)symmetric wave functions [PSMF20). Another application is clas- sification of point clouds in computer vision, which should be invariant under permutation of points ZKR+18)
Even if general NN can learn the (anti)symmetry, it will only do so approximately, but some ap- plications require exact (anti)symmetry, for instance in quantum physics to guarantee upper bounds on the true ground state energy [PSMF20) This has spawned interest in NNs that can represent only (anti)symmetric functions [ZKR+ HLL+ 19]. A natural question is whether such NNs can represent all reasonable (anti)symmetric functions, which the focus of this paper. We will answer this question for the (symmetric) EMLP [ZKR+18 defined in Section and for the (AS) FermiNet
[PSMF20 defined in Sections K
Approximation architectures need to satisfy number of criteria to be practically useful:
(a) they can approximate a large class functions, e.g. all continuous (anti)symmetric functions,
(b) only the (anti)symmetrie functions can be represented.
(c) fast algorithm exists for computing the approximation.
(d) the representation itself is continuous or differentiable,
(e) the architecture is suitable for learning the function from data
(which we don't discuss).
Section Section@reviews existing approximation results for (anti)symmetric functions. Section discusses various "naive" representations (linear, sampling, sorting) and their (dis)advantages, before intro- ducing the "standard" solution that satisfies (a)-(e) based on algebraic composition of basis func- tions, symmetric polynomials, and polarized bases. For simplicity the section considers only totally symmetric functions of their n real-valued inputs (the d
case), i.e. particles one dimension. Section 4 proves the representation power of single GSD for totally anti-symmetric (AS) func- tions (also d = 1). Technically we reduce the GSD to a Vandermonde determinant, and determine the loss of differentiabilityy due to the Vandermonde determinant. From Sections 5 on consider the general case of functions with n d inputs that are (anti)symment dimensional input vectors. The case = 3 is particularly relevant for particles and point clouds in 3D space. The difficulties encountered for d = 1 transfer to d > 1, while the positive results don't, or only with considerable extra effort. The universality construction and proof for the EMLP is outlined in Section with a proper treatment and all details in Sections 6-8 of the supplementary, which implies universality of symmetric MLPs and of the AS FermiNet. Section Sarioonooconee concludes. We took great care to unify notation from different sources. The list of notation in the appendix should be helpful to disambiguate some similarly looking but different notation.
when permuting their n d-
Our main novel contributions are establishing the universality of the anti-symmetric FermiNet with a single GSD (Theorems ( for and (the results are non-trivial and unexpected), and the universality of (2-hidden-layer) symmetric MLPs (Theorem 6) with complete and explicit and self-contained equivariant universality construction based on (smooth) polynomials. We took care to avoid relying results with inherently asymptotic or tabulation or discontinuous character, to enable (in future work) good approximation rates for specific function classes, such as smooth functions those with 'nice" Fourier transform [Bar93 Mak96), The supplementary material con- tains the extended version of this paper with (more) details, discussion, and proofs.
2 RELATED WORK
The study of universal approximation properties NN has a long history, see e.g. [Pin9 for a pre-millennium survey, and e.g. [LSYZ20 for recent results and references. For (anti)symmetric NN such investigation has only recently begun [ZKR + 18 WFE 19 HIL* 19 SI19].
Functions sets necessarily invariant under permutation, since the order of set elements is irrel- evant. For countable domain, [ZKR 18) derive a general representation based on encoding domain elements as bits into the binary expansion of real numbers. They conjecture that the construction
2

---

Under review as a conference paper at ICLR 2021
can be generalized to uncountable domains such RR, but it would have to involve pathological everywhere discontinuous functions [WFE' + 19]. Functions on sets of fixed size n are equivalent to symmetric functions in variables. [ZKR 18 prove symmetric version of Kolmogorov-Amold superposition theorem [Ko157] (for d = 1) based on elementary symmetric polynomials und using Newton's identities, also known as Girard-Newter or Newton-Gires formulae, which we will gen- eralize to d > 1. Another proof is provided based on homeonorphisms between vectors and ordered vectors, also with no obvious generalization to d > They do not consider AS functions.
For symmetric functions and any d 2 1, [9L provide two proofs of the symmetric superpo- sition theorem of [ZKR* + 18]: Every symmetric function can be approximated by symmetric poly- nomials, symmetrized monomials can be represented as a permanents, and Ryser's formula brings the representation into the desired polarized superposition form. The down-side is that computing permanents is NP complete, and exponentially many symmetrized monomials are needed to approx- imate f. The second proof discretizes the input space into a n d-dimensional lattice and uses indicator functions for each grid cell. They then symmetrize the indicator functions, and approxi- mate by these piecewise constant symmetric indicator functions instead of polynomials, also using Ryser formula for the final representation. Super-exponentially many indicator functions are needed, but explicit error bounds are provided. The construction is discontinuous but they remark on how make it continuous. Approximating AS for d > is based a similar lattice construction, but by summing super-exponentially many Vandermonde determinants, leading to a similar bound. We show that a single Vandermonde/Slater determinant suffices but without bound. Additionally for d = 1 we determine the loss in smoothness this construction suffers from.
SI19 prove tighter but still exponential bounds if f is Lipschitz w.r.t. 8 based on sorting which inevitably introduces irreparable discontinuities for d > 1.
The FermiNet (PSMF20 also based on EMLPs ZKR 18 but symm-tyymessiizss not with Vander- monde determinants but with GSDs. It has shown remarkable practical performance for modelling the ground state of variety of atoms and small molccules. To achieve good performance. linear combination of GSDs has been used. We show that in principle single GSD suffices, a sort of generalized Hartree- -Fokk approximation. This contrast to the increasing number of conventional Slater determinants required for increasing accuracy. Our result implies (with some caveats) that the improved practical performance of multiple GSDs due to a limited (approximation and/or learning) capacity of the EMLP, rather than a fundamental limit of the GSD.
DNE-DIMENSIONAL SYMMETRY
This section reviews various approaches to representing symmetric functions, and is the broadest review we are aware of. To ease discussion and notation, we consider d in this section. Most considerations generalize easily to d >> 1, some require significant effort, and others break. We dis- cuss various "naive" representations (linear, sampling) and their (dis)advansages, before introducing the "standard" solution that can satisfy (a)-(e). All representations consist of a finite set of fixed (inner) basis functions, which are linearly, algebraically, functionally, or otherwise combined. We then introduce symmetric polynomials, which can be used to prove the "standard" representation theorem for d 1.
The extended version contains a broader and deeper review of alternative representations, including composition by inversion, generally invariant linear bases, symmetric functions by sorting, and lin- bases for symmetric polynomials. Indeed it is the broadest review and summarized as far as possible in one big table. The extended review may also help to better grasp the concepts introduced in this section, since it is less dense and contains some illustrating examples.
aware of, and unified
Motivation. Consider E N one-dimensional particles with coordinates x, R for partiele i 1,..., n. In quantum mechanics the probability amplitude of the ground state can be described by a real-valued joint wave function X(#1 2,). Bosons have a totally symmetrie wave function: 6(#1. ((.,.....aa .rn)) ((xx(1); ..., Fn(n)) for all permutations π S C (1 n) + (1 n). Fermions v .... (r(()) where (TT) = =1 is the parity or sign of permutation म. Wave functions are continuous and almost everywhere differentiable, and often posses higher derivatives are even analytic. Nothing in this
have totally Anti-Symmetric (AS) wave functions: (III,,,, = (".
3

---

Under review as a conference paper at ICLR 2021
work hinges any special properties wave functions may possess or interpreting them as such, and the precise conditions required for our results to hold are stated in the theorems.
We are interested in representing approximating all and only such (anti)symmetric functions by neural networks. Abbreviate x = (#1,..,, and let S²(x) := (I=(1), (x(n)) be the permuted coordinates. There is an easy way to (antissymmetrize any function,
(xx)
1
Σ (x),, TES,
(x)
1
Σ (x))((((()))
(1)
n!
nz! RES..
and any (anti)symmetric function can be represented in this form (proof: use X := á or x v) we train a NN X IR" + R to approximate some function f: IK" + R to accuracy E > 0, then á (t) are (anti)symmetric approximations of f to accuracy & > 0 too, provided f itself is (anti)symmetric. Instead of averaging. the minimum or maximum median or many other compositions would also work, but the average has the advantage that smooth X lead to smooth & and th and more general, preserves many desirable properties such (Lipschiz/absolutee..) continuity, (k-times) differentiability, analyticity, etc. It possibly has all important desirable properties, but one:
Time complexity, sampling, learning. The problem with this approach is that it has n! terms, and evaluating X super-exponentially often is intractable even for moderate n, especially if is a NN. There also be no clever trick to linearly (anti)symmetriie arbitrary functions fast, intuitively since the sum pools n! independent regions of x- In the extended version we prove that computing and v are indeed NP-hard. There we also show that approximating (I) by sampling permutations is unsuitable, especially for & due to sign cancellations. Even if we could compute (I) fast, a NN would represent the function separately on all n! regions, hence potentially requires n! more training samples to learn from than an intrinsically (anti)symmetric NN. See the extended version for more detailed discussion.
Function composition and bases. Before delving into proving universality of the EMLP and the FermiNet, is instructive to first review the general concepts of function composition and basis func- tions, since NN essentially is a composition of basis functions. We want to represen//dccompse functions as f(x) = (x)). In this work we are interested symmetrie B,, where ultimately | will be represented by the first (couple of) layer(s) of an EMLP, and g by the second (couple of) layer(s). Of particular interest
n2
((x) Σ ((z))
for then 33 and hence I are obviously symmetric (permutation invariant) x. Anti-symmetry is more difficult and will be dealt with later. Formally let ʃ E F C R" - R be function (class) we wish to represent or approximate. Let 3. R" + R be basis functions for = 1,... m E N U {oo}, and B = (B1,... 3mm : E" + R be what we call basis vector (function). and 1/- : + R a basis template, sometimes called inner function [Act18] or polarized bass function. Let g G C R R be composition function (class), sometimes called 'outer function' [Act18), which creates new functions from the basis functions. Let g o 3 {o(B(-))
E G} be the class of representable functions, and G o 3 its topological closure, i.e. the class of all approximable functions x @ is called a G-basis for F if F = 9 B or F = go 3 depending on context. Interesting classes of compositions are linear Giin == {g g(x) ag Σ Di=1 Dú; Og, ag E R), algebraic Gaig := (multivariate polynomials), functional 9yunc = Rm + R, and fu-ftnctional gf == Ch for k-times continuously differentiable functions. The extended version illustrates on some simple examples how larger composition classes G allow (drastically) smaller bases (m) to represent the same functions F.
th
Algebraic basis for symmetric polynomials. is well-known that the elementary symmetric poly- nomials eb (x) generated by
II (1+ =: 1 de (x) + Xx22(x) +... + (x)
Functions may be detined on sub-spaces of k function composition may not exists, and convergence can be w.r.t. different topologies. We will ignore these technicalities unless important for our results, but the reader may assume compact-open topology, which induces uniform convergence on compacta.
4

---

Under review as a conference paper at ICLR 2021
algebraic basis of all symmetric polynomials. Explicit expressions are c1(x) = E, 24. and (x Eie, T2Zy, ..., and en (x) = 21...Zn and general ex(x) = Ei.c... <i. I,,,., For given x, the polynomial in on the l.hss. of (3) can be expanded to the r.h.s. in quadratic time or by FFT even in time On log n). so the e(x)
be computed in time (n log n),, but is not of the desired form 2 Luckily Newton already solved this problem for us. Newton's identities express the elementary symmetric polynomials e, (x),,.... ...; Cn (x) polynomials in pb(x) Σ zi;. b I,..., R. hence also (x) := (x)(x)..... ...,,((())) is an algebraic basis for all symmetric polynomials, hence by closure for all continuous symmetric functions, and is of desired form (2):
Theorem (Symmetric polarized superposition [ZKR ous symmetric function & : R + can be represented as ((x) = g(Z; ((r))) with n(x)) =
WFE 19 Thm.7) Every continu-
xx,x² x²) and continuous g 1 + R.
[ZKR provide two proofs, one based on 'composition by inversion', the other using symmet- ric polynomials and Newton's identities. The non-trivial generalization to d 1 is provided in Section
Theorem a symmetric version of the infamous Kolmogorov-Amold superposition theorem [Ko157], which solved Hilbert's 13th problem. Its deep and obscure") constructions continue to fill whole PhD theses [Liu15] Act18). It is quite remarkable that the symmetric version above is very natural and comparably easy to prove.
?
For given x, the basis ((x) can be computed in time O so is actually slower to compute than e(x). The elementary symmetric polynomials also have other advantages (integral coefficients for integral polynomials, works for fields other than I, is numerically more stable, mimics 1,2,3... particle interactions), that we need at least m 2 n functional bases for a continuous representation, so Theorem 2 is
symmetric NN based on e rather than ps may be worth pursuing. Note
optimal in this sense WFE 19 The extended version contains discussion and table with bases and properties.
4 ONE-DIMENSIONE ANTISYMMETRY
We now consider the anti-symmetric (AS) case for d = We provide representations of AS func- tions in terms of generalized Slater determinants (GSD) of partially symmetric functions. In later sections we will discuss how these partially symmetric functions arise from equivariant functions and how to represent equivariant functions by EMLP. The reason for deferral is that EMLP inherently tied to d > 1. Technically we show that the GSD can be reduced to a Vandermonde determinant, and exhibit potential loss of differentiability due the Vandermonde determinant.
Let sp: : > IR be single-particle wave functions. Consider the matrix
(11(11)
(n(x1)
(xx)
( (In)
pp (x.))
where x = (I), J. The (Slater) determinant det (x) is anti-symmetric, but can represent only small class of AS functions, essentially the AS analogue of product (wave) functions (pure states, Hartree-Fock approximation). Every continuous AS function can be apprxximatedreprrsentee by a finite/infinite linear combination of such determinants:
(e ... Inn)
det ( (x),, where $ (x) = of (x,)
alternative to generalize the Slater determinant itself PSMF20 by allowing the functions pp (zyy) to depend on all variables
((x)
( (an
involving continuous 77 with derivative 0 almost everywhere, and differentiable dense of points.
5

---

Under review as a conference paper at ICLR 2021
where Ezz ( 2441,, Fn). If (1yg( is symmetric in æzj, which we henceforth assume [6 then exchanging 2; ++ 2j is (still) equivalent to exchanging rows and j in (x)). hence det is still AS. The question arises how many GSD are needed to be able to represent every AS function 4s. The answer turns
be 'just one", but with non-obvious smoothness relations: Any AS y can be represented by some D, any analytic &i can be represented by an analytic @ for k-times continuously differentiable ei C* a large number of derivatives are potentially lost:
Theorem 3 (Representation of all (analytic) AS v)) For every (general/cnalyticcC--- (((tt))t AS function (x) there exist (general/nnllyicC()) (((())(zy)))) symmetric in zzj such that (xx) det (x).
Proof. sketch. The proof uses (1((z)(zt) == x(x1m) with x(x) (xx)/A(x) and A(x) := I1 z,)) and ( == z) for 1 < < d. For this choice, det & reduces to X times the Vandermonde determinant A. X is obviously symmetrie, but properly extending its definition to x for which A(x) = is subtle. For general tb, any continuation will do. For polynomial v representation dh x A in terms of a symmetric polynomial and AS polynomial A is well-known. This can be extended to analytic & via Taylor series expansion. For k' times differentiable di. the construction is more difficult and the reduction in differentiability unfortunate and perhaps surprising. Full proofs can be found in the extended version.
We do not know whether the loss of In(n 1) derivatives is artefact of the proof or 'real'. For instance, we have seen that linear anti-yymmetrization preserves differentiability. In Section we show that continuity preserved (only for d 1).
5 d-DIMENSIONAL (ANTI)SYMMENT
This section generalizes the theorems from Sections 3 and to d > 1: the symmetric polynomial algebraic basis and the generalized Slater determinant representation.
Motivation. We now consider n E N, d-dimensional particles with coordinates æ; E IRd for parti- cles i = 1,.... n. For d we write x; (xt, Ye: 2 E R As before, Bosons/Fermions have symmetric/AS wave functions X .... Zx). That is, does not change/changes sign under the exchange of two vectors I; and 2y. It is not symmetric/AS under the exchange of individual coor- dinates e.g. Vi <> yj. X = (æ1, .... nn,) is matrix with columns and d rows. The (representation of the) symmetry group is Sy = {
E S,} with (1 En.) == (Z.. rather than Sn-d- Functions/ f Rd + R invariant under S are sometimes called multisymmetric or block-symmetric, if calling them symmetric could cause confusion.
Algebraic basis for multisymmetric polynomials. The elementary symmetric polynomials (3) have a generalization to d > 1 [Wey46]. We only present them for d= 3. The general case is obvious from them. They can be generated from
x2
[[ λx; + ugs + v22) =:
Σ Pp epgr (X)
(4)
OSptatrSR
Even for d the explicit expressions for Epgr are rather cumbersome, but straightforward to obtain. One can show that {eppr p- S n) an algebraic basis of size m = (n+3) for all multisymmetric polynomials [Wey46). Note that constant 600o is not included/nceded. For given X, their values can be computed in time 0(mn) by expanding (4) or in time Om log n) by FFT, where =Onn.). Newton's 's identities also generalize: Epgr (X) polynomials in the polarized sums Ppgr (X) := Σn= Upprr (xx) with (x) == x"y"=". The proofs are much more involved than for d 1. For the general d-case we have:
Theorem (Multisymmetric polynomial algebraic basis (ey46)) Every continuous (block- symmmeriymmmtric function & Inn-d + R can be represented as ((X) = g(Σ (xx)) with continuous
R - IR and n Rdd - Re defined upp...p (x) = pp.. for
1 1 + + Pa (p: E ((,,...n)). hence =0 (n+d)
The bar is used visually indicate this symmetry, otherwise there difference using comma.

---

Under review as a conference paper at ICLR 2021
The basis can be computed in time ((m-d) S ((d-(n+1))) Note that there could be much smaller functional bases of size m = dn as per "our" crrppostioonbb-iivrrsieee representations in Section 3 of the extended version, which readily generalizes to d >> 1, while the above minimal algebraic basis has larger size m = O(n") for n >> d > 1. It is an open question whether continuous functional basis of size ((d)) exists, whether in polarized form (2) not.
argument for continuous
Anti-Symmetry. For 1, all AS functions v have the same (core) zeros (called Fermion nodes), namely when z; z; for some + j. which form a union of linear spaces dividing R into n! isomorphic partitions on which d are identical apart from sign 11. This fact allowed representing every & as product of symmetric function ø and the universal anti-symmetric polynomial A, leading to representation Theorem 3 For d > 1, the Fermion nodes {x : ((X) 0} form essentially arbitrary vi-dependent unions of (non-linear) manifolds partitioning Red into an arbitrary even number of cells of essentially arbitrary topology [Mn07]. This fact prevents similar simple factoring (1) Φ A) and Vandermonde-like reduction in the proof of Theorem 3 and indeed
prevents finite algebraic bases for AS polynomials. We can still show similar representation result, albeit weaker and via a different construction:
As in Section consider & (X) == (2( (20 i.e.
4 (0)
Pn (2) (ممي
(X) =
pp (a (p))
pn (n(ann2441
where ( is symmetric in Tzzj.
Theorem (Representation of all AS tb) For every AS function (X) there exist spilar (441)))))))))))))))) symmetric in Tzz such that (xX) = det (X).
The proof in the extended version is based on sorting T#(1) S x#(2) S I Ta(n) with suitable म, which is discontinuous operation in X for d > 1. is continuous though not differentiable for 1, hence Si can be chosen continuous for continuous v in d = 1. For n = and any any AS continuous/smoothhaaalyyyt representation as a GSD. Choose (o (21 222) := 2 and (2(2)](0)) == eb x2). Whether this generalizes to > 2 and d > 1 is an open problem.
function (( has easy continoous/mmoochhaaaliiio
NEURAL NETWORKS
In this section will restrict the representation power of classical MLPs to equivariant functions, which are then used to define universal (anti)symmetric NN.
Equivariance and all-but-one symmetry. We are mostly interested in (anti)symmetric func- tions, but for (de)composition we need equivariant functions, and directly need to consider the d-dimensional case. A function 4 (Rd)" - (Re")" y" is called equivariant under permutations if ( (X) s (x)))) for all permutations E Sn. With slight abuse of notation we iden- tify (x(())ı = (X) = xpi (21,02,_0 2,,) = x with so (01 (2 It is easy to see (see extended version) that a function & is equivariant (under permutations) if and only pp (X) = ( Vi and ( is symmetric in Izg. Hence Φi suffices to describe
all of y.
Equivariant Neural Network. We aim at approximating equivariant &o by an Equivariant MLP (EMLP) defined as follows: The output X' Rd' xn of an EMLP layer is computed from its input X E _dxx by
o = TX(X) (25 V. = ar (Wa; + V VEjzs u)
(5)
where Ædxn + Rd''n can be shown to be equivariant "transfer" function with weight
matrices W. V d'd'd and Rdd the biases. Using E, in [ZKR+18 18) instead of E in PSM works well. A L-(hidden)-layer EMLP concatenates L such layers (with non -ineeriyyy removed from the last layer). It is easy to see that EMLP is indeed equivariant and that the argument of ()) is the only linear function in X with such invariance 1ZKR+18 Lem.3).

---

Under review as a conference paper at ICLR 2021
In previous work may have been tacitly been assumed that the universality of the polarized rep- resentation in Theorem _ implies that EMLP can approximate all equivariant functions. In Sec- tions 7&8 of the extended version provide an explicit construction and proof based Theorem The explicit steps in the proof can be retraced if one wishes to derive error bounds.
Theorem (Universality of (wwo-hidden-layer EMLP) For any contimuous non-linear activa- tion function, EMLPs can approximate (uniformly compacta) all and only the equivariant con- tinuous functions. If a is non-polynomial, a two-hidden-layer EMLP suffices.
Proof. idea. The construction follows steps: (1) representation of polynomials in single vector 2; (2) multisymmetric polynomials in all-but-one vector crucially exploiting Theorem (3) equivariant polynomials, (4) equivariant continuous functions. Each step (1-3) constructs an EMLP. One hidden-layer EMLP suffice by classical results for MLPs [Pin99]. Two layers can be merged, leading to a 2-hidden-laye EMLP. Step (4) uses the -Stere--Wiiessrrass theorem, for which also quantitative versions exist with error bounds, e.g. based on Chebyshev polynomials.
Universal Symmmetric Network. We can approximate all symmetric continuous functions by applying any symmetric continuous function s Rdd x - RRd with the property (y.... y) - y to the output of an EMLP, e.g. s(Y) = , E Y4 or s(Y) max Vn if d' 1
Universal AntiSymmmetric Network. By Theorem we know that every AS function ab can be represented GSD of n functions symmetric in ull-but-one-variable. The proof of Theorem requires only a single symmetric function, but using an EMLP with n equivariant function can potentially preserve smoothness as discussed in the extended paper.
Let us define (toy) FermiNet as computing single GSD from the output of a universal EMLP. The real FermiNet developed in [PSM220] contains number extra features, which improves practical performance, theoretically most notably particle pair representations. Since it is a superset of our toy definition, the following theorem also applies to the full FermiNet. We arrived at the following result (under the same conditions in Theorem 6):
a single GSD can approximate any Theorem (Universality of the FermiNet) A FermiNet with continuous anti-symmeetic function.
For d = 1, the approximation is again uniform on compacta. For > 1, the proof of Theorem involves discontinuous (a( (zz)). Any discontinuous function can be approximated by continu- ous functions, not in oc-oorm but only weaker p-norm for 1 S < co. This implies the theorem also holds for important because approximating continuous functions by discontinuous components can cause all kinds of problems.
in L norm. Whether a stronger L result holds is an important open problem,
DISCUSSION
We reviewed variety of representations for (anti Gammersymettric functions (v) (Rd) IR. The most direct and natural way is as sum over n! permutations of some other function X. If e Ck then also (1)) Ck. Unfortunately this takes exponential time, or at least NP hard, and other direct approaches such as sampling or sorting have their own problems. The most promising approach is using Equivariant MIPs, for which we provided a constructive and complete universality proof, combined with trivial symmetrization and non-trivial antisyymmetrization using large number Slater determinants. We investigated to which extent single generalized Slater determinant introduced in [PSMF20), which can be computed in time (nz²), can represent all AS vb. We have shown that for d = 1, all AS v ck+a(n-1)/2 can be represented det & with & C Whether E C suffices to represent all i E C is unknown for > 0. For & = 0 it suffices. For d > 1 and 2, were only able show that AS v have representations using discontinuous Tb
Important problems regarding smoothness of the representation are open in the AS case. Whether continuous & can represent all continuous & is unknown for d >> 1, and similar for differentiability and for other properties. Indeed, whether any computationally efficient continuous representation of all and only AS is possible is unknown.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
[Act18]
Jonas Actor Computation for the Kolmogorov Superposition Theorem. Thesis, May 2018.
[Bar93]
A.R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information Theory. 39(3):33-994,, May 1993.
[HLL* 19]
Jiequn Han, Yingzhou Li, Lin Lin, Jianfeng Lu, Jiefu Zhang, and Linfeng Zhang. Universal ap- proximation of symmetric and anti-symmetric functions. arXiv:1912.0175 [physics]. December 2019.
[Ko15]]
Andrej Kolmogorov. On the Reprepsentation of Continuous Functions of Several Variables as Superpositions of Continuous Functions of One Variable and Addition. 1957.
[Liu15]
Xing Liu. Kolmogorov superposition theorem and its applications. September 2015,
[LSYZ20]
Jianfeng Lu, Zuowei Shen, Haizhao Yang. and Shijun Zhang. Deep Network Approximation for Smooth Functions. arXiv:2001 .03040 [cs, math. stat], January 2020.
[Mak96]
Y. Makovoz. Random Approximants and Neural Networks. Journal of Approximation Theory, 85(1):98-109, April 1996.
[Mit07] Lubos Mitas Topology of fermion nodes and pfaffian wavefunctions, 2007. http://nan-- bio.chu. eeo.ees/iilssTooology... -f wweemoonnoodeee ataeesssan__aafiii www.wwaanctioons-iiaaaa. Mitas.pdf.
[Pin99]
Allan Pinkus. Approximation theory of the MLP model neural networks. Acta Numerica, 8:143-195, January 1999.
[PSMF20]
David Pfau, James S. Spencer, Alexander G. D. G. Matthews, and W. M. C. Foulkes. Ab-Initio Solution of the Many-Electron Schrödinger Equation with Deep Neural Networks. Physical Review Research, 2(3):033429, September 2020.
[ST19]
Akiyoshi Sannai Masaaki Imaizumi. Improved Generalization Bound Group Invariant Equivariant Deep Networks via Quotient Feature Space. arXiv:9910.06552 [cs, stat), 2019.
[Wey46]
Hermann Weyl. The Classical Groups: Their Invariants and Reprexentations. Princeton Land- marks Mathematics Chichester, 2nd ed., with suppl edition, 1946.
Physies Mathematics. Princeton University Press, Princeton, N.J.
[WFE 19] Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, and Michael Osborne. On Limitations Representing Functions on Sets. In ICML, October 2019.
IZKR 18) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep Sets. In Advances in Neural Information Processing Systems, pages 3391-3401, April 2018.


Reviews:
[{"review_id": "o2fT2bngqCV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update:\nI have read the authors' responses and other comments.  I still think that the theoretical results on anti-symmetric functions of this submission are novel, which is, however, not well-delivered. A lot of space is wasted to discuss symmetric functions, for which the contributions of this paper are not clear.  I suggest substantially rewriting this paper by only focusing on the anti-symmetric functions. \n\n===============================================================\nSummary:\n\nThis paper studies the representation of symmetric and anti-symmetric functions as well as the parameterization with neural networks.  This issue is very important for applying deep learning to solve problems from computational quantum physics as well as point clouds.  \n\nPros:\n\nThis paper is well-organized, in particular the connection to the previous work.  The representations of symmetric and anti-symmetric functions are very important but less-studied problems. As I understand it, this paper makes some interesting contributions to this topic.  Theorem 3 & 5 are very especially interesting, which basically shows that one Slater determinant is enough to approximate any anti-symmetric functions. \n\nCons:\n\nWhile the theorems in this paper look pretty, it is not clear if they have computational advantages over the other ansatzes.  After all, no approximation rates and numerical results are provided. For example, computing Vandermonde determinants is much efficient than computing Slater determinants.  But as suggested in this paper, the approximation with Slater determinants is more efficient than the one with Vandermonde determinants. Combined them together, it is not clear which one will be more practical. Could you comment more on this point?\n\n\nOther comments:\nThe authors do not put the proofs in the appendix.  Instead, they provide an extended version of the paper in the supplemental material which includes the proofs.  This makes the reading of the proof more challenging since readers have to dig out the proofs from the long paper. So basically, there are two versions of this paper. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fsaeNYjzv2B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is about representing functions $\\psi : (\\mathbb{R}^d)^n \\rightarrow \\mathbb{R}$ that are symmetric or asymmetric with respect to the permutation group $S_n$.  The aim is to consider neural networks giving only functions that symmetric or asymmetric, and to establish universality results.  The motivation comes from applications such quantum physics or computer vision with permutation symmetries. \n\nHonestly, I am very unconvinced by this paper.  In particular, the representation for symmetric functions is essentially due to Newton ($d=1$) and to Weyl ($d > 1$).  On the other hand, the representation for asymmetric functions -- dressed up in elaborate notation and the language of Slater determinants -- seems to just be the statement that an asymmetric function is divisible by the Vandermonde determinant (when $d=1$).  Maybe there are interesting results in this paper, but the writing is so informal and apparently rushed, I simply could not tell.  Itemized comments follow.\n\n\nPage 1, Footnote 4, terminology: I would suggest just sticking to one of “covariant” or “equivariant” throughout the paper\n\nPage 1, Definition 1, notation: Although I understand the authors are using Matlab notation when they write “$\\{1 : n \\}$ is short for $\\{1, \\ldots, n\\}$”, it would be more standard to abbreviate $[n] := \\{1, \\ldots, n\\}$.\n\nPage 2, usage of $d$, notation: Please define the meaning of $d$ before referring to this notation.\n\nPage 3: “Functions on sets of fixed size n are equivalent to symmetric functions in n variables.”  Isn’t it symmetric functions in n variables restricted to the domain where no two variables take the same value?\n\nPage 4: “Instead of averaging, the minimum or maximum or median or many other compositions would\nalso work, but the average has the advantage that smooth \u001f lead to smooth \u001e and  , and more\ngeneral, preserves many desirable properties such as (Lipschitz/absolute/...) continuity, (k-times)\ndifferentiability, analyticity, etc.”  Could the authors expand on what they mean by minimum, maximum, median or other compositions to (anti)symmetrize functions?  Never heard of that.  Also, it should be remarked that the averaging operator is an orthogonal linear projection onto the subspace of (anti)symmetric functions known as the Reynolds operator in classical group invariant theory; in particular, averaging has the property that it is the identity applied to the functions that are already (anti)symmetric.\n\nPage 4, Footnote 6: “which induces uniform convergence on compacta”. I had to google “compacta” to find out it is the plural of compact subset or compact metric space. Suffice to say this word is not widely used.\n\nPage 4:  Do you mean $\\mathcal{G}_{func} := \\{g: \\mathbb{R}^m \\rightarrow \\mathbb{R}\\}$?  Also could you say more about how the basis templates $\\eta_b$ are coming in?\n\nPage 5: It is stated that computing with elementary symmetric polynomials “is numerically more stable” than with power sums.  Why?  Also why do “we need at least $m \\geq n$ functional bases for a continuous representation”?\n\nPage 5: “ Every continuous AS function can be approximated/represented by a finite/infinite linear combination of such [Slater] determinants:” Why?\n\nPage 6, Theorem 3, theorem statement: Thus you have reduced the representation of an antisymmetric function in $n$ variables to that of $n$ symmetric functions in $n-1$ variables, at the expense of an $n \\times n$ determinant.  It is not clear how computationally useful this could be, since symmetric functions in $n-1$ variables are nontrivial computationally to represent already, e.g., Theorem 2’s approach would involve $n-1$ power sums.  \n\nPage 6, Theorem 3, proof: The actual representation of $\\psi({\\bf{x}})$ that is constructed in the proof is almost certainly not useful, namely that it is the determinant of the matrix whose rows look like the following:\n\n$$\n\\begin{pmatrix}\n\\psi({\\bf{x}}) / \\Delta({\\bf{x}})  & x_1 & x_1^2 & \\ldots & x_1^{n-1} \n\\end{pmatrix}\n$$\n$$\n\\begin{pmatrix}\n\\psi({\\bf{x}}) / \\Delta({\\bf{x}})  & x_2 & x_2^2 & \\ldots & x_2^{n-1} \n\\end{pmatrix}\n$$\n\netc. (Sorry, can't get multi-rowed matrices to render properly in OpenReview...)\n\nCrucial question: why is this a good way of expressing antisymmetric functions, in theory or practice?  The content here is that any asymmetric function is divisible by the Vandermonde determinant.  If the larger $d$ representation results depend on this, I don't know how much they tell me...\n\nPage 7: “For $d > 1$, the Fermion nodes $\\{{\\bf X} :  \\psi({\\bf X}) = 0\\}$ form essentially arbitrary $\\psi$-dependent unions of (non-linear) manifolds partitioning $\\mathbb{R}^{dn}$ into an arbitrary even number of cells of essentially arbitrary topology [Mit07].”  This language is too intuitive for me.  What does this sentence mean??\n\nPage 7, Theorem 5, proof discussion:  “Whether this generalizes to $n > 2$  and $d > 1$  is an open problem.”  This is confusing.  Does the theorem have a restriction on $n$ and $d$?\n\nPage 7–8, “Equivariant Neural Network” subsection: work of Risi Kondor and coauthors needs to be cited here.\n\nPage 8, Theorem 6: It would help the reader to include in the body of the paper a more precise statement or diagram showing the construction of the approximating EMLP.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JCu-sW8HPym", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post discussion:\nI read the author's response and other reviews. I will stick to my rating and encourage the author to resubmit a revised version focusing on the antisymmetric case. \n\n\n\n\n\nSummary:\n\nThe paper studies the approximation power and shows universality results for two recent neural network models that represent symmetric and antisymmetric functions. The main contributions of the paper are claimed to be (1) Universality of Fermi-Net (antisymmetric model) with a single Generalized Slater determinant (2) Universality of symmetric MLPs. In both cases, the authors emphasize the fact that the theorems deal with (i) vector inputs rather than scalar inputs, and that (ii) the approximation results are based on smooth polynomials rather than discontinuous functions as done in previous works. \n\nWhile the problem the paper targets is interesting and important, the paper missed several important previous works and does not do a good job explaining their novelty with respect to the previous work that was cited. See below.\n\nContribution 1: I am not an expert on antisymmetric function approximation and didn’t know Ferminet, but contribution 1 seems novel to me, although the authors should make a better job explaining the difference between their results and the original FermiNet paper. It is not entirely clear what was done before and what is new\n\nContribution 2 and points (i),(ii) were discussed before in several papers. First “Provably Powerful Graph Networks” (NeurIPS 2019) used the power sum multi symmetric polynomials for representing set functions in the same way they are used in this paper.  Second, “On universal equivariant set networks” (ICLR 2020) proves a universal approximation theorem for equivariant set functions based on these polynomials. Given these two works, I am not sure the current paper has any additional contribution.\n\nStrong points:\n\nUnderstanding the approximation power of invariant/equivariant neural networks is an important goal.\nThe results on antisymmetric functions are nice\n\nWeak points:\n\nThe work is not properly positioned with respect to previous work and pretty much misses all the work done on the approximation of invariant functions since DeepSets. Except for the discussion above, the following should be cited/discussed:\n\n-- “Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs” ICLR 2019, which discusses permutation sampling strategies. \n\n-- “Universal approximations of invariant maps by neural networks” 2018 that discusses symmetrization and approximation of symmetric functions (and function invariant to many other compact groups). \n\n-- “PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation” CVPR 2017, which also show universal approximation for symmetric functions.\n\n-- “On the Universality of Invariant Networks”, \"Universal Equivariant Multilayer Perceptrons\" ICML 2019/2020 might also be relevant.\n\nRecommendation:\n\nThe paper studies an important problem but missed significant previous work. I believe that the results on antisymmetric function approximation are novel and suggest rewriting the paper focused on these results, with a clear discussion on the contribution with respect to previous works. It might also be good to spend more time on Ferminet while doing so since this model is less known to the machine learning community. In its current form, The paper is not ready for publication.\n\nMinor comments:\n\nThe authors added a long version (22 pages) as an appendix. Not sure if this is OK. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1-B5jF2nkMB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors study the representability of symmetric or antisymmetric functions using neural networks. In particular, we say f: R^n -> R is symmetric/ antisymmetric if f(x)= f(pi(x)) for all pi in S_n or is of the form f(x)= sign(pi) *f(pi(x)) where sign(pi) is the sign of the permutation. Such functions with such symmetries are ubiquitous in quantum physics since if one looks at the wave function of a  system of identical bosons, then they are symmetric and if you look at fermions they are antisymmetric. In this paper they authors try to understand if there exists succinct architectures that can learn/represent functions with such a symmetry property.  In this direction the author makes a few observations For every \"nice\" antisymmetric function f, there exists a symmetric function Phi and a matrix associated to Phi such that determinant of Phi can be used to represent f.  Then the authors show that the standard Ferminet (the first demonstration of deep learning) can be used to represent determinants of slater determinant and hence an arbitrary continous antisymmetric function.\n\nOverall, this paper is interesting to read but I wouldn't recommend it for acceptance for the following reasons:\n\n1) There are many points which seem like \"overselling\". The author claims that a polynomial f: R^n -> R has n! many terms and that is too many to approximate and so on. Sure this is true, but the symmetries make a huge difference here. Additionally, there is a rich theory of approximation theory saying we can approximate symmetric functions by low-degree polynomials, so why not just allow the NN to compute this low-degree polynomial which in turn approximates f? \n\n2) It seems to me that this paper is more of a review, than something novel. Even the author at many places claims that this paper is a thorough review, so its not clear if it clears the bar for ICLR.\n\n3) The main results of this paper are straightforward in some sense. In fact the author doesn't even talk of the main results for the first 5 pages and the main results are simply swept under the rag, and it's not clear to me what is the novelty of the results in that case. The quantum motivation also seems very weak, i prefer a much more solid motivation for why such functions are useful (given the author mentions practicality).\n\nGiven these reservations I wouldn't accept it for recommendation.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received reviews from experts in representation of invariant functions. They all have expressed concerns regarding the novelty of the technical contributions, and the lack of appropriate comparisons to existing results. This applies in particular to representation of symmetric functions using neural networks which was largely covered by previous works, as acknowledged by the authors. The authors are encouraged to consider the valuable inputs by the reviewers and revise accordingly. 
Decision: Reject