# The Dimension of Self-Directed Learning

arXiv: https://arxiv.org/abs/2402.13400 · HTML: https://mlsanity.com/paper/2402.13400/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 20 Feb 2024.

## Builds on (most cited first, 3 of 3)

- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [2 Notes on Classes with Vapnik-Chervonenkis Dimension 1](https://mlsanity.com/paper/1507.05307/) (2015)
- [Bounds in Query Learning](https://mlsanity.com/paper/1904.10122/) (2019)

## Built on by (most cited first, 4 of 4)

- [Learning from Snapshots of Discrete and Continuous Data Streams](https://mlsanity.com/paper/2412.06079/) (2024)
- [Formal Models of Active Learning from Contrastive Examples](https://mlsanity.com/paper/2506.15893/) (2025)
- [Self-Directed Learning of Convex Labelings on Graphs](https://mlsanity.com/paper/2409.01428/) (2024)
- [Thompson Sampling Is 2-Competitive for Mistakes](https://mlsanity.com/paper/2607.12389/) (2026)

## Abstract (arXiv)

Understanding the self-directed learning complexity has been an important problem that has captured the attention of the online learning theory community since the early 1990s. Within this framework, the learner is allowed to adaptively choose its next data point in making predictions unlike the setting in adversarial online learning. In this paper, we study the self-directed learning complexity in both the binary and multi-class settings, and we develop a dimension, namely SDdim, that exactly characterizes the self-directed learning mistake-bound for any concept class. The intuition behind SDdim can be understood as a two-player game called the "labelling game". Armed with this two-player game, we calculate SDdim on a whole host of examples with notable results on axis-aligned rectangles, VC dimension 1 classes, and linear separators. We demonstrate several learnability gaps with a central focus on self-directed learning and offline sequence learning models that include either the best or worst ordering. Finally, we extend our analysis to the self-directed binary agnostic setting where we derive upper and lower bounds.