An Online Algorithm for Learning a Labeling of a Graph

This short report analyzes a simple and intuitive online learning algorithm - termed the graphtron - for learning a labeling over a fixed graph, given a sequence of labels. The contribution is twofold, (a) we give a theoretical characterization of the possible sequence of mistakes, and (b) we indicate the use for extremely large-scale problems due to sublinear space complexity and nearly linear time complexity. This work originated from numerous discussions with John, Mark and with Johan.