# Online Learning of Halfspaces with Massart Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 21 May 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2006.06467/) (2020)
- [Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2201.09818/) (2022)
- [Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability](https://mlsanity.com/paper/2006.04787/) (2020)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)

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

- [The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification](https://mlsanity.com/paper/2510.01020/) (2025)

## Abstract (arXiv)

We study the task of online learning in the presence of Massart noise. Instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the context x is selected adversarially but the label y presented to the learner disagrees with the ground-truth label of x with unknown probability at most η. We study the fundamental class of γ-margin linear classifiers and present a computationally efficient algorithm that achieves mistake bound η T + o(T). Our mistake bound is qualitatively tight for efficient algorithms: it is known that even in the offline setting achieving classification error better than η requires super-polynomial time in the SQ model. We extend our online learning model to a k-arm contextual bandit setting where the rewards -- instead of satisfying commonly used realizability assumptions -- are consistent (in expectation) with some linear ranking function with weight vector w^ast. Given a list of contexts x1,ldots xk, if w^*· xi > w^* · xj, the expected reward of action i must be larger than that of j by at least Delta. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least (1-1/k)~ Delta T - o(T) bigger than choosing a random action at every round.