The Dimension of Self-Directed Learning
Pramith Devulapalli Steve Hanneke
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.