Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Computable universal online learning
Authors: Dariusz Kalociลski, Tomasz Steifer
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we bridge this gap by introducing computability constraints into the universal online learning framework, asking when a class of hypotheses admits a computable learning scheme that guarantees a finite number of mistakes. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference. |
| Researcher Affiliation | Academia | Dariusz Kaloci nski Institute of Computer Science Polish Academy of Sciences EMAIL Tomasz Steifer Institute of Fundamental Technological Research Polish Academy of Sciences EMAIL |
| Pseudocode | No | The paper describes theoretical concepts, definitions, and proves theorems. While it discusses algorithms conceptually (e.g., a variant of Weighted Majority Algorithm in Appendix B), it does not present any formal pseudocode blocks or algorithms with structured steps explicitly labeled as such. |
| Open Source Code | No | The paper is theoretical and does not involve empirical experiments. The NeurIPS Paper Checklist explicitly states 'NA' for 'Open access to data and code' and 'the paper does not include experiments requiring code', indicating no source code is provided for the methodology. |
| Open Datasets | No | The paper is theoretical and focuses on abstract 'hypothesis classes' and 'functions' rather than empirical datasets. The NeurIPS Paper Checklist explicitly states 'NA' for 'Open access to data and code' and 'the paper does not include experiments requiring code', confirming that no datasets are used or provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving datasets. Therefore, there is no mention of dataset splits (e.g., training, validation, test splits) in the text. The NeurIPS Paper Checklist explicitly states 'the paper does not contain any experimental results'. |
| Hardware Specification | No | The paper is purely theoretical and does not report on any empirical experiments. Consequently, there is no discussion or specification of hardware used for running experiments. The NeurIPS Paper Checklist explicitly states 'the paper does not contain any experimental results'. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementations or dependencies with specific version numbers. The NeurIPS Paper Checklist explicitly states 'the paper does not include experiments requiring code'. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments. Therefore, there are no details provided regarding experimental setup, hyperparameters, model initialization, or training configurations. The NeurIPS Paper Checklist explicitly states 'the paper does not contain any experimental results'. |