Error Correction Output Codes for Robust Neural Networks against Weight-errors: A Neural Tangent Kernel Point of View
Authors: Anlan Yu
Shusen Jing
Ning Lyu
Wujie Wen
Zhiyuan Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: error correction output codes
ECOC
DNN hardware accelerator
DNN robustness
Primary area: deep_learning_architectures

Abstract: Error correcting output code (ECOC) is a classic method that encodes binary classifiers to tackle the multi-class classification problem in decision trees and neural networks.
Among ECOCs, the one-hot code has become the default choice in modern deep neural networks (DNNs) due to its simplicity in decision making. However, it suffers from a significant limitation in its ability to achieve high robust accuracy, particularly in the presence of weight errors. While recent studies have experimentally demonstrated that the non-one-hot ECOCs with multi-bits error correction ability, could be a better solution, there is a notable absence of theoretical foundations that can elucidate the relationship between codeword design, weight-error magnitude, and network characteristics, so as to provide robustness guarantees. This work is positioned to bridge this gap through the lens of neural tangent kernel (NTK). We have two important theoretical findings: 1) In clean models (without weight errors), utilizing one-hot code and non-one-hot ECOC is akin to altering decoding metrics from $l_2$ distance to Mahalanobis distance. 2) In non-clean models (with weight errors), if the normalized distance exceeds a threshold, then non-clean DNNs can reach the clean model's accuracy as long as the code length approaches infinity. This threshold is determined by DNN architecture (e.g. layer number, activation), weight error magnitude, and the distance between the output and the nearest codeword. Based on these findings, we further demonstrate how to practically use them to identify optimal ECOCs for simple tasks (short-code ECOCs) and complex tasks (long-code ECOCs), by balancing the code orthogonality (as per finding 1) and code distance (as per finding 2). Extensive experimental results across four datasets and four DNN models validate the superior performance of constructed codes, guided by our findings, compared to existing ECOCs. To our best knowledge, this is the first work that provides theoretical explanations for the effectiveness of ECOCS and offers associated design guidance for optimal ECOCs specifically tailored to DNNs.

Error Correction Output Codes for Robust Neural Networks against Weight-errors: A Neural Tangent Kernel Point of View
Anlan Yu" Lehigh University
Shusen Jing' University of California, San Francisco shusen. wwnggnnsnn......mmmm edu
Ning Lyu Lehigh University ni ni14180lehigh. edu
any218@lehigh.co edu
Wujie Wen
Zhiyuan Yan Lehigh University zhy6@lehigh. edu
North Carolina State University
wwen20ncsu.edd
Abstract
Error correcting output code (ECOC) is a classic method that encodes binary classifiers tackle the multi-class classification problem in decision trees and neural networks. Among ECOCs, the one-hot code has become the default choice in modern deep neural networks (DNNs) due its simplicity in decision making. However, it suffers from significant limitation in its ability to achieve high robust accuracy, particularly in the presence of weight-errors. While recent studies have experimentally demonstrated that the non-one-hov ECOCs with multi-bits error correction ability, could be better solution, there is notable absence of theoretical foundations that can elucidate the relationship between codeword design, weight- error magnitude, and network characteristics, as to provide robustness guarantees. This work is positioned to bridge this gap through the lens of neural tangent kernel (NTK). We have two important theoretical findings: 1) clean models (without weight-errors), utilizing one-hot code and non-one-hot ECOC is akin to altering decoding metrics from distance to Mahalanobis distance. There exists a threshold, determined by the normalized distance among codewords, the DNN architecture, and the scale weight-errors, the distance between clean output (without weight-errong and its nearest codewords is smaller than this threshold, then the DNN can make predictions as it is free of weight-errors. Based on these findings, further demonstrate how to practically use them to identify optimal ECOCs for simple tasks (small number of classes) and complex tasks (large number of classes), by balancing the code orthogonality (as per finding 1) and code distance (as per finding 2). Extensive experimental results across four datasets and four DNN models validate the superior performance of constructed codes, guided by our findings, compared to existing ECOCs. To our best knowledge, this is the first work providing theoretical explanations for the effectiveness of ECOCs and offers associated design guidance for optimal ECOCs specifically tailored to DNNs.
Introduction
Inspired by error correction codes in wireless communication and memory system, егтоr correction output codes (ECOCs) proposed to improve the generalization performance of multi-class classification in decision trees by decomposing a complex problem into simpler binary classification
'Theee authors contributed equally to this work
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

tasks M. As deep neural networks (DNNs) are ever ever-increasingly popular in machine learning, one-hot code, as a special ECOC providing one bit protection, has been most widely adopted in the output layer of modern DNNs due to its simplicity in decision making and decent generalization performance. However, it experiences notable accuracy degradation in the presence of weight errors, such as those originating from hardware defects in non-volatile compute-in-meman memorr (NVCIM) DNN accelerators 3 71
A number of works has adopted general ECOCs (non-one-hot code) to improve DNN's robust accuracy against weight errors 8 T0 12). While these studies demonstrate that ECOCs with stronger error correction capability, can outperform one-hot codes to some extent through experiments, they often directly apply existing ECOCs to DNNs, with no explicit code design optimization tailored to modern DNNs. In this regard, there lacks a systematic theoretical study to answer the following key questions: 1) What is the mechanism behind ECOC's efficacy DNNs? 2) How effective can ECOC be? 3) How optimal ECOCs tailored for DNNs can be designed principally? ? To bridge this gap and provide insights to code construction, in this work, we overcome the challenges of characterizing the connection between the actual DNN performance and the application of ECOCs, and answer these questions rigorously based on novel theoretical proof. For the first question, the prevailing intuition in existing research, which suggests that enlarging the distance among codewords enhances robustness, is somewhat imprecise. In fact, we prove that the normalized distance (by the square root of the code length) among codewords is the crucial quantity in improving the DNNs' robustness. For the second question, we establish that there exists a threshold, determined by the normalized distance among codewords, DNN architecture, and the scale of weight-errors. If the distance between a clean output (in the absence of weight-errors) and its nearest codewords is smaller than this threshold, the DNN can make predictions as if it is free of weight-errors. For the third question, we analyze the overall performance of ECOCs by separating it into clean performance (in the absence of weight-errors) and performance degradation due weight-errors. We demonstrate that the clean performance is influenced by the correlation among ECOC codewords (code orthogonality), while robustness is determined by the normalized distance among the codewords (code distance). Thus, both aspects should be carefully considered during code construction.
Contributions: To this end, provide theoretical characterization of the efficacy of ECOCs on DNNs through the lens of the neural tangent kernel (NTK). Building on our theoretical insights, we propose two ECOC construction methods tailored to DNNs focusing on small tasks and complex tasks. Our contributions are summarized as follows:
In clean models (without weight errors), utilizing one-hot code and non-one-hot ECOC is akin to altering decoding metrics from l2 distance to Mahalanobis distance.
We prove that there exists a threshold, determined by the normalized distance among codewords, the DNN architecture, and the scale of weight-errors. If the distance between a clean output (in the absence of seight-errors) and its nearest codewords is smaller than this threshold, the DNN can make predictions as if it free of weight-errors.
Inspired by our theoretical results, we propose two ECOC construction methods optimizing the trade-off between codewords orthogonality and distance among codewords.
Extensive experimental results on four datasets and four DNN models show that our constructed codes, based on our findings, surpass the performance of existing ECOCs with up to 7%.
To the best of our knowledge, this is the first work providing theoretical explanations for the effectiveness of ECOCs and offers associated design guidance for optimal ECOCs specifically tailored to DNNs.
2 Related Works
Error Correction Output Codes Previous works have adopted ECOCs to improve the robustness of DNNs 8 I0 12 11. Gupta al. construct ECOCs by maximizing row-wise and column-wiss - Hamming distances together [12]. They particularly focus on short codes and weight- error free scenarios, instead of NN's robustness against weight-errors. Yu el al. propose DNN output error decorrelation framework to enhance performance of ECOCs [II]. Deng el al. apply ECOCs to DNNs to improve reliability and false rejection rate B.. Liu et al. adopt Hamming codes to improve the robustness of DNNs (9. Verma et al. claim that the robustness provided by ECOCs may stem from

---

sigmoid activation functions, which allows larger error margin than softmax [T]. Existing works are mostly empirical studies and fail address the theoretical foundation of ECOCs.
Neural Tangent Kernel
Jacot et al. propose the concept of neural tangent kernel. They prove that the learning dynamic of an -inntte-width DNN with proper initialization essentially dynamic of kernel ridge regression with defined neural tangent kernel [13] Lee et al. refine the results in [T3 and prove that infinite-widd DNNs evolve like linear model under gradient descent [14. Lee er
al. demonstrate that infinitely wide deep neural networks with specific types of initialization and
non-linear activation functions converge to Gaussian processes [15]. These works focus on learning dynamic of the DNN in NTK regime without considering weight-errors.
3 Preliminaries
3.1 Error Correction Output Codes (ECOCs)
ECOC is generalization of conventional one-hot codes with various code length and arbitrary binary entries. An ECOC is defined by an encoding function & : [C] - (1, -1) where C' is the number of classes, and [C] denotes the set [C] & {1,2, C}. Here nz the code length, which is equal to the dimension of the DNN's outputs. The encoding function essentially maps class label to a binary codeword. Let 'D denote the training data set with each entry as a pair (z, c), where z E R" and CE [C] are DNN inputs and the corresponding label, respectively; no is the input dimension of the DNN. Let f(;;; 0) RT + In be the DNN model parameterized with weights 0. The objective during the training process is to minimize the loss function
(()) A
Σ (*,0)ED
g(f(z;0),E(c))
(I)
D
where g(;,)) -) is referred to as sample loss. During the inference, the DNN outputs f(x;; mapped to classification decisions through the following decoding process
D( 0)) A arg min [I](=;;) - -((e)l cE(C]
(2)
where D(-) RKK - [C] is the decoding function. We can choose arbitrary metric in Eq. ( for decoding, but we mainly focus on the l2 norm this paper.
3.2 Neural Tangent Kernel (NTK)
NTK is tool for analyzing the learning dynamic and generalization of DNNs. It allows us to study DNNs reproducible kernel Hilbert space (RKHS) instead of intractable DNN weights space. We adopt a fully-connected feed-forware neural networks with L layers. At the (I + 1)-th layer, we have
hu+1 = w1+112 beF
(3)
T141 ((h+11)
for = 0,,,...., 2, where h141 E R and J4+ E "R= are the pre- and post-activation values at the (1 + 1)-th layer; w1+1 R and b1+1 R the weights and bias accordingly; ny is the width of the 1-th layer; o(.) is the activation function. In this case, no is the dimension of DNN inputs and nt is the dimension of DNN outputs (also the ECOC code length). With NTK parameterization, the entries of w1+1 and b are initialized with independent and identically distributed (i.i.d.) Gaussian random variables with A NO0 1 and A 1), respectively.
Let X' E | be the input set in D, where each column represents a sample of inputs, and let Y E R be the corresponding codewords, where each column represents the corresponding parameterize n, ain with some aj 0 and n 0, for 1 I L - 1, then training DNNs in the NTK regime minimizing MSE will result in the following [13 when hidden layer width parameter oc,
target. Without loss of generality,
DNN function according
f(x) = VKC(X X") -1((xx))))))))))))))))))))))))
where K. 1 1oe + IR is the NTK, K(X 12 X and K(X, [
3

---

Theoretical Results
In this section, we analyze the efficacy of ECOCs DNNs through the lens of NTK. To the best of our knowledge, this represents the first theoretical exploration of ECOCs' effectiveness on DNNs. Our findings summarized as follows:
We prove that adopting ECOC as a replacement of one-hot codes equivalent to changing the decoding metric from l2 distance to Mahalanobis distance.
We establish an upper bound for the perturbation of DNN outputs, suggesting that the normalized distance of code is a crucial factor determining the emror correction capability of ECOCs.
4.1 Assumptions
Assumption 1. The activation functions in the hidden layers are bounded at 0, i.e., @(0) oo, and they are Lipschitz continuous with parameter B, i.e., i.e. for any h and h', we have
lØ(h) - <(hh)))) S B h.".
(5)
Assumption 2. For any DNN imput xo. we have | /na
< 1. Assumption 3. The matrix K(X, RiPiXIDi is full-rank. Assumption 4. The initial gradient with respect to the DNN output is bounded, i.e, there exists constant Ro such that ||V 1/V5(x.8 ((xx,.)) < Ro-
Assumption Tholds for most of the common state-of-the-arr (SOTA) activation functions, such as ReLUU, sigmoid and tanh. Assumption @essentaally assumes a bounded norm all DNN inputs.
Without loss of generality, this assumption holds after input normalization. Assumption 3 holds almost surely for smooth kernel and continuous probability distribution of input samples. The
assumption here is used to avoid the corner cases of uninvertible K((,, X)). Assumption 4 should hold with high probability with proper choice of Ro due to random initialization.
4.2 Efficacy of ECOCs in Absence of Weight-errors
In this subsection, we discuss the behavior of DNNs after being trained with ECOC. Our first result based on eq. 4 proved in [3
Proposition 1. Let Assumption 7 and 4 hold. Suppose there is no weight-errors and hidden layer width parameter n - oc, then applying ECOC equivalent changing the decoding function of one-hot codes (with 0 and 1 entries) to the following
D(f(=)) = arg min cE(C)
llf(x) - - -ellletenneett
(6)
where E RC is the c-th one-hot codeword and || VIT Ar is referred as the Mahalanobis nomn with positive definite matrix A.
Remark 1. From Proposition | we observe that, in NTK regime, ECOCs affect the performance of DNNs through the correlation matrix E(CC))* E(CC) of the codewords when the DNNs are free of weight-errors. For both one-hot and ECOCs, their target spaces TR* are equipped with no-norm and the corresponding decoding metries. Proposition suggests that ECOCs generalize the decoding metric. Applying ECOCs is equivalent to equipping the target space of one-hot code with the Mahalanobis norm and the corresponding decoding metric.
A Although it remains unclear which correlation matrices yield the best performance for ECOCs in absence of weight-errors
know that codewords that approximately orthogonal generally perform comparably to one-hot codes. Consequently, it is reasonable to regularize the orthogonality of the codewards during the ECOC construction.
4.3 Efficacy of ECOCs on the Robustness of DNNs
has been reported in multiple works that ECOCs can improve the robustness of DNNs against weight-errors 8 However, these studies lack rigorous theoretical explanation of why DNNs become more robust after ECOC application. In this section, we provide theoretical guarantee on the error correction capability of ECOCs. We begin with the weight-error model.

---

4.3.1 Weight-error Model
We consider the weight-errors proportional to the weight scale. Considering the typically small initial values of neural network weights and the minimal changes from these initial values after training in the NTK regime [14], we assume that the noise terms are independent and identically distributed (i.i.d.) Gaussian variables with zero mean and variance o² //n.
4.3.2 Theoretical Guarantee for Robustness with ECOCs
We first show the bound of hidden layer outputs in absence of weight-errors, which will be used to prove other results.
Lemma (Hidden layer output bound). Let Assumptions 2 and 4 holld. Then, for any hidden layer < L 1 and any d > O,
|0all2 nn
1 B'
B+ (o(0))
+ B + (0)
+
1 1-B B
holds with probability least 1 5 when is large enough, where the hidden layer width au7 with constant aq > for all 1 S S
Based on the lemma, we show the perturbation bound in the following theorem. Theorem 1 (Perturbation bound). Let Assumptions 7 2
and 4 hold. Adopt the weight-error model in Sec. 4.3.7 and denote o² max; aqō² Let æ and I denote any clean output (in absence of
weight-errors) and its perturbed counterpart due to neight-errors, respectively. Then for arbitrary > 0 and arbitrary DNN inpul, we huve
1 - dLll2 S B, (o(0),,
(8)
VNL
with probability at least 1 - 5 - olni 1-
when n. and n are large enough, where
B (0())
v1+ V1+0="-1 VI+o2-1 + Ba 1+ 10(0)
(BV1+02)
E(a, B, ())
(9)
1-B
T-B BVI+02-1
Remark 2.
The theorem suggests that the normalized output perturbation |a2-āzllz can be bounded V
in terms of weight-erron error scale a, Lipschitz constant B. absolute activation funition value (o(0) and DNN depth L with high probability when hidden layer width n and code length n.z, are large enough. can be observed that: 1) The bound can be made arbitrarily small when o 0, suggesting that the bound is tight. 2) The bound can be made arbitrarily small when B = 0, which means the activation function & always outputs a constant regardless of its input. Obviously, in this situation, there will be no output perturbation, but training this DNN will be meaningless. 3) The DNN depth L on the exponents accounts for the error propagation due to the feed-forward architecture of the DNNs.
we present our main result in the following corollary to characterize the error correction capability of ECOCs.
Based on Theorem
Corollary 1 (Main result). Let all the conditions in Theorem Thold. Denote normalized (l2) distance of a codeword (() and normalized uncertainty of clean prediction given the clean output I as dist(E(i)) and UIL), respectively, with the following definition:
1 E())l U(æl) = min
di))(E(1)) = min
[|E()) xzLl2-
(10)
jifi
VnL
VnL
Then a DNN with ECOC can make prediction with æ as if it is free of weight errorrs after decoding, i.e. D(ā)) = D(L)) with probability arbitrarily close to 1, if the ECOC satisfies
dist(D(x1)) U(5I) 5(o, B, (0)), L.) + +
(11)
for arbitrary small 8 > 0 when n2 + CC.
Remark 3. In eq. 440 U(x1.) accounts for the distance between clean oulput v.s. and its closest
codewords, and E(o, B, (o(0)), L) accounts for the output perturbation due to weight-errors. Note that Corollary of weight-errors; however, does not guarantee that these predictions will be the ground -ruth labels. Even in the absence of wright- DNNs may still produce incorrect predictions due to the data and model generalization, which cannot be corrected by ECOCs.
7 specifies conditions under which predictions can be made as if the DNN is free
5

---

A geometric explanation of Corollary is given in Figure r The perturbed output ž, (red diamond) within the ball centered at clean output
dist(D(()))
(blue dot) with radius + according to Theorem [ If eq. (40) holds, then distance between ž and the codeword (TTL) (black dot at the bottom left), which is the decoding result of clean output z,, will be smaller than the distance from ī to any other codewords (black dot top right), mean that D(IL) ( after decoding.
dist(((s..)
Hisc GG)
v00))
2
5 ECOC Constructions
D(..) D(x)
Inspired by our theoretical results, in this section, we pro- pose two ECOC construction methods for small scale and large scale classification tasks, respectively.
Figure illustration for Corollary 1
5.1 Problem Formulation
The final performance ECOCs is determined by weight-error free performance and performance degradation on top of that due to weight-errors, which are discussed in Proposition [ [and Corollary 1. respectively. According to Proposition [] the weight-error free performance influenced by
the correlation matrices of ECOCs. Although the optimal correlation matrices remain unidentified, extensive experiments have verified that near orthogonal codewords are generally good. Therefore, we penalize the correlation of codewords during code construction. On the other hand, according to larger normalized distance of codes leads to better error correction capability of ECOCs, therefore encourage the distances of the codes during code construction. Let 2 {-1, , be the ECOC codebook, i.e., a horizontal stack of codeword, then we construct the code by solving the following optimization problem:
Corollary [
min 7E(-1.1)m6xc
12 - -bll +A
EZz B Σ |2
(12)
pair-wise distance
Note the second part of the objective penalizes the magnitude of off-diagonal elements while promoting the amplitude of diagonal elements in the correlation matrix zT Z.
5.2 Method 1: Direct Optimization
Before employing standard optimization algorithms,, is necessary to relax the feasible set from the discrete binary domain 1-1,1)mxxe to the continuous interval -1,, n To further eliminate these box constraints, we reparameterize Z with Z tanh(Z'), This allows the application of gradient descent to effectively solve the optimization problem. Finally, we take the sign of each elements in as the generated codebook.
5.3 Method Picking from Hadamard
Since the objective in eq. 12 is non-convex, Method 1 can be easily trapped in local optima, especially for ECOCs with large number classes C. For this reason, we introduce Method 2 in this section which constructs ECOCs top of Hadamard codes. Hadamard codes exhibit several beneficial properties: I) the number codewords equal to the code length, and both are powers of 2; 2) all codewords are orthogonal to each other; 3) the Hamming distance between any two codewords half of the code length. This property allows Hadamard codes to achieve the upper bound of the minimum Hamming distance of ECOCs given the code length. Hadamard code is an excellent choice for ECOCs, which has been validated in previous works [10] example of Hadamard code with code length 8 is given in Section A.2
[6]. An
In Method 2, we pick C codewords from Hadamard codes and their complementary codes. Without loss of generality, we decompose C into C. = 2a b. where and b are non-negative integers. Let

---

Hadamard
Method
Hadamard
Method
Hadamard
Method 2
(a) Geometric structure
(b) Correlation matrix
(c) Distance matrix
Figure A comparison between Hadamard codes and the codes constructed by Method 2. (a) Geometric structure: the codewords of Hadamard code are orthogonal to each other. In contrast, Method 2 allows one codeword to be located in the opposite direction from another. (b) Correlation matrix: correlation matrix for the codes constructed by Method 2 contain off-diagonal elements, indicating higher level of correlation compared to that of Hadamard codes. (c) Distance matrix: codewords of Hadamard codes have uniform Hamming distances, whereas Method 2 produces some codeword pairs with larger Hamming distances and others are equivalent to those found in Hadamard codes, where the colors black, grey, and white are values of 8, 4, and 0, respectively.
{1,, U2,,.., ... UH} be the Hadamard codewords, then the code constructed by Method 2 is given by
Us, for Si a Snick (i) Vi-a; for a < 2a
(13)
a,b
Ui-a: for 2a < <i< C.
In other words, its codebook Egick (IC1)) fui, ...,.., Va: - U1, U22 - Va+11 Pa+2, ... Va-b b.
We can observe that for a codeword E (1) = 2 with i S a, it is orthogonal to all other codewords except epick (i + a) = U; In addition, the Hamming distance between and other codewords half of the code length 2/ except epick
a,b (i + a), where the Hamming distance is nz. When codebook egick ([C])) (v1, u2,,.., vC)) composed of codewords from Hadamard code.
Figure 2aare2]pree provides more intuitive comparison between Hadamard codes and the codes constructed by Method Figure 2(a) illustrates the geometric structure of Hadamard codes and the codes constructed by Method 2 with C' = 3, 1. As previously mentioned, the codewords of Hadamard code are orthogonal to each other. In contrast, some pairs of codewords in Method 2 are located in the opposite direction from another. Figure compares the correlation matrices of Hadamard code with code length ny 8 and the code constructed by Method with observe that the correlation matrix of Method 2 contains off-diagonal elements, indicating higher level of correlation compared to that Hadamard codes. Figure 2(c) shows the distance matrices of Hadamard code and Method with C' = 8, 3. We observe that the codewords of Hadamard codes have uniform Hamming distances (the number of different entries), whereas the codewords constructed by Method 2 produces some codeword pairs with larger Hamming distances and others that are equivalentt to those found in Hadamard codes. Notice that, by adjusting a and we can achieve different trade-off between averaged codeword distance and correlations.
8, a 3. We
Experiments
6.1 Experimental Setup
We conducted all simulations using PyTTorch framework on workstation equipped with an AMD EPYC 7542 32-Core Processor and four NVIDIA RTX A6000 GPUs, each with 40GB of memory.
Datasets and models are used for evaluation. our experiments, MNIST and CIFAR10 represent small scale tasks, while CIFAR 100 [18] and Tiny ImageNet represent large scale tasks. We adopt a (784-4096-4096-1) multilayer perceptron (MLP), AlexNet, VGG16 and ResNet-50 for MNIST, CIFARIO, C1FAR100 and Tiny ImageNet, respectively.
MNIST [7]. CIFAR10 and CIFAR100 [88, and Tiny ImageNet [19 datasets

---

Benchmarks Our ECOCs are compared against one-hot codes, repetition codes, random codes, and Hadamard codes [TO. For a given number of classes, both the number of codewords and code length for one-hot codes are the same as the number of classes. We further derive repetition code from one-hot code: each codeword of a one-hot code is repeated for multiple times. Hence, the number of codewords in repetition code is the same as the number of classes, but its code length a multiple of the number of classes. The codewords of a random code is obtained by choosing random binary entries of -1 and I with equal probability. For small scale tasks such as MNIST and CIFARIO, 10, we compare codes constructed using Method to with benchmarks. For large scale tasks, Le., CIFARIO0 and Tiny ImageNet, codes constructed based on Method 2 are used for comparison.
Weight-errors Gaussian noises with different variance w² are added to the weights during infer- ences to test the robustness of the networks. For each code, except for random codes, the network is trained 20 times. After each training session, we perform 200 inference runs, each with different randomly generated weight-errors applied. For random codes, each training uses different randomly generated codes.
6.2 Results and Analysis
Superior performance of the proposed methods over existing ECOCs The performances of different ECOCs on small scale tasks (MNIST and CIFAR 10) and large scale tasks (CIFAR100 and Tiny ImageNet) are summarized in Tables I and 2 respectively. We made the following observations from Tables and 2 1) The clean accuracy (w = 0) of different codes are similar for small scale tasks in Table even with different code lengths. We believe this is partially due the simplicity of the tasks. Besides, these codes all have good orthogonality, therefore they have similar generalization performance according to Proposition T In contrast, the clean accuracy is more varied for large scale tasks in [ We believe this is because the assumption of infinitely wide DNN does not hold when the code length comparable the width of networks. In these cases, ECOCs with better structures can reduce more generalization error. 2) One-hot and repetition codes have much worse performance than other codes under large weight-errors. This is due to their smaller normalized distances. On the contrary, our proposed codes outperform other benchmarks under large weight- errors because of their larger normalized distances. 3) Larger code length nz yields better robustness under weight-errors since more protections are applied by the additional nodes. Besides, longer codes lead to higher success probability of bounds our theoretical results, making the proposed methods inspired by them more effective. 4) Interestingly, Hadamard and random codes perform similarly when the code length large. This is because the expectation of correlation matrices and pair-wise distances of
Table 1: Performance of different ECOCS with various code length (nz) on small scale tasks, i.e., MNIST and CIFAR10. The proposed method achieves better performance in the presence of weight- errors.
Onc-hoo
Repetition
Random
Hadamard
Method
10
20
16
16
16
98.44 1 0.05
98.45 1: 0.05
98.27 = 0.10
98.48 =: 0.04
98.51 1 0.05
0.03
88.67
0.75
89.60
0.62
87.27
2.81
93.54
0.18
93.43 1: 0.23
0.05
35.46
+ 1.26
46.39
0.88
45.59
= 4.53
60.49
= 0.86
58.35 + 0.94
0.08
11.61
0.46
17.39
0.28
19.65
1.42
23.65
23.31
0.36
0.1
10.80
+ 0.26
13.71 +: 0.34
14.94
= 0.58
16.59
= 0.25
16.48
1 0.33
MNIST
R1 130
R1
B1 128
11g
0
98,40 = 0.04
98.49
0.04
98.31
= 0.04
98.51
= 0.05
0.03
94.10 1 0.15
96.72 0.22
96.90
1 0.05
97.04 1. 0.06
0.05
58.43 - 0.69
80.78
2.53
83.52
84.33 + 0.72
0.08
24.54 = 0.41
38.34
2.05
40.27 = 0.89
42.47 + 0.59
17.59
24.44
0.39
10
20
16
16
16
82.88 = 0.20
82.50 = 0.28
81.56 = 0.24
82.08 = 0.30
82.08 + 0.33
0.01
78.83 1 0.13
78.92 1 0.16
80.41 0.23
81.09
0.25
81.18 1 0.23
0.02
60.40
+ 0.58
61.10 - 0.48
71.38 = 1.99
75.78
= 0.31
76.21
+ 0.31
11.15
13.93
32.52
45.66
0.04
10.00 1 0.19
10.01 1 0.04
14,47
1.39
17.43
0.25
19.58 1. 0.25
CIFARIO
R1 130
R1
128
128
ng = 128
82,59 = 021
82,14
= 0.28
82.30 = 0.20
82.30 + 0.29
0.01
80,90 - 0.17
81.14
= 0.19
81.27 = 0.13
81.28 + 0.24
0.02
72.70 0.29
76.58
0.23
76.82
0.17
77.15
1 0.24
0.03
41.30 - 0.75
$4.45 = 193
$7.23 = 0.50
59.52
1 0.65
16.61 0.26
21.08
0.92
22,92
24.52
8

---

Table 2: Performance of different ECOCs with various code length (nz)) on large scale tasks, i.e. CIFAR100 and Tiny ImageNet. The proposed method shows better performance among all.
One-hoe
Repetition
Random
Hadamard
Method
100
1100
1024
ar. 1024
n1. 1024
0
62.81 1 0.01
64.95 = 0.92
67.37 = 0.35
61.45 = 0.35
68.25 1: 0.22
0.008
3.72 0.01
29.83
58.73
60.41
0.27
0.01
1.56 1: 0.00
13.05
:: 3.65
49.08
1: 0.84
53.26
- 0.39
55.69 1: 0.54
0.012
1.05 0.00
4.78 1.53
30.64
1.57
38.87 0.95
44.49 + 1.07
0.013
1.00
0.00
3,07 + 0.92
19.75 = 1.66
28.63
1
36.13 = 1.41
CIFARIOO
TV. = 2100
0y = 2048
ar. = 2048
n. = 2018
0
66.50 0.46
67.9% 1 0.32
67.90 1 0.34
68.42 1 0.14
0.008
39.58 = 6.60
64.77
+ 0.23
65,26 = 0.25
65.79 + 0.12
0.01
21.53
62.39
63.47
0.012
4
58.51 + 0.32
60.74 = 0.25
61.38 + 0.20
0.013
5.10 2.00
55.00 0.46
58.82 = 0.27
$9.55 - 0.12
1 200
1200
VLg 1024
n2 1024
R. 1024
0
48.74 = 0.43
49.36 0.21
53.34 = 0.47
55.15 = 0.41
56.42 = 0.42
0.001
42.99
0.26
46.63 0.20
52.96
$2.92
56.24
0.003
13.41 + 0.45
26.24 = 0.28
50.28 + 0.27
51.04 = 0.43
54.53 + 0.31
0.005
2.29 : 0.07
6.46 0.06
44.19 0.18
46.87 0.45
50,69 + 0.29
0.008
0.55 0.02
0,92 0,02
25,91
0.48
34,02 0.64
38,17 + 0.43
Tiny ImageNet
B1 = 2200
T1 = 2048
R1 = 2048
R. = 2048
49.83 0.21
54.00 1 0.43
35.33 0.15
57.64 1 0.37
0.001
47.66 = 0.18
54.52 = 0.45
55.39 = 0.07
57.56 + 0.33
0.003
53.65
54.33
0.005
9.46 + 0.16
51.78 = 0.35
52.13 0.16
55.54 + 0.27
0.008
1.06 + 0.06
46.07 = 0.17
46.62 = 0.34
51.73 + 0.25
Table 3: Performance of Method and Method on CIFARIOO, CIFAR80, CIFAR40. CIFAR20, and CIFARIO. The datasets are constructed by taking the corresponding number classes from CIFARIO0. We choose VGG16 as the model and code length n, 1024 for all codes. Method I is better at small tasks, i.e., CIFARIO; while Method 2 is better at large tasks, i.e., CIFAR 20, 40, 60, 80 and 100.
0.008
0.01
0.012
0.013
Method
67.65 + 0.21
61.18 + 0,19
55.00 + 0.17
42.15 + 0.45
33,83 + 0.76
CIFAR100
Method
68.25 + 0.22
61.71
+ 0.27
55.69
+ 0.54
44.49 +
36.13 +
CIFARSO
Method
69.47 1. 0.13
63.19
1: 0.18
57.47
1 0.27
46.34 1: 0.68
38.08 1 0.83
Method 2
69.52 0.18
63.22
0.12
57.56
+: 0.25
46.56 +: 0.37
38.21 + 0.86
Method
1. 0.14
71.60
1 0.16
1.
58.50 1
CIFAR40
Method
76.01 + 0.29
71
0.23
68.33 + 0.28
63.17 + 0.41
59.57 + 0.63
Method
81.59 0.50
77.18 0.28
73.69 + 0.29
67.72 + 0.46
63.34 + 0.74
CIFAR20
Method
+
77.53
+
Method
0.33
84.61 + 0.24
80.90 + 0.44
72.74 + 1.20
66.35 = 1.93
CIFARIO
Method 2
88.38 0.21
84.67 + 0.33
80.85 + 0.54
72.54 + 1.12
66.19 + 1.27
codeword in random codes are exactly same to those of Hadamard codes. When the code length is larger, the randomness of these quantities concentrate due to the law of large number.
Performance comparison between Method and Method Recall that Method and Method are proposed for small scale and large scale tasks, respectively. Here, we compare the performance of Method 1 and Method 2 on tasks with different number of classes, which is summarized Table 3 For small scale task, i.e., CIFAR10, Method 1 outperforms Method 2. However, for larger tasks with more classes, i.c., CIFAR20- 100, Method 2 outperforms Method 1. As mentioned previously, we believe this is because Method 1 is more likely to be trapped in bad local minima in large scale tasks than small scale tasks. Additional experiments and analysis can be found in Section A.3
7 Conclusion
In this paper, we provide theoretical explanations for the efficacy of ECOCs. We showed that using ECOCs to replace one-hot code equivalent to changing the decoding metric from la norm a Mahalanobis norm corresponding to the correlation matrix of the codewords. Moreover, we provided an NN output perturbation bound, implying that the quantity normalized distance of codes the key factor of the robustness of DNN with ECOCs. Based on the theoretical findings, we proposed two code construction methods for small and large scale classification tasks. Experimental results show that our proposed methods perform better than cxisting ECOCs.

---

Acknowledgments and Disclosure of Funding
This work is partially supported by the National Science Foundation (NSF) under Grants No. 2349538 and No. 2401544.
References
[1] Thomas G Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of artificial intelligence research, 2:263-288 286, 1994.
[2] Guanpeng Li, Siva Kumar Sastry Hari, Michael Sullivan, Timothy Tsai, Karthik Pattabiraman, Joel Emer, and Stephen Keckler. Understanding error propagation in deep learning neural network (dnn) accelerators and applications. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. pages 1-12, 2017.
[3] Xiaofan Zhang, Junsong Wang. Chao Zhu, Yonghua Lin, Jinjun Xiong, Wen-mei Hwu, and Deming Chen. Drnbuilder: An automated tool for building high-performance dan hardware accelerators for fpgas. In 2018 TEEE/ACM International Conference Computer-Aided Design (ICCAD), pages 1-8. IEEE, 2018.
[4] Yun Long, Xueyuan She, and Saibal Mukhopadhyay. Design of reliable dnn accelerator with un-reliable reram. 20/9 Design, Automation Test in Europe Conference Exhibition (DATE), pages 1769-1774. IEEE, 2019.
[5] Sparsh Mittal, A survey on modeling and improving reliability of dnn algorithms and accelerators. Journal of Systems Architecture, 104:101689 2020.
[6] Younis Ibrahim. Haibin Wang, Junyang Liu, Jinghe Wei, Li Chen, Paolo Rech, Khalid Adam, and Gang Guo. Soft errors in dan accelerators: A comprehensive review. Microelectronies Reliability, 115: 133969, 2020.
[7] Saurabh Dash, Yandong Luo, Anni Lu, Shimeng Yu, and Saihal Mukhopadhyay. Robust processing-in- memory with multibit reram using hessian-driven mixed-precision computation. IEEF Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(4):1006-100 2021.
[8] Huiqun Deng. George Stathopoulos, and Ching Y Suen. Applying crror-correctigg output coding enhance convolutional neural network target detection and pattern recognition. 2010 20th International Conference on Pattern Recognition, pages 4291-4299 IEEE, 2010.
[9] Tao Liu and Wujie Wen. Making the fault-tolerance of emerging neural network accelerators scalable. In 2019 JEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1-5. IEEE, 2019.
[10] Gunjan Verma Ananthram Swami. Error correcting output codes improve probability estimation and adversarial robustness of deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[11] Anlan Yu, Ning Lyu, Jieming Yin, Zhiyuan Yan, and Wujie Wen. COLA: Orchestrating error coding and learning for robust neural network inference against hardware defects. In Proceedings of the 40th International Conference Machine Learning, volume 202, pages 40277-40289 PMLR, 23-29 Jul 2023.
[12] Samarth Gupta and Saurabh Amin. Scalable design of error-correcting output codes using discrete optimization with graph coloring. Advances Neural Information Processing Systems. 35:10094- 10107, 2022.
[13] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[14] Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha fohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
[15] Jaehoon Lee. Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sick-Dickstein. Deep neural networks gaussian processes. arXiv preprint arXiv:1711.00165, 2017.
[16] Yang Song, Qiyu Kang, Wee Peng Tay, and Y Tay. Enror-orrecting output codes with ensemble diversity for robust learning in neural networks. In AAAI, pages 9722-9729, 2021.
[17] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/, 1998.
10

---

[18] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[19] Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3:211-252. 2015.
A Supplementary Material
A.1 Proofs for Theoretical Results
We start with a results in 14. which will be used our proof.
Theorem 2 (Theorem G.1 in [4] ). Let Assumptions
and The satisfied. For any given 6 >> 0, there exist and tyu such that for all n' and any step employing gradient descent with
constants n'
a learning rate of 7 1o ensures that
ARa vn
100 0oll2 1
(14)
with probubility least 8.
A.1.1 Proofs of Proposition
Proposition 1. Let Assumption
3 Hand@hooddd Suppose there is weight-errors and hidden layer width
paraneter n + 0o, then applying ECOC equivalent changing the decoding function of one-hot codes (with and entries) to the following
D(f(z)) = arg min llf(z) - -cale(cc)
(15)
cE[C]
where e, R is the c-th one-hot codeword and & the ECOC encoding function.
Proof. Let y denote the target encoded by the one-hot code. Notice that E(c) = 8(CC)),, then the ECOC larget can written as y E(CI)) The decoding process can be described
D(f(=)) arg min .E(C] [[E(c) VK 10xC-'(x,,00 (),X,)
arg min
[((CT])c E((C))DIC (X,, XX)XX
(16)
|cc (xx-5x((xxx))x11 (x,,, | eccon=eee
min cE
A.1.2 Proofs of Lemma
Lemma 1 (Hidden layer output bound). Ler Assumptions 7 and hold. Then, for any hidden layer I L and any 8
|ealll
1- 1--1-B (1-
<
B 10(1)(0)
B'
B [6(0)
B +
(17)
VTLL
holds with probability at least 1 - when n is large enough, where the hidden later width ogn with constant ffror all I.
Proof. Consider Wons and bini, I the initial weights and bias of the I-th layer, respectively. Define m and en as the adjustments to the weights and bias of the 1-th layer due training, respectively, meaning wn = Wontd + an and by bins,1 + uy. From eq. (3) we get
h
(Wsmett + u1)x-11 + bens.t +
(18)
Win bine, + uEre- +
Applying the triangle inequality, we obtain
|| ll2 < [[ + bensitll + || wxlla-
(19)
Recall that the entries of Wois and brss. follow (o, 1/nx-1) and (O 1). respectively, the elements of [W1- 1 + bins.t) independently and identically distributed Gaussian with zero mean and variance

---

(12--111//1 / + 1). The square of each element follows x² distribution with mean (11=)- /n- + 1)
and variance 2(112=1112 /m--1 + 1). Leveraging Chebyshev's 's inequality, for any 81 >> 0,
[ + bims,ell2
|10- 2 + +1+85
| V
1 + 6
(20)
vnu
RM-1
with a probability of at least 20|
alla/ar
1+1)
For the second term.
mi6s
|13/11 + villa
lulll |
|olll V
+
TTu
V
Val-1
|/eelle pp ||11-1122
van-1 ||ulll
Vai
Ai-1
Vai v ARo vau-i 1
(21)
ARa
var-1
|| Voi
vn
V
vn vai v
ARa
var- ||22-1112 +1
Vax
VIH-T
where the second incquality uses Theorem 2 and the definition of on n/nn. Acknowledging Assumption which posits (o(h)
x(0)] & Blh], and combining eq. (19) with eqs.
20 and (1.. we have
| 74
| hlll2 |o(0)
m
(22)
ARo vau-1
1a1-1ll2 M1-1
BAR vai-1
$
1+
+ B
+ B8, + |o(0))
vn
Voi
Vn Vou
v n
(1)))+))
with a probability of at least
With sufficiently large n, have
|
|| Vn-1
+ (B (0))
(23)
Viu
with probability least 8 and large enough. After recursion, have
aalll Vmu
|s0l
+ (B + (0()) 1 B'
<
Bd
5
Vno
B
(24)
B²
B' + (B [o()))
+
1
with probability least 8' and large enough, where the last inequality uses Assumption
2
A.1.3 Proofs of Theorem 1
Theorem (Perturbation bound), Let Assumptions 7 2 and A Adopt the weight- model in Sec. 4.3.1 and denote o² maxi and². Let x and ā. denote the clean output (in absence of weight-errors) and perturbed output due to weight-ernors, respectively. Then for arbitrary 5 > O and arbitrary DNN input, we have
| E2ll2 < E(aa, B, (o(1)) L) +
(25)
VnL
with probability at least 1 8 o(1 when vu and are large enough, where
E(a, B, [[(0) =)=
VI+02-1 (1
B+16(01
v1+02*-1
Bo
+ 100) (BVI+o")--1 "-1
(26)
1-B
B B
Proof. Let 1 and b denote the noisy weights and bias the (1 1)-th layer, respectively, with the noise variances being ow/nm /n for the weights and or for the bias. Consequently, the I + layer, the relationships can be represented as:
hht1 = .t b+t1,
(27)
8441 = @h141)).
Analyzing the preactivation term further, we obtain:
hu+1 = (wi+1 + Am + An) + (b++1 + Ab411
h1-1 Awrf1 + (W1+1 + A A2 + Ab141
(28)
h1-1 Aw1+1 (WoLA41 + Aw Az) u41 Ari + Ab
12

---

where 1 represents the initial weights at the (1 + 1)-th layer. characterized by variance of 1 1/ru, and 4441 is the adjustment of weights result of the training process. The prefix A denotes the perturbation of corresponding variable due to the weight noise. Utilizing the triangle inequality, we deduce:
Ju41 hu+1 ll. | + [1( + Awr4 Amill) |1u411millz + 1|Ab++11l2
(29)
Recalling that the weight perturbation Att+1 has zero mean and a variance of 0²/ni for S I. 2. Similar to eq. 220,, Chebyshev's incquality gives
||5r|l2 + 61
S
(30)
Vi4+1
vin
for any 6, > 0, with the probability at least 1
20 [
< 1 - o(n -r
11
Similarly, for the perturbed weights combined with the perturbed inputs, we obtain:
[[Wani,t+1 + Aww+))mmll
v 0² Am ll
+ 82
(31)
v
20 21444)1 For the bias perturbation, "y
for any 52 > 0, with a corresponding probability of at least we have
|| Abtttll2
<o 83
(32)
Viii
for any ōs > with the probability at least 1
20
1 1- 1 16 According Theorem for arbitrary
8g > 0, we have |uu+ille S A AR 1/2 with probability at least - 54 and n large enough, which results in
|1141 Amill 1u Axill2
ARo
V
ARo
Voi
||
(33)
vni+i
Vo++i
Vn
VTi
Vn
/au+1
VTH
Note that this term can be arbitrarily small when n large enough. Combine eq. we have
and
Azutill
B
vm++1
Vni+1
σ |1vill
v1+0= 1 +o Sr
B
Vni
Vni
(34)
1 B²
VI+02 AAmll
B
B' (B (b()))
B +
+o
+ 51
Vni
AAmll V/u
(1- B + (1-B+ 1-B
[o(0)]
Bo + |o{0)]
B 1 + σ²
B'+1
+
1 B
with probability at least 1 6t for n large enough, where the first inequality uses Assumption
2 and the second
incquality uses Lemma T Reuse eq. 334 for multiple times, we have for I S L --1
|azill2 Vni
< (BVI+02)
|| llz + (1-
B + (o(0))
(BVI+O7) B'
nno
1-B
+ Bo
1 + |b(0))
B (BVI+02)
Σ
B BBVI+ +
5n-1
1- B
1m
(35)
oB'
(1 1- 1-
16(0))
Σ (VI+o2)
Bo 1+ ++)(
Σ 1
1-1
(BVI+02)
+.6%
B
(1- B + 10(0))
VI+ -1 V1+ + Bo
1+ [6(0) (BV1+ + 0²)
= cB'
BVI o² -1 + 8
1 1-
1-B
B
with prohability at least 1 - 8/ when n is large enough, where the second inequality uses the fact and that 5, can he arbitrarily small for all when n is large enough.
| = 0.
We take care of the final layer specially due to the finite dimension. Specifically, we first rewrite eq.
33 as
||u2 ATLL-1ll <
ARo VVL-1 ||TL-Ill
A ARovaz-1 |1
(36)
VOL
Vn
VNL
ML-1
VnL
/ VL-
13

---

According to eq. 34
we have
A
a 1
vI+ AATL-
ARayav aL-i
ATL
-
i1l2
to 82
(37)
nrr.
V
vnr.
vng-i
arbitrary 8
with probability at least 8% large enouch. Note that probability bound eq. we finally have
30
32
and (33) all have order o 8 ). Plug in eq. (35) and use Lemmal
| VRL
A ARayaL-
+1)
OBL (1
VI+ B -+1001
-1
VNL
1-
v1+
(38)
+ 10(0) (BVT+ -1
Bo
1-B BVI+o3-1 +
with probability at least - 8 - o0ni'8 8-1) when is large enough.
A.1.4 Proofs of Corollary
1
Corollary (Main result), Let all conditions Theorem Soreemm@holle hold. Denote normalized (la) distance of codeword E(i) and normalized uncertainty of clean prediction given the clean output ur, as (Es)(E(i)) and U(L)), respectively, with the following definition:
1 VTL
dist(E(())
min 3:5
|E(1)) - EiI122 U(ZL) = min
[[(())
22
(39)
Then DNN with ECOC make prediction with 3t, it is free of weight-errors after decoding, i.e.. D(āL)= D(LL) with probability arbitrarily close to the ECOC satisfies
(D<LL)( Uxx2) + B, ())
(40)
2
for arbitrary small 8 0 when nL
Proof. Our goal is prove that for any codeword E(i) D(z1.), the distance which suggests that æz. is mapped to D(xr) instead of any other codewords after decoding. By triangle inequality, we have
|| - [ -0())
[. D(ax)ll | =xll2 + U(r)) ()) VTL
dist(D(EL))
(41)
VnL
2
where the second and the third inequality eq.
B and 40 respectively. Given the definition of dist (iss)D((r.)).
have [[(()) D(ae))la 2 dist((D(x By triangle inequality again, have
(E()) &1ll2
(E(1)
D(x1)ll
|+ - D(r ll
dist(D(xL))
(42)
VTL
Vng
where the second inequality uses eq.
Comparing eqs.
41 and
42
we complete the proof.
A.2 Hadamard Codes
Hadamard codes exhibit several beneficial properties: 1) the number of codewords is equal to the code length, and both are powers of 2; all codewords orthogonal to each other; 3) the Hamming distance between any two codewords half the minimum Hamming distance given the code length. Hadamard code is an excellent choice for ECOC, which has been validated in previous works
length. This property allows Hadamard codes achieve upper bound for
12] An example of Hadamard code with code length 8 is as follows:
-1
-1
1
-1
-1
-1
-1
-1
Hg
(43)
-1
-1
1
-1
14

---

Table 4: Performance of codes constructed by Method and Method on AlexNet CIFARIO. n 1024 for both codes.
Method 82.34 1 0.23
81.33 1 0.18
77.54
0.21
65.63 1 0.60
34.89 1: 0.88 63.53 4: 0.62
Method 2
82.00 +: 0.28
81.01 + 0.19
76.71 = 0.25
34.71 = 0.75
Accuracy [90
40
35
30
25
0.01 0.012
0.013
20
10
30
40
50
Number complement pairs
Figure 3: Accuracy comparisons for different number of complement pairs included when construct- ing ECOC with Method 2. Including more complement pairs means higher average distance while larger correlation. complement pair is Hadamard code. this plot, 40 complement pairs achieve the best trade-off between distance and correlation. The dataset, model and code length are CIFARI00, VGG-16 and 1024.
A.3 Additional Experiments
Performance comparison between Method 1 and Method Additionally, compare the perfor- mance ECOC constructed by Method and Method 2 on small scale task with small scale DNN, i.e., AlexNet CIFARIO. Similarly, as shown in Table [ Method outperforms Method 2, which emphasizes the benefit of using Method I on small scale tasks.
Performance comparison with correlation and distance tradc-off In Section we claimed that correlation of code matrices determines the weight-error free performance of ECOC and distance of codewords Method 2 an example show such
determines the performance degradation from weight-error. Here trade-off. shown in Figure 3 we vary the number of complement pairs a ECOC constructed by Method and compare the performance. Larger a means larger correlation while larger distance. In this set of experiments, 40 achieves the best correlation and distance trade-off.
A.4 Limitation
In this paper, experimental results are from simulation without implementation on actual hardware accelerator: The theoretical results adopt assumptions of NTK, which requires the width of the network to approach to infinity. This assumption can be strong for some neural networks.
15

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics. and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow references and precede the (optional) supplemental material, The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant
information is Not Available.
Please provide a short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked "[Yes] is generally preferable to "[No] ". is perfectly acceptable to answer "[No] provided a proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset used"). In general, answering "[No] oo "[NA] is not phrased in binary way. acknowledge that the answer
the checklist as of the factors in their evaluation. While
grounds for rejection. While the questions often more nuanced, so please just use your best judgment and write a justification elaborate. evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
supporting
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main theoretical results and proposed ECOC construction methods clearly summarized in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 he expected to generalize other setrings.
It is fine to include aspirational goals motivation long it is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Section A.4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
16

---

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 seel-sppeiiiiaatinn. asympiotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a 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 or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because 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 be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to penalize honesty concerning limitations.
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]
Justification:
We provide the full set of assumptions and complete proof in Section 2 and Scction
A.
Guidelines:
The answer NA means that the paper does not include thcoretical 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 thcorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide a short proof sketch to 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 experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Implementation details can be found in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless 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 novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 a large language model), releasing of model checkpoint, or other means that appropriate to the research performed.
17

---

While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. . a large language model), then there should either be a way to access this model for reproducing the results a way to reproduce the model (e.g.. with open-source datasct instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of booed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other rescarchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does paper provide open access to the data code. with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Code submitted a zip file.
Guidelines:
The answer means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines battpa://nips.cc/pubte Setee/CooSSuumisssiii
for more details.
While we encourage the release of code and data, we understand that this might not be possihle,
so "No" an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g.. for a 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 lattpa://nipe http:///nip.ccccpplllee cc/public/ htteee//oodSutmiisssoooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparamcters, how they were chosen, type of optimizer. etc.) necessary to understand results?
Answer: [Yes]
Justification: All the details are provided in Section and the code submitted.
Guidelincs:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [Yes]
Justification: All the experimental results provide error bars shown in Table Table and Table
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The authors should answer "Yes" if the results are accompanied by enoor bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims the paper.
factors variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions madc should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is report I-sigma error bars, one should it. The authors should preferably report a 2-sigma error than state they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric enror bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, docs the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
CPU and GPU types are provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide amount compute required each the individual experimental runs as well as 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 I 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
Answer:
[Yes]
Justification:
This research does not violate any of NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
authors should make sure preserve anonymity (e.g.. if there special consideration 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 the work performed?
Answer: [NA]
Justification: The paper aims to improve the robustness of DNNs, which does not have more potential societal impact than the original DNN does.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance). fairness considerations (e.g., deploy- ment lechnologies that could make decisions that unfairly impact specific groups), privacy considcrations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it not needed point out that generic algorithm for optimizing neural networks could enable people 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible relcase of data or models that have a high risk for misuse (e.g. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not have such 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 allow for controlled use of model, for example by requiring users adhere to 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 we 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 (e.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:
The corresponding papers, which published the datasets used in this paper, are cited in
Section
Guidelines:
The answer NA mcans that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset is used and, possible, include a URL..
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should he provided. For popular datasets, papprsswi thcode. com/ datasetaatetaaaaaaaaaa has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
this information not available online, the authors are encouraged reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
20

---

Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/codc/model as part of their sub- missions via structured templates. This includes details about training, license, limitations,
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
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 contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, other lahor should be paid at least minimum wage country data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does paper describe potential risks incurred by study participants, whether such risks were disclosed to 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?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review,
21


Reviews:
[{"review_id": "hWVpuVE25C", "reviewer": "Reviewer_Nfve", "summary": "This paper studies  theoretical foundations of Error correcting output code for multi-class classification by means of coding theory  and NTK.  NTK is employed to  alter the decoding metric from  l2 to Mahalanobis norm and  based on that a few  code construction methods are proposed.", "questions": "-What is the reason  you present your work in the context of NTK?  I see that you make a  connection between ECOC  and NTK because both are in the infinite width regime. However you don't use NTK to analyze the training dynamics of the  networks. \n\n- Given the sensitivity of your analysis  to width of the  networks, I expected some  figures demonstrating the  effect of increasing number of neurons on performance. Could you provide such a result to  show in what regime your codes are optimal?", "limitations": "NTK theory in general holds in the infinite width limit. Further discussions are  needed to adapt the methods in this paper to finite regime. For instance empirical NTK is developed in the literature to address the finite width regime.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The NTK  sees the model as an  Gaussian process, making it a  powerful tool for analysis of neural networks’ convergence and generalization. This paper  derives an interesting connection between decoding function in the infinite width regime  and NTK  formulation of Neural networks. The  derivation of bounds are  clear and  the codes are  tested  on different  tasks and datasets which is promising.", "weaknesses": "The presentation of the paper  could be further improved. Please consider the following:\n- All parameters need to be defined in the main text. In  (6),  E([C])   and in (8)  $\\bar{\\delta}$ are not defined.\n-There are sporadic grammatical errors such as \n\"... then training DNNs in the NTK regime minimizing MSE will result ....\"\n\"... adopt a fully-connected feed-forward neural networks with L layers...\"\n\"... can reduce more generalization error....\"\n\"...each training uses a different randomly generated codes...\"\n\n- in eq (20), <= should be = .\n\n\n-I see in the NTK papers a regularized form of  (4) as  $(K(x,x)+\\lambda I)^{-1}$, therefore no need to   make assumption 3. \n-NTK is merely used in the  proof of theorem 1 and is not the main  topic  of this paper.  I feel it is overemphasized in the title of the paper. please consider choosing a better title.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for taking your time to review and support our work. We appreciate your constructive feedback and provide our responses below: \n\n### **Response to weakness 1**\n**Q1). All parameters need to be defined in the main text. In (6), $\\mathcal{E}([C])$ and in (8) $\\bar{\\sigma}$\n are not defined. -There are sporadic grammatical errors such as \"... then training DNNs in the NTK regime minimizing MSE will result ....\" \"... adopt a fully-connected feed-forward neural networks with $L$ layers...\" \"... can reduce more generalization error....\" \"...each training uses a different randomly generated codes...\"**\n\n**In eq (20), <= should be = .**\n\nA1) We apologize for the typos, grammar errors and missed definitions. We will fix all these issues. \n\nIn Eq. (6), $\\mathcal{E}([C])$ is an $n_L$-by-$C$ code matrix, where each column is a codeword $\\mathcal{E}(i)$ for $1 \\leq i \\leq C$. In Eq. (8), $\\bar{\\sigma}$ is defined in Sec. 4.3.1 (weight-error model): we add noise with variance $\\bar{\\sigma}^2/n$ to the weights, where $n$ is a luxury variable defining the network width as specified in Sec. 3.2. Specifically, the $l$-th layer has a width of $\\alpha_l n$ with a constant $\\alpha_l$. The reasons behind this model are as follows: 1). On hardware devices, the noise is proportional to the scale of the weights. (The signal-to-noise ratio (SNR) matters.) 2). In NTK regime, the weights after training is of order $1/\\sqrt{n}$ at the same scale of its initialization. \n\nFor Eq. (20), we believe it should be $\\leq$ because of Chebyshev’s inequality. Notice that in the proof, we only claim $n$ is large enough instead of approaching infinity. If $n$ approaches infinity, the first $\\leq$ should be $=$ as suggested.\n\n### **Response to weakness 2**\n**Q2). I see in the NTK papers a regularized form of (4) as $(\\mathcal{K}(\\mathcal{X},\\mathcal{X})+I)^{-1}$, therefore no need to make assumption 3. -NTK is merely used in the proof of theorem 1 and is not the main topic of this paper. I feel it is overemphasized in the title of the paper. please consider choosing a better topic.**\n\nA2) We appreciate your valuable suggestions. First, we agree that Assumption 3 can be removed if $l_2$ regularization of the weights is applied during model training. Second, regarding the title, since the focus of this manuscript is to establish the foundation of ECOC design within the context of neural networks, with the NTK being used as a tool to analyze the behavior of neural networks trained with ECOC, we could modify the title as \"On the Efficacy of Error Correction Output Codes for Robust Neural Networks Against Weight-Errors” per your suggestion if the conference rule allows.\n\n### **Response to Questions**\n**Q3). What is the reason you present your work in the context of NTK? I see that you make a connection between ECOC and NTK because both are in the infinite width regime. However you don't use NTK to analyze the training dynamics of the networks.**\n\nA3). The reason we present the work in the context of NTK is as follows: Existing research on ECOC's applicability to modern deep neural networks (DNNs) mainly focuses on directly adopting well-known error correction codewords from the communication domain. It does not consider the unique information processing of DNNs, leading to suboptimal results. In our work, we want to provide guidance on ECOC design dedicated to DNNs through analyzing how DNNs behave after being trained with different codes. However, it is nontrivial given NN weight space is usually too complicated to analyze, we therefore leverage the NTK model to make the problem more tractable for the first time. In this regard, our focus is not on the dynamics of NTK itself, but rather on the consequences of training NNs (with ECOC) within the NTK regime.\n\nMore specifically, our work relates to NTK from the following aspects: \n1) In Proposition 1 (without weight-errors), we use the expression of NNs resulting from kernel-ridge regression (the dynamic of NTK).\n2) Theorem 1 relies on the assumptions and intermediate results within the NTK regime. \n\n\n\n**Q4). Given the sensitivity of your analysis to width of the networks, I expected some figures demonstrating the effect of increasing number of neurons on performance. Could you provide such a result to show in what regime your codes are optimal?**\n\nA4) We added the experiment results on MNIST dataset with a 2-hidden layer MLP where the width of the layers is 512, 1024, 2048, or 4096. We construct the code using Method 1 with code length 128. The results are presented as follows:\n\n| width \\ noise scale | 0 | 0.03 | 0.05 | 0.08 | 0.1 |\n| ----- | :------: | :-----: | :------: | :------: | :------: |\n| 512 | 98.43 | 89.75 | 59.82 | 26.86 | 18.67 |\n| 1024 | 98.48 | 93.23 | 66.52 | 28.80 | 19.37 |\n| 2048 | 98.50 | 95.48 | 73.40 | 32.30 | 20.99 |\n| 4096 | 98.51 | 97.04 | 84.33 | 42.47 | 26.54 |\n\nFrom the table we can observe that the robustness of NNs is improved when the network width $n$ becomes larger. This is because the success rate of the bound derived in the manuscript increases as $n$ becomes larger.\n\n### **Response to limitations**\nIn this work, only proposition 1 is based on the infinite width assumption. Both Theorem 1 and Corollary 1 assume $n$ is large enough instead of infinity (Our statement involves slack variable $\\delta$ in the bound and the bound success rate in the form of ($1-...$)). We thank the reviewer for pointing out the empirical NTK. We leave refining the proposition 1 to the finite width version in future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XudXjHFOMb", "reviewer": "Reviewer_Vn9W", "summary": "The paper deals with the use of error-correcting output codes (ECOCs) for multi-class classification problem. The standard solution is to use one-hot code. Existing literature shows that there are codes which are better than one-hot code. At the same time there is a lack of theory and explanations of this phenomenon. The current paper aim to fill this gap and provide theoretical results which help to choose proper ECOC as well as provide guarantees. The authors utilize neural tangent kernel (NTK) approach for theoretical analysis.", "questions": "See Weaknesses", "limitations": "In my opinion, the limitation section should be increased, please discuss the limitations of your method rather that «hardware acceleration».", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors provide the results of theoretical analysis - this definitely the strong aspect of the paper. In particular, the main results are as follows:\n- the authors showed that replacing one-hot code with other ECOC is equivalent to the change of decoding metric from Euclidean distance to Mahalanobis distance. \n- the authors established an upper bound for the perturbation of DNN outputs (in case on weight-noise), which helps to choose the minimal distance of ECOC.\n- two ECOC constructions are proposed: optimization-based construction and the construction based on Hadamard matrix.\n- theoretical results are supported by numerical experiments.", "weaknesses": "I list the major weak points below:\n1. The main contribution is repeated several times, namely in Introduction and in Section 4.\n2. Please provide an explicit problem statement and describe the conditions. As I understand the main task is to deal with weight-error.\n3. Please introduce the weight-error model explicitly. Now (in section 4.1) it is described by words but please define it formally. E.g. what does «\tweight-errors proportional to the weight scale» mean? The result is w(1+z), where z ~ N(0, sigma^2) or it is not true? \n4. If you have the weight-error model, then in my opinion, it would be better to train such noisy NN. In this case ECOC should be learned automatically. Could you please make such a comparison?\n5. Corollary 1 seems to be trivial and follows directly from the coding theory. It says that (for the guaranteed recovery) the norm of the errors should be less or equal then d/2.\n6. «Although it remains unclear which correlation matrices yield the best performance for ECOCs in absence of weight-errors, we know that codewords that are approximately orthogonal generally perform comparably to one-hot codes. Consequently, it is reasonable to regularize the orthogonality of the codewards during the ECOC construction». This is strange statement for the theoretically oriented paper. Actually the correlation is related to the minimum distance, namely $||a-b||^2 = ||a||^2 + ||b||^2 - 2 a^T b$ (codeword norms are usually fixed).\n7. There are many ways to construct good codes over {+-1} alphabet. Usually you should start with good binary code (e.g. Reed-Muller code) and map 0 to +1 and 1 to -1. There exist tables of good binary codes. Please try to use them and compare to your solutions. I believe your Method 2 to be some particular case of this approach.\n8. Experimental results demonstrate that constructed codes are better than one-hot code. At the same time my question is as follows. Is ECOC itself strategy beneficial? Could you please improve some state-of-the-art classifier with this approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate your feedback and provide our responses below:\n\n**A1).** We will rephrase in the revised manuscript.\n\n**A2).** Recall that $f(\\cdot; \\theta)$ is the NN with weights $\\theta$. Let $\\mathcal{A} (\\mathcal{E}, f, \\mathcal{D};u)$ be a training algorithm, which takes the ECOC $\\mathcal{E}$, NN architecture $f$, and dataset $\\mathcal{D}$ as input and outputs the trained weights. Here $u$ accounts for the randomness in the algorithm. Define the test error $\\mathcal{T}(\\theta, \\mathcal{D}) = \\sum_{(x,c)\\in \\mathcal{D}}\\mathbf{1}[D(f(x;\\theta))-c]$, then the problem is\n\n$$\\min_{\\mathcal{E}} \\mathsf{E}_{\\Delta\\theta} \\mathsf{E}_u \\mathcal{T}(\\mathcal{A} (\\mathcal{E}, f, \\mathcal{D};u)+\\Delta\\theta, \\mathcal{D})$$\nwhere $\\Delta\\theta$ is the random weight-errors. **Conditions:** NTK assumptions. This statement is for clarification, and we translate it into a trackable form in eq. (12).\n\n\n**A3).** Not True. The perturbed weights $\\tilde{\\theta} = \\theta + \\Delta\\theta$, where entries of weight-errors $\\Delta\\theta$ are i.i.d. Gaussian with zero-mean and $\\frac{\\bar{\\sigma}^2}{n}$-variance. We chose $\\frac{\\bar{\\sigma}^2}{n}$ because: 1). On hardware devices, the noise is proportional to the scale of the weights. 2). In the NTK regime, the weights after training are of order $1/\\sqrt{n}$ at the same scale of its initialization. \n\n**A4).** Noise-injection training (NIT) is an approach orthogonal to ECOC to combat weight-errors (see, e.g. [1]). However, it suffers from unstable training and long training time because each weight experiences variations independently in every training iteration. We compare the **accuracy** and **training time** of NIT and ECOC on MLP & MNIST task below, where vanilla is the original NN with one-hot code and NITs are noisy training NNs with different standard deviations. \n\nAccuracy:\n|method/noise level| 0 | 0.03 | 0.05 | 0.08 | 0.1 |\n|---------- |:----------: |  :---------: | :---------: | ---------: | :----------: |\n| vanilla | 98.44 | 88.67 | 35.46 | 11.61 | 10.80 |\n| NIT 0.03 | 98.51 | 98.02 | 93.44 | 24.56 | 11.42 |\n| NIT 0.05 | 98.16 | 97.85 | 96.66 | 73.25 | 23.50 |\n| NIT 0.1 | 10 | 10 | 10 | 10 | 10 |\n| ECOC (ours) | 98.51 | 97.04 | 84.33 | 42.47 | 26.54 |\n| ECOC (ours) + NIT 0.05 | 98.14 | 98.03 | 97.33 | 88.60 | 66.51|\n\nTraining time (on NVIDIA RTX A6000 GPU)\n| Method | Training time |\n| ------------- | :----------: |\n| vanilla | 414s |\n| NIT | 3355s |\n| ECOC (ours) | 410s |\n| ECOC (ours) + NIT | 3309s |\n\nThese results show that: 1) NIT improves the robustness but it significantly increases the training time; 2) training noise needs to be carefully picked when using NIT; 3) integrating the ECOC and NIT yields the best result.\n\n**A5).** Corollary 1 bears resemblance to the aforementioned coding theory result (i.e. half distance greater than the error), but is **different** in several aspects:\n1) The definition of the minimum distance is different in that ours involves code length $n_L$ (see Eq. (10)). \n2) The right hand side (RHS) of Eq. (11) is different from coding theory. In addition to weight-errors, which correspond to the \ncoding theory result, the RHS of Eq. (11) accounts for the \"confidence\" of clean inference because the clean inference may fall far from a codeword. \n3) While the classic coding theory result is deterministic, Corollary 1 is probabilistic. \n\nWhile Corollary 1 parallels the coding theory result, it **does not follow directly from the coding theory**. In fact, the derivation of Corollary 1 is quite involved and different from that for its counterpart in the coding theory. Hence, Corollary 1 is non-trivial.\n\n**A6).** We believe this stems from a misunderstanding of the our theoretical results. We claim that large codewords distance matters to the NN's robustness to weigh-errors. However, in terms of clean performance (in absence of weight errors), a good choice is to choose codewords to be orthogonal (based on the success of one-hot codes in absence of weight-errors), which does not directly relate to the codewords distance. In fact, our ECOC construction is a trade-off between clean performance and robustness, accounting for the final performance of NN with weight-errors.\n\n**A7).** Our Method 2 presented in Section 5.3 indeed constructs ECOC from good codes such as the Hadamard codes as suggested by the reviewer. Coincidentally, Method 2 uses a union of Hadamard codes and its complement, which is actually RM(1,N) code.\n \nGiven a good binary code, the **challenge** is how to select a subset of codewords from it to form an ECOC. If codewords are randomly picked without methodology, it does not necessarily lead to the optimal performance. We compare the performances of these codes on the MNIST/MLP task:\n|method/noise level| 0 | 0.03 | 0.05 | 0.08 | 0.1 |\n| ------------- | :-----------: |  :----------: | :-----------: | :-----------: | :----------: |\n| Reed-Muller (n=128) | 98.51 | 96.81 | 81.52 | 39.27 | 24.98 |\n| Hadamard (n=128) | 98.51 | 96.90 | 83.52 | 40.27 | 25.43 |\n| Ours (n=128) | 98.51 | 97.04 | 84.33 | 42.47 | 26.54 |\n\nOur proposed method has better performance than ECOCs formed by randomly picking codewords from either the RM or Hadamard code.\n\n**A8).**  ECOC strategy itself can be beneficial only if codewords are properly designed ([2] shows a case of ECOC with lower clean accuracy than one-hot). Without loss of generality, we provide the results of ResNet-50/TinyImageNet suggesting ECOC is beneficial. We believe more followup researches should be conducted to further enrich the potentials of ECOC in NNs, which has been far less explored yet.\n|method| accuracy | \n| ------------- | :-----------: |\n| Vanilla | 48.74 |\n| Ours | 57.64 |\n\n[1] Y. Long et al. \"Design of reliable DNN accelerator with un-reliable ReRAM.\" IEEE DATE, 2019.\n\n[2] A. Yu, et al. \"COLA: orchestrating error coding and learning for robust neural network inference against hardware defects.\" ICML, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hZ1S0kpfIT", "reviewer": "Reviewer_vbnL", "summary": "The authors applied ECOCs to DNNs to bolster the model’s resilience to weight errors. Most significantly, they have derived a perturbation bound through the utilization of the neural tangent kernel. According to their mathematical analysis, some principles of designing the ECOCs were revealed, leading to the construction of ECOCs based on Hadamard codes or direct optimization.  Experimental results indicate that the proposed method is effective.\n\nI have not thoroughly examined the proofs of the theorems, but the theorems themselves appear to be plausible based on my understanding.", "questions": "+ Is there a parallel line of research analyzing the model’s robustness with one-hot/softmax outputs through the lens of the NTK?\n+ Line 223, \"Although the optimal correlation matrices remain unindentified\". The authors should consider adding a relevant citation or providing an explanation to substantiate this claim. Could there be combinatorial approaches for constructing better codes?\n+ Section 3.2. The use of $\\ell$ (\\ell in math mode) is preferred over $l$, as it helps to distinguish it from the numeral $1$.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ The perspective presented under the NTK is novel.\n+ The mathematical analysis within this work is sound and offers valuable contributions to the academic community, particularly in the context of considering the one-hot code as a specialized form of ECOC. \n+ The experimental results indicate that the proposed method exhibits a considerable performance advantage over existing approaches.\n+ The manuscript is well written.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful for your effort to provide constructive comments and support this work. Our responses to your comments are summarized below.\n\n### **Response to questions**\n**Q1). Is there a parallel line of research analyzing the model’s robustness with one-hot/softmax outputs through the lens of the NTK?**\n\nA1). To the best knowledge of the authors, this is the first work analyzing ECOC's effectiveness on the robustness of NNs against weight-errors in the NTK regime. Although the softmax activation makes the learning dynamic more complicated, the perturbation of the final pre-activation caused by weight-errors can still be described by Theorem 1. With some analysis on the softmax function, the results could be extended. We thank the reviewer for pointing it out. \n\n\n**Q2). Line 223, \"Although the optimal correlation matrices remain unindentified\". The authors should consider adding a relevant citation or providing an explanation to substantiate this claim. Could there be combinatorial approaches for constructing better codes?**\n\nA2). We apologize for the confusion. Our key point is that the generalization performance (of the NTK model) depends on not only the correlation matrix but also the dataset (or the task). To identify the best correlation matrix, we need to know the data distribution (from which the dataset is sampled), which is often not available in real applications. \n\nThe \"combinatorial approaches\" mentioned by the reviewer is actually a good point. While the searching space is very large considering the code length and number of classes, one possible direction could be to employ mixed integer programming. We will explore these approaches in our future work.\n\n\n**Q3). Section 3.2. The use of $\\ell$  (\\ell in math mode) is preferred over $l$ as it helps to distinguish it from the numeral $1$**\n\nA3). We thank the reviewer for the suggestion. We will make changes in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors have implemented Error-Correcting Output Codes (ECOCs) with Deep Neural Networks (DNNs) to enhance the model’s robustness against weight errors. Notably, they have derived a perturbation bound using the neural tangent kernel (NTK). Their mathematical analysis uncovers key design principles for ECOCs, leading to the development of ECOCs based on Hadamard codes or through direct optimization. Experimental results demonstrate the effectiveness of the proposed method. The NTK perspective introduced is novel and provides fresh insights.

The mathematical analysis presented is rigorous and makes a valuable contribution to the field, particularly in understanding the one-hot code as a specific type of ECOC. The experimental results show that the proposed method significantly outperforms existing approaches. Overall, the concept is compelling and offers notable advancements.
Decision: Accept (poster)