- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes a new way to bound weighted errors of the empirical distribution (built from i.i.d. samples over categories), where the weights may depend on the data. The main result (Theorem 3.1) centers the weights at a constant and splits the error in two. One of these parts covers unobserved categories and is controlled by the expected missing mass. Taking as the median of the observed weights gives a leading term (coined "effective sparsity"), which is claimed to remove the or dependence of classical bounds. The paper proposes two applications: (i) in robustness-based generalization bounds, a new uncertainty term replaces that of recent bounds with one experiment on ImageNet reporting it half as large, and (ii) in off-policy evaluation for POMDPs, the claim is that, under sparsity conditions, the dependence on history size improves from exponential to polynomial in the horizon.
Critical strengths
Centering is a useful observation. The frequency term is unchanged when all weights are shifted by the same constant. As far as I know, existing robustness-based uncertainty terms do not use this. Centering the weights at a data-dependent constant is a simple idea that could transfer to other bounds, and the bound remains valid for weights, and hence models, that depend on the data.
Unobserved categories are handled more carefully. The bound separates the contribution of unseen categories and controls it through the expected missing mass and its concentration. Another recent bound accounts for it using the maximum unobserved weight times a factor. In this paper, it is a probability-weighted average times the missing mass. This is an improvement when the sample is large relative to the number of categories ().
Critical weaknesses
Weaknesses are labelled for future reference.
(W1) The dependency on and is preserved in general. Let me recall the notations: , with . It is clear that is the minimizer of the mean absolute deviations of the weights, e.g., a median of the weights: . With these notations, one can rewrite . This exhibits a clear linear dependence on in general. Such a worst-case linear scenario is easy to build: consider that half the weights are 0, half are 1. In that case, and . A similar introduction of the notation hides the dependence on .
(W2) The comparison with other bounds from the literature is unfair. The novel term (Theorem 4.1) is compared to which, in the worst case, scales in . This should be compared to the scaling of in its own worst case scenario. Once some quantities are rewritten with the relevant notations (see (W1)), it appears that in the worst case, scales in . This should appear and be discussed clearly somewhere in the paper.
(W3) Missing baselines and scenarios. In the experiment of Section 4.3, computing the simple bound from 2012 given in (5) with , and yields , which is lower than for roughly half the models in Figure 2. Also, a sweep over until could help understand the competitiveness of the bound in less favorable scenarios.
Questions for authors
Questions are labelled for future reference.
(Q1) Could you state the worst-case scaling of explicitly (W1, W2)?
(Q2) Could you add (5) and its centered version as baselines in Figure 2, and run a sweep over (W3)?
(Q3) Could you report the full bounds, including , against the actual test error? With the 0-1 loss and 200 regions, I would expect to dominate the uncertainty terms.
Response to Reviewer jkjR
We thank the reviewer for recognizing the usefulness of centering data-dependent weights and separately controlling unobserved categories. We agree that the original presentation did not sufficiently distinguish the adaptive advantages of our bound from its worst-case behavior. The revised paper now makes this distinction explicit, adds the requested baselines and partition-size sweep, and evaluates the complete risk bounds.
We thank the reviewer for this important observation. We agree that the original manuscript emphasized favorable effective-sparsity regimes without stating the worst-case behavior sufficiently clearly.
We now explicitly discuss this limitation in Remark 3.3. For bounded coefficients, seff can scale as O(∣T∣), so the original ℓ1-based uncertainty term can scale as UncO=O(∣T∣/n+K/n), where K/n arises from the distribution-free control of the unseen mass. Thus, Theorem 3.1 does not uniformly improve the worst-case dependence on the alphabet or observed support size. Its advantage is adaptive: it can be substantially sharper when the centered coefficients have small residual mass.
Motivated by the related suggestion of Reviewer WBrX, we have also added Theorem 3.2, which replaces seff with the centered ℓ2 residual mass seff(2)=infc∈R∑i∈T(fi−c)2. For bounded coefficients, seff(2)=O(∣T∣) in the worst case, improving the observed-region term from O(∣T∣/n) to O(∣T∣/n). The resulting full uncertainty term scales as O(∣T∣/n+K/n) under the same distribution-free control of the unseen mass.
The revision therefore makes two points explicit: the original ℓ1 formulation provides an adaptive rather than uniform improvement, while the new ℓ2 formulation additionally recovers the sharper worst-case scaling for the observed-region term.
Thank you for suggesting these comparisons. Figure 2 now includes the uncertainty term in (5), its centered version, the term in (6), and both versions of our term based on seff and seff(2).
Across all 22 models, both versions of our uncertainty term are smaller than the term in (6). The original seff-based term is larger than the term in (5) and its centered version, thereby revealing the limitation of the ℓ1 formulation in this experiment. In contrast, the new seff(2)-based term is consistently the smallest across all 22 models.
We have also added a sweep over K∈50,100,200,500,1000,5000 in Appendix C.2. Figure 5 shows that the seff(2)-based term is substantially smaller than the seff-based term, particularly for large K. It outperforms the term in (6) and the original term in (5) at every tested partition size. It also outperforms the centered version of (5) in all tested settings except K=50 for both models and K=5000 for ResNet18. These results clarify both the regimes in which our bound improves over the baselines and the exceptional cases in which the centered baseline remains competitive.
Yes. Figure 3 now reports the complete population-risk bounds obtained from (5)–(8), including the centered version of (5), together with the ImageNet validation error. In particular, our complete bound includes the empirical-risk term, the average local-sensitivity term ϵˉ(h), and the uncertainty term.
Across all 22 models, our ℓ2-based bound is consistently the tightest and remains non-vacuous. It is 8.1%--17% tighter than the bound in (7). Since (7) and (8) share the same empirical-risk and sensitivity terms, this improvement is entirely attributable to the tighter uncertainty term.
The experiment also confirms that including ϵˉ(h) does not eliminate the practical effect of improving the uncertainty term. By contrast, the complete bounds in (5) and (6) depend on the global robustness parameter ϵ(D), which is large for these pretrained models and makes those bounds vacuous.
Summary. The revised paper directly addresses the reviewer’s three concerns. It now
We respectfully invite the reviewer to reconsider the overall assessment.