kozmath
unread,Apr 10, 2024, 8:17:03 PMApr 10Sign in to reply to author
Sign in to forward
You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to Kolmogorov seminar on complexity
Date: Aptil 15, 2024.
Time: 18:30 (Moscow time), 17:30 (CET).
Speaker: Tomasz Steifer
Title: Simple online learning with consistent oracle.
Abstract:
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 function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al.~(COLT'23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem.
Assos et al.~gave an online learning algorithm in this model that makes at most Cd mistakes on classes of Littlestone dimension d, for some absolute unspecified constant C>0. Our estimates show that their C is of order 2^{300,000}. We give a novel algorithm that makes at most O(256^d) mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than 3^d mistakes
--
Saludos
Sasha