acceptodds
Withdrawn from ICLR 2027

Correcting Errors, Correctly: Certified Robustness for Error-Correcting Output Codes

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Error-Correcting Output Codes (ECOC) leverage redundancy from coding theory to map classes into structured codewords rather than standard one-hot encodings. While this paradigm enhances empirical robustness in machine learning tasks, it remains a heuristic defense susceptible to adaptive adversaries, and to date no certified robustness guarantee exists. We bridge this gap by presenting the first certification framework for ECOC-based models. Leveraging per-bit certification and decoding-aware analysis, we derive closed-form robustness bounds for both hard and soft decoding schemes, enabling efficient and scalable certification for structured multi-class outputs. Extensive experiments show that our approach consistently certifies a larger certified radius and a higher proportion of inputs than naive certification of the same ECOC model, while also increasing resistance to practical adversarial attacks. These results demonstrate that integrating error-correcting structure into certification yields stronger and more reliable robustness guarantees for multi-class prediction.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Certified Robustness, Adversarial Machine Learning, Trustworthy Machine Learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_ET6GOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Addressing the lack of provable robustness guarantees in existing ECOC (Error-Correcting Output Codes) classification models, this paper proposes a robustness certification framework that combines per-bit certification and decoding-aware aggregation. It also designs two certification methods, ECOC-HD and ECOC-SD, to compute certified robustness radii for ECOC classifiers. The authors conducted experiments on multiple image classification datasets. The results show that, compared to traditional randomized smoothing methods, this approach achieves a larger certified radius and higher certified accuracy, and demonstrates greater robustness in certain adversarial attack experiments.

Critical strengths
  1. This paper addresses the lack of structure-aware robustness certification in existing ECOC classification models. The research motivation is clear, and the work holds both theoretical and practical significance.
  2. Combining per-bit certification with decoding-aware aggregation, the paper proposes ECOC-HD and ECOC-SD for hard decoding and soft decoding, respectively, and provides corresponding theoretical analyses and certification algorithms, offering a degree of methodological novelty.
  3. The paper evaluates certified robustness across multiple datasets and models, and through adversarial attack experiments, parameter analysis, and computational overhead tests, the experimental coverage is relatively comprehensive.
Critical weaknesses
  1. Some of the results of the Targeted ECOC Attack do not fully align with the authors’ conclusions.
  2. The baseline descriptions in Section 4.1 and Table 2 appear inconsistent.
  3. The coverage of recent related work is insufficient, particularly regarding studies on randomized smoothing and structured output robustness certification in recent years.
  4. The experiments primarily compare the method with classical randomized smoothing approaches, lacking comparisons with other representative certification methods.
  5. There is a lack of ablation experiments targeting core components.
Questions for authors

Q1. In Table 2, the Targeted ECOC Attack achieved a lower Robust Accuracy on CIFAR-10 than the C&W attack, which does not fully align with the paper’s conclusion that this attack offers no additional advantages. Additionally, the baseline entry in the Targeted ECOC Attack column corresponds to a targeted C&W attack rather than the same attack applied to the proposed methods. Please further explain these result.

Q2. There appears to be a discrepancy between the description of the Baseline in Section 4.1 and that in Table 2. Clarify the Baseline settings across different experiments.

Q3. One of the paper’s main contributions is the use of Decoding-aware Aggregation to combine per-bit certification results into an overall robustness guarantee; however, the current ablation experiments primarily focus on codeword length and noise parameters.

Q4. We suggest that the authors conduct a more comprehensive literature search and supplement the paper with recent research (particularly from 2024–2026) related to Randomized Smoothing, ECOC, and structured output robustness certification.

Q5. It is recommended to further consider representative methods such as SmoothAdv and MACER, or to discuss their compatibility with the proposed framework, and, conduct fair comparisons to more fully evaluate the advantages of the proposed method.

Reviewer_gSjdOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes the first certified robustness framework for Error-Correcting Output Code (ECOC)–based neural classifiers. The key idea is to treat each bit of the ECOC codeword as an independent binary classifier, certify each bit’s sign or interval stability via randomized smoothing (or median smoothing), and then aggregate these per-bit certificates through the ECOC decoding rule (hard or soft) to obtain a class-level certified radius. The authors derive closed-form bounds (Theorem 3.1 for hard decoding, Theorem 3.2 for soft decoding) and demonstrate that the resulting ECOC-HD and ECOC-SD methods outperform standard randomized smoothing on one-hot classifiers across MNIST, FMNIST, CIFAR-10, CIFAR-100, and Tiny-ImageNet, both in certified accuracy and under empirical attacks (PGD, C&W, targeted ECOC attacks). The paper also includes ablation studies on codeword length and noise level, a bit-error correlation analysis justifying the independence assumption, and complexity/runtime benchmarks.

Critical strengths
  1. The decoding-aware aggregation is a principled and non-trivial extension of randomized smoothing to structured output spaces.

  2. The empirical gains are consistent and meaningful across datasets and attack types.

Critical weaknesses
  1. The paper is missing substantial relevant work on certified robustness, making the positioning and baseline comparison incomplete. The paper discusses ECOC and randomized smoothing but omits major certified robustness lines—IBP, dual/LP certification, abstract interpretation, and certified training methods like SmoothAdv and MACER. Empirically, only Cohen et al.'s standard randomized smoothing is used as a baseline, so the claim that ECOC certification "outperforms standard certification" really means it outperforms one method. This weakens both positioning and the strength of the empirical claim.

  2. The technical novelty relative to randomized smoothing is incremental, and the paper does not convincingly address the unique challenges of the ECOC setting. The core mechanism is per-bit randomized smoothing followed by codebook aggregation. The aggregation is well-executed, but each bit's certificate is a direct application of Cohen et al. (or Chiang et al.). The paper frames correlated binary outputs as the central challenge, yet handles it by choosing a Hadamard codebook that makes bits nearly independent (correlation ≈ 0.064), then bounding via a Cartesian product. This is a reasonable engineering choice but undercuts the framing of a fundamental advance in certifying structured outputs.

  3. Evaluation is limited to small-scale datasets, and certified radii are modest. Primary experiments use ResNet-18 on MNIST/FMNIST/CIFAR-10/CIFAR-100, with Tiny-ImageNet only in the appendix. Mean certified radii are typically below 1.0 ℓ₂ (e.g., 0.584 on CIFAR-10), and there is no large-scale (e.g., ImageNet) evidence. Scalability to m ≥ 1024 codewords—needed for 1000-class problems—is not demonstrated, leaving the "practical certified defense" claim aspirational.

  4. The baseline comparison may be confounded by architectural and training differences. The baseline applies one-hot smoothing to an ECOC model trained with multi-bit BCE and m outputs, rather than comparing against a one-hot model trained with cross-entropy and Gaussian augmentation under identical hyperparameters. The reported gains could partly reflect this mismatch rather than a genuine benefit of decoding-aware aggregation.

Questions for authors
  1. On missing baselines: Why was the comparison limited to Cohen et al.’s standard randomized smoothing? Could the per-bit certificates be improved by using SmoothAdv or MACER training, and would that change the relative ranking between ECOC-SD and a well-tuned one-hot smoothed classifier? A direct comparison to a one-hot ResNet-18 trained with Gaussian augmentation and certified via Cohen et al. under identical hyperparameters would substantially clarify whether the gains come from ECOC structure or from the decoding-aware aggregation.

  2. On the independence assumption: The bit-error correlation analysis (Section D.1) shows low correlation on CIFAR-10 with Hadamard codes. Does this hold when the number of classes is not a power of two (e.g., CIFAR-100, where 100 rows are subsampled from a 128×128 Hadamard matrix)? Subsampling may break the exact column orthogonality, and if correlation increases, the Cartesian bounding becomes looser. The paper reports results on CIFAR-100 but does not repeat the correlation analysis there.

  3. On scalability: For a 1000-class problem like ImageNet, a Hadamard codebook would require m ≥ 1024 bits. The paper evaluates up to m = 512 on Tiny-ImageNet (200 classes). Does the certification overhead or the aggregation complexity become prohibitive at m = 1024, and does the statistical correction (Bonferroni with α/m) become so stringent that per-bit abstention rates rise substantially? A brief discussion or a small-scale experiment would address this.

  4. On the targeted ECOC attack: The paper reports that targeted ECOC attacks are “no more effective” than C&W/PGD. Were these attacks run with full EOT and with gradients through the continuous surrogate? The table shows ECOC-HD sometimes achieving higher accuracy under targeted attack than under C&W on FMNIST (67.50% vs. 65.98%). Could this indicate that the targeted attack was not fully optimized, or that the attack objective (maximizing correlation with target codeword) is not the strongest formulation for hard-decoded models? An adaptive attack that directly minimizes the aggregated margin used in Theorem 3.1 might be more informative.

  5. On the practical significance of certified radii: The mean certified radius on CIFAR-10 is 0.584. What is the threat model that this radius is meant to address? In the randomized smoothing literature, radii below ~0.5 are often considered marginal for CIFAR-scale images. Does the ECOC framework offer a path to substantially larger radii (e.g., via longer codewords or different smoothing distributions), or is the modest radius an inherent limitation of the approach?

Reviewer_HyDfOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

In this paper authors focus on the problem of certifying the robustness to adversarial perturbations of an ECOC based multi-class classifier. Hadamard codebooks is used for encoding throughout. For decoding, two strategies are considered: hard-decoding and soft decoding. For certification existing methods of Cohen et al. 2019 (randomised smoothing) along with Chiang et al. 2020 (median smoothing) are used. Models (ResNet-18 and ResNet-50) are trained with Gaussian noise based data-augmentation. Empirical experiments are provided on the trained models MNIST, FMNIST, CIFAR-10, CIFAR-100.

Critical strengths

The paper overall read well and is easy to follow. Understanding the certifiable properties of an ECOC based classifier is an important problem.

Critical weaknesses

As I have mentioned before that certifying ECOC based classifiers is an important problem, however the novel contributions made by this paper is minimal.

Theorems 3.1 and 3.2 are trivial and follows directly from the error-correcting property of a codebook and therefore cannot be considered as a significant novel contribution. They are necessary mathematical machinery, but not a major contribution and calling them theorems would be a stretch, maybe propositions at best.

Out of the box methods of Cohen et al. 2019 and Chiang et al. 2020 are used for certification without any justification as to why only these specific methods are chosen. There are plenty of other certification methods such as MILP/LP based, convex-polytope etc. which can also be used. This is where novelty is expected the most, but the paper lacks it.

Regarding model training, authors use Gaussian noise based data-augmentation, but this is not a requirement of ECOC based classifiers. Therefore should the models be considered nominally trained or adversarially trained? If its latter, then why not simply extend the loss in eq (7) to min-max loss for PGD based adversarial training?

Certifiable accuracy provides a lower bound (LB) to the true adversarial accuracy. An upper-bound (UB) can be obtained with say 20-step PGD based attack. What matters is how close the LB it to the UB. Figure 2 provides in itself only shows that ECOC based methods are suitable to certification using the approach of Cohen et al., but this trend may not hold with some other certification method.

Empirical results are only limited to hadamard codebooks? Instead of more ablations on the dataset, I would have preferred more ablations on the types of codebooks used as that is the main area of focus of the paper. For eg: Dense (Random) codebooks of larger sizes can also provide both high clean and adversarial accuracy. CIFAR-100 can be dropped, MNIST and CIFAR10 suffices in my opinion. It is well known that adversarial accuracy will plummet for large number of classes and therefore CIFAR-100 is not really helpful.

Table 2 doesnt really provide any new information and also lacks critical detail of how many PGD-steps are used in the attack? Given that PGD accuracy is close to CW in the table, my guess is not enough, which kind of defeats the whole purpose of PGD attack.

Figure 2 and Table 2 should be merged to understand the gap between LB and UB on true adversarial accuracy.

Questions for authors

Given that authors have not developed a new method for certification, why only rely on Cohen et al. 's method for certification?

In figure 2, certified accuracy is shown for three settings (models): baseline, ECOC-HD, ECOC-SD and it appears that ECOC based models have a higher certified accuracy, but since only Cohen et. al's method is tested, how are we suppose to interpret these results?

What is the number of PGD steps used ? This information is critical in evaluating table 2.

Clarification: When the code-length is increased in fig 3. on page 18, does the number of model parameters change in the fully-connected final layer of the ResNet?

Why only hamming decoding is considered?

Comments on the paper

1 comment

We sincerely thank the reviewers for their time and effort, and greatly appreciate their valuable feedback and suggestions. After careful consideration, we have decided to further revise the paper and withdraw it from this submission.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.