VC DIMENSION OF PARTIALLY QUANTIZED NEURAL NETWORKS IN THE OVERPARAMETRIZED REGIME
Year: 2021

Abstract:
Vapnik-Chervonenkis (VC) theory has so far been unable to explain the small generalization error of overparametrized neural networks. Indeed, existing applications of VC theory to large networks obtain upper bounds on VC dimension that are proportional to the number of weights, and for a large class of networks, these upper bound are known to be tight. In this work, we focus on a subclass of partially quantized networks that we refer to as hyperplane arrangement neural networks (HANNs). Using a sample compression analysis, we show that HANNs can have VC dimension significantly smaller than the number of weights, while being highly expressive. In particular, empirical risk minimization over HANNs in the overparametrized regime achieves the minimax rate for classification with Lipschitz posterior class probability. We further demonstrate the expressivity of HANNs empirically. On a panel of 121 UCI datasets, overparametrized HANNs match the performance of state-of-the-art full-precision models.

text: Vapnik-Chervonenkis (VC) theory has so far been unable to explain the small generalization error of overparametrized neural networks. Indeed, existing applications of VC theory to large networks obtain upper bounds on VC dimension that are proportional to the number of weights, and for a large class of networks, these upper bound are known to be tight. In this work, we focus on a subclass of partially quantized networks that we refer to as hyperplane arrangement neural networks (HANNs). Using a sample compression analysis, we show that HANNs can have VC dimension significantly smaller than the number of weights, while being highly expressive. In particular, empirical risk minimization over HANNs in the overparametrized regime achieves the minimax rate for classification with Lipschitz posterior class probability. We further demonstrate the expressivity of HANNs empirically. On a panel of 121 UCI datasets, overparametrized HANNs match the performance of state-of-the-art full-precision models.

heading: 1 INTRODUCTION
text: Neural networks have become an indispensable tool for machine learning practitioners, owing to their impressive performance especially in vision and natural language processing (Goodfellow et al., 2016). In practice, neural networks are often applied in the overparametrized regime and are capable of fitting even random labels (Zhang et al., 2021). Evidently, these overparametrized models perform well on real world data despite their ability to grossly overfit, a phenomenon that has been dubbed “the generalization puzzle” (Nagarajan & Kolter, 2019).
Toward solving this puzzle, several research directions have flourished and offer potential explanations, including implicit regularization (Chizat & Bach, 2020), interpolation (Chatterji & Long, 2021), and benign overfitting (Bartlett et al., 2020). So far, VC theory has not been able to explain the puzzle, because existing bounds on the VC dimensions of neural networks are on the order of the number of weights (Maass, 1994; Bartlett et al., 2019). It remains unknown whether there exist neural network architectures capable of modeling rich set of classfiers with low VC dimension.
The focus of this work is on a class of neural networks with threshold activation that we refer to as hyperplane arrangement neural networks (HANNs). Using the theory of sample compression schemes (Littlestone & Warmuth, 1986), we show that HANNs can have VC dimension that is significantly smaller than the number of parameters. Furthermore, we apply this result to show that HANNs have high expressivity by proving that HANN classifiers achieve minimax-optimality when the data has Lipschitz posterior class probability in an overparametrized setting.
We benchmark the empirical performance of HANNs on a panel of 121 UCI datasets, following several recent neural network and neural tangent kernel works (Klambauer et al., 2017; Wu et al., 2018; Arora et al., 2019; Shankar et al., 2020). In particular, Klambauer et al. (2017) showed that, using a properly chosen activation, overparametrized neural networks perform competitively compared to classical shallow methods on this panel of datasets. Our experiments show that HANNs, a partially-quantized model, match the classification accuracy of the self-normalizing neural network (Klambauer et al., 2017) and the dendritic neural network (Wu et al., 2018), both of which are fullprecision models.

heading: 1.1 RELATED WORK
text: VC dimensions of neural networks. The VC-dimension Vapnik & Chervonenkis (1971) is a combinatorial measure of the complexity of a concept class, i.e., a set of classifiers. The Fundamental Theorem of Statistical Learning (Shalev-Shwartz & Ben-David, 2014, Theorem 6.8) states that a concept class has finite VC-dimension if and only if it is probably approximately correct (PAC) learnable, where the VC-dimension is tightly related to the number of samples required for PAC learning.
For threshold networks, Cover (1965); Baum & Haussler (1989) showed a VC-dimension upper bounded of O(w logw), where w is the number of parameters. Maass (1994) obtained a matching lower bound attained by a network architecture with two hidden layers. More recently, Bartlett et al. (2019) obtained the upper and lower bounds O(w` logw) and Ω(w` log(w/`)) respectively for the case when the activation is piecewise linear, where ` is the number of layers. These lower bounds are achieved by somewhat unconventional network architectures. The architectures we consider exclude these and thus we are able to achieve a smaller upper bound on the VC dimensions.
The generalization puzzle. In practice, neural networks that achieve state-of-the-art performance use significantly more parameters than samples, a phenomenon that cannot be explained by classical VC theory if the VC dimension ≥ number of weights. This has been dubbed the generalization puzzle (Zhang et al., 2021). To explain the puzzle, researchers have pursued new directions including margin-based bounds (Neyshabur et al., 2017; Bartlett et al., 2017), PAC-Bayes bounds (Dziugaite & Roy, 2017), and implicit bias of optimization methods (Gunasekar et al., 2018; Chizat & Bach, 2020). We refer the reader to the recent article by Bartlett et al. (2021) for a comprehensive coverage of this growing literature.
The generalization puzzle is not specific to deep learning. For instance, AdaBoost has been observed to continue to decrease the test error while the VC dimension grows linearly with the number of boosting rounds (Schapire, 2013). Other learning algorithms that exhibits similarly surprising behavior include random forests (Wyner et al., 2017) and kernel methods (Belkin et al., 2018).
Minimax-optimality. Whereas VC theory is distribution-independent, minimax theory is concerned with the question of optimal estimation/classification under distributional assumptions1. A minimax optimality result shows that the expected excess classification error goes to zero at the fastest rate possible, as the sample size tend to infinity. For neural networks, this often involves a hyperparameter selection scheme in terms of the sample size.
Faragó & Lugosi (1993) show minimax-optimality of (underparametrized) neural networks for learning to classify under certain assumptions on the Fourier transform of the data distribution. Schmidt-Hieber (2020) shows minimax-optimality of s-sparse neural networks for regression over Hölder classes, where at most s = O(n log n) network weights are nonzero, and n = the number of training samples. Kim et al. (2021) extends the results of Schmidt-Hieber (2020) to the classification setting, remarking that effective optimization under sparsity constraint is lacking. Kohler & Langer (2020) and Langer (2021) proved minimax-optimality without the sparsity assumption, however in an underparametrized setting. To the best of our knowledge, our result is the first to establish minimax optimality of overparametrized neural networks without a sparsity assumption.
(Partially) quantized neural networks. Quantizing some of the weights and/or activations of neural networks has the potential to reduce the high computational burden of neural networks at test time (Qin et al., 2020). Many works have focused on the efficient training of quantized neural networks to close the performance gap with full-precision architectures (Hubara et al., 2017; Rastegari et al., 2016; Lin et al., 2017). Several works have observed that quantization of the activations, rather than of the weights, leads to a larger accuracy gap (Cai et al., 2017; Mishra et al., 2018; Kim et al., 2019).
Towards explaining this phenomenon, researchers have focused on understanding the so-called coarse gradient, a term coined by Yin et al. (2019), often used in training QNNs as a surrogate for the usual gradient. One commonly used heuristic is the straight-through-estimator (STE) first introduced in an online course by Hinton et al. (2012). Theory supporting the STE heuristic has recently been studied in Li et al. (2017) and Yin et al. (2019).
1Without distributional assumptions, no classifier can be minimax optimal in light of the No-Free-Lunch Theorem (Devroye, 1982).
QNNs have also been analyzed from other theoretical angles, including mean-field theory (Blumenfeld et al., 2019), memory capacity (Vershynin, 2020), Boolean function representation capacity (Baldi & Vershynin, 2019) and adversarial robustness (Lin et al., 2018). Of particular relevance to our work, Maass (1994) constructed an example of a QNN architecture with VC dimension on the order of the number of weights in the network. In contrast, our work shows that there exist QNN architectures with much smaller VC dimensions.
Sample compression schemes. Many concept classes with geometrically structured decision regions, such as axis-parallel rectangles, can be trained on a properly chosen size σ subset of an arbitrarily large training dataset without affecting the result. Such a concept class is said to admit a sample compression schemes of size σ, a notion introduced by Littlestone & Warmuth (1986) who showed that the VC dimension of the class is upper bounded by O(σ). Furthermore, the authors posed the Sample Compression Conjecture. See Moran & Yehudayoff (2016) for the best known partial result and an extensive review of research in this area. Besides the conjecture, sample compression schemes have also been applied to other long-standing problems in learning theory (Hanneke et al., 2019; Bousquet et al., 2020; Ashtiani et al., 2020). To the best of our knowledge, our work is the first to apply sample compression schemes to neural networks.

heading: 2 NOTATIONS
text: The set of real numbers is denoted R. The unit interval is denoted [0, 1]. For an integer k ≥ 1, let [k] = {1, . . . , k}. We use X to denote the feature space, which in this work will either be Rd or [0, 1]d where d ≥ 1 is the ambient dimension/number of features. Denote by I{input} the indicator function which returns 1 if input is true and 0 otherwise. The sign function is given by σsgn(t) = I{t ≥ 0}− I{t < 0}. For vector inputs, σsgn applies entry-wise. The set of labels for binary classification is denoted B := {±1}. Joint distributions on X × B are denoted by P , whereX,Y ∼ P denotes a random instance-label pair distributed according to P . Let f : X → B be a binary classifier. The risk with respect to P is denoted byRP (f) := P (f(X) 6= Y ). For an integer n ≥ 1, the empirical risk is the random variable R̂P,n(f) := 1n ∑n i=1 I{f(Xi) 6= Yi}, where (X1, Y1), . . . , (Xn, Yn) ∼ P are i.i.d. The Bayes risk inff :X→BRP (f) with respect to P is denoted by R∗P .
Let f, g : {1, 2, . . . } → R≥0 be nonnegative functions on the natural numbers. We write f g if there exists α, β > 0 such that for all n = 1, 2, . . . we have αg(n) ≤ f(n) ≤ βg(n).

heading: 3 HYPERPLANE ARRANGEMENT NEURAL NETWORKS
text: A hyperplane H in Rd is specified by its normal vector w ∈ Rd and bias b ∈ R. The mapping x 7→ σsgn(w>x + b) indicates the side of H that x lies on, and hence induces a partition of Rd into two halfspaces. A set of k ≥ 1 hyperplanes is referred to as a k-hyperplane arrangement, and specified by a matrix of normal vectors and a vector of offsets:
W = [w1 · · ·wk] ∈ Rd×k and b = [b1, . . . , bk]>. Let qW,b(x) := σsgn(W>x + b) for all x ∈ Rd. The vector qW,b(x) ∈ Bk is called a sign vector and the set of all realizable sign vectors is denoted SW,b := {qW,b(x) : x ∈ Rd}. Each sign vector s ∈ SW,b uniquely defines a set {x ∈ Rd : qW,b(x) = s} known as a cell of the hyperplane arrangement. The set of all cells forms a partition of Rd. For an example, see Figure 1-left.
A classical result in the theory of hyperplane arrangement due to Buck (1943) gives the following tight upper bound on the number of distinct sign patterns/cells:
|SW,b| ≤ ( k
≤ d
) := { 2k : k < d,( k 0 ) + ( k 1 ) + · · ·+ ( k d ) : k ≥ d. (1)
See Fukuda (2015) Theorem 10.1 for a simple proof. A hyperplane arrangement classifier assigns a binary label y ∈ B to a point x ∈ Rd solely based on the sign vector qW,b(x). Definition 3.1. Let BX be the set of all functions from X to B. A concept class C over X is a subset of BX . Fix r, k positive integers, r ≤ min{d, k}. Let Boolk be the set of all Boolean functions
Bk → B. The hyperplane arrangement classifier class is the concept class, denoted HAC(d, r, k), over Rd defined by
HAC(d, r, k) = {h ◦ qW,b : h ∈ Boolk, qW,b(x) := σsgn(W>x+ b), W ∈ Rd×k, rank(W) ≤ r, b ∈ Rk}.
See Figure 2 for a graphical representation of HAC(d, r, k). When the set of Boolean functions is realized by a neural network, we refer to the resulting classifier as a hyperplane arrangement neural network (HANN). Remark 3.2. Consider a fixed hyperplane arrangement W, b and Boolean function h ∈ Boolk. When performing prediction with the classifer h ◦ qW,b, the feature vector x is mapped to a sign vector to which h is applied. Thus, we do not need to know how h behaves outside of SW,b. The restriction of h to SW,b is a partially defined Boolean function or a lookup table.
Remark 3.3. The hidden layer of width r in Figure 2 allows the user to impose the restriction that the hyperplane arrangement classifier depends only on r relevant features, which can be either learned or defined by data preprocessing. When r = d, no restriction is imposed. In this case, the input layer is directly connected to the Boolean layer. This is consistent with Definition 3.1 where the rank constraint rank(W) ≤ r becomes trivial.
Our next goal is to upper bound the VC dimension of HAC(d, r, k).
Definition 3.4 (VC-dimension). Let C ⊆ BX be a concept class overX . A set S := {x1, . . . , xn} ⊆ X is shattered by C if for all sequences (y1, . . . , yn) ∈ Bn, there exists f ∈ C such that f(xi) = yi for all i ∈ [n]. The VC-dimension of C is defined as
VC(C) = sup{|S| : S ⊆ X , S is shattered by C}.
The VC-dimension has many far-reaching consequences in learning theory and, in particular, classification. One of these consequences is a sufficient (in fact also necessary) condition for uniform convergence in the sense of the following well-known theorem. See Shalev-Shwartz & Ben-David (2014) Theorem 6.8.
Theorem 3.5. Let C be a concept class over X . There exists a constant C > 0 such that for all joint distributions P on X ×B and all f ∈ C, we have |R̂P,n(f)−RP (f)| ≤ C √ (VC(C) + log(1/δ))/n with probability at least 1− δ with respect to the draw of (X1, Y1), . . . , (Xn, Yn).
The above VC bound is useless in the overparametrized setting if VC(C) = Θ(# of weights) because # of weights > n and therefore the VC bound does not vanish. We now present our main result: an upper bound on the VC dimension of HAC(d, r, k). Theorem 3.6. Let d, r, k ≥ 1 be integers and HAC(d, r, k) be defined as in Definition 3.1. Then
VC(HAC(d, r, k)) ≤ 8 · ( k(d+ 1) + k(d+ 1)(1 + dlog2 ke) + ( k
≤ r
)) .
In the next section, we will prove this result using a sample compression scheme. Before proceeding, we comment on the significance of the result. Remark 3.7. Since ( k ≤r )
= O(kr), we have VC(HAC(d, r, k)) = O(kr + dk log k) which only involves the input dimension d and the width of the first two hidden layers r and k. For constant d and r ≥ 2, this reduces to VC(HAC(d, r, k)) = O(kr). In particular, the number of weights used by an architecture to implement the Boolean function h does not affect the VC dimension at all and can be even infinitely wide such as in Neural Tangent Kernels (Jacot et al., 2018).
For instance, Mukherjee & Basu (2017) Lemma 2.1 states that a 1-hidden layer neural network with ReLU activation can model any k-input Boolean function if the hidden layer has width ≥ 2k. Note that this network uses ≥ k2k weights, and k2k kr for fixed r and k large. Baldi & Vershynin (2019) study implementation of Boolean functions using threshold networks. A consequence of their Theorem 9.3 is that a 2-hidden layer network with widths ≥ c2k/2/ √ k can implement all k input Boolean functions, where c is a constant not depending on k. This requires ≥ c22k/k weights which again is exponentially larger than kr. Furthermore, this lower bound on the weights is also necessary as k →∞. Remark 3.8. Using the memorization approach of Vershynin (2020); Rajput et al. (2021), it is also possible to implement HAC(d, r, k) with far fewer weights than in Remark 3.7. This can be done by applying Theorem 1 of Rajput et al. (2021) to memorize the ( k ≤r ) distinct sign vectors in Rk.

heading: 4 A SAMPLE COMPRESSION SCHEME
text: In this section, we will construct a sample compression scheme for HAC(d, r, k). As alluded to in the Related Work section, the size of a sample compression scheme upper bounds the VC-dimension of a concept class, which will be applied to prove Theorem 3.6. We first recall the definition of sample compression schemes with side information introduced in Littlestone & Warmuth (1986). Definition 4.1. Let C be a concept class. A length n sequence {(xi, yi) ∈ X ×B}i∈[n] is C-labelled if there exists f ∈ C such that f(xi) = yi for all i ∈ [n]. Denote by LC(n) the set of C-labelled sequences of length at most n. Denote by LC(∞) the set of all C-labelled sequences of finite length. The concept class C over X has an m-sample compression scheme with s-bits of side information if there exists a pair of maps (ρ, κ) where
κ : LC(∞)→ LC(m)× Bs, ρ : LC(m)× Bs → BX
such that for all C-labelled sequences S := {(xi, yi)}i∈[n], we have ρ(κ(S))(xi) = yi for all i ∈ [n]. The size of the sample compression scheme is size(ρ, κ) := m+ s.
Intuitively, κ and ρ can be thought of as the compression and the reconstruction maps, respectively. The compression map κ keepsm elements from the training set and s bits of additional information, which ρ uses to reconstruct a classifier that correctly labels the uncompressed training set.
The main result of this section is: Theorem 4.2. HAC(d, r, k) has a sample compression scheme (ρ, κ) of size
size(ρ, κ) = k(d+ 1) + k(d+ 1)(1 + dlog2 ke) + ( k
≤ r
) .
We remark that both the hyperplane arrangement (W, b) and the Boolean function h contribute to the number of parameters/weights. The rest of this section will work toward the proof of Theorem 4.2. The following result states that a C-labelled sequence can be labelled by a hyperplane arrangement classifier of a special form. Proposition 4.3. Let {(xi, yi)}i∈[n] be HAC(d, r, k)-labelled. Then there exist V = [v1 · · · vk] ∈ Rd×k, c ∈ Rk and h ∈ Boolk such that for all i ∈ [n], we have 1) yi = h(σsgn(V>xi + c)), 2) rank(V) ≤ r and 3) |v>j xi + cj | ≥ 1 for all i ∈ [n], j ∈ [k].
The proof, given in Appendix A.1, is similar to showing the existence of a max-margin separating hyperplane for a linearly separable dataset. Definition 4.4. Let I be a finite set and let ai ∈ Rn for each i ∈ I . Let A = {ai}i∈I . A conical combination of A is a linear combination ∑ i∈I λiai where the weights λi ∈ R≥0 are nonnegative. The conical hull of A, denoted coni(A), is the set of all conical combinations of A, i.e., coni({ai}i∈I) := {∑ i∈I λiai : λi ∈ R≥0, ∀i ∈ I } .
The result below follows easily from the Carathédory’s theorem for the conical hull (Lovász & Plummer, 2009). For the sake of completeness, we included the proof in Appendix A.2. Proposition 4.5. Let a1, . . . , am ∈ Rn and b1, . . . , bm ∈ R. For each subset I ⊆ [m], define PI := {x ∈ Rn : a>i x ≤ bi ∀i ∈ I}. Suppose that P[m] is nonempty. Then 1) minx∈PI 12‖x‖ 2 has a unique minimizer, denoted by x∗I below, and 2) there exists a subset J ⊆ [m] such that |J | = min{m,n} and for all I ⊆ [m] with J ⊆ I , we have x∗[m] = x ∗ I .
Proof of Theorem 4.2. Let (xi, yi) be HAC(d, r, k)-realizable, and V, c and h be as in Proposition 4.3. For each i ∈ [n], define the Boolean vectors si := σsgn(V>xi + c) ∈ {±1}k and sij = σsgn(v > j xi + cj) denote the j-th entry of si. Note that sij(v > j xi + cj) = |v>j xi + cj | ≥ 1.
We first outline the steps of the proof:
1. Using a subset of the samples {(xi` , yi`) : ` ∈ [d(k+1)]} with additional k(d+1)(1+dlog2 ke) bits of side information {(si`j` , j`) : ` ∈ [d(k + 1)]}, we can reconstruct W, b such that σsgn(W > xi + b) = si for all i ∈ [n].
2. Using an additional subset of samples {(xι` , yι`) : ` = 1, . . . , ( k ≤r ) } in conjunction with the
W, b reconstructed in the previous step, we can find g ∈ Boolk such that g(si) = h(si) for all i.
Now, consider the set P := { (W, b) ∈ Rd×k × Rk : sij(w>j xi + bj) ≥ 1, ∀i ∈ [n], j ∈ [k] } .
Note that P is a convex polyhedron in (d + 1)k-dimensional space. Let (W, b) be the minimum norm element of P . Note that σsgn(W > xi + b) = σsgn(V >xi + c) = si by construction.
By Proposition 4.5, there exists a set of tuples
{(i`, j`)}`=1,...,(d+1)k , where (i`, j`) ∈ [n]× [k]
such that W, b is also the minimum norm element of P ′ := { (W, b) ∈ Rd×k × Rk : si`j`(w>j`xi` + bj`) ≥ 1, ` = 1, . . . , d(k + 1) } .
To encode the defining equations of P ′, we need to store
samples {(xi` , yi`)} d(k+1) `=1 and side information {(si`j` , j`)} d(k+1) `=1 . (2)
Note that each si`j` requires 1 bit while each j` ∈ [k] requires dlog2 ke bits. In total, encoding P ′ requires storing d(k + 1) samples and d(k + 1)(1 + dlog2 ke) of bits. To reconstruct g ∈ Boolk that agrees with h on all the samples, it suffices to know h when restricted to {si}ni=1. Since {si}ni=1 is a subset of SW,b, we have by eq. (1) that |{si}ni | ≤ ( k ≤r ) . Thus,
{si}ni=1 has at most ( k ≤r ) unique elements. Let { sι` : ` = 1, . . . , ( k ≤r )}
be a set containing all such unique elements. Thus, we store
samples {(xι` , yι`) : ` = 1, . . . , ( k ≤r ) }. (3)
Using W, b as defined above, we have sι` = σsgn(W > xι` + b). Now, simply choose g such that g(sι`) = yι` for all ` = 1, . . . , ( k ≤r ) .
To summarize, we formally define the compression and reconstruction functions (κ, ρ). Let κ take the full sample {(xi, yi)}ni=1 and output the subsample (and side information) in eq. (2) and eq. (3). The reconstruction function ρ first constructs W, b using eq. (2). Next, ρ constructs g using W, b and the samples of eq. (3).
Now, the following result together with the sample compression scheme for HAC(d, r, k) we constructed imply Theorem 3.6 from the previous section.
Theorem 4.6 (Littlestone & Warmuth (1986)). If C has sample compression scheme (ρ, κ), then VC(C) ≤ 8 · size(ρ, κ). Remark 4.7. Note that the reconstruction function ρ is not permutation-invariant. Furthermore, the overall sample compression scheme ρ, κ is not stable in the sense of Hanneke & Kontorovich (2021). In general, sample compression schemes with permutation-invariant ρ (Floyd & Warmuth, 1995) and stable sample compression schemes (Hanneke & Kontorovich, 2021) enjoy tighter generalization bounds compared to ordinary sample compression schemes. We leave as an open question whether HAC(d, r, k) has such specialized compression schemes.

heading: 5 MINIMAX-OPTIMALITY FOR LEARNING LIPSCHITZ CLASS
text: In this section, we show that empirical risk minimization (ERM) with respect to the 0-1 loss over HAC(d, r, k), for properly chosen r and k, is minimax optimal for classification where the posterior class probability function is L-Lipschitz, for fixed L > 0. Furthermore, the choices for r and k is such that the associated HANN, the neural network realization of HAC(d, r, k), is overparametrized for the Boolean function implementations discussed in Remark 3.7.
Below, let X ∈ [0, 1]d and Y ∈ B be the random variables corresponding to a sample and label jointly distributed according to P . Write ηP (x) := P (Y = 1|X = x) for the posterior class probability function.
Let Σ(L, [0, 1]d) denote the class of L-Lipschitz functions f : [0, 1]d → R, i.e.,
|f(x)− f(x′)| ≤ L‖x− x′‖2, ∀x, x′ ∈ [0, 1]d.
The following minimax lower bound result2 concerns classification when ηP is L-Lipschitz:
Theorem 5.1 (Audibert & Tsybakov (2007)). There exists a constant C > 0 such that
inf f̃n sup P : ηP∈Σ(L,[0,1]d)
E[R(f̃n)]−R∗P ≥ Cn− 1 d+2 .
The infimum above is taken over all possible learning algorithms f̃n, i.e., mappings from (X × B)n to Borel measurable functions X → B. When f̂n is an empirical risk minimizer (ERM) over HAC(d, r, k) where d = r for k = n 1 d+2 , this minimax rate is achieved.
Theorem 5.2. Let d ≥ 1 be fixed. Let f̂n be an ERM over HAC(d, d, k) where k = k(n) n 1
d+1 . Then there exists a constant C ′ such that
sup P : ηP∈Σ(L,[0,1]d)
E[R(f̂n)]−R∗P ≤ C ′n− 1 d+2 .
2The result we cite here is a special case of (Audibert & Tsybakov, 2007, Theorem 3.5), which gives minimax lower bound for when ηP has additional smoothness assumptions.
Proof sketch (see Appendix A.3 for full proof). We first show that the histogram classifier over the standard partition of [0, 1]d into smaller cubes is an element of C := HAC(d, d, k), thus reducing the problem to proving minimax-optimality of the histogram classifier. Previous work Györfi et al. (2006) Theorem 4.3 established this for the histogram regressor. The analogous result for the histogram classifier, to the best of our knowledge, has not appeared in the literature and thus is included for completeness.
The neural network implementation of HAC(d, d, k) where k n1/(d+2) in Theorem 5.2 can be overparametrized. Using either the 1- or the 2-hidden layer neural network implementations of Boolean functions as in Remark 3.7, the resulting HANN is overparametrized and has number of weights either ≥ k2k or ≥ c22k/k respectively. Both k2k and c22k/k n exponentially while VC(HAC(d, d, k)) = o(n).

heading: 6 EMPIRICAL RESULTS
text: In this section, we discuss experimental results of using HANNs for classifying synthetic and real datasets. Our implementation uses TensorFlow (Abadi et al., 2016) with the Larq (Geiger & Team, 2020) library for training neural networks with threshold activations. Note that Theorem 5.2 holds for ERM with respect to the 0-1 loss over HANNs, which is intractable in practice. Furthermore, our theory is for binary classification, while some of the datasets in the experiments are multiclass.
Synthetic datasets. We apply a HANN (model specification shown in Figure 3-top left) to the MOONS synthetic dataset with two classes with the hinge loss.
The heuristic for training networks with threshold activation can significantly affect the performance (Kim et al., 2019). We consider two of the most popular heuristics: the straight-through-estimator (SteSign) and the SwishSign, introduced by Hubara et al. (2017) and Darabi et al. (2019), respectively. Below, we use SwishSign since it reliably leads to higher validation accuracy (Figure 3- bottom left), consistent with the finding of Darabi et al. (2019).
The width of the hidden layer is 210 = 1024. Thus, by Mukherjee & Basu (2017) Lemma 2.1, the model can assign labels to the bolded cells arbitrarily without changing the training loss. Nevertheless, the optimization appears to be biased toward a topologically simpler classifier. This behavior is consistently reproducible. See Figure 7.
Real-world datasets. Klambauer et al. (2017) introduced self-normalizing neural networks (SNN) which were shown to outperform other neural networks on a panel of 121 UCI datasets. Subsequently, Wu et al. (2018) proposed the dendritic neural network architecture, which further im-
proved classification performance on this panel of datasets. Following their works, we evaluate the performance of HANNs on the 121 UCI datasets.
A crucial hyperparameter for HANN is the number of hyperplanes k. We ran the experiments with k ∈ {15, 100} to test the impact on accuracy. The Boolean function h is implemented as a 1-hidden layer residual network (He et al., 2016) of width 1000. The logistic loss is used.
We use the same train, validation, and test sets as in Klambauer et al. (2017). The reported accuracies on the held-out test set are based on the model with the highest validation accuracy. The models will be referred to as HANN15 and HANN100, respectively. The results are shown in Figure 4. The accuracies of SNN and DENN are obtained from Table A1 in the supplemental materials of Wu et al. (2018). Full details for the training and accuracy tables can be found in the appendix.
Comparing HANN with SNN and DENN over the UCI datasets
The HANN15 model (top row of Figure 4) already achieves median accuracy within 1.5% of both SNN and DENN. With the larger HANN100 model (bottom row), the gap is reduced to zero. The largest training set in this panel of datasets has size 77904. The HANN15 and HANN100 models use ≈ 104 and 105 weights, respectively. By comparison, the average numbers of weights used by SNN and DENN are both ≥ 5 ∗ 105. Details on these estimates are included in Appendix C. Thus, all three models considered here are overparametrized.

heading: 7 DISCUSSION
text: We have introduced an architecture for which the VC theorem can be used to prove minimaxoptimality of ERM over HANNs in an overparametrized setting with Lipschitz posterior. To our knowledge, this is the first time VC theory has been used to analyze the performance of a neural network in the overparametrized regime. Furthermore, the same architecture leads to state-of-the-art performance over a benchmark collection of unstructured datasets.
To the best of our knowledge, no existing theoretical bound for overparametrized NNs yields meaningful results. Yet there is immense interest in understanding what aspects of deep NNs can explain their performance, even if the bounds aren’t yet small (Bartlett et al., 2017; Neyshabur et al., 2017; Jiang et al., 2019). Our work shows that the compressibility of the network, as reflected by the sample compression scheme, is a useful avenue, and one that has not previously been explored – ours is the first work applying sample compression to NNs. This seems likely to open the door to further analysis of quantized NNs.
REPRODUCIBILITY STATEMENT
All anonymized code for downloading and parsing the data, training the models, and generating plots in this manuscript are submitted along with the manuscript to OpenReview. Complete proofs for all novel results are included in the main article or in an appendix.

heading: A PROOFS
text: A.1 PROOF OF PROPOSITION 4.3
By definition, there exists h ∈ Boolk, W ∈ Rd×k of rank at most r, and b ∈ Rk such that yi = h(σsgn(W >xi + b)).
Now, let j ∈ [k] be fixed. Since |w>j xi + bj | ≥ 0 for all i ∈ [n], there exists a small perturbation c̃j of bj such that |w>j xi + c̃j | > 0 for all i ∈ [n]. Now, let λj := mini∈[n] |w>j xi + c̃j | which is positive. Define vj := wj/λj and cj = c̃j/λj , we have |v>j xi + cj | ≥ 1 for all i ∈ [n], as desired. Note that rank(V) = rank(W).
A.2 PROOF OF PROPOSITION 4.5
If m ≤ n, then the result holds trivially by letting J = [m]. Below, suppose that m > n. Let gi(x) = a > i x − bi for each i ∈ [m] and f(x) = 12‖x‖ 2 2. Then ∇f(x) = x and ∇gi(x) = ai. By definition, x∗I is a minimizer of
min x∈Rn
f(x) s.t. gi(x) ≤ 0, ∀i ∈ I,
which is a convex optimization with strongly convex objective. Thus, the minimizer x∗I is unique and furthermore is the unique element x of Rn satisfying the KKT conditions:
x ∈ PI and ∃ a set of nonnegative weights {λi}i∈I such that − x = ∑ i∈I λiai.
Thus, x∗I can be equivalently characterized as the unique element of x ∈ Rn satisfying
x ∈ PI and − x ∈ coni({ai}i∈I). (4)
In particular, x∗[m] ∈ P[m] and −x ∗ [m] ∈ coni({ai}i∈[m]). By the Carathédory’s theorem for the conical hull (Lovász & Plummer, 2009), there exists I ⊆ [m] such that |I| = n and −x∗[m] ∈ coni({ai}i∈I). Thus, for any J ⊆ [m] such that I ⊆ J , we have −x∗[m] ∈ coni({ai}i∈J). Furthermore, J ⊆ [m] implies PJ ⊇ P[m]. In particular, x∗[m] ∈ PJ . Putting it all together, we have x∗[m] ∈ PJ and −x ∗ [m] ∈ coni({ai}i∈J). By the uniqueness, we have x ∗ J = x ∗ [m].
A.3 PROOF OF THEOREM 5.2
In this proof, the constant C does not depending on n, and may change from line to line.
We fix a joint distribution P such that ηP ∈ Σ(L, [0, 1]d) throughout the proof. Thus, the notation for risks will omit the P in their subscript, e.g., we write R̂n(f) instead of R̂P,n(f) andR∗ instead of R∗P . Below, let β > α > 0 be constants such that αdn 1/(d+2) ≤ k ≤ βdn1/(d+2). Let k̃ := dk/de.
Let R1,R2, . . . ,Rk̃d denote the hypercubes of side length ` = 1/k̃ forming a partition of [0, 1]d. For each i ∈ [k̃d], letR−i := {x ∈ Ri : ηP (x) < 1/2} andR + i := {x ∈ Ri : ηP (x) ≥ 1/2}.
Let f̃ : [0, 1]d → B be the classifier such that
f̃(x) =
{ +1 : x ∈ Ri, ∫ Ri ηP (x)dP (x) ≥ ∫ Ri(1− ηP (x))dP (x)
−1 : x ∈ Ri, ∫ Ri ηP (x)dP (x) < ∫ Ri(1− ηP (x))dP (x).
In other words, f̃ classifies all x ∈ Ri as +1 if and only if P (Y = 1|X ∈ Ri) ≥ 1/2. This is commonly referred to as the histogram classifier (Györfi et al., 2006). It is easy to see that
P (f̃(X) 6= Y,X ∈ Ri) = min {∫ Ri (1− ηP (x))dP (x), ∫ Ri ηP (x)dP (x) } For the remainder of this proof, we write “ ∑ i” to mean “ ∑ i∈[k̃d]”. Thus,
R(f̃) = ∑ i P (f̃(X) 6= Y,X ∈ Ri) = ∑ i min {∫ Ri (1− ηP (x))dP (x), ∫ Ri ηP (x)dP (x) } .
Next, we note that f̃ ∈ HAC(d, d, k). To see this, let j ∈ [d]. Take Hj1, . . . ,Hj(k̃−1) ⊆ Rd to be the hyperplanes perpendicular to the j-th coordinate where, for each ` ∈ [k̃], Hj` intersects the j-th coordinate axis at `/k̃. Consider the hyperplane arrangement consisting of all {Hj`}j∈[d],`∈[k̃−1] and let {C1, C2, . . . } be its cells. Then {C1 ∩ [0, 1]d, C2 ∩ [0, 1]d, . . . } = {R1, . . . ,Rk̃d} is the partition of [0, 1]d by 1/k̃ side length hypercubes. See Figure 5.
Let W be the matrix of normal vectors and b be the vector of offsets representing this hyperplane arrangement, which requires d(k̃ − 1) = d(dk/de − 1) ≤ d(k/d) = k hyperplanes. Since f̃ is constant onRi, there exists a Boolean function h ∈ Boolk such that h ◦ qW,b|[0,1]d = f̃ . From this, we conclude that f̃ ∈ HAC(d, d, k).
Thus R̂n(f̂n)− R̂n(f̃) ≤ 0 and so
R(f̂n)−R∗ = R(f̂n)− R̂n(f̂n) + R̂n(f̂n)− R̂n(f̃)︸ ︷︷ ︸ ≤0 +R̂n(f̃)−R(f̃) +R(f̃)−R∗
≤ R(f̂n)− R̂n(f̂n)︸ ︷︷ ︸ Term 1 + R̂n(f̃)−R(f̃)︸ ︷︷ ︸ Term 2 +R(f̃)−R∗︸ ︷︷ ︸ Term 3 .
We now bound Terms 1 and 2 using the uniform deviation bound. From Theorem 3.6, we know that there exists a constant C independent of n such that
VC(HAC(d, d, k)) ≤ 8 · ( k(d+ 1) + k(d+ 1)(1 + dlog2(k)e) + ( k
≤ d
)) ≤ Ckd.
Thus, by Theorem 3.5 with δ = 1/(2n) and a union bound, with probability at least 1− 1/n
max { |R̂n(f̂n)−R(f̂n)|, |R̂n(f̃)−R(f̃)| } ≤ C √ kd + log(n)
n (5)
for some C > 0.
Next, we focus on Term 3. Recall that
R∗ = ∫ [0,1]d min{ηP (x), 1− ηP (x)}dP (x) = ∑ i ∫ Ri min{ηP (x), 1− ηP (x)}dP (x)
and that
R(f̃) = ∑ i min {∫ Ri ηP (x)dP (x), ∫ Ri 1− ηP (x)dP (x) } .
Fix some i ∈ [kd]. Our goal now is to bound the difference between the i-th summands in the above expressions for R(f̃) and R∗:
min {∫ Ri ηP (x)dP (x), ∫ Ri 1− ηP (x)dP (x) } − ∫ Ri min{ηP (x), 1− ηP (x)}dP (x). (6)
First, consider the case that
min {∫ Ri ηP (x)dP (x), ∫ Ri 1− ηP (x)dP (x) } = ∫ Ri ηP (x)dP (x). (7)
We claim that there must exist x0 ∈ Ri such that ηP (x0) ≤ 1/2. Suppose ηP (x) > 1/2 for all x ∈ Ri. Then ηP (x) > 1/2 > 1− ηP (x). Since ηP (x) is continuous, this would contradict eq. (7). Continue assuming eq. (7), we further divide into two subcases: (1) ηP (x) ≤ 1/2 for all x ∈ Ri, and (2) there exists some x1 ∈ Ri such that ηP (x1) > 1/2. Under subcase (1), min{ηP (x), 1− ηP (x)} = ηP (x) for all x ∈ Ri in which case eq. (6) = 0.
Under subcase (2), since ηP (x0) ≤ 1/2 < ηP (x1), we know by the intermediate value theorem that there must exist x′ ∈ Ri such that ηP (x′) = 1/2. Now,
eq. (6) = ∫ Ri (ηP (x)−min{ηP (x), 1− ηP (x)})dP (x)
≤ ∫ R+i (ηP (x)−min{ηP (x), 1− ηP (x)})dP (x)
+ ∫ R−i (ηP (x)−min{ηP (x), 1− ηP (x)})dP (x)
= ∫ R+i (ηP (x)− (1− ηP (x))dP (x) ∵ Definition ofR±i
+ ∫ R−i (ηP (x)− ηP (x))dP (x)
= ∫ R+i (2ηP (x)− 1)dP (x)
= 2 ∫ R+i (ηP (x)− ηP (x′))dP (x) ∵ 2ηP (x′) = 1
≤ 2L ∫ R+i ‖x− x′‖2dP (x) ≤ 2L √ dPr(Ri)/k̃ ∵ ‖x− x′‖2 ≤ √ d‖x− x′‖1 ≤ √ d(1/k̃)
≤ 2Ld3/2 Pr(Ri)/k ∵ 1/k̃ = 1/dk/de ≤ 1/(k/d) = d/k.
Thus, under assumption eq. (7), we have proven that eq. (6) ≤ 2Ld3/2/k. For the other assumption, i.e., the minimum in eq. (7) is attained by ∫ Ri 1 − ηP (x)dP (x), a completely analogous argument again shows that eq. (6) ≤ 2Ld3/2/k. Putting it all together, we have
R(f̃n)−R∗ ≤ 2Ld3/2 ∑ i P (Ri)/k = 2Ld3/2/k. (8)
We have shown that, with probability at least 1− 1/n,
R(f̂n)−R∗ ≤ C √ kd + log(n)
n +
2Ld3/2
k .
Using αdn1/(d+2) ≤ k ≤ βdn1/(d+2), we have with probably at least 1− 1/n that
R(f̂n)−R∗ ≤ C √ kd + log(n)
n +
2Ld3/2
k ≤ C √ (βd)dnd/(d+2) + log(n)
n +
2Ld3/2
αdn1/(d+2)
≤ C
(√ nd/(d+2)
n + n−1/(d+2)
) ∵ log(n) = o(n1/d+2)
= C (√ n−2/(d+2) + n−1/(d+2) )
≤ Cn− 1 d+2 .
Taking expectation, we have E[R(f̂n)]−R∗ ≤ (1− 1/n)Cn− 1 d+2 + 1/n · 1 ≤ Cn− 1 d+2 .

heading: B TRAINING DETAILS
text: Data preprocessing. The pooled training and validation data is centered and standardized using the StandardScaler function from sklearn. The transformation is also applied to the test data, using the centers and scaling from the pooled training and validation data:
scaler = StandardScaler().fit(X_train_valid) X_train_valid = scaler.transform(X_train_valid) X_test = scaler.transform(X_test)
If the feature dimension and training sample size are both > 50, then the data is dimension reduced to 50 principal component features:
if min(X_train_valid.shape) > 50: pca = PCA(n_components = 50).fit(X_train_valid) X_train_valid = pca.transform(X_train_valid) X_test = pca.transform(X_test)
Note that this is equivalent to freezing the weights between the Input and the Latent layer in Figure 2.
Validation and test accuracy. Every 10 epochs, the validation accuracy during the past 10 epochs are averaged. A smoothed validation accuracy is calculated as follows:
val_acc_sm = (1-sm_param)*val_acc_sm + sm_param*val_acc_av ## Variable description: # sm_param = 0.1 # val_acc_av = average of the validation in the past 10 epochs # val_acc_sm = smoothed validation accuracy
The predicted test labels is based on the snapshot of the model at the highest smoothed validation accuracy, at the end once max epochs is reached.
Heuristic for coarse gradient of the threshold function. We use the SwishSign from the Larq library (Geiger & Team, 2020).
# import larq as lq qtz = lq.quantizers.SwishSign()
Dropout. During training, dropout is applied to the Boolean output of the threshold function, i.e, the variables B1, B2, . . . , Bk in Figure 2. This improves generalization by preventing the training accuracy from reaching 100%.
# from tensorflow.keras.layers import Dense, Dropout hyperplane_enc = Dense(n_hyperplanes, activation = qtz)(inputs) hyperplane_enc = Dropout(dropout_rate)(hyperplane_enc)
Implementation of the Boolean function. For the Boolean function h, we use a 1-hidden layer residual network (He et al., 2016) with 1000 hidden nodes:
# from tensorflow.keras.layers import Dense, Add # output_dim = num_classes n_hidden = 1000 hidden = Dense(n_hidden, activation="relu")(hyperplane_enc) out_hidden = Dense(output_dim, activation = "linear")(hidden) out_skip = Dense(output_dim, activation = "linear")(hyperplane_enc) outputs = Add()([out_skip,out_hidden])
Hyperparameters. HANN15 is trained with a hyperparameter grid of size 3 where only the dropout rate is tuned. The hyperparameters are summarized in Table 2. The model with the highest smoothed validation accuracy is chosen.
The model HANN15 is trained with the following hyperparameters:
For HANN100, we only used 1 set of hyperparameters.

heading: C PARAMETER COUNTS
text: The widest part of HANN15 and HANN100 models are the weights mapping from Bk (k = number of hyperplanes) to R1000 (1000 = number of hidden layer of the boolean function) where k ∈ {15, 100}. Thus, the two HANN models use ≥ 15 × 1000 ≥ 104 and ≥ 100 × 1000 = 105 weights, respectively.
The weight count estimates for the Self-normalized Neural Network (SNN) and Dendritic Neural Network (DENN) use the formula (# layers − 1)× (# neurons per layer)2. For the Self-normalized Neural Network (SNN), average number of layers = 10.8, and the number of neurons per layers≥ 256, found on page 7 and Table A4 of Klambauer et al. (2017), respectively. The number of weights is ≥ (10− 1) ∗ (2562) = 655, 360 weights. The parameters for the dendritic neural network (DENN) is found in the public GitHub repository xiangwenliu/DENN of Wu et al. (2018) which lists number of layers = 3 and number of neurons per layer = 512, found on line 41 and 52 of train uci.py, respectively. The number of weights is ≥ (3− 1) ∗ (5122) = 524, 288 weights.

heading: D ADDITIONAL PLOTS
text: Multiclass hinge versus cross-entropy loss. Figure 6 shows the accuracy differences when the Weston-Watkins hinge loss is used. Compared to the results shown in Figure 4, the performance for HANN100 is slightly worse and the performance for HANN15 is slightly better.
Comparing HANN with SNN and DENN over the UCI datasets
Implicit bias for low complexity decision boundary. In Figure 7, we show additional results ran with the same setting for the MOONS synthetic dataset as in the Empirical Results section. From the perspective of the training loss, the label assignment in the bold-boundary regions is irrelevant. Nevertheless, the optimization consistently appears to be biased toward the geometrically simpler classifier, despite the capacity for fitting complex classifiers.

heading: E TABLE OF ACCURACIES
text: Below is the table of accuracies used to make Figure 4. The last column “HANN100trn” records the training accuracy at the epoch of the highest validation accuracy.
DSName HANN15 HANN100 SNN DENN HANN100trn
abalone 63.41 65.13 66.57 66.38 70.60 acute-inflammation 100.00 100.00 100.00 100.00 100.00 acute-nephritis 100.00 100.00 100.00 100.00 100.00 adult 84.32 85.04 84.76 84.80 86.35 annealing 47.00 74.00 76.00 75.00 96.81 arrhythmia 62.83 64.60 65.49 67.26 97.19 audiology-std 56.00 68.00 80.00 76.00 99.79 balance-scale 92.95 96.79 92.31 98.08 98.32 balloons 100.00 100.00 100.00 100.00 100.00 bank 88.50 88.05 89.03 89.65 95.62 blood 75.94 75.40 77.01 73.26 82.03 breast-cancer 70.42 63.38 71.83 69.01 86.63 breast-cancer-wisc 97.71 98.29 97.14 97.71 98.65 breast-cancer-wisc-diag 97.89 98.59 97.89 98.59 99.65 breast-cancer-wisc-prog 73.47 71.43 67.35 71.43 98.50 breast-tissue 61.54 80.77 73.08 65.38 95.78 car 98.84 100.00 98.38 98.84 99.32 cardiotocography-10clases 78.91 82.11 83.99 82.30 94.69 cardiotocography-3clases 90.58 93.97 91.53 94.35 97.09 chess-krvk 47.75 72.77 88.05 80.41 67.16 chess-krvkp 98.62 99.37 99.12 99.62 99.93 congressional-voting 61.47 57.80 61.47 57.80 66.54 conn-bench-sonar-mines-rocks 78.85 84.62 78.85 82.69 99.51 conn-bench-vowel-deterding 89.39 98.92 99.57 99.35 98.38 connect-4 78.96 86.39 88.07 86.46 86.83 contrac 52.72 49.73 51.90 54.89 62.95 credit-approval 81.98 79.65 84.30 82.56 98.47 cylinder-bands 69.53 73.44 72.66 78.12 99.54 dermatology 98.90 97.80 92.31 97.80 99.63 echocardiogram 84.85 87.88 81.82 87.88 94.62 ecoli 86.90 84.52 89.29 85.71 92.83 energy-y1 93.23 97.40 95.83 95.83 97.84 energy-y2 89.06 91.15 90.63 90.62 95.72 fertility 92.00 92.00 92.00 88.00 95.44 flags 39.58 50.00 45.83 52.08 94.96 glass 77.36 60.38 73.58 60.38 96.77 haberman-survival 72.37 65.79 73.68 65.79 82.34 hayes-roth 71.43 82.14 67.86 85.71 85.61 heart-cleveland 53.95 59.21 61.84 57.89 96.65 heart-hungarian 72.60 79.45 79.45 78.08 95.67 heart-switzerland 45.16 51.61 35.48 48.39 89.86 heart-va 36.00 30.00 36.00 32.00 94.34 hepatitis 82.05 82.05 76.92 79.49 100.00 hill-valley 66.83 68.81 52.48 54.62 72.69 horse-colic 80.88 83.82 80.88 82.35 97.65 ilpd-indian-liver 70.55 69.18 69.86 71.92 86.75 image-segmentation 87.76 90.57 91.14 90.57 99.31 ionosphere 89.77 87.50 88.64 96.59 98.84 iris 100.00 97.30 97.30 100.00 97.39 led-display 73.60 75.20 76.40 76.00 75.96
Continued on next page
DSName HANN15 HANN100 SNN DENN HANN100trn
lenses 50.00 66.67 66.67 66.67 100.00 letter 81.82 96.86 97.26 96.20 96.47 libras 64.44 81.11 78.89 77.78 98.20 low-res-spect 86.47 90.23 85.71 90.23 99.81 lung-cancer 37.50 62.50 62.50 62.50 100.00 lymphography 89.19 94.59 91.89 94.59 99.67 magic 86.52 87.49 86.92 86.81 87.84 mammographic 81.25 80.00 82.50 80.83 87.10 miniboone 90.04 90.73 93.07 93.30 89.98 molec-biol-promoter 73.08 80.77 84.62 88.46 99.38 molec-biol-splice 79.05 78.04 90.09 85.45 98.35 monks-1 65.97 69.91 75.23 81.71 99.89 monks-2 66.20 66.44 59.26 65.05 98.42 monks-3 54.63 61.81 60.42 80.09 99.78 mushroom 100.00 100.00 100.00 100.00 99.98 musk-1 77.31 84.87 87.39 89.92 98.86 musk-2 97.21 98.61 98.91 99.27 99.83 nursery 99.75 99.91 99.78 100.00 99.56 oocytes-merluccius-nucleus-4d 86.27 83.14 82.35 83.92 94.29 oocytes-merluccius-states-2f 92.16 92.55 95.29 92.94 97.61 oocytes-trisopterus-nucleus-2f 81.14 82.02 79.82 82.46 96.13 oocytes-trisopterus-states-5b 93.86 96.05 93.42 94.74 99.26 optical 93.10 95.94 97.11 96.38 99.55 ozone 96.53 95.58 97.00 97.48 99.78 page-blocks 96.49 96.13 95.83 96.13 98.33 parkinsons 87.76 89.80 89.80 85.71 99.47 pendigits 94.40 97.11 97.06 97.37 99.79 pima 71.88 73.44 75.52 69.79 84.47 pittsburg-bridges-MATERIAL 88.46 92.31 88.46 92.31 99.33 pittsburg-bridges-REL-L 76.92 73.08 69.23 73.08 97.66 pittsburg-bridges-SPAN 60.87 69.57 69.57 73.91 95.09 pittsburg-bridges-T-OR-D 84.00 84.00 84.00 84.00 99.67 pittsburg-bridges-TYPE 65.38 65.38 65.38 57.69 96.39 planning 66.67 55.56 68.89 60.00 93.45 plant-margin 50.50 79.50 81.25 83.25 98.18 plant-shape 39.00 66.50 72.75 72.50 81.77 plant-texture 51.75 75.25 81.25 81.00 99.14 post-operative 40.91 63.64 72.73 68.18 95.64 primary-tumor 54.88 47.56 52.44 53.66 79.04 ringnorm 90.43 85.35 97.51 97.57 98.42 seeds 92.31 96.15 88.46 92.31 98.52 semeion 74.37 92.71 91.96 96.73 99.12 soybean 77.93 88.83 85.11 88.03 99.48 spambase 93.57 94.17 94.09 94.87 98.14 spect 62.90 63.44 63.98 62.37 90.87 spectf 91.98 91.98 49.73 89.30 99.66 statlog-australian-credit 65.12 63.37 59.88 61.05 78.57 statlog-german-credit 72.40 72.40 75.60 72.00 97.52 statlog-heart 85.07 91.04 92.54 92.54 93.88 statlog-image 95.15 96.88 95.49 97.75 99.00 statlog-landsat 87.55 89.25 91.00 89.90 96.39 statlog-shuttle 99.92 99.92 99.90 99.91 99.96 statlog-vehicle 78.67 77.25 80.09 81.04 95.04 steel-plates 73.61 76.49 78.35 77.53 94.86 synthetic-control 94.00 98.00 98.67 99.33 99.76
Continued on next page
DSName HANN15 HANN100 SNN DENN HANN100trn
teaching 57.89 57.89 50.00 57.89 78.35 thyroid 98.37 98.25 98.16 98.22 99.65 tic-tac-toe 96.65 97.07 96.65 98.33 99.84 titanic 78.73 78.73 78.36 78.73 78.61 trains 100.00 50.00 NaN NaN 100.00 twonorm 97.30 98.27 98.05 98.16 99.51 vertebral-column-2clases 88.31 85.71 83.12 85.71 93.85 vertebral-column-3clases 81.82 80.52 83.12 80.52 95.40 wall-following 92.45 94.79 90.98 91.86 98.16 waveform 85.84 84.00 84.80 83.92 95.14 waveform-noise 84.72 84.96 86.08 84.32 96.39 wine 97.73 100.00 97.73 100.00 99.80 wine-quality-red 62.50 65.00 63.00 63.50 90.25 wine-quality-white 54.82 61.03 63.73 62.25 81.79 yeast 59.03 60.65 63.07 58.22 68.48 zoo 96.00 96.00 92.00 100.00 99.68

Review summaries:
This paper proposes a network architecture, HANN. HANN contains a hidden layer of binary activations, and can has a VC dimension smaller than the number of network parameters. HANN can be potentially a VC theory for studying the generalization of overparameterized neural networks. HANN is competitive with sota on UCI datasets.

The paper studies the VC dimension and minimax properties of a subclass of partially quantized NNs they name HAC(d,r,k) where d is the input dim, r is the latent (linear map) dim and k is the boolean function dim. The authors show a bound on the VC dim of HAC of O(k^r) which is independent of the number of weights. Further, the authors show that when the conditional density p(y|x) is lipschitz, H(d, d, r) achieve minimax optimality when d is fixed and $r=n^{1/(d+2)}$. 

This paper considers VC dimension for a class of partially quantized networks referred to as hyperplane augmented neural networks (HANNs). The architecture of this class of networks consists of a first hidden layer of width r and a second hidden layer of width k with Boolean (sign) activations. The name HANNs seems to be inspired by this Boolean layer which introduces a hyperplane arrangement. An upper bound of O(k^r) is established on the VC dimension of this network that is independent of the rest of the network (a Boolean function). In addition to this result on the VC dimension of HANNs, a result is proven on their representation power. In particular, it is shown that HANNs achieve the minimax rate for classification when the posterior probability is Lipschitz.