A Tutorial on Online Supervised Learning with Applications to Node Classification in Social Networks

Alexander Rakhlin, Karthik SridharanarXiv 2016 · OpenReview

Abstract

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.

Introduction

Traditional machine learning often assumes data is generated from a well-behaved stochastic process, such as i.i.d. data. However, in complex environments like social networks, these assumptions frequently break down due to intricate interactions, time dependencies, and potentially adversarial behaviors. This tutorial addresses the challenge of online supervised learning—predicting a sequence of labels one by one and receiving feedback after each step—in a purely non-stochastic setting.

A significant hurdle in this domain is the computational bottleneck: for structured data like graphs, finding the best predictive model in hindsight (the offline benchmark) is often an NP-hard combinatorial problem. This work explores how to bypass this intractability while maintaining strong predictive performance guarantees against adversarial sequences.

Methodology: Cover's Observation and Improper Learning

The foundation of this approach is T. Cover's 1965 observation. If one can define a "stable" potential function $\phi$ representing the expected proportion of tolerable mistakes, and its expected value over random coin flips is at least $1/2$, a randomized algorithm exists that guarantees this mistake bound for any sequence.

Building on this, the authors propose algorithms for computationally hard problems using three key concepts:

  1. Improper Learning: Instead of forcing the algorithm to output a solution from the original NP-hard set of models (e.g., exact graph cuts), the algorithm is allowed to make predictions that do not strictly belong to that set.
  2. Convex Relaxations: To ensure computability, strict combinatorial constraints are relaxed into Semidefinite Programs (SDPs) or using the Lasserre hierarchy.
  3. Doubly-Randomized Strategies: To avoid costly exact minimax computations at every time step, a "random playout" technique is used. The algorithm simulates random future paths (hallucinating future coin flips) to efficiently approximate the optimal prediction.

Application: Node Classification in Social Networks

The applicability of these methods is particularly evident in node classification within networks. In a social network, one might wish to predict user attributes or preferences based on the network structure and observed labels of neighbors.

Figure 1: Illustration of a social network where node classification tasks, such as predicting user preferences or labels, are performed in an online setting.

For node classification on weighted graphs, where the offline benchmark is the NP-hard MinUnCut problem, the authors demonstrate that an SDP relaxation can achieve a strong regret bound. This allows for effective prediction even when finding the absolute best model is computationally unfeasible.

Key Results and Theoretical Insights

  • Probabilistic checks for deterministic bounds: Existence of a forecasting strategy with a specific mistake bound on arbitrary sequences can be verified via a probabilistic inequality over uniform random noise, requiring no statistical assumptions about the data.
  • The power of improper learning: Relaxing the constraint set allows algorithms to predict as well as the combinatorial benchmark, plus a lower-order error term, without solving NP-hard problems.
  • Integrality gaps and analysis: When using computational hierarchies, the "integrality gap" (the cost of approximation) only affects the theoretical mistake bound analysis. The prediction algorithm itself does not require complex "rounding" of the relaxed solution.
  • Hallucinating the future: For settings with side information, the optimal strategy involves "rolling out the future" by hallucinating upcoming data points using unlabeled data, effectively handling adaptive adversaries.

The authors prove that achieving a specific mistake bound against an adaptive adversary is mathematically equivalent to bounding the sequential Rademacher complexity of the hypothesis class.

Discussion and Future Directions

While these methods provide a robust framework for online learning, certain limitations remain. The upper bounds derived for Rademacher averages of relaxed sets can be crude, and the exact price paid for using relaxed solutions is not always precisely known. Furthermore, while SDP relaxations are polynomial-time, they remain computationally intensive for massive real-world networks.

Future research directions include developing linear or sublinear time methods for large-scale graphs, conducting empirical evaluations on real-world data to optimize potential functions, and extending these methods to partial-information settings like contextual bandits.

Summary updated

Abstract

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.
BibTeX
@misc{rakhlin2016tutorial,
  author = {Alexander Rakhlin and Karthik Sridharan},
  title = {{A Tutorial on Online Supervised Learning with Applications to Node Classification in Social Networks}},
  year = {2016},
  eprint = {1608.09014},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.09014},
}
Figure