Online Prediction on Large Diameter Graphs
Published on Dec 20, 20083305 Views
We continue our study of online prediction of the labelling of a graph. We show a fundamental limitation of Laplacian-based algorithms: if the graph has a large diameter then the number of mistakes ma