Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity

Introduction

A possible approach to learning is to choose some feature map $\varphi(x)$, or equivalently some kernel $K(x,x^{\prime}):=\left\langle\varphi(x),\varphi(x^{\prime})\right\rangle$, appropriate for the problem, and then reduce the problem of learning, to that of learning a linear predictor, or a low (Euclidean or Hilbert) norm linear predictor, with respect to this embedding. Such an approach is often successful in practice, and is the basis of “kernel methods”. But what are the inherent limits of such an approach? Are there easily learnable hypothesis classes that cannot be learnt using such an approach, or perhaps require many more samples for learning, no matter what feature map or kernel is used? This classic question about the limits of kernel methods has been explored by, e.g. Ben-David et al. (2002), and has lead to the notions of dimensional and margin complexity of a hypothesis class— these correspond to the minimal dimension and minimal norm (respectively) of a feature space sufficient to exactly represent all hypotheses in the class as linear predictors (see precise definitions in \sectionrefsec:dc-mc). Dimensional and margin complexity have also been studied in communication complexity (See e.g., Forster and Simon, 2006; Forster et al., 2003; Sherstov, 2008; Razborov and Sherstov, 2010). Questions about the limits of kernel methods have resurfaced in recent years, in the context of understanding the advantage of deep learning over kernel methods, and identifying hypothesis classes that are learnable by training a neural network (using an efficient and simple training procedure) but that are not learnable, or at least not without many more samples, using any kernel or feature map (Allen-Zhu and Li, 2019, 2020; Yehudai and Shamir, 2019).

While the standard notions of dimensional and margin complexity are sufficient for learning by reduction to linear learning, they might not be necessary for such an approach. This is because these notions insist on a feature map that can be used to exactly represent all hypotheses in the class, without any errors. But for learning, it is sufficient to only approximate the hypotheses, up to a small error $\varepsilon$. Furthermore, once we allow small errors, we might want to consider randomized rather than deterministic feature maps or kernels. This is not only a hypothetical possibility—examples of specific randomized feature maps and kernels include Random Fourier Features (Rahimi and Recht, 2008), the Conjugate Kernel (Daniely, 2017), and the Neural Tangent Kernel at a random initialized neural network (Jacot et al., 2018). One might ask if such randomized approximate embedding are in fact more powerful, or whether perhaps they can always be de-randomized and made exact. In this paper we establish (\theoremrefthm:dc-vs-probdc-sep, combined with \theoremrefthm:lin-tilde-vs-dc) that randomized approximate embedding are indeed more powerful: we show that learning is possible using a randomized feature map, even for a hypothesis class for which no exact low dimensional representation exists (i.e. with a very high, or even infinite, dimensional complexity). In order to truly understand the power of kernel methods and reduction to linear learning, we must therefore also allow for such randomized feature maps and kernels, and understand their power and limitations.

In this paper we propose and study relaxed notions of dimensional and margin complexity that (a) allow for randomized feature maps; and (b) can be shown to be not only sufficient, but also necessary for learning by reduction to linear or kernel methods, and so yield strong lower bounds on the power of such an approach. In discussing approximation of a hypothesis class, we must consider the loss used, and we study both classification problems with respect to a hard (0/1) loss, as well as classification and regression with continuous losses such as the hinge and squared loss.

In order to be able to discuss a necessary condition for “learning by reduction to linear or kernel methods” we must precisely define what we mean by this phrase. We do so in \sectionrefsec:linear-learning. We consider both distribution-dependent and distribution-independent learning. Correspondingly, we define both distribution-dependent and distribution-independent approximate dimensional and margin complexity (in \sectionrefsec:dc-mc). Our complexity definitions are justified by showing how they are both necessary and sufficient (in a sense) for learning by reduction to kernel or linear methods. We also show how the distribution-dependent approximate dimension complexity lower bounds linear and kernel learning in a very broad sense, and with respect to a generic loss function. In \sectionrefsec:dc-lowerbounds we further show how this complexity measure can be lower bounded, in turn, by other well studied complexity measures, providing for a generic way of obtaining strong lower bounds on the power of kernel methods.

Our generic lower bound approach mirrors, to a large extent, the lower bound on the sample complexity of kernel based learning in several recent papers exploring the power of deep learning versus kernel method (Allen-Zhu and Li, 2019, 2020; Yehudai and Shamir, 2019). We distil the approach to a crisp complexity measure, which simplifies making such lower bound claims on specific hypothesis classes, and can also lead to stronger statements—we demonstrate this by strengthening the lower bound and resolving an open question of Yehudai and Shamir (2019). Our lower bound is stated in terms of the Statistical Query dimension, as defined by Blum et al. (1994), making a concrete connection between these complexity measures (“dimensionalities”). Our treatment also highlights a potential deficiency of this approach: although we can establish lower bounds for learning w.r.t. the squared loss, using the same technique to establish a strong lower bound on learning w.r.t. the 0/1 loss would resolve a long-standing question in circuit complexity theory and thus seems much more difficult.

Throughout the paper, we are not overly concerned with the precise dependence on the “error parameter” $\varepsilon$. Although we always explicitly note the dependence on $\varepsilon$, we think of it as a small constant, perhaps $0.01$, and do not worry about factors which are polynomial in $\varepsilon$. In this paper, we only refer to learning and approximating in expectation—it is possible to define and relate approximating and learning with high probability instead, but we avoid doing so for notational simplicity.

Dimension & Margin Complexities and their Probabilistic Variants

We recall the definitions of the dimension and margin complexities of a hypothesis class and introduce their probabilistic variants. Our definitions of the error-free notions are also stated in terms of a loss function so that we can then extend them to allow errors.

2 Margin Complexity

3 Relationship between Probabilistic Dimension & Margin Complexity

A classic result attributed to Arriaga and Vempala (1999) and Ben-David et al. (2002) shows that

This result is proved by an application of the lemma of Johnson and Lindenstrauss (1984). The term of $\mathcal{O}(\log|\mathcal{H}||\mathcal{X}|)$ comes up due to a union bound over all pairs of $(x,h)\in\mathcal{X}\times\mathcal{H}$. Although the result can be seen as establishing a tight connection between the dimension and margin complexity, it is not applicable with continuous (or simply infinite) domains, and we are not aware of any way of avoiding this dependence on the cardinality of the domain.

As a first application of our probabilistic notions, we show how this bypasses the cardinality dependence when allowing a randomized feature map.

The proof is similar to that of Ben-David et al. (2002) in its use of the lemma of Johnson and Lindenstrauss (1984). We defer the proof details to \appendixrefapx:proof-dc-mc. The random feature map used here is analogous to random features used in practice to approximate kernels (Rahimi and Recht, 2007).

4 Separations between Deterministic and Probabilistic Dimension Complexity

For $\mathcal{X}=\left\{1,-1\right\}^{n}$, there exists a hypothesis class $\mathcal{H}\subseteq\left\{1,-1\right\}^{\mathcal{X}}$ with $|\mathcal{H}|=2^{n}$ such that, for all $\varepsilon\in(0,\nicefrac{{1}}{{2}})$,

For every $n$, there exist hypothesis classes $\mathcal{H}\subseteq\left\{1,-1\right\}^{\mathcal{X}}$ with $|\mathcal{H}|=|\mathcal{X}|=2^{n}$ such that for all $\varepsilon\in(0,\nicefrac{{1}}{{2}})$,

We prove \theoremrefthm:dc-vs-probdc-sep as follows (full details in \appendixrefapx:proof-dc-vs-probdc-sep): We define another notion of probabilistic dimension complexity that has a stronger requirement of pointwise correctness and hence is larger than $\mathsf{dc}_{\varepsilon}$. This notion is equivalent to probabilistic sign-rank studied in communication complexity. In particular, Alman and Williams (2017) showed that if the function $E_{\mathcal{H}}:\mathcal{H}\times\mathcal{X}\to\left\{1,-1\right\}$ defined as $E_{\mathcal{H}}(h,x):=h(x)$ is computable by a “small” depth-$2$ threshold circuit (for some encoding of $\mathcal{H}$ and $\mathcal{X}$ into bits), then $M_{\mathcal{H}}$ has “small” probabilistic sign-rank. The theorem follows from a lower bound on sign-rank shown by Chattopadhyay and Mande (2018) for matrices that are computable by “small” depth-$2$ threshold circuits. The hypothesis class $\mathcal{H}$ witnessing this separation is a class of decision lists of conjunctions over disjoint variables.

We prove \theoremrefthm:dc-vs-prob-dist-dc-sep as follows (full details in \appendixrefapx:proof-dc-vs-prob-dist-dc-sep): We use the “covering lemma” of Haussler (1995) to show that the probabilistic distributional dimension complexity of any class can be bounded, albeit exponentially, in terms of the VC dimension, establishing the following Lemma:

This is in contrast to the exact dimensional complexity, which can be polynomially large in $|\mathcal{H}||\mathcal{X}|$ even for classes of bounded VC dimension Alon et al. (2016). \theoremrefthm:dc-vs-prob-dist-dc-sep now follows by considering a hypothesis class with VC-dimension $2$ with dimensional complexity of $2^{\Omega(n)}$.

The construction in \theoremrefthm:dc-vs-probdc-sep uses extremely large magnitude features and weights, whereas the construction in \theoremrefthm:dc-vs-prob-dist-dc-sep uses bounded magnitude of features and weights, but relies on having a known marginal $\mathcal{D}$ over $\mathcal{X}$. Our theorems therefore leave open the following questions.

Linear & Kernel Learnability with Probabilistic Embeddings

We now turn to precisely defining learning by reduction to Linear Learning or Kernel Learning. These notions serve as the primary motivation for our work, and their definitions guided the definitions of the other complexity notions we consider.

where we require generalization for any minimizer of the empirical error. We formalize the Linear Learning Complexity of a hypothesis class $\mathcal{H}$ as the minimal sample complexity of any learning rule of the form \eqrefeq:dcERM.

The proof of \theoremrefthm:lin-tilde-vs-dc is presented in \appendixrefapx:proof-learn-dc-mc-upper. Thus, $\mathsf{dc}_{\varepsilon}(\mathcal{H})$ (and $\mathsf{dc}^{\mathcal{D}}_{\varepsilon}(\mathcal{H})$) precisely captures “the sample complexity of learning $\mathcal{H}$ using a linear embedding by relying on a guarantee that follows from dimension based generalization bounds”, and are therefore sufficient for linear learning. In \sectionrefsubsec:learning-lower, we will return to the question of whether they are also necessary for the weaker notion of linear learning of Definition 3.1, i.e. whether they also lower bound $\mathsf{Lin}_{\varepsilon}$ and $\mathsf{Lin}^{\mathcal{D}}_{\varepsilon}$. But before that, we introduce the analogous notions for kernel based learning.

2 Kernel Learning Complexity

Recall that for any $\mathscr{D}$, any bounded embedding with $\|\varphi\|_{\infty}\leq 1$, any $R$ and any Lipschitz loss (c.f. Shalev-Shwartz and Ben-David, 2014),

As we did in the case of linear learning, to relate $\mathsf{Ker}_{\varepsilon}(\mathcal{H})$ to $\mathsf{mc}_{\varepsilon}(\mathcal{H})$, we again consider a stronger notion that requires learning that can be guaranteed based only on the norm, using \equationrefeq:norm-based-uniform:

The proof of \theoremrefthm:ker-tilde-vs-mc is presented in \appendixrefapx:proof-learn-dc-mc-upper. Thus, $\mathsf{mc}_{\varepsilon}(\mathcal{H})$ and $\mathsf{mc}_{\varepsilon}^{\mathcal{D}}(\mathcal{H})$ precisely captures “the sample complexity of learning $\mathcal{H}$ using a kernel with a guarantee that follows from norm based generalization bounds”, both for margin-based binary classification, and with respect to a Lipschitz loss.

Remark. Our definitions of $\mathsf{Lin}_{\varepsilon}$ and $\mathsf{Ker}_{\varepsilon}$ capture realizable learning. We can also consider agnostic variants where we allow any $\mathscr{D}$ and the right hand side of \eqrefeqn:lin-learn, \eqrefeqn:lin-tilde-learn, \eqrefeqn:ker-learn, \eqrefeqn:ker-learn-01, \eqrefeqn:ker-tilde-learn and \eqrefeqn:ker-tilde-learn-01 changes to $\inf_{h\in\mathcal{H}}\mathcal{L}_{\mathscr{D}}(h)+\varepsilon$, for loss functions where this makes sense. The lower bounds on learning of course still hold, and for typical loss functions, including those discussed in this work, we can still get upper bounds in terms of the approximate dimensional and margin complexities.

3 Lower Bounds on Learning

This follows as a consequence of the Representer Theorem, which allows us to replace any high-dimensional embedding by an $m$ dimensional one that is obtained as the span of the embeddings of the samples from $\mathscr{D}$. The proof is presented in \appendixrefapx:proof-learn-dc-mc-upper.

Since \theoremrefthm:learn-lowerbound holds for any distribution $\mathcal{D}$, the lower bound on distribution independent learning can also be stated as

Lower bounds on Probabilistic Distributional Dimension Complexity

For a distribution $\mathcal{D}$ over $\mathcal{X}$, the min-Eigenvalue dimension of a normalized hypothesis class $\mathcal{H}$, denoted as $\mathsf{minEV}\text{-}\mathsf{dim}^{\mathcal{D}}(\mathcal{H};\lambda)$, is the largest $t$ for which there exists a subset of hypotheses $H_{t}:=\left\{h_{1},\ldots,h_{t}\right\}\in\mathcal{H}$ such that $\lambda_{\min}(G^{\mathcal{D}}_{H_{t}})\geq\lambda$.

Let $\mathcal{H}_{t}=\left\{h_{1},\ldots,h_{t}\right\}\subseteq\mathcal{H}$ such that $\left\langle h_{i},h_{j}\right\rangle_{\mathcal{D}}\leq 1/2t$. Thus, all off-diagonal entries of $G^{\mathcal{D}}_{\mathcal{H}_{t}}$ are at most $1/2t$ in magnitude, whereas all diagonal entries are $1$. It follows from Geršgorin (1931) “circle theorem” that all eigenvalues of $G^{\mathcal{D}}_{\mathcal{H}_{t}}$ are at least $1-t/2t=1/2$.

Remark. More generally, we could define $\mathsf{SQ}\text{-}\mathsf{dim}^{\mathcal{D}}(\mathcal{H};\gamma)$ with respect to parameter $\gamma<1$, as the largest $t$ for which there exist hypotheses $h_{1},\ldots,h_{t}\in\mathcal{H}$ such that $\left\langle h_{i},h_{j}\right\rangle_{\mathcal{D}}\leq\gamma$ for each $i\neq j$. \objectrefprop:SQdim-EVdimPropositionPropositions could then be $\mathsf{SQ}\text{-}\mathsf{dim}(\mathcal{H};\gamma)=t$ implies that $\mathsf{minEV}\text{-}\mathsf{dim}(\mathcal{H};1-t\gamma)\geq t$.

Observe that the bound becomes vacuous at $\varepsilon=\frac{1}{2}$, and rightly so, because the zero function incurs a square loss of $1/2$ for any $h\in\mathcal{H}$, since $\mathcal{H}$ is a normalized hypothesis class. The constant function is realizable with an embedding of dimension $1$.

Our proof of \theoremrefthm:dcl2-lowerbound-EV is inspired by the technique due to Alon et al. (2013) for lower bounding the “approximate rank” of a matrix that is well studied in communication complexity. We present the full proof in \appendixrefapx:proof-dcl2-lowerbound-EV. Combining \objectrefprop:SQdim-EVdimPropositionPropositions with \theoremrefthm:dcl2-lowerbound-EV immediately gives us the following corollary.

1.1 Applications of Theorem 4.5

We now discuss some applications of our \theoremrefthm:dcl2-lowerbound-EV and \corollaryrefcor:dcl2-lowerbound-SQ.

Let $\mathcal{X}_{n}=\left\{1,-1\right\}^{n}$ and $\mathcal{H}_{n}^{\oplus}=\left\{\chi_{S}(x):=\prod_{i\in S}x_{i}:S\subseteq[n]\right\}$ be the class of all parity functions on $n$ bits. Let $\mathcal{D}$ be the uniform distribution over $\mathcal{X}$. For any two distinct subsets $S,T\subseteq[n]$, we have that $\left\langle\chi_{S},\chi_{T}\right\rangle_{\mathcal{D}}=0$. Thus, $\mathsf{SQ}\text{-}\mathsf{dim}^{\mathcal{D}}(\mathcal{H}_{n}^{\oplus})=2^{n}$. More strongly, we also have $\mathsf{minEV}\text{-}\mathsf{dim}(\mathcal{H}_{n}^{\oplus};1)=2^{n}$. Thus, from \theoremrefthm:dcl2-lowerbound-EV, we get

Our proof builds on a proposition from Yehudai and Shamir (2019) and also follows the outline there quite closely. However, we believe that this way of presenting the proof is more insightful as it is modular, involving a lower bound on SQ-dimension. The details are deferred to \appendixrefapx:proof-relu.

2 Probabilistic dimension complexity w.r.t. 0-1 loss

In the previous subsection we considered regression problems, and learning with respect to the squared loss. We now turn to the classification and learning with respect to the 0/1 loss.

Fix $\varepsilon<1/2$. For $\mathcal{D}$ being the uniform distribution over $\mathcal{X}_{n}=\left\{1,-1\right\}^{n}$ it holds that,

where $h(q):=q\log_{2}\left(\frac{1}{q}\right)+(1-q)\log_{2}\left(\frac{1}{1-q}\right)$ is the binary entropy function.

thm:dcl01-lowerbound-sparse also shows that the exponential dependence in our upper bound of $\mathsf{dc}_{\varepsilon}^{\mathcal{D}}(\mathcal{H})$ in terms of $\mathsf{VC}\text{-}\mathsf{dim}(\mathcal{H})$ (\lemmareflem:dc_vc_upper) is indeed necessary, and \lemmareflem:dc_vc_upper is, in this sense, tight.

In \theoremrefthm:dcl01-lowerbound-sparse we proved a lower bound on $\mathsf{dc}_{\varepsilon}^{\mathcal{D}}(\mathcal{H}_{n})$ for the class of $1$-sparse predictors, which has $|\mathcal{X}_{n}|=2^{|\mathcal{H}_{n}|}$. Even just representing a single instance in this example requires $\log\left\lvert{\mathcal{X}_{n}}\right\rvert=n$ bits, and so the runtime for any learning algorithm would also be at least $\Omega(n)$. That is, even though we showed the sample complexity for linear or kernel based learning is exponential in the VC-dimension, i.e. insisting on linear or kernel based learning causes an exponential increase in sample complexity, the sample complexity of linear learning is still no more than linear in the runtime or even memory of a direct approach. This is in contrast to the examples of \sectionrefsec:sqsq, where the lower bound on the sample complexity of linear or kernel based learning was exponential also in the representational cost of instances, i.e. in $\log\left\lvert{\mathcal{X}}\right\rvert$.

In turns out that proving such a lower bounds for any explicit class $\mathcal{H}$ will have significant complexity theoretic consequences. Suppose for example, we have an explicit class $\mathcal{H}\subseteq\left\{1,-1\right\}^{\mathcal{X}}$ for which we could prove, for some value of $\varepsilon>0$, that

That is, we could establish a lower bound on $\mathsf{dc}_{\varepsilon}^{\mathcal{D}}(\mathcal{H})$ that is super-polynomial in $\log\left\lvert{\mathcal{X}}\right\rvert$ and in $\mathsf{VC}\text{-}\mathsf{dim}(\mathcal{H})$ (recall that $\mathsf{VC}\text{-}\mathsf{dim}(\mathcal{H})\leq\log\left\lvert{\mathcal{H}}\right\rvert$). As shown by Alman and Williams (2017) (see \lemmareflem:alman-williams & \objectrefprop:prob-dc-vs-ptPropositionPropositions) it will follow that depth-$2$ threshold circuits computing $E_{\mathcal{H}}:(h,x)\mapsto h(x)$ require size that is at least $(\log|\mathcal{H}||\mathcal{X}|)^{\omega(1)}$, for any binary encoding of $\mathcal{H}$ and $\mathcal{X}$.

Proving super-polynomial lower bounds on the size of depth-$2$ threshold circuits is a major frontier in Complexity Theory (the best lower bounds known so far is due to Kane and Williams (2016), who show a lower bound of $\widetilde{\Omega}(n^{1.5})$ for an explicit $n$-bit function). And so, establishing strong lower bounds on linear or kernel based learning with respect to the 0/1 loss for specific classes seems difficult. This explains, perhaps, why recent work on the relative power of deep learning over kernel method focused on regression w.r.t. the square loss, and indicates that establishing similar results also for classification might not be so easy.

Summary

We hope that our notions of probabilistic dimensional and margin complexity prove useful in the further understanding of the limitations of linear and kernel learning.

We thank Josh Alman, Shai Ben-David, Avrim Blum, Brian Bullins, Surbhi Goel, Mika Göös, Suriya Gunasekar, Adam Klivans, Nati Linial, Raghu Meka, Prasad Raghavendra, Sasha Razborov, Ohad Shamir, Sasha Sherstov, Blake Woodworth and Gilad Yehudai for helpful discussions. We would especially like to thank Surbhi for suggesting the formulation in \corollaryrefcor:dcl2-lowerbound-SQ in terms of SQ dimension and Mika for suggesting the proof of \theoremrefthm:dcl01-lowerbound-sparse.

Research was partially supported by NSF BIGDATA award 1546500 and NSF IIS/RI award 1764032. Part of the work was done when the authors were visiting the Simons Institute as part of the program on Foundations of Deep Learning.

References

Appendix A Relating 𝗱𝗰𝗱𝗰\mathsf{dc} and 𝗺𝗰𝗺𝗰\mathsf{mc} : Proof of Lemma 2.5

We can also derive an expectation version of the above to get