- 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
-
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.
-
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 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
-
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.
-
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?
-
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 characterizes -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?
-
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 , 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
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.
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
ϵ∗=TlogN/2<T,
support-m Hedge instances have
UAmcmp(ϵ∗,T)=logm,
while full-class worst-case regret is T for m<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 and
ΘH={aV:V∈{−1,+1}d},a=2ϵ/d.
Success on every cube point gives
∑iI(Vi;ZT)≤∑iI(Vi;ZT∣V−i)≤2ϵ2T/d.
The sign decoder uses sign(0)=+1. On success there are at most d/4 sign errors. At failure probability 1/4 the average sign-error probability is at most 7/16. Binary Fano gives
∑iI(Vi;ZT)≥d[ln2−hb(7/16)]>0.
Hence T≥cd2/ϵ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 M gives logM≤(nκ+log2)/(1−δ). A profile bound additionally needs the condition on a maximum-cardinality packing, or uniformly over finite success-set packings.
4. Remark 7
For nonempty S, comparator regret is the maximum actual individual regret. The exact test is that this maximum is at most ϵ. For one fixed prior and one fixed rate, a sufficient condition is
maxj∈S(ηlog(1/πj)+8ηT)≤ϵ.
All comparators in S are checked; no necessity is claimed.
5. Experiments
Fixed families use R=40/30/50. Counts and 95% simultaneous brackets are within an algorithm-budget setting. E2 uniform at T=1000: point 37, analytic 58, bracket [0,64]; at T=2000: [56,64]; E3 isotropic at T=4000: [36,48]; E4 at n=720: [44,45]. E3 coordinate means .495/.981 agree with unregularized-LS .498/.985; ridge 10−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.