G-Net: A Provably Easy Construction of High-Accuracy Random Binary Neural Networks
Authors: Alireza Aghasi
Nicholas F. Marshall
Saeid Pourmand
Wyatt D. Whiting
Venue: NeurIPS 2025 poster ()
Keywords: Hyperdimensional Computing
Random Binary Neural Networks
Primary area: theory
TL;DR: High-Accuracy Random Binary Neural Networks

Abstract: We propose a novel randomized algorithm for constructing binary neural networks with tunable accuracy. This approach is motivated by hyperdimensional computing (HDC), which is a brain-inspired paradigm that leverages high-dimensional vector representations, offering efficient hardware implementation and robustness to model corruptions. Unlike traditional low-precision methods that use quantization, we consider binary embeddings of data as points in the hypercube equipped with the Hamming distance. We propose a novel family of floating-point neural networks, G-Nets, which are general enough to mimic standard network layers. Each floating-point G-Net has a randomized binary embedding, an embedded hyperdimensional (EHD) G-Net, that retains the accuracy of its floating-point counterparts, with theoretical guarantees, due to the concentration of measure. Empirically, our binary models match convolutional neural network accuracies and outperform prior HDC models by large margins, for example, we achieve almost 30\% higher accuracy on CIFAR-10 compared to prior HDC models. G-Nets are a theoretically justified bridge between neural networks and randomized binary neural networks, opening a new direction for constructing robust binary/quantized deep learning models. Our implementation is available at \url{https://github.com/GNet2025/GNet}.

G-Net: A Provably Easy Construction of High-Accuracy Random Binary Neural Networks
Alireza Aghasi'
Nicholas Marshall
Dept. Electrical Engineering and Computer Science
Dept. Mathematics
Oregon State University
Oregon State University
alireza. wwwpe/aa..gaiiioieoe wwwassi@regoosstteee... edu
marsni www.rnoosttteeeeeeeoooooooooooee edu
Sacid Pourmand
Wyatt D Whiting
Dept. Electrical Engineering and Computer Science
Dept. Mathematics
Oregon State University
Oregon State University whit whitinay@oregonstatee edu
courmaan@@rregosttatee edu
Abstract
We propose novel randomized algorithm for constructing binary neural networks with tunable accuracy. This approach is motivated by hyperdimensional computing (HDC), which is brain-inspired paradigm that leverages high-dimensional vector representations, offering efficient hardware implementation and robustness model corruptions. Unlike traditional low-precision methods that use quantization, consider binary embeddings of data points in the hypercube equipped with the Hamming distance. We propose a novel family of floating-point neural networks, G-Nets, which are general enough to mimic standard network layers. Each floating- point G-Net has a randomized binary embedding, an embedded hyperdimensional (EHD) G-Net, that retains the accuracy of its foating-point counterparts. with theoretical guarantees, due to the concentration of measure. Empirically, our binary models match convolutional neural network accuracies and outperform prior HDC models by large margins, for example, we achieve almost 30% higher accuracy on CIFAR-10 compared to prior HDC models. G-Nets are a theoretically justified bridge between neural networks and randomized binary neural networks, opening a new direction for constructing robust binary/quantized deep learning models. Our implementation is available at https:: / thub. com Soon//Neet22///00 /eett
Introduction
We motivated by hyperdimensional computing (HDC), brain-inspired computational paradigm that uses high-dimensional vectors as the basic elements of computation [33]. Applications of HDC include classification and regression [7, 10, 17, 35, 39]. reinforcement learning [4, 25], and dimensionality reduction [14, 24]. Recent works have also explored online learning approaches [10, 12] and advanced the theoretical understanding of HDC [26, 31, 37J. HDC methods can be efficiently implemented on hardware, making these models attractive for edge and low-energy computing [3, 5, 13, 16, 18, 19]. For readers less familiar with HDC, Section A of the Appendix offers detailed taxonomy and broader overview of HDC methods.
For predictive tasks, an HDC pipeline typically consists of two core components: hyperdimensional embedding module, which often carries some component of randomness, and an inference module [32]. The embedding transforms input data into high-dimensional representations (often binary
*Corresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

hypervectors) that retain key structural features while simplifying the data space. The inference module, commonly a lightweight classifier. operates on these embeddings and often resembles a support vector machine in decision making [20, 19]. These components are generally decoupled, and due to limited representational capacity, lack of task-specific learning (especially in the embedding stage) and the simplicity of the overall architecture, HDC models struggle to match the performance of state-of-the-au predictors. Moreover, the ligh-dimensional and highly structured (e.g., binary) nature of the embedding space hinders the training of more sophisticated models in that domain.
In this paper, we introduce a new class of (random) binary neural networks that operate in the hyperdimensional Hamming space without requiring training within that space. Typical approaches to training binary neural networks include using a srrright-througe estimator (STE) [6. 28], a continuous piecewise-defined approximation [21], thermometer encoder [38]. or quantization [9, 11] (see Section B of the Appendix for a more detailed overview of binary neural networks). In contrast, our approach leverages the geometry of the hypercube and random matrix theory. We propose a class of floating- point networks, G-Nets, that can be converted into randomized binary networks with accuracy guarantees derived from the concentration of measure. Central to our method is the random binary encoding é RP + {-1, 11.,, defined as Φ(x) = sign( G where G E R xp has i.i.d, standard normal entries-a a common HDC encoding scheme [27, 13]. For large N, Grothendieck's ' identity (see Lemma 3.1) ensures that N (6(z), o(y)) ~ 2 arcsin (a. y)) when 2, y E S Thus, inner products in SP-1 can be approximated by those in the Hamming space, up to a known nonlincarity. By absorbing this nonlinearity into the activation functions, we construct a new class of multi-layer neural networks that can be trained on source real-valued data and directly mapped along with the data to the binary hyperdimensional space, maintaining comparable predictive performance.
Empirically, our approach circumvents the need to train expressive models directly in the binary domain, which is both high-dimensional (N >> p) and structurally constrained (posing significant challenges for fitting predictive models). Theoretically, the proposed framework for constructing high-performing binary neural networks addresses key open questions in HDC research. First, address questions about how far HDC models can be pushed to achieve accuracies on par with neural networks (asymptotically, the accuracies of the proposed hyperdimensional models converge to that of a G-Net as N increases). Second, we provide non-asymptotic results on how large the hyperdimension N needs to be for desirably close performance to that of G-Net. At a more abstract level, the proposed framework can be interpreted as an inexpensive access to a meta-disttibution over binary neural networks tailored a prediction task, where G-Net controls its mean accuracy and the hyperdimension controls the level of concentration. Sampling from this distribution without training may benefit applications such as privacy, robustness, and ensemble learning. Moreover, individual binary networks drawn from this distribution can be further refined through fine-tuning techniques.
The remainder of the paper is organized as follows. Section 2 introduces the bundle embedding problem, which concerns embedding both data and predictive models coherently, with minimal loss in performance within the embedded space. Section 3 presents the core G-Net framework as solution to this problem and outlines architectural variations designed for varying levels of hardware compatibility. In Section 4, we provide detailed consistency analysis between the performance of G-Net and its byperdimensional counterpart (EHD G-Net), including non-asymptotic, layer-wise, and network-level results showing how the choice of hyperdimension governs the discrepancy between the two. Section demonstrates, under realistic conditions, how the encoding can be significantly simplified by replacing Gaussian matrices with Rademacher matrices. Finally, Section 6 presents numerical experiments that showcase the strong performance of the proposed method, followed by discussion and concluding remarks. Proofs of all theoretical results, along with additional experiments and implementation details, are provided in the Appendix.
Notations. Let S and BT denote the unit sphere and unit Euclidean ball in R", respectively. We use lowercase letters for vectors and uppercase letters for matrices. For two binary vectors (-1, Du (x. y) represents the normalized Hamming distance: DH (z. y) = n =n : v, & yi yiHl- For two vectors y y E g--1, Da(a, y) represents the normalized geodesic distance between the two vectors obtained by dividing the smaller angle between the two vectors by æ. A random vector/matrix is called Gaussian (or Rademacher) if the elements are independently drawn from a standard normal distribution (or Rademacher distribution taking values 1 and -1 with equal probability 1/2). We use script font for random quantities (c.g., g, G). We use teletype font for functions that operate
E

---

sign Aggul (aa
PCs
i (gg)(Ga)
po:
PCs
PG
2 e g
Pa(a), X' (-1,1)
Pa(a), ( 13.000
poly a+)
joly .2) R poly xx)
poly ()) = poly at)
colileembediiii
Figure 1: A graphical demonstration of data embedding, and bundle embedding
on matrices/vectors in an element-wise fashion, e.g., sign(z) is vector with sign(æ;) as its i-th element.
2 Bundle Embedding Problem
Quantization simplifies data representation and computation better suit hardware constraints. Its effectiveness is maximized when the geometric structure of the data is preserved, motivating the use of (nearly) distance preserving mappings, often referred to as (near) isometries.
Definition 2.1. Suppose that >> and let X and y be metric spaces equipped with distances Dx and Dy, respectively. A mapping A X' + y is called an E-near-isomety if for all Iι, 22 E X: (x1 x2)] S E.
[Dy ((a11).Axx))
A prominent example of such mappings is the random binary embedding, where real-valued vectors are converted to high-dimensional binary codes via a random linear projection followed by a quantiza- tion operator (such as sign function). Typically, such embeddings takes the form A(z) = s gign (Zx), where G is a Gaussian matrix. is well-understood that by increasing the height of G. the mapping can be made arbitrarily close to an isometry, stated below.
Proposition 2.1. For a Gaussian matrix G E RNx", consider the mapping A(x) = sign( from X S (equipped with a geodesic distance DG) to to 1-1,1)" 13." (equipped with a normalized Hamming distance DH). Fix & E (0. 1), then there exist absolute constants and such that if A is an e-near- isomeryy That
N cnn/s?, with probability exceeding
Vz,ye Sa-1
[DH (sign (Gz), sign (Cu)) Do(x, Se.
(1)
Throughout this paper, refer to X as the primal space and y as the embedded space. For sufficiently large N, Proposition 2.1 guarantees, with high probability, an E-consistency between the pairwise distances measured in the primal space X' = Sa-1 and the embedded space y = [-1, To be able to use a similar metric on both spaces, for the same setting as Proposition 2.1, one may consider the normalized mapping A(x) = -11/22ign//
which will map unit vectors s to unit vectors in g As detailed in the proof discussion of Proposition 2.1, in this case, the consistency result (1) can reformulated as
Va, y E 5m-1
sin
ST (o N (N-1/2 DN
(Gx), (G=),N-11 N/2 sigg (Qv)) Da(a, w) se, (2)
where a geodesic metric is used on both spaces. Equation (2) reveals that no matter how small & is, there is an intrinsic (g-) deformation of the geodesic distance when applying A to the source data. To visually illustrate the effect of this embedding, Figure I shows the result of applying A to a dense set of points on S using N 100 and N 1000. The binary codes produced in 1-1,1)" are then visualized in R33 via their first three principal components to illustrate how the representation improves as N increases. Although the spherical geometry is nearly intact for N 1000, the deformation is noticeable when comparing the color labels the coloring pattern on the right deviates from that of the original on the left.
In this paper, the bundle embedding problem broadly refers to the problem of coherently embedding both data and predictive model defined on it, such that the model remains functional in the embedded space without requiring retraining. As a motivating example, suppose that a model po (x) is trained on the source data X' illustrated in Figure 1. After binary embedding, such a model is unusable due
3

---

to two main issues: first, the data format has changed from continuous to binary, and, second, there a nonlinear distortion introduced by the embedding, which standard predictors are not equipped to correct easily. On the other hand, training a high-accuracy classifier in the embedded space that operates in binary mode is itself difficult, owing to both the discreteness of the problem and the often-large dimension N. In this case our goal is to construct predictive models that can be embedded along with the data to operate in binary mode while maintaining accuracy.
To this end, we introduce a flexible class of neural networks, whose performance remains close after the data are quantized via a random sign embedding, ensuring consistent accuracies in both the primal and embedded domains. Rewiring these models to their binary neural network counter- parts is as simple as going through random sign embedding of the primal model weights. In a hyperdimensional-coo computiig pipeline, this approach supplies high-accuracy predictors that operate directly on the binary- binary-represented data, obviating any training in the embedded domain.
G-Net Main Idea
At a high level, many standard feed-forward neural networks can be viewed as a cascade of L layers given by yt = ore (Wrgt-1)). where W/ are learnable weight matrices, Yt is the output of the ε-th layer, and og is nonlinear, typically element-wise, activation function. In this section, we discuss the bundle embedding of class of neural networks originally operating on real-valued data, demonstrating how they be systematically transformed to operate binary data while maintaining accuracy controllably close to the original real-valued model. The construction is grounded in Grothendieck's identity (cf. [34, page 63]); hence, we refer to the proposed architectures as G-Nets.
Lemma 3.1 (Grothendieck's 's Identity). Let g be a standard Gaussian vector in R'. Then, for fixed vectors u, U R EE [sign((" (g T u) sign(g v)] = aresin [| ||
u
If G E IR XXP is standard Gaussian matrix with rows g," then by the law of large numbers
1 N' N Σ
1 (sigu(CU) N
2
sign(g, T u) sign(g, v) arcsin (u, v)).
U, U.E
This observation offers new perspective on Grothendieck's Identity: through the random sign embedding, inner products in S are approximately mapped to inner products in (-1.1} up to some scaling and sine distortion. More generally, when W RRxp has normalized rows (that is, w. E S E (1.....7) n)), and y E S then 1 sign where sign and arcsin functions act element-wise. Applying a suitable activation (later to be specified) can preserve this approximation, and for general input E IR" deliver neural network layer of the form
.....,n)..
N gn (WGT)& sign (Gy) x 2 Parcsinn (Wy), y).
W (W (Bull
(sign (WG") sign (Gv)),
where = To 2N arcsin. Observe that the left-hand side of (3) operates on inner products of real-valued vectors, while the main right-hand side operation is inner products between their binary embeddings. The activations differ between the two sides, since further carries the nonlinear distortion introduced by Grothendieck's identity. the discrepancy between the two sides of (3) is controllably small (specifically, by picking large N), then cascading multiple layers which are embedded via independent Gaussian matrices Ge, forms a neural network operating in the embedded regime, with performance that closely matches its primal counterpart. The above construction and conversion can be extended to L layers as follows.
Definition 3.1 (G-Net). Let flu..... .u....,.0 nu be a sequence of positive integers, and be activation function. Suppose that , is an nl X n4-1 matrix whose rows are l fz-normalized for 1...., L, and let an imput vector yo
I E Rno be given. We define the oulput yr. of an L-layer G-Net L, where = = 2 arcsin.
iteratively by = σ We [luee
for for
9e-1
Definition 3.2 (EHD G-Net: Embedded Hyperdimensional G-Net). Suppose a trained G-Net is given as in Definition 3.1. Fix sequence of hyperdimensions N1y..., Ni, and let Ge be independent Gaussian matrices of size N₃ X T4-11- We define the output dy of the L-layer Hyperdimensionnll embedding of the given G-Net iteratively by Ūe T rssign(W,GG) sigu(Grejt-1),,
i = I,..., We propose three element-wise choices for r. The simplest choice is the identity map, r(x) = Id(x:). primarily used for analysis purposes, which corresponds to the arc-sine activation unit a(x)

---

Primal Layer
layer L
layer F
layer
In
2
Inps
momnslled Road
linor tranifomm
nommalzation
actvation
Lineutranntoon
nommaliation
selvotion
nomma Eze
trandomm
nomaliatioo
inear sunidrm
txpur
weight
layer embedking thmugh
embeddinng
embooking
embeddiing
pitralactivatin optionss
random marri
dhrough G2
througgh Oo
through Gi
See aed dl
sign cunballaa mabalddal
Trour tranformm
sign emboading
iitent activatio
embkaddd
inour inoir tranform
sign embolding
Satett adivalio
sign embedded
sign embboliing
sign(W ( G jx
lppa
crabesiled wegghts
cniookinn
Embedded Layer
coresponddngg activation units the endeciiial bayrr
(b) Figure 2: (a) A G-Net layer (top), and its corresponding EHD G-Net layer (bottom); the input each block is denoted by and the output is represented by y; (b) A G-Net and corresponding EHD G-Net constructed by cascading the proposed layer blocks
(a)
ASU(x) aarcsin(z) in the G-Net architecture. Additionally, we T(z) ReLU(x), and T(x) = sign(1 (x). which lead respectively to the following G-Net activations a:
arcsin(x))
x N 0, x O,
2k
RASU(x))
and (A) tanh
aresin(z))
0.
In the last activation, we employed smooth approximation of the sign function, specifically 7(r) = tanh (sx) for sufficiently large K, to ensure that the associated G-Net activation remains smooth. The top panel of Figure 2(a) presents the architecture of a G-Net layer, and the bottom panel depicts the corresponding EHD G-Net layer. An L-layer G-Net and correspondingly a similar- depth EHD G-Net can be constructed through the composition of the proposed layers. Note that in Definition 3.2 and Figure 2, we omitted the normalization factors 1/Ne. In intermediate layers, this factor can be absorbed by the subsequent sign operation. For the final layer, neglecting this normalization merely affects the output's scale, which is typically inconsequential.
The core bundle embedding process involves first training G-Net on the original real-valued data to learn the weights We, and subsequently converting it into an EHD G-Net by selecting sufficiently tall Gaussian matrices Ge- The resulting EHD G-Net is sequential neural network featuring binary weights sign(W:C) and appropriately adjusted activations, which are acquired without truining on the embedded binary data. Once the EHD G-Net is constructed, the first sign embedding block of the first layer (i.e., sign sign(Cix)) can be interpreted as the random sign embedding of the source data, and the rest of the pipeline (shown the dashed box in the bottom panel of Figure 2(b)) can be viewed as an embedding of the primal inference module. Since HDC models typically employ a simple inference stage (see Section A of the Appendix), the framework can equivalently be viewed as an HDC pipeline with multi-stage embedding: the first - 1 layers constitute the embedding stack, and the final classification layer serves the inference block. Under either interpretation, unlike many current HDC frameworks, the designs of our embedding and inference modules are tightly coupled by construction.
The primary distinctions between a G-Net layer (top panel of Figure 2(a)) and a standard feed- forward network layer are the nz-oomaaliittion applied at the input, and the enforced row-wise normalization on the learnable weight matrices W. While these constraints may initially seem to limit the flexibility and expressiveness of G-Nets, they have been shown to accelerate training and enhance the generalization accuracy [30, 22, 36], making them advantageous design choices rather than limitations. Furthermore, the choice of activation function, which is the sole distinction between RASU and TASU G-Nets, directly influences the operating mode of the resulting EHD G-Nets. In RASU networks, each layer output (i.e., the right-hand side of (3)) is non non-negative integer vector, whereas in TASU layers, the output is binary, allowing their EHD G-Nets to operate entirely in binary mode.
The rest of the paper delves more deeply into a theoretical understanding of the proposed framework. We first examine how the hyperdimension N controls the approximation error between G-Net
5

---

layer and its EHD counterpart, and how these errors accumulate when multiple layers are cascaded. Although Grothendieck's 's identity naturally linked Gaussian distributions, Section 5 shows that much simpler Rademacher embeddings offer comparable guarantees.
From a practical standpoint, the framework extends well heyond fully connected layers: convolution, bauch-normalization pooling, and similar modules can all be incorporated into G-Net and subse- quently embedded into hyperdimensionall model. In addition to addressing such details in Section N of the Appendix, we will also discuss details such as handling the bias term for all such layers, and the activation chosen for the last layer, which determines whether the resulting network behaves as a classifier or a regressor.
4 Consistency of G-Net and EHD G-Net
This section presents a non-asymptotic analysis of the consistency between G-Net layer and its hyperdimensional embedding, providing high-probability bounds on the required value of N to achieve a target discrepancy between the primal and embedded layers. First, we analyze the RASU layer, which yields bounds analogous to those of an ASU layer.
Theorem 4.1. Consider a RASU (or ASU) layer with input x E SP-1 and weight matrix W E T2xp whose rows are Eg-ormmalized Let the layer output be given by y RASU(Wa:) (or = ASU(Wx) x)). Define the embedded output as ÿ = ReLU (sign(WGG
sign((x)) (or ÿ Id (sigm([ TT edgn(Gx)) where G E RNxx is a standard Gaussian matrix. Then, for any c > 0, with probability at least exp(-c): 11 vll2 S /2N-1(c+ (c log 2n)n.
Corollary 4.1. To ensure that the discrepancy between a RASU/ASU layer output and its hyperdi- mensional embedding satisfies 2 3112 S it is possible choose the embedding dimension N such that
N = O (c logn.
(4)
few remarks are in order. First, the log n term in (4) arises from reusing the same embedding matrix G across all rows of W, which induces dependencies among components of the discrepancy vector. In the discussion following the proof of Theorem 4. in the Appendix, we argue that if independence were enforced- e.g..
e.g.. by using a distinet embedding matrix Gi for each row w; and computing this would remove the log factor but at a considerable cost in both computation and memory. Second, in our discrepancy analysis, we compare y to the scaled output + purely for normalization purposes, since ÿ/ is integer-valued by construction. As stated before, this scaling does not affect downstream computations, as jī is passed through another sign-based embedding layer in subsequent processing, rendering the 1/N scaling irrelevant in practice. Next, analyze a TASU layer, where in addition to the standard discrepancy, one also needs to account for the error introduced by approximating the sign(-) function with tanh(r-).
ü: ReLU (sign(w; G.T (sig)(G.x)) -his
Theorem 4.2. Consider a TASU layer with outpul y = TASU, (Wx), where x E SP-1 and W E RRux has normalized rows w. (Ilwa]l2 = 1 for i I,...,n)) n)) Define the embedded layer output as g = sign (sign(WG)) T) (sinn(G))) where G E Nx is a standard Gaussian matrix, Assume
|u: x 2 Emin > O, == I....,n n.
(5)
Pick target discrepancy& 8 S /n and set K. 2m log Ayn Then, for any scalar e 0, selecting N 2 8(c+ 2n 2n)nx?//" guarantees that with probability exceeding 1 - 3 exp((-c): Ily- 0l12 S e.
We emphasize that assumption (5) is essential for the analysis, to handle the discontinuity of the sign function. Specifically, when w; = 0 for some row i, the TASU output yields y; = 0, whereas the corresponding embedded output Th takes a binary 11 value as the output of a sign function. Practically, a common approach to handle such zero inputs to sign quantizer is to assign #1 randomly with equal probabilities. In our framework, this behavior emerges naturally from the symmetry of the Gaussian matrix G. Substituting the required into the hyperdimension bound, we find that achieving an e-discrepancy necessitates hyperdimension of N = O(n log" n2/(=2(2 which is larger compared to that required for a RASU layer. The increased scale of log" n/ 22 reflects the cost of constructing an embedded layer that, unlike the integer- valued outputs of RASU layers, produces binary codes at the layer's 's output.

---

4.1 Network Consistency
The preceding layer-wise result motivates us to analyze the overall discrepancy of the EHD G-Net as a cascade of multiple layers. For conventional feed-forward architectures, tracking the error accumulation across the network layers straightforward (e.g., see [1, 2D). In G-Net, however, the normalization operation complicates this tracking, requiring more careful analysis. To streamline the discussions, while still covering the key technical steps, we focus on the base ASU G-Net case. Specifically, we consider a cascade of L sequential layers, where
Ve = ASU We Dt-1 116-11122
Ue = Id (sign (W&Ge) sign (Giūe-1)), t= 1= L. (6)
Here We E R are the G-Net weights with normalized rows, and Ge E RNxxx--- are independent Gaussian matrices used for the embedding of each layer. Since G-Net layers operate on normalized inputs, we define de- (-th layer. Clearly, since both networks are fed with identical inputs, 6n 0.
Mi IBlll to quantify the accumulated discrepancy up to the
Bella
While normalizing the layer inputs is a common practice improve the training and generalization of neural networks [30], to avoid edge cases, the cascade analysis demands some assumptions about the degree of nonlinear distortion each layer introduces, as will be detailed below.
Definition 4.1. A given matrix W RRxx with normalized rows called consistent with near isometry of ASU in set 'D C B2 for all x, E DD
| - | (W x) ASU(Wy))l S 1| vir-yll2+2 +
(7)
where B > O and & E [0, 1) are constants independent of x and (possibly dependent on and p)-
When the layers of an ASU G-Net maintain the property in (7), we can show that the network discrepancy scales linearly with the number of layers:
Theorem 4.3. Consider the cascade of L G-Net layers and the corresponding hyperdimensional embedding as (6). Assume that each layer of the network is consistent with near isometry of ASU in gae-1-1 with parameters Br and Et, as stated in (7). Then with probability exceeding - L exp( c)):
{
L.
(c+logge)
1161
d' Σ
VN
NeBe (1- EE) +
EE V 1+
where 52
and d' is absolute constant.
18
T
natural question is: what conditions on the set D or on the matrix W are sufficient to ensure that (7) holds? One simple scenario occurs when DD has sufficiently small radius, so that (7) follows directly from the continuity of ASU (the case with more restricted datasets). Beyond this rather trivial case, broadly speaking, one can show that when W is picked to be tall generic matrix with normalized rows, (7) is likely to hold within the entire unit ball By. To state this rigorously, let's consider W E g of the form
91 sill
W
(8)
/ /
where 9: ~ ~N, 1p) are independent standard normal vectors.
Theorem 4.4. Consider W E R following the construction format in (8), where n 2 2 27. Let 9i ~ (0, Ip) be independent standard normal vectors. Then, for all x. y E By, with probability
exceeding cexp(-d'p) || v112 <hopp S B [\ASD(wx) - WSS(Wy)l W < | - 2112 + Sh where
2pp
Vp
Cu (
vp
n + p2
B3- 4 (Vπ+ vD)²
S_.p = Vn /D"
+
Vn+ vp p pV vD)
and d' Ct and Cu are absolute numerical constants.
Observe that by choosing n to be a sufficiently large multiple of p. eh.p and &h.p in Theorem 4.4 can be made desirably small. The proof of the theorem precludes the use of concentration results for
7

---

Lipschitz functions, due to the infinitely steep slope of the aresin function around =1. A technical contribution and key part of the proof is bounding a fourth-order induced norm of W (which does not offer independence along the columns). Clearly, We are determined by the G-Net training algorithm, however, by covering large class of matrices, Theorem 4.4 showcases that when the trained weight matrices are tall and "spread-out", there is good chance that (7) holds. It is also noteworthy that wide neural networks experience only minor changes in their weight distributions during training [15] (see Section M of Appendix for more details). This provides distribution of the trained models. Empirically, in all the experiments performed in this paper, we randomly initialized the G-Net weights according (8), and never observed instance of poor consistency between a G-Net and its corresponding hyperdimensional embedding.
opportunity to control the weight
5 Rademacher Embedding
One promising approach to enhance the efficiency of the proposed framework for hardware imple- mentation is to utilize random vectors that are simpler to generate and apply than Gaussian vectors. In this section, we demonstrate that even the most basic choice of Rademacher vector can be employed as the embedding matrix, provided that the G-Net weights are sufficiently "spread out" (a condition that often holds in practice). The following result extends Grothendieck's 's lemma to Rademacher vectors.
Theorem 5.1 (Approximate Grothendieck identity). Suppose that u, 3P-1 are unit vectors. Let be a Rademacher random vector in RP. Then,
v (u, oiYu
[sign (z (Tu) sign (x [J]]] arcsin(u TTT) u) S cg u. - (u, b)uu12)
π
where 264 is an absolute constant, and and wt in SP-1, g(w,, w²) Ei-r + w/233/22.
Corollary 5.1. Consider unit vectors u. U E 8P-1 such that ||u|lso = 0wx )/2,, ||1|| = 0p and there exists some constant > 0 such that ((u, r\ 1 c. Then
E sign (tT)) sign (z [o)] aresin(u (0(p-112) -
2 π
Informally speaking, Corollary 5.1 says that Grothendieck's identity approximately holds for Rademacher vectors when the inner product factors are dispersed. The layer consistency results of Section 4 can be readily extended to this substantially simpler encoding scheme.
Proposition 5.1. Consider a similar RASU (or ASU) layer as Theorem 4.1, where for fixed constants
C, > O, ||]||cc I Cp 1/2 ||ws]]lo S Cp-1122 embedded output as ÿ ReLU (sign(W sign(xx)) (or ū = Ia (sign(WWR sign(Rx))) where R E R.Nx is a Rudemacher matrix. Then, with high probability: |l ull2 S
1/2 and |w! x² S 11-5for all E ([......)) n... Define the
O(VN-1 log + vn/p).
Proposition 5.2. Consider a similar TASU layer as Theorem 4.2, where additionally for fixed constants C, 0. ||=||0o S Cp-1p/1/ 1/2), [|wileo S CCp 1/2 and < lmiu S |w! x| S 1 5 for Cp211/2
all (1.....m). n.. Define the embedded layer output as ÿ sign (ign(sigmm (sign( WRR sign((x))) where R E NXP is a Rademacher matrix. Assume Cp-1/2 S Emmn/ Fix S vi and set O(E+xvnTD))
- log -y with high probability.
AVT, Then, picking N O(ax² log n/E²) guarantees that ||l -1y 1
In both cases, we observe an additional vn/p discrepancy term which, unlike the Gaussian case, does not vanish by increasing N. However, taking into account the fact that |/llz scales with nn the above results can be interpreted as the relative discrepancy diminishing with increasing N and p. While Gaussian embedding offers the best theoretical results, our numerical experiments show that Rademacher embedding achieves a comparably close performance.
6 Numerical Experiments and Concluding Discussion
Among various applications of the proposed framework, a key contribution lies in enhancing the accuracy of predictive HDC models. Practical implementation details of G-Nets beyond standard
8

---

fully connected layers (such as convolutional, pooling, classification, etc) are provided in Section N of the Appendix. Also, a detailed and extended version of the numerical experiments presented in this section, along with additional accuracy and robustness analysis across other datasets, is included in Section O. Here, we selectively present classification results on MNIST, CIFAR-10 10, and human activity recognition (HAR-WSS [29]).
The experiments involve fitting a G-Net the original training data, followed by evaluation in the binary hyperspace by applying the corresponding EHD G-Net to the random sign embedding of test data. Owing to the G-Net's normalization property, all experiments required most three convolutional and two fully connected layers, enabling fast and efficient training in the primal space, while still achieving strong baseline accuracies for the G-Net. Panels (a-c) of Figure 3 report the average test accuracies of EHD G-Net and other HDC methods. The reported hyperdimension N represents the average N₂ across G-Net layers and the dimension used other methods. For each N, the conversion of the reference G-Net to an EHD G-Net was repeated multiple times with different random matrices; the same number of repetitions was applied to other HDC techniques. The plots show the resulting mean accuracies along with =1 standard deviation.
No. Buxiue OulaeDD
BET-EDC
90
G Nee Then The Orlletli
30
SoNNe Beelin - Dolteel
BEID G-Xs
RFF-HDC
XII Ne.
REF BDC
Clork 10C
Lepter 110
LaD
dopertiammee (N)
Sypendaszkk (N)
Hspertiaumnee 1V
RASU G Noe Dueiee
TESSU C-Nr: Buddiz
-4-TASU Haiinnitee
RASI C-Net Busdier
AU Teedecaace
TASU Gezaana
TASU--Radeaad
6.5
0.4
0/
0.6
1.2
70 0.2
0.4
D4
28
1.0 1.4
X100
(e)
Figure 3: (a-c) Comparison of Rademacher RASU G-Net with other HDC methods (classic HDC [8]. HoloGN [23], Laplace HDC [26], OnlineHD [10] and RFF-HDC(37D) on MNIST, CIFAR-10, 10, and WSS (left to right); (d,e) performance of different G-Nets MNIST (left) and WSS (right)
The G-Net architecture used in panels (a-c) RASU network. Although Gaussian embedding yields slightly better results, we report EHD G-Net accuracies with Rademacher embedding due to its hardware efficiency. One observes that without training a large binary model, and by training only compact network in the primal space followed by inexpensive binary encoding, we achieve classifiers that outperform state-of-the-at art HDC models by significant margin. For example, HDC accuracies exceed 99% on MNIST and 81% % on CIFAR-10 10, rivaling real-valued convolutional neural networks. Accuracy can be even further improved by employing larger G-Nets and higher hyperdimensions, as EHD G-Net performance asymptotically approaches that of the original G-Net with increasing N, as evidenced in the plots. Panels (d.e) present G-Net and EHD G-Net accuracies for both RASU and TASU networks, as well as for Gaussian and Rademacher embeddings. While RASU networks tend to yield higher accuracies, TASU remains competitive, for instance, achieving 98.4% on MNIST. As theory suggests, TASU-based EHD G-Nett converge more slowly to their G-Net baselines. These plots also reinforce the earlier statement regarding the close performance of Gaussian and Rademacher embeddings. Additional experiments and discussion provided in Section O of the Appendix.

---

Relevance to Other Binary Neural Network Designs The proposed framework is rooted in hyperdimensionall computing: it constructs binary, nigh-dimensional models without heavy training pipelines. Leveraging random matrix theory, we derive sample-complexity and concentration guar- antees for the resulting embeddings. This contrasts with conventional BNN training, which poses challenging discrete optimization problem and is therefore commonly addressed with heuristics that offer limited theoretical guarantees. G-Net sidesteps this difficulty by learning a continuous, low-dimensional generator whose sign embedding yields the binary model. Furthermore, thanks to the randomized nature of the process, a single trained G-Net can instantiate combinatorially many EHD G-Nets, providing architectural diversity that can be exploited for privacy and security on edge devices. In the extended experiments (Appendix, Section O), we also observe that BNNs initialized via an EHD G-Net attain peak accuracy within few epochs, whereas BNNs trained from scratch typically require substantially many more epochs.
Computational Cost of EHD G-Net versus Floating Point G-Net At the hardware level, any floating-pont network can be viewed as a "binary" system by interpreting each weight as a bit sequence manipulated by loating-poin operators. Unlike the EHD G-Net, however, these bit sequences contain significance structure, and the induced operations are substantially more complex. In Appendix Section P. we provide mathematical comparison of computational cost, both time and memory, between EHD G-Net and its floating-pont G-Net counterpart. We show that the binary encoding not only reduces computational complexity via simpler representation, but also confers markedly higher robustness. More specifically, EHD G-Nets are significantly more resilient to bit flips than the corresponding floaing-poiil models where weights are viewed as bit sequences.
In conclusion, this paper introduces a new class of randomized binary neural networks formed by inexpensive sampling from meta-distribution with controllable mean and variance. As primary application, the proposed framework demonstrates that hyperdimensional computing can serve a practical and competitive computational paradigm, achieving performance comparable to conventional deep learning methods, if multi-layer encoding or inference pipelines are considered. Additionally, the paper advances the theoretical foundations of HDC by establishing connections between hyperdimension size and model performance. Moreover, this paper opens several promising directions for future research. One avenue involves fine-tuning and compressing the theoretically grounded models introduced here, including the possibility of directly training EHD G-Nets through easy optimization techniques. Another direction expanding the theoretical understanding of the Rademacher based embeddings of the hypersphere to the hypercube we introduced. Additionally, exploring the robustness of the proposed randomized binary neural networks, especially under adversarial conditions, remains a compelling avenue.
In terms of limitations, the proposed framework is primarily motivated by HDC applications where high-dimensional models are typical. Accordingly, EHD G-Nets (derived without training in the binary space) are also high-dimensional, which could be seen as limitation in certain use cases. Moreover, the network analysis in Section 4.1 focuses on the base ASU activations to streamline the theoretical development. While the cascade analysis of TASU and RASU layers involves many similar steps, a comprehensive treatment requires additional analysis, which is deferred to a more extended presentation.
References
[1] Alireza Aghasi, Afshin Abdi, Nam Nguyen, and Justin Romberg. Net-trim: Convex pruning of deep neural networks with performance guarantee. Advances in neural information processing systems, 30, 2017.
[2] Alireza Aghasi, Afshin Abdi, and Justin Romberg. Fast convex pruning of deep neural networks. SIAM Journal on Mathematics of Data Science, 2(1): 2020.
[3] Toygun Basaklar, Yigit Tuncel, Shruti Y. Narayana, Suat Gumussoy, and Umit Y. Ogras. Hypervector design for efficient hyperdimensional computing on edge devices. In tinyML 2021 Research Symposium, 2021.
[4] Hanning Chen, Mariam Issa, Yang Ni, and Mohsen Imani. Darl: Distributed reconfigurable accelerator for hyperdimensional reinforcement learning. In 2022 IEEF/ACM International Conference On Computer Aided Design (ICCAD), pages 1-9. ACM, 2022.
10

---

[5] Yu-Chuan Chuang. Cheng Yang Chang, and An- Yeu Andy Wu. Dynamic hyperdimensional computing for improving uccuracy-energ efficiency trade-offs. In 2020 IEEE Workshop on Signal Processing Systems (SiPS), pages 1-5. IEEE, 2020.
[6] Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran EI- Yaniv, and Yoshua Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 or -1. arXiv e-print 0rXiv.160..02830, 2016.
[7] Shijin Duan, Yejia Liu, Shaolei Ren, and Xiaolin Xu. Lehde: learning-basee based hyperdimensional computing classifier. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pages 1111-1116. ACM, 2022.
[8] Lulu Ge and Keshab K Parhi. Classification using hyperdimensional computing: A review. IEEE Circuits and Systems Magazine, 20(2):30-47, 2020.
[9] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. survey of quantization methods for efficient neural network inference. Low-power computer vision, pages 291-326 Chapman and Hall/CRC, 2022.
[10] Alejandro Hernández-Cano, Namiko Matsumoto, Eric Ping, and Mohsen Imani. OnlineHD: Robust, efficient, and tangle-pas online learning using hyperdimensional system. 2021 Design, Automation, and Test in Europe Conference Exhibition (DATE), pages 56-61. IEEE, 2021.
[11] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-yan and Yoshua Bengio. Quan- tized neural networks: Training neural networks with low precision weights and activations. journal of machine learning research, 18(187):1-30, 2018.
[12] Mohsen Imani, Justin Morris, Samuel Bosch, Helen Shu, Giovanni De Micheli, and Tajana Rosing. Adapthd: Adaptive efficient training for brain-inspired hyperdimensional computing. In 2019 IEEE Biomedical Circuits and Systems Conference (BioCAS), pages 1-4. JEEE, 2019.
[13] Mohsen Imani, Justin Morris, John Messerly, Helen Shu, Yaobang Deng, and Tajana Rosing. BRIC: Locality-bast based encoding for energy energy-efficient brain-inspired hyperdimensional computing. In Proceedings of the 56th Annual Design Automation Conference 2019, pages 1-6, 2019.
[14] Mohsen Imani, Sahand Salamat, Behnam Khaleghi, Mohammad Samragh, Farinaz Koushan- far, and Tajana Rosing. Sparsehd: Aggorithmhhardwan co co-optimization for efficient high- dimensional computing. In 2019 IEEE 27th Annual International Symposium on Field- Programmable Custom Computing Machines (FCCM), pages 190-198. IEEE, 2019.
[15) Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemne:: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[16) Geethan Karunaratne, Manuel Le Gallo, Giovanni Cherubini, Luca Benini, Abbas Rahimi, and Abu Sebastian. In-memory hyperdimensional computing. Nature Electronics, 36):377733 2020.
[17) Geethan Karunaratne, Abbas Rahimi, Manuel Le Gallo, Giovanni Cherubini, and Abu Sebastian. Real-time language recognition using hyperdimensional computing on phase-change memory array. In 202/ IEEE 3rd International Conference on Artificial Intelligence Circuits and Systems (AICAS), pages 1-1, 2021.
[18] Behnam Khaleghi, Hanyang Xu, Justin Morris, and Tajana Šimunié Rosing. tiny-HD: Ultra- efficient hyperdimensional computing engine for IoT applications. In 2021 Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 413. 2021.
[19] Denis Kleyko, Dmitri Rachkovskij, Evgeny Osipov, and Abbas Rahimi. A survey on hyperdi- mensional computing aka vector symbolic architectures, part ii: Applications, cognitive models, and challenges. ACM Computing Surveys, 55-9):1-52, 2023.

---

[20] Denis Kleyko, Dmitri A Rachkovskij, Evgeny Osipov, and Abbas Rahimi. A survey on hyperdi- mensional computing aka vector symbolic architectures, part i: Models and data transformations. ACM Computing Surveys, 55(6):1-40, 2022.
[21]
Zechun Liu, Baoyuan Wu, Wenhan Luo, Xin Yang, Wei Liu, K Kwang- Ting Cheng, Martial Hebert, Cristian Sminchisescu, Yair Weiss, and Vittorio Ferrari. Bi-real net: Enhancing the performance of 1-bit cmns with improved representational capability and advanced training algorithm. In Computer Vision ECCV 2018, volume 11119 of Lecture Notes in Computer Science, pages 747-763. Springer International Publishing AG, Switzerland, 2018.
[22] Chunjie Luo, Jianfeng Zhan, Xiaohe Xue, Lei Wang, Rui Ren, and Qiang Yang. Cosine normalization: Using cosine similarity instead of dot product neural networks. In Artificial Neural Networks and Machine Learning-ICan -CAANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pages 382-391. Springer, 2018
[23] Alec Xavier Manabat, Celine Rose Marcelo, Alfonso Louis Quinquito, and Anastacia Alvarez. Performance analysis of hyperdimensional computing for character recognition. In 2019 International Symposium on Multimedia and Communication Technology (ISMAC), pages 1-5, 2019.
[24] Justin Morris, Mohsen Imani, Samuel Bosch, Anthony Thomas, Helen Shu, and Tajana Rosing, Comphd: Efficient hyperdimensional computing using model compression. In 2019 IEEE/ACM International Symposium on Low Power Electronics and Design (ISLPED), pages 1-6. IEEE, 2019.
[25] Yang Ni, Mariam Issa, Danny Abraham, Mahdi Imani, Xunzhao Yin, and Mohsen Imani. Hdpg: hyperdimensional policy-basse reinforcement learning for continuous control. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pages 1411-146. ACM, 2022.
[26] Saeid Pourmand, Wyatt D. Whiting, Alireza Aghasi, and Nicholas F. Marshall. Laplace-hde Understanding the geometry binary hyperdimensional computing. The Journal of artificial intelligence research, 82: 02:1293-1323, 2025.
[27] DA Rachkovskij. Formation of similarity-reflectnng binary vectors with random binary projec- tions. Cybernetics and Systems Analysis, 51:313-323, 2015.
[28) Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, Ali Farhadi, Nicu Sebe, Jiri Matas, Max Welling, and Bastian Leibe. Xnor-net: Imagenet classification using binary convolutional neural networks. In Computer Vision ECCV 2016, volume 9908 of Lecture Notes in Computer Science, pages 525-542. Springer International Publishing AG, Switzerland, 2016.
[29] Jorge Reyes-Ortiz, Davide Anguita, Alessandro Ghio, Luca Oneto, and Xavier Parra. Human Activity Recognition Using Smartphones. UCI Machine Learning Repository, 2013. DOI: hutp://doi.org/ 10,2443//C5444K
[30] Tim Salimans and Durk P Kingma. Weight normalization: A simple reparametetizzttoon to accelerate training of deep neural networks. Advances in neural information processing systems, 29, 2016.
[31] Anthony Thomas, Sanjoy Dasgupta, and Tajana Rosing, A theoretical perspective on hyper- dimensional computing. Journal of Artificial Intelligence Research, 72:215-244 October 2021.
[32] Pere Vergés, Mike Heddes, Igor Nunes, Denis Kleyko, Tony Givargis, and Alexandru Nicolau. Classification using hyperdimensional computing: A review with comparative analysis. Artificial Intelligence Review, 58(6):173, 2025.
[33] Pere Vergés, Mike Heddes, Igor Nunes, Denis Kleyko, Tony Givargis, and Alexandru Nicolau. Classification using hyperdinensional computing: review with comparative analysis. The Artificial intelligence review, 1836) 2025.
[34] Roman Vershynin. High-dimensional probability: An introduction with applications data science, volume 47, Cambridge university press, 2018
12

---

[35] Junyao Wang, Sitao Huang, and Mohsen Imani. Disthd: A learner-aware dynamic encoding method for hyperdimensionall classification. 2023 60th ACM/IEEE Design Automation Conference (DAC), pages 1-6. IEEE, 2023.
[36] Skyler Wu, Fred Lu, Edward Raff, and James Holt. Exploring the sharpened cosine similarity. In Can't tt Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification, 2022.
[37] Tao Yu, Yichi Zhang, Zhiru Zhang, and Christopher M De Sa. Understanding hyperdimensional computing for parallel single-pass learning. Advances in Neural Information Processing Systems, 2022.
[38] Yichi Zhang, Junhao Pan, Xinheng Liu, Hongzheng Chen, Deming Chen, and Zhiru Zhang. Fracbnn: Accurate and fpga-efficient binary neural networks with fractional activations. In The 2021 ACM/SIGDA International Symposium on Field- Programmable Gate Arrays, pages 171-182, 2021.
[39] Zhuowen Zou, Yeseong Kim, Farhad Imani, Haleh Alimohamadi, Rosario Cammarota, and Mohsen Imani. Scalable edge-based hyperdimensional learning system with brain-like neural adaptation. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-15. ACM, 2021.
13

---

Appendix
Contents
A An Overview of Hyperdimensional Computing
15
A.1 Hypervector Arithmetic
15
A.2 Encoding Methods
15
A.3 Inference Methods
16
An Overview of Binary Neural Networks
17
C Proof of Proposition 2.1
17
Proof of Lemma 3.1 (Grothendieck Identity)
18
Proof of Theorem 4.1
19
E.1 Example
20
E.2 Proof of Theorem E.2
21
F Proof of Theorem 4.2
23
Proof of Theorem 4.3
24
G.1 Auxiliary Lemmas
25
G.2 Proof of the Main Theorem
26
Proof of Theorem
27
H.1 Proof of Lemma H.1
31
H.2 Proof of Lemma H.2
................................
32
H.2.1 Auxiliary Lemmas Needed to Prove Lemma H.2
................................
32
H.2.2 Main Proof of Lemma H.2
35
I Proof of Theorem 5.1
36
J Proof of Corollary 5.1
38
K Proof of Proposition 5.1
39
Proof of Proposition 5.2
40
M Minor Distribution Shift of Wide Neural Networks
41
G-Net Implementation Details
Extended Numerical Experiments
44
Computational Cost of EHD G-Net versus a Floating Point G-Net
48
14

---

A An Overview of Hyperdimensional Computing
Hyperdimensional computing (HDC) is machine learning paradigm inspired by the structure and operation of the brain. In HDC systems, data are represented by high-dimensional vectors, called hypervectors, typically on the order hundreds or thousands of dimensions. Vector entries may be taken from any number of sets; various models have used real-valued entries [62], complex entries [63], and binary entries [26]. [48]. the latter of these cases, hyperdimensional computing schemes benefit from greatly simplified arithmetic,, in contrast to traditional neural networks with float-valued arithmetic. HDC computations are also highly parallclizable and tolerant to stochastic computation environments [37], [69, 60].
HDC scheme principally comprised of two stages: embedding and inference. Consequently, the differences in HDC schemes primarily stem from the differences in their respective embedding and inference methods. the embedding stage, input data some input space X' is embedded into a high-dimensional vector space (hyperspace) Y hypervector through an embedding map 6: X + V/ Regardless of the embedding method, the mapping to Y should ensure that similar input data are represented by similar hypervectors.
For classification tasks with output labels, the inference stage involves constructing set of class representatives de ) for each class E {1..... k.. Predicting the class of an input x then reduces comparing its embedding y with all class representatives and selecting the label corresponding to the representation most similar to It is worth noting that our proposed framework can be interpreted
within the HDC framework, where in the EHD G-Net architecture of Figure 2(b), the first L. layers function as multi-stage embedding pipeline, and the final classification layer operates as the inference module.
A.1 Hypervector Arithmetic
In classic HDC, with information embedded as hypervectors, one may use operations on these hypervectors to form composite hypervectors, and measure similarity of hypervectors with a similarity metric. The vector arithmetic operations often used are superposition, binding, and permutation as detailed below.
Superposition.
The superposition operation +: y x ) + y combines hypervectors in a way that the similarity the original operands is preserved [33]. most cases, the superposition operation is taken as typical deement-wise vector addition, motivating the choice of notation.
Binding. The binding operation y - y associates two hypervectors into new hypervector, which is dissimilar from both its operands. This operation is often used to combine component hypervectors into composite hypervectors, retaining some information of each its factors. In the special case of binary-valued hypervectors when binding is taken to be elementwise multiplication, the resulting vector arithmetic is particularly amenable to hardware-level implementation [26).
Permutation. The permutation operation, as the name suggests, permutes the entries of a hypervector. Denoting by II permutation matrix, the product Ily permutes the entries of according to II.
Similarity. similarity measure a function 5: y x y - The measure typically used to determine to which class a hypervector belongs, e.g. by selecting
class(y) = arg ( 8(y, vhe)
linear classifier is obtained by selecting 5(y. v/) = y TTy. Naturally, the choice of embedding method and similarity measure should be amenable in the sense that, 8(0(2), o(x')) correlates with the similarity of x and x' in
A.2 Encoding Methods
We now briefly review several representative encoding techniques, nearly all of which incorporate some form randomness.
Record-Based Encoding. or can be closely approximated by discrete levels. This encoding method employs two types of hypervectors, representing the feature positions and their level values, respectively. The encoding
This encoding framework applies when the feature values are discrete
15

---

involves the binding and bundling of random hypervectors associated with the feature positions and level values [51]. In this framework, the position hypervectors are independent and uncorrelated, while the level hypervectors are correlated for neighboring levels. This way correlated vectors in X' remain correlated in y.
(Gram-Basel Encoding. This method also applies to feature vectors with discrete levels. First level hypervectors are randomly generated. Then the encoding happens by binding level hypervectors that are rotationally permuted according to their feature position [8].
Fractional Power Encoding. This method enables the representation of continuous numerical values using complex- valued hypervectors. It begins by sampling a random basis hypervector with complex values (each component corresponds to random phasor). A value is encoded by applying fractional self-binding of the basis hypervector æ number of times. The similarity kernel of the resulting encoding depends on the distribution generating the basis hypervector [54, 47].
Random Projection Encoding. This is also a general encoding scheme which incorporates random projections as the core operation [27]. For hyperspace y of dimension N and input space X' C RP this encoding is performed by <(x) = o (Gr), where G RR-xxp has i.i.d. standard normal entries, and a is quantization operation such as a sign function. A bias b E y may optionally be added to the argument o, as in the method described in [66].
Random Fourier Feature Encoding This method proposed in [37] begins by prescribing desired symmetric similarity matrix M E R among level hypervectors. Then, binary hypervectors are generated by computing the singular value decomposition (SVD) of sin( 2 M) to obtain left singular values U and diagonal matrix S+. which is identical to the typical S with its negative entries set to O, and X E R D has i.i.d. standard normal entries. The Haplace-HDCC model by Pourmand et al. [26] extends this work and shows that choosing M to be a Laplacian kernel is particularly amenable to this framework.
A.3 Inference Methods
In this section, we will briefly describe several HDC schemes present recent literature. We will discuss both broad classes of architectures, as well as some selected realizations of these architectures. We emphasize the following techniques are not mutually exclusive within any particular HDC model. As the array of methods present in HDC models is quite large, we will discuss relatively small number of selected methods. For more complete survey of HDC methods, see [33].
Centroid Classifiers. Centroid classifiers are the simplest type of HDC classifiers [53]. In these methods, a hypervector is generated for each class by adding the hypervectors of the training data that belong to that class.
Adaptive Training, Adaptive learning techniques able to adapt to changing data, and are suitable for real-time predictions. Essentially, they operate by updating class representatives only when the classifier would incorrectly predict the class of a training datum. The update to the class representative may be done directly proportional to the misclassified hypervector, as in the AdaptHD model [12], or by scaling the misclassified vector by some expression relating to similarity of the misclassified vector with its predicted class, as in OnlineHD [10].
Regenerative Training. Regenerative training techniques attempt to improve the selection of class representatives by passing through the data several times. each pass, a prescribed number of entries of the class representatives carrying the least information (determined by entries with the smallest variance, tracked over the updates) are dropped and re-selected. Notable examples of HDC schemes utilizing this technique are NeuralHD [39] and DistHD [35]. Dimensionality Reduction. number of HDC models reduce the dimensionality of the hyperspace, thereby increasing the time and memory efficiency of computation. With fewer dimensions in which to embed data, HDC models utilizing dimensionality reduction techniques often incorporate adaptive and regenerative techniques. The SparseHD [14] first trains a standard dense centroid classifier, and compares its performance against a sparsified copy of the classifier, with retraining in the case the sparsification reduces the model accuracy by too large margin. CompHD [24] partitions hypervectors into s equally-sized components, then binding each component with another hypervector based on its position, and superimposing each component to yicld compressed model.
16

---

Optimization-Bann Based Methods. Many HDC models involve tunable parameters, and broad class of these methods optimize performance by jointly tuning them. this sense, subset of HDC approaches can be regarded as optimization-based. As an example, LeHDC [7] learns a classifier as neural network, and binarizes its classification matrix to produce a small binary classifier.
We emphasize that these models all share the common two-step classification pipeline of embedding and inference. While classification a prototypical task for HDC, many HDC models perform other machine learning tasks, such as data regression [50], reinforcement learning [4], [25] and multi-task learning [44, 43].
B An Overview of Binary Neural Networks
Binary neural networks (BNNs) are class of neural networks which use binary-valued weights during operation. There a rich existing literature on BNN architecture, for which we provide here non-exhaustive review. Extant methods for developing binary neural networks can be broadly divided into several types. no particular order, first are those that convert an existing pre-trained neural net operating with weights of non- -inabaary datatype, often float into an equivalent one operating with binary-valued weights. Second are those which train a without the need for float-valued weights during any step of training or deployment. Additionally, there are several schemes which hybridize these types, using some combination of float- and binary- valued weights during training. For more extensive review of BNN methods and architectures, see [71, 68, 73].
network from scratch
A notable subclass of BNN methods is the related XNOR/XOR-NeIs, a class of methods which approximate the convolution operations in a network with binary-valued weights, in the former by using a combination of XNOR and bitcount, and in the latter with XOR in place of XNOR [28], [74]. In either variety, these networks train flout-valued network and update an approximate binary-valued network which is updated in parallel in every training pass [28]. [57, 74], in contrast with our method of binarizing G-Net into an EHD G-Net, which occurs distinct steps in our pipeline. The
Bi-Real Net framework proposed by Liu et al. [21], connects the float- valued activations to those of consecutive blocks to increase the representational capacity of the network [56, 59]. In this sense, layers in Bi-Real net have a degree of cross- cross-communication which is not present in our model. Another approach at network binarization is the Accurate- Accurate-Binary- -ew--Bannnnooouueeee which converts pre-trained CNN into BNN by determining basis of binary filters which, together with the appropriate weights, yield approximations of the original layer [58]. contrast, our EHD G-Nets need only single binary weight tensor in each layer.
Network (ABC-Net)
C Proof of Proposition 2.1
Proposition 2.1. For standard Gaussian matrix G E Xxn, consider the mapping A(z) sign(Ga) from X = g--1 (equipped with geodesic distance DG) to y {-1,1] (equipped with normalized Hamming distance Dz). Fix s (0, then there exist constants e1 and 02 such that if N 2 cnn/E? with probability exceeding exp( exp(-c2n), A is an e-near-isometry That is
Yx, LeyEs"" S
IDH (sign (Gz), sign (Gv)) Dola, v)l Sc.
Proof. The proof a direct application of the following result from [61] which provides an optimal dependency on the dimensions and
17

---

Lemma C.I (Theorem 2.2 [6]]). Suppose G E R. N xm has independent NO,, 1) entries. For given set K _ ga-1, define the Gaussian width as
((K) (g-AN((.1)
sup 9
ZEK
and denote cone(K) far: : 2 0, v K}. If cocoee K) is subspace, then for fixed
(0,1), there exist constants and 02 such that when N 2 c1 (K) with probability exceeding 1 exp (-c28²N):
Vx, y E ST-1;
[De (sign (Gz), sign (Gu)) Da y) s..
Here angle(z,y) y) denotes the smaller angle between x and y.
Based on Lemma C.I, to use the result we only need compute the Gaussian width of the unit sphere:
E v2I(m/2+1/2)
(S"-1) EggWA(o.))
sup g² gTx L
[(n/2) S vn,
where we used the fact that lg l2 has a chi distribution with n degrees of freedom, and applied Gautschi's inequality.
As an alternative presentation of Lemma C.I, one may be interested in version of (9), which uses the same metric on both the source and encoded spaces. To that end, notice that
Dr (sign (Gx), sign (Gv))
ssggn (Gx) - sign (Gy)
4N
sign (Gx),
sign (Gv)
2
2
VN
VN
1
cos
angle
sign (Gx), sign (Gu)
2
2
=sin2
1
angle
sign
(Gr).
sign (Gu)
VN
VN
π Da
=sin
sign
(Ga),
sign (G:y
2
VN
VN
where angle(u, v) represents the smaller angle between two vectors u and v. Therefore, an alternative presentation of the e-near isometry in (9) is
Yx,y ST-1: sin 2 (m (
( sign (Gx), VN sign (Gv)
Da(x, v) Se,
where a geodesic distance is used for the source vectors x, y and their encodings sign (Gx) and sign (Gv).
D Proof of Lemma 3.1 (Grothendieck Identity)
Lemma 3.1. Let g be standard Gaussian vector in IR. Then, for fixed vectors u, RR:
2 arcsin
Tv
E [sign(g" u) sign(g] T v)]
|
Proof. We show that for fixed vectors u, v E 1:
[sign(g T u) sign(g v]]
arcsin (u v).
π
18

---

Among different ways to show this identity, the geometric argument is the most straightforward. By the rotational invariance the Gaussian distribution, can restrict our attention the two- dimensional subspace spanned by u and Consider the set S {= u v O and v 2 0). If the angle between and v, then the angle between the two lines that define the boundary of S, which are perpendicular to and e, respectively, is also a, see Figure 4.
S
a
a
Figure 4: The set S f= : u 0 and v== 1=20 0}
By similar reasoning, the set {z:uTz 2 and v. S 00] is a radial set of angle a. Thus, sign(uT>) 2) = sign(uT>) 2) outside of radial sets of combined angle 2a. Thanks to the rotation invariance of the Gaussian vectors:
2x 2a
arcsin(u m)
P {isinn""" g) sign(v) g)}
+
2x
where we used the fact that a arccos (u u) x 2
- arcsin(u u). Finally,
[g uu) sign(g T v)] P {sign(u (u g) sign(v' {)} P {sign(w 99) + sign(v' [g)
= 2IP {sign(u u T g) = sign(v [)} -
aresin (u TT)) v).
n
E Proof of Theorem 4.1
Theorem 4.1. Consider a RASU (or ASU) layer with input x Gr-1 and weight matrix W E Raxp whose rows are Ey-normalized. Let the layer output be given by y = RASU(Wx) (or = ASU(Wx)), Define the embedded output as ū = ReLU ReLU (sign(WG sign Gx)) (or ÿ- Id (sign(WGT)) sign(Gz))) where G I Nxp is a standard Gaussian matrix. Then, for any > O, with probability at least exp(-xp -c),
2 + log 2n)n
7 y
S
N
Proof. We present the following general result, applicable to both RASU and TASU layers, with its proof provided at the end of this section.
19

---

Theorem E.2. Consider a random matrix X' E RExN with entries aij, such that S
Fij S b almost surely. Define vector E IR" with entries =[(N-
> Ej= Tig)
f(B[N- ΣØ= ris),, where f is a functioni in (a, b). Then
(a) When X. maintains independence both along the rows and columns (i.e., independent entries), then for all >> with probability exceeding exp(-c):
|lell2 - p(b - V)vn + (-)
1/4 plb - a)ne = (00000-00
n
2
VN
NNN
where d' is positive constant.
(b) When I maintains independence only along the columns, then for all >> 0, with probability exceeding exp(-c):
||ell2 S /
(c log 2n) 2n)npp2 a)² =0
(0lb -a n log n
2N
We now proceed by applying this result to a RASU/ASU layer. Recall that y RW)), and = ReLU (sign(WG) )sign(Gx)) (F))
The discrepancy between the two layers can be written as || v|l² = Ei= ei2 where
1
ReLU
Σ sign (g) w;) sign (g) Tx)
(² ReLU
arcsin (w: at)
N
= ReLU
sign (0) w.) sign (g,Tx)
ReLU
E
1 N
sign (o) w:) sign (g) (g,Ta)) x))
N
This is clearly an instance of Theorem E.2 part (b), with ReLU as the Lipschitz function and the quantities sign (g) w;) sign (g, Tx) as Tij. Since the Lipschitz constant for ReLU and the identity function corresponding to an ASU layer are both 1, and S sign (9) w:) sign (g) ()) S this
immediately implies that with probability exceeding exp(
2(c + log 2n)n
log N
N 1
y
N
2
the construction were modified such that the elements of e became independent, Theorem E.2(a) implies that the discrepancy could be reduced to O O(vn/N). However, achieving such independence would require employing separate embedding matrix for each row of W, which increases the memory and computational overhead. The following example suggests that the maximum possible reduction achievable through promoting independence is limited to factor of log
E.1 Example
Suppose that f(x) pr, and let Jij be i.i.d. random variables for j I,..., N such that
P|æı = +a] = IP( = -aj = 1/2. Assume that 4új x15 for = 2,... and j = N.
Applying the upper bound on ||e||a from Theorem E.2 part (b) to this example gives
n log
||l|| O pa
N
with high probability. For comparison, observe that
N
E |ell2 =
PVn
Σ
Ø1j
4
pa
11
N
N
i=1
20

---

as NN + oo. Hence, the upper bound is only a factor of O (vlogg n greater than the expected value, least some cases.
E.2
Proof of Theorem E.2
Proof of part (a). We start the proof by using Hoeffding's s inequality stated below:
Lemma E.1 (Hoeffding's Inequality). Let Xi..... XN be independent random variables such that az S X, S by almost surely. Then for all t 0:
N
21
P
Σ
X
Σ
Xi j=l
21
1
S 2 exp
Applying this inequality to Us = N-1 EØ= Tiy reveals that for all & > 0:
P P(T:: P(m=-Blui - E(yn)) 2 21} S exp (-(o- a)2
2NL
A direct consequence of the Lipschitz continuity of is that if (f(()))((22) then (21 - 22) 2 t/p², which implies
P fe 2 = ((((((())))) (B())) 2 t) s PP - -E(p)) 2 p2)
$ 2 2exp (- a)2
2Nt
This implies that oî is sub-exponential random variable with sub-exponential norm
| pl = o - ( N)²
This also indicates that ||ا E Eeeill w. S (b a- (see $2.7 of [34]). Next, we will use Bernstein's 's inequality for the sum of sub-exponential random variables.
Lemma E.2 (Bemstten'' Inequality). Let .I...., be independent zero-mean sub- exponential random variables. Then all 2
P Σ
ExzIee
S exp
(-mmin
t2
Σ 1x
maxisisN Ixxilles
where ē is a positive constant.
Applying Lemma E.2 to the sub-exponential random variables e? B[e?] gives
26 2
1 B
exp (-ôn min cb
(b a)4* cp -)p))
N212
N
)) (10)
==1
Setting Co e/c². when is sufficiently large, picking
(bb-a)) VnN
in (10) guarantees that for all > O, with probability exceeding exp(-c):
p2 a)² Vm
|ell
<
|e
N
1=1
or equivalently
1/4
p(b - 1/4
|ell2 <
Σ
[ef] +
c
(11)
VN
1=1
21

---

We now proceed by bounding E|e follows:
27
N
Σ
Efe
Σ
f
Σ
zij
Σ
Blras]]
N
N
j=l
1=1
27
1
p²
E
Fij
Σ
E
E(r
N
N
i=1
0²
var
[r
N2
i=1j=1
116-a) an
(12)
4N
where the first inequality is thanks to the Lipschitz continuity of f, and the second inequality is direct result of the Popoviciu's 's inequality which states that for a random variable .r, bounded between a and b, var[æ] I (b a)2/4. Combining (12) and (11) proves that with probability exceeding
1 - exp(-c):
||e|l2 V p(b a)vá
(
1/4 p(b a)m
VN = =0 (000000)
2
N-1 Σ}= Tzj. and Proof of part (b). Since I offers independence along the columns, setting y/: N appealing to the Hoeffding's inequality in Lemma E.1 yields
N
2N+
vt > 0: P flu - E|a]l 2 t S exxp
(b a)²
direct implication of the Lipschitz continuity of f that if [2()) f2(2)) 2 then 121-22 2 t/p. which yields
2 (((r(w))
=P
(F(()))) 2
1
< P 1 - -E(y,]
n
Vn
PVn
2N+
$ 2exp
(13)
np² (b - ab)
For arbitrary real-valued random variables Xi.... Xn and scalars t1....,
tnn one has
n
P
X
P
U { 2
t
N P
xx
24),
(14)
im
where the first inequality is valid since
(x Xa)
Σ X Σ
C
Ux::x: xx2 24.
and the second inequality is thanks to the union bound. An application of (14) to (13) yields
2N
P (1]el|22 2 () = [1ell 2 (2)
2n exp
np - a)
2N
exp (oog(n)
np2 (b a)²
which means for all with probability exceeding
exp(-c): (c (o=loo(2n))))ttee a)²
0 0006-- (a(
n log m
|el|a <
2N
N
22

---

Proof of Theorem 4.2
Theorem 4.2. Consider TASU layer with oulput (WS xi), where E S and W E RaxP has normalized rows w (1wwil2 1 for i = ...... n.). Define the embedded layer output as ÿ = sign (sign(WG sign(Gx)). where G E RN a standard Gaussian matrix. Assume
| x: 2 Emin O, ==
Pick target discrepancy vn and set 2 26 log 1ynn Then, for any scalar > 0, selecting N 2 8(c+Hog 2n) /E² guarantees that with probability exceeding 1-3 exp(-c):
ly 2 S e.
Proof. Recall that
TASU,, and ÿ sign (sign(W )sign(G*)) Denoting the discrepancy between the layers y, by triangle inequality we have ||e|| = ||e' + ||="||2,
where
2k Σ sign (g] ws) sign (gj Tx) tanh
c = tanh
aresin (w: x)
N
π
sign (g) wo, sign (g) T2)) ))
tanh
sign (g) wx) sign (g) xx) tanh
N
and
o' = sign
1 N
sign (g) w.)) sign (0,Tx) Tx)
tanh
sign (g) w:) sign (giTx)) Tx))
N
The first term ||e|||2 can be related to Theorem Eb)(b) with f(x) tanh(Ræ) as the Lipschitz function, for which it is easy to verify that p = Therefore, with probability exceeding 1 exp(-c)
|le' = 2(c + log((n))
(15)
N
For the second term, using the fact
(sign(2) (anh(xz) S 2 2cxp(-2xx)
yields
le'1l < 2 exx
-2k
1 N
sign (gz wi) sign (g) Tx]
bounding which requires finding a lower bound for 1/2 Σe= sign (9) wx) sign (x) J. Notice that for general and u, the inequality |u] inequality
|u] >> / implies Iu > l. Therefore, using Hoeffding's
N Σ
2
P
arcsin(ws (w, x)
sign (g, ws) sign (oj Ta) 2t }
N
N
2
Nt3 2
< P
sign (g) w.) sign (0, Tx) arcsin(w, x) 2t 2exp
N
23

---

which implies that with probability exceeding 1 - exp(-c)
N
22c
sign (0) wi) sign (gj xx)
arcsin [1, x)
VN
2
V2c
T
VN
V2c
min
π
VN
This indicates that with probability exceeding - exp(-c))
8k ( Emin
32c
1e S 4 exp
ki
which, after applying union bound analogous to (14), implies that with probability at least 1 2n cxp(-c):
8k liii VVV
32c
1 S 4n exp
N
equivalently, with probability exceeding - 2 exp(-cc):
4x ||e||2 s exx log v - Emi + ki
8(c + log
N
After combining this result with (15) we can claim that with probability exceeding 1 - 3 eex((-c)
|ella S 2(c + log((2)) )
4x Emin + mo
8(c + log n)
+ 2exp log vn
N
N
Setting N 8(c + log 2n mn) a /e² gives
|lel12 s + 2exp
log v - Emin +
4xc
E
(16)
Vn
Notice that
4k min 2 2 2og
4/n
6
c log
2 log vn
Vn 4
where the first inequality is thanks the assumption on x and the second inequality is valid long as n 2 2 Together with (15) and (16), this implies that with probability exceeding 3 exp(-c).
E + 2 exp (log 5) E.
lella s 2
G Proof of Theorem 4.3
Theorem 4.3. Consider the cascade of G-Net layers and the corresponding hyperdimen- sional embedding as (6). Assume that each layer & of the network is consistent with near isometry of ASU in -1 with parameters 3e and Ex. as stated in (7). Then with probability
exceeding 1 L -x)
1161 S Σ (1v
(
1.
Et 1 1 Ez
+
N₂ (1
where d' is an absolute constant.
24

---

G.1 Auxiliary Lemmas
To prove Theorem 4.3, first need to state some auxiliary lemmas, which follow.
Lemma G.1. If (7) holds then then for all x, E D:
3 8- -
3 2
x'y 2 =
(ASU(Wx) ASU(W v)) Sx' x y
(17)
Proof. By the left-hand side of (7) we have
||=l| + ||v|| 2x
< 8 ASU (Wx)ll - 8- ||ASU (W w - 233 (ASU (Wx) ASU (Wy))
$ ||:|| + + |/y/l + 2 (ASU (W x) ASU (Wy)).
where in the second inequality we used 8- and once to y. This implies that
= || twice, once by setting to
8 (ASU (Wz). ASU ())) 1 x y+ 2C
Also by the second side of the inequality have | + ||
2x y + 2 3-1 ||AUU (Wz)ll 8-1 |SSU (W Wy)l 2,- (ASU (Wx). ASU (Wy))
2 ||>||| + |1 E 2,3 (ASU (Wx) x)) ASU (Wy)).
which implies that
3 2
8- (ASU (Wz). ASU (W 2 x
Lemma G.2. Consider two arbitrary non-zero vectors y and R2
If
ull2 S e and
lvll2 2 K > 0, then
y
S
1
1
Proof. A direct implication of the assumptions
(18)
l
1
12
On the other hand
1
llllla
|
ly
||
(19)
l701
l
levlla
ll
l
K
where we used the reverse triangle inequality. Now using the triangle inequality along with (18) and (19) we get
2/
5
y
2s
S
<
1112
1B
17l12
11v/12
12
1
11v/12
2
K
which completes the proof.
Lemma G.3, Consider W E Raxp which is consistent with near isometry of ASU SP-1,
stated in (7). Then for all x, y sp-1;
ASU (Wx)
WW 2
5c
AS (W))l $ <1
v12 +
(20)
[ASU(Wa))
1
25

---

Proof. Expanding the left-hand side of (20) gives
ASU (Wx)
ASU (Wy) y)
ASU (Wx)
ASU (W y) 2
2 (ASU (Wr) ASU (W y))
+
ASU (Wx)])
ASU (W y)
|SSU (xx)
|SSU (W b)ll
ASU (Wx) |SS (W w>1
2 (ASU (Wx) ASU (Wy))
=
B-1/2
ASU (Wx) >>)l2 1 1/2 ASU (Wy)ll2
22 2 x V E0
1
|| v112
(3 13+22* 2x T
1+
5c
$ | vll
1 1+
where the first inequality is thanks to Lemma G.1. This completes the proof.
G.2 Proof of the Main Theorem
Proof.
We are now ready to prove Theorem 4.3. By the triangle inequality we have
RASU
(We Ne-1
RASU
de We
|16ell2 -
Te
Ie 1I1
+
all
V/
(21)
|10el12
RASU
Me-1 (W
RASU
W
8r-1 Be-
1/ ll
[[p--1]
We start bounding ||öe|l2 by first bounding the first term on the right-hand side (21). By the layer consistency know that given Øt-1, with probability exceeding pt (where as shown in Theorem 4.1, Pe = exp(-op for some desired c > 0):
1 N₂ Mr RASU
Wr 1 =0
(c log ne)re
(22)
Ne
By the near isometry consistency of the l-th layer we have
Me-1
){
RASU
W
2 / Be Er).
(23)
Using Lemma G.2, the bounds (22) and (23) imply that given Ii--1, with probability exceeding 1 pe:
We RASU
= =0 =o (
(V
(c+ log n4 ne) mo
(24)
||
RASU
We
NeBr (1 ET)
The second term on the right-hand side of (21) can be bounded using Lemma G.3 as
RASU
WeTTccil1 [i-li _e-1 |12
We Be-1
RASU
We
Ār-1 [
RASU
W We-1 [Tuc-1l]
RASU
1 l2
RASU
We T 0r-1
RASU
We [
Be-ill
Ne
Ml-
2
5e
1|2
11
1 &e
5El
|18,_1 113
+
(25)
1
Using (25) and (24) in (21) we conclude that given J6-1, with probability exceeding - Pe.
(V log ne)me
Et
||bl||2 $ [162-1112 +
t= 1....,, L.
(26)
(1-Et)
11+t2
26

---

where c' is an absolute constant and 60 O. Now consider Ae to be the event that (22) holds. Then we have
IP (AL) 2 P (AL-1)
2 (A
2 ((A) II P
2=2
II Pc).
8=1
By the Weierstrass inequality we know if E [0, 1] for l = I,.... L, then
1.
II [1-
Σ
Pt-
t=1
E=1
Together with (26), this implies that with probability exceeding - L exp(-c):
logne)) Ne3: (1 -x))
Et
|1óz|12
(27)
1
where e' is absolute constant.
H Proof of Theorem 4.4
Theorem 4.4. Consider W E REXP, where 2 27, following the construction format in (8). Let (0, Ip) be independent standard normal vectors. Then, for all x. E By, with probability exceeding
ccxp(-ce
|| - 2112 E'p S B AAS((x)) w))(w)) I 1 - -1112 + =m.p'
where
x2p p
P cu
vp +
n p² p (V + vD)2
BTD
S'. =
E..
(Vn+ vD)
2'
Vn + vp'
vn
vp
and c, c', ai and cu are absolute numerical constants.
Proof. We present the proof as four main steps and for each step provide the related lemmas which are all proved at the end this section.
Step 1. Bounding the ASU Variations: inequality:
Using basic calculus, one could establish the following
1-1 Lemma H.1. Consider f, E ( 1). Then
2 (x 2)² < (ASU(>)) ASU(n))) <
(I
y)
+ 1 1- n²
+ (x + +y²)
(a
72
4
y)
2
Proof. See Section H.
27

---

By Lemma H.1, for each row of W we have
x²2 (w, x y) I (ASU(w) x) ASU(w, ) S x
2 (10) x w/ + 5
6 ((w,T x) + (we vulz)))
Summing along the rows and scaling both sides gives
3n
0 5 (S)) y))l l[ w)l
(102|11+||1000)
(28)
10
Consider 8min (W) and max (W)) to denote the smallest and largest singular values of W. Then for any and y:
min (l)l vll2 = ||w'(z v)| - s (W)l yll..
(29)
On the other hand, using the notion of induced norm, for any BR2 one has
||02211 - ||
(30)
where
22-4 sup |all
|
Using (30) and (29) in (28) we get the following general bound for all a., y E IB3:
6n
min (W)) y112 (S) ASU( S max (W)llz Ell +
| (31)
10
The next step is using high probability bounds for smin (W/), smax (W) and || to express them in terms of the problem dimensions and p.
Step 2. High Probability Bounds for Smin (W) and smax (W)): In this step will focus bounding the singular values of S in (8), where 9r ~ NN Ip) are independent standard normal step the following lemma,
vectors. A central component of the proofs of this step and the which characterizes the moment generating functions rows of W. Since parts (a) and (b) are closely related, they are consolidated
result, while only part (a) is used in this step.
Lemma H.2. Consider x E S where 2 27, and g = [gi.....9h mpl ~ ~N T). Define the random variable
x 0
|1
Then
(a) For all E (0,2/5):
25 Eexp (T'pa?) exp
(b) For all (0g)66)))
137
E Eexp (rpu*) S cxp
Proof. See Section H.2.
As a well-known result, a random variable is sub-Gaussian there exists a constant > such that for all satisfying |r| < k-1, one has Eexp (72)) exp (k272) (e.g., Proposition 2.5.2 of [34]). Defining | g) /llg]l. it is immediate from part (a) Lemma H.2 that ypu is sub-Gaussiaa random variable. Furthermore, since Lemma H.2 considers
$ as any arbitrary unit vector on the sphere, this guarantees that the normalized vector g/ |||||| is generally a sub-Gaussian random vector. Notably, 9/ll follows uniform distribution on the unit sphere, which guaranteed to follow sub-Gaussian distribution (see Theorem 3.4.6 of [34]). However, in analysis, we provide
28

---

more detailed characterization of this property with explicit constants, which are later needed in part (b) of Lemma H.2 and the analysis in step
The sub-Gaussian property of vpu allows using the following uniform result:
Lemma H.3 (Theorem 4.6.1 of (34D. Let be an n. x matrix whose rows of are i..d, zero-mean, sub-gaussie gaussianssn isotropic random vectors in IRP Let || Then for any t 2 0 and all x E SP-1:
Vn- CK² 5 S vn + cx² (vp+
with probability at least 1 eexp (-t?).
Lemma H.3 provides an immediate way of uniformly bounding the singular values of /pW. To that end, notice that for g ~N Ip):
99
1 p
E
119
which be easily verified by symmetry for diagonal elements and negative symmetry for off- diagonal elements. This observation makes the rows of /pW/ isotropic. Moreover, part (a) of Lemma H.2 guarantees that the nab-Gausiia norm of ypu is a constant, i.e., ll //pplll> O(1). Now appealing to Lemma H.3 and setting L = c/P guarantees that with probability exceeding 1 - 2 exp ( (-ep), for all x E 1p-1:
Vn c lVpiexl12 S V d Vv.
equivalently, with probability exceeding 1 - 2 exp (-cp):
vn d VT VP
Vn + c' VD
S smin (1) S mmax
(32)
SStep 3. High Probability Bounds for [|]]2-44 In this section we focus on bounding | 1222 using a covering argument. While the induced norm of random matrices with bounded and indepen- dent values has been studied in the literature [42, 49, 55], to the best of our knowledge, such result available for random matrices like (8) with dependence across the columns. Here using part (b) of Lemma H.2, we will provide concentration bounds ||167||2-.4.
Consider random matrix 1 E R following the construction in (8). For given E SP-1 have
g, x|
Werli
For fixed F within the designated region of Lemma H.2 we have
Eexp (TP((W>)()) & exp 13rn
By the Markov's inequality for non-negative random variable and all > 0: Pfz 2 t) <
Ez /t. Fixing 7 log(2)/6 and applying the Markov's inequality : exp (Tpl (x with t exp(13rnn/ 7/)) guarantees that for any 7 0:
P rpllWx|1
13rn + [D)
1 < 2 13n + log 2 yp²
exp(-11))
(33)
p
We now proceed by applying a union bound the tale bound above using a covering argument. The following standard result (c.g., see Corollary 4.2. of [34]) bounds the size of an s-net on gp-1,
29

---

Lemma H.4. The covering number of the unit sphere Sp {ar E IP: ||a|| = 1} satisfies the following for any ε E (0, 1l:
NSP .6) 8 (-+1)=
(2
where (SP-11,) represents an s-net of S i.e.
VI E S 3z' E N ,)) || - 2'll Se.
We next relate ||W1 version of it computed on (SP ,e) by fixing E (0, and using standard covering argument for the norms. Let x E S be vector such that || || 1-244
By the triangle inequality for any x' E N(SP- .E) we have:
||<''l 414 2 ||10z/1a [| a' 1|4 2 |Wlla-11 || æ'1l2 2 (1 ||
After fixing = 1/2, dividing both sides of this incquality by 1 - and taking a maximum with respect to x'' we get
1 sup
||||2-14 S 1- e (EN(Se-1,e)
||Wa||1 = 2
sup ||
(34)
*EN (8 1/22
Note that by Lemma H.4 the cardinality of the net can be bounded by [N(SP-L 1,12)) 5", which admits applying a union bound as follows:
VP 1 2- 2
13n
6
?p?
1/4
P
VP
sup ||0zll1
13n + log 2 yp
1/4
log 2
#EN
1./2)
13n 6
1/4
Σ
VPllW//l1
yp²
log 2
x N( .1/2)
5" eep(px1)
exp (llog 5 5- 5>))
which implies that for positive constants é and ~' with probability exceeding 1 exp(-('p) we have p² @ 1 I z(n + p²), or equivalently
(n + p²) p²
1
I
(35)
Step 4. Combining the Results of Previous Steps:
Let's define
p
Pn,p (Vi++ vD) 2'
and multiply both sides of (31) by Mnpp to get
Mnn (1)) 2112 s B.. [AASU(())=ASU(/( S Mn.p ( (iiaax (1)) w112 +
6TT
|1001/-111
2-+1
10
(36)
where
n²p
8 m
4 (Vn + vT)
By (32) for all x, y E By and with probability exceeding 2exp (-cp) the left side of (36) can be lower bounded as:
Mmnp (w)l v112 ( Vn cVvP)
| v112 = (1 (c'
(c'+ + 1) || v113
/n vD
vn + vp
2(c' + 1)vF
|| v/1
|| -vli
Vn+ + vp
8(c'+ + 1)vp
2 || y1ß
+n+ v/P (37)
30

---

On the other hand, combination of (35) and (32) guarantees that for all 2, y E IS, with probability the right side of (36) can be upper-bounded as
exceeding 1 - exxx((-2'p
6n 2 un.p
2 1001 S ( (c' (vvP
6ên²
(n p²2
max
(W)] --12
1 -11
10
vn + vp
10
P p(vn + vD)
vp
n + p²
I | - 21l2 + cu
vn - vD
p(vn + vp)
P
(38)
for some positive constant Cu- In the second inequality above we used the fact that | v1 < 4 and
Va+vp (c'-1)) < 1 for sufficiently large n. The outcomes of (37) and (38) combined with (36) validate
the claims made in Theorem 4.4, and the proof is complete.
H.1 Proof of Lemma H.1
Proof. Consider the following functions:
fe(x,g) =2 =2(1= π²
4
4
(x* + t²)
(x y)² +
(arcsin(x) arcsin(y))
x²
and
4
4 n2 (x - y)
fa(z, =
(x* v²a 73
+
(arcsin(1) - arcsin(y))) (aresin())=accsin(u))))
72
To prove the lemma, it suffices show that for (z, v) 1- [-1, fe(r, u) 2 and (x, 3) 2 O. To establish the inequality for fe (z, y), notice that by the Lipschitz continuity of the sin function:
(sin(a) 2 (a= B)3
which by setting arcsin(x) and arcsin(y) and multiplying both sides by 4/n² yields
4
(arcsin(z) arcsin(y))
72 (x y)² 0,
(39)
from which it immediately follows that fe(r, u) 2 O.
To show the inequality fu w) 2 O, we begin by rearranging the terms of fu and bounding them as
fu(x, 2 (1
4
4 (arcsin? (x) aresin (v))
(x² + )²)
2
n
4
+ 2
(arcsin (z) arcsin zy)
π²
4
8 (xt v
8 (arcsin arcsin (v)) (40)
>
(x² + +
72
2
x2
8
(h(x) + h(y)),
= n²
where
Mxx = -(+ -1) + x² (r))
?
In the derivations above, inequality (40) uses the fact
(arcsin(x) arcsin(y))* 2 (x + y)
which is direct implication (39), when one uses and - y as the arguments. Thanks to symmetry in and y. show (2, y) 2 0 it suffices to show that h(x)) 2 0. and since h is an even function,
31

---

we can restrict the domain to E [0, 1].
Notice that since x² 2 n,2 arcsin"(x):
n²²
1(x))
1 + x (rcsin((x)
4
1 4
x² arcsin²(x) x² arcsin
π²
0,
where the second inequality is thanks to the elementary inequality
arcsin(z)
V1- (1 2/2 x²
which is valid for E [0, 1] (e.g., see Theorem of [41]). This completes the proof.
H.2 Proof Lemma H.2
H.2.1 Auxiliary Lemmas Needed to Prove Lemma H.2
To prove the lemma, we first need to state two integral bounds (Lemma H.5 and Lemma H.7) which will be later used in the main proof. Also to bound the moment generating functions, we need tail bound which is stated in Lemma H.8 below. We first present and prove these lemmas, and then combine them to prove Lemma H.2.
Lemma H.5. For all integers 2 27:
dr
6
(1+22)
6
Proof. Consider ls E 1 n E N}. Defining Is as below and doing an integration by parts we get
da
T =
(41)
+ 22)
dd
+ 2k
(1 222
(1 + x2))++1
dr
dr
2k
2k
(1 + x2)R
(1+x* x1+++)
which implies
1
2k -
I
Is.
(42)
k2
2k
now use an inductive argument and show Js k-1/2, then I++1 S (A: + 1) 1/2
To this end,
state the following lemma which is proved the end of this section:
Lemma H.6. For any k { :n n 21, n NN::
3
2k
(43)
k2*+1
10 V
Vk +
2
Using Lemma H.6, assuming I 5 k 1/2 by the recursive equation (42) get
2h
1
k22+I +
2k
2k
1
10 Vk
2k
1
(44)
Vk 11
32

---

proving the inductive step. Notice that we have unit inductive step increments in (42), while the increments are integer multiples of 1/6. Hence, establish the induction base case, it suffices to show that for some no. the integrals / I 7 ngts are dominated by /6/no, (n 1),... v 6m 5), respectively. This can be verified for no More specif- ically, J = 0.7854 1, 17/6 0.7575 < VG/7, .......... ...////////66 0.6628 < 6/11. Together with the common inductive step, this verifies that
vk 6 n 2 21, n MEN]: 1 k
(45)
For given integer p 2 27, setting p/6 and appealing to (45) gives
dr (1+22) which completes the proof. We are only left with providing the proof of Lemma H.6, which is presented in the sequel.
6
6
The first inequality in (43) straightforward as the exponential expression 122+1 dominates the monomial 10 w/2 for sufficiently large k. It can be easily verified that the domination happens after k 2 21/6. To prove the upper-bound, suffices to show that
3
3
2k
k
10k2
2k
k+1
which after squaring both sides and rearranging the terms is equivalent showing that
(k: 1)(3 + 10k 5k)² < k (1043)²
Taking both expressions to one side and expanding the terms reveals that
to (10k²)² (k: + 1)(3 + 10k 54))² 15k 55 + 21k -1 9,
(46)
which is a strictly positive quantity, simply because 15 + 21 consistently dominates 55 + for every integer 2 3. This verifies the upper-bound (43), and the proof of Lemma H.6 is complete.
Lemma H.7. For all integers 27:
22
33/2
(1+
2(p - 6)3/2'
Proof. Let k E { n n N). then
L. dd
L.
(1 + dd
dx (1+
Ik-1 Ik:
21+
(1 11+22)
where Te follows the formulation in (41). By the recursive equation (42) which valid for l E { n 2 21, E N] we have
1
T- I
2k - 2 TR-1
(I: 1)2F
+
(k: - 1)2k
2(k 1)Vk -
1
2(k: - 1)3/2*
where the second inequality uses the fact I < 112 which was proved after equation (42). Setting p/3 (which still keeps i an integer multiple of 1/6) gives
L
2d
33/2
<
(1+89)
2(p 6)3/2
This completes the proof.
33

---

The next lemma provides tail bound for the random vectors of interest in Lemma H.2.
Lemma H.8. Consider E Sp-1 where p 2 3, and 191......pp) ~ ~N(0, 1). For all
A (0,
2 T(P -02) 2)
(1+
P
11ll
A
Proof. Since a E SP-1 and the standard normal distribution rotation invariant, we can set e1 (the first canonical basis) which implies
P
X
|1g
[g
TP
|
IP
X
9 + 92
0
S PP
[9n1
X/ 02 + g3
00
(EP 07 (p -
= P
2 x² 1)
(47)
g
where the inequality is thanks to the fact that
{ E > of 2 ... + 2 C 2 : X 23
+ + +
(E /(p-1) is the ratio of two independent chi-squared random variables each normalized by their degrees of freedom, hence follows an F-distribution with 1 and degrees of freedom, denoted as Fp-1.1- Generally, the cumulative distribution function (CDF)
Notice that the random variable
of
of Jd at given point is evaluated
d,z d2 di d1=td 2
P ( de 2
B (1; 2
where represents an incomplete beta function:
B(zaa,b) / 10-1(1 (1-)011 -2
Notice that the probability in (47) is basically the CDF of Fp-1,1 evaluated at (>²(p 1)) 1))- therefore
B Tt 2
B
(
ax
IP
J p
N²(p
1)
B
11
(2
2
where in the last equation we used the well-known relationship between the beta function and the gamma function:
B(L:a,b) r())r(b)
I'(a +
Since r(1/2) =T, and for p 2 by the Gautschi's inequality:
p-1
2
2
p
34

---

one can bound as
1
p 1
DA S
B
2TT
1 X2
2
2
14x2 1 di
2T
VI-t
P
1 + X2
1+x3 t² dt
2TT
X2
(1+ 772
2p
T(p- 1)2
X
(1+ X²) 32"
(pp
2)
A
where in the second inequality we used v1 - 2 proof.
V
1+x²
Xa
when 0 Stt 1
This completes the 14x2.
H.2.2 Main Proof of Lemma H.2
We are now ready to use the results of the auxiliary lemmas stated above to prove Lemma H.2. ('(,,, I). We define the random variable
Consider x E SP-1 where p 3, and g [ : mpl T
g
|
Notice that by construction 0 S a S 1, which combined with the result of Lemma H.8 gives
= 0
A A21 1
-1+23)'-8 B
P Pfu > A}:
5
2 x)
0< A <
(48)
A
As result, for all t 2 0 and integers q 2 2:
E Exxp (lu²)= S' exp (IA9) d (PP < ^)) 1/" exp ((A)) {u *])
1 /'' exp P(u AjdA
I X9-2 exp (1 (1 (2) T(p 2)
$ 1 tg
=2)-
(49)
where the third equality is thanks to integration by parts and the fact that P(u > 1] = 1 P(u>
0}- = O.
Part (a) Proof Consider q 2, then by (49) we get
2
L' exp (1X²) (1 (1) -d
Eexp (tx²) < + 2t
T(p
2)
2
/''
114 + 2t
(1 + X2) - 11+ dd
T(P 2)
2
=1 2t
(1 X2) 1+ m 1+
=d
(50)
T(p 2)
35

---

where in the second inequality we used the fact that for all E [0. 1]: exp(=) S (1 =)
جلक which
implies that
22 E 10.1]. t 0: exp(tz) - (1 + 2)
For all E 0, (log(2)/VV/] setting t = ppp in (50) gives
E Eexp (r' 5 11+ 27
T 2) J (1+ da
$ <1+ 11+22pp
(1 + 2 =d
T(p - 2) 5o
[0, (log(())))) 2)/ v3 and p 2 27:
Now using Lemma H.5, we have for all r E
12 T(P 2)(p 6)
E Exxp (r"pu²) 51+ 27
25
< + T
4
25
S exp
72
4
Since 2/5]
0. /log(2 ( \/3 the advertised claim is valid.
Part (b) Proof
Notice that by (49) we have
T(p 2) S. 22 [ (( Edd
E Eexp (tu") s 1 + 4t
For all E [0, log(2)/6) setting L = TP gives
E Eexp (TpM*) < 4TP4
2
2 + x1)
T(p 2)
2
S
12(1+23)--
< 1 4Tp/
T(p 2)
Now using Lemma H.7 we get
54
13r
137
E Exxp (Tpu*) ") s 11+ =112TP <(p 11p-2)p 2p 6)3
S1
- exp
p
p
I Proof of Theorem 5.1
Theorem 5.1. Suppose that u. v E S are unit vectors. Let : be a Rademacher random vector in RP. Then,
E sign (z T u) sign (z [v] arcsin(u T v) s cg u, | (u, v
2
v (u, v32u
where 264 is an absolute constant, and for two unit vectors and w/ in Sp-1;
g(w, w') = Σ (w) + w/ 2//33//2
(51)
1=1
36

---

Proof. A main component of the proof is the following result due to Raiè [67].
Theorem I.2 (Multivariate Beny-Esseen [67]). Let ri...., Tp be independent random vectors in R. Assume that Ex, 0 for all and that Ei= Cov(x;) La. Let -i= R.+
Then, for all convex sets A [ R we have
By E A} Pfg E AAI (42d + 16)
Σ
B|a,,11
i=1
where 3 is random vector with standard normal distribution (0, Ta).
Consider W be the subspace formed by u and and columns W E R forming an orthonormal basis for W. Consider W [w, w/). Projecting any vector onto W is done through (w(x) WT.. Since projection does expand the angles we should have sign (z u) sign (x WWW u) sign (z WWT u/ Tull)
(52)
and similar relation holds for v. Define
ύ := W u/ || u||
ú= W // W e/|
The random vector W can be viewed as the sum W = > 1= 2; for
I,....P. .. P.
where the i subscript denotes the i-th element of each vector. Note that by construction I; are independent, E.,; = 0 and
Σ Cov(1,) E [WT tt T w] = W E 1 W = W ,, = I2, Am
which indicates that ay meet the conditions stated in Theorem 1.2. We now have
E sign (z T u)) sign (r TT) u)] sign (z W sign (z [Wi]
2P fr W 0, We > 0} - 2P 0, Two <0}
where the first equality is thanks (52) and the second equality is a simple expansion of the expectation, using the fact that sign(() 0 and due to symmetry of r:
P ft w > 0,z² WT > 0} =p TTT wu 0, Tw < 0)
f T w 0,z WT < 0} PP (r T 0, 7 TW 0}.
For 3 NO 12), we have
arcsin ūū 3)
arcsin(u vv)
2x where the second equality holds since the angle between ū and the same as that of u and v. Applying the triangle inequality and twice appealing to Theorem 1.2 we get
2x
E sign (x u) sign (: [u]] arcsin(u v)
2 π
<
2 PP Wū 0, T WT > 0} -P(s 103000.5 To> 0}
P (z Wū 0, T 0) P
W
(
0,5 6 < 0]
1/
+ 16 Σ E 1
< 264
E11 12
1=1
264
Σ
(w) + w!?"
(53)
Kml
37

---

Since this inequality holds for all selections of w and w', we can specifically pick the ones offered by the Gram- Schmiid procedure
(u, u/ur
w U,
w/
(54)
1/e (u, u)uil'
which implies that
- (u, o)u E sign (z (zT sign (x (zTo)]- arcsin(u" o) S Cg
(55)
||0 (u, r)u(l
In the sequel we show that the Gram-Schmidt selection is already tight and the right-hand side expression cannot be made any tighter. For this purpose, assume that we pick a different matrix with columns w and w.. Since v and w' must reside within the same plane w and w' in (54), and still meet the orthonormality conditions, we must have
= sin(a)w + cos(a)) T' = cos(a)w + sin(a))'
for some a E 2T). Now, notice that
g w') =
u + u?? 3/2
Σ (sin(a)w:: + cos(a)w!)) + (- cos(a)) + sin(a)w?)) 3/2
w + w!? 3/2
Σ
= sg(, w'),
which indicates that the right-hane side of the inequality (55) oblivious to the selection of W, and all such selections present identical right-hand side.
Proof of Corollary 5.1
Corollary 5.1. Consider unit vectors u, E S such that ||u||>0 O(p-1/2), |/u|l = Opp-1/2), and there exists some constant 0 such that (u,, v) < Then
2 E ssig (z u) sign (a v)] arcsin(u u) = 0 -2/2)
Proof. We only need to show that g(w, w/) Opp-0pppp00) 1/2) for ws and w' picked (54) and g defined as (51). Clearly, by construction ||w]|oo = 1/22. On the other hand
||0 (u, u)uuloo
S || x0 ((,, v) ||u|loo
< || xo |||||2///|aa|l/
|| so ||
O(p -12)).
(56)
Moreover,
|| (u, u)ull2 2 || KN, w/ll/
Ku, v>1
(57)
38

---

Combining (56) and (57) implies || = O1p-1/3), and therefore
2 Σ
g(w, w/)
w w!
max
w
i= u
wi
max i=...pp
w
0(p-1/2)
K Proof of Proposition 5.1
Proposition 5.1. Consider similar RASU (or ASU) layer as Theorem 4.1, where for fixed constants C, 8 >> O, ||<]|/>. S Cp-11/2 ||w;]| Cp-1/2, and |'m x] 8 for all i E nn.. Define the embedded output as ÿ ReLU(sign(( WiRgn(WRR (iig((Rx) for " Id (signn(W sign(Rx))), where R RNxp a Rademacher matrix. Then, with high probabiliry:
log n N
N 1/
y
S 2
Proof. The main difference between Theorem 4.1 and Proposition 5.1 is that the Gaussian matrix G E Nxp is replaced by a Radamacher matrix R E RNNx, Recall that 9 denotes the j-th row of and note that gj enters the proofs of Theorem 4.1 through the random variables
3ij sign (9) w.) sign (gi Tx).
(58)
These proofs rely on three properties of these random variables:
(P1) -1 S Sij I 1 for all (i.j) E (1..... n) x (1,...,p).
(P2) For fixed i [l.....n], n}, the random variables 31.. Bep are ii.dd,
(P3) The expected value Eøsý arcsin(u: 2z)
When replace the rows o/ of & with the rows zJ_ of R, and define
ãuj sign (t. ws) sign (zj x),
(59)
properties (P1) and (P2) continue to hold for Bij. and by Corollary 5.1, property (P3) approximately holds
2 arcsin(w, x) + O(p 1/2)).
E (Be;))
(60)
π
If we define of = ReLL((E(A))) (or yf ((5r)) for the ASU case) for i {l...., n), then the proof of Theorem 4.1 implics that for any c 0,
1 N
2(c + log 2n)n
N
with probability at least - exp(-op Using (60) and the triangle inequality we get
(Velos
N Ø
+ V
(61)
with high probability, which completes the proof.
39

---

L Proof of Proposition 5.2
Proposition 5.2. Consider a similar TASU layer as Theorem 4.2, where additionally for fixed constants C, > O, || I Cp-1/2), lwillo I Cp-1/2, and O < lmin I |wm x I 1 8 for all E mI.. Define the embedded layer output as sign (on(ssue signi sign(Rt)), where R E RN is Rademacher matrix.
Assume Cp 1/2 S mmin/T.. T. Fix E S v and set it Z
Cp-112
I log Aym Then, picking Emin
N Onk log n/=2) guarantees that -yy- 0 12
O(E + mw/n/p) with high probability.
Proof. The proof is similar to that of Theorem 4.2 and we outline the main steps. The discrepancy between the two layers can be bounded ||e||2 || 2ll ||e ||e||2, where following (59) as the notation:
2x tanh
aresin (w: xo] o0)
e tanh
3ij
N
π
and
c/ = sigm
Sig
tanh
3y
The term e' in the proof of Theorem 4.2 can be handled in similar way as in the proof of Theorem 5.1, indicate that with probability exceeding exp(-c):
2(c+
+ CV RZn
|e'll2 <
N
where the additional term / /22n/p comes from the Lipschitz continuity of Lanh(x-) and a triangle inequality similar to (60) and (61).
For the second term we similarly have
N
|ee1
exp
-2k
j=1
Applying Hoeffding's inequality and the triangle inequality guarantees that with probability exceeding 1 2 exp(-c)):
1
N
2
22c C
3k
min
π
VN
VD
This indicates that with probability exceeding 1 -2exp(-c)
4x Emin + =
8(c log n)
Ck vp)
|10" < 2exp log vn π
Setting N = 8(c+ log 2n)nn3// /E3 guarantees with probability exceeding 1 - 3 3expp--0
|el|2 < & +
C
kPn + 2 eexp
log vn
Liin + 6
Ck /p
2
p
If pick in a way that
4K
4
Cn
miin
>
22og
(62)
π
8
40

---

then by similar argument as before we will have
4x 4/n
Ck
Ck
min 2 2log
2
log
vn
+ +
log
π
8 vp
vn
vp
and subsequently
kZn
|lll2 S + CV
It only remains to see that when Cp-1/2 < mina/ v and 2
Emin log
4yD condition (62) is met.
M Minor Distribution Shift of Wide Neural Networks
is well-known that in wide neural networks, the weight distribution shifts only slightly over the course of training [15]. In this section, present numerical experiment to demonstrate this property. For this purpose, we train a fully connected G-Net on MNIST data with wide first layer (width 1024) initialized using normalzzd Gaussian weights. During training, monitor the evolution of the layer's weights and report their empirical distributions at epochs 0, 1, 10, and 25, as shown in 5. 5.
12
12
10
10
4-
2-
2
0
0
-0.2
-0.1
0.1
0.2
-0.2
-0.1
0.1
0.2
Initialization
opoch
10
10
8
8
6
2-
0
0
-0.2
-0.1
0.2
-0.2
-0.1
0.1
0.2
10 epochs
epochs
Figure 5: Minor weight distribution shift for wide layers: the distribution of the weights of fully connected G-Net Layer at epochs 1, 10, and
N G-Net Implementation Details
In this section, we discuss key implementation details of G-Nets, including the handling of fully connected layers, convolutional layers, general linear layers, and classification versus regression output layers. We also present alternative strategies for incorporating bias in linear layers to enhance the concentration properties of the EHD G-Net.
41

---

Fully-Connected Layers. As discussed in the paper, when W E R"xp maintains &2 lg-nommalized rows, z E gP-1 and G E RRVx xx is Gaussian matrix, then by Grothendieck's identity and the law of
large numbers:
sign (WG)) sign (Ga)
arr)
(63)
N
N 00
For finite N, we refer to the left-hand side of (63) as the EHD representation of the right-hand side expression. When W and do maintain the normalization property, the right-hand side argument needs to be normalized properly. More specifically, consider general W E <Rxx,, RP, and Gaussian matrix G R Nx,,
x9, structured as follows:
W
W
G
Then we can construct a diagonal matrix to perform the normalization on W as
N
2
arcsin (Dwa Wx)
EHD
sign ((g, x)) sign (Wg).
(64)
π
where
Dw,z ||01|2 diag (l...l...... [w,,1l1))
(65)
and diag(an,.... Oaa) is a diagonal matrix with elements on,.... On- Basically, the left-hand side expression of (64) is what is implemented in fully-connected layer of G-Net.
Smooth Approximation of the Norm. When training G-Net, the rows of W need to be normalized by their & norm. Basically, the i-th row of W takes the form w. /|[wa]12- To maintain bounded gradient flow during the training, we use the smooth approximation
||w
11:1112 + +
where 0 is small constant.
Different Handling of the Bias for Faster Concentration. For an input v E RR, the output of a fully-connected layer is normally in the form Wa b where W gaxp and b e R2 are learnable weight and bias parameters. One could think of absorbing the bias in the weight matrix as
x
Wx + b = Wa, where: W = IW b]. H
and view the problem as instance of the aforementioned fully-comnected case. However, as discussed the theoretical results, especially for Rademacher embedding, having the weights evenly spread out helps with a better concentration of EHD G-Net. Since the scales of b and W after training can differ significantly, an alternative approach to introducing a bias term in linear layers (aimed at promoting more balanced distribution of weights) is to use fully connected layer of the form
W (x + clp).
where W E _R and E E is a learnable scalar. By trading off a negligible degree of freedom, this formulation eliminates the issue of uneven scaling between weight and bias parameters. This idea naturally extends to other linear layers and simply involves adding learnable constant to the input.
General Linear Layers. The implementation scheme described above for fully connected layers can be extended to general linear layers, which may include layers such as batch normalization, average pooling, or cascades of multiple linear transformations. Consider a more general linear operator Tw V + R", where V IRPt X Xp.x...Xp, and W denotes the parameters associated with the operator Tw. Let e, denote the j-th canonical basis vector in R Then the j-th component the output of Tw can be expressed
(66)
42

---

where Th is the Hermitian adjoint of Tw. According to (66), one can interpret 1h (e,)ll Hs. the Hilbert Hilbert-Schmide Schmidt norm of (e,), the norm of the j-th "row" of the operator Tw. Letting Go for i == ...... N, be i.i.d. Gaussian tensors of the same shape as X, generalization of (64) takes the form
N
arcsin
( O (x)(X))
EHD
sign ((Gi, X)) sign (Tw (G:),,
(67)
where @ denotes Hadamard product, d W.X denotes the Hadamard inverse of the vector dw.x. and
(e))les
dw.x = ||=||
(en)lle
Equation (67) shows that, once the Hermitian adjoint of a linear operator is available, normalizing the operator and constructing the hyperdimensional embedding become straightforward tasks. For a simpler notation of the canonical basis, the range of Tw is considered to R However, this framework readily generalizes to multi-dimensional output arrays, in which case dw,x is replaced by Dw,x, a tensor with the same dimensions as Tw (X).
Convolutional Layers. Although convolutional layers linear and can, in principle, be addressed using the formulation from the previous section, we introduce a specialized approach tailored for compact representation and improved concentration properties. For notational simplicity, we focus on one-dimensional convolution with a single output channel; the generalization to higher dimensions and multiple channels is straightforward. Consider RP input array, E IR" convolutional filter, and let * denote a vector-wise convolution (or cross-correlation). The convolution is vector of length m, where depends on input parameters such as p. n, padding, and stride. Each vector-wise convolution w x can be expressed as a matrix-vector product:
W
P
W
(68)
1
PT
where Ps
(0, 1, & {L...., m). circularly shift the elements of w. While the explicit construction of Ps is not required, the row norms of the matrix in (68) can be efficiently obtained via simple convolution operation as follows:
|| Pi wl
(w w) * 1p
||
where 1p denotes length-p vector of all ones. Following the base equation in (64), for ~ 10) the embedding takes the following form
2
arcsin (Dwd(w +
EID
Σ sign ((g,, x)) sign (w (g:),
(69)
where
D w,
||0|| diag ((w @ w) * 1p).
One can use the commutative property of the convolution and write
P
W =
w,
Pm
which for gs (N Iw) offers the following alternative embedding scheme
2 arcsin (D))(w+=))
EUD
sign ((gs w)) sign (æ * gi),
(70)
TTh Hadamard inverse of vector is acquired by inverting each element of d, i.e., 1 1/d,-
43

---

where
Dw,a= = 1|w|2 diag ((x 1,).
In convolutional layers, it typically the that < p. which makes (70) preferable over (69) due to its faster concentration with increasing N.
For multi-channel imput signals, consider an imput vector of length with n. channels, and learnable weights length n corresponding to each input channel. We use the notation
X [ ..... In. IR"x",
W [ W Wo.]
Rax*=
In this case, the output of the convolutional layer is vector of length which is computed via
W 8 X
For independent Gaussian matrices Gi Rax*, generalization of (70) the multi-channel input case is offered through
arcsin (Dw'x (W + x))
sign ((Qi, W)) sign (X G.),,
(71)
where
Dw.x
loyll
diag
Σ
xj Ozj
* Ln
|| diag ((X o X) @ lnxn.).
Network Output Layer. In this section, we describe how to configure the network's output layer to function either regressor classifier.
For regression, we can model the final layer as
ASU
D DW WLUL-1)
where Dwi.ii- is given by (65), and the subsequent hyper-dimennsional embedding follows the standard procedure. To employ this structure, the only requirement is to rescale the response variable to the interval 2 so that its range is consistent with yz above.
For classification G-Nets, we can still use standard soft-max activation
yL = SoftMax (DW² (WWL.LL- WIBL-1).
(72)
Since the ASU function is monotonic and preserves the position of the dominant component in an array. it is omitted from (72). yet a standard hyperdimensional embedding the right-hand side of (65) can be used. The EHD G-Net predicted label is determined by identifying the index of the maximum absolute component in the output vector.
Extended Numerical Experiments
In this section, we conduct numerical experiments on several datasets commonly used as benchmarks
in HDC classification tasks [32], focusing on more challenging vision datasets such MNIST,
FashionMNISTT, and CIFAR10. We also include two human-acts -umannacttiity recognition datasets, HAR- WSS (walking, sitting, standing) [65] and Epilepsy [70]; an automotive dataset, Ford-A [40]; natural-language dataset, AG News [72]; and time-series dataset, Fault Detection-A [64]. A key characteristic all datasets selected for evaluation that, unlike simpler HDC datasets such as European Languages [52] and ISOLET [45], which achieve high accuracy with linear classifiers like support vector machines (SVMs), the chosen benchmarks are not easily addressed by such models. In fact, many HDC methods struggle to perform well on these datasets. To assess the effectiveness of
44

---

the proposed framework, we compare its performance against several established and recent methods, including classic HDC [8]. HoloGN [23]. Laplace HDC [26], OnlineHD [10], and RFF-HDC [37].
Table summarizes the datasets used, including the number of input features (no), output classes (nz), and the corresponding G-Net architectures. We aimed to vary the layer configurations across datasets while maintaining simplicity and reproducibility, For instance, on the FashionMNIST dataset, we employed a single convolutional layer stress-test G-Net under shallower architecture. demo of G-Net training/EHD conversion, along with all experiments reported in this section, is available at https:// /gi thub. com http//Nee222/////t /
Table 1: Dataset and G-Net architecture specifications. In layer descriptions: CN denotes convo- lutional layer (input channels, filters, output channels), EM an embedding layer (vocabulary size, number of outputs), FC a fully connected layer (number of outputs), and CL classification layer (number of classes)
MNIST
MashionMNIST
Ford-A
WSS
Epilepsy
CIFARIO
AG
Fault Detection-A
Data Specilications
28
no 28
500
206
206 3 Ag x22 x3
Ng (400, 512)
Ro 5120 22g
0gg
10
ng
2gg
G-Net Specifications
CN(L322.3
CN(L332,5)
15() 1N(16.66.15)
CN(364,11) CNI6LA4)) CL16)
(N13,6A,11 CN16LA887 CL())
CN13.32,5)
2MHH1200112 CNIS1264,
CNLL 3. 64,
CN(2264,5)
PCYS12) CL/10)
CN(3266455
CN(64, 48, CLD3)
FC(512)
CN(16.25,13)
FCLS12)
CL(4)
CL210)
CL22)
CL(10)
The first set of experiments involves fitting a G-Net to the original training data, followed by evalua- tion in the binary hyperspace by applying the corresponding EHD G-Net to the hyperdimensional embedding of test data. The G-Net training is quick, for instance, training ten epochs on MNIST requires roughly 48 seconds on desktop computer equipped with GeForce RTX 4090 GPU. The EHD conversion of the same G-Net takes less than 0.5 seconds, and the inference time for each embedded sample is in the order of milliseconds. Figure 6 reports the average test accuracies of EHD G-Net and other HDC methods. The reported hyperdimension N represents the average Ne across G-Net layers and the dimension used in other methods. For each N, the conversion of the reference G-Net to an EHD G-Net was repeated multiple times with different random matrices; the same number of repetitions was applied to other HDC techniques. The plots show the resulting mean accuracies along with +1 standard deviation.
The G-Net architecture used in Figure 6 is RASU network, and the results, both for Gaussian and Rademacher embeddings are reported. While Gaussian embedding yields slightly better results, the accuracies of the two embedding methods are very close. One observes that without training large binary model, and by training only a compact network in the primal space followed by inexpensive binary encoding, achieve classifiers that outperform state-of-the-as HDC models by significant margin. For example, HDC accuracies exceed 99.2% on MNIST, 81% % on CIFAR-1Ó, 10, and 91% on MashionMNISTT rivaling real-valued convolutional neural networks. The reported accuracies can be even further improved by employing larger G-Nets and higher hyperdimensions, as EHD G-Net performance asymptotically approaches that of the original G-Net with increasing N.
We extend our study of the first four datasets under the same experimental setup described above. While Figure 6 presents the performance of RASU G-Nets with both Rademacher and Gaussian embeddings, Figure 7 provides a more comprehensive comparison across a broader range of hyper- dimensions for both activation types. Specifically, it presents G-Net and EHD G-Net accuracies of RASU and TASU networks, evaluated with Rademacher and Gaussian embeddings. As expected, RASU networks generally attain higher G-Net accuracies, with faster EHD G-Net concentration. However, TASU still remains competitive (achieving, for instance, 98.4% accuracy on MNIST) al- though, as theory predicts, TASU-based EHD G-Nets converge more slowly to their G-Net baselines. This modest accuracy gap is the trade-off for a fully binary inference pipeline. Notably, the same constraint also gives TASU networks greater robustness to model perturbations, will be discussed below.
As discussed earlier, the proposed framework develops base G-Net model, from which combinato- rially many BNNs can be instantiated. Although the frameworks and objectives differ, it natural to ask how our approach relates to existing BNN methods. To this end, Figure 8 compares G-Net
45

---

96
Accessc (30
-i-Nit Baadiee
- Lap
LHD Se. Rainzador OslacHD
Gacerar
00
--G.k Surdan
Tapla-HDD
75
Hatezooke
9000
Hxpeddiocaton
(b)
80
76
Ac3002 (36
70
00
RIE Bexite
LapkoelDo
50
Gabvill
40
BED
SED G-Net Faraddr
Claee HDC
3.5
15
0.8
1.4 Heprrdimento (N)
1.2
1.
14
Hyperciteerrinn (N)
x10
x13
80
70
2HDD Gole Genetas
fi-Ne Ruberader DateelI
--B---DDC
.-.
-Cless-EDC
60
30
20
OslavED
BED G.Ne Grrelas
RFT
Chank HDC
1.5
34
Hyppecdineeoconn [N]
Elprrdimnetto (N)
(c)
ff)
100
100
50
50
Mounney
50
40
Laptaz
NN, Badier
Exprrditenaton
(b)
Figure 6: Comparison of Gaussian/Raddmmache RASU G-Net with other HDC methods on different datasets (a) MNIST, (b) FashionMNIST, (c) Ford-A, (d) WSS, (e) Epilepsy, (f) CIFAR10. (g) AG
News, (h) Fault Detection-A
46

---

96
Acrueyy (83)
Accunc
80
RASU C-Nex Baadinz
80
RASU G.Set Busiie
TASU G-Ne Roedine
TASU G.Nec Roodline
RASU -Grreiee
RASU Corpoia
- R.5SU Radenndes
704
RASU Radcwsdet
Boleasncker
0.2
0.4
1.2
1.4
1.8
0.5
1.5
2.5
By Rypentinnction (N)
x10
Hype dimmmiio (N)
x10
100
100
TASU G-Net Budlas
-e- IASU Gezsii
-e- TAS Tlldeernoeer
Accuney (5))
Accuncy
85
86
RASU G-Nis Baadier TANU Boeetto
80
TASU
Repennlimetsion (N)
x000
x10f
(d)
Figure 7: Performance of TASU versus RASU networks for Gaussian and Rademacher Embedding: (a) MNIST, (b) FashionMNIST, (c) Ford-A, (d) WSS
with XNOR-Net [28] and BinaryConnect [46]. A direct, fair comparison with hybrid designs such Bi-Real Net [21] is not feasible, those models interleave binary and foating-point operations. To conduct fair comparison. we first train fully connected G-Net with two hidden lay- ers (each of width 256) on FashionMNIST and then form binary EHD G-Net using hyper- dimensional embedding of size N 1000. We subsequently fine-tune this model with either BNN technique and benchmark it against sim- ilar BNN initialized with random weights. Fig- ure 8 shows that EHD-initialized BNNs start with substantially higher aceuracy and attain their peak within few epochs, whereas stan- dard BNNs typically require many more epochs to reach comparable accuracy. From opti- mization standpoint, G-Net allows performing major part of the optimization in smaller, continuous space, without the challenge of working with binary decision variables. G-Net accuracy serves as a baseline for the binary model, indicating how far its performance can be pushed in the course of training.
XNOR Noe
10
Givrt with Enarypinnnet Pining
GSvt with XNOIt- Net Piae- Timin
Nusaoe
Figure 8: Comparison with BNN Methods
Hyperdimensional models are known their resilience to model corruption, and our G-Net variants are no exception. To quantify this robustness, we stress-test RASU and TASU EHD G-Nets by randomly flipping a fraction of binary weights every layer. For instance, applying a 10% flip rate the MNIST model randomly inverts 10% of the weights in each of its four layers. Figure plots the resulting accuracy degradation versus corruption level, with confidence regions created by repeating the experiments twenty times. Notably, TASU networks lose accuracy more gradually than their RASU counterparts. This stems from TASU's architecture: each TASU output the sign of an inner product between two binary vectors, quantity less sensitive to individual bit flips than the zero- sero-thresholded binary inner products used in RASU layers. As a result, even after flipping 35% of the EHD G-Net weights, the TASU model MNIST still maintains over 95% accuracy.
Because each HDC method employs its own hyperdimensionaa embedding and inference pipeline, the weight- fiihhiifiippng corruption described above cannot be applied uniformly across other HDC
47

---

50
Arcisay (54)
Mernay (5)
40
40
90
60-
RASI BID G-Set
75
RASU RHD G-Net
TASU EHD
02
0.3
011
025
0.45
03
80
80
70
Acciing 191
RASU EMD G. Ge TASU ERID G-Net
30
RASU RID G.Net TASU EHD GeNet
Ratao Rassioilyy Flaped Wetahee Encia Lagez
Batio Razdomll Fliypod Weighta
Bodi Lages
(d)
Figure 9: Robustness of TASU and RASU networks against random bit flips across all layers: (a) MNIST, (b) FashionMNIST, (c) Ford-A, (d) WSS
frameworks. Instead, we observe shared step across all models: each generates a hypervector that subsequently fed into an inference block for prediction. To apply a common corruption pattern across all the HDC models in comparison study, fix the hyperdimension and corrupt the hypervectors by flipping a specified fraction of bits immediately after the embedding stage of each method. The noisy hypervector is then fed to the inference block for prediction, and the mean accuracy across multiple experiments is reported. For EHD G-Nets, bit flips are injected right after the first random-sign embedding, and the corrupted embedding propagated through the network. Figure 10 plots accuracy degradation for the various HDC models under this hypervector corruption. The TASU and RASU networks had less noticeable performance gap under this test, and only TASU accuracies are reported in these plots. We attribute the superior robustness of EHD G-Nets to their tightly integrated, binary, multi-stage inference pipeline, which is feature largely absent from existing HDC architectures.
P
Computational Cost
of EHD G-Net versus a Floating Point G-Net
In this section, we mathematically compare the computational cost, in terms of time and memory, of EHD G-Net versus the corresponding floating-point G-Net. sense, any floating-pon can be considered as binary neural network by viewing the floating-point weights as bit sequences, which are operated on by foating-point arithmetic operators. However, unlike the EHD G-Net, these bit sequences would have significant bits, and the operations on these bit sequences In contrast, the EHD G-Net uses simple operations and has no significant bits; consequently, the EHD G-Net architecture is robust to random bit flips, see Figure 9, On the other hand, floating-poit point numbers have significant bits (such as those encoding the sign and exponent of a floating point number, which significantly change the output when changed). Thus, the EHD G-Net architecture is more suitable for noisy computing environments, such as low-power computing.
network
complicated.
It is still instructive to study the different computational costs, in terms of memory and time, of each method. For simplicity, we restrict our attention to a single fully-connected EHD G-Net layer using a Rademacher matrix and the corresponding floating G-Net layer.
48

---

100
100
70
Aoverary
Not -nioodiD
BDC Nox
aI B-BDC
10
--BBoGGN ---TT-- F-EDDC
Legitss HDC - Chesie HDC
... ---aaaan Clasii HDC
0.2
0.3
0.1
0.35
0.45
Ratio Hegatrvector Flipped Bita
Rutia Roparvooior Fliyoal Bits
70
70
80
60
80
-- IDD G. Not - =--OnreeI - -HoooS
+0-DC G Not - O-OOiEUDD
-DFF-DDC
+-BobGG -EFF-DDC
-TpphooHte Closte-IDX
-.. ---LatecHtCC Cansie HDC
0.05
011
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.05
0.1
0.15
02
025
Da
0.35
0.4
0.45
0.
Raiso of Hoperrector Flippod Bits
Rolio Hypeevecto Fliyood Hits
(c)
(d)
Figure 10: Comparing the robustness of an EHD G-Net with other HDC methods: (a) MNIST, (b) FNShionMNIST, (c) Ford-A, A, (d) WSS
Fix a hyperdimension N, and the number of bits used in the floating-point representation of numbers F (for example, F' 64 for double precision floating point numbers). Let and be the input and output dimensions, respectively. Assume that æ E IR", W E Rm*x,, and R E {-1, 11 the hyper-dimension is N. Consider the EHD G-Net Layer that performs the map
x - sign WWR )sign((x))
and the corresponding floating-pont point G-Net layer
r arcsin(Wz).
The EDH G-Net must store sign(W2 WWR which has dimensions m N and R, which has dimensions N x The entries of these matrices can be encoded in binary, so the total memory required to store EHD G-Net layer is
memory G-Net = (m + n)N bits.
The floating point (FP) G-Net involves storing the bits to encode, for a total of
matrix W whose entries each require F
memoryrp G-Nee = (m n)F bits.
Next, we consider the computational cost terms of time. The EHD G-Net layer starts by applying R to x and then applying the sign function. This involves an XOR of sign bits, adding the resulting integers, and taking the sign of the result. Let fxoR and fz denote the time to compute the XOR and add integers, respectively. Finally, let fsign be the time to take the sign. After that, we need to compute fXOR of Nm entries, and then sum Nm binary value, which can done with popcount. Let (popeount denote the time for popcount (summing binary values). In summary, we have
(Nae)) timeEhD G-Net = ((tror + (popeounn) (Nm) + (txor tz (NN) + (N))
Next, consider the floating-poit G-Net layer. Let laresin the cost to apply 2/TT aresin, tR. be the time to add floating point numbers, and fg,x be the time to multiply floating point numbers. Then, we have
timerr G-Net G-Net = O =( + (m n)( + (2x))
49

---

If N and F' are fixed, along with the time cost of all operations, then the computational complexity of EHD G-Net is (m + n) in terms of memory and time complexity compared to O(m n for floating point G-Net. However, even when m and are small, we emphasize that EHD G-Net offers an advantage terms of robustness to random bit flips. Figure 11 replicates the first row of Figure 9 where we previously showed that randomly flipping the binary weights of an EHD G-Net causes a slow drop of accuracy. However, instead one considers randomly flipping bit sequences on floating point G-Net, the accuracy drops much faster, as demonstrated in Figure 11.
03
80
Atstaay (5)
60
Acerary (K)
60
50
80
-AAUU EHD 61-Nit
G-Net
TASU RHED G Net
+- TASII FIRD G-Ner
10
RASU Net (Bit Sequence)
G-Nee Segunee)
10
RASU G-Net (BIL Sequesos)
TASU G.Net Sequencce
02
0.1
Eadi
Booh
Figure 11: Robustness of TASU/RASU networks against random flips of EHD G-Net weights, and bit sequences of the corresponding G-Net: (a) MNIST, (b) MNSSI
Appendix References
[40] A. Bagnall. Dataset:
httpps///ww.iinesrrrsssst http://www..beeeeeeeeaasiiiaaaoe com/ pttprrppptioo.pppppaaatsst-trrro php?Dataset-Ford.
FordA.
description,
[41] Yogesh J BBaul and Ramkrishna M Dhaigude. Simple efficient bounds for arcsine and arctangent functions. Research Square Preprint, 2021.
[42] Grahame Bennett, Victor Goodman, and Charles Newman. Norms of random matrices. Pacific Journal of Mathematics, 59(2):359-365. 1975.
[43] Cheng- Yang Chang, Yu-Chuan Chuang, En-Jui Chang, and An- Yeu Andy Wu. Multa-hde:
A multi-task learning framework for hyperdimensional computing. IEEE transactions computers, 70(8):1269-12888 2021.
[44] Cheng-Yang Chang, Yu-Chuan Chuang, and An-Yeu Andy Wu. Ip-hde: information-preservv hyperdimensional computing for multi-task learning. 2020 IEEE Workshop on Signal Processing Systems (SiPS), pages 1 1-6. IEEE, 2020.
[45] Ron Cole, Yeshwant Muthusamy, and Mark Fanty. The ISOLET spoken letter database. Oregon Graduate Institute of Science and Technology, Department of Computer.... 1990.
[46] Matthieu Courhariaux, Yoshua Bengio, and Jean-Pierre David, Binaryconnect: Training deep neural networks with binary weights during propagations. Advances in neural information processing systems, 28, 2015.
[47] E. Paxon Frady, Denis Kleyko, Christopher J. Kymn, Bruno A. Olshausen, Friedrich T. Sommer, Murat Okandan, and James Aimone. Computing on functions using randomized vector representations (in brief). In Newro-Inspired Computational Elements Conference, pages 115- 122. ACM, 2022.
[48] Ross W. Gayler. Multiplicative binding, representation operators, and analogy. Advances in Analogy Research: Integration of Theory and Data from the Cognitive, Computational, and Neural Sciences, pages 1-4, 1998.
[49] Olivier Guédon, Aicke Hinrichs, Alexander E Litvak, and Joscha Prochno. On the expectation of operator norms of random matrices. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2014-2016, pages 151-162. Springer, 2017.
50

---

[50] Alejandro Blernandez-Came Cheng Zhuo, Xunzhao Yin, and Mohsen Imani. Reghd: Robust and efficient regression in hyper-dimensional learning system. 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 7-12. IEEE, 2021.
[51] Mohsen Imani, Samuel Bosch, Sohum Datta, Sharadhi Ramakrishna, Sahand Salamat, Jan M Rabaey, and Tajana Rosing. Quanthd: A quantization framework for hyperdimensional com- puting. IEEE Transactions Compuler-Aided Design of Integrated Circuits and Systems, 39(10):2268-22)) -2278, 2019.
[52] Aditya Joshi, Johan T Halseth, and Pentti Kanerva. Language geometry using random indexiig. In International Symposium Quantum Interaction, pages 265-274. Springer, 2016.
[53] Denis Kleyko, Evgeny Osipov, Nikolaos Papakonstantinou, Valeriy Vyatkin, and Arash Mousavi. Fault detection the hyperspace: Towards intelligent automation systems. 2015 IEEE 13th International Conference Industrial Informatics (INDIN), pages 1219-1224. IEEE, 2015.
[54] B. Komer. Biologically Inspired Spatial Representation. PhD thesis, University of Waterloo, 2020.
[55] Rafal Latala and Marta Strzelecka. Operator ép + lg norms of gaussian matrices, 2025.
[56] Duy H. Le and Tuan Pham. Improving bi-real net with block-wise quantization and multiple- steps binarization on activation. In 2020 RIVF International Conference on Computing and Communication Technologies (RIVF), pages 1 1-6. IEEE, 2020.
[57] Zewen Li, Fan Liu, Wenjie Yang. Shouheng Peng, and Jun Zhou. survey of convolutional neural networks: Analysis, applications, and prospects. IEEE transaction on neural networks and learning systems, 33(12)x6999-701) 2022.
[58] Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network. Advances in neural information processing systems, 30, 2017.
[59] Zechun Liu, Wenhan Luo, Baoyuan Wu, Xin Yang, Wei Liu, and Kwang-Ting Cheng. Bi-real net: Binarizing deep network towards real-network performance. International journal of computer vision, 128(1):002-219 2020.
[60] Alisha Menon, Daniel Sun, Melvin Aristio, Harrison Liew, Kyoungtae Lee, and Jan M. Rabaey. highly
hyperdimensional computing processor for wearable multi-modal classification. In 2021 IEEE Biomedical Circuits and Systems Conference (BioCAS), pages 1-4. IEEE, 2021.
[61] Samet Oymak and Ben Recht. Near-optimal bounds for binary embeddings of arbitrary sets. arXiv preprint 11Xhv:1512.04433, 2015.
[62] T.A. Plate. Holographic reduced representations. IEEE transuctions neural networks, 6(3):623-641, 1995.
[63] Tony A Plate. Holographic Reduced Representation: Distributed representttiinnnnnnnn for cognitive structures, volume 150. CSLI Publications, 2003.
[64] Paul Rabich. Dataset: Fault Detection-A. https://www.ttt http://///..ttteeeereessssssaaae http://www..teerrrreeeaaaaatttto com/description. ort.opoppppppaaatteeeaatttttttor
[65] Paul Rabich. Dataset: Walkingsittingsttaddngg. attps://wwwt
com com/description. cttp///escccppoooooopppptttsttte
[66] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt,
D. Koller, Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
[67] Martin Raič. A multivariate berry-esseen theorem with explicit constants. Bernoulli, 25(4A), November 2019.
[68] Ratshih Sayed, Haytham Azmi, Heba Shawkey, A. H. Khalil, and Mohamed Refky, A systematic literature review on binary neural networks. IEEE access, 11:1-1, 2023.
51

---

[69] Pere Vergés, Mike Heddes, Igor Nunes, Tony Givargis, and Alexandru Nicolau. Hdce: A hyper- dimensional computing compiler for classification on embedded systems and tigh-perfrrmacce computing, 2023.
[70] Jose Ramon Villar. Dataset: Epilepsy.
http:://ww..theerreeeddassssrrro com/
[71] Chunyu Yuan and Sos S. Agaian. A comprehensive review of binary neural network. The Artificial intelligence review,
2023.
[72] Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
[73] Wenyu Zhao, Teli Ma, Xuan Gong, Baochang Zhang, and David Doermann. A review of recent advances of binary neural networks for edge computing. IEEE journal on miniaturization for air and space systems, 2(1 3:25-35, 2021.
[74] Shien Zhu, Luan H. K. Duong, and Weichen Liu. Xor-net: An efficient computation pipeline for binary neural network inference on edge devices. In Proceedings International Conference on Parallel and Distributed Systems, pages 124-131. IEEE, 2020.
52

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Supporting theoretical results stated in Sections 3, 4, and 5, while experi- ments results are Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
53

---

Justification:
Each result is precisely stated with all assumptions, and detailed proofs of each theorem and support lemmas and references are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The setup of the experimental results is detailed in the paper and Appendix. link to a GitHub repository reproducing all the results is included in the abstract. All data sets used for testing are publicly available and referenced appropriately.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
54

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code that reproduces all figures and results linked the abstract as public GitHub repository. The Appendix provides the experimental details.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
ceabbbisssiooooiccyy... for more details. Sttpii//guiidd//Ceeeuee
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips cttpssscccpcccccccccpcccccccccct c/guides /eeudddde//oeebmiiii
CoodeSubmis ssi aasionPoiccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The training and test details are specified in Section O of the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All experiment results in Section 6 and Section of the Appendix include appropriate error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
55

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information about the computation resources used for the experiments is included in Section O of the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics btttps://neuriie cc/public/ wwwwihihiieeeleneeeeeee
Answer: [Yes]
Justification:
We follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work consists of fundamental research into random binary neural networks and binary hyperdimensional computing models, and has no direct positive or negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
56

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This work consists of fundamental research into random binary neural networks and binary hyperdimensional computing model and poses no such misuse risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All data sets and code used are publicly available for scientific use, and are appropriately referenced.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
57

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasttssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code accompanying the paper is documented with instructions about installation and execution steps.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Neither crowdsourcing nor human subjects involved the research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Neither crowdsourcing nor human subjects is involved in the research.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
58

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The research does involve any LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ //tprr//n.eu...eeeeeee / for what should or should be described.
59


Reviews:
[{"review_id": "Za6zEI10X0", "reviewer": "Reviewer_fAxG", "summary": "This paper presents a new class of randomized binary neural networks, G-Nets, designed to operate in the hyperdimensional Hamming space with guaranteed accuracy. Unlike traditional quantization methods, G-Nets employ a random binary embedding that enables neural networks to be represented in binary form without a significant loss in performance. This embedding is derived from hyperdimensional computing (HDC), a paradigm inspired by brain-like computation using high-dimensional vector representations. The approach provides theoretical guarantees for performance and is shown to outperform prior HDC models, achieving near state-of-the-art accuracy with significantly lower computational resources. The authors empirically demonstrate the effectiveness of G-Nets on classification benchmarks such as CIFAR-10 and MNIST.", "questions": "Task Generalization: Could the authors explore the application of G-Nets to other domains such as NLP or time-series forecasting?\n\nDimensionality vs. Efficiency: While high-dimensional embeddings contribute to the accuracy of the method, how does the model perform on hardware with limited resources, such as microcontrollers or edge devices? Could the authors explore how to balance dimensionality and hardware constraints?\n\nComparison with Binary Neural Networks: How do G-Nets perform compared to existing binary neural network architectures, such as Bi-Real Net or XNOR-Net, in terms of both accuracy and computational efficiency?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\nNovel Approach: The introduction of randomized binary embeddings and the theoretical framework based on HDC for constructing high-accuracy binary neural networks is highly innovative. It opens up new possibilities for low-resource deep learning.\n\nTheoretical Rigor: The paper provides strong theoretical underpinnings, including proofs and consistency analysis, which justify the performance of the proposed method. The use of Grothendieck’s identity and concentration of measure guarantees the method's accuracy.\n\nEmpirical Results: The experimental results on MNIST, CIFAR-10, and human activity recognition clearly demonstrate the superiority of the proposed G-Nets over prior methods in HDC. The results are consistent and include appropriate error bars, making them reliable.\n\nReproducibility: The paper offers detailed information about experimental setups, making it easy for other researchers to reproduce the results. The code is publicly available on GitHub, which is a strong positive.\n\nPractical Relevance: The proposed G-Nets show significant potential for edge and low-energy computing, which makes the work practically valuable for resource-constrained devices.\n\nWeaknesses:\nLimited Task Evaluation: While the empirical results are compelling, they focus primarily on image classification tasks (MNIST, CIFAR-10). The generalizability of the approach to other domains, such as NLP or time-series forecasting, remains untested.\n\nHigh-dimensional Embeddings: The reliance on high-dimensional binary embeddings may become inefficient in some use cases, especially when the hardware constraints are not well-suited for high-dimensional spaces. More discussion on potential downsides of this high-dimensionality in practical applications would be beneficial.\n\nComputational Complexity: The theoretical analysis focuses on Gaussian embeddings, but the paper does not sufficiently address the computational overhead when applying these methods in real-world scenarios with larger networks or datasets. The complexity analysis of Rademacher embeddings is promising, but more clarity is needed on the trade-offs.\n\nEvaluation against More Baselines: The comparison to existing methods in the HDC domain is solid, but the paper could benefit from a comparison against more state-of-the-art deep learning models, including quantized neural networks and binary neural networks.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n_________________________________________________________________________________________________________________\n\nTask Generalization (Q & W):\n\nYes, 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.\nTo 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.\n\n_________________________________________________________________________________________________________________\n\nDimensionality vs. Efficiency (Q & W): \n\nIn 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.\n\n_________________________________________________________________________________________________________________\n\nComparison with Binary Neural Networks (Q & W): \n\nIn 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:\n\n- 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.\n\n- 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.\n    \n- 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.\n\n_________________________________________________________________________________________________________________\n\nComputational Complexity (W):\n\nBecause 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."}, {"review_id": "K015li30hL", "reviewer": "Reviewer_dbXx", "summary": "This paper introduces G-Net, a novel approach for constructing high-accuracy random binary neural networks. The method is inspired by hyperdimensional computing (HDC) and aims to bridge the gap between traditional neural networks and randomized binary neural networks. The core idea is to train a \"floating-point\" G-Net in the real-valued domain and then convert it into an Embedded Hyperdimensional (EHD) G-Net, which operates on binary data, without requiring further training in the binary space. This conversion is theoretically justified by Grothendieck's identity and concentration of measure, ensuring that the EHD G-Net retains the accuracy of its floating-point counterpart. The paper provides theoretical consistency guarantees for both Gaussian and Rademacher embeddings and demonstrates strong empirical performance, significantly outperforming prior HDC models on benchmark datasets like MNIST and CIFAR-10, while rivaling real-valued CNNs.", "questions": "- Could the authors elaborate on the practical implications of the l2​-normalization and row-wise weight normalization constraints for real-world datasets that might not inherently adhere to these properties? Are there recommended preprocessing steps or training adjustments for such cases?\n- For practical deployment, when would a user prefer a RASU G-Net over a TASU G-Net?\n- Regarding the assumption $|w_i^T​x| \\geq l_{min} ​>0$ for TASU analysis (Theorem 4.2), how robust are the empirical results to violations of this assumption? Are there strategies to ensure this condition is met during training, or does it hold naturally in common scenarios?\n- The paper mentions that \"wide neural networks experience only minor changes in their weight distributions during training.\" Could the authors expand on how this property is leveraged or maintained to ensure the \"spread-out\" condition for applying Theorem 4.4 and Proposition 5.1?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n- The paper provides rigorous theoretical guarantees for the accuracy preservation during the conversion from G-Net to EHD G-Net, leveraging Grothendieck's identity and concentration of measure. This is a significant contribution, as many prior HDC works lack such deep theoretical underpinnings.\n- The concept of training in the real domain and then performing an \"inexpensive binary encoding\" to achieve high-accuracy binary networks without training in the high-dimensional, constrained binary space is highly innovative and practical.\n- The experimental results clearly show that G-Nets outperform existing HDC models by substantial margins (e.g., almost 30% higher accuracy on CIFAR-10 compared to prior HDC models). They also achieve accuracies comparable to real-valued convolutional neural networks, which is a major step forward for HDC.\n- The motivation from HDC for efficient hardware implementation and the exploration of Rademacher embeddings (which are simpler to generate and apply than Gaussian vectors) highlight the practical relevance and potential for deployment on edge and low-energy devices.\n- The paper is well-organized, with a clear introduction of concepts, theoretical results, and experimental validation. \n- The authors provide a link to their GitHub repository, which significantly aids reproducibility and allows for further research and application of their method.\n\nWeakness:\n- G-Nets require -normalization of inputs and row-wise normalization of weight matrices. While the authors argue these are advantageous, they might limit flexibility or require specific preprocessing steps not explicitly detailed for all scenarios.\n- The network consistency analysis (Section 4.1) focuses on the base ASU G-Net case and defers comprehensive treatment for TASU and RASU layers to an extended presentation. While understandable for brevity, it leaves a theoretical gap in the main paper for the more practically relevant RASU/TASU architectures.\n- The $\\sqrt{n/p}$​ discrepancy term in Rademacher embedding that doesn't vanish with increasing N is acknowledged, but its practical implications or strategies to mitigate it could be discussed further, especially given the claim that Rademacher embeddings achieve \"comparably close performance.\"", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n_________________________________________________________________________________________________________________\n\nImplications of the $\\ell2$-Normalization (Q & W):\n\nReferences [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.\n\nImportantly, $\\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.\n\n_________________________________________________________________________________________________________________\n\nRASU G-Net over a TASU G-Net (Q):\n\nAs 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.\n\n_________________________________________________________________________________________________________________\n\nAssumption $|w_i^T x| > l_{min} > 0$ for TASU analysis (Q):\n\nThis 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.\n\n_________________________________________________________________________________________________________________\n\nMinor Distribution Shift of Wide Neural Networks (Q):\n\nTo 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).\n\n_________________________________________________________________________________________________________________\n\nNetwork Consistency Analysis (W): \n\nWe 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.\n\n_________________________________________________________________________________________________________________\n\nThe $\\sqrt{n/p}$ Discrepancy (W): \n\nAs 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."}, {"review_id": "i6Zg1bLCrl", "reviewer": "Reviewer_XuMH", "summary": "This paper investigates a method for constructing highly accurate binary neural networks, motivated by hyper-dimensional computing (HDC). The key idea builds on the Grothendieck identity and random matrix theory, which imply that the composition of a linear transformation and the arcsin function can be approximately converted into a binary linear transformation by multiplying a large random Gaussian matrix to the continuous parameter and input vector. Based on this observation, the authors introduce G-Net, a (continuous) neural network with an activation involving the arcsin function. After training of G-Net, it can be converted into a binary neural network (EHD G-Net) by the above technique, enabling binary inference in an approximately lossless way. The experimental results show that the proposed method successfully constructs binary neural networks that outperform previous methods in HDC.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- (S1) The paper is written so clearly and easy to follow.\n- (S2) The paper demonstrates an excellent application of the Grothendieck identity and random matrix theory for binary neural networks. Although the continuous counterpart, G-Net, has a seemingly weird activation involving arcsin, they is easily learnable via backpropagation and SGD.\n- (S3) While the main motivation in this paper is HDC, the proposed method may have broader applications as a novel technique of lossless binarization for neural networks.\n\n**Weaknesses**\n\n- (W1) Even though the method is motivated by the potential application to efficient computing with HDC, the paper lacks an analysis of actual or idealized computational costs.\n  - Is the proposed approach truly efficient? For instance, one could trivially binarize a given DNN by viewing floating-point weights as bit sequences. How does the proposed method compare in terms of the number of parameters or computational costs against such naive binarization?\n- (W2) According to Definition 3.2, in each layer, the input vector should be binarized by multiplying random Gaussians as well as the parameter matrix. However, in Figure 2 (b), it appears that such binarization (called sign embedding or input embedding) is applied only in the first layer.\n  - I'm confused by this gap. If we employed the sign embedding only in the first layer following Figure 2 (b), the approximate consistency would be broken. Indeed, the proof of Theorem 4.3 recursively applies Theorem 4.1, and thus the sign embedding seems to be required in each intermediate layer.\n  - On the other hand, if we employ Definition 3.2 as is, I'm concerned that the sign embedding in intermediate layers may be incompatible with the HDC computation because it involves continuous operations in each layer.\n- (W3) The paper does not cite a lot of prior work in neural network binarization/quantization. Even if the main motivation is HDC, there are many such prior work having a similar purpose or related method to this paper, and thus should be appropriately discussed as related work.", "was_revised": true, "final_justification": "I would like to keep my score since my major concern on computational efficiency has not been addressed, especially:\n\n> the paper lacks an analysis of actual or idealized computational costs.", "rebuttal": "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.\n_________________________________________________________________________________________________________________\n\nComputational Efficiency (W1):\n\nOur 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.\n\n_________________________________________________________________________________________________________________\n\nFigure 2 Note on Layer-wise Embedding (W2):\n\nWe 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). \n\n_________________________________________________________________________________________________________________\n\nPrior Work on Binarization/Quantization (W3):\n \nThanks 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:\n\n- 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.\n\n- 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.\n    \n- 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.\n\nWe 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."}, {"review_id": "cZ87QKIHbC", "reviewer": "Reviewer_xoVW", "summary": "The paper focuses on hyperdimensional computing (HDC), where the data is first transformed to some very high dimensional binary vector, and then inference is performed via some simple linear method. This paper shows how a network of a specific (but still quite generic) form can be converted to binary (in some sense) network in the infinite limit and some convergence results are presented for finite widths. Experiments on some datasets, such as MNIST and CIFAR10 are presented. The central result of the paper is to train a floating point network and binarizing it later in a way nothing is lost (in the infinite limit; in finite width, we are losing something and the paper quantifies how much)\n\nThe main identity that is behind all the constructions is the Grothendieck identity (quantifying the probability for two vectors $u,v$ that they are on the same side of a hyperplane with normal vector $g$, $g$ is normally (or rademacher) distributed; the probability is some function of $<u,v>$ for unit vectors $u,v$). Then, by the law of large numbers, if we draw enough normal vectors $g_i$, we can recover $<u,v>$ from the binary indicators sign$(<g_i,u>)$. Then, one  can express the inner product $<u,v>$ between input and weight matrix using the inner product of the binary embedings (sign$(<g_i,u>)$ for i-th element of embedding of $u$) modulo some technicalities such as input normalization or non-linearity application.  This is then used for every layer sequentially.", "questions": "The network architecture used in the paper is a bit weird (chosen so that it can be binarized) and the experiments were presented only on small datasets. Can the method me scaled up to (say) Imagenet? CIFAR100? If not, what is the bottleneck? Does the training get challenging, or is it the binarization?", "limitations": "-", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The technique itself is neat and I like the rigorous quantification of the approximation error. I am not aware of the technique being used in a similar context, but my knowledge of the field is arguably limited.\n\nOn the other hand, there seem to be limited motivation. The goal of this paper is a bit vague. It presents a way  of constructing (binary, in some sense) networks with some goals in mind (efficient computation), but the evaluation solely focuses on accuracy on some datasets and it is not clear if this method should be preferred over standard CNN, because no concrete scenario where standard CNN is worse (or not applicable) is not presented.\n\nI personally did not understand the HDC link as descibed in the paper. Specially, this paper does not propose a method falling to that framework (as described in the paper) in a nontrivial sense; i.e., there is no high dimensional representation with a linear classifier. Instead, to me this work falls in the binary (resp. integer) network paradigm, where with suitable design choices in the paper, the internal representations/operations are integral. Thus, I am not convinced the baselines are chosen well.\n\nTo summarize, the paper is entertaining, presents an interesting technique, but I find it hard to conclude more from the paper, because the task considered in the paper is not well specified and I fail to see a concrete scenario where I would consider using this technique. I think the paper would benefit from proper task definition and subsequent comparison with other methods on the task.\n\n#### typo\nI think fig2 contains wrong variable names at places. Say in the embedded layer. First, we compute embedding $y = sign(Gx)$, then we should multiply this with $sign(GW)$ (cf. eq (3)), but the \"linear transform by embedded weights\" multiplies this weight thing by $x$ (and not by $y$. This seem to be a consistent typo in the figure, where $x$ is often used instead of $y$.", "was_revised": true, "final_justification": "I have read the response and I was not convinced by the answers so i keep my score.\n\nin general there is nothing really wrong with the paper but it does not reach the bar for me. If the rest of the reviewers and AC decide to accept the paper, I think it is fine.", "rebuttal": "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.\n\n_________________________________________________________________________________________________________________\n\n\nNetwork Architecture (Q):\n\nWe did not observe any bottlenecks due to our non-standard architecture that would cause issues when scaling to larger datasets. \n\nBecause 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.\n\nBeyond 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.\n\n\nSecond, 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.\n\n_________________________________________________________________________________________________________________\n\n\nLimited Motivation & Preference Over a Standard CNN (W):\n\nWe 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.\n\n_________________________________________________________________________________________________________________\n\n\nHDC Link (W):\n\nConsider 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.\n\nTo 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?\"\n\nThis 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.\n\nThe 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.  \n\n_________________________________________________________________________________________________________________\n\nProper Task Definition (W): \n\nRegarding 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). \n\n_________________________________________________________________________________________________________________\n\n\nVariable Names in Fig 2 (W):\n\nWe 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."}]

Author rebuttal:

Meta-review: This paper introduces G-Net, a novel method for constructing high-accuracy random binary neural networks. Three reviewers responded very positively, while one raised concerns about its potential use cases. The AC acknowledged these limitations but found the work interesting,  ultimately recommending acceptance at NeurIPS.
Decision: Accept (poster)