On-line learning with linear loss constraints

We consider a generalization of the mistake-bound model (for learning {0, 1 }-valued functions) in which the learner must satisfy a general constraint on the number M+ of incorrect 1 predictions and the number M- of incorrect 0 predictions. We describe a general-purpose optimal algorithm for our form ulation of this problem, We describe several applications of our general re sults, involving situations in which the learner wishes to satisfy linear i nequalities in M+ and M-. (C) 2000 Academic Press.