We address the problem of predicting the labeling of a graph in an online setting when the labeling is changing over time. We provide three mistake-bounded algorithms based on three paradigmatic methods for online-algorithm design. Our primary algorithm is based on a specialist approach; we develop the machinery of cluster specialists which probabilistically exploits the cluster structure in the graph. We show that this algorithm surprisingly only requires O(log(n)) time on any trial t. Our second algorithm with the strongest guarantee is a quasi-Bayesian classifier which requires O(tlog(n)) time to predict at trial t on an n-vertex graph. We also give an algorithm based on a kernelized Perceptron with an intermediate per-trial time complexity of O(n) and a mistake bound which is not strictly comparable. We finally compare the performance of these algorithms using experiments on simulated data.
We address the problem of sequential prediction with expert advice in a non-stationary environment with long-term memory guarantees in the sense of Bousquet and Warmuth [4]. We give a linear-time algorithm that improves on the best known regret bounds [26]. This algorithm incorporates a relative entropy projection step. This projection is advantageous over previous weight-sharing approaches in that weight updates may come with implicit costs as in for example portfolio optimization. We give an algorithm to compute this projection step in linear time, which may be of independent interest.
I'm currently pursuing a PhD in machine learning at UCL. Before working in this field I obtained my masters degree in Physics from the Univeristy of Nottingham.
I also enjoy full-stack web development (I built this site using Django).
I am interested in collaborating and working on interesting projects. Don't hesitate to contact me!
