VC dimension of partially quantized neural networks in the overparametrized regime
Authors: Yutong Wang
Clayton Scott
Venue: ICLR 2022 Poster (2022)
Keywords: VC dimension
quantized neural networks
classification
minimax theory
overparametrization

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 class 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 are able to match the performance of state-of-the-art full-precision models.

Published as a conference paper at ICLR 2022
VC DIMENSION OF PARTIALLY QUANTIZED NEURAL NETWORKS IN THE OVERPARAMETRIZED REGIME
Yutong Wang's & Clayton Scott!?
'Department of Electrical Engineering and Computer Science
*Department of Statistics
University of Michigan Ann Arbor, MI 48109, USA
{yutongw, clayscot wecrscottttmmicmmmmm eemmmmichhh cincch.co edu
ABSTRACT
(VC) theory has so far been unable to explain the small generalization error of overparametrized neural networks. Indeed, existing appli- cations of VC theory to large networks obtain upper bounds on VC dimension that are proportional the number of weights, and for large class of networks. these upper bound are known to be tight. In this work, we focus 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 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 panel 121 UCI datasets, overparametrized HANNs match the performance of state-of-the-arr full- full-precision models.
INTRODUCTION
Neural networks have become an indispensable tool for machine learning practitioners, owing to their impressive performance especially in vision and natural language processing (Goodfellow eet al., [016]) In practice, neural networks often applied in the overparametrized regime and are capable of fitting even random labels (Zhang et al. 2021). Evidently, these overparametrized models perform well real world data despite their ability to grossly overfit, phenomenon that has been dubbed "the generalization puzzle" (Nagarajan & Kolter 2019).
Toward solving this puzzle, several research directions have flourished and offer potential expla- nations, including implicit regularization (Chizat & Bach 2020), interpolation (Chatterji & Long. 2021], and benign overfitting (Bartlett et 2020). So far, VC VC theory has 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 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, apply this result to show that HANNs have high expressivity by proving that HANN classifiers achieve minimax-oue -optimaalyy when the data has Lipschitz posterior class probability in overparametrized setting.
We benchmark the empirical performance of HANNs on panel of 121 UCI datasets, following several recent neural network and neural tangent kemel works (Klambauer et al.) 2017 7 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, partially-quantizee model, match the classification accuracy of the self self-normalizing neural network

---

Published as a conference paper at ICLR 2022
[Klambauer et al. (017) and the dendritic neural network (Wu al. 2018), both of which are full- precision models.
1.1
RELATED WORK
VC dimensions of neural networks. The VC dimension (Vapnik & Chervonenkis/ 1971) a com- binatorial measure of the complexity of concept class, i.e., 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 (w log w), logw),
where is the number of parameters. Maass (1994) obtained matching lower bound attained by a network architecture with two hidden layers. More recently, Bartlett recently,Barrlet et al. (2019) obtained the upper and lower bounds Oww log w) and ((ww log(w/E) respectively for the case when the activation is piecewise linear, where I 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 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 the VC dimension 2 number of weights. This has been dubbed the generalization puzzle (Zhagg 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 not specific to deep learning. For instance, AdaBoost has been ob- served 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 al. 2017) and kernel methods (Belkin et al. 2018).
Minimax-optimaalty. Whereas VC is distrbutionniineeeedenn, minimax theory is concerned with the question of optimal estimation//lassifiaatiii under distributional assumptions
minimax optimality result shows that the expected excess classification error goes to zero at the fastest rate possible, as the sample size tend infinity. For neural networks, this often involves hyperparameter selection scheme in terms of the sample size.
Faragó & Lugosi 1993) show minimax-optimaliig of (underparameerizzed) 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 Hölder classes, w where at most s ( log network weights are nonzero, and n the number of training samples. Kim et al. (202T) extends the results of Schmidt-Hiehhe (220) to the classi- fication setting, remarking that effective optimization under sparsity constraint is lacking. [Kohler & Langer (2020) and Langer (202T) proved minimax-optimalle
without the sparsity assumption, however in underparametrivzed 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 neu- ral networks has the potential to reduce the high computational burden neural networks at test time QQn 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 understanding the so-called coarse gradient, a term coined by Yin et al. (2019). often used in training QNNs as a surrogate
'The No-Free-LLund Lune- Theorem DDevoye 1982 implies that no classifier can be minimax optimal without
distributional assumption.
2

---

Published as a conference paper at ICLR 2022
for the usual gradient. One commonly used heuristic is the http:/t-ttroog--sttiiie (STE) first introduced an online course by Hinton et al. (2012). Theory supporting the STE heuristic has recently been studied in Li et al. (017) and Yin et al. 20119)
QNNs have also been analyzed from other theoretical angles, including mean- field theory (Blumen-
feld et al.] 2019), memory capacity (Vershynim 2020), Boolean function representation capacity [Baldi & Vershynin 2019) and adversarial robustness (Lin et al. 2018). Of particular relevance to our work, Maass| (994) constructed an example of 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 re- gions, such as axis-paie sais-larlllel rectangles, can be trained on properly chosen size a subset of an arbitrarily large training dataset without affecting the result. Such concept class is said to admit a sample compression schemes of size d, notion introduced by Littlestone & Warmuth (T986) who showed that the VC dimension of the class is upper bounded by O(o). Furthermore, the au- thors 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 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.
2 NOTATIONS
The set of real numbers is denoted R. The unit interval is denoted Jo. 1]. For an integer i 2 1, let kk] (1....,k) .).. We use X' to denote the feature space, which in this work will either be Rd or [0, 1jdd where d is the ambient dimension/nummber of features.
Denote by [(input} the indicator function which returns if input true and 0 otherwise. The sign function is given by aggo (t) = 1(t 2 0} -((t 0}. For vector inputs, agnn applies entry-wise.
The set of labels for binary classification is denoted IB : [+ Joint distributions on X' x B are denoted by P. where X, P denotes a random instance-label pair distributed according to P. Let f + B be a binary classifier. The risk with respect to P is denoted by Rp(S)= = P(((X) # Y)- For an integer n 2 1, the empirical risk is the random variable (f) = > i==1 T(f(X,) o YJ), where (X1, Yi),................ (Xni Yn) ~ P are i..dd The Bayes risk inf f:x-3 Rp(f) with respect to P is denoted by Rpp
Let f.g: : (1, 1... + Rzo be nonnegative functions on the natural numbers. We write s g there exists a, B such that for all n 1,2,... ... we have ag((n) I f(n) 8g(n).
HYPERPLANE ARRANGEMENT NEURAL NETWORKS
A hyperplane H in Rdd is specified by its normal vector w E Rdd and bias R. The mapping + agga (w + b) indicates the side of H that lies on, and hence induces a partition of Bd into two halfspaces. set h 2 1 hyperplanes is referred to as a k-hyperplane arrangemntt, and specified by matrix of normal vectors and vector of offsets:
W [w] ... wk] E Rdxk and b= b=Ib,....,b bb]
Let (w, == agn (T x + b) for all æ E Rdd The vector (w,6(x) E TB* is called sign vector and the set of all realizable sign vectors is denoted Gw,s == ((w,,(x) a E Rd). Each sign vector 8 E Gw. uniquely defines set far E Rd (w,((r) = 8} known as a cell of the hyperplane arrangement. The set of all cells forms a partition of Rdd For an example, see Figure I
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:
k.
(2
: k d,
Gw.bl
(1)
< d
+
: k 2
3

---

Published as a conference paper at ICLR 2022
See Fukuda 2015) Theorem 10.1 for simple proof. A hyperplane arrangement classifier assigns a binary label y E to a point æ E R2 solely based on the sign vector gw.b(z).
B2
Y
H1
+
+
+
+
+
H2
H1
Figure 1:
Left: An arrangement of 3 hyperplanes {H,. H2, Hs} in R There are 7 sign patterns. Middle: An example lookup table (see Remark 3.2p. Right: the resulting classifier.
Definition 3.1. Let E be the set of all functions from X' to B. A concept class C over X' is a subset of B Fix r, positive integers, r S minfd, k). Let Bool; the set of all Boolean functions B + IB. The hyperplane arrangement classifier class is the concept class, denoted HAC(d, r, k), over Rd defined by
HAC(d,r,k) {h QW,6 h Boolk, (w,( agn (W x x b),
W E Ba rank (W) S r, E R*}.
See Figure 2 for graphical representation of HAC(d, r,)), When the set of Boolean functions is realized by neural network, we refer to the resulting classifier as hyperplane arrangement neural network (HANN).
Remark 3.2. Consider a fixed hyperplane arrangement W. and Boolean function h E Boolg- When performing prediction with the classifer h 9w.b. b. the feature vector is mapped sign vector to which is applied. Thus, we do not need to know how h behaves outside of Gw,,. The restriction of Gw, is partially defined Boolean function lookup table.
Input R
Boolean B*
B
Activations
Bs
B2BrB3
Lincar
Threshold
Output
B2
X
B
Latent R
Figure 2: The HAC(d, A:) concept class as a neural network where d = 4, r and k = 3. The Boolean function is realized neural network hg-
Remark 3.3. The hidden layer of width r Figure the user to impose the restriction that the hyperplane arrangement classifier depends only or defined by data preprocessing. When r = d. no restriction imposed. In this case, the input layer is directly connected the Boolean layer. This is consistent with Definition 3.1 where the rank constraint rank W) S becomes trivial.
relevant features, which can be either learned
Our next goal is to upper bound the VC dimension of HAC(d, r. k).
Definition 3.4 (VC-dimension). Let S x be concept class over X. A set S == (#1,.... . S X' is shattered by C for all sequences (y1....: Yn) E B", there exists f E C such that f(x,) 91 for all E [n]. The VC-dimension of C' is defined
vC(C) SSp
X, S is shattered by C).
4

---

Published as a conference paper at ICLR 2022
The VC-dimension has many far-reaching consequences in learning theory and, in particular, clas- sification. 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. Ler C be a concept class over X. There exists a constant C > 0 such that for all joint distributions P on X x T and all f C. we have Rp R < C (VC(C) ()) +
with probability at least 1 5 with respect to the draw of (X1, Yi),..., (X.,
The above VC bound is useless in the overparametrized setting if VC(CC = O 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 Z 1 be integers and HAC(d, T; k) be defined as in Definition 3.1 Then
<r )
k:
VC(HAC(d, r, k)) = 8. (k(d+ k(d + () + [log2 k1) +
In the next section, we will prove this result using sample compression scheme. Before proceeding, we comment on the significance of the result.
Remark 3.7. Since (++) Ok*), we have VC(HAC(d, r)) O(K + dk log k) which only involves the imput dimension and the width of the first two hidden layers r and k. For constant d and 2 2, this reduces to VC(HAC k.)),,))) k)) Okk). In particular, the number of weights used by an architecture to implement the Boolean function 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 -hidddnn layer neural network with ReLU activation can model any k-input Boolean function if the hidden layer has width > 2 Note that this network uses 2 k:2 weights, and h- >> k-' for fixed r and & large.
Baldi & Vershynin 2019) study implementation of Boolean functions using threshold networks. A consequence of their Thcorem 9.3 is that a 2-hidden layer network with widths > c2t/2/ /vk can implement all & input Boolean functions, where c a constant not depending on This requires 2 2²2h /kc weights which again is exponentially larger than k". Furthermore, this lower bound on the weights is also necessary as I -> XC.
Remark 3.8. Using the memorization approach of Veeshynin 2020)) Rajput et al. (022) 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 of Rajput al. (2021) to memorize the distinct sign vectors in R*
A SAMPLE COMPRESSION SCHEME
In this section, we will construct sample compression scheme for HAC(d, r, k). As alluded 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. length n sequence {(rr, vs) E X x IB se is C-labelled there exists f E such that fx;;) = y: for all i E [n]. Denote by Lc(n) the set of C-labelled sequences of length at most n. Denote by Le(oo) 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
there exists pair of maps (p, x) where
P: Lc(m) x B + B K : (o())) + Lc(m) x B",
such that for all C-labelled sequences = ((,,, u:)) we have ((x(S))(z:)) y: for all E [n]. The size of the sample compression scheme is size(p, R) m s
Intuitively, x and p can be thought of as the compression and the reconstruction maps, respectively. The compression map keeps elements from the training set and bits of additional information, which p uses to reconstruct a classifier that correctly labels the uncompressed training set.
The main result of this section is:
5

---

Published as a conference paper at ICLR 2022
Theorem 4.2. HAC(d, k)) has sample compression scheme (p. K)) size size
size(p,x) k(d + 1) k(d ()(1+)))(++))))))))))))))))1 [log2 k() +
S
We remark that both the hyperplane arrangement (W, b) and the Boolean function h contribute to the number 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 hyperplane arrangement classifier of a special form.
Proposition 4.3. Ler {(r; bi] be HAC(d, r, k)-labelled. Then there exist [12 ... F&l Rdxk C E g² and h E Bool; such that for all E [m]. we have 1) y: = hg V 24 + c)), 2) rank(V) S r and 3) 1v] 24 cyl 2 for all E [m].j E [k].
The proof, given in Appendix A. is similar to showing the existence of a max-margin separating hyperplane for linearly separable dataset.
Definition 4.4. Let be a finite set and let a; E IR" for each E I. Let = faihez- A conical combination of A is linear combination Eier Aea; where the weights X; Rzo nonnegative. The conical hull of A, denoted coni (A), is the set of all conical combinations of A, i.e., coni (fas)ie)) = { Aça; X E R2,, vi E T}.
The result below follows easily from the Carathédory's theorem for the conical hull Lovász & Plummer 2009). For the sake of completeness, we included the proof in Appendix A.2
Proposition 4.5. Let a1.......
Rh" and bi...., bm E R. For each subset T S [m]. define
PI = {o E IR" a, x S 6, E 1}. Suppose that Pin] is nonempty. Then 1) milleP; 1 || has a unique minimizer, denoted by z below, and 2) there exists a subset [J] min(m.n] n} for all I S [m]] with J C I, we have [im] = =x7.
[m] such that
Proof of Theorem 4.2 Let (Ir; 9:) HAC(d, -reallizaa, and V, e and as in Proposi-
tion 4.3 For each E [n]. define the Boolean vectors = agn (V Ia + c) E [+1]* and
8ij Jaga (v) + cÿ) denote the j-th entry of Note that sig (1 xj cj) |0] ai +cl
We first outline the steps the proof:
1.
Using subset of the samples ((Ti,) Bi.) ) : l E [d(k+ 1)]} with additional 1) [[log, k1) bits of side information {(Suje Je) E [d(k + 1)]}, we can reconstruct W, such that
Jaga ( x; b) = for all i E [n].
Using an additional subset of samples {(F., Vc,) : 1,..., ( in conjunction with the W, reconstructed in the previous step, we can find g E Bool, such that g(s;) h(s;) for all
Now, consider the set
P = ((W,b) b) dRaxk R sy 0; + b,), 1, Vi E [n], j [R]]
Note that P is a convex polyhedron in (d + 1)k-dimensional space. Let (W,b) be the minimum norm element of Note that segal W x; + b) = Tega (VT + c) = s by construction.
By Proposition 4.5 there exists set of tuples
where (fr,.ee) E [n] x [k]
such that W, b is also the minimum norm element of = {W. b) kd x g Stzje (w], Fi, + by) 2, l= 1,.... d(k + +1).
To encode the defining equations of P', we need to store
samples {(ri Vi, )
d(k+1) and side information (ci d(k+1)

---

Published as a conference paper at ICLR 2022
Note that each Sy,y requires 1 bit while each je [k] requires [loge k] bits. In total, encoding p requires storing d(k + 1) samples and d(k + 1) + flog, kl) of bits.
To reconstruct g E Boolı that agrees with h all the samples, it suffices to know h when restricted to {st) Since {s, ) is subset of @... we have by eq- (1 that {st))] (5,)- Thus,
{s has at most unique elements. Let Suu :.=1......
be a set containing all such
Sr
unique elements. Thus, we store
samples {(Trer Bie) il -1==1,.. I,..., (5r))
(3)
Using W, 5 as defined above, we have S1z- = Jegal Iie + b). Now, simply choose g such that g(x.,) y/ for all { 1,..., (g.).
To summarize, formally define the compression and reconstruction functions (k. p). Let take the full sample {(T;, yi))== and output the subsample (and side information) in eq. and eq. (3)
The reconstruction function first constructs W, using eq. (). Next, constructs y using W, and the samples of eq. (3)
Now, the following result together with the sample compression scheme for HAC(d, r,k we con- structed imply Theorem 3.6 from the previous section.
Theorem 4.6 (Littlestone & Warmuth (1986). If C has sample compression scheme (p, 1e), then VC(C) < 8 size(p,
Remark 4.7. Note that the reconstruction function p is not permutation-invarte invariant. Furthermore, the overall sample compression scheme p. 6 is stable in the sense of Hanneke & Kontorovich (202T). In general, sample compression schemes with permutation-invaaiinn
(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.
5 MINIMAX FOR LEARNING LIPSCHITZ CLASS
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 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 is such that the associated HANN, the neural network realization of HAC(d, k), is overparametrized for the Boolean function implementations discussed in Remark 3.7
Below, let X E [0, and IB be the random variables corresponding sample and label jointly distributed according to P. Write (r()) = P(Y = =| = x)) for the posterior class probability function.
Let E(L, [o, 1]d) denote the class of L-Lippchitz functions f: 10, 1] + IR, i.e.,
[f(x) f(x'1 | s L| x'112, Va, x' E 1].
The following minimax lower bound resul concerns classification when 7pp is I.-Lipschitz: Theorem 5.1 (Audibert & Tsybakov (007 There exists constant C such that
inf sup fn P.ppe (00,
E E[ - RT On गें.
The infimum above taken over all possible learning algorithms Ju. i.e., mappings from (X x B)" to Borel measurable functions X' + BB When fn is an empirical risk minimizer (ERM) over HAC(d, r, k) where d for k nd+2 this minimax rate is achieved.
'The result cite here is special case of (Auiieett & Tsybakow 2007 Theorem 3.5), which gives minimax lower bound for when np has additional smoothness assumptions.

---

Published as a conference paper at ICLR 2022
Theorem 5.2. Let d be fixed. Let fn be ERM over HAC(d, d)k) where & k(n) nait. Then there exists a constant C" such that
E[R(fW) - Rtp S C'n
sup P P:n,EE(L.,0.14)
Proof sketch (see Appendix A.3 full proof). We first show that the histogram classifier over the standard partition of [0, 1]dh into smaller cubes the problem to proving minimax-oppimality of the histogram classifier. Previous work Györfi et al. (2006) Theorem 4.3 established this for the histogram regressor. The analogous result for the his- togram classifier, to the best our knowledge, has not appeared in the literature and thus included for completeness.
element of C == HAC(d, k),,, thus reducing
The neural network implementation of HAC(d, k) where l n l/(+2)) in Theorem 5.2 can be overparametrized. Using either the 1- or the 2-hidden layer neural network implementations of Boolean functions in Remark 3.7 the resulting HANN is overparametrized and has number of weights either 2 k:2* or 2 222 respectively. Both k2 and c224 /k > n exponentially while VC(HAC(d, d, k)) = onn).
EMPIRICAL RESULTS
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, theory is for binary classification, while some of the datasets in the experiments multiclass.
Synthetic datasets. We apply a HANN (model specification shown in Figure toop left) to the MOONS synthetic dataset with classes with the hinge loss.
The heuristic for training networks with threshold activation can significantly affect the performance (Kim al. 2019). We consider two of the most popular heuristics: the straightthhroggh-estinaa (SteSign) and the SwishSign, introduced by Hubara et al. (2017) and Darabi et al. (2019), respec- tively. Below,
SwishSign since it reliably leads higher validation accuracy (Figure bottom left), consistent with the finding of Darabi et al. (2019).
Networ Archi bnduure
Hiddon layer <lm=10 Threshold
Hitdan 2 dimin 1024 Rell
dam -
dim
Validation accuracy over 100 independent runs Curve median, Riabonn 20/80 inter-quartile
1.000
0.875
0.850
0.825
Stediinn
SwishSigg
0.800
0
1.0
200
300
500
Esochs
Figure 3: Top left. Architecture of HANN used for the MOONS dataset (nake moons in sklearn). Bottom left. Validation accuracies from 100 independent runs with random initialization and data. Right. Dotted lines denote the hyperplane arrangement. Coloring of the cells denote the decision region of the trained classifier. A cell A is bolded if 1) no training data lies in A and 2) A does not touch the decision boundary.
The width of the hidden layer is 20 = 1024. Thus, by Mukherjee & Basu 2017) Lemma 2.1, 1, the model assign labels to the bolded cells arbitrarily without changing the training loss. Neverthe- less, the optimization appears to be biased toward a topologically simpler classifier. This behavior is consistently reproducible. See Figure
8

---

Published as a conference paper at ICLR 2022
Real-world datasets. Klambauer et al. (2017) introduced nofonlllmliing neural networks (SNN) which were shown to outperform other neural networks on a panel of 121 UCI datasets. Subse- quently, 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 the 121 UCI datasets.
crucial hyperparameter for HANN is the number of hyperplanes k. We ran the experiments with 1-hidden
k {15, 100} to test the impact on accuracy. The Boolean function h is implemented
layer residual network (He et al. 2016) of width 1000. The logistic loss is used.
We the same train, valiclation, and test on the held-out test set are based on the model with the highest validation accuracy. The models will be referred as HANN15 and HANNI 00, respectively. The results are shown in Figure The accuracies of SNN and DENN are obtained from Table Al in the supplemental materials of Wu al. (2018) Full details for the training and accuracy tables can be found in the appendix.
in Klambauer et al. (017). The reported accuracies
Comparing HANN with SNN and DENN the UCI datasets
of hyperplanes HANN
-1.0 [-7.1,
-1. (-7.4,
Median
Density of ftt
0.06
20/80-10 th quantiles
15
0.04
0.02
0.10
0.0 2.6]
0.0 1.1]
0.08
100
0.02
11
11110
10
1100
-20
15
10
-
10
15
20
-20
-15 100
-5
10
15
20
Accuracy of HANN minus accuracy of (in percentages)
Figure 4: Each blue tick above the x-axis represents single dataset, where the x-coordinate of the tick is the difference the accuracy HANN and either SNN (left) or DENN (right) on the dataset. The solid black curves are kernel density estimates for the blue ticks. The number of hyperplanes used by HANN is either 15 (top) or 100 (bottom). The quantities shown the top-left corner of each subplot are the median, 20-th and 80-th quantiles of the differences, respectively, rounded to decimal place.
The HANN15 model (top row of Figure 4 already achieves median accuracy within 1.5% of both SNN and DENN. With the larger HANNI00 model (bottom row), the gap is reduced zero. The largest training set in this panel of datasets has size 77904. The HANN1 5 and HANN1 00 models use 10a and 10 weights, respectively. By comparison, the average numbers of weights used by SNN and DENN are both 5 10 Details these estimates are included in Appendix C Thus, all three models considered here are overparametrized.
DISCUSSION
We have introduced an architecture for which the VC theorem can be used prove minimax- optimality of ERM over HANNs in an overparametrized setting with Lipschitz posterior. To our knowledge, this the first time VC theory has been used to analyze the performance neural net- work 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 mean- ingful results. Yet there immense interest 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 sam- ple compression scheme, is useful avenue, and one that has previously been explored the first work applying sample compression to NNs. This seems likely to open the door to further analysis of quantized NNs.
is

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
The authors were supported in part by the National Science Foundation under awards 1838179 and 2008074, and by the Department of Defense, Defense Threat Reduction Agency under award HDTRAI-200--0002.
REPRODUCIBILITY STATEMENT
All code for downloading and parsing the data, training the models, and generating plots in this manuscript are available at https: httptttttuuu...e//g com. Yut wag.angguiccc.h.....mmmoo HANN Complete proofs for all novel results are included in the main article or in an appendix.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mane, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, llya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viegas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: A system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pp. 265-283, 2016.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2019.
Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via compression schemes. Journal of the ACM (JACM), 67(6): 122, 2020.
Jean-Yve Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608-633 2007.
Pierre Baldi and Roman Vershynin. The capacity of feedforward neural networks. Neural networks, 116:288-311 11188-311,2200 2019.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6241-6250, 2017.
margin bounds for
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Muchine Learning Research, 20(63):1-17, 2019.
Peter L Bartlett. Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(49):3063333007 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. Acta Numerica, 2021.
Eric B Baum and David Haussler. What size net gives valid generalization? Neural computation, (1):151-160, 1989.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. In International Conference on Machine Learning, pp. 541-549, 2018.
Yaniv Blumenfeld, Dar Gilboa, and Daniel Soudry. A mean field theory of quantized deep net- works: The quantization-deptl trade-off. In Advances in Neural Information Processing Systems, volume 32, 2019.
10

---

Published as a conference paper at ICLR 2022
Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, Helly number, and an optimal SVM bound. In Conference on Learning Theory. 2020.
Robert Creighton Buck. Partition of space. The American Mathematical Monthly, 50(9):41--54, 1943.
Zhaowei Cai, Xiaodong Hc, Jian Sun, and Nuno Vasconcelos, Deep learning with low precision by half-wave Gaussian quantization. In Proceedings of the IEEE conference computer vision and patter recognition, pp. 5918-5926, 2017.
Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129): 2021.
Lenaic Chizat and Francis Bach. Implicit bias gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory, pp. 1305-1338. PMLR, 2020.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with ap- plications in pattern recognition. IEEE transactions on electronic computers, (3):326-334, 1965.
Sajad Darabi, Mouloud Belbahri, Matthieu Courbariaux, and Vahid Partovi Nia. Regularized bi- nary network training. In Fifth Workshop on Energy Efficient Machine Learning and Cognitive Computing NeurlPS Edition (EMC2-NIPS), 2019.
Lue Devroye. Any discrimination rule have arbitrarily bad probability of error for finite sample size. IEEE Transactions on Pattern Analysis and Machine Intelligence, (2):154-157, 1982.
Gintare Karolina Dziugaite and Daniel Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Conference on Uncertainty Artificial Intelligence, 2017.
András Faragó and Gábor Lugosi. Strong universal consistency of neural network classifiers. IEEE Transactions on Information Theory, 39(4): 111444::1166111 1411-1166111111 1151, 1993.
Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the dimension. Machine learming, 21(3):66-3304, 1995.
Komei Fukuda. Lecture: Polyhedral computation, Spring 2013, 2015.
URL
http://www-oldune inf wtt. http:ha.chh...eoooooaaaaaaaaeete Lttpeeeeeaaeeepppp.ceccee//cc///
note=20015/Polycom2201....
Lukas Geiger and Plumerai Team. Larq: An open-source library for training binarized neural net-
works. Journal of Open Source Software, 5(45):1746, January 2020.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, 2018.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A distribution-fre theory of nonparametric regression. Springer Science & Business Media, 2006.
Steve Hanneke and Aryeh Kontorovich. Stable sample compression schemes: New applications and an optimal SVM margin bound. In Algorithmic Learning Theory, pp. 697-721. PMLR, 2021.
Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. Sample compression for real- valued learners. In Algorithmic Learning Theory, pp. 466-488. PMLR, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey Hinton, Nitsh Srivastava, and Kevin Swersky. Neural networks for machine learning. Coursera, video lectures, 264(1):2146-2153, 2012.

---

Published as a conference paper at ICLR 2022
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Jour- nal of Machine Learning Research, 18(1):686966888 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, 2018.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. In International Conference on Learning Representations, 2019.
Hyungjun Kim, Kyungsu Kim, Jinseok Kim, and Jae-Joon Kim. Binaryduo: Reducing gradient mis- match in binary activation network by coupling binary activations. In International Conference on Learning Representations, 2019.
Yongdai Kim, lisang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification. Neural Networks, 138:179-1999 2021.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Advances in Neural Information Processing Systems, pp. 971-980, 2017.
Michael Kohler and Sophie Langer. On the rate of convergence of fully connected deep neural network regression estimates. arXiv preprint arXiv: 1901:1198..1133,, 2020.
Sophie Langer. Analysis of the rate of convergence of fully connected deep neural network regres- sion estimates with smooth activation function. Journal of Multivariate Analysis, 182:104695, 2021.
Hao Li. Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 5813-5823, 2017.
Lin, Chuang Gan, and Song Han. Defensive quantization: When efficiency meets robustness. In International Conference on Learning Representations, 2018.
Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network.
Advances in Neural Information Processing Systems, 30, 2017.
Nick Littlestone and Manfred Warmuth. Relating data compression and learnability, 1986.
lászłó Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical
Soc., 2009.
Wolfgang Maass. Neural nets with superlinear VC-dimension. Neural Computation, 6(5):877-884, 1994.
Asit Mishra, Eriko Nurvitadhi, Jeffrey Cook, and Debbie Marr. WRPN: Wide reduced--recisionn networks. In International Conference on Learning Representutions, 2018.
Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. Journal of the
ACM (JACM), 6303):1-10, 2016.
Anirbit Mukherjee and Amitabh Basu. Lower bounds over Boolean inputs for deep neural networks with ReLU gates. arXiv preprint arXiv:1711.03077, 2017.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generaliza- tion in deep learning. In Advances in Neural Information Processing Systems, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring gener- alization in deep learning. In Proceedings of the 3 International Conference on Neural Infor- mation Processing Systems, pp. 0949-5958. 2017.
Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe. Binary neural networks: survey, Pattern Recognition, 105:107281, 2020.
12

---

Published as a conference paper at ICLR 2022
Shashank Rajput, Kartik Sreenivasan, Dimitris Papailiopoulos, and Amin Karbasi. An exponential improvement on the memorization capacity of deep threshold networks. Advances in Neural Information Processing Systems, 2021.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. XOR-Net: Imagenet classification using binary convolutional neural networks. In European conference on computer vision, pp. 525-542. Springer, 2016.
Robert E. Schapire. Explaining AdaBoost. In Empirical inference, pp- 37-52. Springer, 2013.
Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReL.U acti- vation function. Annals of Statistics, 48(4):1875-1897, 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil, Jonathan Ragan- Kelley, Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. In International Conference Machine Learning, pp. 8614-8623. PMLR, 2020.
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complexity, 16(2):11, 1971.
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 2(4):1004-1033, 2020.
Xundong Wu, Xiangwen Liu, Wei Li, and Qing Wu. Improved expressivity through dendritic neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8068-8079, 2018.
Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of AdaBoost and random forests as interpolating classifiers. The Journal of Machine Learning Re- search, 18(1):1558-158 2017.
Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Under- standing ttraight-through estimator in training activation quantized neural nets. In International Conference on Learning Representations, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
A PROOFS
A.1 PROOF OF PROPOSITION 4.3
By definition, there exists h E Bool,, W E Rdxk of rank at most r, and b E R² such that y: h(o.gn WT 2; + b)).
Now, let j E [k] be fixed. Since |w] x; + byl 2 0 for all E [n], there exists small perturbation & of by such that we] x; + Ln > for all i [n]. Now, let >3 = min [ui] xq + 0yl which
positive. Define by := wy/A Aj and = Z//A,. we have [v] x4 - egl 2 for all E [n]] as desired.
Note that rank V) = rank(W) W).
A.2 PROOF OF PROPOSITION 4.5
If m S n, then the result holds trivially by letting J [m]. Below, suppose that m n. Let (x(x) = a, x b, for each E [mr] and f(x) a | Then v/(x) x and (g. = 04 By definition, o a minimizer of
min f(x) s.t. gx(x)) S ViEl, #ER
13

---

Published as a conference paper at ICLR 2022
which is convex optimization with strongly convex objective. Thus, the minimizer 2) is unique and furthermore is the unique element x of IR satisfying the KKT conditions:
Pj and a set of nonnegative weights {Niteer such that
\aa
Thus, 27 can be equivalently characterized as the unique element of x E IR. satisfying
x E Pa and - x E coni (ax her).
(4)
In particular, 3imil Pim) and ml coni (m))) By the Carathédory's theorem for the conical hull {Loáász& & Plummer 2009). there exists 1 _ [m]] such that [ = n and [mm) E coni(fa, hez). Thus, for any S mm] such that I S J, we have -Pinj E coni(fa;hel Furthermore, J [m] implies P, 2 Pmm- In partieular, "im] Py. Putting it all together, have T[m]] E Py and - [mm) E coni he)). By the uniqueness, we have 2 = [[m]]
A.3 PROOF OF THEOREM 5.2
In this proof, the constant does not depending on n, and may change from line to line.
We fix joint distribution P such that 7/r (L, [0, 1J throughout the proof. Thus, the notation
for risks will omit the P in their subscript, e.g., write (J) instead of (f),a() and It instead of Rp. Below, let B > a > O be constants such that cadn ((d-2) I k S (dd22( Let k == [k/d].
Let R1, R2,... Rga denote the hypercubes of side length l = 1/k forming partition of [o, 1j For each i E [k= let R2 {x R; n)(2) 1/2} and R {x R; <)(xx) 2 1/2].
Let f [0, 1jd B be the classifier such that
+1 : x E R4, JR. 1p np(x)dP(x) 2 JR. (=(()())))P())
[(x) -w-)-
E Ri, JR. nr(x)dP(s) < SR. (1 (d))))))(())
In other words, f classifies all R. as +1 if and only if P(Y 1|X R2) 2 1/2. This is commonly referred to as the histogram classifier (Györf et al. 2006). it easy to see that
P(f(X) XY = min (/e R, (1 no (r))))
nr(x)dP(a))
JR.
For the remainder of this proof, we write "E," to mean "iE(Kaa]" Thus,
+Y R,) Emin min {S. (1 (1-18 -=ne(=))d((s) / ne(z)dP(a))
R(f) x,
Next, we note that f E HAC(d, d, k). To see this, let j E [d]. Take H,1...., "y1....,H((kk]) ((--1) S Rd to be the hyperplanes perpendicular to the j-th coordinate where, for each E E [k]. HG intersects the j-th coordinate axis t/k. Consider the hyperplane arrangement consisting of all {Hj and let {C1, . be its cells. Then {C1 n [o, 1) C2 0. 11d
= (R..... Rea is the
partition of [o, 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 diie - 1) d([k/d 1) < d(k//d) k hyperplanes. Since f is constant on R,,, there exists a Boolean function Bool, such that h o ow.oll..jj From this, we conclude that f E HAC(d, k).
Thus (f,( (f) 0 and so R(f..) R²" R(fr.) - (fa) + R.(ff)) (n)())) +R,(() R(J) + R()) - R
50
< R(f.)) - (fa)) + Rr,(
R() R()) - R.
Tem
14

---

Published as a conference paper at ICLR 2022
H22
1/3
H21
H11
H12
Figure 5: Partition of [0, 1 into 1/k hypercubes via arrangement of d(k 1) hyperplanes, where
d = 2 and k = 3. Shaded region is [0, 1]". Dotted region is a cell of the hyperplane arrangement.
We now bound Terms 1 and 2 using the uniform deviation bound. From Theorem 3.6 we know that there exists constant C' independent of n such that
dc( <8 (k(d+1) k(d+ 1)(1 [k)))
) < Cka
Thus, by Theorem 3.5 with ō 11((n) and union bound, with probability least 1/n
kdd + log(n)
max {
( RR(F) - -R(i) s CV
(5)
for some C >
Next, focus Term 3. Recall that
R S 10.11" 1 (p()))d((x) // -/00))>>//// min(np(x),1 (
and that
R() = Σ min V ne(w)dP(a),
/ 1- 1-)p(r)dP(0)
R;
Fix some i E [. Our goal now is to bound the difference between the i-th summands in the above expressions for R(f) and Rt:
min VL (e(x)dP(z), ( R.
1- 1-np(x)dP(()) min(m (mpp)))) (6)
R.
First, consider the case that
min U/ (r())dP(s),
/ 1- (o(
(x(x))P(x)
R.
We claim that there must exist 2o R, such that (2())) 1/2. Suppose Π)(x)) 1/2 for all x E R4. Then (x)) 1/2> (z)). Since pp (2) is continuous, this would contradict eq. 7
Continue assuming eq. 77). further divide into two subcases: (1) (p(x) 1/2 for all R; and (2) there exists some œ1 E R, such that f) > 1/2.
Under subcase (1), min(nr(2)) nr(x)) (r(x) for all R; in which case eq. (6) 0.
15

---

Published as a conference paper at ICLR 2022
Under subcase (2), since (=(2)) 1/2 (2(1)) we know by the intermediate value theorem that there must exist x' E R4 such that (1()')) = 1/2.. Now,
/ (π)(x)
eq. 6
-
- (ppp)))-mmbpp)))---eee(ddddp
R
+
-
S nt
(np(x) - (1 nr(x))d((s)
Definition of R²
{ (11(2)) (=(2)))((z)
+
R.
/ (2mp(x) - 1)dP(x))
=
R
2 / (Πι(1) (dP)())
::2m(('') =1
JR.
{ ||0- (2)))))
< 2L
< 22
- S vdl 2'1l1 S vā(1/k)
s 2/ Pr(R,)/k
:: 1 /k/d s 1/(k/d) d/k.
Thus, under assumption eq. we have proven that eq. 6 < / /k. For the other assumption,
i.e., the minimum in eq. 7 attained by SRe (P completely analogous argument
again shows that eq. 6 Ld
Putting all together, we have
R(h.) R < 2/
3 P(R.)/k==2l0 2LG/12 //k
(8)
We have shown that, with probability at least 1 1/n.
R(fa) - H S CV kd + log(n) 2L23/2
Using odn 2/(d+2) < k < Bdn (dd42), we have with probably at least 1/n that
kd + log(n)
2Ld3/2
R(fa) - R² s <Cv
+ +og((n)
2T/3/2
<Cv
adn! l/d+2)
n
nd/(442)
+ n (1/(4+)))
:. loggn)) = oon2
n
C (n (n-2/(a+2) n 11((422))
< Cn atz.
Taking expectation, have E(((f.)) - R < (1- 1/n)Cn -n---t +े + +1/n 5 Cn-
16

---

Published as a conference paper at ICLR 2022
B TRAINING DETAILS
Data preprocessing. The pooled training and validation data is centered and standardized using the StandardSca 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_vaiio
X_train_valid scaler. taantrransss.t scaler.trans form (X_ (X_train_valid) X test scaler. transfrrafmmmmmm (t (X_test)
If the feature dimension and training sample size are both > 50, then the data is dimension reduced to principal component features:
min (X train valid. shape) 50:
pea PCA (n in_components 50) fit ix_train_valill X_train_valid pea. trantrrasss form (x (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
Validation and test accuracy, Every 10 epochs, the validation accuracy during the past 10 epochs averaged. A smoothed validation accuracy is calculated as follows:
val a_____________ am (1-sm param) vval acc_sm sm paw.m-aal_aaaaoo
## Variable description:
smmparam 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 the snapshot of the model at the highest smoothed validation accuracy, at the end once max epochs reached.
Heuristic for coarse gradient of the threshold function. We the SwishSign from the Larq
library (Geiger & Team 2020).
import 1arq as 1q qtz 1g. quantizeze SwishSign
Dropout. During training, dropout is applied to the Boolean output of the threshold function, i.,, the variables B1, B2...,, ., B₃ in Figure This improves generalization by preventing the training accuracy from reaching 100%.
from tensorflow. keras. layers import Dense, Dropout hyperplane_ent Dense mn_hyperplanes, activation qtz) (inputs)
hyperplane_enc Dropout (dropout_rate) thyperplanc_cne
Implementation of the Boolean function. For the Boolean function h, we use 1-hidden layer residual network (He al. 2016) with 1000 hidden nodes:
from tensorflow keras. 1ayers import Dense, Add output_ dim = num classes
n hidden = 1000
hidden Dense (n hidden, activation="relu"" (hyperplane enc)
out_hicden 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 size 3 where only the dropout rate is tuned. The hyperparameters summarized in Table The model with the highest smoothed validation accuracy is chosen.
The model HANN15 is trained with the following hyperparameters:
17

---

Published as a conference paper at ICLR 2022
Table 1: HANN15 5 model and training hyperparameter grid
OPTIMIZER
SGD
LEARNING RATE
0.01
DROPOUT RATE
{0.1, 0.25, 0.5)
MINIBATCH SIZE
128
BOOLEAN FUNCTION
1-HIDDEN RESNET WITH 1000 HIDDEN NODES
EPOCHS
100 MINIBOONE
5000 FOR ALL OTHERS
For HANN100, we only used set of hyperparameters.
Table 2: HANN1 00 model and training hyperparameter
OPTIMIZER
SGD
LEARNING RATE
0.01
DROPOUT RATE
0.5
MINIBATCH SIZE
128
BOOLEAN FUNCTION
I-HIDDEN LAYER RESNET
WITH 1000 HIDDEN NODES
EPOCHS
100 MINIBOONE
5000 FOR ALL OTHERS
C PARAMETER COUNTS
The widest part of HANN15 and HANN100 models are weights mapping from B number of hyperplanes) to 1000 (1000 number of hidden layer of the boolean function) where E {15, 100). Thus, the two HANN models use 2 15 x 1000 2 10 and 2 100 x 1000 = 10 weights, respectively.
The weight count estimates for the Self-normalized Neural Network (SNN) and Dendritic Neural Network (DENN) the formula (# layers 1) (# neurons per layer)?
For the Self-normalized Neural Network (SNN), average number of layers = 10.8, and the number of neurons per layers > 256, found page and Table A4 of Klambauer al. (2017), respectively. The number of weights is 2 (10 - 1) (256²) = 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 layers = 3 and number of neurons per layer 512, found line 41 and 52 of train_uci. py, respectively. The number of weights is (3 1) * (512²) 524, 288 weights.
D ADDITIONAL PLOTS
Figure 6 shows the accuracy differences when the Weston Watkins hinge loss is used. Compared to the results shown in Figure the performance for HANNI 00 is slightly worse and the performance for HANN1 5 is slightly better.
Multiclass hinge versus cross-entropy loss.
18

---

Published as a conference paper at ICLR 2022
Comparing HANN with SNN and DENN over the UCI datasets
0.10
-0.7 [-6.0, 1.5]
-1.1 0.6]
Median
hyperplaan annerplanesseee HANN
Density of KDE fit
0.06
20/80-th antiles
15
0.04
0.02
0.10
0.0 (-3.8, 3.0]
-0.2 (-3.1, 1.4]
0.08
0.06
100
0.04
0.02
11
111
-20
-15
-10
-5
0
10
15
20
-20
-15
10
-5
5
10
15
20
SNN
DENN
Accuracy of HANN minus accuracy
(in percentages)
Figure 6: Each blue tick above the x-axis represents single dataset, where the x-coordinate of the tick is the difference of the accuracy of HANN and either SNN (left) DENN (right) the dataset. The number of hyperplanes used by HANN is either 15 (top) or 100 (bottom). The quantities shown in the top-left comnrr of each subplot are the median, 20-th and 80-th quantiles of the differences, respectively, rounded to decimal place.
Implicit bias for low complexity decision boundary. In Figure 7 we show additional results ran with the same setting for the MOONS synthetic dataset in the Empirical Results section. From the perspective of the training loss, the label assignment in the bold-boundary regions irrelevant. Nevertheless, the optimization consistently appears be biased toward the geometrically simpler classifier, despite the capacity for fitting complex classifiers.
Figure 7: Four independent runs of HANN on the MOONS synthetic dataset. Similar to Figure
19

---

Published as a conference paper at ICLR 2022
E TABLE OF ACCURACIES
Below the table accuracies used to make Figure The last column "HANN100tm" records the training accuracy at the epoch 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 blood
88.50
88.05
89.03
89.65
95.62
75.94
75.40
77.01
73.26
82.03
breast-cancer
70.42
63.38
71.83
69.01
86.63
breast-cancer-wise
97.71
98.29
97.14
97.71
98.65
seeutt-cance-wise-diee
97.89
98.59
97.89
98.59
99.65
breast-cancer-wise-mmee
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-I144e 10clases
78.91
82.11
83.99
82.30
94.69
cardiotocographyy-eeeass
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
congressionallvoting
61.47
57.80
61.47
57.80
66.54
con--bench-sonar-mineee
78.85
84.62
78.85
82.69
99.51
conn- houn-bench--owll-deeeeee
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
sylinder-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-yl
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
ulpd-indian-live 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 next page
20

---

Published as a conference paper at ICLR 2022
DSName
HANNI5
HANN100
SNN
DENN
HANN
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-mertucctus--muuaae
86.27
83.14
82.35
83.92
94.29
secytes-merluccin--stteee-
92.16
92.55
95.29
92.94
97.61
oogytes-tiippternn-nuddu----
81.14
82.02
79.82
82.46
96.13
becytes-trisplemusstttee---bbb
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
bittsburg-bridge--MATTEERII
88.46
92.31
88.46
92.31
99.33
butsbburg-bridges-RELLL
76.92
73.08
69.23
73.08
97.66
pittsurg--ridgee--50
60.87
69.57
69.57
73.91
95.09
pittsbrrg-rridges-TOo
84.00
84.00
84.00
84.00
99.67
pittsburg-bridges-TYPP
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-tumot
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
naatog-austtalian-ee
65.12
63.37
59.88
61.05
78.57
72.40
72.40
75.60
72.00
97.52
statlog-
85.07
91.04
92.54
92.54
93.88
satlog--mage
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
stecl-plates
73.61
76.49
78.35
77.53
94.86
synthetic-control
94.00
98.00
98.67
99.33
99.76
Continued next page
21

---

Published as a conference paper at ICLR 2022
DSName
HANNI5
HANN100
SNN
DENN
HANN100tm
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-2llee
88.31
85.71
83.12
85.71
93.85
vertebral-column-cllae
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-whie
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
22


Reviews:
[{"review_id": "w1dBOcWYap7", "reviewer": "Reviewer_QZye", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 paper is very well written. All the concepts and ideas are explained well. The results are supported by detailed proofs and extensive references to the existing work. Nice graphics are used to present the ideas of hyperplane arrangement and resulting classifiers\n\nThe analytical results nicely complement each other. It is shown that while useful bounds on VC dimension can be proven for HANNs, the representative power of HANNs is comparable to the full precision models.\n\nThe VC dimension is known to lead to vacuous generalization bounds in full precision overparameterized neural networks. The main contribution of this paper is providing useful bounds on VC dimension for a class of highly expressive models. The bound still seems quite large though: O(k^r). It is a power of width of the layer which seems to determine the expressive capacity of the network (through determining the hyperplane arrangement). This seems a major limitation in application of the main result of the paper. If I am right, I think the paper can significantly benefit from a discussion on this (either explaining more cases where the results are useful or clarifying this limitation). For example, if we use the numbers given in experiments (which are relatively small experiments), with a data set of size 77904 and k=100, and r=3 seems to result in vacuous bounds on generalization again.", "summary_of_the_paper": "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.\nAn 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.", "summary_of_the_review": "The paper is written very well and has nice complementary results. I am however uncertain about whether the main result would be effective in explaining generalization error using VC dimension in reasonable scenarios. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_F5iu0GV1Wq", "reviewer": "Reviewer_UWBZ", "summary": "", "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": "To the best of my knowledge the theory appears sound and the proofs are correct and the usage of the compression scheme is neat. Moreover the experimental evaluation is thorough and surprising to some extent (e.g., how does this class achieve about state of the art performance). However, I have some reservations about the paper. First, reading the title and introduction has led me to believe that a much more general class of QNNs have small VC dimension. However the model that the authors study is basically a two layer NNs, shedding doubt on whether any non-toy quantized models will have small VC dim (could be easily checked via and experiment ala Zhang et al 2017). \n\nMoreover, I'm doubtful about studying the VC dim of NNs in the first place. I'd love to hear the authors take of what are we aiming to learn here as in practice VC dims will give us non-meaningful bounds. \n\nMinor comments:\nShould the following be number of samples: \n       Note that the above VC bound is useless in the overparameterized setting if VC(C) =(# of weights)\nIn proposition 4.5, P_I could be an empty set. (e.g., if a_1 = -a_2 and b_1 = -b_2). Then, there is no unique minimizer to P_I. \nIf m < n how can the size of J be n? \n\nIt would be helpful to further explain the second paragraph in page 8 (e.g., how did you count the weights?).  \n\nRegarding the experiments, in my opinion, using the number of weights to measure overparameterization is not indicative. A much better way to know whether the models are overparameterized is to look at the training error/loss (if it is very close to zero we are overparameterized).\n", "summary_of_the_paper": "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)}$. ", "summary_of_the_review": "The work is technically sound however I find the title/introduction overstating the significance of the results to some extent and not sure if the motivation is strong enough.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AMoWBruMTeP", "reviewer": "Reviewer_W4WM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Strength:\n- demystify the generalization puzzle of overparameterized neural networks is an important topic to study\n- novelty: the first VC theory of overparameterized neural networks\n- the construction is not too complicated\n\nWeakness:\n- I don't fully understand the implication of Theorem 4.2. size(rho, kappa) critically depends on r, the rank of the weight matrix W. But if we decompose W=UV, where U is d*r and V=r*k. Isn't the VC dimension of HANN still higher than the number of effective parameters, dr+rk? In this case, what benefit do HANN have over ReLU and sigmoid networks?\n\nPost rebuttal\n====\n\nThanks for answering my questions. I'm still confused about what role does the binary activation play here though. I think the critical assumption of Theorem 4.2 is that the weight matrix is low-rank. In this case, can't I just reformulate the layer with low-rank weight as two layers with a small bottleneck hidden layer of dimensionality r, which has much smaller number of parameters than the equivalent network? If this is the case, I think the result is only relevant to the low-rank assumption, not the HANN itself.\n\nI'm still maintaining my score based on these concerns.", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper solves an important problem and is novel, though I am not fully convinced by the claims due to some potential misunderstanding.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors analyzing the VC-dimension of a class of neural networks
with hard thresholds at the hidden nodes that include a low-rank weight
matrix and hard-thresholds at hidden units.  The bounds are independent
of the number of weights used to represent functions mapping a hidden
layer to the output.  They also provided some experiments supporting the
practicality of networks like those treated in their theoretical analysis.

There was some question about whether the VC-dimension continues to be relevant.
Also, while the upper bounds have attractive properties that were highlighted by the
authors, they also are not very strong in other respects.

The consensus view overall, though, was that this is a "nice result",
a clean illustration of a generalization affect of the type that has
been of wide interest lately.
Decision: Accept (Poster)