Bits-Limited Leaderboards: Minimax Guarantees for Adaptive Submissions Under Quantized Feedback

We study the problem of preventing overfitting in leaderboard competitions where an adaptive analyst submits a sequence of models to a holdout test set. Previous mechanisms like the Ladder and Shaky Ladder algorithms address this by adding noise or thresholding improvements, effectively limiting the information leakage. In this work, we formalize the information constraint directly by modeling the feedback as being quantized to b bits per round. For bounded loss functions (taking values in [0, 1]), we propose a new mechanism that provides fixed-horizon anytime-valid leaderboard error guarantees, meaning the displayed score is close to the true generalization error for all submissions simultaneously with high probability, given that the total number of rounds T is known in advance. We prove a minimax lower bound on the leaderboard error for any mechanism with b-bit feedback, establishing the fundamental limits of this resource-constrained setting. Our upper bound matches the lower bound up to logarithmic factors, demonstrating minimax optimality in the worst-case agnostic setting up to these factors. This work provides a rigorous theoretical foundation for designing communication-efficient and robust leaderboards.