Online learning with linear loss constraints.

D. P. Helmbold, N. Littlestone and P. M. Long. Online learning with linear loss constraints. Information and Computation, 161(2):140-171, 2000.

(Available in Postscript and PDF formats.)

Abstract
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 formulation of this problem. We describe several applications of our general results, involving situations in which the learner wishes to satisfy linear inequalities in M+ and M-.