The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers

Abstract:
It has been recently observed that neural networks, unlike kernel methods, enjoy a reduced sample complexity when the distribution is isotropic (i.e., when the covariance matrix is the identity). We find that this sensitivity to the data distribution is not exclusive to neural networks, and the same phenomenon can be observed on the class of quadratic classifiers (i.e., the sign of a quadratic polynomial) with a nuclear-norm constraint. We demonstrate this by deriving an upper bound on the Rademacher Complexity that depends on two key quantities: (i) the intrinsic dimension, which is a measure of isotropy, and (ii) the largest eigenvalue of the second moment (covariance) matrix of the distribution. Our result improves the dependence on the dimension over the best previously known bound and precisely quantifies the relation between the sample complexity and the level of isotropy of the distribution.

heading: 1 Introduction
text: We revisit the problem of supervised classification using quadratic features of the data. We do so to highlight the influence of properties of data distrbution on the generalization error. Most of the existing results on this error only use a bound on the support of the distribution. By leveraging results from matrix concentration, we show an improved bound that uses more refined properties of the data distribution, like the second moment matrix.
The use of the second moment matrix in the error bound shows that the intrinsic dimension of the data distribution plays an important role. This is of particular interest because it is widely believed that real-world data distributions have nice properties that allow classifiers, namely neural networks, to avoid the worst-case sample complexities predicted by generalization bounds Jiang* et al. (2020).
Indeed, assumptions like the manifold hypothesis, which state that the data lies on lower dimensional embedded manifold, are often made to explain the practical success of some generative methods. A recent paper by Pope et al. (2021) computes estimates of this true dimensionality of common machine learning datasets and shows that they are much lower than the ambient dimension of the pixel space [0, 1]d. It is therefore important that properties of the data distribution, going beyond simple bounds on the support, intervene in the study of generalization.
This influence of intrinsic dimension on generalization has been recently observed in the context of differentiating neural networks and from their kernel approximations, like the neural tangent kernel Jacot et al. (2018) or random feature models Yehudai and Shamir (2019). In particular, Ghorbani et al. (2020) observe that neural networks seem to require fewer samples than kernel methods to learn when the data distribution is isotropic.
We show that a similar phenomenon occurs in the simpler setting of quadratic classifiers, which leads to a better understanding of the causes. An improvement in sample complexity on isotropic data
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
distributions can be proved when comparing nuclear-norm constrained quadratic classifiers and the corresponding kernel method (Frobenius norm constrained classifiers).
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 Du and Lee (2018); Bai and Lee (2020). The nuclear-norm constraint is a natural one to study in this context. Indeed, when applying weight-decay (or `2-regularization) on a single-hidden layer neural network with quadratic activations, the regularization is in effect encouraging a low nuclear norm of the coefficient matrix of the quadratic polynomial.
A better understanding of quadratics is also a worthwhile goal in its own right: complex architectures like those in Jayakumar et al. (2020) use quadratics as building blocks, attention layers Vaswani et al. (2017), which have seen great success in language processing tasks, are multiplicative interactions.
For these reasons, we present theoretical and practical developments of nuclear-norm regularization for quadratic classification. We summarize our contributions as follows
Rademacher complexity bounds. We present a new bound on the Rademacher complexity of quadratic classifiers with a nuclear norm constraint c.f. Theorem 1. It improves upon the previously known bound, implied by the results by Kakade et al. (2012), by up to a square-root factor of the dimension, depending on the distribution of the data c.f. Lemma 4.
As a consequence of our bound, we draw attention to a clear difference between the complexity of nuclear-norm constrained and Frobenius-norm constrained quadratic classifiers. When the input data distribution is nearly-isotropic, the former enjoys a reduced dependency on the dimension. In contrast, the complexity of Frobenius-norm constrained classifiers has the same dependency on the dimension, independently of how isotropic the input data distribution is (Corollary 2).
This observation motivates the use of data whitening pre-processing steps, which are commonly used in practice: such transformation might bring the second-order moment (covariance) matrix of the distribution close to the identity matrix and thus to nearly-isotropicity.
Computable generalization bounds. The refined Rademacher complexity bound that we obtain depends on the often unknown second-order moment of the distribution, rather than simple bounds on the diameter of the support as in (Kakade et al., 2012). Even though useful in theory, it is desirable in practice to obtain bounds that can be computed from a sample. We overcome this difficulty in Theorem 3, where we provide high-probability computable generalization error bounds for nuclear-norm constrained quadratic classifiers.
Experiments. We illustrate our theoretical results on synthetic data. We show how the isotropy of the input distribution plays a major role in the generalization properties of quadratic classifiers. As the dimension increases and the sample size remains proportional to it, we observe a constant generalization gap for the nuclear-norm constrained classifier. In contrast, for SVMs, the gap grows at a predicted √ d rate. In the case of anisotropic distributions, we observe similar performance for both regularization schemes.

heading: 1.1 Related work
text: Kakade et al. (2012) provides generalization error bounds for the more general problem of learning a linear classifier over matrices. An upper bound for quadratic classifiers with a nuclear norm constraint can be derived as a consequence of their results c.f. Corollary 1. To the best of our knowledge, it is the only known bound for the hypothesis class we study, and thus the one we compare to. Our analysis improves the dependency on the dimension. See subsection 2.1 for a technical discussion.
Because of the generality of the results in Kakade et al. (2012), it is only natural that the implied bound in some particular case is not the tightest. We precisely give a step towards tight complexity estimates for classification with quadratic polynomials. We look on our results as relevant, given the simplicity and widespread use of linear learning over features.
Wimalawarne et al. (2016) study linear classifiers over higher-order tensor spaces, using constraints on generalized notions of the nuclear norm. The problem we study is thus a particular case. Generalization error bounds via Rademacher complexity are provided, but they apply only under a highly restrictive assumption: the entries of the tensor are independent standard normal random variables. In contrast we only require a boundedness condition.
Srebro et al. (2005); Srebro and Shraibman (2005) develop the theory of nuclear-norm regularization for matrix completion. Bounds on the Rademacher complexity of the class of matrices with bounded nuclear-norm are obtained in Srebro (2005). However, in this setting matrices are understood as mappings from an index pair to a value, and the generalization error measures how well the missing entries of the target matrix can be predicted. In contrast, in our setting the matrix corresponds to the coefficients of a quadratic polynomial, so the bounds are not comparable.
Pontil and Maurer (2013) study nuclear-norm regularization in the context of multi-task learning (Caruana, 1997). Rademacher complexity bounds are obtained for nuclear-norm constrained multitask classifiers. In this setting, each row of the matrix corresponds to a linear classifier for a different task, and each task corresponds to a different distribution over data-label pairs.
Matrices with bounded trace norm also have been studied by Amit et al. (2007) and Yu et al. (2014) in the related multi-class classification and multi-label learning setting, respectively. Yu et al. (2014) remark essential differences between Rademacher complexity bounds of nuclear- and Frobenius-norm constrained linear classifiers, similar to our conclusion in Corollary 2. In all such problems, however, the setting is not comparable to ours: the matrix acts as a linear mapping of the sample, rather than as a quadratic. Thus, the analysis is not analogous and requires a different set of tools in our case.
The analysis in Yu et al. (2014) is closest in spirit to ours, as their bound also depends on the intrinsic dimension of the distribution, and the largest eigenvalue of the second moment (covariance) matrix. However, we go the extra mile and achieve bounds that can be computed from the sample at hand (Theorem 3), as the true second moment (covariance) matrix is usually unknown.
The papers Du and Lee (2018); Bai and Lee (2020) establish a similar result as ours for a different norm for a non-convex parametrization of quadratic polynomials. The reparametrization consits of writing the coefficient matrix as a sum of m rank 1 matrices which facilitates analogies to neural networks. It is straighforward to see that their studied norm ‖ · ‖2,4 is, in essence, a way of upper bounding the nuclear-norm by using the reparametrization.

heading: 2 Rademacher complexity bounds
text: Notation. Throughout this section x ∈ Rd is a random variable with distribution µ, and Xn = (x1, . . .xn) is a sample of i.i.d. random variables drawn from µ. The second moment matrix of µ is denoted by Σ := E[xxT ]. Note that, for centered (mean zero) random variables, this notion coincides with the covariance matrix. For a square symmetric matrix A we denote with ‖A‖F , ‖A‖2 and ‖A‖tr its Frobenius-norm, spectral-norm and nuclear-norm, respectively. The notation . stands for less than or equal, but hides constants independent of the dimension or number of samples. The notation x ≈ y means that there exist constants c, C > 0 such that cy ≤ x ≤ Cy. We consider a binary classifier obtained from a homogeneous quadratic polynomial. Such a function can be parametrized as fA(x) := xTAx, where A is a square symmetric matrix containing the coefficients of the monomials. In order to control the complexity of a quadratic polynomial we choose a matrix norm ‖·‖ and consider only elements in a constrained set:
Q‖·‖,λ := {fA(x) = xTAx : ‖A‖ ≤ λ}, Q‖·‖ := Q‖·‖,1 (1)
We quantify the complexity of such function classes using the classical notion of Rademacher complexity. It is well known that high probability generalization error bounds can be obtained in terms of this quantity (Koltchinskii and Panchenko, 2002; Bartlett and Mendelson, 2003). For this reason, we focus only on deriving upper bounds on this complexity measure. Definition 1 (Rademacher complexity). Let σ be uniformly distributed over the set {−1, 1}n and let Xn = [x1, . . . ,xn] ⊆ Rd be an i.i.d. sample drawn according to µ. For a class of functions F : Rd → R we define the empirical Rademacher complexity and the Rademacher complexity (with respect to µ) of F , respectively, as:
R̂(F ;Xn) := Eσ [ sup f∈F 1 n n∑ i=1 σif(xi) ] , Rn,µ(F) = E[R̂(F ;Xn)] (2)
Our bounds depend on the distribution through its intrinsic dimension (Tropp, 2015, Section 7), which measures how much the probability density concentrates near low-dimensional subspaces.
Definition 2. The intrinsic dimension of a distribution µ is the ratio 1 ≤ r(Σ) := tr(Σ)/‖Σ‖2 ≤ d.
We are now ready to state our main results about the Rademacher complexity of homogeneous quadratic polynomials with nuclear norm constraint:
Theorem 1. Let x ∈ Rd such that ‖x‖22 . E‖x‖22 almost surely and suppose n & r(Σ) log d. It holds that Rn,µ(Q‖·‖tr,λ) . λ √ r(Σ) log d
n ‖Σ‖2 (3)
Now we proceed to prove Theorem 1. First, we only focus on the class Q‖·‖ corresponding to the unit nuclear-norm ball. This is justified by well-known technical result Lemma 1, whose proof is included for completeness in Appendix D.
Lemma 1. Rn,µ(Q‖·‖,λ) ≤ λRn,µ(Q‖·‖).
The backbone of Theorem 1 is Lemma 3, which relates the Rademacher complexity of a class of functions to concentration of empirical means to expectations with respect to the dual norm. It makes use of the technical Lemma 2, whose proof is included for completeness in Appendix B.
Lemma 2. For all even n ∈ N, it holds that ∑n k=0|2k − n| ( n k ) < √ n2n
Lemma 3. Denote by ‖·‖∗ the dual norm of ‖·‖. DefineMk := E ‖Σk − Σ‖∗ , Σk := 1 k ∑k i=1 xix T i The Rademacher complexity of the class Q‖·‖ can be upper bounded as follows:
Rn,µ(Q‖·‖) ≤ 1
n2n−1 n∑ k=1 k ( n k ) Mk + ‖Σ‖∗√ n
(4)
Proof. We first compute an upper bound on the empirical Rademacher complexity. The result will follow after taking expectation of the bound over the sample Xn = [x1, . . . ,xn]. By definition of the dual norm, using the basic algebraic identity xTAx = 〈A,xxT 〉 we have
R̂(Q‖·‖;Xn) = 1
n Eσ sup ‖A‖≤1
〈 A,
n∑ i=1 σixix T i
〉 = 1
n Eσ ∥∥∥∥∥ n∑ i=1 σixix T i ∥∥∥∥∥ ∗
(5)
We now compute the expectation in eq. 5. There is a bijection between the possible configurations of the Rademacher variable σ ∈ {−1, 1}n and the power set of [n], namely σ 7→ {i ∈ [n] : σi = 1}. This allows us to write eq. 5 as:
R̂(Q‖·‖;Xn) = 1
n Eσ ∥∥∥∥∥ n∑ i=1 σixix T i ∥∥∥∥∥ ∗ = 1 n2n ∑ B⊆[n] ∥∥∥∥∥∑ i∈B xix T i − ∑ i∈Bc xix T i ∥∥∥∥∥ ∗︸ ︷︷ ︸
:=DB
(6)
Let ΣB := |B|−1 ∑ i∈B xix T i . Using the triangle inequality, we can bound DB as:
DB ≤|B|‖ΣB − Σ‖∗ + ||B| − |Bc||‖Σ‖∗ + |Bc|‖ΣBc − Σ‖∗ (7)
To obtain a bound on the Rademacher complexity, we need now sum over B ⊆ [n] the terms on the right hand side of eq. 7, and take expectation with respect to the sample Xn. First, we will deal with the sum of the second term in eq. 7, as it is actually a deterministic value. We can sum over B ⊆ [n] by grouping together subsets B of the same cardinality |B| = k. We obtain:
∑ B⊆[n] ||B| − |Bc||‖Σ‖∗ = n∑ k=0 ( n k ) |2k − n|‖Σ‖∗ ≤ √ n2n‖Σ‖∗ (8)
where the last inequality follows from Lemma 2.
Finally, we compute the expectation of the sum over B ⊆ [n] of the first and third term in eq. 7. After taking the sum, both terms become equal by symmetry. It suffices to bound the sum of the first term.
Notice that because the variables x1, . . . ,xn are i.i.d., the distribution of ΣB depends only on the size of the set B. Using the same counting argument as in eq. 8 we arrive at:
E ∑ B⊆[n] |B|‖ΣB − Σ‖∗ = ∑ B⊆[n] |B|E‖ΣB − Σ‖∗
= n∑ k=1 k ( n k ) E‖Σk − Σ‖∗︸ ︷︷ ︸
=Mk
(9)
Combining the bounds in eq. 8 and eq. 9, and dividing by n2n we obtain the result.
Note that the proof of Lemma 3 follows from technical arguments but the final result is not to be found in the literature, in this form or a similar one. In particular, it is completely unrelated to the result by Vershynin (2011) with which it only shares the fairly trivial split of Rademacher random variables preceding eq. 6.
Lemma 3 provides a way to derive Rademacher complexity bounds from a bound on the expected deviations Mk defined in Lemma 3, and might be of independent interest. In the particular case where the norm in consideration is the nuclear-norm, this lemma will be used to establish Theorem 1 as a simple application of a well-known non-asymptotic bound for the convergence of the empirical second moment (covariance) matrix to the true second moment (covariance) matrix.
Proof of Theorem 1. Recall that the dual norm of the nuclear-norm is the spectral-norm. The value of Mk in Lemma 3 measures the average deviation of the empirical second moment matrix Σk to the true Σ, in spectral-norm. Our assumption that ‖x‖22 . E‖x‖22 almost surely, implies the concentration result (Vershynin, 2018, Theorem 5.6.1), which concludes that
Mk .
(√ r(Σ) log d
k + r(Σ) log d k
) ‖Σ‖2 (10)
Plug this in eq. 4, and use the bound √ k ≤ √ n for k ≤ n to obtain the inequality
Rn,µ(Q‖·‖tr) .
(√ r(Σ) log d
n + r(Σ) log d n
) ‖Σ‖2 (11)
By assumption n & r(Σ) log d, so that the first term in eq. 11 is the largest. The second term is of smaller order and thus ends up hidden by the notation .. We conclude
Rn,µ(Q‖·‖tr) . √ r(Σ) log d
n ‖Σ‖2 (12)
Invoking Lemma 1 we obtain the desired result.

heading: 2.1 Improvement upon previous work
text: We now show how our derived upper bound improves over the current best known bound by Kakade et al. (2012). To the best of our knowledge, the Rademacher complexity of quadratic classifiers with a nuclear-norm constraint has not been previously analyzed in a direct manner, as we do. Instead, the only existing bound (Corollary 1) appears as a particular case of Theorem 2.
Theorem 2 (Kakade et al. (2012) page 1876). Let
G‖·‖tr,λ := {gA(X) := 〈A,X〉 : ‖A‖tr ≤ λ} (13)
be the class of nuclear-norm constrained linear functions over square d × d matrices. Let µ be a distribution supported on X ⊆ Rd×d. It holds that:
Rn,µ(G‖·‖tr,λ) . λX∞
√ log d
n , X∞ = sup X∈X ‖X‖2
Corollary 1. Let x ∈ X ⊆ Rd be a random variable with distribution µ. The Rademacher complexity of the class in eq. 1 can be bounded as
Rn,µ(Q‖·‖tr,λ) . λx∞
√ log d
n , x∞ := sup x∈X ‖x‖22
Corollary 1 is a consequence of the fact that a function of the form fA(x) = xTAx can be written as a linear classifier on matrices, gA(X) = 〈A,X〉, where X = xxT . In this case, it is easy to see that X∞ = supx∈X ‖xxT ‖ = supx∈X ‖x‖22 =: x∞. The only difference with our bound in Theorem 1 is that the term x∞ appears in place of √ r(Σ)‖Σ‖2.
In order to understand the difference between the two bounds, we turn to the analysis of the quotient between the bound in Corollary 1 and our bound Theorem 1. In Lemma 4 we show that this quotient can differ drastically, depending on the distribution.
Remark 1. The variablesX∞ and x∞ defined respectively in Theorem 2 and Corollary 1 respectively, correspond to the supremum of a random variable. Because the Rademacher complexity arises as an expectation, it is clear that such quantities can be (and should be) replaced by the closely related measure-theoretic notion of essential supremum (denoted by ess sup): the least upper bound that holds almost surely. In this way the bounds are only tighter, and we believe this was the true intended definition by Kakade et al. (2012). In the following we will compare our bound to this tighter, modified bound.
Lemma 4. Let x be a random variable supported on a set X ⊆ Rd, and such that ‖x‖22 . E‖x‖22 almost surely, then: √
r(Σ) . ess supx∈X ‖x‖22√ r(Σ)‖Σ‖2 . √ r(Σ) (14)
Proof. By definition of essential supremum it holds that E‖x‖22 ≤ ess supx∈X ‖x‖22. Further, our assumption clearly implies that ess supx∈X ‖x‖22 . E‖x‖22. The identity E‖x‖22 = tr(Σ) and Definition 2 imply the result.
In summary, Lemma 4 shows that the baseline bound of Kakade et al. (2012) is larger by a square-root factor of the intrinsic dimension of the distribution (modulo global constants), compared to our bound in Theorem 1. Such factor ranges between 1 and the square root of the ambient dimension.
Precisely, when the intrinsic dimension of the distribution is equal to the ambient dimension, our bound enjoys a reduced dimension complexity. This is the case, for example, for isotropic distributions i.e., distributions such that their second moment matrix is the identity matrix. The dependency of the Rademacher complexity on the intrinsic dimension of the distribution is not revealed by the more general proof of Theorem 2 (Kakade et al., 2012).
Remark 2. The logarithmic term in Theorem 1 can be removed under the more restrictive dimensionindependent L-subgaussianity assumption (Mendelson and Zhivotovskiy, 2018).

heading: 3 Computable Generalization error bounds
text: Let y = (y1, . . . , yn) ∈ {−1, 1}n be the labels associated with the data sample, and let
L(f) := P{sign(f(x)) 6= y} (15)
L̂(f ;Xn) := 1
n n∑ i=1 min(1,max(0, 1− yif(xi))) (16)
be the missclassification probability and the empirical margin loss of the classifier f , respectively. It is well-known (Mohri et al., 2018, Theorem 5.8.) that with probability at least 1 − δ, for all f ∈ Q‖·‖tr,λ:
L(f) . L̂(f ;Xn) +Rn,µ(Q‖·‖tr,λ) + √ log 1δ 2n
(17)
This bound, together with the results in section 2, allow high probability uniform bounds on the misclassification error of a nuclear-norm constrained quadratic classifier.
However, the bound derived in this way is not actually computable: the Rademacher complexity bound in Theorem 1 depends on the second moment matrix of the distribution, which is unknown in practical applications. In the rest of this section we will overcome this drawback.
Rewriting our bound in eq. 3 as: Rn,µ(Q‖·‖tr) . √ tr Σ‖Σ‖2 log d n
(18)
we observe that we need to estimate the trace and the largest eigenvalue of the second order moment matrix. Our hope is that the empirical estimators, based on the empirical second moment matrix Σn, will provide a good approximation of the true values.
We arrive at the following high probability bound on the Rademacher complexity in eq. 18, which is readily computable from samples and a bound on the diameter of the support of the distribution:
Theorem 3. Suppose that ‖x‖22 . E‖x‖22 almost surely. This implies that ‖x‖22 ≤ B for some B > 0. Define
K1 := log d n− √ nd(log d+ log 1δ )
K2 :=
√ 2 log 1δ log d
2n( √ n− √ d(log d+ log 1δ ))
(19)
Let δ > 0 and fA ∈ Q‖·‖tr,λ. Provided n & d(log d + log 1δ ), with probability at least 1 − 3δ it holds that Rn,µ(Q‖·‖tr) . √ K1 tr Σn‖Σn‖2 +BK2‖Σn‖2︸ ︷︷ ︸
:=M(n,d,δ)
(20)
Moreover, with probability at least 1− 4δ, uniformly for all fA ∈ Q‖·‖tr,λ it holds that
L(fA) . L̂(fA;Xn) + λM(n, d, δ) + √ log 1δ 2n
(21)
Proof. See Appendix C.

heading: 4 Frobenius vs Nuclear-norm constraint
text: Perhaps the most common way to use quadratic features is to use a support vector machine (SVM) with the quadratic kernel K(x,y) := 〈x,y〉2. Lemma 5, which is folklore in the kernel methods literature, precisely states that the RKHS norm constraint is equivalent to a Frobenius-norm constraint on the matrix of coefficients A of the underlying quadratic polynomial. Its proof is included for completeness in Appendix D.
Lemma 5. Let H be the Reproducing Kernel Hilbert Space associated to the symmetric, positive semidefinite polynomial kernel K(x,y) = 〈x,y〉2, and denote its induced norm by ‖·‖H. Then f ∈ H if and only if there exists a symmetric matrix A such that f(x) = xTAx and ‖f‖H = ‖A‖F .
For this reason, we now turn to compare the qualities of nuclear-norm and Frobenius-norm constrained quadratic classifiers. As a consequence of our derived bound (eq. 3), we uncover a fundamental difference between both regularization schemes (Corollary 2): as the dimension increases, the growth rate of the complexity of nuclear-norm constrained quadratics strongly depends on the intrinsic dimension of the distribution. In contrast, that of Frobenius-norm constrained quadratics is insensitive to it.
In order to derive this rate, we need a way to argue about distributions across different dimensions and express our generalization bounds only in terms of dimension and number of samples. To this end, we introduce a natural boundedness assumption on the data distribution:
Assumption 1. ‖x‖22 ≈ d almost surely.
We now argue why this is a natural scaling order for this norm: if the entries of the random vector x are upper bounded as |xi| ≤ αmax and their average magnitude is lower bounded as 0 < αmin ≤ 1d ∑d i=1 |xi|. Then
αmin √ d ≤ 1√
d ‖x‖1 ≤ ‖x‖2 ≤
√ d‖x‖∞ ≤ √ dαmax,
and hence, Assumption 1 is satisfied. If we think about distributions of pixel (natural image) data of increasing resolution, we indeed have an upper bound on the intensity of each pixel. A lower bounded average pixel intensity only means that images are not arbitrarily dark, which often holds in practice. Any distribution of similar characteristics (e.g., sensor data) will probably satisfy our assumption.
We also introduce a growth condition on the intrinsic dimension, which states that r(Σ) ≈ ds for some 0 ≤ s ≤ 1. Rather than being an assumption, this condition helps to understand how our bounds change as the distribution falls between the two possible extremes given by the bound 1 ≤ r(Σ) ≤ d. Traditionally, distributions that attain the lower bound (s = 0, r(Σ) = 1) or the upper bound (s = 1, r(Σ) = d) are called anisotropic or isotropic, respectively.
Corollary 2. Let Assumption 1 hold, and suppose that r(Σ) ≈ ds for some s ∈ [0, 1] and n ≥ r(Σ) log d. Then
Rn,µ(Q‖·‖tr,λ) . λ d1−s/2 √ log d√
n (22)
Rn,µ(Q‖·‖F ,λ) ≈ λ d√ n
(23)
Proof. For the first inequality, note that ‖x‖22 ≈ d implies that tr Σ = E‖x‖22 ≈ d. Thus, tr Σ‖Σ‖2 = r(Σ) ≈ ds =⇒ ‖Σ‖2 ≈ d1−s Using these two identities in the inequality eq. 3 we obtain the first result.
For the second identity, Lemma 5 implies the class of Frobenius-norm constrained quadratic functions is equal to the ball of radius λ in the RKHS corresponding to the quadratic kernel. By Mohri et al. (2018, Theorem 5.5)1, we have that
R̂(Q‖·‖F ,λ;Xn) ≈ λ
n √√√√ n∑ i=1 K(xi,xi) = λ n √√√√ n∑ i=1 ‖xi‖42 ≈ λd√ n
(24)
where the final inequality comes from our assumption that ‖x‖22 ≈ d. Taking expectation with respect to the sample we obtain thatRn,µ(Q‖·‖F ,λ) ≈ λ d√n .
Corollary 2 then states that the nuclear norm constraint adapts to the intrinsic dimension of the distribution. In the worst case (s = 0) it grows linearly2 with dimension; In the best case (s = 1) it is much slower, and grows as the square root of the dimension.
Note that we can bring any distribution to approximate isotropic position, given a good approximation of Σ. Hence, it makes sense to expect performance gains if we perform such normalization procedure before training nuclear-norm constrained quadratic classifiers. In section 5 we will put to test this claim in synthetic datasets, to illustrate the theory.

heading: 5 Experiments
text: The results derived in Corollary 2 pertain to the worst case generalization gap. This worst case gap is not guaranteed to be attained by the function found through empirical loss minimization. Therefore, in order to better test our results, we try to find the function that attains this worst case generalization gap.
1See remarks following the proof 2for simplicity we ignore the logarithmic factor
The experiment we propose to illustrate the difference in intrinsic dimension sensitivity consists of computing the quadratic function f such that E[`(f(x, y))] − 1n ∑n i=1 `(f(xi, yi)) is maximized. The expectation in the term above being generally difficult to compute in closed form, we replace the objective by an empirical estimate
1
ntest ntest∑ k=1 `(f(xk, yk))− 1 ntrain ntrain∑ i=1 `(f(xi, yi)).
We expect this quantity to more faithfully track the upperbounds derived in Corollary 2. Indeed, what we evaluate here is the capacity of the class constraining f to attain a low loss on ntrain samples while attaining a very high one on ntest samples.
To illustrate that Frobenius and nuclear norm constrained classifiers exhibit different behaviors depending on the intrinsic dimension of the data, we compute the result of the maximization procedure on isotropic distributions on one hand and on anisotropic on the other. We set the radius λ = 1 for both Nuclear and Frobenius norm constrained classifiers. We then observe the evolution of these quantities as the dimension increases.
Generating Isotropic Data To generate isotropic data satisfying our assumptions, we sample a standard Gaussian random vector in Rd and normalize to obtain i.i.d samples xi that are uniformly distributed on the sphere of radius √ d.
Generating Anistropic Data To generate anisotropic data, we first generate isotropic data features by uniformly sampling points on the sphere of radius √ d as described previously. We then transform the samples into more anisotropic ones by multiplying each feature vector coordinate-wise by a vector α(s) defined as α(s)i = Cs 1 is , i = 1, . . . , d, for s ∈ [0, 1] where Cs is chosen such that
‖α(s)‖2 = √ d. That, way, s = 0 induces no change on the data, since α(1) = [1, 1, . . . , 1]T , and larger s implies that the data will be more squashed along the first few coordinates, inducing smaller intrinsic dimension. This transform does not affect the norm of the vectors since E[‖α(s) × xi‖2] =∑d k=1(α (s) k ) 2E[[xi]2k] = ∑d k=1(α (s) k ) 2 = √ d
Generating the labels We test two approaches for generating the labels : (1) We generate a random matrix A with i.i.d standard Gaussian coordinates and set yi = sgn(x>i Axi), (2) We set the labels randomly with yi ∼ Bern(0.5).
The results We observe that the maximal gaps do indeed evolve as the theory predicts. We indeed have the nuclear norm constrained classifier on isotropic data not exhibiting the same growth as the others, indicating that the maximal generalization gap for nuclear norm constrained classifiers is indeed sensitive to isotropy. Additional experiments and details are provided in Appendix E.

heading: 6 Discussion
text: Our result shows that given a fixed regularization parameter λ, nuclear-norm constrained classifiers can take advantage of the properties of the data distribution to shave off a √ d factor from the Rademacher complexity, whereas Frobenius-norm constrained ones cannot.
We rely on two main elements to show this : Hölder’s inequality in equation (5) which introduces the dual norms and a bound on the expected deviations Mk, which quantifies how fast the empirical moment estimate converges to the true moment matrix. Both these elements admit extensions to higher order tensors which corresponds to polynomials of higher degree.
The extension of Hölder’s inequality is immediate. The main difficulty of extending our result lies in establishing the convergence rate of the deviations E[‖ 1k ∑k i=1 x ⊗m i −M‖op], whereM = E[x⊗m] is the tensor of m-th moments. For matrices, the rate is obtained through the matrix Bernstein inequality. Therefore, an extension can be derived by using the recently proved tensor Bernstein inequality in Luo et al. (2019) obtained by flattening the tensors and recycling the results for matrices.

heading: Acknowledgements
text: This work is funded (in part) through a PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 725594 - time-data). This project was sponsored by the Department of the Navy, Office of Naval Research (ONR) under a grant number N62909-17-1-2111. Research was sponsored by the Army Research Office and was accomplished under Grant Number W911NF-19-1-0404. This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021_178865 / 1.

Review summaries:
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.  

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. 

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.