acceptodds
Under review as a conference paper at ICLR 2027

Generalization Analysis for Multi-Dimensional Classification

Abstract

Recent studies have experimentally demonstrated that multi-dimensional classification (MDC), where each example is represented by a single instance while associated with multiple class variables, can achieve empirical success in many application scenarios, however, the problem of theoretically understanding MDC remains under-explored. In an attempt to make up for the gap in the generalization theory of MDC, we establish an effective unified theoretical framework, which makes it possible to analyze the generalization of MDC using existing theoretical results. However, the generalization bounds induced by existing theoretical results are vacuous for MDC. To this end, we introduce two decomposition operators and exploit the Lipschitz continuity of loss functions to develop novel vector-contraction inequalities, and derive tight generalization bounds with a logarithmic dependency on the maximum number of classes and with square-root and logarithmic dependency on the number of dimensions, respectively. In addition, we derive generalization bounds for prediction models of different architectures, which reveal the impact of various architectures on generalization bounds. Our tight generalization bounds without strong assumptions explain the good generalization ability of MDC.

Primary area:
learning theory
Keywords:
Multi-Dimensional Classification, Generalization

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_aTH2OpenReview ↗
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
  1. The paper addresses a relevant theoretical question: how the number of output dimensions and classes affects generalization.
  2. It considers cross losses, both Hamming and exact-match surrogate losses, and provides detailed proofs.
  3. 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?

1 comment
AuthorsOpenReview ↗

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,andDisfaOes97, Oes10, WaterQuality, WQplants, Scm1d, and Disfa-$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 1010-fold cross-validation. We report the empirical generalization gap of the 00-11 Hamming loss, defined as the test risk minus the training risk and averaged over the ten folds, against q⋅kq\cdot k.

We use Binary Relevance with per-dimension ℓ2\ell_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⋅kq\cdot k. On the largest dataset, Disfa (n=13,095n=13{,}095), the gap remains at most 0.0020.002, which is consistent with the 1/n1/\sqrt 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.

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

This paper provides a generalization analysis for multi-dimensional classification problem. Although previous papers have addressed multi-label classification, no generalization analyses for MDC are given. The paper first derives a basic bound obtained by applying existing methods, showing that the bound is not tight enough. Then, the paper derives tighter bounds for ℓ2\ell_2 Lipschitz loss and ℓ∞\ell_\infty Lipscitz loss introducing outer and inner decomposition of functions.

Critical strengths
  • The paper gives a generalization analysis for MDC, providing a non-trivial bounds that cannot be obtained by applying previous results. The theoretical results are build upon reasonable assumptions.

Although the theoretical part are highly complex and I cannot follow the detail, they generally look like reasonable.

Critical weaknesses

There are many notation errors. Most of them seem easy to fix, but some needs more explanations.

I think the most confusing one is the definition of fj(x)f_j(\mathbf{x}) (line 129), which is defined as fj(x)=max⁡s∈[k]{hsj(x)}f_j(\mathbf{x}) = \max_{s\in [k]} \{h^j_s (\mathbf{x})\}. Since fjf_j is defined as a mapping from X\mathcal{X} to Yj\mathcal{Y}_j, I think that fj(x)=argmaxs∈[k]{hsj(x)}f_j(\mathbf{x}) = \mathrm{arg max}_{s\in [k]} \{h^j_s (\mathbf{x})\} is correct, and g(t)g(\mathbf{t}) also should be modified accordingly. However, such modification results in errors in proofs of main results. For example, line 1048 in the proof of lemma 9 uses the fact that gg is defined as max.

Other minor errors:

  • line 109: ℓ\ell is defined as X×Y→R+\mathcal{X} \times \mathcal{Y} \to \mathbb{R}_{+}, but it is used as Y×Y→R+\mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{+} in this paper.

  • Line 113: L\mathcal{L} seems not well-defined unless the domain of x\mathcal{x} and y\mathcal{y} are defined.

  • Line 130: max⁡s∈[k]{hsj(x)}=max⁡s∈[k]{wsj⊤ϕsj(x)}\max_{s \in [k]} \{ h_s^{j}(\mathbf{x}) \} = \max_{s \in [k]} \{ \mathbf{w}^{j\top}_s \phi_{s}^j(\mathbf{x})\} will not hold in general. We need some assumptions on the form of h.

  • The equation in line 760 seem something strange. How do you define jj? Where F\mathcal{F} is used?

  • Line 779 R(f)→R(ℓ)R(\mathbf{f}) \to R(\ell)?

  • Line 839 The definition of hih_i is not given.

  • Line 974 Assumption 6 does not exist.

Questions for authors

Is fj(x)=argmaxs∈[k]{hsj(x)}f_j(\mathbf{x}) = \mathrm{arg max}_{s\in [k]} \{h^j_s (\mathbf{x})\} correct? If so, how can we modify proofs using g(t)=max⁡s∈[k]tsg(\mathbf{t}) = \max_{s \in [k]} t_s?

2 comments
AuthorsOpenReview ↗

Response to Reviewer WPvB (Part 1)

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:

1. Response to Weakness and Question

We agree that simply replacing maxmax by argmaxargmax would cause the proof difficulties identified by the reviewer. Therefore, we use argmaxargmax only for the final categorical prediction, not as an input to the real-valued surrogate loss.

The previous operator g(t)=max⁡stsg(\boldsymbol t)=\max_s t_s has been replaced by the target-dependent margin operator $ g_y(\boldsymbol t) =t_y-\max_{s\ne y}t_s =\min_{s\ne y}(t_y-t_s). $ The surrogate loss is then defined as ℓb(gy(hj(x)))\ell_b(g_y(\boldsymbol h^j(x))), where ℓb\ell_b is a non-increasing convex loss. This formulation preserves the target-class identity and provides explicit upper bounds on the corresponding 00-11 classification losses.

The proofs have been modified using $ |g_y(\boldsymbol t)-g_y(\boldsymbol t')| \le\sqrt2\|\boldsymbol t-\boldsymbol t'\|_2 $,

$ |g_y(\boldsymbol t)-g_y(\boldsymbol t')| \le2\|\boldsymbol t-\boldsymbol t'\|_\infty $.

Corollary 6 now applies Maurer's contraction lemma to the sample-dependent maps gyijg_{y_i^j}. Lemma 9 uses the covering radius ϵ/2\epsilon/2, while Lemma 18 uses ϵ/(2μ)\epsilon/(2\mu). No Lipschitz analysis of argmaxargmax is required. The inner decomposition class and the entropy-integral structure remain unchanged; only constant factors are revised, without introducing additional qq or kk factors.

2. Response to Other minor errors

We thank the reviewer for carefully identifying these notation and definition issues. We have checked each item and revised the manuscript accordingly. Our detailed responses are as follows.

a) Line 109:

We agree that the original declaration ℓ:X×Y→R+\ell:\mathcal X\times\mathcal Y\to\mathbb R_+ was incompatible with its subsequent use as ℓ(f(x),y)\ell(\boldsymbol f(\boldsymbol x),\boldsymbol y), since the first argument is the prediction output rather than the original input. The revised text distinguishes the discrete classification loss from the real-valued surrogate. In particular, the 00-11 loss is now defined on Y×Y\mathcal Y\times\mathcal Y, while the scalar base surrogate is defined as ℓb:R→R+\ell_b:\mathbb R\to\mathbb R_+ and acts on a multiclass margin. The aggregate Hamming and matching surrogates act on the target-dependent margin vector, not directly on the original input x\boldsymbol x.

b) Line 113:

We agree that the original set-builder notation did not adequately specify that L\mathcal L is a class of loss functions. We now define its elements explicitly as functions on X×Y\mathcal X\times\mathcal Y: $ \mathcal L= \left\{ (\boldsymbol x,\boldsymbol y)\mapsto \ell \left(\boldsymbol f_{\boldsymbol y}(\boldsymbol x),\boldsymbol y\right): \boldsymbol f\in\mathcal F \right\}. $ The domains X\mathcal X and Y\mathcal Y are defined at the beginning of the Preliminaries. Thus, L\mathcal L is now a well-defined function class rather than an unspecified collection of loss values.

c) Line 130:

We agree that the equality $ \max_s h_s^j(\boldsymbol x) =\max_s\boldsymbol w_s^{j\top}\phi_s^j(\boldsymbol x) $ would not hold without an explicit assumption on the form of hsjh_s^j. The revised model definition directly assumes $ h_s^j(\boldsymbol x) =\langle\boldsymbol w_s^j,\phi_s^j(\boldsymbol x)\rangle $ within a fixed feature family, together with the global joint norm constraint ∑j,s∣wsj∣22≤Λ2\sum_{j,s}\\|\boldsymbol w_s^j\\|_2^2\le\Lambda^2. Moreover, argmaxargmax is used only for the final categorical prediction, while the surrogate analysis uses target-dependent multiclass margins. Hence, the questioned equality is no longer presented as an unjustified general identity.

d) Line 760:

We have rewritten this definition to make all quantifiers explicit. For 1≤p<∞1\le p<\infty, the covering number is now defined as the smallest integer mm for which there exist vectors v1,…,vm∈Rn\boldsymbol v^1,\ldots,\boldsymbol v^m\in\mathbb R^n such that, for every f∈Ff\in\mathcal F, there exists j∈[m]j\in[m] satisfying $ \left( \frac1n\sum_{i=1}^n|f(\boldsymbol x_i)-v_i^j|^p \right)^{1/p}\le\epsilon. $ Here vijv_i^j denotes the ii-th coordinate of vj\boldsymbol v^j, and jj is the index of the covering center selected for the particular function ff. This also makes explicit how F\mathcal F enters the definition. We corrected the exponent from PP to pp and separately stated the p=∞p=\infty condition as $ \max_{i\in[n]}|f(\boldsymbol x_i)-v_i^j|\le\epsilon, $ again for some j∈[m]j\in[m] depending on ff.

e) Line 779:

It is a typographical error in the risk notation. We have revised it and make the notation consistent with the predictor-indexed risks R(f)R(\boldsymbol f) and R^D(f)\widehat R_D(\boldsymbol f) defined in the Preliminaries.

AuthorsOpenReview ↗

Response to Reviewer WPvB (Part 2)

f) Line 839:

We have expanded the lemma statement so that hih_i is defined formally. Specifically, for a Hilbert space (H,∣⋅∣2)(\mathcal H,\\|\cdot\\|_2) with a specified orthonormal basis, we now assume that, for every i∈[n]i\in[n], the map hi:H→Rh_i:\mathcal H\to\mathbb R satisfies

$ |h_i(\boldsymbol u)-h_i(\boldsymbol v)| \le L\|\boldsymbol u-\boldsymbol v\|_2, \quad \forall \boldsymbol u,\boldsymbol v\in\mathcal H. $

We also explicitly state that ϵ1,…,ϵn\epsilon_1,\ldots,\epsilon_n are independent Rademacher variables, that (ϵij)(\epsilon_{ij}) is an independent doubly indexed Rademacher sequence, and that fj(xi)f_j(\boldsymbol x_i) is the jj-th coordinate with respect to the specified basis.

For the application to multiclass margins, we further clarify that, conditioned on the observed sample, we set hi=gyijh_i=g_{y_i^j}. These sample-dependent maps are fixed before taking the expectation over the Rademacher variables and are 2\sqrt2-Lipschitz in ℓ2\ell_2. Thus, the contraction lemma legitimately allows the composing map to vary with the sample index ii.

g) Line 974:

We have replaced the numerical reference with an explicit reference to the ℓ2\ell_2-Lipschitz assumption. We also checked the manuscript for similar residual numerical assumption references and replaced them with automatic cross-references to the corresponding labelled assumptions. Therefore, the reference to a nonexistent Assumption 6 has been removed.

The covering-number and contraction-lemma revisions make the intended quantifiers and sample dependence explicit without changing the resulting complexity bounds or convergence rates.

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.

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

This paper develops a general generalization framework for multi-dimensional classification using Rademacher complexity and decomposition-based vector contraction inequalities. It claims O~(q/n)\widetilde O(\sqrt{q/n}) bounds for ℓ2\ell_2-Lipschitz losses and O~(1/n)\widetilde O(1/\sqrt n) bounds for ℓ∞\ell_\infty-Lipschitz losses, where qq is the number of dimensions ,with applications to FNNs and Transformers.

Critical strengths
  1. The paper establishes a general theoretical framework for multi-dimensional classification, enabling generalization analysis via existing tools for multi-dimensional classification and multi-classification.

  2. The paper is comprehensive, deriving lower bounds and comparisons with related work.

  3. The stated bounds apply to architecture-specific bounds for FNNs and Transformers, which are popular in deep learning.

Critical weaknesses
  1. In Sections 2.1–2.2, the paper defines y^j\hat y_j using arg⁡max⁡shjs(x)\arg\max_s h_{js}(x), but defines the surrogate loss on fj(x)=max⁡shjs(x)f_j(x)=\max_s h_{js}(x). Since fj(x)f_j(x) does not contain the predicted class s∗s^*, I think the stated multiclass loss ℓb(fj(x),yj)\ell_b(f_j(x),y_j) is not well-defined.

  2. In Appendix A.4.4, the proof replaces the supremum over independently constrained parameters wjsw_{js} by Λ∣∑i,j,sϵijsϕjs(xi)∣\Lambda\\|\sum_{i,j,s}\epsilon_{ijs}\phi_{js}(x_i)\\|. Under Assumption 3, however, each wjsw_{js} is constrained separately by ∣wjs∣≤Λ\\|w_{js}\\| \leq \Lambda. Then, the supremum should equal Λ∑j,s∣∑iϵijsϕjs(xi)∣\Lambda\sum_{j,s}\\|\sum_i\epsilon_{ijs}\phi_{js}(x_i)\\|, which gives B/nB/\sqrt{n}, rather than the claimed B/nqkB/\sqrt{nqk}. The latter rate seems to require an additional assumption such as ∑j,s∣wjs∣22≤Λ2\sum_{j,s}\\|w_{js}\\|_2^2\leq\Lambda^2. Since Eq. (12) is essential for cancelling the qk\sqrt{qk} factor, this issue appears to affect the main bounds in Theorems 12, 20, and 24.

  3. In Appendix A.6.2 Eq. (18), ∣∑i,uϵiuXi⊤piu∣\\|\sum_{i,u}\epsilon_{iu}X_i^\top p_{iu}\\|, where piu=softmax⁡(XiWu,QK⊤x[CLS])p_{iu}=\operatorname{softmax}(X_iW_{u,QK}^\top x_{[CLS]}), is replaced by $\|\sum_{i,u}\epsilon_{iu}X_i^\top\| \sup_{i,u}\|p_{iu}\|$ (the first norm is 2,∞{2,\infty} norm, and the second norm is ℓ1\ell_1 norm), However, the inequality ∣Px∣≤∣P∣∣x∣\\|Px\\|\leq\\|P\\| \\|x\\| (on the right-hand side, the first norm is 2,∞{2,\infty} norm, and the second norm is ℓ1\ell_1 norm) applies only when the same vector xx multiplies the summed matrix, whereas here piup_{iu} varies across samples and heads and depends on the optimized attention parameters. The condition ∣piu∣=1\\|p_{iu}\\|=1 (ℓ1\ell_1 norm) can only be applied termwise, yielding the generic bound $ \|\sum_{i,u}\epsilon_{iu}X_i^\top p_{iu}\| \leq \sum_{i,u}\|X_i^\top\|_{2,\infty}, $ which does not provide the claimed 1/nH1/\sqrt{nH} rate. Consequently, Eq. (18), Eq. (19), and the resulting Transformer bound in Theorem 24 appear unsupported without an additional argument controlling the attention-weight class.

Questions for authors
  1. Could the authors give more detailed explanations of the definition of ℓb(fj(x),yj)\ell_b(f_j(x),y_j)?

  2. Could the authors give more detailed explanations of the derivations of Eq.(12) and Eq.(18)?

  3. In Appendix A.7.6, the authors state that ``one cannot find a similar result in Srebro et al. (2010).'' However, Lemma A.2 of the extended version of Srebro et al. (2010) (https://arxiv.org/pdf/1009.3896) explicitly states $ N_{\infty}(\alpha,H,n) \leq ( \frac{2eBn} {\alpha,fat_{\alpha}(H)} )^{fat_{\alpha}(H)}, $ which directly implies the bound used in Lemma 22(a) of Lei et al. (2019). Could the authors clarify why they regard the citation in Lei et al. (2019) as a mis-citation?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Bf7y (Part 1)

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:

1. Response to Weakness 1 and Question 1

We thank the reviewer for pointing out that ℓb(fj(x),yj)\ell_b(f_j(x),y^j) was not well-defined. We agree that fj(x)=max⁡shsj(x)f_j(x)=\max_s h_s^j(x) does not retain the predicted-class identity.

We now define ℓb\ell_b as a univariate, non-increasing convex loss acting on the multiclass margin $ m_{y^j}(\boldsymbol h^j(x)) =h_{y^j}^j(x)-\max_{s\ne y^j}h_s^j(x). $ The revised surrogates are ℓH=1q∑jℓb(myj)\ell_H=\frac1q\sum_j\ell_b(m_{y^j}), ℓM=max⁡jℓb(myj)\ell_M=\max_j\ell_b(m_{y^j}), where ℓb\ell_b can be hinge loss [1−m]+[1-m]_+, logistic loss log⁡(1+e−m)\log(1+e^{-m}), or exponential loss e−me^{-m}. Thus, the loss explicitly depends on the target-class score and all competing scores through their maximum.

Misclassification implies myj≤0m_{y^j}\le0. Consequently, hinge and exponential surrogates upper-bound the corresponding 00-11 losses directly, and logistic surrogates satisfy ℓ0-1≤ℓ/log⁡2\ell^{0\text{-}1}\le\ell/\log2.

Propositions 5 and 17 and the subsequent proofs have been updated accordingly. Since the margin operator is 2\sqrt2-Lipschitz in ℓ2\ell_2 and 22-Lipschitz in ℓ∞\ell_\infty, the contraction and covering arguments remain valid with adjusted constants and no additional qq or kk dependence.

2. Response to Weakness 2 and Question 2

We agree that, under independent per-coordinate constraints, the correct supremum is

Λ∑j,s∣vj,s∣2\Lambda\sum_{j,s}\\|v_{j,s}\\|_2,

vj,s=∑iϵijsϕsj(xi)v_{j,s}=\sum_i\epsilon_{ijs}\phi_s^j(x_i),

which leads to an O(ΛA/n)O(\Lambda A/\sqrt n) bound rather than O(ΛA/nqk)O(\Lambda A/\sqrt{nqk}). The original Eq. (12) was therefore unjustified.

To retain the stronger upper-bound rates, we have explicitly adopted a global joint constraint,

$ \sum_{j,s}\|\boldsymbol w_s^j\|_2^2\le\Lambda^2, $

together with fixed feature maps. The revised proof uses

$ \sup_{\overline{\boldsymbol w}} \sum_{j,s}\langle\boldsymbol w_s^j,v_{j,s}\rangle =\Lambda\left(\sum_{j,s}\|v_{j,s}\|_2^2\right)^{1/2}, (\|\overline{\boldsymbol w}\|_2\le\Lambda) $

which gives $ \widetilde{\Re}_{nqk} \le \frac{\Lambda A}{\sqrt{nqk}}. $ Accordingly, the upper-bound rates in Theorems 12 and 20 are retained under this stronger and explicitly stated assumption. We have also clarified the resulting scope: these rates are not claimed for independent per-coordinate constraints with an unchanged constant.

3. Response to Weakness 3 and Question 2

We thank the reviewer for identifying this issue. We agree that piup_{iu} varies across samples and heads and depends on the optimized attention parameters. Therefore, it cannot be extracted as a common vector from the Rademacher sum. We have replaced that step with a joint parameter-covering argument.

First, we decompose the output perturbation into four parts, corresponding to the readout vector, output matrix, value matrix, and query-key matrix. The attention perturbation is bounded only within each individual sample, using the ℓ1/ℓ∞\ell_1/\ell_\infty Lipschitz property of softmax. No common attention vector is extracted from any sum.

Second, we construct a joint ℓ∞\ell_\infty cover sequentially in the order WQK→WV→WC→wW_{QK}\to W_V\to W_C\to w, which accounts for the dependencies of p,z,Yp,z,Y on the preceding parameters. The cover is based on a direct ℓ2\ell_2-ball sparsification argument and provides explicit constants for all four perturbation classes. In particular, the readout-weight constant includes the required Λ2\Lambda^2 factor. These constants contain only logarithmic dependence on qkHqkH and no polynomial dependence on the sequence length TT.

The perturbation radii mentioned above are simply the accuracy levels of these covers. They are chosen so that each of the four error contributions is at most ϵ/4\epsilon/4, giving total output error at most ϵ\epsilon. This yields a joint covering-number bound of order A+CR2/ϵ2A+C_R^2/\epsilon^2.

Third, we apply Dudley's entropy integral with an explicitly valid truncation level and define an attention-capacity constant Catt(N)C_{\mathrm{att}}(N) containing the resulting covering and logarithmic terms. This gives an expanded Rademacher complexity bound of order Catt(N)/NC_{\mathrm{att}}(N)/\sqrt N. The analysis uses global joint parameter constraints and a fixed, norm-bounded CLS vector.

Finally, substituting this bound into the multi-head and MDC decompositions and the current Lemma 18 yields the generalization guarantee. The resulting bound has an n−1/2n^{-1/2} leading rate, linear dependence on HH, only logarithmic dependence on q,kq,k, and no polynomial dependence on the sequence length TT, while avoiding any merging of independently parameterized attention suprema.

AuthorsOpenReview ↗

Response to Reviewer Bf7y (Part 2)

4. Response to Question 3

I agree that Lemma A.2 of the extended version of [1] states a bound strong enough to imply the one used in Lemma 22(a) of [2]. My concern is therefore not about the formal implication. Rather, I am not yet convinced that Lemma A.2 itself can be relied upon as a fully established result, for the following reasons.

a) The significance of obtaining a logarithmic power below 2.

[4] proved that finite fat⁡γ(F)\operatorname{fat}_\gamma(\mathcal{F}) implies $ H(\mathcal{F},2\gamma,n)=O(\log^2 n), $ and explicitly asked whether the log⁡2n\log^2 n dependence could be improved to O(log⁡n)O(\log n). [5] subsequently obtained O(log⁡1+εn)O(\log^{1+\varepsilon}n), but only at a further enlarged scale, while the question of reducing the exponent to 11 remained open. Thus, obtaining a logarithmic power strictly below 22, particularly reducing it to 11, was a longstanding open problem before the new work.

b) My concern about Proposition 7 in A.2 of [1]

Proposition 7 is stated without what I would regard as a sufficiently clear proof. It claims that, for H⊆0,…,kX\mathcal{H}\subseteq\\{0,\ldots,k\\}^{\mathcal{X}} with fat⁡2(H)=d\operatorname{fat}_2(\mathcal{H})=d,

$ N_\infty(1/2,\mathcal{H},n)\leq \sum_{i=0}^{d}\binom{n}{i}k^i. $ However, I have not been able to identify this statement in the cited paper by [4]. Their corresponding Lemma 3.2 instead gives the substantially weaker, quasi-polynomial packing bound $ M_{\ell_\infty}(2,\mathcal{F}) < 2(nb^2)^{\lceil\log y\rceil}$, $ y=\sum_{i=1}^{d}\binom{n}{i}b^i. $ This concerns a packing number and contains an additional log⁡y\log y in the exponent. As far as I can see, it does not imply Proposition 7.

There also appears to be a more concrete tension between Proposition 7 and the known lower bounds for disambiguating partial concept classes. [6] construct VC-dimension-one partial concept classes requiring disambiguations of size n(log⁡n)1−o(1)n^{(\log n)^{1-o(1)}}. If we map 0,1,⋆0,1,\star to 0,2,10,2,1, respectively, we obtain a three-valued class with fat⁡2=1\operatorname{fat}_2=1, for which Proposition 7 would predict

$ N_\infty(1/2)\leq2n+1. $

On the other hand, every 1/21/2-cover of this class induces a disambiguation of the original partial concept class, apparently leading to the lower bound n(log⁡n)1−o(1)n^{(\log n)^{1-o(1)}}. This seems to conflict directly with the displayed upper bound.

For these reasons, I find the status of Proposition 7 unclear, and consequently I would be cautious about treating the proof of A.2 as complete without an independent justification of this combinatorial step.

c) Relationship to the new paper

The new paper [3] directly bounds empirical ℓ∞\ell_\infty covering numbers without using the standard packing-number detour. In terms of $ \gamma^\star=\inf{\gamma:\operatorname{fat}_\gamma(\mathcal{F})<\infty}, $ it obtains O(log⁡2n)O(\log^2n) in the intermediate regime and O(log⁡n)O(\log n) above 2γ⋆2\gamma^\star, together with an Ω(log⁡2−o(1)n)\Omega(\log^{2-o(1)}n) lower bound below γ⋆\gamma^\star. It leaves the precise behavior in γ⋆<γ≤2γ⋆\gamma^\star<\gamma\le2\gamma^\star open.

If A.2 were valid as stated, it would give O(log⁡n)O(\log n) whenever fat⁡α(F)<∞\operatorname{fat}_\alpha(\mathcal{F})<\infty, and hence throughout α>γ⋆\alpha>\gamma^\star. It would therefore (i) immediately resolve the remaining intermediate regime and (ii) already have settled Alon et al.'s metric-entropy conjecture for uniform Glivenko-Cantelli classes. This is another reason why I think the proof and provenance of A.2 deserve clarification before it is used to close the discussion.

d) Subsequent work by Lei and collaborators

It is also worth noting that the relevant later works use the O(log⁡2n)O(\log^2n) bound rather than the stronger O(log⁡n)O(\log n) consequence of A.2. These include [7]-[10]. This pattern suggests that the issue may already have been recognized in this line of work, although it does not establish exactly when each author became aware of it.

Overall, I think the most constructive next step would be to clarify the proof status of Proposition 7 and Lemma A.2. Until that is done, it seems safer either to supply an independent proof of the bound used in Lemma 22(a), or to rely on the established O(log⁡2n)O(\log^2n) result and examine the resulting logarithmic powers.

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.

AuthorsOpenReview ↗

Response to Reviewer Bf7y (Part 3)

[1] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic Rates for Learning with a Smooth Loss. arXiv 2010.

[2] Yunwen Lei, Umit Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-Dependent Generalization Bounds for Multi-Class Classification. TIT 2019.

[3] Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, and Tom Waknine. Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale. arXiv 2026.

[4] Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, and David Haussler. Scale-Sensitive Dimensions, Uniform Convergence, and Learnability. JACM 1997.

[5] Mark Rudelson and Roman Vershynin. Combinatorics of Random Processes and Sections of Convex Bodies. Annals of Mathematics, 2006.

[6] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A Theory of PAC Learnability of Partial Concept Classes. FOCS 2022.

[7] L. Wu, A. Ledent, Y. Lei, and M. Kloft. Fine-grained Generalization Analysis of Vector-Valued Learning. AAAI 2021.

[8] W. Mustafa, Y. Lei, A. Ledent, and M. Kloft. Fine-grained Generalization Analysis of Structured Output Prediction. IJCAI 2021.

[9] Hieu et al. Generalization Analysis for Deep Contrastive Representation Learning. AAAI 2025.

[10] Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuan Zhou. Generalization Analysis for Contrastive Representation Learning. ICML 2023.

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

The paper studies capacity-based generalization guarantees for multi-dimensional classification, where each example has several categorical outputs. It introduces outer and inner decomposition operators to relate the loss class to scalar coordinate classes. Using covering-number and vector-contraction arguments, it claims bounds with a square-root dependence on the number of output dimensions for \ell_2-Lipschitz losses and only logarithmic dependence on the numbers of dimensions and classes for \ell_\infty-Lipschitz losses. The paper also presents an ERM lower-bound construction and specializations to feedforward networks and Transformers. The proposed dependence on output structure would be valuable if established, but the current prediction representation and key complexity calculations leave the main claims unsupported.

Critical strengths
  1. The paper addresses a meaningful theoretical question. Understanding how generalization depends on both the number of output dimensions and the number of classes per dimension is relevant to multi-dimensional classification. Distinguishing the consequences of \ell_2- and \ell_\infty-Lipschitz losses is also a useful organizing principle. The effort to connect this analysis to Hamming and exact-match objectives and to neural architectures gives the work a clear intended scope. However, this motivation does not compensate for the foundational issues below.
Critical weaknesses
  1. The analyzed prediction representation does not retain the information needed for categorical prediction. Section 2.1 correctly defines the predicted class through an argmax, but then replaces the class prediction with f_j(x)=\max_s h_s^j(x) in Eq. (1). The maximum score is a real number, not the identity of the maximizing class. For example, the score vectors (1,0) and (0,1) have the same maximum but predict different classes. Consequently, for a fixed target label, a loss depending only on this maximum and the label cannot distinguish these two predictions. Section 2.2 nevertheless defines Hamming and matching surrogates through \ell_b(f_j(x),y^j), without explaining how class-specific scores or margins are recovered. The manuscript therefore needs a precise connection between the real-valued class actually analyzed and the classification risks it seeks to control. Replacing the maximum by an argmax would not automatically repair the subsequent Lipschitz analysis.
  2. The Rademacher-complexity calculations used to obtain the claimed rates are not valid for the stated class. In Appendix A.4.3, the subclass used for Eq. (10) consists of functions explicitly fixed at h_s^{*j}(x)=B. Under Definition 1, this singleton class has empirical Rademacher complexity zero, because the expectation of the signed sum is zero. The derivation then introduces a supremum over weights that is absent from the fixed subclass and obtains a positive lower bound. A suitably justified symmetric subclass might repair this particular step, but that is not the construction given. More seriously, Appendix A.4.4, Eq. (12), replaces a supremum over separately parameterized weights w_s^j by a single norm of a sum over all coordinates. Under independent per-coordinate norm constraints, the relevant expression for fixed features is sup⁡∥wsj∥2≤Λ∑j,s⟨wsj,∑iϵijsϕsj(xi)⟩=Λ∑j,s∥∑iϵijsϕsj(xi)∥2,\sup_{\|w_s^j\|_2\leq\Lambda} \sum_{j,s}\left\langle w_s^j,\sum_i\epsilon_{ijs}\phi_s^j(x_i)\right\rangle = \Lambda\sum_{j,s}\left\|\sum_i\epsilon_{ijs}\phi_s^j(x_i)\right\|_2,

rather than \Lambda|\sum_{i,j,s}\epsilon_{ijs}\phi_s^j(x_i)|_2. A concrete counterexample also satisfies a per-dimension Frobenius-norm constraint. Set n=1, q=4, k=2, use fixed scalar features \phi_s^j(x)=A, and allow w_1^j\in[-\Lambda,\Lambda] independently while fixing w_2^j=0. Each dimension's weight vector has norm at most \Lambda, yet this subclass has empirical complexity B/2 on the expanded sample, where B=\Lambda A. This exceeds the claimed upper bound B/\sqrt{nqk}=B/\sqrt{8}. Thus Eq. (12) does not follow from the stated constraints. It is used directly in the proofs of Theorems 12 and 20, so the advertised dependence on output dimensions and class counts is not established by the current argument.

Questions for authors
  1. Prediction and loss formulation: What is the precise score representation supplied to the surrogate loss, and how does it retain the identity of the target and predicted classes? Please provide an explicit multiclass surrogate and explain whether the contraction and covering-number arguments remain valid for that representation.
  2. Core complexity bound: How should Eq. (12) handle the independently parameterized coordinates and the counterexample above? If a shared parameter vector or a joint norm constraint across dimensions and classes is intended, please state it explicitly and explain how it changes the scope and rates of the theorems. Please also clarify whether the feature maps are fixed or learned; a norm bound on their outputs alone does not justify moving a supremum over learned maps outside the Rademacher expectation. For Eq. (10), what admissible non-singleton subclass supplies the claimed positive complexity?
  3. Lower-bound clarification: In Appendix A.4.5, are the sample-dependent binary “labels” auxiliary shattering codes used to select a hypothesis, or actual target labels? The former need not violate a fixed i.i.d. sampling model. Please state the fixed population distribution, an admissible nonnegative loss, and the ERM selection rule precisely, and distinguish existence of a poorly generalizing ERM solution from a statement about every ERM solution. A constant shift could address negative loss values without changing the generalization gap; the essential issue is whether the full construction establishes Theorem 14 under the stated model.
2 comments
AuthorsOpenReview ↗

Response to Reviewer wMP2 (Part 1)

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:

1. Response to Weakness 1 and Question 1

We thank the reviewer for identifying this issue. We agree that max⁡shsj(x)\max_s h_s^j(x) discards the predicted-class identity and is insufficient for defining a multiclass surrogate. Simply replacing max⁡\max by argmaxargmax would also be inappropriate, since argmaxargmax is discrete and not Lipschitz.

We have revised Sections 2.1--2.2 to separate categorical prediction from the real-valued surrogate analysis. The complete score vector hj(x)\boldsymbol h^j(x) is retained, while argmaxargmax is used only for the final prediction. For a target class yjy^j, we define $ m_{y^j}(\boldsymbol h^j(x)) =h_{y^j}^j(x)-\max_{s\ne y^j}h_s^j(x), $ and introduce the explicit surrogates ℓH=1q∑jℓb(myj)\ell_H=\frac1q\sum_j\ell_b(m_{y^j}), ℓM=max⁡jℓb(myj)\ell_M=\max_j\ell_b(m_{y^j}), where ℓb\ell_b is a non-increasing convex loss, such as hinge, logistic, or exponential loss.

Misclassification implies myj≤0m_{y^j}\le0. Thus, hinge and exponential surrogates upper-bound the corresponding 00-11 losses directly, while logistic surrogates satisfy ℓ0-1≤ℓ/log⁡2\ell^{0\text{-}1}\le\ell/\log2. This establishes an explicit connection between the surrogate and classification risks.

The proofs remain valid without applying Lipschitz analysis to argmaxargmax. The margin operator gy(t)=min⁡s≠y(ty−ts)g_y(\boldsymbol t)=\min_{s\ne y}(t_y-t_s) satisfies $|g_y(\boldsymbol t)-g_y(\boldsymbol t')| \le\sqrt2\|\boldsymbol t-\boldsymbol t'\|_2$,

$|g_y(\boldsymbol t)-g_y(\boldsymbol t')| \le2\|\boldsymbol t-\boldsymbol t'\|_\infty $.

Accordingly, we have updated Propositions 5 and 17, applied contraction to the sample-dependent maps gyijg_{y_i^j} in Corollary 6, and used covering radii ϵ/2\epsilon/2 and ϵ/(2μ)\epsilon/(2\mu) in Lemmas 9 and 18, respectively. The inner decomposition class remains unchanged; only constant factors are affected, with no additional dependence on qq or kk.

2. Response to Weakness 2 and Question 2

We thank the reviewer for identifying these issues and agree that the original Eq. (12) is invalid under independent per-coordinate constraints. The counterexample is correct, so the original bound cannot be retained without strengthening the assumption.

We have revised Assumption 3 and the corresponding proofs as follows.

First, the feature family Φ=(ϕsj)j,s\Phi=(\phi_s^j)_{j,s} is now explicitly fixed, and the weights satisfy the global joint constraint

∑j=1q∑s=1k∣wsj∣22≤Λ2\sum_{j=1}^q\sum_{s=1}^k\\|\boldsymbol w_s^j\\|_2^2\le\Lambda^2.

Thus, there is no supremum over learned feature maps in the Rademacher analysis. Any outer supremum over Φ\Phi is only a worst case over separately fixed feature families.

Second, with w‾=(wsj)j,s\overline{\boldsymbol w}=(\boldsymbol w_s^j)_{j,s} and

vj,s=∑iϵijsϕsj(xi)v_{j,s}=\sum_i\epsilon_{ijs}\phi_s^j(x_i), Eq. (12) now uses the correct stacked-weight identity

$\sup_{\overline{\boldsymbol w}} \sum_{j,s}\langle\boldsymbol w_s^j,v_{j,s}\rangle =\Lambda\left(\sum_{j,s}\|v_{j,s}\|_2^2\right)^{1/2}. (\|\overline{\boldsymbol w}\|_2\le\Lambda) $

This yields

$ \widetilde{\Re}_{nqk} \le \frac{\Lambda A}{\sqrt{nqk}} \le \frac{B}{\sqrt{nqk}}. $

Therefore, the upper-bound rates in Theorems 12 and 20 are retained under these explicit fixed-feature and global joint-norm assumptions.

Finally, Eq. (10) now uses an admissible non-singleton subclass. With fixed features ϕsj(x)=Ae1\phi_s^j(x)=A\boldsymbol e_1, we consider all sign patterns η∈−1,+1qk\eta\in\\{-1,+1\\}^{qk} and set

$ \boldsymbol w_s^j(\eta) =\eta_{j,s}\frac{\Lambda}{\sqrt{qk}}\boldsymbol e_1. $

Every member satisfies the global constraint, and the resulting 2qk2^{qk}-function subclass gives $ \widetilde{\Re}_{nqk} \ge \frac{B}{2\sqrt{2nqk}}$,

Hence, the revised construction is non-singleton, symmetric, and consistent with the global joint constraint.

AuthorsOpenReview ↗

Response to Reviewer wMP2 (Part 2)

3. Response to Question 3

We thank the reviewer for requesting these clarifications. We have rewritten Theorem 14 and Appendix A.4.5 so that the population distribution, loss, hypothesis class, and ERM selection rule are all fixed explicitly before the training sample is drawn.

The construction uses a fixed target vector y⋆=(1,…,1)y^\star=(1,\ldots,1) and a uniform distribution PP over the hard support, with every pair (xi,y⋆)(x_i,y^\star) determined before sampling. The binary vectors in the proof are only auxiliary shattering codes used to select hypotheses, they are not the target labels in this fixed sampling model. We also use a nonnegative convex loss ℓ+(v,y)=ℓ0(v)+ε\ell^+(v,y)=\ell_0(v)+\varepsilon, which satisfies ℓ+(0,y)=0\ell^+(0,y)=0, is 88-Lipschitz, and is bounded by M=8(1+ε)M=8(1+\varepsilon). The target-margin bound is B=1+εB=1+\varepsilon, so μ,B,M=O(1)\mu,B,M=O(1).

For each training multiset DD, we choose the auxiliary code ci(D)=0c_i(D)=0 for observed support points and ci(D)=1c_i(D)=1 for unobserved points, and select A(D)=f(c(D))A(D)=f^{(c(D))}. Every training occurrence has code zero and hence loss zero. Since the loss is nonnegative, this already minimizes the empirical risk, so A(D)A(D) is an ERM minimizer. Every unobserved point has loss 2ε2\varepsilon, and at least half of the support is unobserved when n≤N/2n\le N/2. Therefore, $ R(A(D))-\widehat R_D(A(D))\ge\varepsilon. $ This holds with probability one over D∼PnD\sim P^n in the stated regime. The all-zero code also gives an ERM and population minimizer, which makes clear why the conclusion is existential over ERM minimizers and cannot be strengthened to every ERM minimizer.

Every constructed hypothesis uses fixed features and satisfies $ \sum_{j,s}\|w_s^j\|_2^2 =\|W(c)\|_F^2 \le1+\frac q{13}. $ Thus, the constructed class is contained in the globally joint-norm-bounded class required by Assumption 3. Taking $ \varepsilon=\sqrt{\frac q{26n}} $ gives N=2nN=2n and $ R(A(D))-\widehat R_D(A(D)) \ge\sqrt{\frac q{26n}} =\Omega\left(\sqrt{\frac qn}\right). $ On the same constructed class, Theorem 12 provides an O~(q/n)\widetilde O(\sqrt{q/n}) upper bound. Hence, in this normalized existential setting, the qq-dependence of the upper and lower bounds matches up to logarithmic factors. The result is not claimed for every surrogate loss or every ERM solution.

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.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.