# Self-Directed Linear Classification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 64 references that are in the map.
- First posted on arXiv 6 Aug 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [On The Power of Curriculum Learning in Training Deep Networks](https://mlsanity.com/paper/1904.03626/) (2019)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [On Radial Isotropic Position: Theory and Algorithms](https://mlsanity.com/paper/2005.04918/) (2020)

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

- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)

## Abstract (arXiv)

In online classification, a learner is presented with a sequence of examples and aims to predict their labels in an online fashion so as to minimize the total number of mistakes. In the self-directed variant, the learner knows in advance the pool of examples and can adaptively choose the order in which predictions are made. Here we study the power of choosing the prediction order and establish the first strong separation between worst-order and random-order learning for the fundamental task of linear classification. Prior to our work, such a separation was known only for very restricted concept classes, e.g., one-dimensional thresholds or axis-aligned rectangles. We present two main results. If X is a dataset of n points drawn uniformly at random from the d-dimensional unit sphere, we design an efficient self-directed learner that makes O(d log log(n)) mistakes and classifies the entire dataset. If X is an arbitrary d-dimensional dataset of size n, we design an efficient self-directed learner that predicts the labels of 99% of the points in X with mistake bound independent of n. In contrast, under a worst- or random-ordering, the number of mistakes must be at least Omega(d log n), even when the points are drawn uniformly from the unit sphere and the learner only needs to predict the labels for 1% of them.