# Learning arithmetic series

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

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.
• 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. Nov 15 at 7:52