G-Net: A Provably Easy Construction of High-Accuracy Random Binary Neural Networks

We sincerely thank the reviewer for their thoughtful feedback. We appreciate the valuable remark on the novelty and contribution of our approach and are grateful for the recognition of the rigor in our approximation analysis. Below, we respond to the specific points raised by the reviewer, using "Q" to indicate questions and "W" to denote identified weaknesses.

---

Network Architecture (Q):

We did not observe any bottlenecks due to our non-standard architecture that would cause issues when scaling to larger datasets.

Because of the high-dimensional nature of HDC models and their emphasis on simplicity and interpretability, they are often evaluated on relatively smaller datasets such as MNIST, UCI HAR, and European Languages. In our experiments, we aimed to explore a more diverse set of datasets, including more challenging (in terms of achievable accuracy) and less commonly used benchmarks in the HDC literature, such as CIFAR-10. The use of very large datasets, such as ImageNet, is uncommon in HDC research due to the substantial memory and computational demands associated with high-dimensional vector encoding and classification. In future work, this can be extended to even more challenging datasets like ImageNet if applications beyond HDC are considered and lower dimensional embeddings become involved.

Beyond the binary embedding, the only non-standard aspects of the network architecture we introduce are: (1) $\ell_2$-norm normalization of the weights and input, and (2) composition of the activation by $\arcsin$. First, the $\ell_2$-norm normalization is equivalent to using a cosine similarity instead of a standard inner product when composing layers of the network. In fact, recent work has shown that such normalization helps with the performance of neural networks. References [32] (Salimans & Kingma), [24] (Luo et al.), [38] (Wu et al.), and references therein highlight key advantages of $\ell_2$ normalization, which we briefly summarize here. In [32], the authors demonstrate that $\ell_2$ normalization improves gradient conditioning and accelerates convergence during optimization. Luo et al. [24] advocate for using cosine similarity (equivalent to the Pearson Correlation Coefficient) instead of the dot product in neural networks, as the unbounded nature of dot products can lead to high variance in neuron activations. This high variance increases sensitivity to input distribution shifts, impairs generalization, and exacerbates internal covariate shift, ultimately slowing down training. Wu et al. [38] extend this idea to convolutional layers by applying cosine similarity, aiming to mitigate the variance issues associated with standard convolution operations. While methods such as batch normalization have gained more popularity due to their simpler gradient computations, both prior literature and our experimental results consistently show that $\ell_2$ normalization enhances model accuracy. Across a wide range of standard CNN architectures, we observed that the G-Net variants incorporating $\ell_2$ normalization consistently outperformed their CNN counterparts in terms of accuracy.

Second, empirical results suggest that composing the activation with the $\arcsin$ function does not significantly impact performance. In practice, neural networks have been successfully trained using a wide range of nonlinear activation functions, which may explain why our approach achieves comparable accuracy to standard activations such as ReLU or Sigmoid. Rather than heuristically introducing a new activation function, the G-Net formulation provides a principled justification for the proposed activations. We believe this offers a meaningful technical contribution to the broader discussion on activation function selection.

---

Limited Motivation & Preference Over a Standard CNN (W):

We began the paper by presenting HDC as the central motivation. As noted in the introduction and discussed in detail in Section S1 of the Supplement, HDC techniques typically consist of an embedding step followed by an inference step. However, these components are often designed heuristically and lack effective coordination, which is a key reason for the reduced accuracy commonly observed in HDC models. To address this issue, Section 2 introduces the bundle embedding problem and explains that resolving this problem could enable HDC models to achieve accuracies comparable to those of high-performance models trained directly in the primal space (i.e., with floating-point storage and operations). The remainder of the paper presents our proposed strategy for solving the bundle embedding problem, including its mathematical formulation, theoretical analysis, and empirical evaluation. We would be glad to incorporate any additional comments that might help further clarify or strengthen the motivation behind our work.

---

HDC Link (W):

Consider a classic HDC framework, where the embedding stage maps input samples into high-dimensional binary vectors, followed by a simple linear classifier applied to these representations. While conceptually elegant, this approach often lacks the flexibility and expressive power required for complex datasets, resulting in poor classification performance.

To address this limitation, one can envision a multi-stage embedding pipeline designed to progressively transform the data such that the samples become increasingly linearly separable. The key challenge then becomes: "how can we coordinate these consecutive embeddings to ensure that, by the final stage, the data is suitably structured for accurate linear classification?"

This is precisely where the G-Net framework comes into play. Once trained, each layer of the EHD G-Net can be interpreted as an embedding stage. These stages are not independent or heuristic but are carefully coordinated through the G-Net's architecture. As a result, by the time the samples reach the final classification layer, the data has been transformed to a space where class separability has matured, allowing the final softmax layer to perform effective and accurate classification.

The proposed framework can essentially be viewed as an HDC pipeline with multi-stage embeddings, in which the consecutive embedding stages are systematically coordinated through the initial training of the G-Net in the primal data space. This viewpoint has already been briefly discussed in the paper (lines 187-191) and Section S1 of the Supplement; in the final version, we will further clarify this point.

---

Proper Task Definition (W):

Regarding the task specification, as stated earlier, under an HDC framework, the problem statement was solving the bundle embedding problem, where G-Net was proposed as a solution strategy (please refer to the extended response above related to limited motivation).

---

Variable Names in Fig 2 (W):

We appreciate the comment. If we wanted to use global variables, we would need to use many variables and long expressions in Figure 2. Instead we followed the convention that the input to each block of Figure 2 is denoted by $x$, and the output is denoted by $y$, and each block explains how the input ($x$) and output ($y$) are related. Upon your note, we added a clarifying remark in the caption that for each block $x$ represents the input and $y$ represents the output.

We sincerely thank the reviewer for their thoughtful comments and valuable feedback. We are grateful for the recognition of our theoretical contribution and appreciate the encouraging remarks highlighting its distinction from prior HDC studies. Below, we respond to the specific points raised by the reviewer, using "Q" to indicate questions and "W" to denote identified weaknesses.

---

Implications of the $\ell2$-Normalization (Q & W):

References [32] (Salimans & Kingma), [24] (Luo et al.), [38] (Wu et al.), and references therein highlight key advantages of $\ell_2$ normalization, which we briefly summarize here. In [32], the authors demonstrate that $\ell_2$ normalization improves gradient conditioning and accelerates convergence during optimization. Luo et al. [24] advocate for using cosine similarity (equivalent to the Pearson Correlation Coefficient) instead of the dot product in neural networks, as the unbounded nature of dot products can lead to high variance in neuron activations. This high variance increases sensitivity to input distribution shifts, impairs generalization, and exacerbates internal covariate shift, ultimately slowing down training. Wu et al. [38] extend this idea to convolutional layers by applying cosine similarity, aiming to mitigate the variance issues associated with standard convolution operations. While methods such as batch normalization have gained more popularity due to their simpler gradient computations, both prior literature and our experimental results consistently show that $\ell_2$ normalization enhances model accuracy. Across a wide range of standard CNN architectures, we observed that the G-Net variants incorporating $\ell_2$ normalization consistently outperformed their CNN counterparts in terms of accuracy.

Importantly, $\ell_2$ normalization imposes no practical limitations on the learning task. In classification settings with a softmax output layer, scaling the outputs does not affect the resulting class probabilities. For regression problems, the response variable can be scaled by a factor such as $y_{max}$, or an additional learnable scaling parameter can be introduced in the output layer to match the scale of the target values. For implementation purposes, Section S12 of the supplementary material provides a detailed and comprehensive guide for applying $\ell_2$ normalization across different layers, such as fully connected, convolutional, general linear, and classification versus regression output layers. It also presents numerical strategies for incorporating bias in linear layers to enhance the concentration properties of the EHD G-Net.

---

RASU G-Net over a TASU G-Net (Q):

As noted in Section 3 (lines 199–200), the RASU layer outputs non-negative integer vectors, while the TASU layer produces fully binary outputs. When hardware resources support integer operations—such as via expanded binary representations—RASU networks typically yield higher accuracy, as shown in our experiments. Otherwise, TASU networks operate entirely in binary mode, with a slight trade-off in accuracy.

---

Assumption $|w_i^T x| > l_{min} > 0$ for TASU analysis (Q):

This assumption stems from the properties of the sign function, which in our formulation outputs only $\pm 1$ and is undefined at zero, see the proof of Theorem 4.2. While it is possible to define sign$(0) = 0$, doing so would result in a trinary rather than binary network. Many HDC frameworks address this by randomly assigning $\pm 1$ when a zero occurs. In practice, the condition $w_i^T x = 0$ is extremely rare, and experimentally, how we handled this edge case didn't make a practical difference in the results. An alternative presentation of Theorem 4.2 could have excluded neurons producing zero outputs from the analysis, as, given their rarity, their effect on discrepancies is minimal. However, the current form of Theorem 4.2 offers a more concise and readable presentation.

---

Minor Distribution Shift of Wide Neural Networks (Q):

To illustrate this property numerically, we performed an experiment (which will be included in the revised final paper supplement) where a wide G-Net layer is initialized with row-normalized Gaussian weights. The experiment shows that, after training, the shift in the weight distribution is minimal. This behavior is well-known and has been highlighted in prior works, such as reference [16] (on neural tangent kernels), which demonstrates this property in wide neural networks. In Theorem 4.4, we assume that a trained G-Net layer follows the normalized Gaussian model of equation (8). If the layer weight initialization follows (8), given that wide Gaussian layers experience only minor shifts during training (and the $\ell_2$ norm of all rows concentrate around a similar value), the trained weights are still expected to remain close to (8), supporting the applicability of Theorem 4.4 assumption. Moreover, the Gaussian initialization makes the weights initially “spread out”, and for sufficiently wide networks, they tend to remain so throughout training. This “spread-out” property is key to Corollary 5.1, which leverages Grothendieck’s identity to show that it approximately holds for Rademacher vectors when the inner product factors are well-dispersed. This connection enables the extension of Gaussian-based embedding results to Rademacher embeddings. Informally, the importance of the “spread-out” condition lies in its role in enabling central limit theorem behavior, allowing Rademacher embeddings to approximate Gaussian distributions—more precisely, it facilitates the application of a multivariate Berry–Esseen-type theorem (see Supplementary Material Section S8, Theorem S2).

---

Network Consistency Analysis (W):

We appreciate the note. For TASU layers, the near-isometry property in equation (7) can still be established using a similar strategy, thanks to the symmetry of the activation function. However, for RASU layers, the proof requires some modifications due to the one-sided nature of the ReLU activation. Including these additional details would have complicated the step-by-step exposition and reduced clarity, so we felt it was more appropriate to defer them to a future contribution.

---

The $\sqrt{n/p}$ Discrepancy (W):

As demonstrated numerically in the experiments, the performance of Gaussian and Rademacher embeddings are very close and sometimes indistinguishable (e.g., see panel (d) of Figure 3). As stated shortly after Proposition 5.2 (lines 323 and 324), taking into account the fact that $\|y\|_2$ scales with $\sqrt{n}$, the relative discrepancy is of order $O(\sqrt{1/p})$ diminishing with increasing $p$, which makes it less concerning.

We sincerely thank the reviewer for their valuable and insightful feedback. We truly appreciate the recognition of our contributions and the encouraging remarks regarding the broader potential of our method for lossless binarization in neural networks.

---

Computational Efficiency (W1):

Our network architecture has three key properties of HDC models: (1) there are no significant bits, so the architecture is robust to model noise and computing environments where random bit flips may occur; (2) the architecture can be implemented only using simple operations, binary XOR and popcount; and (3) the models have inherent randomness, and can be sampled from a distribution of models, which provides robustness to adversarial constructions. Note that we demonstrate (1) empirically in Supplementary Material Figures S4 and S5. In some cases, a trivial binarization given by considering floating-point weights as bit sequences may use fewer bits, but would lack these properties. Our work introduces a new theoretically justified random binary neural network architecture. An interesting direction for future work, which makes the method accessible beyond HDC applications, is compressing the embedded network architecture, which our G-Net analysis shows performs at the same level as standard DNNs with theoretical guarantees.

---

Figure 2 Note on Layer-wise Embedding (W2):

We thank the reviewer for pointing this out. There was a typo in Figure 2: the text “normalization” in the second and third blue blocks of panel (b) should be replaced with “sign embedding,” and this will be corrected in the final version. Regarding your comment, when using a Gaussian embedding, note that all inputs to interior layers in EHD G-Net are either binary or integer, so the operations reduce to simple additions and subtractions—no multiplications are needed for inner products. These additions and subtractions can be performed at low precision, as ultimately a sign function follows the inner product. In fact, a Rademacher vector can be seen as an extremely low-precision version of a Gaussian vector, and both theoretically and empirically, their performance is shown to be comparable. In practice, we recommend the Rademacher embedding for its fully binary operations and almost identical performance as Gaussian embedding (please refer to panel (d) of Figure 3 as an example).

---

Prior Work on Binarization/Quantization (W3):

Thanks for the suggestion. In addition to the current cited works on binary neural networks (BNNs), we will perform a more comprehensive review and update the final version to include references and comparisons to state-of-the-art quantization and binarization techniques (suggested by Reviewer fAxG). The initial submission placed less emphasis on BNNs for the following reasons:

• Our proposed technique is both inspired by and fundamentally grounded in the Hyperdimensional Computing (HDC) paradigm, where binary high-dimensional models are constructed without requiring complex training procedures. In contrast, training conventional BNNs often involves significant numerical challenges due to the discrete nature of the problem and difficulties in approximating gradients.

• HDC models typically incorporate an element of randomness, which is also a key feature of our proposed framework. Once a G-Net is constructed, exponentially many EHD G-Nets can be derived from it through a randomized process. This level of inherent variability and randomness is generally not present in conventional BNN training approaches.

• A central contribution of our framework lies in providing rigorous mathematical guarantees on the performance of the constructed models. To the best of our knowledge, most existing BNN training methods rely on heuristic approaches and lack such guarantees, largely due to the inherent difficulty of the problem. Our method, through a novel randomized construction, introduces G-Nets as a new class of hardware-efficient architectures that are amenable to mathematical analysis.

We greatly appreciate the reviewer’s constructive comment and agree that incorporating additional references and adding these comparisons can broaden the scope of the work and enhance its relevance to a wider audience.

We sincerely thank the reviewer for their thoughtful comments and valuable feedback. We are grateful for the recognition of our work as an innovative contribution with the potential to advance low-resource deep learning. Below, we respond to the specific points raised by the reviewer, using "Q'" to indicate questions and "W'' to denote identified weaknesses.

---

Task Generalization (Q & W):

Yes, our techniques are immediately applicable to other domains. In particular, since our approach is compatible with linear, convolutional, and normalization layers (when these layers are appropriately modified by composing the activation with an arcsin function and adding $\ell_2$-normalization), it can immediately be applied in cases where network architectures using these layers are effective. To provide concrete examples, we applied our method to AG News Classification dataset (as an NLP dataset) and the FaultDetection-A dataset from the UCR time-series repository (as a time series dataset), and obtained results comparable with neural network approaches. These experiments will be included in the final version of the manuscript.

---

Dimensionality vs. Efficiency (Q & W):

In the Supplementary Material Figures S2 and S3, we demonstrated how model accuracy depends on the hyperdimension. If the hyperdimension is restricted by hardware constraints, then these plots can be interpreted as illustrating model accuracy for a given hardware constraint. Moreover, in the Supplementary Material, Figures S4 and S5 demonstrate the robustness of the models to bit-flips; these figures illustrate that the network architecture is robust to computing environments where random bit flips may occur.

---

Comparison with Binary Neural Networks (Q & W):

In the final version of the paper, we will include a comparison with several well-known Binary Neural Network (BNN) frameworks, including Bi-Real Net, XNOR-Net, ABC-Net, and BinaryConnect. This comparison was not included in the initial submission for the following reasons:

• Our proposed technique is both inspired by and fundamentally grounded in the Hyperdimensional Computing (HDC) paradigm, where binary high-dimensional models are constructed without requiring complex training procedures. In contrast, training conventional BNNs often involves significant numerical challenges due to the discrete nature of the problem and difficulties in approximating gradients.

• HDC models typically incorporate an element of randomness, which is also a key feature of our proposed framework. Once a G-Net is constructed, exponentially many EHD G-Nets can be derived from it through a randomized process. This level of inherent variability and randomness is generally not present in conventional BNN training approaches.

• A central contribution of our framework lies in providing rigorous mathematical guarantees on the performance of the constructed models. To the best of our knowledge, most existing BNN training methods rely on heuristic approaches and lack such guarantees, largely due to the inherent difficulty of the problem. Our method, through a novel randomized construction, introduces G-Nets as a new class of hardware-efficient architectures that are amenable to mathematical analysis.

---

Computational Complexity (W):

Because of the high-dimensional nature of HDC models and their emphasis on simplicity and interpretability, they are often evaluated on relatively smaller datasets such as MNIST, UCI HAR, and European Languages. In our experiments, we aimed to explore a more diverse set of datasets, including more challenging (in terms of achievable accuracy) and less commonly used benchmarks in the HDC literature, such as CIFAR-10. The use of very large datasets, such as ImageNet, is uncommon in HDC research due to the substantial memory and computational demands associated with high-dimensional vector encoding and classification. While we believe that the G-Net embedding theory and techniques have the potential to be applied to other domains and large-scale problems, this work represents an initial step. There remain several opportunities for improvement to enhance the scalability of the proposed framework for more complex machine learning tasks, beyond HDC.