Learning Integer Lattices
David P. Helmbold, Robert H. Sloan, Manfred K. Warmuth · SIAM Journal on Computing · 1992
The problem of learning an integer lattice of ${\bf Z}^k $ in an on-line fashion is considered. That is, the learning algorithm is given a sequence of k-tuples of integers and predicts for each tuple in the sequence whether it lies in a hidden target lattice of ${\bf Z}^k $. The goal of the algorithm is to minimize the number of prediction mistakes. An efficient learning algorithm with an absolute mistake bound of $k + \lfloor k\log (n\sqrt k ) \rfloor $ is given, where n is the maximum component of any tuple seen. It is shown that this bound is approximately a $\log \log n$ factor larger than the lower bound on the worst case number of mistakes given by the VC dimension of lattices that are restricted to $\{ - n, \cdots ,0, \cdots ,n \}^k $. This algorithm is used to learn rational lattices, cosets of lattices, an on-line word problem for abelian groups, and a subclass of the commutative regular languages. Furthermore, by adapting the results of [D. Helmbold, R. Sloan, and M. K. Warmuth, Machine Learning, 5 (1990), pp. 165–196], one can efficiently learn nested differences of each of the above classes (e.g., concepts of the form $c_1 - (c_2 - (c_3 - (c_4 - c_5 )))$, where each $c_i $ is the coset of a lattice).