acceptodds
Under review as a conference paper at ICLR 2027

Universality Profiles: How Much Task Coverage Can a Fixed Model Sustain?

Abstract

We study *sustainable breadth*: for a *fixed* algorithm and a finite budget, how broad is the family of tasks on which it can succeed while remaining fast? For a frozen foundation model, an in-context learner, or a multi-task procedure, this is the question of how much coverage a single fixed model can sustain at a target error, a quantity observed to saturate in practice but left unquantified by existing theory. Rather than fixing a task class and optimizing over algorithms as in minimax theory, we fix the algorithm and quantify the complexity of the subset it can cover. We formalize this through the *universality profile*, the packing complexity of the algorithm's success set at a target accuracy or regret level. Our main converse shows that success on distinguishable tasks requires the transcript to reveal at least information about the underlying task; once this information is upper bounded, one obtains a quantitative breadth–convergence frontier. In online prediction with expert advice, the classical minimax law becomes an explicit universality law with budget , and varying only the prior support of Hedge yields different algorithmic breadth on the same ambient class. In a packed -armed bandit identification family with environments, the framework yields a sharp lower bound together with a matching, up to logarithmic factors, uniform-sampling upper bound. A local linear-bandit analysis turns the same proof skeleton into a two-sided structured frontier, with a lower bound that holds for every algorithm and a least-squares achievability guarantee at the scale set by full-parameter estimation. On a fixed expert class, we moreover characterize the success set of a given algorithm explicitly, showing that the profile ranges over a whole spectrum of values as the algorithm varies while the ambient minimax hardness stays put. A finite-feature kernel witness shows that capacity bounds breadth in a nonparametric setting, and real-data checks on digit classification make the same breadth–budget law visible outside simulation: saturation at the class packing, a phase-transition knee, and coverage bounded by the capacity of a frozen representation. The point is not to replace minimax hardness, but to add an algorithm-centric axis that measures the task coverage achieved by a particular procedure.

Primary area:
learning theory
Keywords:
learning theory, information-theoretic lower bounds, minimax theory, universality, sample complexity, online learning

Reviews

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

This paper introduces the universality profile, an algorithm-dependent measure of task coverage defined as the logarithm of the packing number of the set of tasks on which a fixed algorithm succeeds at a given accuracy and sample budget. The main theoretical result uses Fano's inequality to relate the universality profile to the mutual information between the underlying task and the algorithm's observation transcript, yielding a general sample-complexity lower-bound template.

The authors study this framework in several settings, including online learning with experts, Bernoulli bandit identification, linear bandits, and kernel regression. They derive algorithm-dependent coverage results and sample-complexity bounds in these settings. The paper also presents synthetic experiments and classification experiments on digits and CIFAR-10, illustrating how the empirical task-coverage measure varies with the sampling budget and representation capacity.

Critical strengths
  • The paper considers an interesting question: how many different tasks can a fixed algorithm solve within a given budget? I think the algorithm-dependent perspective is potentially useful, as it differs from the usual minimax perspective that focuses on the best achievable performance over a task class.

  • The definition of the universality profile is simple and intuitive. The authors also attempt to illustrate the proposed framework in several settings, including online learning with experts, bandit identification, linear bandits, and kernel regression. I appreciate the effort to connect the conceptual framework to concrete theoretical and empirical examples.

Critical weaknesses
  1. Theoretical novelty.

    My main concern is that the theoretical contributions appear rather limited. Theorem 1, which is presented as the main theorem of the paper, seems to follow directly from the standard Fano inequality. Once the universality profile is defined as the packing entropy of the success set, applying Fano's inequality to a packing of this set immediately gives the claimed result.

    The authors remark that Theorem 1 provides a reusable framework for deriving lower bounds by combining Fano's inequality with model-specific upper bounds on transcript mutual information. However, constructing a packing, bounding the mutual information or KL divergences, and applying Fano's inequality are already standard steps in information-theoretic lower-bound proofs. I do not see what new technical ingredient or reduction is introduced by Theorem 1.

    Moreover, the concrete applications mostly recover familiar regret or sample-complexity bounds. For example, the experts result follows from standard Hedge guarantees, and the bandit results recover classical identification rates. While the algorithm-dependent interpretation is reasonable, I am not convinced that the paper establishes a sufficiently substantial theoretical contribution beyond existing techniques.

  2. Correctness concerns. I found several mathematical statements that appear incorrect or insufficiently justified.

    The proof of Proposition 5 contains a gap. The authors establish an information bound under a Gaussian prior and then attempt to transfer it to a discrete packing using quantization and data processing. However, the two information quantities concern different observation distributions, and the required comparison is not established. Consequently, the claimed adaptive linear-bandit lower bound is not proved by the provided argument.

    There are also statements that are false as written. For example, Corollary 1 incorrectly derives an upper bound on the maximum packing number of the success set from a KL condition on an arbitrary packing. The positive-prior characterization in Remark 7 treats a sufficient Hedge regret condition as necessary and uses a minimum over comparators where a maximum is required.

    Finally, I am concerned that the experiments do not directly measure the proposed universality profile. The theoretical definition requires success with probability at least 1−δ1-\delta on each task, whereas the experimental protocols appear to count successful realizations of individual runs. These are different quantities, and averaging does not resolve this discrepancy. I therefore do not think the experiments directly validate the theoretical claims as presented.

Questions for authors
  1. Novelty of Theorem 1.

    Could the authors clarify what is technically new in Theorem 1 compared with the standard packing-and-Fano approach to statistical lower bounds? The authors emphasize that the main contribution is a reusable reduction to bounding transcript mutual information. However, constructing a packing, bounding mutual information through KL divergences, and applying Fano's inequality are already standard steps in lower-bound proofs. I would appreciate a more precise explanation of what new theoretical insight or result this framework provides beyond applying these classical arguments to the success set of a fixed algorithm.

  2. Proof of Proposition 5.

    Could the authors clarify the Gaussian-to-discrete reduction in Appendix A.9, particularly equation (48)? Data processing gives an information bound for the quantized parameter when observations are generated under the original Gaussian parameter. However, the desired bound concerns observations generated under the discrete parameter itself. These are different statistical experiments, and I do not see how the claimed information inequality follows. Could the authors provide a rigorous argument establishing the required mutual-information upper bound for the discrete packing under adaptive sampling?

  3. Could the authors clarify the following points?

    • In Corollary 1, the KL assumption concerns a particular packing contained in the success set. This seems to bound only the size of that packing, rather than the maximum packing number defining the universality profile. Is an additional assumption needed?
    • On page 7, lines 327–330, the authors claim that the condition log⁡(1/πj)≤2ϵ2/T\log(1/\pi_j)\le 2\epsilon^2/T characterizes ϵ\epsilon-admissibility exactly. However, this appears to be at most a sufficient condition under an appropriate choice of learning rate, rather than a necessary condition. Moreover, the characterization of admissible comparator sets in Remark 7 appears incorrect: the worst-case regret against the best expert in a comparator set equals the maximum of the individual comparator regrets, whereas the proposed characterization uses a minimum over the prior penalties. Could the authors clarify or correct these claims?
  4. Experiments.

    Could the authors explain how the reported empirical breadth corresponds to the formal definition of the universality profile? The definition requires each task to be solved with probability at least 1−δ1-\delta, whereas the experiments appear to count the number of tasks successfully solved in individual runs. These are different quantities, and averaging over random seeds does not appear sufficient to estimate the theoretical success set. Could the authors clarify how per-task success probabilities are estimated and how the reported experimental quantity relates to the theoretical profile?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 2rQZ

Thank you. We have corrected the invalid reduction and the single-run evaluation claims in the revised manuscript.

1. Novelty

Theorem 1 is the standard Fano argument. The contribution is the coverage object and fixed-algorithm characterizations, not a new inequality. At the common tolerance

ϵ∗=Tlog⁡N/2<T,\epsilon_{*}=\sqrt{T\log N/2}<T,

support-mm Hedge instances have

UAmcmp(ϵ∗,T)=log⁡m,U^{\mathrm{cmp}}_{\mathcal{A}_m}(\epsilon_*,T)=\log m,

while full-class worst-case regret is TT for m<Nm<N. Theorem 2 also gives the exact comparator success sets and strict failure outside the support; that assignment, not the Fano step, is the intended content. The feature bound is an upper bound, not achieved breadth.

2. Proposition 5

The original Eq. (48) is invalid: data processing for the Gaussian transcript does not bound the discrete experiment, and maximality does not make Voronoi cells equal. The replacement fixes δ=1/4\delta=1/4 and

ΘH={aV:V∈{−1,+1}d},a=2ϵ/d.\Theta_{H}=\lbrace aV: V\in\lbrace-1,+1\rbrace^{d}\rbrace,\quad a=2\epsilon/\sqrt{d}.

Success on every cube point gives

∑iI(Vi;ZT)≤∑iI(Vi;ZT∣V−i)≤2ϵ2T/d.\sum_{i} I(V_{i};Z_{T})\le\sum_{i} I(V_{i};Z_{T}\mid V_{-i})\le 2\epsilon^{2}T/d.

The sign decoder uses sign⁡(0)=+1\operatorname{sign}(0)=+1. On success there are at most d/4d/4 sign errors. At failure probability 1/41/4 the average sign-error probability is at most 7/167/16. Binary Fano gives

∑iI(Vi;ZT)≥d[ln⁡2−hb(7/16)]>0.\sum_{i} I(V_{i};Z_{T})\ge d[\ln 2-h_{b}(7/16)]>0.

Hence T≥c d2/ϵ2T\ge c\,d^{2}/\epsilon^{2}. This is a weaker full-cube replacement; the cube contains an exponential strict packing, but success only on that packing is not the proved hypothesis.

3. Corollary 1

The average one-sample KL bound for one packing of size MM gives log⁡M≤(nκ+log⁡2)/(1−δ)\log M\le(n\kappa+\log 2)/(1-\delta). A profile bound additionally needs the condition on a maximum-cardinality packing, or uniformly over finite success-set packings.

4. Remark 7

For nonempty SS, comparator regret is the maximum actual individual regret. The exact test is that this maximum is at most ϵ\epsilon. For one fixed prior and one fixed rate, a sufficient condition is

max⁡j∈S(log⁡(1/πj)η+ηT8)≤ϵ.\max_{j\in S}\left(\frac{\log(1/\pi_{j})}{\eta}+\frac{\eta T}{8}\right)\le\epsilon.

All comparators in SS are checked; no necessity is claimed.

5. Experiments

Fixed families use R=40/30/50R=40/30/50. Counts and 95% simultaneous brackets are within an algorithm-budget setting. E2 uniform at T=1000T=1000: point 37, analytic 58, bracket [0,64]; at T=2000T=2000: [56,64]; E3 isotropic at T=4000T=4000: [36,48]; E4 at n=720n=720: [44,45]. E3 coordinate means .495/.981 agree with unregularized-LS .498/.985; ridge 10−610^{-6} makes this approximate. E4 is a fixed-split benchmark, not a packing or population-risk certificate. Adaptive E3, E5 and E8 remain descriptive; E1 is a regret illustration.

We would appreciate your assessment of whether the replacement statement and this protocol resolve the soundness concerns.

I thank the authors for the response. It seems that the original Proposition 5 is not proved. Moreover, my concern about the novelty is not directly addressed, and I remain unconvinced about how this paper goes beyond the standard Fano analysis. Therefore, I will maintain my score.

Reviewer_rgP2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces a coverage profile that measures how many distinguishable tasks a fixed algorithm can solve at a given accuracy and sample budget. It relates this profile to mutual information to derive necessary sample requirements for broad coverage. Examples from expert prediction, bandit identification, and function estimation illustrate the viewpoint, alongside empirical studies.

Critical strengths

A well-motivated view of algorithmic coverage

The paper offers a useful perspective by asking how broadly a fixed algorithm succeeds, rather than focusing only on the difficulty of an entire task class. The motivation is clear and convincing. Connecting the packing complexity of an algorithm’s success set to the information available in its observations also gives a clear way to reason about the relationship between coverage and sample requirements.

Critical weaknesses

Unclear analytical benefit beyond the coverage interpretation

Section 4 appears to be the paper’s main theoretical contribution. Lemmas 1–3 follow from standard information-theoretic arguments, and Theorem 1 connects these arguments to the proposed coverage profile. However, the analytical benefit\textit{analytical benefit} of this template is not clear to me from the examples I examined. Section 5 seems to combine standard expert-learning bounds with the profile definition, while Section 6 uses familiar identification and estimation arguments. These examples help explain the profile, but the analytical benefit of the reusable template claimed in Section 4 remains unclear to me. Could the authors point to a concrete example showing how the template simplifies or extends a standard analysis, beyond expressing its conclusion in terms of coverage?

My concern is therefore about the evidence for the template’s analytical contribution, rather than the value of the coverage viewpoint itself. Section 8 also presents the framework as a bridge between several research directions. These connections lie outside my main expertise, so I cannot confidently assess their conceptual novelty or significance.

Questions for authors

1. Clarification on the Technical Contribution of Section 5 My understanding is that Section 5 mainly illustrates the meaning of the proposed profile, rather than providing substantially new technical results. Corollary 2 seems to follow from the standard minimax lower bound applied to a subset of experts. Proposition 4 and Theorem 2 seem to follow from the standard Hedge regret bound and the fact that experts with zero prior weight are never selected.

Is this a fair reading of the role of Section 5, or is there a technical contribution beyond these standard arguments that I have missed?

2. The Role of Section 6.1 and 6.2 in the Proposed Framework

Sections 6.1 and 6.2 give general lower bounds and guarantees for specific algorithms. I agree that these results provide useful information about coverage. However, it is unclear to me what the profile adds beyond expressing standard identification and estimation guarantees in terms of coverage. Do these examples provide any further insight into differences between fixed algorithms?

3. Clarification on the reduction to the discrete packing

Could you clarify two steps in A.9?

First, why does maximality imply that the Voronoi cells are near-congruent and that the projected Gaussian is (1+o(1))(1+o(1))-uniform? Could a maximal packing have Voronoi cells of different sizes? Does the particular packing used here have an additional property that ensures this uniformity?

Second, even assuming this uniformity, how does data processing give (48)? Let Q=π(Θ~G)Q=\pi(\tilde\Theta_G). The transcript generated under Θ~G\tilde\Theta_G, denoted by ZTGZ_T^G, differs from the transcript generated under QQ, denoted by ZTQZ_T^Q. Data processing gives I(Q;ZTG)≤I(Θ~G;ZTG)I(Q;Z_T^G)\le I(\tilde\Theta_G;Z_T^G), whereas the discrete argument requires a bound on I(Q;ZTQ)I(Q;Z_T^Q). Why does the information bound proved for the Gaussian experiment also apply to the discrete experiment? I find it difficult to follow (48) because the notation ZTZ_T does not distinguish these two experiments. Could you make explicit which experiment generates the transcript in each term of (48)?

4.Interpreting the Coverage Profile

I agree that studying coverage is useful, and I appreciate that distribution-weighted universality is left for future work. Still, two algorithms may have the same profile while solving very different tasks. Could you clarify how we should interpret comparisons based on the profile? In particular, what does a larger profile tell us about an algorithm, and what does it leave out?

2 comments
AuthorsOpenReview ↗

# Response to Reviewer rgP2

Your distinction between the coverage viewpoint and the analytical role of Section 4 is helpful. We have revised the text accordingly.

1. Section 4

Section 4 applies the classical estimation-to-testing/Fano argument. We now present it as a standard converse; the examples do not establish a new analytical simplification. The contribution is the algorithm-specific coverage measure and success-set characterizations, not a new Fano inequality.

A common-tolerance comparison makes the distinction concrete. Fix log⁡N<2T\log N<2T and

ϵ∗=Tlog⁡N/2<T.\epsilon_{*}=\sqrt{T\log N/2}<T.

For support-mm Hedge instances,

UAmcmp(ϵ∗,T)=log⁡m,U^{\mathrm{cmp}}_{\mathcal{A}_m}(\epsilon_*,T)=\log m,

while full-class worst-case regret is TT for m<Nm<N. Algorithms with the same full-class worst-case regret can therefore have different coverage at one tolerance. This is a simple analytic witness, not a new proof technique.

2. Sections 5 and 6

Corollary 2 is the classical minimax bound on a comparator subclass; Proposition 4 uses the standard Hedge guarantee; failure outside zero support follows from an elementary loss sequence. Section 5 now identifies these ingredients and presents an explicit success-set characterization. Sections 6.1 and 6.2 use standard identification and estimation rates to constrain coverage; the added value is the fixed-procedure comparison.

On the same 64-task Bernoulli family at T=2000T=2000, uniform sampling covers all 64 tasks at probability .75 with bracket [56,64]; greedy has point count 0 and bracket [0,0]. Each interval is simultaneous over tasks within its own configuration, not joint across algorithms. E3 uses a strict 48-task packing; ordinary nonadaptive LS error is parameter-independent. Adaptive E3, E5 and E8 were not rerun under this protocol and remain descriptive; E4 is a fixed-split benchmark, not a population-risk or packing certificate.

3. Appendix A.9

Maximality does not imply near-congruent Voronoi cells, and

I(Θq;ZG)≤I(ΘG;ZG)I(\Theta_{q};Z_{G})\le I(\Theta_{G};Z_{G})

concerns the Gaussian-generated transcript; it does not bound the discrete-generated experiment. We removed that argument. The replacement fixes δ=1/4\delta=1/4 and uses

ΘH={aV:V∈{−1,+1}d},a=2ϵ/d.\Theta_{H}=\lbrace aV: V\in\lbrace-1,+1\rbrace^{d}\rbrace,\quad a=2\epsilon/\sqrt{d}.

With the seed in the transcript, the per-coordinate genie bounds give

∑iI(Vi;ZT)≤∑iI(Vi;ZT∣V−i)≤2ϵ2T/d.\sum_{i} I(V_{i};Z_{T})\le\sum_{i} I(V_{i};Z_{T}\mid V_{-i})\le 2\epsilon^{2}T/d.

The sign decoder uses sign⁡(0)=+1\operatorname{sign}(0)=+1; success leaves at most d/4d/4 errors, average at most 7/167/16, and binary Fano gives a positive gap. Hence T≥c d2/ϵ2T\ge c\,d^{2}/\epsilon^{2}. This assumes success on every cube point; the original packing-only hypothesis is not recovered.

4. Interpretation

A larger profile means a larger separated family is covered at the same metric, tolerance, confidence and budget. It does not imply success-set inclusion, better performance on each task, or higher task-distribution-weighted coverage. Equal profiles may correspond to disjoint sets. When identities or overlap matter, report the success sets or overlap statistics. The profile is a geometric summary, not a complete ordering of algorithms.

We would appreciate your assessment of whether this narrower role answers the analytical-benefit question.

Thank you for the careful response and clarifications. I appreciate the value of the coverage perspective. However, it is still unclear to me what the proposed profile adds beyond standard analyses. I will therefore maintain my score.

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

The paper introduces the universality profile, which measures the number of distinguishable tasks a fixed algorithm can solve at a given accuracy, confidence, and sample budget. Using Fano's inequality, it derives bounds for expert learning, bandits, and kernel methods, supported by synthetic and real-data experiments.

Critical strengths

The algorithm-specific view of task coverage is interesting and complements classical minimax analysis.

The paper connects information theory and learning theory within a unified framework.

The basic Fano/KL arguments, Hedge regret bound, and isotropic least-squares upper bound are essentially correct.

Theorem 2 provides a concrete illustration using support-restricted Hedge.

Critical weaknesses
  1. Limited novelty. Theorem 1 follows directly from Fano's inequality applied to the algorithm's success set. Most applications recover known rates, and the paper does not clearly demonstrate a substantial new theoretical consequence.

  2. Mathematical errors and proof gaps. Proposition 3 / Corollary 2: The claimed (\Omega(\sqrt{T\log N})) lower bound cannot hold for arbitrary (N,T), since regret is at most (T). The correct rate includes (\min{\sqrt{T\log N},T}).

Theorem 3 (A.8): The claimed exponential (2\epsilon)-packing fails at (\epsilon=1/4) by the Plotkin bound. A uniform positive packing rate also fails as (\epsilon) approaches (1/4).

Proposition 5 (A.9, Eq. 48): The authors project a Gaussian prior onto a discrete packing and assume the resulting distribution is approximately uniform, without proof. More importantly, data processing does not justify transferring the information bound from observations generated under the Gaussian prior to those generated under a uniform discrete prior. Thus, the claimed (d^2/\epsilon^2) lower bound remains unproved.

Proposition 6 (A.15): The covering argument does not establish the required (2\epsilon)-packing bound. The conclusion may be correct, but the proof is incomplete.

Remark 7 (B.3): The positive-prior characterization incorrectly uses a minimum over prior penalties, although comparator-set regret is determined by the maximum individual regret. The Hedge bound is also sufficient, not necessary.

  1. Theory–experiment mismatch. The theoretical profile requires per-task success probability at least (1-\delta), whereas the experiments count observed successful tasks.

  2. Insufficient comparison with prior work. The relationship with classical Fano/minimax arguments and per-expert Pareto regret frontiers is not adequately discussed. The additional theoretical value of the proposed profile remains unclear.

Questions for authors

Proposition 5: How does nearest-neighbor projection of the Gaussian prior produce an approximately uniform discrete packing, and how is Equation (48) justified for the actual discrete observation model?

Can the authors correct the parameter ranges in Proposition 3, Corollary 2, and Theorem 3?

Can the authors provide a valid proof of Proposition 6 and correct the positive-prior characterization in Remark 7?

How do the empirical breadth measurements estimate the probability-based universality profile?

What new theoretical result does this framework provide beyond existing information-theoretic or minimax methods?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 7pkm

Your comments identified real errors. We have incorporated the corrections and the prior-work comparison into the revised manuscript.

1. Contribution

Theorem 1 is the classical packing-to-testing/Fano converse, not a new inequality. At the common tolerance

ϵ∗=Tlog⁡N/2<T,\epsilon_{*}=\sqrt{T\log N/2}<T,

support-mm instances satisfy

UAmcmp(ϵ∗,T)=log⁡m,U^{\mathrm{cmp}}_{\mathcal{A}_m}(\epsilon_*,T)=\log m,

while full-class worst-case regret is TT for m<Nm<N. This separates coverage from one risk scalar; it is not a new Hedge result. The feature bound is an upper bound, not achieved breadth.

2. Proposition 3 / Corollary 2

The regret ceiling was omitted. The corrected rate is

cmin⁡{Tlog⁡N,T}≤inf⁡Asup⁡ℓE[RegT]≤Cmin⁡{Tlog⁡N,T}.c\min\lbrace\sqrt{T\log N},T\rbrace\le\inf_{\mathcal{A}}\sup_{\ell}\mathbb{E}[\mathrm{Reg}_{T}]\le C\min\lbrace\sqrt{T\log N},T\rbrace.

The profile implication is ϵ≥cmin⁡{TU,T}\epsilon\ge c\min\lbrace\sqrt{TU},T\rbrace; the square-root form is the non-saturated regime.

3. Theorem 3

A strict 2ϵ2\epsilon-packing needs Hamming distance above 2ϵ2\epsilon. At ϵ=1/4\epsilon=1/4 the Plotkin bound rules out a positive exponential rate. For fixed ϵ<1/4\epsilon<1/4, define c0=1−h2(2ϵ)>0c_{0}=1-h_{2}(2\epsilon)>0 with h2h_{2} in bits. Then

log⁡2∣Θ0∣≥[c0−o(1)]K.\log_{2}\lvert\Theta_{0}\rvert\ge[c_{0}-o(1)]K.

The finite Fano inequality, with natural logs and pairwise KL at most 16TΔ216T\Delta^{2}, is

16TΔ2≥(1−δ)log⁡∣Θ0∣−log⁡2.16T\Delta^{2}\ge(1-\delta)\log\lvert\Theta_{0}\rvert-\log 2.

For large KK this gives T=Ω(c0K/Δ2)T=\Omega(c_{0}K/\Delta^{2}); no positive rate is uniform up to the endpoint.

4. Proposition 5

The Gaussian projection is invalid: data processing for the Gaussian transcript does not bound the discrete experiment, and maximality does not make Voronoi cells equal. The replacement fixes δ=1/4\delta=1/4 and

ΘH={aV:V∈{−1,+1}d},a=2ϵ/d.\Theta_{H}=\lbrace aV: V\in\lbrace-1,+1\rbrace^{d}\rbrace,\quad a=2\epsilon/\sqrt{d}.

Success on every cube point gives

∑iI(Vi;ZT)≤∑iI(Vi;ZT∣V−i)≤2ϵ2T/d.\sum_{i} I(V_{i};Z_{T})\le\sum_{i} I(V_{i};Z_{T}\mid V_{-i})\le 2\epsilon^{2}T/d.

The sign decoder uses sign⁡(0)=+1\operatorname{sign}(0)=+1; success leaves at most d/4d/4 errors, average at most 7/167/16, and binary Fano gives a positive gap. Hence T≥c d2/ϵ2T\ge c\,d^{2}/\epsilon^{2}. This assumes success on the whole cube and does not recover the original packing-only statement.

5. Proposition 6

Use L=Rλ1L=R\sqrt{\lambda_{1}} as the L2L^{2} radius, or normalize λ1≤1\lambda_{1}\le1 and use L=RL=R. With f=g+hf=g+h and an ϵ/2\epsilon/2 projection net, each cluster contains at most two packing points; the three-tail identity gives

UAm(ϵ,n)≤log⁡2+mlog⁡(1+4L/ϵ).U_{\mathcal{A}_m}(\epsilon,n)\le\log 2+m\log(1+4L/\epsilon).

Only for L/ϵ≥8L/\epsilon\ge8 is the tube entropy summarized as Θ(mlog⁡(L/ϵ))\Theta(m\log(L/\epsilon)). This is a tube bound, not learner achieved breadth.

6. Remark 7

The exact test is that the maximum actual individual regret is at most ϵ\epsilon. For one fixed prior and one fixed rate, a sufficient condition is

max⁡j∈S(log⁡(1/πj)η+ηT8)≤ϵ.\max_{j\in S}\left(\frac{\log(1/\pi_{j})}{\eta}+\frac{\eta T}{8}\right)\le\epsilon.

All comparators are checked; no positive-prior necessity is claimed.

7. Experiments

Fixed families use R=40/30/50R=40/30/50. E2 uniform at T=1000T=1000: point 37, analytic 58, bracket [0,64]; at T=2000T=2000: [56,64]; greedy [0,0]. E3 isotropic at T=4000T=4000: [36,48]. E4 at n=720n=720: [44,45]. E3 coordinate means .495/.981 agree with unregularized-LS .498/.985; ridge makes this approximate. E4 is a fixed-split benchmark. Adaptive E3, E5 and E8 remain descriptive; E1 is regret.

8. Prior work

Koolen and van Erven, COLT 2015 combined second-order and quantile adaptivity for expert advice; this is a different guarantee from coverage at a fixed tolerance. Lattimore, NIPS 2015 characterized per-arm regret tradeoffs under bandit feedback, not an identical full-information theorem. For a fixed algorithm the profile is a log threshold count of its comparator-risk vector; a Pareto frontier concerns achievable vectors across algorithms. The profile does not subsume either object.

We would welcome any remaining objections.

Reviewer_7pkmOpenReview ↗

Rebuttal response

The corrections to Proposition 3, Corollary 2, Theorem 3, and Proposition 6 appear to resolve my earlier objections. My main remaining concern is Proposition 5. The new proof assumes success on the entire hypercube, whereas the original proposition requires success only on an exponentially large (2\epsilon)-packing. Since the new argument does not establish the original claim, I think Proposition 5 and the corresponding claims in the manuscript should be revised accordingly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.