Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance

We sincerely thank the reviewer for their thorough review of our paper, and for acknowledging the significance of the proposed problem and our contribution to it. We now respond to individual points below.

Weakness 1: technical detail clarification

We clarify the reviewer’s points in the sections below. Indeed, we believe these issues are non-issues, but the reviewer should please feel free to follow up if anything remains unclear (and we very much thank the reviewer for their attention to detail).

Weakness 2: MLP with augmentations performs best

Indeed, the message of our empirical findings is that a simple method (data augmentation) works best, although as noted in Section 5, some care must be taken to augment with reasonably well-conditioned elements of $SL(2,\mathbb{R})$. This could save practitioners time, in not designing a complex polynomial-based equivariant architecture; it could also prompt the development of different equivariant paradigms.

Weakness 3: Why our $SL(2,\mathbb{R})$-equivariant architecture failed, and whether another architecture will work better

The reviewer is correct that multiple factors can contribute to the failure of an architecture to train. However, we demonstrate not just that the architecture isn’t universal, but that it can’t represent the very function we would like to train it to represent for positivity verification. Therefore, it is at the very least one problem in our experiments with this architecture. Moreover, the conclusion of Section 4.3 is not just that this particular architecture will not work -- it’s that the function we are trying to learn cannot be approximated by any equivariant polynomial. Therefore, any architecture based on approximation via polynomials will fail for this application. However, we agree that designing an architecture that goes beyond approximating equivariant polynomials is a natural future direction. Should such an architecture continue to underperform relative to an augmented MLP, it would likely then be due to another reason.

Question: Certificate degrees of freedom

As you pointed out, for the degree 2 case there is a unique feasible point. However, as soon as the polynomial is degree 4, there is a degree of freedom. For example, consider $p = x^4 - x^2y^2 + y^4$. For any $z$, a matrix of the form $Q = \begin{pmatrix} 1 & 0 & z\\\ 0 &-1-2z& 0\\\ z &0 & 1 \end{pmatrix}$ is a witness for the positivity of $p$. Restricting that the main antidiagonal has equal entries (like in a moment matrix) would give the matrix $\begin{pmatrix}1& 0& -\frac13\\\ 0 & -\frac13& 0\\\ -\frac13 & 0 & 1\end{pmatrix}$, which does not have a positive determinant. On the other hand, $\begin{pmatrix}1 & 0 & -.75 \\\ 0 & .5 & 0\\\ -.75 & 0 & 1\end{pmatrix}$ is also a witness (with $z = -.75$), and the eigenvalues are positive. This is just one example of why additional restrictions will sometimes prohibit you from finding a PSD certificate. (See Example 4.1 of [Parrilo] for another example of how playing with the free parameter may uncover a PSD certificate). We selected the certificate of maximal determinant because it is the analytic center of all such possible witnesses.

To be clear, we do require $(xy)(xy) = x^2 y^2$. For example, consider the following bilinear form: $\begin{pmatrix} x_1^2 \\\ x_1y_1 \\\ y_1^2 \end{pmatrix}^T \begin{pmatrix}1 & 2& 3\\\ 2 & 4& 5\\\ 3& 5& 6\end{pmatrix} \begin{pmatrix} x_2^2 \\\ x_2y_2 \\\ y_2^2 \end{pmatrix} =\cdots + 3y_1^2x_2^2 + 4x_1y_1x_2y_2+3x_1^2y_2^2 + \cdots$ Because we require $x_1 = x_2$ and $y_1 = y_2$, these 3 terms collapse to $10 x^2y^2$. However, there is no reason to require the coefficient 3 to equal the coefficient 4.

Question: Rounding in non-universality proof

You are correct that the matrix M does not precisely satisfy the linear equations. However, this is due to rounding (which we tried to imply by using “$\approx$”). As you pointed out, this is confusing, so we can include more digits

We thank the reviewer for their positive review of our paper.

We thank the reviewer for providing feedback on our paper, and for highlighting the novelty of the positivity certification application. We hope to clarify the reviewer’s questions below.

Transvectant/Clebsch-Gordan Clarification

Although the form may look unfamiliar, the transvectant, which we denote by $\psi$, indeed describes precisely the map from two irreps to their tensor product’s decomposition back into irreps. It may be helpful to recall that the finite dimensional irreducible vector spaces of $SL(2,\mathbb{R})$ can be identified with the homogeneous polynomials of a given degree, so the Clebsch-Gordan coefficients for $SL(2,\mathbb{R})$ should map two input polynomials to an output polynomial. ($\psi_n$ indeed maps two input polynomials to an output polynomial.) Please also see the first paragraph of the introduction to Böhning [1] for formal clarification that the transvectant operation, which we denote by $\psi$, is exactly the Clebsch-Gordan map for this group.

Section 4.2 and pseudocode

Thank you for pointing out the ambiguity in the functions in the pseudocode in Section 4.2. We have corrected this in the updated draft.

We have also rewritten the description of the last layer in Section 4.2, deferring the exact details of the mathematical derivation (which may have been confusing) to the appendix.

Relevance of Section 4.3 to polynomial optimizations, and experimental details

Positivity verification, as described in Section 3, is an equivariant learning task. Therefore, one might naturally design an equivariant architecture for this problem, as we do in Sections 4.1-4.2. The surprising, and central, theoretical contribution of this paper is that an equivariant network ostensibly designed for the very purpose of positivity verification, is in fact unable to approximate the function of interest for positivity verification. Therefore, any network designed to solve this problem must be able to output more than just equivariant polynomials, which is a significant restriction on the architectural design space relative to prior work! To the best of our knowledge, such a finding is also without precedent in the equivariance literature. It also provides some motivation for using data augmentation, rather than an equivariant architecture. This is the content of Section 4.3. Corollary 1 implies that it doesn’t matter what loss function we use -- no equivariant polynomial can approximate the function of interest under any standard loss function. In the paper, we used the normalized mean squared error loss (with a small additive stabilization term in the denominator), as noted in the caption of Figure 2.

By “natural” polynomials, we just meant that they come from a naturally occurring, application-specific distribution, such that it is empirically possible to well-approximate an NP-hard optimization like polynomial positivity verification over this distribution. (Intuitively, we would expect such a distribution to have low entropy -- it should differ significantly from a uniform distribution over polynomials in a norm-bounded ball, e.g.) For example, one of our experiments is on the polynomials that arise from spherical code bounds; this provides one example of a “natural” set of polynomials, but there is no single definition of such a distribution. This point should not be critical to our main arguments.

Q1: Utility of $SL(2,\mathbb{R})$ equivariance

While the symmetry group is not crucial for studying the problem, equivariant learning has been helpful from a sample complexity perspective in many other contexts. Since our positivity verification problem is equivariant with respect to the large group $SL(2,\mathbb{R})$, it is natural to try exploiting this structure in the learning pipeline. Please see the paragraph after (1) for an explanation of the precise equivariance property, and please feel free to follow up with further questions if this point remains unclear.

Q2: Clarification on timings

Indeed, the MLP times are for inference, while the Mosek times are full solves. The motivation of this work is to speed up the online determination of nonnegativity, which is possible with just MLP inference. Amortizing the runtime of a traditional solver over many instances is not possible, hence why we compare to the full solve time. For reference, the training time for the MLP was on the order of 90 minutes, which even included many different loss evaluations (e.g. evaluating the loss under random $SL(2,\mathbb{R})$-augmentations).