acceptodds
Under review as a conference paper at ICLR 2027

Effective Sparsity in Distribution and Error Estimation and Off-Policy Evaluation

Abstract

Estimating a discrete probability distribution from a finite sample is a fundamental problem in machine learning and statistics. Classical guarantees typically depend on the alphabet size or the observed support , although in many applications the quantity of interest depends only on a structured, data-dependent combination of distributional errors. We identify *effective sparsity* as a useful notion of complexity for such quantities and develop a concentration bound that adapts to the residual structure of data-dependent coefficients while separately accounting for the probability mass of unseen categories. *Our bound removes the direct dependence on and *, which can be crucial in high-dimensional problems with approximately sparse structure. We further demonstrate substantial improvements in two important problems. First, in generalization analysis via Algorithmic Robustness, our bound replaces the or dependence in existing guarantees by the effective residual mass of local model errors. Experiments on 22 pretrained ImageNet models show that our uncertainty term is consistently substantially smaller than the recent robustness-based bound. Second, in off-policy evaluation for finite-horizon confounded partially observable decision processes, our analysis replaces the exponential dependence on the observation-action history space in existing first-order error bounds by polynomial dependence on the horizon under realistic effective-sparsity conditions, *yielding an exponential improvement in the dependence on history size*. These results establish effective sparsity as a general mechanism for obtaining substantially sharper distribution and error estimation guarantees in high-dimensional problems.

Primary area:
learning theory
Keywords:
Effective Sparsity, Distribution Estimation, Error Estimation, Off-Policy Evaluation

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_jkjROpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a new way to bound weighted errors ∑ifi(pi−p^i)\sum_i f_i(p_i - \hat p_i) of the empirical distribution p^\hat p (built from nn i.i.d. samples over KK categories), where the weights fif_i may depend on the data. The main result (Theorem 3.1) centers the weights at a constant cc and splits the error in two. One of these parts covers unobserved categories and is controlled by the expected missing mass. Taking cc as the median of the observed weights gives a leading term seff/ns_{\mathrm{eff}}/\sqrt{n} (coined "effective sparsity"), which is claimed to remove the K\sqrt{K} or ∣T∣\sqrt{|\mathbb{T}|} 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 ∑ifi(pi−p^i)\sum_i f_i(p_i - \hat p_i) 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 ∣T∣ln⁡K/n\sqrt{|\mathbb{T}| \ln K / n} 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 (n≥Kn \geq K).

Critical weaknesses

Weaknesses are labelled for future reference.

(W1) The dependency on KK and ∣T∣|\mathbb{T}| is preserved in general. Let me recall the notations: seff=∑i∈T∣fi(X)−c∗∣s_\mathrm{eff} = \sum_{i \in \mathbb{T}} \left|f_i(\mathbf X) - c^* \right|, with c∗=arg⁡min⁡c∈R∑i∈T∣fi(X)−c∣c^* = \arg \min_{c \in \mathbb{R}} \sum_{i \in \mathbb{T}} \left|f_i(\mathbf X) - c \right|. It is clear that c∗c^* is the minimizer of the mean absolute deviations MAD(X)=1∣T∣∑i∈T∣fi(X)−c∣\mathrm{MAD}(\mathbf X) = \frac{1}{|\mathbb{T}|} \sum_{i \in \mathbb{T}} \left|f_i(\mathbf X) - c \right| of the weights, e.g., a median of the weights: c∗=med({fi(X)}i∈T)c^* = \mathrm{med}\left(\{f_i(\mathbf X)\}_{i \in \mathbb{T}}\right). With these notations, one can rewrite seff=∣T∣MAD(X)s_\mathrm{eff} = |\mathbb{T}| \mathrm{MAD}(\mathbf X). This exhibits a clear linear dependence on ∣T∣|\mathbb{T}| 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, MAD(X)=1/2\mathrm{MAD}(\mathbf X) = 1/2 and seff=∣T∣/2s_{\mathrm{eff}} = |\mathbb{T}|/2. A similar introduction of the notation eoe_o hides the dependence on KK.

(W2) The comparison with other bounds from the literature is unfair. The novel term UncO\mathrm{Unc}_O (Theorem 4.1) is compared to UncK\mathrm{Unc}_K which, in the worst case, scales in O(∣T∣log⁡K/n)\mathcal{O}(\sqrt{|\mathbb{T}| \log K / n}). This should be compared to the scaling of UncO\mathrm{Unc}_O in its own worst case scenario. Once some quantities are rewritten with the relevant notations (see (W1)), it appears that in the worst case, UncO\mathrm{Unc}_O scales in O(∣T∣/n)\mathcal{O}(|\mathbb{T}|/\sqrt{n}). 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 K=200K=200, n=1,281,167n=1,281,167 and δ=0.01\delta = 0.01 yields 0.0150.015, which is lower than UncO\mathrm{Unc}_O for roughly half the models in Figure 2. Also, a sweep over KK until K≥nK \geq n 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 UncO\mathrm{Unc}_O explicitly (W1, W2)?

(Q2) Could you add (5) and its centered version as baselines in Figure 2, and run a sweep over KK (W3)?

(Q3) Could you report the full bounds, including ϵˉ(h)\bar\epsilon(\mathbf h), against the actual test error? With the 0-1 loss and 200 regions, I would expect ϵˉ(h)\bar\epsilon(\mathbf h) to dominate the uncertainty terms.

1 comment
AuthorsOpenReview ↗

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.

(Q1) Could you state the worst-case scaling of UncO\mathrm{Unc}_O explicitly (W1, W2)?

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, seffs_{\rm eff} can scale as O(∣T∣)O(|\mathbb T|), so the original ℓ1\ell_1-based uncertainty term can scale as UncO=O(∣T∣/n+K/n)\mathrm{Unc}_O=O(|\mathbb T|/\sqrt n+K/n), where K/nK/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 seffs_{\rm eff} with the centered ℓ2\ell_2 residual mass seff(2)=inf⁡c∈R∑i∈T(fi−c)2s_{\rm eff}^{(2)}=\inf_{c\in\mathbb R}\sqrt{\sum_{i\in\mathbb T}(f_i-c)^2}. For bounded coefficients, seff(2)=O(∣T∣)s_{\rm eff}^{(2)}=O(\sqrt{|\mathbb T|}) in the worst case, improving the observed-region term from O(∣T∣/n)O(|\mathbb T|/\sqrt n) to O(∣T∣/n)O(\sqrt{|\mathbb T|/n}). The resulting full uncertainty term scales as O(∣T∣/n+K/n)O(\sqrt{|\mathbb T|/n}+K/n) under the same distribution-free control of the unseen mass.

The revision therefore makes two points explicit: the original ℓ1\ell_1 formulation provides an adaptive rather than uniform improvement, while the new ℓ2\ell_2 formulation additionally recovers the sharper worst-case scaling for the observed-region term.

(Q2) Could you add (5) and its centered version as baselines in Figure 2, and run a sweep over KK (W3)?

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 seffs_{\rm eff} and seff(2)s_{\rm eff}^{(2)}.

Across all 22 models, both versions of our uncertainty term are smaller than the term in (6). The original seffs_{\rm eff}-based term is larger than the term in (5) and its centered version, thereby revealing the limitation of the ℓ1\ell_1 formulation in this experiment. In contrast, the new seff(2)s_{\rm eff}^{(2)}-based term is consistently the smallest across all 22 models.

We have also added a sweep over K∈50,100,200,500,1000,5000K\in\\{50,100,200,500,1000,5000\\} in Appendix C.2. Figure 5 shows that the seff(2)s_{\rm eff}^{(2)}-based term is substantially smaller than the seffs_{\rm eff}-based term, particularly for large KK. 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=50K=50 for both models and K=5000K=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.

(Q3) Could you report the full bounds, including ϵˉ(h)\bar\epsilon(\mathbf h), against the actual test error? With the 00-11 loss and 200 regions, I would expect ϵˉ(h)\bar\epsilon(\mathbf h) to dominate the uncertainty terms.

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)\bar\epsilon(\mathbf h), and the uncertainty term.

Across all 22 models, our ℓ2\ell_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)\bar\epsilon(\mathbf 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)\epsilon(\mathbf 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

  • states the worst-case scaling and the adaptive nature of Theorem 3.1 explicitly,
  • introduces a new ℓ2\ell_2 theorem that improves the worst-case observed-region term to O(∣T∣/n)O(\sqrt{|\mathbb T|/n}),
  • includes the requested evaluations.

We respectfully invite the reviewer to reconsider the overall assessment.

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

The authors bound data-dependent weighted multinomial deviations by a residual mass seffs_\text{eff} instead of, e.g., an alphabet and apply this to generalization bounds and off-policy evaluation in POMDPs.

Critical strengths
  • The paper produces a clean data-dependent concentration for weighted multinomial functionals
Critical weaknesses
  • On ImageNet the population errors fif_i are replaced by training-set estimates, i.e., the final bounds are not certified
  • seffs_\text{eff} stems from the ℓ1\ell_1-ℓ∞\ell_\infty pairing, and a standard ℓ2\ell_2 argument matches or improves upon it. Theorem 3.1 bounds ∑i∈T(fi−c)(pi−p^i)\sum_{i\in\mathbb T}(f_i-c)(p_i-\hat p_i) by ∑i∈T∣fi−c∣⋅∥p−p^∥∞\sum_{i\in\mathbb T}\lvert f_i-c\rvert\cdot\lVert p-\hat p\rVert_\infty, although the errors share the budget ∥p−p^∥2≤1/n+log⁡(1/δ)/n\lVert p-\hat p\rVert_2 \leq 1/\sqrt{n} + \sqrt{\log(1/\delta)/n}; Cauchy-Schwarz with this budget gives (∑i∈T(fi−c)2)1/2∥p−p^∥2\big(\sum_{i\in\mathbb T}(f_i-c)^2\big)^{1/2}\lVert p-\hat p\rVert_2, which is never worse than Theorem 3.1 by more than a factor 2\sqrt 2, is smaller by up to ∣T∣\sqrt{\lvert\mathbb T\rvert} for spread-out weights, and needs no sparsity.
Questions for authors
  1. Can the authors explain why one would do the ℓ1\ell_1, ℓ∞\ell_\infty pairing instead of the ℓ2\ell_2 bound and what role does effective sparsity play in that scenario?
  2. Could the authors evaluate the full bound on imagenet with the local errors estimated given a held-out data set instead of the training set?
5 comments
AuthorsOpenReview ↗

Response to Reviewer WBrX

We thank the reviewer for the positive assessment of our data-dependent concentration result. We especially appreciate the suggested ℓ2\ell_2 argument, which has led to a substantially sharper theorem and stronger empirical results in the revised paper. We'd like to clarify the remaining concerns below.

(Q1) Can the authors explain why one would use the ℓ1,ℓ∞\ell_1,\ell_\infty pairing instead of the ℓ2\ell_2 bound, and what role does effective sparsity play in that scenario?

The reviewer is correct that the ℓ2\ell_2 argument provides a sharper general bound for the observed-region term. Our original ℓ1,ℓ∞\ell_1,\ell_\infty pairing was motivated by its direct connection to sparsity: after centering, seff=inf⁡c∈R∑i∈T∣fi−c∣s_{\mathrm{eff}}=\inf_{c\in\mathbb R}\sum_{i\in\mathbb T}|f_i-c| is small when only a few observed coefficients differ substantially from a common value. This formulation makes the role of sparse residual coefficients particularly transparent.

However, as the reviewer observes, the ℓ1\ell_1 quantity can scale as O(∣T∣)O(|\mathbb T|) in the worst case, giving an observed-region term of order O(∣T∣/n)O(|\mathbb T|/\sqrt n). We now state this limitation explicitly in Remark 3.3.

Following the reviewer’s suggestion, we added Theorem 3.2 based on the centered ℓ2\ell_2 residual mass seff(2)=inf⁡c∈R∑i∈T(fi−c)2s_{\mathrm{eff}}^{(2)}=\inf_{c\in\mathbb R}\sqrt{\sum_{i\in\mathbb T}(f_i-c)^2}. For bounded coefficients, seff(2)=O(∣T∣)s_{\mathrm{eff}}^{(2)}=O(\sqrt{|\mathbb T|}) in the worst case, reducing the observed-region term from O(∣T∣/n)O(|\mathbb T|/\sqrt n) to O(∣T∣/n)O(\sqrt{|\mathbb T|/n}). A detailed proof is provided in Appendix A.

Effective sparsity remains relevant under this sharper formulation. The key complexity is not the number of observed regions itself, but the residual variation of the coefficients after removing their best common component. Thus, seff(2)s_{\mathrm{eff}}^{(2)} can be small when the coefficients are sparse, small, rapidly decaying, or nearly constant. The latter case is important because the common component cancels through ∑i(pi−p^i)=0\sum_i(p_i-\widehat p_i)=0, even when the original coefficient vector is dense.

Accordingly, the revised paper uses the ℓ2\ell_2 result as the sharper general guarantee, while retaining the ℓ1\ell_1 formulation for its direct sparsity interpretation. Both formulations exploit effective residual structure, but the ℓ2\ell_2 version substantially improves the worst-case dependence on ∣T∣|\mathbb T|.

(Q2) Could the authors evaluate the full bound on ImageNet with the local errors estimated using a held-out dataset instead of the training set?

Yes. In the revised experiment, we estimate the local errors using the 50,000 labeled images in the public ImageNet validation set.

Figure 3 reports the complete population-risk bounds, including the empirical training risk, the average local-sensitivity term, and the corresponding uncertainty term. Across all 22 models, our bound is consistently the tightest and remains non-vacuous. In particular, it is 5.45.4%--1717% tighter than the bound of Than et al. (2025). Because the two bounds share the same empirical-risk and average local-sensitivity terms, the improvement comes entirely from our tighter uncertainty term.

By contrast, the bounds of Xu and Mannor (2012) and Kawaguchi et al. (2022) depend on the global robustness parameter ϵ(D)\epsilon(\mathbf D), which is large for these pretrained models and makes their complete bounds vacuous in this experiment.

Summary. We believe that the new ℓ2\ell_2 theorem and the held-out ImageNet evaluation directly address the reviewer’s two main concerns and substantially strengthen both the theoretical and empirical contributions. We respectfully invite the reviewer to reconsider the overall assessment of the revised paper in light of these changes.

Thank you for the rebuttal.

  • On the ℓ2\ell_2-based bound: The new bound requires no sparsity, and the ℓ1\ell_1-based bound is never better, so the paper is now focused on the weaker of the two bounds. As it is a textbook proof with standard components, the only remaining new contribution seems to be the centering of the coefficients, if I understand correctly. Is there any other contribution? Finally, if the paper is accepted, I would appreciate a reviewer acknowledgment, as the ℓ2\ell_2 approach is now central to the paper.
  • The revised version of the paper is rather chaotic. The abstract and most of the text still claim independence from K\sqrt K and ∣T∣\sqrt{|T|}, while Remark 3.3 acknowledges that this is no longer true. The same goes for, e.g., Section 5. Additionally, please revise the new text from Remark 3.3 onward. Currently, you manage to write "worst" eight times (including the typo) in two paragraphs.
  • The rebuttal claims a bound that is 5.4–17% tighter, while the paper claims 5.4–12.6%. Which one is correct?
  • ImageNet bound: As far as I can see, the local errors are estimated and then plugged into the final bound as point estimates, without any accounting for the resulting estimation error. If so, the final bound is merely an approximation, not a certified upper bound.
AuthorsOpenReview ↗

Response to further concerns of Reviewer WBrX

We thank the reviewer for the follow-up and constructive feedback. We have revised the manuscript accordingly and address each concern below.

C1. ℓ2\ell_2-based bound, contribution, acknowledgment

We thank the reviewer for suggesting the ℓ2\ell_2 formulation. It has preferable worst-case scaling for the observed-cell term, and we have therefore incorporated it into our main results.

We would, however, like to clarify that the broader effective-sparsity principle was already central to our original submission. It exploits the invariance of the weighted functional to common shifts of its coefficients, so that the relevant complexity is determined by the centered residuals rather than the nominal support size alone. The original ℓ1\ell_1 quantity measures centered residual mass and captures sparse, rapidly decaying, or approximately constant residuals. The newly added ℓ2\ell_2 quantity provides an alternative measure based on centered residual energy and can also be small for dense but uniformly small residuals.

Contributions. We agree that the concentration step uses standard tools. The novelty lies in identifying centered residual structure and unseen probability mass as the relevant complexity of data-dependent weighted functionals, and in operationalizing this principle:

  • Centering-based concentration. Our complementary ℓ1\ell_1 and ℓ2\ell_2 bounds capture residual mass and residual energy, respectively, yielding guarantees for sparse, decaying, nearly constant, or uniformly small residuals beyond conventional support-size measures.
  • Robustness-based generalization. Applying this framework to local model errors replaces coarse partition-size dependence by realized residual complexity, producing substantially smaller uncertainty terms across 22 pretrained ImageNet models.
  • History-dependent OPE. For confounded POMDPs, the concentration result cannot be applied directly. We derive exact integrated-derivative and population-linearized representations that separate observed-history fluctuations, unseen histories, and higher-order error. The observed-history term has no explicit history-space-cardinality factor; under the stated controls, the complete bound replaces explicit exponential history-space dependence by polynomial horizon dependence.

Thus, centering is not merely a proof device but reveals an adaptive statistical complexity that enables sharper guarantees in both applications. The ℓ1\ell_1 formulation retains a direct sparsity interpretation and supports the unseen-history decomposition, whereas the ℓ2\ell_2 formulation provides preferable worst-case scaling.

We thank the reviewer for suggesting the ℓ2\ell_2 formulation. Subject to the conference’s anonymity and acknowledgment policies, we will acknowledge this contribution in the final version.

C2. The revised version of the paper is rather chaotic...

We apologize for the inconsistency. We have revised the abstract, introduction, Remark 3.3, and the corresponding discussions in Sections 4 and 5.

The manuscript now states that our bounds replace explicit K\sqrt K or ∣T∣\sqrt{|\mathbb T|} factors by centered residual quantities and a separate missing-mass term. These quantities may themselves scale with KK or ∣T∣|\mathbb T|, so we no longer suggest a uniform dimension-free improvement. The bounds improve prior guarantees when the centered residual and missing-mass terms are sufficiently small.

We have also clarified the OPE claims. The observed-history fluctuation bound contains no explicit history-space-cardinality factor. Polynomial horizon dependence for the complete error additionally requires some conditions. Finally, we have revised Remark 3.3 and the subsequent discussion.

C3. The rebuttal claims a bound that is 5.4--17% tighter, while the paper claims 5.4--12.6%.

We apologize for the ambiguity. The previous rebuttal inadvertently combined the lower endpoint for the ℓ1\ell_1 formulation with the upper endpoint for the ℓ2\ell_2 formulation. The correct ranges are 5.4--12.6% for the ℓ1\ell_1-based version and 8.1--17% for the ℓ2\ell_2-based version. We have corrected the manuscript to report the two ranges separately.

C4. the final bound is merely an approximation, not a certified upper bound.

We agree. In the ImageNet experiment, the local errors and robustness-related quantities are estimated from finite validation data and substituted into the theoretical expressions without additional confidence corrections for their estimation. Consequently, the reported values are empirical plug-in comparisons, not certified upper bounds on the true error.

We have added a footnote in Page 8 to make this limitation explicit. The purpose of the experiment is to compare the competing bounds when supplied with the same plug-in estimates, not to claim certified coverage of the population error.

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

The paper takes a classical problem of estimating error bonds of distribution and its empirical counterpart. The original concept is to introduce a weightings (f_i). It seems as a little change but it has big consequences as looking more on some regions than on others. An eye opener how to use the results is Corollary 3.2 and immediate comments.

Critical strengths

paper is clearly written and motivated

Critical weaknesses

This the paper should be more careful defining the mathematical objects. Looking for example at the formulation of Theorem 3.1; is X a set or an element of the set; sometimes it is used f_i(X) for f_i a function and sometimes as a set X \cap X_i . Also Section 4.2 shall have carefull defiitions of F(P,h) and F(D,h).

Questions for authors

Are p_i constant on X_i ? What is the domain of functions f_i ? Can’t \sum_{j \notin \mathbb T} pj = 0 ?, see Theoem 3.1

1 comment
AuthorsOpenReview ↗

Response to Reviewer Qyqv

We thank the reviewer for the positive assessment of the paper. We agree that some notational conventions should be made more explicit. We would like to clarify the remaining concerns.

(Q1) Is X a set or an element of the set?

In Theorem 3.1, X\mathbf X denotes the observed sample containing nn i.i.d. observations, whereas X\mathcal X denotes the sample domain. The sets X1,…,XK\mathcal X_1,\ldots,\mathcal X_K form a disjoint partition of X\mathcal X. Consequently, X∩Xj\mathbf X\cap\mathcal X_j is the subset of observed samples falling in region Xj\mathcal X_j.

(Q2) What is the domain of functions fif_i?

In Theorem 3.1, f1,...,fKf_1, ..., f_K are any functions that may depend on X\mathbf X. Therefore they may receive X\mathbf X as a direct or indirect input. We write fi(X)f_i(\mathbf X) to explicitly show the dependence on X\mathbf X.

In Theorem 4.1, f1,...,fKf_1, ..., f_K represent local errors of a model h\mathbf h and hence we write fi(h)f_i(\mathbf h). Note that those quantities indirectly depend on the training samples D\mathbf D whenever h\mathbf h depends or is trained from D\mathbf D.

Therefore the domain of f1,...,fKf_1, ..., f_K should depend on the application of interest. For example, for generalization analysis in Section 4, their domain is the hypothesis space H\mathcal H.

(Q3) Are pip_i constant on XiX_i?

The quantity pi=P(Xi)p_i=P(\mathcal X_i) is a scalar probability mass assigned to the entire region Xi\mathcal X_i. It is not a pointwise probability function defined on individual elements of Xi\mathcal X_i. For a fixed distribution PP and partition of X\mathcal X, pip_i is constant and does not depend on the observed sample.

(Q4) Can't ∑j∉Tpj=0\sum_{j\notin\mathbb T}p_j=0?

In Theorem 3.1, p=(p1,…,pK)\mathbf p=(p_1,\ldots,p_K) is a discrete distribution supported on the domain ⋃i=1KXi\bigcup_{i=1}^K\mathcal X_i, with the indexed regions corresponding to its support. Hence, pi>0p_i>0 for every i∈[K]i\in[K]. It follows that ∑j∉Tpj>0\sum_{j\notin\mathbb T}p_j>0 whenever ∣T∣<K|\mathbb T|<K. When T=[K]\mathbb T=[K], there are no unobserved regions, and focf_o^c is set to zero by the indicator in its definition. We have made this support convention explicit in the revised theorem.

(Q5) Also Section 4.2 shall have carefull definitions of F(P,h)F(P,h) and F(D,h)F(D,h).

These are explicitly defined in Lines 263--270.

We hope that those clarifications resolve the reviewer's concerns.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Revisions

Dear AC and Reviewers,

We thank the reviewers for their careful evaluations and constructive comments. In response, we have substantially revised the manuscript to sharpen its theoretical results, clarify its notation and scope, and strengthen its empirical evaluation. The principal revisions are summarized below:

  1. Sharper ℓ2\ell_2-based bound. We added Theorem 3.2 based on the centered ℓ2\ell_2 residual mass seff(2)s_{\rm eff}^{(2)}. For bounded coefficients, it improves the worst-case observed-region term from O(∣T∣/n)O(|\mathbb T|/\sqrt n) to O(∣T∣/n)O(\sqrt{|\mathbb T|/n}). A complete proof is provided in Appendix A.

  2. Explicit worst-case analysis. Remarks 3.3 and 4.1 now clarify that the original ℓ1\ell_1-based bound can scale as O(∣T∣/n+K/n)O(|\mathbb T|/\sqrt n+K/n) and is advantageous when the centered coefficients have small residual mass. The revised manuscript therefore distinguishes explicitly between its adaptive advantages and its worst-case behavior.

  3. Clearer notation. We clarified the roles of the sample X\mathbf X, partition regions Xi\mathcal X_i, data-dependent coefficients fi(X)f_i(\mathbf X), local errors fi(h)f_i(\mathbf h), region probabilities pip_i.

  4. Stronger ImageNet evaluation. We now estimate local errors using the ImageNet validation set and report complete risk bounds. Our ℓ2\ell_2-based bound remains non-vacuous and is 8.1%--17% tighter than the recent best bound.

  5. Additional baselines and sensitivity analysis. Figure 2 now includes the original and centered bounds of Xu and Mannor (2012), the bound of Kawaguchi et al. (2022), and both versions of our bound. Appendix C.2 further evaluates them when KK changes, demonstrating that the ℓ2\ell_2 formulation is substantially tighter, particularly for large KK.

These revisions directly address the main concerns raised by the reviewers and materially strengthen the theoretical analysis, empirical validation, and presentation of the paper. We appreciate the reviewers’ careful and constructive feedback, which has contributed substantially to improving the manuscript.

AuthorsOpenReview ↗

Final response to Reviewer jkjR

Thank you for carefully reviewing the revision and appendices. We appreciate that you regard W1/W2/Q1 and Q3 as resolved. We also agree that two further clarifications are needed.

First, Lines 253--254 were too broad. We have revised the sentence accordingly.

Second, following your suggestion, we have added TPV+BHC, combining ϵˉ(h)\bar\epsilon(\mathbf h) from Than et al. (2025) with the uncertainty term, for which Xu and Mannor (2012) used the Bretagnolle--Huber--Carol inequality to derive (5). We also report the centered version of TPV+BHC. These combinations do not appear in prior work. They are close to Ours (ℓ2\ell_2) because ϵˉ(h)\bar\epsilon(\mathbf h) dominates the complete risk value. We now clarify that the larger relative improvements concern the uncertainty terms, while the improvements in the complete risk bounds over these (newly) combined baselines are modest.

We emphasize that centering is our main technical idea: shift invariance replaces the raw coefficient complexity by that of the centered residuals. The original ℓ1\ell_1 formulation captures residual sparsity and supports the unseen-mass decomposition, while the new ℓ2\ell_2 formulation captures residual energy and improves worst-case scaling.

Kawaguchi et al. (2022) remains the closest prior data-dependent baseline. Sections 4 and 5 of their paper show theoretically and empirically that their sparsity-adaptive bound can be exponentially sharper than earlier bounds, including Xu and Mannor (2012), in diverse sparse regimes. Under our residual-structure conditions, our centered ℓ1\ell_1 bound is theoretically sharper than this baseline and smaller in all reported ImageNet comparisons. Outside such structured regimes, classical bounds may be preferable, as the revised paper now states explicitly.

We agree that the current sweep does not cover K≥nK\ge n. This ImageNet experiment requires constructing and evaluating more than one million regions and cannot be completed reliably during the rebuttal period. We will include it in the final version. Increasing KK may weaken the structural conditions required by both sparsity-adaptive bounds, so this experiment will identify where adaptive gains disappear rather than necessarily favor our method.

Finally, the centering principle, ℓ1\ell_1 theorem, and robustness and OPE applications were present in the original submission. The principal new technical additions are the reviewer-suggested ℓ2\ell_2 theorem and the baselines in experiments.

We thank you again for the detailed analysis and helpful feedback. We respectfully invite the reviewer to reconsider the overall assessment in light of these changes in the final PDF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.