The Non-linear $F$-Design and Applications to Interactive Learning

Alekh Agarwal, Jian Qian, Alexander Rakhlin, Tong ZhangICML 2024 · OpenReview

Introduction

In machine learning and statistics, experimental design is the art of choosing which data points to query to learn a model as efficiently as possible. For linear models, the classical theory of "$G$-optimal design" provides a mathematically elegant way to select a small set of query points that allows for confident extrapolation across the entire domain.

However, modern machine learning relies heavily on non-linear models, where finding an optimal set of query points is notoriously difficult. Different non-linear functions fluctuate wildly in different parts of the input space. Historically, researchers have tackled this by either assuming close proximity to the optimal solution (using local Taylor approximations) or relying on complexity measures like the eluder dimension. Unfortunately, the eluder dimension can be overly pessimistic, suggesting the need for exponentially more samples than practically required.

This paper introduces $F$-design, a novel generalization of classical $G$-optimal experimental design tailored specifically for non-linear function classes. By minimizing a new metric called the "$F$-condition number," the authors provide a powerful, drop-in exploration strategy for interactive machine learning tasks, achieving state-of-the-art theoretical guarantees without requiring local approximations.

The $F$-Design Framework

The authors introduce a new mathematical framework centered around two key concepts:

  • The $F$-Condition Number: This metric evaluates the quality of a specific "design" (a probability distribution over the input space). It measures the worst-case ratio between the squared error at any specific point in the domain versus the average squared error across the points sampled by the design. Essentially, it asks: "If the error on the sampled points is controlled, how bad can the error get anywhere else?"
  • $F$-Design: This is the optimal probability distribution over the input space that minimizes the $F$-condition number.

To make this practical, the authors provide a greedy algorithm that constructs sparse designs using an "argmax oracle"—a computational subroutine that finds the hardest instance to predict for a given design. In interactive settings like bandits or reinforcement learning (RL), an agent can use the $F$-design over the action space to decide which actions to test, ensuring optimal data collection.

Theoretical Insights

The $F$-design framework yields several compelling theoretical properties:

  • Perfect Backward Compatibility: When the underlying function class is linear, the $F$-design perfectly coincides with the classical $G$-optimal design, and the $F$-condition number equals the ambient dimension $d$.
  • Exponentially Better than Eluder Dimension: The optimal $F$-condition number is always upper-bounded by the eluder dimension (up to log factors). Crucially, the authors provide a mathematical example where the $F$-condition number is exponentially smaller than the eluder dimension, proving $F$-design can be vastly more sample-efficient for non-linear exploration.
  • A Universal Drop-in Replacement: $F$-design can be seamlessly integrated into existing interactive learning algorithms. Swapping uniform sampling or linear $G$-design for $F$-design instantly upgrades an algorithm to handle non-linear function classes with infinite action spaces.

Applications and Key Results

The authors apply $F$-design to four diverse learning settings, matching or beating state-of-the-art theoretical bounds.

Summary of theoretical bounds achieved by F-design across four interactive learning settings.
  1. Simultaneous Confidence Bands: For non-linear regression, $F$-design allows the construction of confidence bands where the worst-case error scales cleanly with the optimal $F$-condition number ($\mathcal{V}^*$) and the mean squared error.
  2. Contextual Bandits: In realizable settings with potentially infinite action spaces, using $F$-design for exploration yields a PAC regret bound of $\mathcal{O}(\sqrt{\mathcal{V}^* \log|\mathcal{F}| / T})$.
  3. Model-Free Reinforcement Learning: For Markov Decision Processes (MDPs) with a bounded "Bellman rank" and infinite actions, $F$-design achieves a PAC regret of $\mathcal{O}(\log(|\mathcal{F}|T)\sqrt{\text{br} \cdot \mathcal{V}^* H / T})$. This establishes new sample-efficient results for RL environments where Q-values are smooth over actions.
  4. Active Learning: In pool-based active classification, $F$-design bounds the query complexity to $\mathcal{O}(\mathcal{V}^* \log|\mathcal{F}|)$, improving upon recent methods that scale with the much larger eluder dimension.

Limitations and Future Directions

While theoretically powerful, the framework has some current limitations:

  • Computational Bottlenecks: Finding the optimal design efficiently remains an open problem. The current subgradient descent approach requires computing over the entire design space, which is intractable for massive or continuous spaces.
  • Online Regret Minimization: The paper primarily applies $F$-design to pure exploration (PAC regret). Applying it directly to online regret minimization is less straightforward, though there are promising theoretical links between $F$-design and the Decision-Estimation Coefficient (DEC).
  • Other Classical Criteria: Future work could explore non-linear extensions of other classical experimental design criteria (like A-, D-, or L-optimal designs), which might offer complementary benefits to the $G$-optimal generalization presented here.

Summary updated

Abstract

We propose a generalization of the classical G-optimal design concept to non-linear function classes. The criterion, termed F -design, coincides with G-design in the linear case. We compute the value of the optimal design, termed the F-condition number, for several non-linear function classes. We further provide algorithms to construct designs with a bounded F -condition number. Finally, we employ the F-design in a variety of interactive machine learning tasks, where the design is naturally useful for data collection or exploration. We show that in four diverse settings of confidence band construction, contextual bandits, model-free reinforcement learning, and active learning, F-design can be combined with existing approaches in a black-box manner to yield state-of-the-art results in known problem settings as well as to generalize to novel ones.
BibTeX
@inproceedings{agarwal2024non,
  author = {Alekh Agarwal and Jian Qian and Alexander Rakhlin and Tong Zhang},
  title = {{The Non-linear $F$-Design and Applications to Interactive Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=MMMHufVc2v},
}
Figure