Prediction on a graph

We will discuss the problem of robust online learning over a graph. Consider the following game for predicting the labeling of a graph. ”Nature” presents a vertex v1; the ”learner” predicts the label of the vertex ˆy1; nature presents a label y1; nature presents a vertex v2; the learner predicts ˆy2; and so forth. The learner’s goal is minimize the total number of mistakes. If nature is adversarial, the learner will always mispredict; but if nature is regular or simple, there is hope that a learner may make only a few mispredictions. Thus, a methodological goal is to give learners whose total mispredictions can be bounded relative to the ”complexity” of nature’s labeling. In this talk, we consider the ”label cut size” as a measure of the complexity of a graph’s labeling, where the size of the cut is the number of edges between disagreeing labels. We will give bounds which depend on the cut size and the (resistance) diameter of the graph.