4 papers · 1 filter
Optimal bounds for dissatisfaction in perpetual voting
Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proport…
Effective Littlestone Dimension
Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer
Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learn…
Learning Equivalence Relations on Polish Spaces
Dino Rossegger, Theodore Slaman, Tomasz Steifer
We investigate natural variations of behaviourally correct learning and explanatory learning -- two learning paradigms studied in algorithmic learning theory -- that allow us to ``…
Simple online learning with consistent oracle
Alexander Kozachinskiy, Tomasz Steifer
We consider online learning in the model where a learning algorithm can access the class only via the \emph{consistent oracle} -- an oracle, that, at any moment, can give a functio…