TL;DR#
Online and batch learning are two common approaches to train classifiers. While batch learning trains a model on a fixed dataset, online learning updates the model sequentially with each new data point. Recent studies suggested that smoothed online learning (where data is drawn from a distribution with bounded density) might be as easy as batch learning. However, this paper reveals some important issues and challenges associated with online learning. Specifically, it focuses on the limitations of existing theories in scenarios with unbounded label spaces (where the number of possible class labels is infinite). This situation is common in real-world applications such as face recognition or protein structure prediction.
This research introduces a novel hypothesis class to show that existing theories fail for infinite label spaces. It demonstrates that a hypothesis class learnable in a batch setting (PAC learnable) might not be learnable in a smoothed online setting. Despite this hardness result, the paper proposes a new condition, called UBEME (Uniformly Bounded Expected Metric Entropy), that guarantees smoothed online learnability. This work contributes significantly to online learning theory by improving our understanding of its limits and providing new tools for analysis and algorithm development.
Key Takeaways#
Why does it matter?#
This paper is crucial because it challenges the common belief that smoothed online learning mirrors batch learning. It highlights the challenges of online learning with infinite label spaces, opening avenues for improved algorithm design and theoretical understanding. This research directly addresses the growing interest in multiclass learnability with unbounded label spaces, a prevalent issue in many modern machine learning applications.
Visual Insights#
Full paper#
