acceptodds
Under review as a conference paper at ICLR 2027

Output Coding in Multiclass Classification under Shared Bottlenecks

Abstract

In output coding for multiclass classification, each class is assigned a binary codeword, and the model learns the corresponding bits jointly from a shared feature representation. When the shared representation is constrained to be low-dimensional, a representation bottleneck, the binary prediction tasks compete for limited representational capacity, so the choice of code can affect which distinctions between classes are preserved. We study this effect under squared-loss training with a shared low-rank representation. Our goal is not to show that output coding universally improves classification, but to understand how the choice of code shapes the representation learned under this bottleneck. Even when two codes can represent exactly the same multiclass scoring rules, they can weight the training objective differently and therefore select different feature subspaces. We characterize this selected subspace and show that the resulting increase in classification error is proportional to the loss of Gaussian width, a geometric measure of the class structure removed by the projection. We also show that a linear decoder achieves the lowest classification error possible using only the retained representation. To show that conventional code properties do not determine which class information survives the bottleneck, for each bottleneck rank we construct pairs of binary codes with matched conventional code properties and binary-task difficulty, yet whose learned representations retain disjoint feature directions and have provably different multiclass risks. Moreover, the risk gap is at least of the improvement the Bayes classifier achieves over the best classifier that ignores the features, and this separation persists under small perturbations. Frozen-feature experiments further show that sensitivity to code choice can be substantial and task-dependent: coding improves over one-hot regression on Fashion-MNIST, but not consistently on CIFAR-100. These results show that conventional code properties alone do not determine which class information survives a shared representation bottleneck.

Primary area:
learning theory
Keywords:
error-correcting output codes, representation learning, reliable AI, shared bottlenecks, multiclass classification, decision preservation

Reviews

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

This paper investigates how different output coding strategies affect learned representations under a shared low-dimensional bottleneck, providing theoretical analyses that connect code-dependent feature selection with classification error and Gaussian width. Experiments on Fashion-MNIST and CIFAR-100 show that output coding can significantly affect classification performance.

Critical strengths
  1. The paper provides several theoretical results explaining how output coding affects representation learning under a shared bottleneck. I think the connection between classification error and Gaussian width is interesting and provides a useful perspective on understanding representation learning.

  2. The paper addresses a well-defined problem and provides mathematical analysis to support its main findings. I also think the authors do a good job of explaining why conventional code properties may not be sufficient to characterize the learned representations.

Critical weaknesses
  1. My main concern is that the experimental evaluation is relatively limited. Although the theoretical analysis might be interesting, the experiments are mainly conducted on Fashion-MNIST and CIFAR-100 using frozen features. I think more experiments on modern architectures with end-to-end representation learning would make the paper much more convincing.

  2. Another concern is that I find this paper quite difficult to read. I think the writing is rather dry and not very engaging. In the introduction, there are too many technical terms without sufficient explanation or illustration. I am also not sure whether just the first two paragraphs in the introduction are enough to clearly position this paper within the existing research. At least for me, I find it difficult to understand the background and motivation of this work, which makes it hard to properly assess its value and significance. In fact, I still do not clearly see the value of this work.

  3. In line 126, a period is missing after the word "matrix".

Questions for authors
  1. Could you provide more experiments on modern architectures with end-to-end representation learning? I think this would make the paper more convincing and help show whether the findings are useful in practice.

  2. Could you make the paper easier to read, especially the introduction? I think more background and clearer explanations of the main ideas would help readers better understand the motivation and contributions of this work.

  3. Could you explain more clearly the main value of this work compared with existing methods? I am still not fully convinced why these theoretical findings are important and how they could be useful in practice.

2 comments

Thank you for your constructive feedback on expanding the empirical evaluation, improving the Introduction, and clarifying the value of the work. Below, we address these points directly and identify the corresponding changes in the manuscript.

1. End-to-end learning and broader evaluation

Following your suggestion, we added an end-to-end CIFAR-100 experiment with a CIFAR-style ResNet-18 trained from scratch through a shared rank-16 bottleneck (Section 6 and Supplementary Section S12). Using 10,000 training images, 30 epochs, and three paired seeds, coding achieves 81.84% mean test error versus 83.39% for one-hot regression, both with validation-selected projected LDA decoding. Softmax with native decoding achieves 59.95%. This extends the comparison to jointly learned features and places the coding results alongside a strong cross-entropy baseline. The direct test of our subspace predictions remains the separate linear experiment described below.

Beyond ResNet-18, we evaluate frozen features from DINOv2-small, a self-supervised vision transformer, on Fashion-MNIST. At rank four, coding reduces error by 13.77 percentage points relative to one-hot regression using identical training examples and a common Gaussian decoder (Appendix L, Table 9). Supplementary Section S10.6 also reports a small experiment with a trainable nonlinear encoder on Optdigits. To test the predicted directions directly, we trained factorized linear predictors from random initialization (Section 6, Figure 3, and Appendix M). At rank one and the largest sample size, N = 10 million, their mean overlaps with their respective code's predicted population direction are 99.92% and 99.93%, versus 0.07% with the alternative code's prediction (Table 11). These results distinguish close recovery of the population directions from the broader image comparisons.

2. Readability, intuition, and motivation

Regarding the Introduction, we now explain output coding before using a garment-classification example to motivate the bottleneck. Distinguishing shirts, trousers, and coats through a small set of shared features illustrates why class distinctions compete for capacity. Figure 1 then shows how two codes favor different directions. Section 2 presents a four-class example—cat, dog, car, and truck—and Figure 2 follows the path from coded labels through the shared representation to the final prediction. These examples provide an intuitive route into the mathematical argument.

We also define the main terms where they become relevant. The Introduction explains class distinctions as information that changes relative class scores; Section 2 introduces the coding metric through its role in weighting the training loss; and Section 3 explains Gaussian width through its connection to classification error. We have also corrected the missing period you identified after ‘matrix’.

3. Contribution and practical significance

Your question about the value of the work prompted us to sharpen its positioning in Related Work (Section 1.1). Earlier work reports other benefits of coding: Verma and Swami (NeurIPS 2019) find improved adversarial robustness and probability estimates, while Yang et al. (AAAI 2015) report more discriminative features from coded targets. Our analysis complements these empirical findings. Classical analyses relate codeword separation, binary prediction errors, and decoding to multiclass performance; Evron et al. (2023) study assignment effects through the difficulty of the induced binary tasks. We isolate an additional effect of sharing a limited representation. Theorem 4 constructs codes with identical singular spectra, row and column Hamming-distance histograms, and Bayes errors for corresponding binary tasks, yet their retained subspaces have no nonzero direction in common and their optimal multiclass risks differ. Thus, the difference can persist even after controlling these code properties and binary-task difficulties.

The practical implication is that conventional code summaries alone cannot determine which class information a bottleneck retains. In our frozen-feature experiments, 32 row permutations share the same spectra and distance histograms, yet differences between codes averaged over training draws account for 76.5–97.0% of the observed candidate test-error variance on Fashion-MNIST and 39.3–52.5% on CIFAR-100 in the descriptive decomposition (Section 6; Appendix K.3, Table 5). We therefore recommend evaluating assignments on the target features at the intended bottleneck rank, with training examples and decoding controlled. One-hot regression and code whitening help identify the effect of nonuniform loss weighting (Proposition 5, Section 5). Sections 5–7 explain these practical implications, providing a basis for evaluating and developing codes that account for both data and representation capacity.

I appreciate the authors’ efforts to add end-to-end learning experiments and broader evaluations, and to improve the clarity of the paper’s intuition, motivation, contributions, and practical significance. These changes address some of my original concerns. However, the new experiments and substantial rewriting take the paper well beyond its original scope. I feel that it would need another full round of review, so I will maintain my original score.

Reviewer_KDXkOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how output coding affects learned representations in multiclass classification under a shared low-rank bottleneck. The authors show that, even when different binary codes have equivalent expressive power, they can induce different feature subspaces because the coding matrices implicitly reweight class distinctions during squared-loss training.

The main theoretical contributions include a characterization of the code-dependent subspace selected by reduced-rank regression and an exact relationship between classification regret and the Gaussian width lost through projection under a spherical affine model. The authors further construct pairs of binary codes with identical conventional code statistics and matched binary-task difficulties, yet producing disjoint learned subspaces and different multiclass risks. The theoretical results are supported by mathematical constructions and experiments using frozen image features on Fashion-MNIST and CIFAR-100. The experiments show that output coding can substantially outperform one-hot reduced-rank regression on Fashion-MNIST, while the results on CIFAR-100 are mixed. Rank-constrained softmax achieves better performance in the reported comparisons, suggesting that the main contribution is understanding the effect of coding on representation learning rather than demonstrating a generally superior classification method.

Critical strengths
  1. The paper provides a mathematical explanation of how output coding affects learned representations under a shared low-rank bottleneck, establishing a connection between classification regret and Gaussian width.

  2. The authors construct codes with identical conventional properties and matched binary-task difficulties that nevertheless produce different representations and classification risks. This highlights the limitations of conventional code metrics, although the practical implications remain unclear.

Critical weaknesses

The theoretical results rely on restrictive distributional assumptions. Empirically, the improvements over one-hot regression are inconsistent across datasets, and rank-constrained softmax achieves better performance in the reported comparisons. It remains unclear how these theoretical findings can guide the design of more effective classification methods.

Questions for authors

No

1 comment

Thank you for your constructive feedback and positive assessment of our work. Below, we explain the role and broader applicability of the theory, clarify the empirical comparisons, and describe how the findings can inform practical code design.

1. Role of the spherical affine model and extensions

We adopt this idealized model because it yields an exact geometric link between projection and classification risk through Gaussian width (Theorem 2). Evaluating each retained subspace with its Bayes-optimal decoder separates information lost through the bottleneck from errors caused by decoding. This is the analytical advantage of the assumptions, whose role we clarify in the Introduction and Sections 2–3.

The reduced-rank regression characterization itself extends to arbitrary feature distributions with finite second moments and the stated covariance conditions, using covariance-normalized coordinates (Section 2 and Appendix D). We also establish different retained representations and optimal risks under Gaussian class distributions with nonlinear softmax posteriors (Proposition 9; Appendix D and F.3), although binary-task Bayes errors are not matched in that extension. Proposition 12 in Appendix H.2 bounds departures from the affine risk prediction through posterior-approximation and conditional-mean errors. These results connect the analysis to linear bottlenecks on frozen ResNet and DINOv2 features. Supplementary Section S12 further examines a jointly trained encoder, while the exact subspace characterization concerns fixed features.

2. Interpreting the comparisons with one-hot regression and softmax

Our goal is to characterize how output codes change the feature subspace retained by a shared bottleneck, rather than propose coded squared loss as a replacement for cross-entropy (Introduction and Section 7). Squared loss selects directions according to the code's weighting of the class signal; it does not directly optimize classification error or Gaussian width. Consequently, changing the code can help or hurt classification. On Fashion-MNIST at rank four and 3,000 total labels, coding reduces error by 11.39 percentage points relative to one-hot regression with identical training examples and projected LDA decoding (Section 6, Table 1). CIFAR-100 shows less consistent gains and larger relative contributions from training draws and their interaction with code choice (Appendix K.3, Table 5). Rank-constrained softmax achieves lower error in our reported comparisons, and we retain it as a strong performance baseline (Table 1 and Supplementary Section S12).

3. How the findings guide classification methods

Theorem 4 establishes that codes with identical singular spectra, Hamming-distance histograms, and corresponding binary-task Bayes errors can retain subspaces with zero intersection and incur different optimal classification risks. Thus, conventional code summaries do not determine the quality of the retained representation. Our 32 row-permuted assignments also share spectra and distance histograms, yet differences between codes averaged over training draws account for 76.5–97.0% of candidate test-error variance on Fashion-MNIST and 39.3–52.5% on CIFAR-100 in the descriptive decomposition (Section 6; Appendix K.3, Table 5).

In practice, code selection should therefore account for both the target data and the available rank. For a classifier with frozen image features and a small bottleneck, assignments that look equivalent by conventional summaries should be compared using pilot risk estimates or validation on the target features (Section 6, Equation 11). This points toward choosing loss weightings that preserve useful class distinctions at that rank. It is not a rule that a larger Hamming distance always preserves more separation: the selected subspace depends jointly on all class contrasts.

One-hot RRR and code whitening provide controlled references for identifying the effect of nonuniform loss weighting when training examples, capacity, and decoding are held fixed (Proposition 5; Sections 5–7). These findings give a basis for developing and evaluating codes that account for data and capacity; designing an algorithm that consistently surpasses strong classifiers remains a further step.

Reviewer_8FHmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This work investigates how the output coding of multiclass classification tasks affects the class separation under shared feature representation. Under shared feature representation, a classifier typically maps to a low-rank bottleneck and determine the class-discriminating feature directions the classes. Under different codewords, training a multiclass classifier have different classification error. This work focuses on the analysis of the relationship between the low-rank feature representation, output codewords, and model performance.

The work shows that the under a low-rank bottleneck (of rank r) with the shared feature representation, the choice of codewords determines the r shared features directions that are preserved. This comes from changing how the different class distinctions are weighted. The top r eigen-direction of the AKMA⊤AK_{M}A^{\top} are indicative of the optimal rank r predictor. The rank restriction forces the classifier to decide the class-separating directions that are worth preserving.

Critical strengths

(1). The work provides a mathematical mechanism to support the analysis of how multiclass classifier with low-rank shared feature bottleneck determine the class-separating directions.

Critical weaknesses

(1). The math in this paper is difficult to follow in its current form. There are three different math abstraction: coding theory, reduced-rank regression, and statistical geometry. This work transitions between the three without enough information or intuition to help the reader understand. This significantly limits the readability of this work.

(2). The simulation results show that the code choice affects performance under a rank constrained representation. However, it does not verify that the predicted directions are the ones the low-rank feature representation preserve during learning.

Questions for authors

Please see the comments under the critical weaknesses.

3 comments

Thank you for identifying the gap between showing that codes change classification error and showing that training recovers the predicted directions. We have added a direct experiment to address this point. We have also revised the exposition so that the connections between coding, regression, and geometry are easier to follow.

Regarding readability, the Introduction now uses a garment-classification example, and Figure 1 illustrates how two codes favor different feature directions. Section 2 explains how the code changes the weighting of class distinctions in squared loss and how the rank constraint determines which directions are retained. Section 3 then introduces Gaussian width through the expected largest class score and its connection to classification error. This gives the reader the meaning of the geometric quantity before presenting the exact risk identity.

To test whether training recovers the predicted directions, we trained factorized linear predictors from random initialization on labels sampled from the spherical affine model. The optimizer receives neither the population coefficients nor a spectral initialization. Across 240 selected fits, the normalized projector distance to the exact empirical optimum is below 0.00001. At rank one and 10 million training examples, mean overlap with the population direction predicted for the training code is 99.92% and 99.93% for the two codes, compared with 0.07% for the alternative code. Section 6, Figure 3, and Appendix M now report these comparisons. They distinguish close agreement with the empirical optimum from recovery of the population direction, and test the mechanism within the linear setting where the predictions apply. We also state that the large sample sizes do not establish practical sample efficiency.

To connect this result with the image experiments, Section 6 and Appendix K.3 now examine all 32 assignments of each base code. Although these assignments have identical spectra and Hamming-distance histograms, they produce different retained subspaces and test errors. Appendix K.3 also compares variation across codes with variation across training draws, using both raw and covariance-normalized coordinates. This provides broader evidence about the effect of code assignment, alongside the direct test of the theoretical predictions.

Reviewer_8FHmOpenReview ↗

Response to Rebuttal

Dear Authors:

Thanks for response. I still think the math in the current version of this work is difficult to follow. The connection between the three different math abstraction for this work is not clear.

After carefully considering the discussions under this rebuttal, I will maintain my original score.

We appreciate the reply. To address this, we have further smoothed the transitions to make the connection between the three mathematical abstractions (output coding, reduced-rank regression, and our geometric analysis) explicit.

Specifically, we revised the paragraph immediately after Equation (1) to show why output coding and reduced-rank regression arise together. Because the code assigns each class a target vector, fitting those targets by least squares while constraining all predictions to use the same rr features is precisely a reduced-rank regression problem. Solving it directly determines which feature directions training retains for each code.

Our geometric analysis then answers the remaining question: how accurately can we predict the original class using only those retained features? Since two codes can select different directions yet yield the same classification error, we now carry Figure 1 from the end of Section 2 directly into the opening of Section 3 to make this link concrete. Reduced-rank regression explains why one code selects the vertical direction while the other selects the horizontal direction; Section 3 then shows why, under the spherical affine model, the wider horizontal interval leads to lower classification error. We introduce Gaussian width at this exact point so readers can see how the same geometric comparison naturally extends to more than one retained direction.

We hope these revisions improve the paper's readability and clarify how the three mathematical abstractions connect.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Changes in the Revised Manuscript

We thank the reviewers for their thoughtful comments. Their feedback highlighted two priorities: explaining the motivation and mathematical argument more clearly, and showing directly whether training recovers the feature directions predicted by the theory. We have revised the paper with both points in mind.

The Introduction now uses a garment-classification example to explain why class distinctions compete for limited shared features, and Figure 1 illustrates how two codes can favor different directions. Sections 2–3 then connect the code, the training loss, the retained subspace, and classification error. We also distinguish the general regression analysis from the results that require the spherical affine model, and explain the relation to earlier work on assigning codewords to classes in Related Work.

To test the predicted directions directly, we added an experiment with linear predictors trained from random initialization (Section 6, Figure 3, and Appendix M). At rank one and the largest sample size, their mean overlap with the direction predicted for their own code exceeds 99.9%, compared with 0.07% for the alternative code. We also expanded the analysis of all 32 code assignments on frozen image features (Appendix K.3) and added an end-to-end CIFAR-100 experiment with ResNet-18 (Supplementary Section S12). In the latter, coding with LDA decoding improves modestly on one-hot regression, while softmax remains substantially better.

The Introduction now makes the contribution more explicit: the paper explains how output coding affects the information retained by a shared bottleneck. The Conclusion describes what this means in practice—evaluating codes on the target data at the intended bottleneck rank, with common training examples and decoding—alongside the scope of the theoretical and empirical results. We address each reviewer's specific concerns below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.