Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper computes Rademacher complexity estimates for regularised quadratic function classes, and shows that the choice of nuclear norm regularisation makes the complexity to scale with the effective dimension of the covariance (trace / largest eigenvalue) of the underlying data distribution. Numerical experiments are also given to demonstrate this effect and show that Frobenius norm regularisation behaves differently. The results are used to bound the generalisation error of quadratic classifiers.  
main_review: The findings are interesting, albeit the work doesn't seem particularly challenging. The authors plan to extend the analysis to higher order polynomials, which will be an interesting addition. 
  
It is not entirely clear what is the practical implication of the findings so far. Should it be a good idea to use nuclear norm regularisation rather than Frobenius norm in conjunction with quadratic classifiers? (or perhaps more generally?) How was \lambda set in the experiments?

I feel there is a seed of a good idea here albeit the work seems to be in early stages.

The assumption \|x\|_2^2 \ge const E\|x\|_2^2 almost surely seems strange to me. Can the authors justify it? 

I'm not sure how to interpret the experiments. Are we looking for the worst function in the class? Also, in Fig 1 (b) the labels are randomly assigned, but the generalisation gap seems to shrink as d increases?  

The writing quality can be improved in many places. 
- In Proof of Cor 2 it says "both identities in eq. 3" -- but eq(3) is one inequality!
- bottom of p 8: "try to find" sounds vague - indeed, what if the optimiser doesn't find the function we look for?
- top of p 10: what is mean by "an equal regularisation parameter"?

Post rebuttal: 
The authors addressed all clarity issues. 
I don't think the setting of $\lambda=1$ and the setting of this same value for all regularizers is justified - why would this be a good value? I can see that it doesn't change the conclusion of the paper, but still a good justification would help, otherwise this might send the wrong message to practitioners or to beginners in the field.   

On another note, the authors might also be interested in the rank minimising behaviour of the nuclear norm beyond the quadratic classifier, as it was found previously e.g. in matrix completion problems:
Benjamin Recht. A Simpler Approach to Matrix Completion, Journal of Machine Learning Research 12 (2011) 3413-3430.


limitations_and_societal_impact: The authors did not explicitly mention limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper derives generalization bounds using Rademacher complexity for quadratic classifiers, with a nuclear norm constraint on the coefficient matrix. The generalization bound depends on the “intrinsic dimension,” which is a measure of the isotropy of the input distribution, and the largest eigenvalue of the second moment matrix of the distribution. A high-probability computable generalization bound is also given. The authors note that the nuclear norm setting is sensitive to the intrinsic dimension, while the Frobenius norm setting is not. This observation is corroborated by experiments.
main_review: The results are interesting and relevant, with insightful comparison between nuclear norm and Frobenius norm constraints. The results also seem relevant to understanding how neural networks learn from few samples, as explained by the authors.

My main concern is with the style of presentation. Key terms (e.g. isotropic) are defined rather late. Similarly, models are not presented in detail (what exactly is the quadratic classifier?) until quite late.  Concepts are sometimes used without introduction (e.g. the “pixel space” on pg. 1). Please carefully check the order in which you present the content. 

Typos: “triangle inequality” missing the (pg. 4), of vs off (pg. 10), Holder missing accent (pg. 10)

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the generalization ability of quadratic forms under trace norm regularization.
The Rademacher complexity of the trace-norm constrained ball is bounded in dependence on the intrinsic dimension (ID) of the data, it is argued that the bound so obtained improves over existing bounds by a factor of sqrt(ID), and it is concuded, that the bound so obtained shows an advantage for isotropic distributions, thus justifying whitening of the data. Experimental evidence is provided. There is also a section devoted to data-dependent bounds.

main_review: Overall I liked the paper.
The proof of Theorem 1 (the bound on the Rademacher complexity) is elegant and clear and has some interesting ideas, and the conclusions drawn from it are convincing. The comparison to other bounds suffers a bit from the fact that trace-norm-regularization has not been much studied for the classes defined by matrices as quadratic forms, but rather for matrices operating on matrices, so the motivation is different.
The work seems still very relevant, one thinks of the quadratic kernels from the earlier times of kernels in machine learning. The comparison of trace-norm and Frobenius-norm constraints in section 4 is illuminating.

I didn't like the section on computable generalization bounds. For one reason "computable" seems an exaggeration in a paper which consistently avoids explicit constants. Also the proofs use by-now-standard techniques to estimate trace and spectral norm of the second moment matrix from the data. This section does not contribute very much.
Instead the authors could have clarified the connection to the role of intrinsic dimension in neural network learning, alluded to in the introduction. Statements like "The study of quadratic classifiers can serve as an important first step in understanding how neural networks take advantage of the intrinsic dimension to learn with fewer samples" generate a curiosity, which remains frustrated.


limitations_and_societal_impact: adequately adressed
review_title: null

Meta-review: The paper presents an interesting observation on the effect of different norms used 
for regularizing quadratic classifiers. In short, it presents an upper bound on the Rademacher 
averages of quadratic classifiers with bounded nuclear norm that nicely includes effects 
such as the intrinsic dimension of the data measured in terms of norms of the covariance matrix.
While it is not entirely surprising that different regularizing norms may have a different 
dependence on this intrinsic dimensionality, the paper provides solid and interesting results.
On the downside, the wider significance of the considered class of classifiers is at least 
unclear, and the rebuttal phase has not sufficiently resolved this problem. Compared to 
other papers in my badge, I am thus somewhat skeptical in view of impact.
Decision: Accept (Poster)