1
$\begingroup$

Let us say that an arithmetic series is a series of the form $s_t = \{0, t, 2t, \ldots\}$. For example, $s_3 = \{0, 3, 6, \ldots\}$. Now consider the concept class composed of all arithmetic series of that form, i.e. $S = \{s_0, s_1, s_2, \ldots\}$.

Is there a learning algorithm under the mistake bound model for learning this concept class $S$?

$\endgroup$

1 Answer 1

1
$\begingroup$

An arithmetic series is defined by the 1st term $t_1$ and the difference between terms $d$. If you stipulate that $\max(|t_1|,d)\le M$ then you have a finite hypothesis space and hence a finite mistake bound (e.g., via the halving algorithm). Otherwise, one can make $|t_1|$ arbitrarily large so as to thwart any proposed mistake bound.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer! A further question: does there happen to exist a PAC learning algorithm for the concept class of arithmetic series? For simplicity, we can assume that for each concept in the class, the first term $t_1 = 0$ and that the difference between terms $d = 0, 1, 2, \ldots$ across the concepts. $\endgroup$
    – user70055
    Nov 15, 2023 at 7:52
  • $\begingroup$ That should be a new question. Feel free to accept my answer so that this question can be closed. $\endgroup$
    – Aryeh
    Nov 15, 2023 at 11:02
  • $\begingroup$ I have asked a new question here: cstheory.stackexchange.com/questions/53543/… $\endgroup$
    – user70055
    Nov 16, 2023 at 3:08
  • $\begingroup$ I don't think that question is quite the same as the arithmetic series one but I answered it. $\endgroup$
    – Aryeh
    Nov 16, 2023 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.