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_cc_2024_Conference
Published: 2024-05-14 19:58:09

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.

Main paper: 
 introduction: 
 Inspired by error correction codes in wireless communication and memory system, error correction output codes (ECOCs) are proposed to improve the generalization performance of multi-class classification in decision trees by decomposing a complex problem into simpler binary classification sigmoid activation functions, which allows larger error margin than softmax [10] . Existing works are mostly empirical studies and fail to 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 infinite-width DNN with proper initialization is essentially a dynamic of kernel ridge regression with defined neural tangent kernel [13] . Lee et al. refine the results in [13] and prove that infinite-width DNNs evolve like a linear model under gradient descent [14] . Lee et 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.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The main theoretical results and proposed ECOC construction methods are 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 be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 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 not penalize honesty concerning limitations. 
error correction output codes (ecocs): 
 ECOC is a generalization of conventional one-hot codes with various code length and arbitrary binary entries. An ECOC is defined by an encoding function E : [C] → {1, -1} n L , where C is the number of classes, and [C] denotes the set [C] ≜ {1, 2, ..., C}. Here n L is the code length, which is equal to the dimension of the DNN's outputs. The encoding function essentially maps a class label to a binary codeword. Let D denote the training data set with each entry as a pair (x, c), where x ∈ R n0 and c ∈ [C] are DNN inputs and the corresponding label, respectively; n 0 is the input dimension of the DNN. Let f (x; θ) : R n0 → R n L be the DNN model parameterized with weights θ. The objective during the training process is to minimize the loss functionEQUATIONwhere g(•, •) is referred to as sample loss. During the inference, the DNN outputs f (x; θ) are mapped to classification decisions through the following decoding processEQUATIONwhere D(•) : R K → [C] is the decoding function. We can choose arbitrary metric in Eq. ( 2) for decoding, but we mainly focus on the l 2 norm in this paper.NTK is a tool for analyzing the learning dynamic and generalization of DNNs. It allows us to study DNNs in a reproducible kernel Hilbert space (RKHS) instead of intractable DNN weights space. We adopt a fully-connected feed-forward neural networks with L layers. At the (l + 1)-th layer, we haveEQUATIONfor l = 0, 1, ..., L -2, where h l+1 ∈ R n l+1 and x l+1 ∈ R n l+1 are the pre-and post-activation values at the (l + 1)-th layer; w l+1 ∈ R n l+1 ×n l and b l+1 ∈ R n l+1 are the weights and bias accordingly; n l is the width of the l-th layer; ϕ(•) is the activation function. In this case, n 0 is the dimension of DNN inputs and n L is the dimension of DNN outputs (also the ECOC code length). With NTK parameterization, the entries of w l+1 and b l+1 are initialized with independent and identically distributed (i.i.d.) Gaussian random variables with N (0, 1 n l ) and N (0, 1), respectively. Let X ∈ R n0×|D| be the input set in D, where each column represents a sample of inputs, and let Y ∈ R n L ×|D| be the corresponding codewords, where each column represents the corresponding target. Without loss of generality, we parameterize n l = α l n with some α l > 0 and n > 0, for 1 ≤ l ≤ L -1, then training DNNs in the NTK regime minimizing MSE will result in the following DNN function according to [13] when hidden layer width parameter n → ∞,EQUATIONwhere K : R n0 × R n0 → R is the NTK, K(X , X ) ∈ R |D|×|D| , and K(X , x) ∈ R |D|×1 .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: We provide the full set of assumptions and a complete proof in Section 4 and Section A.1.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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. 
theoretical results: 
 In this section, we analyze the efficacy of ECOCs on 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 are summarized as follows:• We prove that adopting ECOC as a replacement of one-hot codes is equivalent to changing the decoding metric from l 2 distance to a 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 error correction capability of ECOCs.Assumption 1. The activation functions in the hidden layers are bounded at 0, i.e., ϕ(0) < ∞, and they are Lipschitz continuous with parameter B, i.e., for any h and h ′ , we haveEQUATIONAssumption 2. For any DNN input x 0 , we have∥x0∥ 2 √ n0 ≤ 1.Assumption 3. The matrix K(X , X ) ∈ R |D|×|D| is full-rank. Assumption 4. The initial gradient with respect to the DNN output is bounded, i.e., there exists a constant R 0 such that ∇ f (X ,θ0) L 2 < R 0 .Assumption 1 holds for most of the common state-of-the-art (SOTA) activation functions, such as ReLU, sigmoid and tanh. Assumption 2 essentially assumes a bounded norm of 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 , X ). Assumption 4 should hold with high probability with proper choice of R 0 due to random initialization.In this subsection, we discuss the behavior of DNNs after being trained with ECOC. Our first result is based on eq. ( 4) proved in [13] . Proposition 1. Let Assumption 1, 2, 3 and 4 hold. Suppose there is no weight-errors and hidden layer width parameter n → ∞, then applying ECOC is equivalent to changing the decoding function of one-hot codes (with 0 and 1 entries) to the followingEQUATIONwhere e c ∈ R C is the c-th one-hot codeword and ∥x∥ A ≜ √ x T Ax is referred as the Mahalanobis norm with positive definite matrix A. Remark 1. From Proposition 1 we observe that, in NTK regime, ECOCs affect the performance of DNNs through the correlation matrix E([C]) T E([C]) of the codewords when the DNNs are free of weight-errors. For both one-hot and ECOCs, their target spaces R n L are equipped with l 2 -norm and the corresponding decoding metrics. Proposition 1 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.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.It has been reported in multiple works that ECOCs can improve the robustness of DNNs against weight-errors [8, 9, 11] . However, these studies lack a 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.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 σ2 /n.We first show the bound of hidden layer outputs in absence of weight-errors, which will be used to prove other results. Lemma 1 (Hidden layer output bound). Let Assumptions 1, 2, 3, and 4 hold. Then, for any hidden layer l ≤ L -1 and any δ > 0,EQUATIONholds with probability at least 1 -δ when n is large enough, where the hidden layer width n l = α l n with constant α l > 0 for all 1 ≤ l ≤ L -1.Based on the lemma, we show the perturbation bound in the following theorem. Theorem 1 (Perturbation bound). Let Assumptions 1, 2, 3, and 4 hold. Adopt the weight-error model in Sec. 4.3.1, and denote σ 2 = max l α l σ2 . Let x L and xL denote any clean output (in absence of weight-errors) and its perturbed counterpart due to weight-errors, respectively. Then for arbitrary δ > 0 and arbitrary DNN input, we haveEQUATIONwith probability at least 1 -δ -o(n -1 L δ -1 ) when n and n L are large enough, whereEQUATIONRemark 2. The theorem suggests that the normalized output perturbation∥x L -x L ∥ 2 √ n Lcan be bounded in terms of weight-error scale σ, Lipschitz constant B, absolute activation function value |ϕ(0)| and DNN depth L with high probability when hidden layer width n and code length n L are large enough. It can be observed that: 1) The bound can be made arbitrarily small when σ = 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.Based on Theorem 1, we present our main result in the following corollary to characterize the error correction capability of ECOCs. Corollary 1 (Main result). Let all the conditions in Theorem 1 hold. Denote normalized (l 2 ) distance of a codeword E(i) and normalized uncertainty of clean prediction given the clean output x L as dist(E(i)) and U (x L ), respectively, with the following definition:EQUATION)Then a DNN with an ECOC can make prediction with xL as if it is free of weight-errors after decoding, i.e., D(x L ) = D(x L ) with probability arbitrarily close to 1, if the ECOC satisfiesEQUATIONfor arbitrary small δ > 0 when n, n L → ∞. Remark 3. In eq. (40), U (x L ) accounts for the distance between clean output x L and its closest codewords, and Ξ(σ, B, |ϕ(0)|, L) + δ accounts for the output perturbation due to weight-errors. Note that Corollary 1 specifies conditions under which predictions can be made as if the DNN is free of weight-errors; however, it does not guarantee that these predictions will be the ground-truth labels. Even in the absence of weight-errors, DNNs may still produce incorrect predictions due to the data and model generalization, which cannot be corrected by ECOCs. A geometric explanation of Corollary 1 is given in Figure 1 . The perturbed output xL (red diamond) is within the ball centered at clean output x L (blue dot) with radius Ξ + δ according to Theorem 1. If eq. (40) holds, then distance between xL and the codeword D(x L ) (black dot at the bottom left), which is the decoding result of clean output x L , will be smaller than the distance from xL to any other codewords (black dot at top right), mean that D(x L ) = D(x L ) after decoding.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. 
ecoc constructions: 
 Inspired by our theoretical results, in this section, we propose two ECOC construction methods for small scale and large scale classification tasks, respectively.The final performance of ECOCs is determined by weight-error free performance and performance degradation on top of that due to weight-errors, which are discussed in Proposition 1 and Corollary 1, respectively. According to Proposition 1, the weight-error free performance is 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 Corollary 1, larger normalized distance of codes leads to better error correction capability of ECOCs, therefore we encourage the distances of the codes during code construction. Let Z ∈ {-1, 1} n L ×C be the ECOC codebook, i.e., a horizontal stack of codeword, then we construct the code by solving the following optimization problem:EQUATION)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 Z T Z.Before employing standard optimization algorithms, it is necessary to relax the feasible set from the discrete binary domain {-1, 1} n L ×C to the continuous interval [-1, 1] n L ×C . 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 Z as the generated codebook.Since the objective in eq. ( 12) is non-convex, Method 1 can be easily trapped in local optima, especially for ECOCs with large number of classes C. For this reason, we introduce Method 2 in this section which constructs ECOCs on top of 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; 2) all codewords are orthogonal to each other; 3) the Hamming distance between any two codewords is 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, 11, 12, 16] . An example of Hadamard code with code length 8 is given in Section A.2.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 a and b are non-negative integers. Let {v 1 , v 2 , ..., v H } be the Hadamard codewords, then the code constructed by Method 2 is given byEQUATIONIn other words, its codebook 6 ExperimentsE pick a,b ([C]]) = {v 1 , v 2 , ..., v a , -v 1 , -v 2 , ..., -v a , v a+1 , v a+2 , ..., v a+b }. We can observe that for a codeword E pick a,b (i) = v i with i ≤ a, it is orthogonal to all other codewords except E pick a,b (i + a) = -v i .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Code is submitted in a zip file.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setup: 
 We conducted all simulations using PyTorch framework on a workstation equipped with an AMD EPYC 7542 32-Core Processor and four NVIDIA RTX A6000 GPUs, each with 40GB of memory.Datasets and models MNIST [17] , CIFAR10 and CIFAR100 [18], and Tiny ImageNet [19] datasets are used for evaluation. In our experiments, MNIST and CIFAR10 represent small scale tasks, while CIFAR100 [18] and Tiny ImageNet represent large scale tasks. We adopt a (784-4096-4096-10) multilayer perceptron (MLP), AlexNet, VGG16 and ResNet-50 for MNIST, CIFAR10, CIFAR100 and Tiny ImageNet, respectively.Benchmarks Our ECOCs are compared against one-hot codes, repetition codes, random codes, and Hadamard codes [10] . 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 a repetition code from a one-hot code: each codeword of a one-hot code is repeated for multiple times. Hence, the number of codewords in a repetition code is the same as the number of classes, but its code length is a multiple of the number of classes. The codewords of a random code is obtained by choosing random binary entries of -1 and 1 with equal probability. For small scale tasks such as MNIST and CIFAR10, we compare codes constructed using Method 1 to with benchmarks. For large scale tasks, i.e., CIFAR100 and Tiny ImageNet, codes constructed based on Method 2 are used for comparison.Weight-errors Gaussian noises with different variance ω 2 are added to the weights during inferences 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 a different randomly generated codes.Superior performance of the proposed methods over existing ECOCs The performances of different ECOCs on small scale tasks (MNIST and CIFAR10) and large scale tasks (CIFAR100 and Tiny ImageNet) are summarized in Tables 1 and 2 , respectively. We made the following observations from Tables 1 and 2: 1) The clean accuracy (ω = 0) of different codes are similar for small scale tasks in Table 1 , even with different code lengths. We believe this is partially due to the simplicity of the tasks. Besides, these codes all have good orthogonality, therefore they have similar generalization performance according to Proposition 1. In contrast, the clean accuracy is more varied for large scale tasks in Table 2 . We believe this is because the assumption of infinitely wide DNN does not hold when the code length is comparable to 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 n L 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 in our theoretical results, making the proposed methods inspired by them more effective. 4) Interestingly, Hadamard and random codes perform similarly when the code length is large. This is because the expectation of correlation matrices and pair-wise distances of 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 1 and Method 2 Recall that Method 1 and Method 2 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 in Table 3 . For small scale task, i.e., CIFAR10, Method 1 outperforms Method 2. However, for larger tasks with more classes, i.e., 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: All the details are provided in Section 6 and in the code submitted.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. Justification: CPU and GPU types are provided in Section 6.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of 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 make it into the paper). 
conclusion: 
 In this paper, we provide theoretical explanations for the efficacy of ECOCs. We showed that using ECOCs to replace one-hot code is equivalent to changing the decoding metric from l 2 norm to 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 is 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 existing ECOCs.[18] Alex Krizhevsky, Geoffrey A Supplementary Material 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This research does not violate any of NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of 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 societal 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.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied 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 is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 a 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 6.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if 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 a 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 be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]  
 
 Appendix: We start with a results in [14] , which will be used in our proof.Theorem 2 (Theorem G.1 in [14] ). Let Assumptions 1, 2, 3, and 4 be satisfied. For any given δ > 0, there exist constants n ′ > 0, A > 0, and η0 > 0, such that for all n > n ′ and any step t, employing gradient descent with a learning rate of η = η 0 n ensures thatEQUATION)with probability at least 1 -δ.Proposition 1. Let Assumption 1, 2, 3 and 4 hold. Suppose there is no weight-errors and hidden layer width parameter n → ∞, then applying ECOC is equivalent to changing the decoding function of one-hot codes (with 0 and 1 entries) to the followingEQUATIONwhere ec ∈ R C is the c-th one-hot codeword and E is the ECOC encoding function.Proof. Let Ỹ denote the target encoded by the one-hot code. Notice that E(c) = E([C])ec, then the ECOC target can be written as Y = E([C]) Ỹ. The decoding process can be described asEQUATIONA.1.2 Proofs of Lemma 1Lemma 1 (Hidden layer output bound). Let Assumptions 1, 2, 3, and 4 hold. Then, for any hidden layer l ≤ L -1 and any δ > 0,EQUATIONholds with probability at least 1 -δ when n is large enough, where the hidden later width n l = α l n with constant α l > 0 for all l.Proof. Consider w ini,l and b ini,l as the initial weights and bias of the l-th layer, respectively. Define u l and v l as the adjustments to the weights and bias of the l-th layer due to training, respectively, meaning w l = w ini,l + u l and b l = b ini,l + v l . From eq. ( 3), we getEQUATIONApplying the triangle inequality, we obtainEQUATION)Recall that the entries of w ini,l and b ini,l follow N (0, 1/n l-1 ) and N (0, 1), respectively, the elements of (w ini,l x l-1 + b ini,l ) are independently and identically distributed Gaussian with zero mean and variance(∥x l-1 ∥ 2 2 /n l-1 + 1). The square of each element follows a χ 2 distribution with mean (∥x l-1 ∥ 2 2 /n l-1 + 1) and variance 2(∥x l-1 ∥ 2 2 /n l-1 + 1). Leveraging Chebyshev's inequality, for any δ1 > 0,∥w ini,l x l-1 + b ini,l ∥ 2 √ n l ≤ ∥x l-1 ∥ 2 2 n l-1 + 1 + δ1 ≤ ∥x l-1 ∥ 2 √ n l-1 + 1 + δ1 (20)with a probability of at least 1 -2(∥x l-1 ∥ 2 2 /n l-1 +1) n l δ 1. For the second term,EQUATIONwhere the second inequality uses Theorem 2 and the definition of α l = n l /n. Acknowledging Assumption 1, which posits |ϕ(h) -ϕ(0)| ≤ B|h|, and combining eq. ( 19) with eqs. ( 20) and ( 21), we haveEQUATION)with a probability of at least 1 -2(∥x l-1 ∥ 2 2 /n l-1 +1) n l δ 1. With sufficiently large n, we haveEQUATIONwith probability at least 1 -δ ′ and n large enough. After recursion, we haveEQUATIONwith probability at least 1 -δ ′ and n large enough, where the last inequality uses Assumption 2.Theorem 1 (Perturbation bound). Let Assumptions 1, 2, 3, and 4 hold. Adopt the weight-error model in Sec. 4.3.1, and denote σ 2 = max l α l σ2 . Let xL and xL denote the clean output (in absence of weight-errors) and perturbed output due to weight-errors, respectively. Then for arbitrary δ > 0 and arbitrary DNN input, we have ∥xL -EQUATIONwith probability at least 1 -δ -o(n -1 L δ -1 ) when n and nL are large enough, whereEQUATION)Proof. Let wl+1 and bl+1 denote the noisy weights and bias at the (l + 1)-th layer, respectively, with the noise variances being σ 2 w /n l for the weights and σ 2 b for the bias. Consequently, at the l + 1-th layer, the relationships can be represented as:EQUATIONAnalyzing the preactivation term further, we obtain:EQUATIONwhere w ini,l+1 represents the initial weights at the (l + 1)-th layer, characterized by a variance of 1/n l , and u l+1 is the adjustment of weights as a result of the training process. The prefix ∆ denotes the perturbation of corresponding variable due to the weight noise. Utilizing the triangle inequality, we deduce:EQUATION)Recalling that the weight perturbation ∆w l+1 has a zero mean and a variance of σ 2 /n l for l ≤ L -2. Similar to eq. ( 20), Chebyshev's inequality givesEQUATIONfor any δ1 > 0, with the probability at least 1 -2σ 2 ∥x l ∥ 2 2 /n l n l+1 δ 1 ≤ 1 -o(n -1 δ -1 1 ).Similarly, for the perturbed weights combined with the perturbed inputs, we obtain:EQUATIONfor any δ2 > 0, with a corresponding probability of at least 1 -2(1+σ 2 )∥∆x l ∥ 2 2 /n l n l+1 δ 2. For the bias perturbation, we haveEQUATIONfor any δ3 > 0 with the probability at least 1 -EQUATION). According to Theorem 2, for arbitrary δ4 > 0, we have ∥u l+1 ∥ F ≤ AR0n -1/2 with probability at least 1 -δ4 and n large enough, which results inEQUATIONNote that this term can be arbitrarily small when n is large enough. Combine eq. ( 29), ( 30), ( 31), ( 32) and (33), we haveEQUATIONwith probability at least 1 -δ l for n large enough, where the first inequality uses Assumption 2, and the second inequality uses Lemma 1. Reuse eq. ( 34) for multiple times, we have for l ≤ L -1EQUATION)with probability at least 1 -δ ′ l when n is large enough, where the second inequality uses the fact ∥∆x0∥ 2 = 0, and that δi can be arbitrarily small for all i when n is large enough.We take care of the final layer specially due to the finite dimension. Specifically, we first rewrite eq. ( 33) asEQUATION)According to eq. ( 34), we have∥∆hL∥ 2 √ nL ≤ σ ∥xL-1∥ 2 √ nL-1 + √ 1 + σ 2 ∥∆xL-1∥ 2 √ nL-1 + AR0 √ αL-1 √ nL ∥∆xL-1∥ 2 √ nL-1 + σ + δ ′ L (37)for arbitrary δ ′ L > 0 with probability at least 1 -δ ′ L and n large enough. Note that the probability bound in eq. ( 29), ( 30), ( 31), ( 32) and (33) all have order o(n -1 L δ -1 ). Plug in eq. ( 35) and use Lemma 1, we finally have∥∆xL∥ 2 √ nL ≤ AR0 √ αL-1 √ nL + 1 σB L 1 - B + |ϕ(0)| 1 -B √ 1 + σ 2 L -1 √ 1 + σ 2 -1 + Bσ 1 + |ϕ(0)| 1 -B B √ 1 + σ 2 L -1 B √ 1 + σ 2 -1 + δ (38) with probability at least 1 -δ -o(n -1 L δ -1) when n is large enough.Corollary 1 (Main result). Let all the conditions in Theorem 1 hold. Denote normalized (l2) distance of a codeword E(i) and normalized uncertainty of clean prediction given the clean output xL as dist(E(i)) and U (xL), respectively, with the following definition:EQUATION)Then a DNN with an ECOC can make prediction with xL as if it is free of weight-errors after decoding, i.e., D(xL) = D(xL) with probability arbitrarily close to 1, if the ECOC satisfiesEQUATIONfor arbitrary small δ > 0 when n, nL → ∞.Proof. Our goal is to prove that for any codeword E(i) ̸ = D(xL), the distance∥x L -D(x L )∥ 2 √ n L ≤ ∥x L -E(i)∥ 2 √ n L, which suggests that xL is mapped to D(xL) instead of any other codewords after decoding. By triangle inequality, we haveEQUATIONwhere the second and the third inequality use eq. ( 8) and (40), respectively. Given the definition of dist(D(xL)), we have∥E(i)-D(x L )∥ 2 √ n L ≥ dist(D(xL)). By triangle inequality again, we haveEQUATIONwhere the second inequality uses eq. ( 41). Comparing eqs. ( 41) and (42), we complete the proof.Hadamard codes exhibit several beneficial properties: 1) the number of codewords is 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 is half of the code length. This property allows Hadamard codes to achieve the upper bound for the minimum Hamming distance given the code length. Hadamard code is an excellent choice for ECOC, which has been validated in previous works [11, 12] . An example of Hadamard code with code length 8 is as follows: H8 =           1 1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 1 -1 1 1 -1           (43)Performance comparison between Method 1 and Method 2 Additionally, we compare the performance of ECOC constructed by Method 1 and Method 2 on small scale task with small scale DNN, i.e., AlexNet CIFAR10. Similarly, as shown in Table 4 , Method 1 outperforms Method 2, which emphasizes the benefit of using Method 1 on small scale tasks.In Section 4, we claimed that correlation of code matrices determines the weight-error free performance of ECOC and distance of codewords determines the performance degradation from weight-error. Here we use Method 2 as an example to show such trade-off. As shown in Figure 3 , we vary the number of complement pairs a in ECOC constructed by Method 2 and compare the performance. Larger a means larger correlation while larger distance. In this set of experiments, a = 40 achieves the best correlation and distance trade-off.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.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 the 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 be published with the paper.The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable to "[No] ", it 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 we used"). In general, answering "[No] " or "[NA] " is not grounds for rejection. While the questions are phrased in a binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.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 the questions and only use the provided macros for your answers.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is 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 a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a 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 or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to 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 closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The presentation of the paper  could be further improved. Please consider the following:
- All parameters need to be defined in the main text. In  (6),  E([C])   and in (8)  $\bar{\delta}$ 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..."

- in eq (20), <= should be = .


-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. 
-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.
questions: 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. 

- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: I list the major weak points below:
1. The main contribution is repeated several times, namely in Introduction and in Section 4.
2. Please provide an explicit problem statement and describe the conditions. As I understand the main task is to deal with weight-error.
3. 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 «	weight-errors proportional to the weight scale» mean? The result is w(1+z), where z ~ N(0, sigma^2) or it is not true? 
4. 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?
5. 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.
6. «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).
7. 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.
8. 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?
questions: questions: See Weaknesses
limitations: limitations: In my opinion, the limitation section should be increased, please discuss the limitations of your method rather that «hardware acceleration».
paper_summary: paper_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.

I have not thoroughly examined the proofs of the theorems, but the theorems themselves appear to be plausible based on my understanding.
strength_weakness: strength_weakness: N/A
questions: questions: + Is there a parallel line of research analyzing the model’s robustness with one-hot/softmax outputs through the lens of the NTK?
+ 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?
+ 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: limitations: N/A

Comments: title: Gentle Reminder: Please kindly review our rebuttal (From the authors)
comment: Dear Reviewer Vn9W,

Thank you once again for your valuable feedback on our work. We wanted to kindly remind you that our rebuttal is now ready for your review. We fully appreciate your busy schedule and the additional effort this process requires.

As the reviewer-author discussion period is concluding in just a few hours, and the other two reviewers have responded positively to our rebuttal, your response and advice will be crucial to our work. We would greatly appreciate your prompt attention to this matter.

Thank you very much for your attention. 

Best,

Authors
Thank you, I will keep my score.
Dear Reviewer Vn9W,

Thank you for reviewing our work and providing feedback that helps us improve the quality of our paper. We provided detailed responses according to your feedback, including some experiment results that you’re curious to see. In this regard, we hope you could take some time to take a look at our results. If you have any further questions or advice, please feel free to let us know. We’re looking forward to your kind response. We kindly remind that the deadline of the discussion period is tomorrow August 13th AOE. Your response is highly appreciated. 

Thank you!

Regards,

Authors
Thank you for addressing my concerns,  I will keep my score.