# Online Learning of Neural Networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 14 May 2025.

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

- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Online Deep Learning: Learning Deep Neural Networks on the Fly](https://mlsanity.com/paper/1711.03705/) (2017)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Mathematical theory of deep learning](https://mlsanity.com/paper/2407.18384/) (2024)
- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (2025)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions](https://mlsanity.com/paper/2502.06443/) (2025)
- [Online Learning with an Almost Perfect Expert](https://mlsanity.com/paper/1807.11169/) (2018)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [Incremental Online Learning of Randomized Neural Network with Forward Regularization](https://mlsanity.com/paper/2412.13096/) (2024)

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

- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Age of Learning: Temporal Persistence of Prediction Errors as a Learning Signal](https://mlsanity.com/paper/2609.32593/) (2026)

## Abstract (arXiv)

We study online learning of feedforward neural networks with the sign activation function that implement functions from the unit ball in ℝd to a finite label set 1, ldots, Y. First, we characterize a margin condition that is sufficient and in some cases necessary for online learnability of a neural network: Every neuron in the first hidden layer classifies all instances with some margin γ bounded away from zero. Quantitatively, we prove that for any net, the optimal mistake bound is at most approximately mathttTS(d,γ), which is the (d,γ)-totally-separable-packing number, a more restricted variation of the standard (d,γ)-packing number. We complement this result by constructing a net on which any learner makes mathttTS(d,γ) many mistakes. We also give a quantitative lower bound of approximately mathttTS(d,γ) ≥ max1/(γ √d)d, d when γ ≥ 1/2, implying that for some nets and input sequences every learner will err for exp(d) many times, and that a dimension-free mistake bound is almost always impossible. To remedy this inevitable dependence on d, it is natural to seek additional natural restrictions to be placed on the network, so that the dependence on d is removed. We study two such restrictions. The first is the multi-index model, in which the function computed by the net depends only on k ll d orthonormal directions. We prove a mistake bound of approximately (1.5/γ)k + 2 in this model. The second is the extended margin assumption. In this setting, we assume that all neurons (in all layers) in the network classify every ingoing input from previous layer with margin γ bounded away from zero. In this model, we prove a mistake bound of approximately (log Y)/ γO(L), where L is the depth of the network.