Locally-Adaptive Nonparametric Online Learning

Ilja Kuzborskij, Nicolò Cesa-Bianchi

In the world of online learning, an algorithm must make predictions on the fly, often without knowing the underlying rules of the environment. To handle complex data, researchers often turn to nonparametric methods, which don't assume a simple shape for the data. Instead, they might assume the target function is "Lipschitz"—meaning it doesn't change too abruptly.

However, standard algorithms usually assume a single, global "smoothness" level. This paper from researchers at DeepMind and the University of Milan introduces a more nuanced approach: an algorithm that adapts to local regularities, performing better in smooth regions without losing its edge in complex ones.

TL;DR

The paper introduces a new online learning framework that automatically adapts to local regularities in data, such as varying smoothness or dimensionality. By dynamically building a hierarchical tree of local learners, the proposed algorithm achieves significantly better performance in complex environments while remaining computationally efficient.

What Problem Does This Paper Address?

Standard nonparametric online learning algorithms often assume global regularity. For instance, they might use a single Lipschitz constant $L$ to describe how much a function can vary. But real-world data is rarely uniform; a function might be very smooth in one part of the input space and highly volatile in another.

If an algorithm assumes the whole world is as "wiggly" as its most volatile part, it wastes effort and suffers higher regret (the difference between the algorithm's performance and the best possible function in hindsight). Conversely, if it assumes everything is smooth, it fails to capture complex patterns. The challenge is to create an algorithm that can "see" these local patterns and adapt its complexity accordingly, all while processing data one point at a time.

Methods

The authors propose a Locally-Adaptive (LA) algorithm based on a few key technical pillars:

  1. Hierarchical $\epsilon$-nets: The algorithm builds a tree structure where each node represents a "ball" (a region) in the input space. As more data arrives, it refines this tree, creating smaller balls at deeper levels to capture finer details.
  2. Sleeping Experts Framework: Every node in the tree hosts a "local learner." For any given input, only the learners on the path from the root to the leaf containing that input are "awake" and contributing to the prediction.
  3. Competing Against Prunings: A "pruning" of the tree represents a specific "locality profile"—essentially a map of which regions are simple and which are complex. The algorithm uses a sophisticated "tree expert" technique to efficiently compete against all possible prunings simultaneously.
  4. Multi-faceted Adaptivity: The framework is versatile. The authors show it can adapt to:
  5. Local Lipschitzness: How smooth the function is in different regions.
  6. Local Metric Dimension: Whether the data in a certain region actually lives on a simpler, lower-dimensional manifold.
  7. Local Performance: How well the local learners are actually doing in specific regions.

Datasets

The paper is primarily a theoretical contribution. To illustrate their findings, the authors use toy one-dimensional data sequences where the target function has clearly defined regions of varying smoothness (e.g., a flat line with occasional high-frequency spikes). No large-scale real-world datasets were used for the primary evaluation.

Key Insights and Ideas

  • Matching Smoothness to Tree Depth: A core insight is that local smoothness can be mapped directly to tree prunings. A smooth region of a function is best "matched" by a shallow leaf in the tree, while a complex region requires a deep leaf. Conceptual mapping of functions to tree prunings
  • The "Best of Both Worlds" Guarantee: The algorithm is designed so that its regret bound scales with the local properties of the data it actually sees. Crucially, even in the worst-case scenario where the data has no local regularity, the algorithm's performance is no worse than standard global methods.
  • Computational Efficiency: Despite competing against an exponential number of possible prunings, the algorithm is highly efficient. The time required for each prediction and update is only logarithmic in the size of the tree (linear in the tree depth $D$).

Key Results

  • Theoretical Regret Bounds: The authors prove new regret bounds that explicitly depend on local Lipschitz constants and local dimensions. These bounds are significantly tighter than previous "global" bounds when local regularities exist.
  • Empirical Proof of Concept: In simulations, the LA algorithm achieves much lower regret than the standard Hazan-Megiddo (HM) algorithm when the target function's complexity varies across the space. Regret comparison between LA and HM algorithms

Limitations and Future Work

  • Memory Growth: Because the algorithm dynamically constructs a tree as it sees more data, its memory usage grows linearly with time. This could be a bottleneck for very long-running applications.
  • Future Directions: The authors suggest investigating "budgeted" versions of the algorithm that could operate within a fixed memory limit. They also aim to extend the "parameter-free" local learning approach (currently used for classification) to a wider range of loss functions.

Summary updated

Abstract

One of the main strengths of online algorithms is their ability to adapt to arbitrary data sequences. This is especially important in nonparametric settings, where performance is measured against rich classes of comparator functions that are able to fit complex environments. Although such hard comparators and complex environments may exhibit local regularities, efficient algorithms, which can provably take advantage of these local patterns, are hardly known. We fill this gap by introducing efficient online algorithms (based on a single versatile master algorithm) each adapting to one of the following regularities: (i) local Lipschitzness of the competitor function, (ii) local metric dimension of the instance sequence, (iii) local performance of the predictor across different regions of the instance space. Extending previous approaches, we design algorithms that dynamically grow hierarchical ε-nets on the instance space whose prunings correspond to different “locality profiles” for the problem at hand. Using a technique based on tree experts, we simultaneously and efficiently compete against all such prunings, and prove regret bounds each scaling with a quantity associated with a different type of local regularity. When competing against “simple” locality profiles, our technique delivers regret bounds that are significantly better than those proven using the previous approach. On the other hand, the time dependence of our bounds is not worse than that obtained by ignoring any local regularities.
BibTeX
@inproceedings{kuzborskij2020locally,
  author = {Ilja Kuzborskij and Nicolò Cesa-Bianchi},
  title = {{Locally-Adaptive Nonparametric Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=vrZIeE6OaKC},
}

Loading related content...

Figure