2016/08/31 by Alexander Rakhlin, Rakhlin, Alexander, Karthik Sridharan +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Spam and Phishing Detection
paper · pdf · doi:10.48550/arxiv.1608.09014
openalex publication_date 2016/08/31 · openalex created_date 2016/09/16 · openalex updated_date 2026/07/28
We revisit the elegant observation of T. Cover '65 which, perhaps, is not as well-known to the broader community as it should be. The first goal of the tutorial is to explain---through the prism of this elementary result---how to solve certain sequence prediction problems by modeling sets of solutions rather than the unknown data-generating mechanism. We extend Cover's observation in several directions and focus on computational aspects of the proposed algorithms. The applicability of the methods is illustrated on several examples, including node classification in a network. The second aim of this tutorial is to demonstrate the following phenomenon: it is possible to predict as well as a combinatorial "benchmark" for which we have a certain multiplicative approximation algorithm, even if the exact computation of the benchmark given all the data is NP-hard. The proposed prediction methods, therefore, circumvent some of the computational difficulties associated with finding the best model given the data. These difficulties arise rather quickly when one attempts to develop a probabilistic model for graph-based or other problems with a combinatorial structure.