Timezone: »

On-Line Prediction on Large Diameter Graphs
Mark Herbster · Massimiliano Pontil · Guy Lever

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @

Current on-line learning algorithms for predicting the labelling of a graph have an important limitation in the case of large diameter graphs; the number of mistakes made by such algorithms may be proportional to the square root of the number of vertices, even when tackling simple problems. We overcome this problem with an efficient algorithm which achieves a logarithmic mistake bound. Furthermore, current algorithms are optimised for data which exhibits cluster-structure; we give an additional algorithm which performs well locally in the presence of cluster structure and on large diameter graphs.

Author Information

Mark Herbster (University College London)
Massimiliano Pontil (IIT & UCL)
Guy Lever (UCL)

More from the Same Authors