15 April talk

54 views
Skip to first unread message

kozmath

unread,
Apr 10, 2024, 8:17:03 PMApr 10
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

kozmath

unread,
Apr 15, 2024, 11:18:05 AMApr 15
to Kolmogorov seminar on complexity

kozmath

unread,
Apr 15, 2024, 1:37:53 PMApr 15
to koz...@proton.me, Kolmogorov seminar on complexity
That's the paper from today...


https://arxiv.org/abs/2308.08055



Sent with Proton Mail secure email.

> --
> Вы получили это сообщение, поскольку подписаны на группу Kolmogorov seminar on complexity.
>
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
> Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/EF89o3GiBvK0BouYUkr_7iAN3XjK6VuExSFHR2qRNdVi92Ss9v37EPaaSg2QL94Opdyy_6yzKSP12i45mFB7ZXkYSyG7rtAk7sarDz_iE4g%3D%40proton.me.
Reply all
Reply to author
Forward
0 new messages