Incremental learning with and without queries in binary choice problems

We consider a binary choice problem represented by a conditional probability p(s|x), where input x∈[0,1] and output s∈{-1,+1}. The function p(s|x) is assumed to be monotonically increasing with respect to x. For the best prediction, the learner must fix the optimal boundary θ_o determined by p(s=+1|θ_o)=p(s=-1|θ_o)=1/2 without precise knowledge of the function. Learning algorithms should work incrementally for practicality, if possible. We present incremental algorithms which ensure that the learner fixes the optimal parameter θ_o in the limit that the number of examples t becomes infinite. We further investigate the rate of convergence in the following two typical cases. When the learner can specify the position of input x by queries in the course of learning, the mean square deviation <(θ-θ_o)²> decreases as O(t^-1). On the other hand, if x is chosen independently from some distribution p(x), the learner cannot attain convergence as O(t^-1), but rather as O(t^-45/). This rate can be accelerated by an elaborate technique up to O((In t)²t^-1), as t→∞.