On batch learning in a binary weight setting

摘要

Considers the problem of inferring a finite binary sequencew*∈{-1,1}n from a random sequence of half-space data {u(t)∈{-1,1}n:〈w*,u/sup(t/)〉⩾0,t⩾1}. In this context, we show that a previouslyproposed randomised on-line learning algorithm dubbed directed drift[Venkatesh, 1993] has minimal space complexity but an expected mistakebound exponential in n. We show that batch incarnations of the algorithmallow of massive improvements in running time. In particular, using abatch of ½πn log n examples at each update epoch reduces theexpected mistake bound to 𝒪(n) in a single bit update mode, whileusing a batch of πn log n examples at each update epoch in a multiplebit update mode leads to convergence to w* with a constant (independentof n) expected mistake bound