Online learning algorithms such as Winnow have received much attention in
Machine Learning. Their performance degrades only logarithmically with the
input dimension, making them useful in large spaces such as relational
theories. However, online first-order learners are intrinsically limited by a
computational barrier: even in the finite, function-free case, the number of
possible features grows exponentially with the number of first-order atoms
generated from the vocabulary. To circumvent this issue, we exploit the
paradigm of closure-based learning which allows the learner to focus on the
features that lie in the closure space generated from the examples which have
lead to a mistake. Based on this idea, we develop an online algorithm for
learning theories formed by disjunctions of existentially quantified
conjunctions of atoms. In this setting, we show that the number of mistakes
depends only logarithmically on the number of features. Furthermore, the
computational cost is essentially bounded by the size of the closure lattice.