On computable online learning
N Hasrati, S Ben-David - International Conference on …, 2023 - proceedings.mlr.press
We initiate the first study of computable online (c-online) learning, which we analyse under
varying requirements for “optimality” in terms of the mistake bound. Our main contribution is …
varying requirements for “optimality” in terms of the mistake bound. Our main contribution is …
On characterizations of learnability with computable learners
TF Sterkenburg - Conference on Learning Theory, 2022 - proceedings.mlr.press
We study computable PAC (CPAC) learning as introduced by Agarwal et al.(2020). First, we
consider the main open question of finding characterizations of proper and improper CPAC …
consider the main open question of finding characterizations of proper and improper CPAC …
Find a witness or shatter: the landscape of computable PAC learning.
V Delle Rose, A Kozachinskiy… - The Thirty Sixth …, 2023 - proceedings.mlr.press
This paper contributes to the study of CPAC learnability—a computable version of PAC
learning–by solving three open questions from recent papers. Firstly, we prove that every …
learning–by solving three open questions from recent papers. Firstly, we prove that every …
From undecidability of non-triviality and finiteness to undecidability of learnability
MC Caro - International Journal of Approximate Reasoning, 2023 - Elsevier
Abstract Machine learning researchers and practitioners steadily enlarge the multitude of
successful learning models. They achieve this through in-depth theoretical analyses and …
successful learning models. They achieve this through in-depth theoretical analyses and …
Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the
classical PAC-learning sample complexity framework. A crucial outcome of their …
classical PAC-learning sample complexity framework. A crucial outcome of their …
Find a witness or shatter: the landscape of computable PAC learning
VD Rose, A Kozachinskiy, C Rojas, T Steifer - arXiv preprint arXiv …, 2023 - arxiv.org
This paper contributes to the study of CPAC learnability--a computable version of PAC
learning--by solving three open questions from recent papers. Firstly, we prove that every …
learning--by solving three open questions from recent papers. Firstly, we prove that every …