- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper introduces a two-fidelity bandit framework in which the high-fidelity target is stationary while the discrepancy of a cheaper low-fidelity evaluator evolves with use. It proposes TACC, an optimistic algorithm that may continue low-fidelity sampling for a bounded period after reaching the usual switching threshold, when the anticipated reduction in proxy-target mismatch makes continuation worthwhile. The authors provide an instance-dependent upper regret bound and a lower bound capturing both proxy-improvement and statistical identification costs. The empirical evaluation includes synthetic bandits, NAS-Bench-201, and LLM-as-a-judge experiments.
Critical strengths
-
A novel and well-motivated framework: The paper identifies an interesting limitation of standard multi-fidelity bandit models, which generally treat the low-to-high-fidelity discrepancy as fixed even when the inexpensive evaluator may improve through various means. The proposed TACC algorithm captures the resulting allocation problem through bounded low-fidelity continuation after the nominal switching threshold. Its theoretical analysis identifies a class of arms for which this continuation can be useful with a bounded amount of additional low-fidelity sampling. This provides a clear theoretical explanation of when exploiting evaluator improvement can reduce regret.
-
Broad empirical evaluation: The paper evaluates the method on synthetic instances, NAS-Bench-201 learning trajectories, controlled LLM-as-a-judge settings, and an experiment based on trained weak-judge checkpoints, with further experiments in the appendix. These experiments showcase that the paper’s key modeling ingredients, such as improved proxy feedback and offline-calibrated mismatch certificates, can arise and be utilized in realistic systems.
Critical weaknesses
-
The guarantees rely on strong assumptions: Assumption 3.1 requires a known, fixed certificate that uniformly bounds cumulative low-to-high-fidelity mismatch for every arm and sample count. This certificate is what permits time-varying low-fidelity observations to be converted into valid confidence intervals for the stationary high-fidelity target, thereby avoiding the difficult problem of learning the evaluator’s evolution online. Although the experiments demonstrate promising offline calibration, obtaining a uniformly valid certificate in deployment may be difficult. Assumption 5.1 additionally requires that a low-fidelity certificate remain valid until the window ends, for which the practical justification is unclear. While the authors mention an alternative derivation in Appendix C, this does not remove this issue for TACC itself: it introduces a different reference algorithm and replaces the continuation assumption with an additional one. This is the main issue that affects my current score.
-
The tightness of the regret analysis remains unclear: The lower bound captures the minimum of a low-fidelity route, involving both a masking period and statistical identification, and a high-fidelity identification route. In contrast, TACC’s upper bound is expressed using the parameters and and the arm classes , , and . The appendix provides qualitative comparisons and a particular two-arm family on which TACC is optimal up to a constant factor, but it does not establish that the upper and lower bounds generally match. A clearer characterization of the gap between them would make it easier to assess the optimality of the proposed algorithm or the tightness of the lower bound.
Questions for authors
-
TACC requires several parameters, including , and . Can some of these be selected internally or removed?
-
What practical conditions justify Assumption 5.1? Does this assumption hold in the experiments provided in the manuscript?
-
Can the authors clarify the general relationship between the upper and lower bounds?
We appreciate the reviewer's careful assessment and valuable feedback.
Q1. Are Assumptions 3.1 and 5.1 practical?
Thank you for raising this concern. Following the offline calibration approach in Appendix D.3, we ran an additional ImageNet16-120 replay using 199-epoch learning curves. We calibrated the certificate on cumulative absolute mismatch, as required by Assumption 3.1, using architectures separate from evaluation. With a 90% coverage target, 33/40, 33/40, and 36/40 held-out groups were covered across three new partitions. Each group contained 20 arms and counted as covered only when the certificate held for every arm and count in the replay. Q4 reports stability checks and algorithm performance on these same groups.
For the Appendix D.11 checkpoint replay, a wider bound increased full-replay coverage from 0/5 to 5/5 arms. Under this bound, TACC had higher mean regret than DNC at the same γ. These checks assess certificate coverage over the evaluated trajectories. Q4 reports our separate checks of Assumption 5.1, while Appendix C provides a separate regret bound for RDFE.
Q2. How do the upper and lower regret bounds match, and when optimal?
Thank you for highlighting this connection. We address it in our response to c3R3 Q3, including how Mk relates to TACC’s certification time and where the bounds match. We will add this explanation to Section 5 and Appendix B.3, with the scope of the matching result stated explicitly.
Q3. Selection of parameters
We can choose γ, η, and S0 on tuning data and set δ to the desired confidence level. These remain inputs to TACC. Appendix D.4 suggests S0≤⌊λ(H)/λ(L)⌋ and reports regret sensitivity in Table 3. In an additional delayed-improvement experiment, increasing η from 10−4 to 10−2 reduced mean continuation queries from 112.5 to 92.6 at γ=0.25.
Q4. Satisfaction of Assumption 5.1 in practice and experiments
In Sections 6.1 and 6.2, the effective gap Δk(L)(n) is nondecreasing, so Assumption 5.1 holds. Additional checks found no decrease across 6,980 synthetic suboptimal-arm trajectories and the three suboptimal NLI arms.
We also checked coverage, stability, and performance together on 199-epoch NAS learning curves, using γ=0.0277, S0=30, and the empirical confidence radius. The stability window lies within the recorded curves. A group passed both checks only when the certificate covered every arm and all suboptimal arms satisfied the stability condition.
For ImageNet16-120, the results on groups passing both checks were:
The table reports mean cost-weighted pseudo-regret at Λ=6,000. TACC had lower mean regret in each partition, with paired 95% bootstrap intervals for the differences below zero. The same direction held when all 40 groups were included.
For CIFAR-10-valid and CIFAR-100, 18–22 and 4–6 groups passed both checks, respectively, and TACC matched DNC at the same threshold. Fixed continuation also matched TACC on ImageNet16-120, while separately tuned TACC and DNC matched across all three datasets. These results show where the assumptions hold in the replay and where continuation helps at the specified threshold. We will include these checks in the revision.
Q5. The relationship between the upper and lower bounds
Our response to c3R3 Q3 explains the relationship between the bounds and the two-arm matching construction in Corollary B.13. We will present its parameter choices alongside the bound comparison in the revision.