The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers
Authors: Fabian Latorre
Leello Tadesse Dadi
Paul Rolland
Volkan Cevher
Venue: NeurIPS 2021 Poster (2021)
Keywords: intrinsic dimension
generalization
rademacher complexity
statistical learning theory

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.

The Effect of the Intrinsic Dimension on the Generalization of Quadratic Classifiers
Fabian Latorre, Leello Dadi, Paul Rolland and Volkan Cevher Laboratory for Information and Inference Systems, EPFL, Switzerland. {first). (last)
Abstract
It has been recently observed that neural networks, unlike kernel methods, enjoy 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 neural networks, and the same phenomenon can be observed on the class of quadratic classifiers (i.e., the sign of a quadratic polynomial) with nuclear-Be 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 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.
Introduction
We revisit the problem supervised classification using quadratic features the data. We do so to highlight the influence of properties of data distrbution the generalization error. Most of the existing results on this error only use bound on the support of the distribution. By leveraging results from matrix concentration, distribution, like the second moment matrix.
show improved bound that uses more refined properties of the data
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. (020)).
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. 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 the study of generalization.
This influence of intrinsic dimension on generalization has been recently observed 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 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 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 (NcurIPS 2021).

---

distributions can be proved when comparing suclear-norn 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 fz-reuularization) on single-hidden layer neural network with quadratic activations, the regularization is in effect encouraging low nuclear norm of the coefficient matrix of the quadratic polynomial.
better understanding of quadratics is also a worthwhile goal in its own right: complex architectures like those in Jayakumar al. (2020) use quadratics as building blocks, attention layers Vaswani et al.) (017)). 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 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 hearly-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-isotropictt
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 theory, it is desirable in practice to obtain bounds that can be computed from sample. We overcome this difficulty in Theorem 3] where we provide high-probabilie 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 it, we observe a constant generalization gap for the nuclear-norm constrained classifier. In contrast, for SVMs, the gap grows at predicted v'd rate. In the case of anisotropic distributions, we observe similar performance for both regularization schemes.
1.1 Related work
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 nuclear norm constraint can be derived as a consequence of their results c.f. [Croolary 1] To the best of our knowledge, it is the only known bound for the hypothesis class we study, and thus the analysis improves the dependency on the dimension. See (ubsecttionn 2. for a technical discussion.
we compare Our
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 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. General- ization error bounds via Rademacher complexity are provided, but they apply only under highly restrictive assumption: the entries of the tensor are independent standard normal random variables. In contrast we only require boundedness condition.

---

Srebro et al. (2005): Srebro and Shraibman (2005) develop the theory of nuclear-noud norm regularization for matrix completion. Bounds on the Rademacher complexity of the class of matrices with bounded nuclear-norm are obtained in [reero (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 1997b. Rademacher complexity bounds are obtained for nuclear-nomn constrained multi- task 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-labe, pairs.
Matrices with bounded trace norm also have been studied by Amit et al. (0077) and Yu et al. 2014
in the related multi-class classification and multi-label learning setting, respectively. Yu al. (014) remark essential differences between Rademacher complexity bounds of nuclear- and Frohenius- 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 linear mapping of the sample, rather than as a quadratic. Thus, the analysis not analogous and requires 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) 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 non-convex parametrization of quadratic polynomials. The reparametrization consits of writing the coefficient matrix as a sum of m rank I matrices which facilitates analogies to neural networks. It is straighforward to see that their studied norm || ||2,4 is, in essence, way of upper bounding the nuclear-norm by using the reparametrization.
Rademacher complexity bounds
Notation. Throughout this section E Id is random variable with distribution μt, and X,, (Xi.... X,, is a sample of i.id. random variables drawn from μ.. The second moment matrix of f is denoted by Σ == E[xx"]. Note that, for centered (mean zero) random variables, this notion coincides with the covariance matrix. For a square symmetric matrix A we denote with || |r, ||Al|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 Re y means that there exist constants c, C such that cy S x < Cy.
We consider a binary classifier obtained from homogeneous quadratic polynomial. Such a function can be parametrized as fA (x) ;= x" Ax, 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 matrix norm ||-|| and consider only elements in constrained set:
QIIA = (x^(x) x Ax ||||| A}, 21 = 11-1111
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 a be uniformly distributed over the set 13" and let X, [xI...., .x.] C R& be i.i.d. sample drawn according to p. For class of functions FR + R we define the empirical Rademacher complexity and the Rademacher complexity (with respect to μ)) of F. respectively, as:
R(F X.) = Ex
Σ oxs(xx) SEF
sup
(F) X
(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.
3

---

Definition 2. The intrinsic dimension of a distribution is the ratio S r(2) == tr S 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 E Rd such that holds that
x
[ almost surely and suppose
r(E) log d. II
r(E) log d
Re 111- XV
(3)
71
Now we proceed to prove Theorem 1 First, we only focus on the class 11-11 corresponding to the unit nuclear-norm ball. This is justified by well-known technical result Lesula whose proof is included for completeness in Appendix D
Lemma 1. Rr 11 1.) S x (11-1)
The backbone of Theorem is Lemma 3 which relates the Rademacher complexity of a class of functions to concentration empirical means expectations with respect to the dual norm. makes use of the technical Lemma 2| whose proof is included for completeness in Appendix B
Lemma 2. For all even n E N, it holds that Σk=ol 12 n2) < V
Lemma 3. Denote by |1-1|+ the dual norm of |1-1]. Define Ms E [ز
En == Ei xxx
The Rademacher complexity of the class 11:11 can be upper bounded as follows:
(Q1H))
1 1=1
M
(4)
n2n
Proof. We first compute upper bound on the empirical Rademacher complexity. The result will follow after taking expectation of the bound over the sample X,, = [xi,..., Xn.. By definition of the dual norm, using the basic algebraic identity x" Ax
(A.
we have
R(Q ) = = EE sup
A,
Σ x 1=1
E
Σ 1=1
X
(5)
||
We now compute the expectation in eq. the Rademacher variable a E {-1, This allows to write 5 as:
There is bijection between the possible configurations of and the power set of [n], namely + {ie [n] a, 1}.
R( X..) = Eg
X
Σ x
Σ
x
n2a
(6)
BC
BEB
BEB
:=D
Let EB = B 1 xix
Using the triangle inequality, we can bound DB as:
DA < E E|| + || - | + |B"|| - EE|--
To obtain a bound on the Rademacher complexity, we need now sum over B C [ri] the terms on the right hand side of of. 7| and take expectation with respect to the sample X,,. First, we will deal with the sum of the second term in eeq. as it is actually deterministic value. We can sum over B [n]
by grouping together subsets B of the same cardinality |B] k. We obtain:
Σ BC
B B E
2k
n/| E|| & vn2"|E11
(8)
k
where the last inequality follows from
Lemma
Finally, we compute the expectation of the sum over C [rx] of the first and third term in eneeq. 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 Xi.....X, Xn are i.i.d. the distribution of Σg depends only on the size of the B. Using the same counting argument as infe. 8 we arrive at:
Σ B
B
E|1
Σ
|BEE
SB
E/1
B BC
k
E
Eg Σ||
k=1
Combining the bounds in ineq. 8 and eq. 9 and dividing by n2" 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 similar In partieular, it completely unrelated the result by Vershynin (2011) with which only shares the fairly trivial split of Rademacher random variables preceding eq.
Lemma 3) provides a way to derive Rademacher complexity bounds from bound on the expected deviations Mj 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 I simple application of well-known non-asymptotic bound for the convergence of the empirical second moment (covariance) matrix to the true second moment (covariance) matrix.
Recall that the dual norm of the nuclear-norm is the spectral-none norm. The value of M₁ in Lemma 3|meauues the average deviation of the empirical second moment matrix Σg to the true Σ, spectral-norm. Our assumption that ||x|| 1 S E|| almost surely, implies the concentration result (Vershynin) 2018, Theorem 5.6.1), which concludes that
Proof of Theorem I
(E) log d
r(E) logd
M& x
|E||
(10)
k
Plug this in eq. and the bound Vk vn for obtain the inequality
(
((2) log n2
r(E) log d
R 11)))
|اا||
(II)
n
By assumption 2 r(E) log d, so that the first term in eq. 11 the largest. The second term is of smaller order and thus ends up hidden by the notation
We conclude
log)ogg
||||
(12)
Invoking Lemma we obtain the desired result.
2.1 Improvement upon previous work
We now show how derived upper bound improves the current best known bound by Kakade ctt al. (2012). To the best of our knowledge, the Rademacher complexity of quadratic classifiers with nuclear-norm constraint has not been previously analyzed in direct manner, do. Instead, the only existing bound (Corollary appears as a particular case of Theorem 2
Theorem Kakade et al. (2012) page 1876). Les
- == (X) = (A, |||||r S S}
(13)
be the class of muclear-noo norm constrained linear functions over square d x d matrices. Let μ be distribution supported X C dd It holds that:
Togd
Rn, S o8
X sup X
n
XEX
5

---

Corollary 1. Letx E & C Rd be random variable with distribution The Rademacher complexity of the class in eq. 1 caa be bounded as
log d Rm (11)) S X
Too
sup XE
sup//>/12 |
71
Corollary 1 is a consequence of the fact that a function of the form (x = x" Ax can be written as a linear classifier on matrices, gA (X) (A, X), where X = xxx" In this case, it is easy see that
|| Xxx supxex x 12 =: Too The only difference with our bound in Theorem is that the term Too appears in place of
Xx = suPxex
In order to understand the difference between the two bounds, we turn to the analysis of the quotient between the bound in Corollary and our bound Theorem can differ drastically, depending on the distribution.
In Lemma 4 we show that this quotient
Remark The variables x and Ioo defined respectively in Theorem 2 Conollly 1 respectivelly correspond to the supremuon of 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- 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 will compare our bound to this fighter, modified bound.
Lemma 4. Let x be a random variable supported on set X S IR.,, and such that [xx S E||x almost surely, then:
CSS eSSSUPPERS x |
Vr(E) S
S Vr(E)
(14)
Vr(E)|E|12
Proof. By definition of essential supremum it holds that E E| S ess supxex' |x xI Further, our
assumption clearly implies that ess supxex||xx| < B The identity E x tr(E) and Definition 2 imply the result.
In summary, Lemma s/swww that the baseline bound of Kakade al. (2012) is larger by square-root factor of the intrinsic dimension of the distribution (modulo global constants), compared to our bound in Theorem Such factor ranges between 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 reduced dimension complexity. This is the case, for example, for isotropic distributions ie., 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 can be removed under the more restrictive dimension- independent L-subgaussianity assumption (Mendelson and Zhivotovskiy 2018).
3 Computable Generalization error bounds
Let y (y1,...,9a. E 1-,, be the labels associated with the data sample, and let
L(f) = P(sign(f (x)) #y}
(15)
i(f:X.) = Σ min(1, max 10:01-y:((1))) (xx)))
(16)
be the missclassification probability and the empirical margin loss of the classifier f, respectively. well-known (Mohri et al., 2018 Theorem 5.8.) that with probability at least 8, for all Qjilee.::
log 1
L(F) S i(f:Xa) + ( + V
(17)
2n

---

This bound, together with the results in section 2, allow high probability uniform bounds on the misclassification error of a nuclear-norm constraied 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.
as:
Rm (11-) tr 11 log d
(18)
we observe that we need 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 Σ,. will provide good approximation of the true values.
We arrive at the following high probability bound on the Rademacher complexity in en. 18 which is readily computable from samples and bound the diameter of the support of the distribution:
Theorem 3. Suppose that ||x|2 x E| almost surely. This implies that ||x1| for some B > Define
2 log 1 8 log d
log d
K1 n nd d + log
K2 ==
(19)
2n(yn v d(log d + log t))
Let 5 0 and fA 111- Provided n 2 d(logd d + log })) with probability least 35
holds that
S K1 tr E., P BK2 En
(20)
=M(ndd
Moreover, with probability at least - 46, uniformly for all fA E 11 it holds that
log 1
L(fA) & i(fA:X.) (M, V
(21)
2n
Proof. Seeenppediix C
Frobenius vs Nuclear-norm constraint
Perhaps the most common way to use quadratic features to use support vector machine (SVM) with the quadratic kernel K(x, y) == y). Lemma 5] which is folklore in the kernel methods literature, precisely states that the RKHS norm constraint is equivalent to Frobenius-norm constraint on the matrix of coefficients A of the underlying quadratic polynomial. Its proof is included for completeness in Appendix
Lemma 5. Let HH be the Reproducing Kernel Hilbert Space associated to the symmetric, positive semidefinite polynomial kernel K(x,)) = yx, and denote its induced norm by ||-I|E. Then E if and only if there exists symmetric matrix such that fxx x" Ax and [| = |||]]
turn 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-non constrained quadratics is insensitive to it.
For this reason,
In order to derive this rate, need 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 the data distribution:
Assumption 1. | se d almost surely.
7

---

We now argue why this is natural scaling order for this norm: if the entries of the random vector x are upper bounded as |X] Omax and their average magnitude is lower bounded as Then
0 < Ommin S 1 >im iml X
O'min vds =
|x|| S |x12 S vallx|lo I Vddmmx:
and hence, Assumption iss 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 similar characteristics (e.g., sensor data) will probably satisfy our assumption.
We also introduce growth condition on the intrinsic dimension, which states that r(E) 2 d' for some 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 < <(=) s d. Traditionally, distributions that attain the lower bound (s = 0, r(x) 1) or the upper bound (s 1,
r(E)= = d) are called anisotropic or isotropic, respectively.
Corollary 2. Let Assumptiin hold, and suppose that r()) z d for some E [0. 1] and 2 r(E) log d. Then
R (2.1)(111/1))) (2)1-1 A dl- Togd
(22)
vn
Rn (21-((1)11))))
(23)
Proof. For the first inequality, note that ||x R d implies that tr = E|x 3 Ri d. Thus, ||
tr
r(E) Ri d =
|E|| x d=- Using these two identities in the inequality eq. 3 we obtain the first
result.
For the second identity, Lemma 5 iimlies 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 we have that
A
x
Ad
1 Xn)
Σ K(X,, xi)
x
(24)
where the final inequality comes from our assumption that ||x|12 RJ d. Taking expectation with respect to the sample we obtain that R.,, (2111(11111))))) R
L
Corollary 2 then states that the nuclear norm constraint adapts the intrinsic dimension of the distribution. In the worst case (s = 0) it grows linearly with dimension; In the best case (s = 1) it is much slower, and grows the square root of the dimension.
Note that we can bring any distribution to approximate isotropic position, given good approximation of Σ. Hence, it makes sense to expect performance gains if we perform such normalization procedure before training nuclear-norn norm constrained quadratic classifiers. sscctionn we will put to test this claim in synthetic datasets, to illustrate the theory.
Experiments
The results derived in Corollary pertain the worst case generalization gap. This case gap is not guaranteed to be attained by the function found through empirical loss minimization. Therefore, in order better test results, try find the function that attains this worst case generalization gap.
'See remarks following the proof
ffor simplicity ignore the logarithmic factor
8

---

The experiment we propose to illustrate the difference in intrinsic dimension sensitivity consists of computing the quadratic function such that E[E( (xx y))l Σx= ((x, y:)) maximized. The expectation in the term above being generally difficult to compute in closed form, we replace the objective by an empirical estimate
e(((x): y1-))
Σ ((f(x,))))
Thest
Tarain
We expect this quantity to more faithfully track the upperbounds derived in "nCorlllayy 2] Indeed, what we evaluate here is the capacity of the class constraining f attain low loss on Thtain samples while attaining very high one on Thest 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 standard Gaussian random vector in Rd and normalize to obtain i.i.d samples that are uniformly distributed the sphere of radius vd.
Generating Anistropic Data To generate anisotropic data, we first generate isotropic data features by uniformly sampling points the sphere of radius vd as described previously. We then transform the samples into more anisotropic ones by multiplying each feature vector coordinate- wise by vector (**) defined a: (s) C. i l,...,de d, for E [0, 1] where C, is chosen such that ||a6 ||2 = vd. That, way, s induces no change on the data, since (1) [1. 1, 1....: : 1)², and larger 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[|la(*) x x
(a 2 (a (2) vd
Generating the labels We test two approaches for generating the labels (1) generate random matrix A with i. standard Gaussian coordinates and set sgn(x? Ax;), (2) We set the labels randomly with y ~ (0rn...5).
Nac. Eotrox
Ruz Idvost
Muc: arkottra
Mic crastops
Fr sotrape
2.0
150
263
(a) Labels generated 34 sgn(x² Ax)
(b) Labels generated randomly
Figure 1: Maximized Train/Test loss gaps for each dimension d. The results are averaged over 5 independent runs. The error bars correspond to the standard error.
The results We observe that the maximal gaps do indeed evolve as the theory predicts. We indeed have the nuclear norm constrained classifier isotropic data not exhibiting the same growth as the others, indicating that the maximal generalization gap for nuclear norm constrained classifiers indeed sensitive to isotropy. Additional experiments and details are provided in Appendix E

---

Discussion
Our result shows that given fixed regularization parameter X, nuclear-norm constrained classifiers can take advantage of the properties of the data distribution to shave off v factor from the Rademacher complexity, whereas Frobenius-norm constrained ones cannot.
We rely on two main elements show this Hölder's incquality in equation (5) which introduces the dual norms and bound on the expected deviations Mg. 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 Elll Σi= 2m -Mllopl, where M [[ the tensor of m-th moments. For matrices, the rate is obtained through the matrix Bernstein inequality. Therefore, extension 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.
Acknowledgements
This work is funded (in part) through PhD fellowship of the Swiss Data Science Center, joint venture between EPFL. and ETH Zurich. This project has received funding from the European Re- search 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 Naval Research (ONR) under grant number N62909-17-1-21 11. Research was sponsored by the Army Research Office and was accomplished under Grant Number W91 19F1-19--100000 This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021_178865 1.
References
Amit, Y., Fink, M., Srebro, N., and Ullman, (2007). Uncovering shared structures in multiclass classification. In Proceedings of the 24th international conference Machine learning, pages 17-24.
Bai, Y. and Lee, D. (2020). Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations.
Bartlett, P. L. and Mendelson, S. (2003). Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3(nu11):463-482
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-MMlne. S., and Zhang, Q. (2018). JAX: composable transformations of PythonnNummP programs.
Buitinck, L., Louppe, G., Blondel, M., Pedregosa, F., Mueller, A., Grisel, O., Niculae, V., Prettenhofer, P. Gramfort, A., Grobler, J., Layton, R., VanderPlas, J., Joly, A., Holt, B., and Varoquaux, G. (2013). API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pages 108-122.
Caruana, R. (1997). Multitask Learning. Machine Learning, 28(1):41-75.
Du, S. and Lee, J. (2018). On the power of over- parametrization in neural networks with quadratic activation. In Dy. J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1329-1338. PMLR.
Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, Т. (2008). Efficient projections onto the I 1-ball for learning in high dimensions. In Proceedings of the 25th international conference Machine learning, pages 272-279.
Fan, R.-F.,, Chang, K.W.,, Hsieh, C.-J,, Wang, X.-R., and Lin, C.-J. (2008). Liblinear: library for large linear classification, J. Mach. Learn. Res., 9:1871-1874.
10

---

Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. (2020). When do neural networks outperform kernel methods?
Jacot, A., Gabriel, F,, and Hongler, C. (2018). Neural tangent kernel: convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages -889.
Jayakumar, M., Czarnecki, W. M., Menick, J., Schwarz, J., Rae, J., Osindero, S., Teh, W., Harley, T., and Pascanu, R. (2020). Multiplicative interactions and where to find them. In International Conference on Learning Representations.
Jiang*. Y., Neyshabur* B., Mobahi, H., Krishnan, D., and Bengio. S. (2020). Fantastic generalization measures and where to find them. International Conference on Learning Representations.
Kakade. S. M., Shalev-Shwarte S., and Tewari, A. (2012). Regularization techniques for learning with matrices. Journal of Machine Learning Research, 13(Jun): 1865-180.
Koltchinskii, V. and Panchenko, D. (2002). Empirical margin distributions and bounding the general- ization error of combined classifiers. Ann. Statist., 30(1):1-50.
Luo, 7., Qi, I.., and Toint, P. L.. (2019). Bernstein concentration inequalities for tensors via einstein products, arXiv preprint arXiv:1902.03056.
Mendelson, S. and Zhivotovskiy. N. (2018). Robust covariance estimation under L Le norm equivalence. arXiv e-prints, page 1eXiv:1809.1000
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of Machine Learning. The MIT Press, 2nd edition.
Pontil, M. and Maurer, (2013). Excess risk bounds for multitask learning with trace norm regularization. In Shalev-Shwartz, S. and Steinwart, I., editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 55-76, Princeton, NJ, USA. PMLR.
Pope, P., Zhu, C., Abdelkader, A., Goldblum, M., and Goldstein, T. (2021). The intrinsic dimension of images and its impact learning. In International Conference on Learning Representations.
Srebro, N. (2005). Learning with matrix factorizations. PhD. Thesis.
Srebro, N., Rennie, J., and Jaakkola, T. S. (2005). Maximum-mare matrix factorization. In Saul, L. K., Weiss, Y., and Bottou, L.,, editors, Advances in Neural Information Processing Systems 17, pages 329-1136. MIT Press.
Srebro, N. and Shraibman, A. (2005). Rank, trace-norm and max-norm. In Auer, P. and Meir, R., editors, Learning Theory, volume 3559, pages 545-560. Springer Berlin Heidelberg. Series Title: Lecture Notes in Computer Science.
Tropp, A. (2015). An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, u., and Polosukhin, I. (2017). Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 6000 1000-6010, Red Hook, NY. USA. Curran Associates Inc.
Vershynin, (2011). A simple decoupling inequality in probability theory (2011. http:// Www www-personal, umich. htlp//romaa//ppperssa hetp:///ccccppiigg wwwiinggnnnppiii pdf [Online: accessed 1-1221.ary-20211..
Vershynin, R. (2018). High-Dimenn Dimensoamels Probubility: An Introduction with Applications in Data Science. Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press.

---

Wimalawame, K., Tomioka, R., and Sugiyama. M. (2016). Theoretical and experimental analyses of tensor-based regression and classification. Neural Computation, 28(4):686-715. Publisher: MIT Press.
Yehudai, G. and Shamir, O. (2019). On the power and limitations of random features for understanding neural networks. 32.
Yu, H.-F., Jain, P., Kar, P., and Dhillon, I. (2014). Large-scale multi-label learning with missing labels. In Xing. E. P. and Jebara, T., editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 593-601, Bejing, China. PMLR.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] The work of theoretical nature and its societal impacts are difficult to foresee.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all thcoretical results? [Yes] They are given in the Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "pX7Qhq4Lajl", "reviewer": "Reviewer_fnjC", "summary": "The paper studies the generalization ability of quadratic forms under trace norm regularization.\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall I liked the paper.\nThe 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.\nThe 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.\n\nI 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.\nInstead 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "adequately adressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ch-G8p9CYG0", "reviewer": "Reviewer_DAu4", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "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.\n\nMy 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. \n\nTypos: “triangle inequality” missing the (pg. 4), of vs off (pg. 10), Holder missing accent (pg. 10)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "Tfvb-bo5Pyf", "reviewer": "Reviewer_WNca", "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "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. \n  \nIt 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?\n\nI feel there is a seed of a good idea here albeit the work seems to be in early stages.\n\nThe assumption \\|x\\|_2^2 \\ge const E\\|x\\|_2^2 almost surely seems strange to me. Can the authors justify it? \n\nI'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?  \n\nThe writing quality can be improved in many places. \n- In Proof of Cor 2 it says \"both identities in eq. 3\" -- but eq(3) is one inequality!\n- bottom of p 8: \"try to find\" sounds vague - indeed, what if the optimiser doesn't find the function we look for?\n- top of p 10: what is mean by \"an equal regularisation parameter\"?\n\nPost rebuttal: \nThe authors addressed all clarity issues. \nI 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.   \n\nOn 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:\nBenjamin Recht. A Simpler Approach to Matrix Completion, Journal of Machine Learning Research 12 (2011) 3413-3430.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not explicitly mention limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

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)