Online Prediction on Large Diameter Graphs
Mark Herbster, Guy Lever, Massimiliano Pontil University College London

ID: M66

Overview: Laplacian min semi-norm interpolant versus "prediction via spine"
Laplacian min semi-norm interpolant
v1

Prediction via graph's spine
2 1 5 6 3 4 7

8

10 9

v2

vn

v3

v4

1

2

6

8

3

4

5

7

10

9

Octopus with "cut size" k = 1  1 octopus : ( n)  Mistakes  k joined octopi: ( kn)  Mistakes

Graph is embedded into path graph 1-NN on path is now Bayes optimal
n Mistakes  O (k log( k ) + k )

n ( kn)  O (k log( ) + k ) k Conclusion: Spine is a minimax improvement over semi-norm interpolant