Thank you for your review. We appreciate your feedback and will address your comments in detail.

In pratical situations, how to set the hyperparameters such as L' and S is not clear for me. Do you have any ideas about this?

Thank you for your question. Our paper addresses this from two perspectives, one theoretical and the other one practical. From the theoretical perspective, we can compute for each $L'$ with Theorem 4.5 a "budget" in the form of a maximal number of monomials $S$, maximal degree $d$ and the other hyperparameters of our pipeline. This yields a provably lower spectral complexity and thus a better bound. From the practical perspective, our experiments indicate that we can remove about 40-50% of all convolutional layers before we observe a significant drop in performance. With the choice of $S$ you raise another interesting question, which we already addressed in the appendix (cf. Figure 6). There we analyse the monomial count ($S$). We found that it is not advisable to choose $S$ to be significantly lower than the latent dimensionality, otherwise we observe a large performance drop. We hope that this answers your question - if not, please let us know.

In section 4.2, the authors investigate the theoretical analysis of generalization error based on the existing results regarding spectral complexity. However, how the geometric aspect of the proposed method helps alleviating the generalization error is not clear for me. Indeed, the bound of $\kappa$ dependes on $2^d$, which becomes large if $d$ is large.

Yes, you are right, the bound of $\kappa$ can become very loose if $d$ is large. However, in practice, we have always found it entirely sufficient to use values of $d$ not larger than $5$. To be more precise, we enforce the bound of $d$ as follows: we let the OAVI algorithm run until it terminates, and then we only take terms with maximum degree $d$. Despite setting $d$ to $5$, we never actually removed any terms from the ideal. In our computational setting, enforcing $d=5$ does in consequence not lead to any performance loss.

Although the authors empirically investigate the accuracy of the proposed method, I think investigating how the proposed method captures the underlying manifold for each class would be interesting. Is it possible to visualize or quantify how the learned polynomials separate the classes of the input data?

We agree that it would be very interesting to investigate how the learned polynomials capture the underlying manifold. Since visualizations in this high-dimensional setting are generally not feasible, we provide the following alternative to see how two classes in particular are being separated. For this, one can choose for each of the class a vanishing polynomial according to our scoring function, say $p_1$ and $p_2$. Then, a simple way to visualize how $p_1$ and $p_2$ separate classes is by using a scatter plot with $x$-axis the absolute value of $p_1$ and the $y$-axis of $p_2$. We provide such a scatter plot here, showing how a training batch is becoming linearly separable: https://imgur.com/o3VlqZl

As for a quantification of separability, this was the reason we introduced our scoring function. It essentially measures separability in the following sense: If the score is of the same order as the vanishing hyperparameter $\psi$, then a polynomial is not only vanishing on its own class but also on other classes. If the score is higher then $\psi$ then this indicates that the polynomial is not as approximately vanishing on other classes. Therefore the score introduced in line 195-197 in the second column is a direct way to quantify how well the learned polynomials separate the data.

Thank you again for your review, we hope to have addressed your concerns. If you have any further questions, please let us know.

Thank you for your review, we appreciate the thorough feedback. Let us address your comments in detail.

However, the evaluation is performed only on the CIFAR dataset. It would be better if the authors could also include other commonly used benchmarks for image classification.

In general, we agree that it would be good to include more benchmarks, albeit this was not the main focus of our work. Scaling vanishing ideal algorithms to larger datasets remains an open problem and is an active area of research [Wirth et al., 2023], our work is a step in this direction, with multiple contributions to that end. However, to directly address your concern, we have run preliminary experiments on TinyImageNet using ResNet-50. We observe that the performance is comparable to the CIFAR-100 and CIFAR-10 experiments, indicating that the method works for larger datasets. We will add these results to the paper and run further experiments on image classification benchmarks for the camera-ready version of the paper. Please find the results here https://imgur.com/a/Beh0DN7.

The only issue is that there seem to be no direct comparison between VI-Net and the base model. For example, under what condition does , i.e. VI-Net has a lower spectral complexity?

The main motivation for using the spectral complexity framework is exactly that it allows for comparison of generalization bounds of different neural network architectures and does more than simply providing a learning guarantee. We can employ Theorem 4.5 to derive for each layer $L'$ a bound on the norms of the newly introduced parameters that is strictly lower than that of the baseline network. This provides a theoretical justification for the use of VI-Net.

Example: suppose we remove the last 3 layers in a pretrained NN. We can compute the spectral norms of their weight matrices $W_1, W_2, W_3$ and compute the product of these terms, i.e., $\prod_{i = 1}^3 \|W_i\|_2$.

Similarly, we can compute $\sum_{i = 1}^3\|W_i^T\|_{2,1}^{-2/3}\|W_i\|_2^{-2/3}$ explicitly. Next, we can choose the number of monomial terms $S$, the number of polynomials $N$, the highest degree $d$, the bound on the norm of the coefficient vectors of the polynomials $\tau$ (Note that these are all hyperparamters of our algorithm pipeline).

If we have further bounds $\lambda_1, \lambda_2$ (cf. Theorem 4.5) on the norms of the final linear weight matrix (either by explicit constraints or implicit regularization), then we can always ensure that

• $2^dd\tau \lambda_1 \sqrt{NS} \leq \prod_{i = 1}^3 \|W_i\|_2$

and

• $2^{2d/3}S^{2/3}+ N^{2/3}S^{1/3} + \lambda_2^{2/3} \leq \sum_{i = 1}^3\|W_i^T\|_{2,1}^{-2/3}\|W_i\|_2^{-2/3}$.

Thus, the spectral complexity of VI-Net is lower compared to the original baseline NN by Theorem 4.5.

The codebase in the supplementary material seems not runnable.

We apologize, this was an oversight on our side while anonymizing the code. We have now ensured that all necessary files are included in the repository, and you should be able to run the code without any problems. If the Area Chair permits, we would be happy to share the complete codebase with you (currently only links to images are allowed).

Also, a dedicated section to related works would be helpful.

We are fairly confident to have included all relevant works with respect to vanishing ideal algorithms, but we appreciate the suggestion of adding a dedicated related work section. We think this will improve the presentation of our work and will add this section to the revision of the paper as soon as possible. Thank you for your suggestion.

Can we apply the methodology of VI-Net to regression tasks?

This is an interesting idea. Indeed, one can apply the standard approach of discretizing the regression problem transforming it into a classification problem (i.e. binning numerical outputs). Do you have any other suggestions? We believe this could be an interesting application and thank the reviewer for this idea.

Moreover, apart from building new models for prediction as you have done in this paper, can we use vanishing ideal algorithms to analyze the structure of the latent manifold itself and provide some kind of interpretability?

We do observe a high correlation between the intrinsic dimensionality of the data and the complexity of the constructed generators (cf. Figure 12). This aligns well with the findings in the broader literature and we believe that this provides insights about the manifold, although relatively hard to interpret.

L201, 202, 304, 285: [...]

Thank you, we fixed the typos and notational issues.

L323: What does $s \in \mathcal{O}(S)$ mean?

The size of the intermediate weight matrix scales linearly with the number of monomials.

L392: Does elapsed time in Table 1 refer to the running time of the vanishing ideal algorithm?

Yes.

Thanks again for your review, we hope to have addressed your concerns and questions. If you have any further remarks, please let us know.

Thank you for your thorough and insightful comments. We have grouped related concerns and clarifications below and revised our paper accordingly.

Overall Clarifications and Algebraic Geometry Context

We used the manifold hypothesis to motivate our work, but we agree that currently, some of the wordings are not entirely mathematically precise. Let us make a few clarifications:

in some theoretical senses "almost all" manifolds fail to be algebraic

In line 42, we cited [Nash, 1952] to reference Tognoli's Theorem that every compact smooth manifold is diffeomorphic to a nonsingular algebraic set. We revised the wording to clarify that some manifolds may not be described by polynomials.

the zero set of the vanishing ideal will be super set of the original manifold.

Please note that we in lines 162-167 we explicitly state that "recovering [the underlying manifold] $U_k$ exactly from a finite sample is impossible without structural information, as $U_k$ could range from being as minimal as $Z_k$ to as broad as $\mathbb{R}^n$" and provide further context in section 2.3.

"while not necessarily linearly separable."

We agree and will modify the statement accordingly. Thanks!

the last paragraph of section 2.1 effectively assumes that the $Z_k$ are pairwise disjoint

Correct, we implicitly state this in line 80-82, but will make it more explicit here.

Experimental Evaluation and Baselines

Linear Probing:

First of all, we agree that Linear Probing should be mentioned earlier in the paper and will revise the manuscript to make this more clear. Thank you for pointing out that this is not easily accessible. Secondly, we understand the confusion regarding the accuracy drop in Fig. 3, whose content was poorly communicated from our side. At 0% removed, we removed 0% of convolutional layers, but still remove the avg.-pooling and linear classifier (lines 332-334, despite badly worded), which may result in a performance drop. We make this more clear to not leave the reader behind to why "0% removal" actually does something. Last but not least, we retuned the hyperparams of the linear probing baseline, improving its performance (https://imgur.com/a/SOpcrEJ). In general, the accuracy drop aligns with the paper you mentioned, reporting a 6% performance drop when using a linear head after the last convolution - which is a non-insignificant drop (cf. Figure 4 in arxiv.org/abs/1610.01644). Now, while VI-Net still outperforms, both methods perform similarly when removing the trailing convolutional layers.

We similarly observe the phenomenon that later layers lead to simpler, sometimes linear, polynomials (cf. Figure 11), aligning with the finding that classes become increasingly linearly separable in later layers; the neural collapse phenomenon is further supported by the good performance of the linear probes. VI-Nets could be seen as a natural extension of linear probing. Could you elaborate on what kind of additional baseline you would like to see?

Further experiments:

To broaden our experimental evaluation, we added TinyImageNet experiments (https://imgur.com/a/Beh0DN7). Further, we conducted additional experiments measuring excess risk to support our hypothesis (please cf. our response to reviewer Gw8X).

We will add the evaluation of ResNet-18 on CIFAR-100 to properly contextualize the throughput improvements, however noting the following: While VI-Net's speedup might not match quantization and hardware optimization, we still observed a notable speedup despite non-optimized hardware, indicating the usefulness of the found generators in describing data manifolds.

Remarks regarding theory

We do agree that not every VI-Net has a lower spectral complexity. Theorem 4.5 allows to choose the hyperparameters of our pipeline such that the bound we have on the newly added terms is lower than what can be measured from the baseline NN (see the answer we provided to reviewer 9he7 on the question on when VI-Net has a lower spectral complexity).

Further, you are correct that the baselines can be analyzed using the same spectral complexity framework. This enables us to compare the spectral complexities of the baseline NN, VI-Net, and linear probing or a shallow wide NN within a unified framework. We think this is a strength of our work.

Other remarks

Fig 12: the number of generators and the dimension of the variety are anti-correlated.

We think this is a result of the approximate VI algorithms. If the underlying data manifold has lower dimension (e.g. a line), fewer monomials are needed to construct polynomials that approximately approximately vanish on the sample.

• We fixed the typos and will include your suggestions, thanks.
• Lem. 4.4: The $d_i$ are the degrees of the InEx activation functions.
• Yes, in Tab. 1 that is the elapsed time to compute the generators.

We hope to have addressed your concerns, please let us know if further clarification is needed.

Thank you for your thoughtful review and for acknowledging the contributions of our work.

Those "learning guarantees" are usually vavous bounds, and thus, an improved upper bound on something may or may not lead to improved performance.

We agree that these bounds are often vacuous. In that sense, we agree that improved upper bounds do not necessarily imply improved performance; thank you for that remark, we will make this more clear in the paper. Our main theoretical contribution is embedding VI-Nets into the established framework of Spectral complexity, with our main theorem providing a theoretical basis for selecting hyperparameters.

As mentioned, this manuscript makes novel contributions to a well-researched area and thus naturally lack some "essential references"

Thank you for providing these references. We believe the provide valuable context and will add them to the paper.

to say something on the structure of the latent manifolds. See one suggestion below, perhaps for a future manuscript.

We also believe this is an interesting future direction of our work. Having constructed these polynomials, we are now able to use the entire toolbox of computational algebra to analyse our found structures. We do believe our work is already quite dense and leave these useful applications to future work - we will address the individual suggestions below!

• Using a fixed monomials budget what is the resulting accuracy?
• Aiming for a fixed target accuracy (e.g., 90%), how many monomials are needed at each layer?

We ran experiments on CIFAR100, testing monomial counts from 50, 100, and increasing by 100, noting their maximal degree. We limit ourselves to the following sparsities, as higher sparsity results in reaching less than 70% accuracy.

We observe that deeper layers need fewer and lower-degree monomials. Deeper layers achieve higher accuracy with a fixed monomial count, but adding more monomials eventually stops improving performance.

Can you provide some analysis on the effect of the maximal degree (keeping the number of monomials fixed)? Are you certain you need to "limit the maximal degree to avoid overfitting"? Assuming the number of monomials is fixed, I'm not sure about that.

Given that tanh-rescaling ensures that the output lies in the unit hypercube, a high degree polynomial with a fixed number of monomials could overfit/vanish on the dataset. However, fixing the number of monomials also has a regularizing effect (cf. Tables below). Our learning guarantee in Theorem 4.5 includes both the highest degree $d$ and the number of monomials $S$, indicating both are relevant. But we agree that our statement is a bit vague, in practice we chose $d = 5$ as maximal degree mainly because we observed that the algorithms never constructed polynomials of degree higher than $5$.

Can you demonstrate a clear benefit of the fact that "the spectral norm of the VI-Net is provably lower than that of the base NN"?

The lower spectral norm of the VI-Net means it might generalize better, resulting in a smaller difference between training and testing errors. For example, below, we see that the VI-Net has a smaller gap between train and test errors in almost all configurations compared to the base neural network.

Baseline (CIFAR-100, ResNet-34) = 1.12

For the experiment you suggested, one can analyse the impact of the number of monomials $S$ on the generalization gap. Fewer monomials typically lead to a smaller generalization gap.

Baseline (CIFAR-100, ResNet-34) = 25.25

Can you clarify which tricks are essential for the results and which just improve your running time slightly?

Tanh-rescaling ensures convergence. Stochastic algorithms speed up computations the most, while lower precision arithmetic offers mainly memory benefits.

We hope to have addressed your concerns. If you have any further questions, please let us know.