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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – meeeeee
    Nov 15 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 at 11:02
  • $\begingroup$ I have asked a new question here: cstheory.stackexchange.com/questions/53543/… $\endgroup$
    – meeeeee
    Nov 16 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 at 13:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.