- Rating
- 3
- Confidence
- 1
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies generalization bounds for multi-dimensional classification (MDC), where each example is treated as having several categorical labels. It introduces decomposition operators and vector-contraction inequalities to reduce the bounds’ dependence on the number of output dimensions and classes. It also extends the analysis to feedforward networks and Transformers.
The theoretical analysis is extensive. However, simple toy experiments showing how the generalization gap changes with the number of dimensions and classes would help readers build intuition and better understand the theoretical results.
Critical strengths
- The paper addresses a relevant theoretical question: how the number of output dimensions and classes affects generalization.
- It considers cross losses, both Hamming and exact-match surrogate losses, and provides detailed proofs.
- The architecture-specific analysis attempts to connect the general framework to neural networks.
Critical weaknesses
The paper is about explaining empirical findings of MDC, but leaves experimental verification to future work. Although experiments are not essential for a theoretical contribution, simple toy experiments would help readers build intuition and connect the bounds to observed behavior. Moreover, improved asymptotic dependence alone does not show that the bounds are informative for practical MDC models, especially since the paper acknowledges that its neural-network bounds can be vacuous. The claim of explaining empirical success therefore needs stronger support or more cautious wording.
Questions for authors
Could the authors provide simple experiments or plots to illustrate the trends predicted by the bounds and help readers build intuition?
Response to Reviewer aTH2
Thank you for your constructive comments and active interest in helping us improve the quality of the paper.
The following are our responses to the Questions:
Response to Weakness and Question
We thank the reviewer for this suggestion. We have added a dedicated illustrative study with six plots to Appendix A.7.4 (Figure 1, Table 1). We evaluate six MDC benchmark datasets$-Oes97,Oes10,WaterQuality,WQplants,Scm1d,andDisfa-$with sample sizes ranging from 334 to 13,095, 7-16 dimensions, and both homogeneous and heterogeneous class spaces. For each dataset, we randomly select dimension subsets of varying sizes and run the complete learning pipeline on each induced sub-problem. Each sub-problem is evaluated using the benchmark's standard 10-fold cross-validation. We report the empirical generalization gap of the 0-1 Hamming loss, defined as the test risk minus the training risk and averaged over the ten folds, against q⋅k.
We use Binary Relevance with per-dimension ℓ2-regularized logistic regression. This simple decomposable learner matches the hypothesis structure analyzed in the paper while avoiding deep-model confounders. As shown in Figure 1, least-squares logarithmic fits capture the overall trend on all six datasets: the empirical gap grows approximately logarithmically with q⋅k. On the largest dataset, Disfa (n=13,095), the gap remains at most 0.002, which is consistent with the 1/n factor multiplying the logarithmic term in Theorem 20.
These experiments provide illustrative support for the logarithmic dependence predicted by Theorem 20, rather than a numerical certification of the asymptotic bound. Moreover, Theorem 20 applies to arbitrary dimension subsets, so the randomly selected sub-problems evaluated here fall within its scope. We have also revised the Future directions paragraph to clarify that the current results provide partial validation and that further experiments on more datasets and with more MDC methods will be conducted.
We have carefully addressed the issues raised by the reviewer in the revised manuscript and have uploaded the revised paper for your review. If you have any further questions or concerns, please do not hesitate to contact us. We would greatly appreciate your updated evaluation and any additional feedback.