Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance
Authors: Hannah Lawrence
Mitchell Tong Harris
Venue: ICLR 2024 poster (2024)
Keywords: equivariance
invariance
polynomials
non-compact
special linear group
data augmentation
universality
Primary area: general machine learning (i.e., none of the above)
TL;DR: We propose machine learning approaches, which are equivariant with respect to the non-compact group of area-preserving transformations SL(2,R), for learning to solve polynomial optimization problems.

Abstract: Optimizing and certifying the positivity of polynomials are fundamental primitives across mathematics and engineering applications, from dynamical systems to operations research. However, solving these problems in practice requires large semidefinite programs, with poor scaling in dimension and degree. In this work, we demonstrate for the first time that neural networks can effectively solve such problems in a data-driven fashion, achieving tenfold speedups while retaining high accuracy. Moreover, we observe that these polynomial learning problems are equivariant to the non-compact group $SL(2,\mathbb{R})$, which consists of area-preserving linear transformations. We therefore adapt our learning pipelines to accommodate this structure, including data augmentation, a new $SL(2,\mathbb{R})$-equivariant architecture, and an architecture equivariant with respect to its maximal compact subgroup, $SO(2, \mathbb{R})$. Surprisingly, the most successful approaches in practice do not enforce equivariance to the entire group, which we prove arises from an unusual lack of architecture universality for $SL(2,\mathbb{R})$ in particular. A consequence of this result, which is of independent interest, is that there exists an equivariant function for which there is no sequence of equivariant polynomials multiplied by arbitrary invariants that approximates the original function. This is a rare example of a symmetric problem where data augmentation outperforms a fully equivariant architecture, and provides interesting lessons in both theory and practice for other problems with non-compact symmetries.

Published as a conference paper at ICLR 2024
LEARNING POLYNOMIAL PROBLEMS WITH S2 R)- EQUIVARIANCE
Hannah Lawrence" & Mitchell Tong Harris" Massachusetts Institute of Technology
ABSTRACT
Optimizing and certifying the positivity of polynomials are fundamental primi- tives across mathematics and engineering applications, from dynamical systems to operations research. However, solving these problems in practice requires large semidefinite programs, with poor scaling in dimension and degree. In this work, we demonstrate for the first time that neural networks effectively solve such problems in a data-driven fashion, achieving tenfold speedups while retaining high accuracy. Moreover,
observe that these polynomial learning problems equiv- ariant to the non-compact group S2 R), which consists of area- area-preserving linear transformations. We therefore adapt our learning pipelines to accommodate this structure, including data augmentation, new SL R eequivarint architecture, and an architecture equivariant with respect to its maximal compact subgroup, SO(2, IR). Surprisingly, the most successful approaches in practice do not enforce equivariance to the entire group, which we prove arises from an unusual lack of architecture universality for S2(,, R) in particular. A consequence of this result, which is of independent interest, is that there exists an equivariant function for which there is sequence of equivariant polynomials multiplied by arbitrary invariants that approximates the original function. This a rare example of a symmetric problem where data augmentation outperforms fully equivariant chitecture, and provides interesting lessons in both theory and practice for other problems with non-compact symmetries.
INTRODUCTION
Machine learning has emerged as a powerful tool for accelerating classical but time-consuming algorithms in scientific domains. In PDE time-stepping and molecular dynamics, for instance, productive lines of work have arisen around learning forward-step in time regress unknown parameters (Batzner et al., 2022; Han et al., 2018). These problems are solvable by existing methods, but can be significantly sped-up by training neural net on a dataset of interest, Machine learning especially valuable for problems for which, once a solution has been found, its correctness can be verified efficiently: this the case for e.g. modeling catalysts, where candidate output conformation can be confirmed with few DFT steps (Chanussot et al., 2021).
Inspired by this line of research, we hypothesize that machine learning may allow for learning from specialized datasets of polynomials. Polynomials are ubiquitous in mathematics and engineering, and primitives such as minimizing a polynomial (Parrilo Sturmfels, 2003; Jiang, 2013; Passy Wilde, 1967; Nie, 2013; Shor, 1998) certifying its positivity (Lasserre, 2001; Prestel & Delzell, 2013; Parrilo, 2000b), have attracted attention due to their direct applications to diverse problems ranging from operations research control theory (Henrion & Garulli, 2005; Tedrake et al., 2010). Examples include certifying the stability of dynamical system with a Lyapunov function, robot path planning, and designing nonlinear controllers (Ahmadi & Majumdar, 2016). Although there exist classical methods (ApS, 2022) for solving these problems, they are often computationally expensive.
particularly attractive polynomial task for machine learning, which discuss in further detail in Section 3, is predicting a matrix certificate of nonnegativity. This certificate can be efficiently checked independently of the neural network, and the matrix is positive semidefinite (PSD), guarantees
Author order determined by coin flip.

---

Published as a conference paper at ICLR 2024
that the original polynomial is nonnegative. Thus, one does not need to trust the trained network's accuracy; the utility of a certificate, once produced by any means, can be verified efficiently.
A trained neural network could not hope to outperform based technique on all instances; rather, we assume that there is an application-specifie distribution of inputs (polynomials), and try to learn the shared attributes of such instances that may make more efficient solution possible. This is similar to the assumption made when searching for sum of squares (SOS) certificates for nonnegativity: in general, is NP hard certify that a polynomial is nonnegative (Murty & Kabadi, 1985), but one could still search for a SOS certificate of low degree via SDPs, as we discuss in Section 3. One simple example of a class with exploitable structure could be polynomials all of the form (x)) = =(x)² + C22 for s(x) a real-rooted polynomial and constants e3. If consistently present in a dataset, this structure can be leveraged to quickly compute global optima. Instead of discovering such features by hand, we learn them with a neural solver ideally more quickly than off shell algorithms for minimization, positivity certification, and beyond.
existing semidefinite programming (SDP)-
In other contexts of structured inputs, it is now common practice adapt neural architectures to the invariances of the input and output data types (Cohen & Welling, 2016). For example, architectures for point clouds are usually agnostic to translation, rotation, and permutation (Thomas et al., 201 Sa; Anderson et al., 2019), imparting improved sample efficiency and generalization (Elesedy & Zaidi, 2021). How can we design learning pipelines which take into account the underlying symmetries of polynomial learning tasks? In particular, the majority of polynomial tasks transform predictably under any linear change of variables. For example, the minimizer of polynomial tranforms equivariantly with respect to linear transformations of the input variables, while the minimum value itself is invariant (Figure 1). Instead of working with the entire general linear group, we restrict our attention to the subgroup S2, R). The special linear group S2, R) consists of 2 x 2 matrices with determinant 1, which are sometimes called auraa-prseevvigg.. Although the group is non-come con-comacct which entails many difficulties (e.g. there is no finite invariant measure over a non- con-cmmpatt group, precluding the "lifting and convolving" approach of Finzi et al. (2020); see also Appendix C.I), the irreducible representations and the Clebsch- Gordan decomposition (defined in Section 4.2) provide building blocks for an equivariant architecture (Bogatskiy et al., 2020). In the case of S2, they are both well-understood and naturally relate to polynomials. As result, we can define an architecture that achieves exact equivariance to area- prea-ereenrinng linear transformations - subject only to numerical error from finite precision, and not Monte Carlo integral approximations as in most previous work on Lie group symmetries (Finzi et al., 2020; MacDonald et al., 2021). To the best of our knowledge, this is the only known architectural technique to achieve exact S2, -equivvaaie
However, we make a surprising discovery: although this well-established method (taking tensor products and linear combinations of irreps) can approximate any equivariant polynomial, it cannot approximate any equivariant function. In other words, we prove that there exists an SL(2, R)- equivariant function for which there is no converging sequence of equivariant polynomials multiplied by arbitrary invariants (Corollary 1), result which may be of independent interest. Moreover, the function (equation 1) may be the very function one wants to approximate in positivity verification applications. Because of this impossibility result, we empirically explore other equivariance--inppred techniques, which obtain promising experimental results: data augmentation over well-conditioned subsets of ST, R), as well as an equivariant architecture with respect to the subgroup SO(2, R).
1.1 OUR CONTRIBUTIONS
In this work, our main contributions are threefold. First, we apply machine learning methods to certain polynomial problems that interest the optimization and control communities: positivity verification and minimization. To the best of our knowledge, this is the first application of machine learning to these problems. Second, we implement the first exactly SL IR) -B)equivariiatt architecture, which is universal over equivariant polynomials. Third, and perhaps most surprisingly, we prove that there exists an ST,2, RR) -equivariaat function for which there is no converging sequence of (,, R)- cquivariant polynomials. This result indicates that no tensor product-based architecture can attain universality over SL, IR) -eeequivari functions. We therefore compare the performance of other equivariance-inspne inspireed techniques that do not enforce strict equivariance to the entire symmetry group. By closely evaluating equivariance with respect to SL IR) on a concrete, undersond set of application problems, we provide a cautionary note on the incorporation of non-compact symmetries, and invitation to lean more heavily data augmentation in such cases.
2

---

Published as a conference paper at ICLR 2024
1.2
0
(c) = 1.4
0 T.4
(a) g
(b)
1.7
Figure 1: The action of SL(2, R)
Each plot is the re- sult of applying some 9 E SL(2, R) to the degrec 6 bivariate polynomial ((x - ((r-3)² (y 3)) ((x ((x+2) 2 + (v- 23) 2) + (y + - + y²). stretching or compressing the polynomial along each coordinate axis. The local minima are marked in red, and the global minimum blue. While the minimum value is invariant, the minimizer transforms equivariantly under S2,
on polynomials.
1.2 RELATED WORK
Equivariant Learning Architectures enforcing equivariance compact Lie groups abound in both theory and practice, often focusing on SO(3) as it arises widely in practice. To name just a few, Cohen al. (2018) enforces spherical equivariance using real-space nonlinearities, while Kondor et al. (2018) uses the tensor product nonlinearity. Several architectures designed for rotation-equivarian point cloud inputs also use tensor product nonlinearities (Thomas al., 201 2018a; Anderson al., 2019). Methods for more general Lie groups based on Monte Carlo approximations of convolution integrals include Finzi al. (2020) and MacDonald al. (2021), while Finzi al. (2021) presents computational method for solving for an equivariant linear layer of an arbitrary Lie group. Most relevant to our architecture is Bogatskiy et al. (2020), which introduces Lorentz-grout equivariant architecture closely related to ours; we discuss the relationship in more detail in Section 4, but note that our application area (and therefore the output layer), empirical findings, and universality properties are distinct. Finally, Gerken et al. (2022) provides one other empirical example where augmentation outperforms equivariance. However, they observe this phenomenon only for invariant tasks with respect to the compact group of rotations, whereas work with task equivariant to non-compact group, and therefore hypothesize that the underlying mechanisms are quite different.
Polynomial problems Interest in polynomial problems is driven in part by the ubiquity of their applications. One application is to find a Lyapunov function to certify stability of a system, which can be accomplished with a semidefinite programming (SDP) solver (Parrilo. 2000a;b). SDP solvers are effective when the dimensions are not too large (Mittelmann, 2003). A different method to prove polynomial nonnegativity on an interval to write the polynomial in the Bernstein basis (Farouki, 2012; Harris & Parrilo, 2023), which has been used to solve problems of robust stability (Garloff, 2000; Garloff al., 1997; Malan al., 1992: Zettler & Garloff, 1998). When the interval is not compact, however, the results are sensitive to the particular nonlinear map of the original interval to [0, 1]. For global polynomial minimization, a comparison of abstract approaches, including sum of cuuares-bascl methods, are given in Parrilo & Sturmfels (2003). Methods such as grid refinement and cutting plane algorithms can be used for many applications (Hettich & Kortanek, 1993), but the results not certifiably feasible. One such application is in designing filter banks for signal processing. Perfect reconstruction is a desirable property of filter bank, and is known to equivalent to nonnegativity of univariate trigonometric polynomial (Kortanek & Moulin, 1998; Moulin et al., 1997).
PRELIMINARIES
Special Linear Group Recall that a group G is a set closed under an associative binary operation, for which an identity element and inverses exist. The group SL(2, R) consists of 2 x real-valued matrices of determinant 1. The condition number a matrix M is the ratio of its maximum to its minimum singluar values. (Note that ST.(2, R.) contains arbitrarily poorly-conditioned matrices, as
3

---

Published as a conference paper at ICLR 2024
e.g. diagonal matrices with entries and have condition number a².) G acts on a s X if for every g. h E G and x E X', g(zz) = (gh)x and ex = x. In this case, the orbit of ry E X is (gro g E G}- A homogeneous polynomial,
form, is one in which every term has the same degree. We are concerned with homogeneous polynomials in two real variables, or binary forms. Let (d) denote the vector space of binary forms of degree d, which can be identified with R For element E V(d), we may write it as p or p(z). The action of g E S2 R) C 12x² on a binary form is defined in Section 4.1 and shown in Figure 1.
Representation Theory A representation of a group G is a vector space V together with a map p:G G or irrep, is a representation for which there does not exist subspace W C V satisfying p(g)w E W for all g E G, w. E W. The irreps are crucial tools for understanding group's s other representations. The tensor product of representations (Vi, P1) and (V2, (2) is given by p G - GT.(V V2), p(g) = Pi(g) @ P2(g). and is itself a representation. A reducible representation V3 may decomposed into direct sum of irreps Vi and V2. When V/3 is itself tensor product of irreps, this is known as the Clebsch-Gordan decomposition. The relation V/3 = V/2 @ V2 means that there exists an invertible, equivariant, linear map T V33 + Ví @ V2. An equivariant map with respect group G is map f: 1/2 + V/2 between representations (V1, P1) and (V2. P2) satisfying ((p(()) = f((1) Ag g E G. E Vi.
GV( satisfying p(g1))((z) = p(gige) for all 91.92 E G. An irreducible representation.
TASK: SUM OF SQUARES CERTIFICATE OF POLYNOMIAL NONNEGATIVITY
For the first time, propose machine learning for learning properties of polynomial input. Many questions about polynomials, as discussed in Section 1, are invariant under a change of coordinates given by SL, R). In this section, we introduce a widely applicable example, positivity verification. and we defer polynomial minimization to Appendix B.
We discuss the following problem in depth because even though the problem can be solved with convex optimization, classical methods are slow for even moderately high degree or dimension polynomials, so an efficient learned solution could be useful in practice. Moreover, many problems about polynomials can be reduced to certifying nonnegativity (e.g. proving a is a lower bound on equívalent to showing p- - a 2 0).
One method to prove that a polynomial is nonnegative is by the semidefinite programming (SDP) method described in Parrilo (2000b); Lasserre (2001). Define the d-lift as zdd (v" zyd-1
rd)". Suppose p(z)- =!d" Qu!dd for some positive semidefinite (d + 1) x (d + symmetric matrix Q. zld" Qz1c is nonnegative by definition, so the equality to p(ž) implies p is nonnegative for all x and y. The problem of finding such Q is traditionally relegated a convex optimization interior point solver. One convenient formulation given to solver is
f()) = argmax log det Q such that p(ž) = _ld" Qzta and Q 2 0,
(I)
because this objective finds the analytic center (Boyd & Vandenberghe, 2004, $8.5) of the feasible
region, which conveniently avoids the boundary of the feasible region. If is positive on R²) (0,
{ 0)}.
then f well-defined as the optimization problem has a unique maximizer. The analytic center is a good choice precisely because of its scale-invariance and the following equivariance property.
For A E S2 R), define the induced matrix Ald as the (d+ 1) x (d + 1) matrix for which (A [4] = A Fl as discussed in Marcus & Minc (1992); Marcus (1973); Parrilo & Jadbabaie (2008). The induced matrices describe how the irreps act; therefore, they are analogous the Wigner d-matrices for S3)3). Viewing a polynomial as an inner product between a basis and a coefficient vector, we get the important relation that (Az))T z/41 (Ald" p). Therefore, the optimizer (() has the equivariance property (p(A7) = Ald" f(p(7))AId.
This application is well-suited for machine learning because we often only care if there exists positive semidefinite Q. If the model predicts some matrix satisfying p(ū) zf4" Qzídl and Q h then p is automatically nonnegative; it is simple to validate this certificate of nonnegativity. This
While this problem makes sense in higher dimensions (with ST.(d, R)), we restrict to d = 2 for simplicity and defer higher dimensions to future work.
4

---

Published as a conference paper at ICLR 2024
feature is unusual for machine learning applications, but highly advantageous. Even in safety-critical systems, a pipeline could include a neural network whose output is then certified.
4 SL(2, -EQUIVAANAA ARCHITECTURE
The equivariance property of f equation suggests using an equivariant learning technique. fully equivariant architecture for (2, R) has not been previously presented. Indeed, since (2, R) a noncompact group, forming invariants by group averaging is impossible, as there is no finite invariant measure over (seee Appendix C.I for details). However, there is nonetheless straightforward strategy for equivariance. We adopt the architecture for noncompact groups given by Bogatskiy et al. (2020), which follows the established framework of taking tensor products between irreps and then applying the Clebsch-Gordan transformation (Thomas et al., 30;8b; Kondor et al., 2018). Our fully equivariant SL(2, IR) architecture insightful Lorentz group architecture. In fact, the exposition simplifies dramatically because our binary form inputs lie precisely in the group's dimeesoaieniion irreps. Moreover, the Clebseh- Gordan decomposition is given by the classical transvectant, which has been well-studied in the invariant theory literature (see Section 4.
be viewed natural specialization of their
In Section 4.1, we provide the necessary background on the representation theory of SL(2, R). In Section 4.2, we deseribe the SL(2, -equiiarrr architecture. In Section 4.3, however, we prove that universality over equivariant polynomials does not provide universality over arbitrary smooth equivariant functions for S S2, R). This is surprising and general impossibility result, which contrasts with Bogatskiy et al. (2020) and casts doubt the possibility of any universal (2, eqquivarra architecture.
4.1 REPRESENTATION THEORY OF (2)
For the purposes of this paper, are interested in knite-dimensional representations of SL(22, IR). For every positive integer d. the (d + 1) -dimensionall vector space of degree d binary forms (V(d)), is an irreducible representation of SL, RR). Throughout, we assume a monomial basis for (dd (i.e. xd. and represent elements of (dd as vectors of coefficients in Rd++1 Let p V(d), and
a=- ".-"y.... ..... ... y²) define the corresponding action on (dd by pa(g)p(z) = p(g-1 -)) These polynomial representations are all of S2 R)'s dimensionan irreps. Polynomial inputs are particularly well-suited to (2, [)- eqquivaraneee because they lie in the finite-dimensional irreducible representations.
Given two of these finite dimensional representations, V(di) and Vd2)). the tensor product represen- tation decomposes as V(d1) & (d22) ~ + min(d, .22)
((1 + d2 2m). The linear map verifying this isomorphism is an invertible, equivariant map we call T, which is the Clebsch- Maacc- decomposition for S2 R) ge. (Böhning & Bothmer, 2010)). A linear map is fully specified when defined on a basis, which we now do for T. Let p(x1, v1) V(d) and ((22, E (db). The di + d2 2n component of T(p @ q) is given by the classical nith order transvectant (see e.g. Olver (1999, $5)):
Vn (p. = (( aun Oyz
82
02
O"p
8"g
Σ (-1) m=0
p p.9
drzōyn
m
Ox m Oym
drm
y=
(2)
where other authors, e.g. Böhning Bothmer (2010), sometimes include constant factor depending on the degrees and n. This is the isomorphism between the tensor product space and the ordinary spaces of binary forms.
4.2 ARCHITECTURE DETAILS
Our equivariant architecture is described in Algorithm and in Figure 3. Each layer can be described by the nonlinear part and the linear part, and we describe each below. The inputs are elements of the finite dimensional irrep spaces of SI((, R).
Nonlinearity Each input channel has a list of polynomials, which we represent with vectors in Rd. We compute all pairwise tensor products and decompose these tensor products with T from Section 4.1, which gives a list of polynomials. We additionally apply a ("LearnedML_P in Algorithm 1) any degree 0 polynomials.
perceptron
5

---

Published as a conference paper at ICLR 2024
Algorithm| S2, ()) -qquivarian architecture
Input: Pinar E RRd+1 where Rd+1 = V(d), di d
Output: M E S4+1
1: Pinit; inputDegrees {d}; outees f
> Irrep bookkeeping
2:
for layer O...., do
3:
Init Qr for all
4:
for i.j input Degrees do
5:
for ..... jin do
6:
Append en (p., Py) E R to Q1+1-2n
> Nonlinearity and CG Decomp.
7:
Append i + 2n to outputDegrees
8: Po LeamedMLLP((Qo..ii)
MLP on Invariants + Skip Connection
9:
for i in out ((0)
P = Lemmmedllllmeenmmmmitttnnnoo
b Linear Layer + Skip Connection
11:
Imgut//egressoootpptbbrrress output
12: Return (pp. Pı. Pd- Pinit), as defined below
Final Linear Layer
Learned linear layer After the Clebsch-Gordan (CG) decomposition T, we have a collection of polynomials ranging from degree 0 to degree 2d. Gather all resulting polynomials of degree (from any tensor product and across any channel) into the vector of polynomials v. Let # be the number of such polynomials. Let e be the number of output channels. W is c x #k learnable matrix. Then Wy are the inputs of degree k for the next layer. This operation is denoted by "LLerneeLineaarCaa inearCombination" in Algorithm 1, where we additionally append the input to the layer of degree k as skip connection.
Last layer (general) The inputs to the last layer spaces, and the output lies in the vector space corresponding some finite-dimensional representation. In other words, L D V(n) V for some reducible representation with associated vector space V. Informally, Schur's Lemma describes the set of equivariant linear maps L with this property those which map linearly from the input irrep space only matching irreps in V; see e.g. Stiefel & Fässler (2012, $2) for details. Although this methodology on its own is quite standard, in the next paragraph, we show convenient way of choosing such L for positivity verification.
elements the irreducible representation
Last layer (positivity verification) Suppose (for this paragraph) the input polynomial degree 2d. The output space V =S symmetric (d + 1) (d + 1) matrices, which decomposes into irreps as Di_o (22) (the odd irreps do not contribute to symmetric matrices). An equivariant, linear map L from Dz=o (2k) to Sd+1 (which is unique up to a linear combination of channels by real version of Schur's s Lemma (Behboodi et al., 2022, $8)) can be conveniently precomputed using the transvectant; see Section A. For our application, we need p(ž) _idd" Qz Although this may seem difficult enforce, there is an elegant solution: we overwrite the degree 2d irrep with the input polynomial before computing L. This yields the desired property, because it can be shown (see Lemma
3) that !d L(O,.... Pt, ... O) 0 for any < 2d, and y.!d L(O, 0, p24) p2d-
This architecture can represent any equivariant polynomial in the following sense, which a restate- ment of Lemma D.1 1 of Bogatskiy et al. (2020) (and common primitive towards universality).
Lemma 1. Let : V + U be a polynomial that is equivariant with respect SL(2, RR,, where V and U are finite fimite-dimensioal representations of SL2,, R). Then there exists fixed choice of architectural parameters such that Algorithm exactly computes p.
4.3 LACK OF UNIVERSALITY
In this section, we prove that the architecture in Section 4.2 is not universal, in spite of Lemma 1. In particular, there invariant) that uniformly approximate the equivariant function ff described in equation
parameter settings (representing equivariant polynomial times an arbitrary
Theorem Let No (p) denote the output of Algorithum I with (learned) parameters W applied to the input p. Let J be the continuous, (2, -qquivarian function defined in equation 1. There exists

---

Published as a conference paper at ICLR 2024
an input potynomial p. and absolute constant 0 such that for any W, If(p) - -Ww(p)) > Therefore, the architecture of Section 4.2 is not universal.
This demonstrates more broadly that the function f is not approximable by any sequence of equivariant polynomials (independent of a particular neural architecture). We highlight that this particular function not an unnatural one dreamt up for the sake of this proof; rather, it is the very function we seek to approximate for positivity verification applications. We show that when p = + y². there an algebraic obstruction predicting (p) (see also Figure 4).
Definition 1. Call the monomial x²y" balanced mod if k = (mod b). The polynomial is balanced mod b if it the weighted sum of monomials that are all balanced mod b.
Lemma 2. If f and g are balanced mod b, then for every n, (f g) is balanced mod b.
Proof. Suppose f= E. and = =, bilinearity, eh,, (f.9) Ei, (n Therefore, is enough to prove that a) (f.. 9j) is the sum of balanced monomials. Let = x zhy"" and 93 = y"" A single term in the second definition of Rn in equation 2 gives a monomial proportional to
93. where all fi and 9j are monomoials balanced mod 6. By
(x 8" ("(""²"²)
drn-m dym 0x dyn-m th
(3)
Since h; r. and k5 = then h; + kj -m (mod b).
Proof of Theorem 1. Since p 8 + 8d is balanced mod 8, every polynomial output from every layer will be as well by Lemma 2. (Note that neither the MLP applied to the invariants nor linear combinations of existing monomials will introduce new monomials.) Therefore, the final degree output is proportional to z²y², implying there is no x² or y term. For the L described in Section 4.2,
any linear combination of L(x*), L(y [(x y ) L x== y²) and L(1) has a sparsity pattern of
1
0
-1.563
0
1/3
0
0
0
3.126
0
8/3
0
0
0
1000
however, f(p) x
-1.563
0
14/3
0
1..63
0000
000
8/3
0
3. 3.6
0
1/3
0
-1.663
0
1
which is a rounded/truncated result from ApS (2022). The sparsity pattern can be checked via the transvectant definition of L. Notice that the boxed numbers in the true solution (right) must be zero for any output of Nw (x:8 y²),, regardless of W. Therefore, no output of the neural net can have the correct sparsity pattern.
In light of Lemma 1, the problem not inherent to our specific architecture, because our architecture can represent any equivariant polynomial. Instead, the problem must fundamentally be that f cannot be approximated by equivariant polynomials. Therefore, we have the following corollary of potential independent interest, even outside of the machine learning community.
There exists a continuous, SL(,, -qquvvaiaan function and a compact subset of its domain for which no sequence of SL -equivaara polynomials times functions converge pointwise to the function on the subset.
Corollary 1.
What is different? There few major differences between this setup and other related universality results. First, the function f is only defined for a subset of binary forms. Another difference the equivariance to the real group ST. R) and not ST,(2, C). Theorem 4.1 of Bogatskiy et al. (2020) states that the analog of the architecture in Section 4.2 for S2 C) is universal over equivariant functions. More generally, is common prove universality via polynomial approximation (Yarotsky, 2018; Dym & Maron, 2021). What goes wrong with such proofs in the real case? One problem is that the algebra of invariants with respect to the group, and the algebra of invariants with respect to a maximally compact subgroup, may differ for the real-valued case, as noted by Haddadin (2021).²
For example, SO(2, R) is the maximal compact subgroup of S2 R) (Lang, 1985, 19). However, a + invariant of the polynomial ax² bry + cy²² under an S0 IR) action, but is not an invariant under an (T, R) action.
7

---

Published as a conference paper at ICLR 2024
Model Name
Description
mlp-aug-rots
MLP with rotation augmentations
mlp-aug-a-b
MLP with augmentations by g4 and g has condition number x s.t. x S
SO2Net-aug-dr
S0(2, IR equivariant network with data augmented by g as above
SO2Net
50 IR) equivariant architecture with no data augmentation
SL2Net
SL(2, R) equivariant architecture with no data augmentation
MLP
multilayer perceptron with no data augmentation
Table 1: Model names and meanings
Implications of these results. Nearly all equivariant universality results of which we are aware rely on polynomial approximation as a crucial intermediate step (Yarotsky, 2018; Dym & Maron, 2021; Bogatskiy et al., 2020). Moreover, the exhibited hard function exactly the one we wish to approxi- mate in many applications. Therefore, it is unclear whether any SL(2, IR) -eqqqirrrii architecture holds promise for this class of problems. Instead, we propose returning to data augmentation, as well as architecture equívariant SL(2, R)'s well-studied maximal compact subgroup, SO(2, R). One might hope to use a clever combination of (non-polynomial) renormalization and SO(2, R)- equivariance circumvent we prove in Proposition 2 of Appendix A.2 that this is not possible. For the sake of completeness, we include the S1.2Net architecture in our experiments, but find that it underperforms alternatives.
impossibility result and recover full SL R) equivariiane; however,
EXPERIMENTS
Since learning on polynomial input data is a novel contribution, there do not yet exist standardized benchmarks. Therefore, we design our own tasks: polynomial minimization and positivity verification. We have released all data generation (as well as training) code. so that future research may build on these preliminary benchmarks. We defer an exploration of polynomial minimization Appendix B.
Our experiments are divided based on the underlying distribution of polynomials used to generate synthetic data, described in further detail in Appendix B.2. The second distribution is a structured class of polynomials that are optimal for the Delsarte linear programming bound for the cardinality of spherical code (Delsarte et al., 1977), providing realistic distribution of "natural" polynomials. An interior point method (ApS, 2022) is used to generate the values of f'v) in equation 1.
There are several practical considerations when augmenting by elements of ST.(2, R.). First, since (2,,, IR) is not compact group, any data augmentation induces distribution shift (see Appendix C for a proof). This is in contrast to compact groups, where any datapoint in an orbit is just as likely as any other datapoint in that orbit. Therefore, SL -equuirrarra methods aid primarily in out- of-distribution generalization, rather than in-distribution sample complexity. Further challenges associated with the non con-compact of SL(,, I) are discussed in Appendix C.
In our experiments, we compare several instantiations of cquivariant learning. The first is the SL R) equivariant architecture described in Section 4.2. The second is class of multilayer perceptrons (MLPs). We train the ML.Ps on an augmented training distribution: starting with the same training set, we apply random SL, IR) transformations of the training polynomials. We control the conditioning of the augmentation matrices both to avoid numerical issues and to induce more or less dramatic distribution shifts to obtain several different trained MLPs. The third architecture is an SO R) equivariant model, whose details are described in Appendix A.3. We train additional versions of the S2,,, R) equivariant architecture by including data augmentations of various condition numbers. description of the model names are given in Table 1. Experiment details for all experiments, as well as equivariance tests for the various models, are included in Appendix B.
Timing Comparison: Trained Network vs Solver An impetus for turning to machine learning was to find faster ways of solving polynomial problems in practice. We compare the run time of a first order SDP solver with the wall time of trained MLP on CPU in Table 2. Since Mosek (ApS, 2022) was used to generate the data distribution, those values are used as ground truth. The MLP is about two orders of magnitude faster, while still very accurate, reported in Table 2. While the true test will be for much higher degrees, where traditional SDP solvers become prohibitive, these results are strong experimental motivation to pursue machine learning for this task.
8

---

Published as a conference paper at ICLR 2024
Degree
10
12
14
MLP NMSE
9.5e-6
6.0e-5
2.9e-5
2.3e-5
1.le-5
MLP times (min)
0.062
0.082
0.17
0.22
0.29
SCS NMSE 2.7e-5
6.2e-5
1.2e-4
2.7e-4
1.2e-3
SCS times (min)
3.50
4.94
9.11
18.8
37.4
Table Comparison the MLP to the first order solver SCS (O D'Donoghue et al., 2016). The mean squared emors are with respect to the ground truth labels computed by the second order solver, Mosek (ApS, 2022). The times are estimates for 5,000 test examples on a single CPU.
Comparison of Equivariance and Augmentation for Figure 2, we report the test enrors for each of the models. We did not only test on the test dataset; we also randomly augmented the test dataset with E SL(2, R) transformations. The average value of the condition number of Al for the transformations on the test set is labeled on the horizontal axis. The leftmost points are the test errors the original test dataset. The rightmost points are the test errors resulting from transforming the test dataset with transformations with large condition numbers.
Generalization In
On the untransformed test set, the best results are the MLP trained with augmentations close to rotations, followed by the SO2Net and unaugmented MLP. An advantage of the SO2Net is that it has about half as many parameters (see Appendix B.2 for model parameter counts). Using high condition numbers for the training augmentation of an MLP increases the test error of the untransformed dataset, validating by poorly conditioned matrices. Similarly, some models have this behavior when they encounter distribution shifts in the test set: the MLP, MLP augmented with rotations, and SO2Nets share the trend that the test error increases as the test distribution undergoes more transformations.
Observations
assertions in Appendix C. about distribution shifts induced
10"4
aug mpp
mlp-aup-34
<tnet
mp-sug-1-3
s02rel-aug-14
10-1
mip-aug-5-7
mi--ug-3-5
Teat
307
so2ret-aug-2
so2mit-au0-1-3
10-4
so2net aug 3-5
10
so2ret-aug 3-4
502 sug 5.7
mip-aug-2-3
10"
10"
10
10a
Conditin Number indured 5122.21-TTane Ti-Tsfoofoomm
Condition Number Indured SL12. 47..ne-r
(a) Test errors for max on random polynomi- als
(b) Test errors max on polynomials aris- ing from spherical code bounds
Figure 2: Test errors. The test dataset is transformed by random A SL R). The average value of the condition numbers of A.d for the transformations is labeled the horizontal axis. The computed loss is the MSE normalized by the ground-truth labels' norm (from the SDP) and with an additive term avoid dividing by zero, /(p)li and averaged over 3 independent runs.
CONCLUSION
In this work, we demonstrated the promise of machine learning for polynomial problems, particularly with equivariant learning techniques. Even simple MLP can vastly outperform an SDP solver terms of speed, while equivariance-basse based approaches such as data augmentation and rotation- equivariance can improve out-of-disttibution generalization. Surprisingly, although we construct an exactly ST, R.) -qquivaariant architecture capable of representing any ST.(2, IR -equiiivrara poly- nomial (demonstrating that
overcome some of the superficial difficulties of equivariance to noncompact groups), turns out that this does not suffice for universality. Therefore, any approach to equivariant architectures based tensor products polynomial approximation likely fails.
As future work, it would be interesting to consider paradigms for equivariance that sidestep the fun- damental roadblock of polynomial approximation. One promising direction is frame averaging (Puny et al., 2021) for S2, RR). From the perspective of applications, our proof-of croof-of-coneee oo-cceeept experiments provide strong signal pursue the acceleration of polynomial optimization with machine learning.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank Pablo Parrilo for inspiring the project and many productive conversations. HL is supported by the Fannie and John Hertz Foundation and the NSF Graduate Fellowship under Grant No. 1745302. MH supported by the NSF Graduate Fellowhip under Grant No. 2141064.
REFERENCES
Amir Ali Ahmadi and Anirudha Majumdar. Some applications of polynomial optimization in operations research and real-time decision making. Optimization Letters, 10:709-729, 2016.
Brandon Anderson, Truong-Son Hy, and Risi Kondor. Cormorant: Covariant Molecular Neural
Networks. Curran Associates Inc., Red Hook, NY, USA, 2019.
MOSEK ApS. Mosek optimizer api for python. Version, 9(17):6 4, 2022.
Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P. Mailoa, Mordechai Korbbluth, Nicola Molinari, Tess E. Smidt, and Boris Kozinsky. B(3)-qquivariant graph neural networks for data-efficient and accurate interatomic potentials. Nature Communications, 13(1), 2022. doi: 10.1038/s41467-000 29939-5. URL https: par..ar.... nsf wttpg//bbbio/o111111.....
Arash Behboodi, Gabriele Cesa, and Taco S Cohen. A pac-bayesian generalization bound for equivariant networks. Advances in Neural Information Processing Systems, 35:5654-5668, 2022.
Alexander Bogatskiy, Brandon Anderson, Jan T Offermann, Marwah Roussi, David W Miller, and Risi Kondor. Lorentz group equivariant neural network for particle physics. Proceedings of the 37th International Conference on Machine Learning, 2020.
Christian Böhning and Hans-Christiian Graf Bothmer. clebsch-gordan formula for s13 (c) and applications to rationality. Advunces in Mathemutics, 224(1):246-255 2010.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Lowik Chanussot, Abhishek Das, Siddharth Goyal, Thibaut Lavril, Muhammed Shuaibi, Morgane Riviere, Kevin Tran, Javier Meras-Dominge Caleb Ho. Weihua Hu, Aini Palizhati, Anuroop Sriram, Brandon Wood, Junwoong Yoon, Devi Parikh, C. Lawrence Zitnick, and Zachary Ulissi, Open catalyst 2020 (oc20) dataset and community challenges. ACS Catalysis, 1(100)6059-6077. 4 2021. doi: 10. htt./a/alll.aco5........
Taco S. Cohen and Max Welling. Group equivariant convolutional networks. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML 16, pp. 2990-2999. MMLR.org, 2016.
Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. International Conference on Learning Representations (ICLR), 2018
P. Delsarte, J. M. Goethals, and J. J. Seidel. Spherical codes and designs. Geometriae Dedi- cata, 6()):363-388 1977. doi: 10. 10.11007/BF01186644, URL https: http://oi..o// http://....o0011111/..1//// BFC318 773186604
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. ArXiv, 0bbs2001000240) 2021.
Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. arXiv preprint 2xXi:22022.0033: 2021.
Rida T Farouki. The Bernstein polynomial basis: A centennial retrospective. Computer Aided
Geometric Design, 29(6):379-119, 2012.
Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolutional neural networks for equivariance to lie groups on arbitrary continuous data. In ICML 2020, volume 1 119 of Proceedings of Machine Learning Research, pp. 3165-3176. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2024
Mare Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equivari- ant multilayer perceptrons for arbitrary matrix groups. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 3318-3328. PMLR, 2021. URL http::ttpp/.... /ttp:///rooceeiippoooooooo ngs ml w.r.rppresse / vv13/vv11///// ft///inzii inzi2il html.
Juergen Garloff, Birgit Graf, and Michael Zettler. Speeding an algorithm for checking robust stability of polynomials. IFAC Proceedings Volumes, 30(16):183-186) 1997.
Jürgen Garloff. Application of bernstein expansion to the solution of control problems. Reliable computing, 6(3):303-32)) 2000.
Jan Gerken, Oscar Carlsson, Hampus Linander, Fredrik Ohlsson, Christoffer Petersson, and Daniel Persson. Equivariance versus augmentation for spherical images. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 7404-74211 PMLR, 17-23 Jul 2022.
Ward Haddadin. Invariant polynomials and machine learning. arXiv preprint arXiv:2104.12733 2021.
Jiequn Han, Arnulf Jentzen, and Weinan E. Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115534)8805--810, 2018.
Mitchell Tong Harris and Pablo A Parrilo. Improved Nonnegativity Testing in the Bernstein Basis via Geometric Means, arXiv preprint MXNi:2339.11677: 2023.
Didier Henrion and Andrea Garulli, Positive polynomials in control, volume 312. Springer Science & Business Media, 2005.
Rainer Hettich and Kenneth O Kortanek. Semi-infinite programming: theory, methods, and applica- tions. SIAM review, 35(3):380-429, 1993.
Bo Jiang. Polynomial optimization: structures, algorithms, and engineering applications. University of Minnesota, 2013.
Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-gordan nets: fully fourier space spherical convolutional neural network. Advances in Neural Information Processing Systems, 31:10117- 10126, 2018.
KO Kortanek and Pierre Moulin. Semi-infinite programming in orthogonal wavelet filter design. Semi-Infiiite Programming, pp. 323-360, 1998.
Serge Lang. SI 2 (r), volume 105. Springer Science & Business Media, 1985.
Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):76-8817 2001.
Lachlan MacDonald, Sameera Ramasinghe, and Simon Lucey. Enabling equivariance for arbitrary lie groups In CVPR, 11 2021.
Stefano Malan, Mario Milanese, Michele Taragna, and Jürgen Garloff. 33 algorithm for robust performances analysis in presence of mixed parametric and dynamic perturbations. In /1992] Proceedings of the 31st IEEE Conference on Decision and Control, pp. 128-133. IEEE, 1992.
Marvin Mareus. Finite dimensional multilinear algebra, volume 23. M. Dekker, 1973.
Marvin Marcus and Henryk Minc. A survey of matrix theory and matrix inequalities, volume 14. Courier Corporation, 1992.
Hans D Mittelmann. An independent benchmarking of sdp and socp solvers. Mathematical Program- ming, 95(2):407-430. 2003.
11

---

Published as a conference paper at ICLR 2024
Pierre Moulin, Mihai Anitescu, Kenneth O Kortanek, and Florian A Potra. The role of linear semi- infinite programming in signal-adapted qmf bank design. IEEE Transactions on Signal Processing, 45(9):2100-211 1997.
Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming. Technical report, 1985.
Jiawang Nie. Polynomial optimization with real varieties. SIAM Journal on Optimization, 23(3): 1634-1646, 2013.
Brendan O' Donooguue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applica- fions, 169(3): 1042-1004 June 2016. http:t:://staaffrddoooo papppparrsapppppppppseapa. papers scs. html.
Peter Olver. Classical invariant theory. Number 44. Cambridge University Press, 1999.
Pablo A Parrilo. On a decomposition of multivariable forms via Imi methods. In Proceedings of the 2000 American Control Conference. ACC (IEEE Cat. No. 00CH36334), volume 1, pp. 322-326. IEEE, 2000a.
Pablo Parrilo.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000b.
Pablo A Parrilo and Ali Jadbabaie. Approximation of the joint spectral radius using of squares. Linear Algebra and its Applicationss, 428(10):2385-24)) -2002, 2008.
Pablo Parrilo and Bernd Sturmfels. Minimizing polynomial functions. Algorithmic and quantitative real algebraic geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 60:83-99 99, 2003.
Ury Passy and DJ Wilde. Generalized polynomial optimization. SIAM Journal on Applied Mathemat- ics, 15(5):1344-13555 1967.
Alexander Prestel and Charles Delzell. Positive polynomials: from Hilbert's 17th problem to real algebra. Springer Science Business Media, 2013.
Omri Puny, Matan Atzmon, Edward Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In The Tenth International Conference on Learning Representations, ICLR. OpenReview.net, 2021.
Naum Zuselevich Shor. Nondifferentiable optimization and polynomial problems, volume 24. Springer Science & Business Media, 1998.
E Stiefel and A Fässler. Group theoretical methods and their applications. Springer Science & Business Media, 2012.
Gabor Szegö. Orthogonal polynomials, volume 23. American Mathematical Soc., 1939.
Russ Tedrake, lan R Manchester, Mark Tobenkin, and John W Roberts. LQR-trees: Feedback motion planning via sums-of-squares verification. The International Journal of Robotics Research, 29(8):
1038-1052, 2010.
Nathaniel Thomas, Tess Smidt, Steven M. Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation- and translation-cquiiariaan neural networks for 3d point clouds. CoRR, obs/1802.,8819, 2018a. URL http: /dblp...... uni-trier. wetierrdee/eee de/db/ journals httr corrr/cor1113 1802 html 1 #abs- 1802-
Nathaniel Thomas, Tess E. Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation- and translation-qquiiariaat neural networks for 3d point clouds. CoRR, abs/1802.08219, 2018b. URL httttt//////ti org/abs/////oooooooooo.oooo.. abs//
/1s//800 11002110010 08219. 9.
Dian Wang. Jung Yeon Park, Neel Sortur, Lawson L. S. Wong, Robin Walters, and Robert Platt. The surprising effectiveness of equivariant models in domains with latent symmetry. CoRR, abs/2211 1,02331, 2022. doi: 2..88500arXiw.2211.0999
12

---

Published as a conference paper at ICLR 2024
Dian Wang, Xupeng Zhu, Jung Yeon Park, Robert Platt, and Robin Walters. A general theory of correct, incorrect, and extrinsic equivariance. CoRR, abs/2303.04745, 2023. doi: 10.48550/arXiv. 2303.04745.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, 55:407-474, 2018.
Michael Zettler and Jürgen Garloff. Robustness analysis of polynomials with polynomial parameter dependency using bernstein expansion. IEEE Transactions on Automatic Control, 43(3):425 431, 1998.
13

---

Published as a conference paper at ICLR 2024
TABLE OF CONTENTS
Technical Background and Details
14
A.I Further architecture details
14
A.2 Scale homogeneity and S0(,, IR) vs ST(2, R)
equivariance
15
A.3 S0(2, R) equivariant architecture
17
Experiments
18
B.1 Hard Example
18
B.2 Experimental Setup
B.3 Polynomial Minimization
19
B.4 Equivariance Tests for Positivity Verification
20
Practical Considerations for SL(2,
C.1 Distribution Shift
21
C.2 Induced Condition Number Study
22
C,3 Condition Number Implications
22
A TECHNICAL BACKGROUND AND DETAILS
A. FURTHER ARCHITECTURE DETAILS
In Figure 3, we provide visual of the SL(2, eqqiivaiia architecture.
We now describe how we compute the linear equivariant map (known as an intertwiner)
We first construct the linear, equivariant map L from V to inreps. Once we have defined L-1 it trivial obtain I. via one-time matrix inversion. To obtain I.-1, we will define T,-1 on each basis element of V, given by 8 e, + ej 8 where represents the monomial a'y2d- Therefor,, L (M) is in fact the Clebsch-Gordee representation space, since describes the change basis from tensor products of irreps individual irreps. As we have seen, the transvectant from equation 2 is precisely this equivariant map between the spaces ((d) V(d) and Di_ V(2k). Therefore, - (e: ej + ej e2) (vx(e, ej) e;)) ) is the inverse of the last layer. One can verify that this L 1 is linear and has the appropriate equivariance property.
decomposition of the element M in the tensor product
The following lemma implies that setting the degree 2d component to the original polynomial p in the last layer correctly enforces the constraint !!dl Mxld
p(x). Lemma 3. If L is the last layer described above, x T 0, O,......Paa... .P)x! p(x) and Id L(O...., O. p. O, ..... 0.... 0.
Proof. The last layer is linear and equivariant by construction. First, we note that every binary form is the sum or difference of 2dth powers of linear forms. (Each form in the sum/difference has 2 free parameters, with an arbitrary number we can write any binary form). Therefore, enough that
0
0
! L(0.0. O........ ... 24 2d L
!
2d
14

---

Published as a conference paper at ICLR 2024
Pairwise Tensor Products
Ciebsch-Gordan Decomposition
Linear Layer
Input
Degree 6
W +
MLP
Degres d/ + sp
4
x W
x
Dagroa
Gix Glay +
[d
Degreo d: 68
X 144
Figure 3: Our S2(2, -equivaarr layer. We use color indicate in which irrep's vector space given activation resides, i.e. the degree of polynomials that vector space. The inputs to the layer live in the fiite-dimeensional irreps of SL(,, R), corresponding to homogeneous polynomials of different degrees. The nonlinear layer takes all pairwise tensor products of these input polynomials, and the resultant matrices decomposed back into elements of the irreps using the Clebsch- decomposition of SL((2, IR). A simple consequence of Schur's Lemma that the only possible cquivariant linear layer one that linearly combines elements within each irrep's 's vector space individually, which is reflected in our linear layer. (Any isomorphism from an irrep to itself can be written as linear combinations of independent channels from the same irrep according to a real version of Schur's 's Lemma (Behboodi et al., 2022, $8).) Finally, we apply an MLP to the invariants. The outputs of the layer again reside the irrep vector spaces, and so we can compose several layers of this form.
where the second equality follows because xd @ x" represents the matrix and Vn, x²*) = 0 for all O. Therefore, the map given by p + !_!''' L(0, .,...,.......................... ......p)).
is an invertible linear transformation with rank + 1. On the other hand + - L(v)..fd is a linear map from a space dimension (d + ()(d + 2)/2 to space of dimension d + 1. By the rank-nullity theorem, the null space has dimension (d + (d + 2)/2 (d + 1), which means that all remaining dimensions of the input are in the null space.
p)z
A.2 SCALE HOMOGENEITY AND SO(2 vs SL, EQUIVARIANCE
In this work, we have evaluated both SL IR) and SO R) equivariant architectures. Because its a bigger group, S2, R) equivariance is naturally stronger than ( equivariance. However, the polynomial positivity verification problem explored in Section has the additional structure that it is not only equivariant, but also 1-scale homogeneous: if homogeneous polynomial p(.)) has verifier matrix M of maximal determinant, then cp(æ)) has verifier matrix cM of maximal determinant. (Similarly, polynomial minimization also I-homogeneous, although it SL IR) Ri)iivariann, not equivariant.) The first implication of this structural property is that we may enforce it via data normalization, as discussed below:
Data normalization If function f is I-homogeneous, and one has an approximating function g. is possible to make J-homogeneous via the following procedure:
((x)
||=: lg
||||||
Indeed, this is the normalization employ in all of our experiments, data normalization (having all inputs roughly of the same scale) is a widespread and important technique to achieve good neural network performance during training. However, it is important note that even if g is
15

---

Published as a conference paper at ICLR 2024
RL(2, eqqiivaria,, may not be. If A (2(,, R), then
Ax 3 Ao g(x) A
Ax |
δ(Az) |Axll
||=
|1
|
|
However, ||-||| * ||=||| in general; the uncertain equality does not hold unless g is already 1-
homogeneous.
One might still reasonably ask whether ST,(2 R) and SO(2, IR) equívariance actually that different in the presence of scale equivariance, since scale equivariance implies that all interesting behavior in the function to be learned is captured by its behavior on the unit ball. In this section, we expound upon the distinctions between SO(2, I) equivariance and SL(2, RR equivariance for scale- equivariant functions. Importantly, for our equivariant problem of polynomial positivity verification, the two notions are distinct this is proven in following proposition. Therefore, although the normalization procedure we employ slightly breaks equivariance (when there is no normalization), capturing both properties at once is promising future direction. Moreover, shown in subsequent plots, our architecture still captures equivariance better than other architectures.
We begin with the following example, which is our only example in which the two notions coincide. However, as explained below, it is a trivial case.
Proposition (O(n) and SI,n, R) invariance are equivalent for scale-invariant problems), Let f: IR" + R be scale-invariant function, i.e. f(ex) = =f(x)), and assume both O(n) and SL,n, R) act on R. Then (L, (in,R))-ivvrrian if and only if it is O(n)-invariii
Proof. The statement follows from the simple fact that function that is both scale-invariant and ((n)-invariant must be constant. This is because ((z) (inv-riirrience implies that f(z) depends only on ||>||, while scale invariance implies that f (xx depends only on x
The above example is not very satisfying. In the next proposition, prove that SO RR) and S2, I)) equivariance are distinct for the polynomial positivity problem considered in Section even when considering I-homogeneous functions via input normalization. The following proposition states that this is not equivalent to an SO(2, R) transformation of p.
Proposition 2 (SO(2,R) equivariance is not equivalent to SL R) equivariance and scale homo-
geneity). There exist p and there exists some element A ST2 R) such that there is rotation R E S0 R.) satisfying
Ald ||A4
Rld
This proposition is somewhat counterintuitive. If A is x then for every R", there exists an orthogonal matrix It depending on R and x such that Ax | Rx. The reason this case is different
is because even though induced matrices are size (d + 1) x (d + 1), they only have 4 degrees of freedom. This idea is formalized below.
Proof. Suppose for the sake of contradiction that for all E SL(,, R), there is some rotation R E S0(,, R) and E R satisfying
Aldlp p
R!d p.
||44p1
Left-multiplying both sides by R.T we obtain
AMD
R|4T
pdd = p.
|A4 pll
Let id
Such an M exists because (RT A) RT Ald the induced matrix map is a homomorphism, and the map is homogeneous. So the condition in the equation above is equivalent p (M) p(x)). For generic p. seems natural that there are only finitely many
n² [4]
Ald
TA
16

---

Published as a conference paper at ICLR 2024
M such that 2( p(z). In general, this is system of d - 1 degree d polynomial equations with 4 variables. For this proposition, however, we only need to show this system has finitely many solutions for a particular p.
In particular, we argue that if p = 2d + y2d, then there are only finitely many M. The terms other than n2dd + y of (ax by) 2d + (ex fy)2d would need vanish. A generic coefficient in the expansion is a constant times a d'b2d- + f'. Any term with even i and 2d i would have no and ef O. The first and last expansion terms give us that a2d + 22d and 12d + f = 1. If for instance = = 0, then e = +1 and f - +1. There are only fimitely many cases of which variables are zero to consider.
solution over the reals unless ab
Next we argue that MA-1 cannot be multiple of an orthogonal matrix (which will be contradiction to the equality M
|| RT Ald)). There exists some A SL(2, R) such that MA- is not
multiple of an orthogonal matrix for any of these finite number of M. The matrix (6
0
is in
1/r
(2, R.) for every E IR \ {0}. We will choose A so that 1 is of this form. If M = QM Ras is the QR decomposition of M, and RM =
then choose r so that 1 o = for every Ra- o²
w
Then the norms of MA-1 :)
Qu ru
and MA-1 (9) QM
e/r
are different. Since w/r)
QM is orthogonal, MA-1 1 is not a multiple of an orthogonal matrix.
Remark As result of the above proposition, SO(2, R) and ST,(2, TR.) equivariance are not equivalent for positivity verification. This is because representations of SL, R) capture richer variety of transformations than induced matrices of (2). even after normalization.
Although the proposition above proves that normalization and S0 I) equuivrrinnce together still do not suffice to capture SL, IR) equivarriace, the following reasoning still captures why we might expect SO(2, IR) -equivarree to perform well. To approximate the S IR) -qqiivariin 1- homogencous function f on an input æ, first normalize z, and then input it to an SO R. -equuivari architecture, and finally re-scale by || (More precisely, the S0(2, R) input representation in the architecture is merely the subrepresentation of the original SL I)) input representation.) Although, by the previous proposition, this technique is not SL, IR) -qquivaaaa,,,,, it still captures equivariance.
A.3
SO R) EQUIVARIANT ARCHITECTURE
The main development for the SO2Net was making such a network compatible with the input and output types required for the tasks. The input for all tasks was binary homogeneous polynomial of degree d.
Input layer The first layer maps the input to elements of the representation spaces of SO IR.. We map the homogeneous polynomial in (x, y) to homogeneous polynomial in (cos 9, sin 0) and then compute its Fourier coefficients.
Nonlinearity In the case of S0 R), the tensor product simplifies immensely. Because the elements of the representation spaces degrees and le are scalars, their tensor product is simply their product that lives in the representation space of order j + k.
Learned linear layer We are free add arbitrary linear combinations of scalars that live in the same representation spaces. These weights are learned parameters. Furthermore, we learn an MLP to apply to each set of invariants (Fourier modes of order O). We send the results of this layer into either another nonlinear layer into the final layer.
Final layer The final layer is output dependent. In the case of an invariant problem, the final layer should return an element of the representation space of order O. For the problem of Section 3, we convert these Fourier modes into a sequence of irreps of S2 R) and apply the final layer used for the SL2Net. We convert channel of Fourier modes to an ordinary binary form as follows. Every Fourier term of the form a (kos())) + b sin(k0) corresponds to a homogeneous polynomial in cos( and sf) of degree k. If l < d, where d is the degree of the binary form that we need,
17

---

Published as a conference paper at ICLR 2024
10
train Enoor
10
mip
10-7
so2net
10-11
s/2net
10-12
Figure Training curves (MSE loss) for the single input datapoint 2 + y with maximum determinant matrix in equation I as the label to fit. As described in Section 4.3, the SL2Net cannot fit this example.
multiply by the necessary power of 1 = cos)(() + sin? to lift to a form of degree d. Then we reverse-substittte (z. y) for (cos 0, sin 8). This can be used input for the last layer of the SL2Net.
The construction of this SO2Net satisfies the requirements of Theorem D. 1 of Bogatskiy et al. (2020), which implies that any equivariant map for our tasks can uniformly approximated by this network.
B EXPERIMENTS
B.1 HARD EXAMPLE
Here, we validate in Figure 4 that the SL2Net cannot learn the hard function at the single input datapoint S y whereas the SO2Net and MLP can.
B.2 EXPERIMENTAL SETUP
Nvidia Volta V100 GPUs, using the AdaM optimizer with learning rate 3 10 Roughly, training on a single GPU took 15-30 minutes for each MLP, 1.5-2.5 hours for each SL.Neet, and 2.5-6 hours for each SO2Net. For runs with data augmentation, augmentations were performed using 10, 000 presaved 2 x 2 (2 IR) matrices (and their induced versions) with condition numbers in the specified range. Details of the distribution from which these matrices generated, as well as from which the random augmentations were applied in our test error plots, can be found in the code github. com www.ooarrtt hwwraarrriiisee -mimmiiee wwtsssmmittollliiieeeee wtt.lyy...lu.i....
All experiments
Random, rotationally symmetric Random positive degree d forms were gener- ated as follows. A real Wigner matrix of dimensions (d+ + 1) (d+ 1) sampled. Each entry is an independently and identically distributed random normal variable with mean 0 and variance Then p rf4 (AT A 10 f)) The identity perturbation is added to ensure strict positivity. The maximum determinant Gram matrix was computed with ApS (2022).
Data distribution:
1.
[-1, 1] and dimension d, a spherical code is set (() S Rd of unit vectors such that for all x, E X, (x, y) E (-1, 1, a). The Delsarte bound gives upper bound for the cardinality of such code. The best such bound (Delsarte et al., 1977) is a solution to the optimization problem
Data distribution: Delsarte spherical code bounds Given constant
Σ G1))
min {ge
=1
(5)
Σ GRGA S 0 [-1,a],
S.t.
where G& is the kth Gegenbauer polynomial (Szegö, 1939, $4.7) of weight d-2 scaled by d+2-k-2 Therefore, we can define G5 recursively as Go(x) = 1, (z) ((x)= = dæ, and
d-2
A++1 G+41 IGa(x) (1 Gx
+ If the optimal polynomial is p(x) = En (z),. we know that g(z) 11==+1)''((22>> ス >
for all R.. For our experiments fix d kmux = 3 and sample uniformly random in |- 1]. Each of these a gives another polynomial (zx) after solving equation We add 10 10-4 so they are strictly positive and then homogenize these results. Our distribution the collection of such ((x).
18

---

Published as a conference paper at ICLR 2024
Architecture
Hyperparameters
Parameters
MLP
hidden layers 100-1000 (dimension 100, then 1000)
117,816
SL2Net
5 layers, 50 channels, max internal deg. 12, invariant MLP 10-10
887.771
SO2Net
3 layers, 10 channels, max internal deg. 12, invariant MLP 10-10
58,110
Table 3: Architecture hyperparameters for the max determinant experiment on random rotationally- symmetric data. For multi-layer perceptron (MLP) architectures, "z-y" indicates x hidden units. followed by hidden units, etc.
Architecture
Hyperparameters
Parameters
MLP
hidden layers 100-1000 (dimension 100, then 1000) 3 layers, 20 channels, max internal deg. 7. invariant MLP 100-1000
117816
SL.Net SO2Net
16021
3 layers, 20 channels, max internal deg. invariant MLP 100-1000
76070
Table 4: Architecture hyperparameters for the max determinant experiment on Delsarte spherical
code data. For multi-layer perceptron (MLP) architectures, "x-y" indicates æ hidden units, followed by hidden units, etc.
Positivity Verification Setup We used 5, 000 training examples, 500 validation examples, and 500 test examples. Experiments were trained for 700 epochs across random seeds. We used the hyperparameters shown in Tables 3 and 4, which were chosen heuristically by comparing validation errors across small number (< 20) of runs.
Minimization Setup For the purpose of computing the minimum of an inhomogeneous polynomial, the polynomial was generated as follows. Let m be sampled from a standard normal distribution. Let (zo, (o) each be the result of sampling independently from standard normal and taking the absolute value. a, are sampled independently from a uniform distribution on [0. 1], then let (æ1. 31) ((2a 1)2a, (26 1)8o). Then multiply collection of polynomials from the five quadratics in {(( + xn)² + (y = 30))), ((x - 21)² + (y 31 }²)} } to get a degree - 2 polynomial. Add together every product from this collection that has degree d - 2 get the polynomial p and then return p ((x -
-2,)) )2 + (y- )) + m. The minimum this polynomial is guaranteed to be m and occur at (I1, 91). After expanding the resulting polynomial, we can separate the polynomial into binary forms of degrees o...., and input all forms simultaneously into the first layer of the neural network. We used 5, 000 training examples, 100 validation examples, and 100 test examples.
Experiments were trained for 400 epochs across 2 random seeds. We used the hyperparameters shown in Table 5, which were chosen heuristically by comparing validation errors across a small number (< 20) of runs.
Normalization As noted in the previous section, we normalize input polynomials via p + [pll where ||p|| is equal to the L, norm of the polynomial's coefficients, in a monomial basis. Since our problems are l-homogennous,
rescale the outputs via ||p]|. This is done for all architectures we compare; therefore, all methods are scale equivariant (or in particular, 1-homogencous) during training and validation.
B.3 POLYNOMIAL MINIMIZATION
In this section, we repeat our experiments for an alternative SL(2, ---eqivarii problem: polyno- mial minimization. If bivariate polynomial (not necessarily homogeneous) has unique minimum,
Architecture MLP
Hyperparameters
Parameters
hidden layers T00- 1000 (dimension 100, then 1000)
104,901
SL2Net SO2Net
3 layers, 20 channels, max internal deg. 12, invariant MLP 10-10
163,628
3 layers, 10 channels, max internal deg. 12, invariant MLP 10-10
48,930
Table
Architecture hyperparameters for the minimization experiment. For multi-layer perceptron (MLP) architectures, "z-y" indicates hidden units, followed by hidden units, etc.
19

---

Published as a conference paper at ICLR 2024
so2net-aug-1-3
100
so2net-aug-3-5
Equivariance Error
10-2
so2net-aug-5-7
so2net
10-4
sl2net
10-6
mip
mlp-aug-rots
10-8
mlp-aug-1-3
10-10
mlp-aug-3-5
102
10a
104
10
mlp-aug-5-7
Condition Number of Induced SL(2, Transfooo
Figure 5: Equivariance errors for different architectures on the polynomial minimization problem. averaged over random seeds with -avvaadddeviationn error bar.
10a
so2net-aug-1-3
so2net-aug-3-5
10-1
so2net-aug-50
10-1.
sožnet
Test
aug
mip-aug-1-3
10-2.
mlp-aug-3-5
mlp-aug.3
10-2
10.
10
10
10
Candition Number Induced SL 28: Transform
Condition Number of Induced SL12, R) Transfformm
Figure 6: Normalized test errors for different architectures on the polynomial minimization problem, averaged over two random seeds with standard deviitttonn error bar.
then that global minimum is invariant to any invertible change of coordinates, including SL(2, IR). The SL IR) -qquivariat architecture amenable to this problem by the following adaptations.
The input the first layer is sequence of forms of different degrees. The degree form are all the terms of degree & of the original polynomial.
The last layer returns an element of the degree representation space an invariant scalar.
The changes to SO2Net are analogous:
The input to the network a sequence forms of different degrees. We implement this as several input channels. We interpret each as polynomial in cos(f) and sin(f) and compute the Fourier transform. We zero-pad the Fourier coefficients so that all channels have the same number of Fourier coefficients, and this collection of channels is the input the first nonlinear layer.
The output returns the Oth Fourier mode of the last layer, again an invariant scalar.
We again compare various architectures for applying machine learning to this problem. As shown in Figure 5, the S2, IR) -qquivariant architecture is far more equivariant than any other architec- ture, with without augmentations. However, as shown in Figure 6, the so2 and s12 equivariant architectures have advantage over an MILP only for very ill-conditioned (2, IR) transformations. Moreover, MIPss with ST.(2, R) augaemmmetttoo perform the best terms of test error. The takeaway similarly that the use-case should inform which model type is preferable.
B.4 EQUIVARIANCE TESTS FOR POSITIVITY VERIFICATION
Equivariance Error The equivariance error of the models in Table after transformation of the input by random A E SL(2, R) with average condition number of Add given on the horizontal axis reported in Figure 7. For p polynomial, the training label (maximum determinant matrix), and
20

---

Published as a conference paper at ICLR 2024
(p) the network's output on p. the equivariance error calculated as
|A ((p) -V(A4 || y
averaged over all p in the test set, where the norm is the Frobenius norm.
As shown, the S1.2Net architecture the most equivariant every transformation level. Almost all of the MLPs also learned some level of equivariance.
siZnet
10a
mlp-aug-rots
10a.
mlp
Equiveriance
mlp-aug-1-3
Lquivertance Error
10:
mip-auq-3a 3-4
10-7.
mlp-aug-3-5
10"2
4/2net
aug-et-aug-1-2
10-5
10"4
mlp-aug-5-7
so2net aug 1-3
so2net-aug-33
10-1
10
mip-aug-122
so2net-aug-2-3
10-10
so2net aug 5-7
11
so2net-aug--24
10c Condition Number of Induced SL12, #) Rt-Transform
10a
so2net
10-
mip-auç-2-3
Condition Number of Induced SLQ,, Rl-Tranaform
Figure 7: Equivariance enror for positivity verification
Impact of architecture In Figure 8, we also study the impact of the equivariant architecture hyperparameters on the equivariance eиrоr of the network. We find that the higher degree the internal irreps, the further the equivariance error is from numerical precision. In the following section, we hypothesize an explanation for this behavior.
C PRACTICAL CONSIDERATIONS FOR SL(2,
C.I DISTRIBUTION SHIFT
There are several crucial difficulties unique to non-compact groups, more fundamental even than the equivariant architectural design question. All of them arise due the following essential fact: non-compact group G does not have finite Haar measure. Recall that the Haar measure μ is left-invariant measure over a compact group, i.e. for any subset S C G, μ(S) = p(gS) Vg G. Since a non-compact G does not have a Haar measure integrating to 1, for any finite measure μ. on G, there exists a subset C G and E G such that p(S) ل p(gS). A similar statement can be made about space X' on which G' acts; for most group actions (and all those we consider), there exists subset C X' and E G such that ((S) + p(gS).
What is the implication of this for machine learning? If X' is data space, then the data distribution a distribution over X. For compact groups, it is nearly always assumed in prior work that is invariant under G: in other words, any datapoint in orbit is just likely any other datapoint in that same orbit. For example, a molecule in space is equally likely to appear a dataset in any 3D) orientation. When the data distribution itself invariant, augmenting data point and its label y as (gr,9) .9) (where g is drawn according to the Haar measure) effectively generates a fresh sample from the data distribution, conditioned on the particular orbit. Both data augmentation and equivariance are therefore eminently reasonable from the perspective of sample complexity, as all points in a given orbit are equally likely (and, for G a subgroup of the orthogonal group O(n). equally "important": |ga=||| || Note that for the special case of the translation group, even though it is non-compact, is trivial to emulate this "nice" behavior by centering the input data pre-procsssing step. This provides simple example of frame-averaging (Puny et al., 2021), but an analog is not known for SL(2,
In contrast, any non-trivial probability distribution over X is not the same as g for g E G when G is non-compact. Therefore, data augmentation induces a distribution shift. In this sense, non-compact equivariance is inextricably linked to the notion of "extrinsic equivariance," introduced by Wang et al. (2022), in which group transformations change the support of the data distribution. As noted in Wang al. (2023), extrinsic equivariance can be helpful or harmful, and we still lack good
21

---

Published as a conference paper at ICLR 2024
Loglo Equivariance Emror
-2
-4
-6
mx-8
mx-10
8
mx-12
-10
-12
102
10a
10a 105
Condition Number of Induced SL(2, Transform
Figure 8: The impact of the SI, R) -equivaari architecture equivariance enror. Architectures with channels in f10, 30, 50). layers in [3, 4, 5), and maximum internal irrep degree stored in {8, 10, 12] (indicated by mx 8, mx-10 etc) are trained for short time (30 epochs). The log equivariance error then averaged across architectures with the same maximum internal degree. As shown, architectures with lower internal degree tend be more equivariant. The variation in equivariance due to the other hyperparameters other than maximum irrep degree is minimal changing the maximum irrep degree has the biggest effect equivariance.
framework for understanding when either case will hold. In sum, we view SL(2, R) -eqquvvaaie as aiding out-of-distribution generalization, rather than sample complexity, where higher condition numbers induce more dramatic distribution shifts. This is an important distinction, and one that will arise when we compare an SO(2, -eqeqivaria architecture on an SO R) -iivariiant distribution with S2, (2),22,,)))g -equiivrrin architecture.
C.2 INDUCED CONDITION NUMBER STUDY
First, we demonstrate in Figure 9 the exponential relationship between the condition number (denoted by x) of A and that of Ald, Each line is randomly generated matrix A E SL RR,, and demonstrates a linear relationship between d and ) This is likely relationship that one can prove, but we defer such theorem future work.
Condition number of Ald)
107
105
103
10a
2
4
6
8
10
d
Figure 9: The condition number of Ald function of for 10 randomly generated matrices E ST, R). Here, each colored line corresponds to a different sampled matrix.
C.3 CONDITION NUMBER IMPLICATIONS
Past work on noncompact Lie groups has largely focused on how to design linear equivariant layers, but not much the practical difficulties that arise from working with group of non-orthogonal matrices. Here, we expound upon some of these difficulties, the hopes that may be useful for future practitioners working with groups which are not subgroups of the orthogonal group.
22

---

Published as a conference paper at ICLR 2024
One gnarly consequence of the non- non-unitarity of given SL(2, R) representation is that data norms vary wildly along an orbit: if g & O(2), |gæو|| * |||||| This makes the choice of loss function important, and something one must bear in mind when assessing out of distribution generalization.
Unlike elements of an orthogonal group, the elements of S2 RR) can be arbitrarily poorly condi- tioned. As shown in the previous subsection, Appendix C.2, even if A E (I, R) has moderate condition number (e.g. less than 10), AA may have condition number several orders of magnitude larger. This affects various aspects of training and testing. First, when A is poorly conditioned, it means that computed values of p(Az) and therefore M (p((A)) may be untrustworthy. This means that there is a limit to how much data augmentation can be done, and how reasonable it is to test on transformed datasets.
Our architecture is designed to be fully equivariant. This means that it should handle arbitrary transformations of the input data. When testing equivariance of our model, it is apparent that the errors from poorly conditioned transformations compound with more Clebsch-Gordan layers and higher irrep degrees. High degree polynomials in the monomial basis are poorly conditioned, and low degree polynomials may have numerical issues when we repeatedly multiply them together. This means there is practical limitation with how big the networks can be before the internal computations become unstable. This is consistent with Figure 8 from the previous section: networks with higher degree internal irrep activations are slightly less equivariant than those with lower degrees, as the architecture - by nature of its very equivariance - is constrained to apply an ill-conditioned matrix to its internal activations, as a result of the representation matrix applied to the input.
One could hope to choose a different basis for each vector space of homogeneous polynomials, such that the resulting induced representation is better-conditioned. This is an open problem for future work, and indeed may not always be possible for the entire group, as shown in the following general theorem about non-unitary representations.
Proposition 3. Let G be a group, and p G - GL(V) a representation of G with associated n-dimensional vector space of V and such that (n) C Im(p(g)). A basis change U E O(n) of V is a mapping' from p to p', where p' [g)x = Up x. Then, there is no unitary basis change of under which maxgeG k((((g) changes.
Proof. We wish to find a basis for the vector space V corresponding to a representation p such that max k(p(g)) is as small as possible. A basis change here corresponds to the mapping p(g) + Up(g)U² Therefore, we want to solve: mingeo()) max x(U p(g)U²). If Im(p(g)) contains (n)) then for any U E O(n), we can define h as the preimage of U: p(h) = U. Then, Up(g)U² = p(hgh-1), so max R=U p(g)))))) maxgeG <(((g)) is independent of U. This implies that no basis is better than any other basis at least from a worst-case perspective.
O
The standard, two-dimensional (irreducible) representation of S2, IR) satisfies the criterion of Proposition 3, as SL2 R) contains SO IR). Therefore, there is no basis under which this representation is better-conditiones
Remark 2.
least, a worst-case sense over SL(,
In spite of Proposition 3, there is still reason to believe basis may exist that performs well in practice. First, the condition that (n)) C Im(p(g)) is restrictive; for representations like the induced representations Ald of G = (T, (2, R) for d 2, this does not hold. (Consider just that there are on the order of n free parameters for elements in ((n) but only 4 for elements of SL(2, IR.) Moreover, perhaps we do not care about the metric maxgeg x(p(g)), but rather something distributional: (p(g)) In this case, could hope to find basis change that is better-conditioned on high-probability group elements.
Finally, one practical consideration to do with S2(,, (2,,2,)))qquiiie -equivarrrie and conditioning is the loss function. Although the T.2 norm is unchanged under orthogonal transformations - so that loss functions often themselves invariant the T22 norm is changed by non-unitary representations, and therefore not invariant under our non-unitary SL(2, IR) representations. As shown below, for the positivity verification problem, the normalized loss function we use in our experiments may be distorted by a factor of up to x² This means that, when we query the loss of an equivariant model on an SL R) transformed datapoint, the loss may vary in accordance with the condition number of the transformation.
We overload terminology somewhat, and refer to this as basis change of the representation itself.
23

---

Published as a conference paper at ICLR 2024
Proposition 4 (Variation of Loss Along Orbits). Let be homogeneous bivariate polynomial. Let f(p) be the true solution as in equation to the problem in Section Let Let (()) be the equivariant neural network prediction. Then
[IV(p) - f S22
[[N - f(ap)((())))
61 S
S x=E2,
(6)
(
[[
where K. is the condition number of 14,
Proof. We calculate directly
(g() M(g))l
(N(p) - H()))
[M
1 f()ggdd |I
[1(ght gldو (ee((N()) (p) f(p))
[[(gl & g Uidl vfo(f()))
mmax (g (d) )a vec (N - f(p))
(gl4) )21 vec(
The lower bound is shown by taking the minimum singular value in the numerator and maximum in the denominator.
24


Reviews:
[{"review_id": "0wUkuuqQhN", "reviewer": "Reviewer_AJ4x", "summary": "This paper poses to solve certain polynomial optimization problems using architectures which respect the SL(2,R) symmetry. \n\nBut most of the critical details are looking very opaque.", "questions": "Q1. \n\nWhy is SL(2,R) equivariance crucial to the usecases identified here? \n\nIts not possible to make the connection between this group and the problem as stated in equation 1.  \n\nQ2. \n\nWhat is the training time for the nets involved in Table 2? I guess what is reported as “MLP times” are just the inference times, right? \n\nBut the timings specified for the other methods are probably the “total” time they take to run and there are no other time costs there.  \n\nQ3. \n\nWhat is the full and explicit specification of the loss function that is being optimized in the experiment in Section 5? \n\nAnd how does this respect SL(2,R)?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "The paper has definitely identified a very novel use case for neural nets – like positivity certification for polynomials. \n\nThe experimental data also seems reasonable.", "weaknesses": "What is this $\\psi_n$ function in equation 2? This does not look like a Clebsch-Gordon coefficient.  \n\nSection 4.2 is extremely vague. The pseudocode is almost unreadable because it is calling functions (in lines 8 and 10) which has never been defined. Also, the entire motivation of this Section seems unclear to me, even if I assume the correctness of Lemma 1. How is this related to the training problem that eventually seems to be the target?  \n\nThe issues delineated in Section 4.3 do not seem relevant to the immediate question at hand which are all about certain polynomial optimizations. Or am I missing something? It would have been much better to use the space to explain what the experimental setup. Like it seems pretty critical to understand what is the author’s idea of a “natural” polynomial and these details are missing from the main paper! The loss functions used in this experiment also seem to be not clearly specified and that makes it further challenging to understand what is happening.", "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": "", "extra_scores": {}}, {"review_id": "OuiqNwHVjI", "reviewer": "Reviewer_b6w7", "summary": "This paper proposes a novel approach to learning polynomial problems with -equivariance. The authors demonstrate the effectiveness of neural networks in solving polynomial problems in a data-driven fashion, achieving tenfold speedups while retaining high accuracy. They also adapt their learning pipelines to accommodate the structure of the non-compact group , including data augmentation and new -equivariant architectures. The paper presents a thorough analysis of the proposed approach, including theoretical proofs and experimental results.", "questions": "Please check the Weaknesses listed above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+The paper presents a novel approach to solve polynomial problems with -equivariance, which is a significant contribution to the field.\n+ The authors provide a detailed analysis of the mathematical properties of the proposed approach, including its equivariance and homogeneity properties. This analysis is essential for understanding the theoretical foundations of the approach.\n+The authors provide a detailed comparison with existing methods, highlighting the advantages of their approach.", "weaknesses": "- The paper could benefit from more detailed explanations of some of the technical concepts and methods used, particularly for readers who are not familiar with the field. For example, the paper could provide more details on the mathematical background of  and its relevance to the problem at hand.\n\n- The paper could provide more details on the implementation of the proposed approach, including the datasets used in the experiments, the choice of neural network architecture and optimization algorithm. \n\n- The paper could benefit from a more detailed discussion of the limitations and potential future directions of the proposed approach.\n\n- While the proposed architecture is effective for learning equivariant polynomials, the LACK OF UNIVERSALITY mentioned could limit its applicability to more complex or diverse datasets. This could be a potential drawback when applying the proposed approach to real-world problems.\n\n- While the experimental results are promising, the authors could provide more detailed analysis and discussion of the results to further support their claims. For example, the paper could provide more details on the sensitivity of the proposed approach to hyperparameters and the robustness of the approach to noisy data.", "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": "", "extra_scores": {}}, {"review_id": "82AyLxJYX5", "reviewer": "Reviewer_J1SQ", "summary": "This paper considers the problem of learning how to provide SDP positivity certificates for polynomials. This problem can be solved using convex solvers but this is typically rather time consuming. \n\nThe paper observes that the mapping from positive polynomials to their `maximal entropy' SDP solution is SL(d) equivariant. Focusing on the d=2 case,the paper suggests an SL(2) equivariant architectures based on the Clebsch-Gordan methodology often used for SO(3) and other groups. In practice, this architecture does not perform as well as augmentation based on SO(2) equivariant baselines. The paper suggests an interesting theoretical find to (possibly) explain this: While the Clebch-Gordan architecture can construct all equivariant polynomials, the equivariant function considered in the paper cannot be approximated by equivariant polynomials.", "questions": "The formulation of finding the positive-definite witness with maximal determinant assumes that there are many such witnesses. Are there many witnesses? e.g. when we discuss polynomials of degree 2 and the monomail vector is (x,y) I think that a symmetric matrix uniquely Q uniquely defines a quadratic polynomial (x,y)Q(x,y).\nWhen we discuss polynomials of higher degree there are ambiguities that come from the fact that, say, (x^2)(y^2)=(xy)(xy). But this can be dealt with directly by adding more symmetry constraints into the matrix. In other words, the matrix should be a moment matrix as defined in [Lasserre 2001]. Once these constraints are added I believe that there will be no more ambiguities. Do you agree? If so wouldn't it make sense to incorporate the symmetries and forget about optimizing over logdet?\n\nI have two issues with the non-universality proof. The first issue has to do with the correctness of the proof. In the proof of theorem 1 you display the matrix f(x^8+y^8) (let's call it M) which was computed numerically using Mosek. Is this matrix really a factorization of x^8+y^8? \nIf I understood everything correctly, denoting v=[x^4, x^3y,...,y^4]^T we should have that for all x,y\nx^8+y^8=v^TMv\nis this correct? Trying this on numpy with the M you specified and x=1, y=1 I get \nv^TMv=1.76\nwhile for x=1 y=1\nx^8+y^8=2\nNote also that the trivial factorization of x^8+y^8 would be M0=diag(1,0,0,0,1). which is not in the domain since det(M0)=0. Thus I would suspect that this polynomial is not in the domain of f. Is that true? Or is it possible for a polynomial to have different factorizations of different ranks? Authors please let me know if there is something I misunderstood of if there is some error. Due to this possible error I'm currently setting the rating at 5 and soundness at 2. I will be happy to raise the rating if there is in fact no error. \n\n\nA second issue is with the result concerning the non-universality of the SL(2) network is not correctness but just about the exposition. It is neat that you prove that the function f you're actually  interested in cannot be approximated by SL(2) equivariant polynomials. But I do think you should note that your function f is not defined on all of the vector space: namely f(p) is only defined if p is indeed positive, and moreover there exists a *strictly* positive definite matrix verifying this. So f is defined on some subset of your vector space. The universality results in [Bogatskiy] pertain to the complex SL_2, but also to functions continuous on the whole domain, and this may end up being the more substantial difference. Another example: in  [Villar et al.] all continuous functions invariant with respect to the non-compact Lorenz group action are shown to be approximated by polynomials. Here again the continuous functions are defined on all of the domain.\n\nAnother angle to think of these issues is: For non-compact groups often distinct orbits cannot be separated by continuous functions. For example: consider the action of SL_d on d by d matrices by multiplication from the right: you can see that a d by d matrix which does not have full rank, say A=diag(0,1,1,...,1), is not in the same orbit as the zero matrix, but its orbit contains all matrices of the form diag(0,epsilon,..,epsilon) and thus any SL_d *invariant* function F continuous on all of the domain will satisfy F(A)=F(0). For more on this see [Dym and Gortler] Section 2.5 and Section 1.4, especially the paragraph titled `algebraic separation vs. orbit separation'.  \n\nSo to be concrete about this: I think you should mention in the paper that the function f is not defined everywhere, and would suggest to change the paragraph `why is SL(2,R) different' and other places where this issue is discussed, to note that this also might be a reason for the difference between universality results elsewhere and your non-universality result here.\n\nOther remarks, questions, suggestions, according to order in the paper and not importance:\nSomewhere in the paper- explain why you decided to restrict yourselves to polynomials of two variables.\n\nIn your discussion of Schur's Lemma in page 6: the lemma applies to complex representations and not real. Do you address this (if not, maybe just add a disclaimer)?\n\nPage 4: when you introduce the function f discuss its domain. Mention that in its domain the function is well defined since the opimization problem has a unique maximizer. \n\nPage 6: I didn't understand your explanation of the last layer.\n\nPage 8 timing: The accuracy you achieve is not bad, but probably can be achieved by first order methods which can be much fast than Mosek. You should at least mention this, even if you do not compare against such a method in practice.\n\nPage 9: you reference the wrong paper by Puny. You meant [Puny 2021] not [Puny 2023]\n\n\n \n\n\nReferences mentioned above:\n[Villar et al.]  Scalars are universal: Equivariant machine learning,\nstructured like classical physics\n[Dym and Gortler] Low Dimensional Invariant Embeddings for Universal Geometric\nLearning\n[Puny 21]  Frame averaging for invariant and equivariant network design\n[Lasserre 2001] Global Optimization with polynomials and the problem of moments.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. I am not aware of previous work considering the problem the paper considered: learning SDP positivity certificates. Given the high time complexity of these solvers, their centrality in convex programming, and the fact that certificates are verifiable as explained in the paper, I believe this is a very interesting problem to consider and should be considered further. The paper does a good job, in my opinion, of setting up a first empirical and theoretical baseline to consider this problem. \n\n2. Writing is good, it is an interesting story to read.\n\n3. Theorem 1 regarding non-universality seems an interesting result (despite possible error, and needing some tuning down or context as I discuss in the questions part)", "weaknesses": "1. I have some issues re the technical details of the main theorem and the premises of the method, see below. If these issues prove to be non-issues I will raise the score\n2. The architecture that actually works is rather basic: MLPs with augmentations. On the other hand one could credit the paper in finding the equivariant structure and hence what the relevant augmentations are.\n3. The argument that the SL_2(R) equivariant architecture doesn't work because of lack of universality is difficult to actually substantiate. There are many reasons why an architectures may not work well. Maybe a different SL_2 equivariant architecture will work better?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)