{'fraction_non_alphanumeric': 0.054098472916524004, 'fraction_numerical': 0.020030130795042116, 'mean_word_length': 4.109692092372288, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
VC dimension of partially quantized neural networks in the overparametrized regime

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 match the performance of state-of-the-art 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 . 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 net-work (Klambauer et al., 2017) and the dendritic neural network (Wu et al., 2018), both of which are full-precision models.

RELATED WORK
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 log w), 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ℓ log w) 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 assumptions 1 . 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. Faragó & 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 Hö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).
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.

NOTATIONS
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 R d 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 , where X, 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 by R P (f ) := P (f (X) = Y ). For an integer n ≥ 1, the empirical risk is the random variableR P,n (f ) := 1 where (X 1 , Y 1 ), . . . , (X n , Y n ) ∼ P are i.i.d. The Bayes risk inf f :X →B R P (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).

HYPERPLANE ARRANGEMENT NEURAL NETWORKS
A hyperplane H in R d is specified by its normal vector w ∈ R d and bias b ∈ R. The mapping x → σ sgn (w ⊤ x + b) indicates the side of H that x lies on, and hence induces a partition of R d 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: 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: See Fukuda (2015) Theorem 10.1 for a simple proof. A hyperplane arrangement classifier assigns a binary label y ∈ B to a point x ∈ R d solely based on the sign vector q W,b (x). Definition 3.1. Let B X be the set of all functions from X to B. A concept class C over X is a subset of B X . Fix r, k positive integers, r ≤ min{d, k}. Let Bool k be the set of all Boolean functions B k → B. The hyperplane arrangement classifier class is the concept class, denoted HAC(d, r, k), over R d defined by 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 ∈ Bool k . When performing prediction with the classifer h • q W,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 S W,b . The restriction of h to S W,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 ⊆ B X be a concept class over X . A set S := {x 1 , . . . , x n } ⊆ X is shattered by C if for all sequences (y 1 , . . . , y n ) ∈ B n , there exists f ∈ C such that f (x i ) = y i for all i ∈ [n]. The VC-dimension of C is defined as 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 ) − R P (f )| ≤ C (VC(C) + log(1/δ))/n with probability at least 1 − δ with respect to the draw of (X 1 , Y 1 ), . . . , (X n , Y n ).
Note that the above VC bound is useless in the overparametrized setting if VC(C) = Ω(# of weights). 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 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(k r ), we have VC(HAC(d, r, k)) = O(k r + 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(k r ). In particular, the number of weights used by an architecture to implement the Boolean function h does not affect the VC dimension at all.
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 ≥ 2 k . Note that this network uses ≥ k2 k weights, and k2 k ≫ k r 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 ≥ c2 k/2 / √ k can implement all k input Boolean functions, where c is a constant not depending on k. This requires ≥ c 2 2 k /k weights which again is exponentially larger than k r . Furthermore, this lower bound on the weights is also necessary as k → ∞.

A SAMPLE COMPRESSION SCHEME
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).
Denote by L C (n) the set of C-labelled sequences of length at most n. Denote by L C (∞) 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 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 κ keeps m 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: 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.
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 a i ∈ R n for each i ∈ I.
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 a 1 , . . . , a m ∈ R n and b 1 , . . . , b m ∈ R. For each subset I ⊆ [m], define We first outline the steps of the proof: 1. Using a subset of the samples 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 ∈ Bool k such that g(s i ) = h(s i ) for all i.

Now, consider the set
By Proposition 4.5, there exists a set of tuples such that W, b is also the minimum norm element of To encode the defining equations of P ′ , we need to store Note that each s i ℓ j ℓ requires 1 bit while each j ℓ ∈ [k] requires ⌈log 2 k⌉ bits. In total, encoding P ′ requires storing d(k + 1) samples and d(k + 1)(1 + ⌈log 2 k⌉) of bits.
To reconstruct g ∈ Bool k that agrees with h on all the samples, it suffices to know h when restricted to has at most k ≤r unique elements. Let s ι ℓ : ℓ = 1, . . . , k ≤r be a set containing all such unique elements. Thus, we store 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 {(x i , y i )} n i=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 2 together with the sample compression scheme for HAC(d, r, k) we constructed imply Theorem 3.6 from the previous section.

MINIMAX-OPTIMALITY FOR LEARNING LIPSCHITZ CLASS
In this section, we show that empirical risk minimization (ERM) 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.
The following minimax lower bound result 3 concerns classification when η P is L-Lipschitz: (2007)). There exists a constant C > 0 such that The infimum above is taken over all possible learning algorithmsf n , i.e., mappings from (X × B) n to Borel measurable functions X → B. Whenf 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.

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 Gyö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 ≍ n 1/(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 ≥ k2 k or ≥ c 2 2 k /k respectively. Both lower bounds on the number of weights are exponentially larger than n meanwhile VC(HAC(d, d, k)) = o(n).

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 over HANNs, which is intractable in practice.
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 Validation accuracies from 10 independent runs with random initialization and data generation. Right. Data points (circles) drawn from make moons in sklearn colored by ground truth labels. The hyperplane arrangement is denoted by dotted lines. Coloring of the cells corresponds to the decision region of the trained classifier. A cell ∆ is highlighted by bold boundaries if 1) no training data lies in ∆ and 2) ∆ does not touch the decision boundary. By Mukherjee & Basu (2017) Lemma 2.1, any Boolean function B k → B can be implemented by a 1-hidden layer ReLU network with 2 k hidden nodes. Here, the width of the hidden layer is 2 10 = 1024. Thus, the architecture in Figure 3 can assign labels to the bold boundary 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. Sub-sequently, Wu et al. (2018) proposed the dendritic neural network architecture, which further improved 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 k, the number of hyperplanes used. We ran the experiments with k ∈ {15, 100} to test the hyperparameter's impact on accuracy. The Boolean function h is implemented as a 1-hidden layer residual network (He et al., 2016) of width 1000.
We use the same train, validation, and test sets from the public code repository of Klambauer et al. (2017). The reported accuracies on the held-out test set are based on the best performing model according to the validation set. 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.  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 ≈ 10 4 and 10 5 weights, respectively. By comparison, the average number of weights used by SNN is ≥ 5 * 10 5 , while the number of weights used by DENN is at least ≥ 2.5 * 10 5 . Thus, all three models considered here, namely HANN, SNN and DENN, are overparametrized for this panel of datasets.

DISCUSSION
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.

REPRODUCIBILITY STATEMENT
All code for downloading and parsing the data, training the models, and generating plots in this manuscript are available at https://github.com/YutongWangUMich/HANN. Complete proofs for all novel results are included in the main article or in an appendix. By definition, there exists h ∈ Bool k , W ∈ R d×k of rank at most r, and b ∈ R k such that . Now, let λ j := min i∈[n] |w ⊤ j x i +c j | which is positive. Define v j := w j /λ j and c j =c j /λ j , we have |v ⊤ j x i + c j | ≥ 1 for all i ∈ [n], as desired. Note that rank(V) = rank(W).
A.2 PROOF OF PROPOSITION 4.5 and f (x) = 1 2 x 2 2 . Then ∇f (x) = x and ∇g i (x) = a i . By definition, x * I is a minimizer of which is a convex optimization with strongly convex objective. Thus, the minimizer x * I is unique and furthermore is the unique element x of R n satisfying the KKT conditions: x ∈ P I and ∃ a set of nonnegative weights Thus, x * I can be equivalently characterized as the unique element of x ∈ R n satisfying x ∈ P I and − x ∈ coni({a i } i∈I ).
In particular, x * [m] ∈ P [m] and −x * [m] ∈ coni({a i } i∈ [m] ). By the Carathédory's theorem for the conical hull (Lovász & Plummer, 2009), there exists I ⊆ [m] such that |I| = n and −x * [m] ∈ coni({a i } i∈I ). Thus, for any J ⊆ [m] such that I ⊆ J, we have −x * [m] ∈ coni({a i } i∈J ). Furthermore, J ⊆ [m] implies P J ⊇ P [m] . In particular, x * [m] ∈ P J . Putting it all together, we have x * [m] ∈ P J and −x * [m] ∈ coni({a i } i∈J ). By the uniqueness, we have 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.
In other words,f classifies all x ∈ R i as +1 if and only if P (Y = 1|X ∈ R i ) ≥ 1/2. This is commonly referred to as the histogram classifier (Györfi et al., 2006). It is easy to see that For the remainder of this proof, we write " i " to mean " i∈[k d ] ". Thus, Next, we note thatf ∈ HAC(d, d, k  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(⌈k/d⌉ − 1) ≤ d(k/d) = k hyperplanes. Sincef is constant on R i , there exists a Boolean function h ∈ Bool k such that h • q W,b | [0,1] d =f . From this, we conclude thatf ∈ HAC(d, d, k).
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 Thus, by Theorem 3.5 with δ = 1/(2n) and a union bound, with probability at least 1 − 1/n for some C > 0.
Next, we focus on Term 3. Recall that and that Our goal now is to bound the difference between the i-th summands in the above expressions for R(f ) and R * : First, consider the case that We claim that there must exist x 0 ∈ R i such that η P ( is continuous, this would contradict eq. (7).

B TRAINING DETAILS
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: 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: 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 B 1 , B 2 , . . . , B k in Figure 2. This improves generalization by preventing the training accuracy from reaching 100%.
The model HANN15 is trained with the following hyperparameters:   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. 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.