Online Learning of Neural Networks

Amit Daniely, Idan Mehalel, Elchanan Mossel

TL;DR

This paper provides the first tight theoretical characterization of online learning for feedforward neural networks with sign activation functions. The authors reveal that a network's online learnability is fundamentally governed by a geometric quantity called the "totally-separable-packing number," which unfortunately scales exponentially with input dimension. To bypass this curse of dimensionality, they introduce two natural structural constraints—the multi-index model and an all-layer margin assumption—that successfully unlock dimension-free online learning.

What Problem Does This Paper Address?

In online learning, a model learns sequentially: it receives an adversarial data point, makes a prediction, suffers a loss if it's wrong, and updates itself for the next round. While we have optimal, dimension-free mistake bounds for simple linear classifiers (like the classic Perceptron), extending these guarantees to deep neural networks has proven incredibly difficult.

Most existing neural network theories rely on the assumption that data is sampled independently and identically distributed (i.e., the i.i.d. PAC-learning setting). Real-world data, however, is often highly adversarial or sequential (e.g., weather forecasting, stock market trends, or next-token prediction in transformers). Furthermore, analyzing networks with discrete activations like the sign function—which are highly popular in resource-constrained Binarized Neural Networks (BNNs)—is notoriously hard because you cannot use gradient descent.

This paper tackles a foundational question: What geometric properties dictate whether a neural network can successfully learn in an adversarial online environment, and can we achieve mistake bounds that do not explode as the input dimension grows?

Methods

The authors analyze neural networks through a clever "two-station" perspective:

  1. Station 1 (First Hidden Layer): Partitions the continuous input space into discrete geometric regions.
  2. Station 2 (Subsequent Layers): Maps these discrete regions to final output labels.

To exploit this structure, they design a Meta-Learner Framework based on a multiclass extension of the classic Weighted Majority (WM) algorithm. This meta-learner manages a pool of "experts." Each expert consists of simulated perceptrons (Neuron_p) that are fed a binary "manual" vector telling them exactly when to update their weights.

To achieve dimension-free bounds under tighter constraints, the authors introduce a novel margin-based pruning technique grounded in Vapnik-Chervonenkis (VC) theory. By applying the uniform convergence theorem, they prove that if a network has a healthy classification margin across all its layers, it can be aggressively pruned down to a tiny subset of "important" neurons without changing its classification behavior on the input sequence.

Finally, because real-world learners rarely know the exact margin ($\gamma$) or complexity exponents ($b$) of their data in advance, the authors develop an adaptive algorithm (Adap) that uses a grid-search doubling trick to automatically adapt to these parameters online.

Datasets

This is a purely theoretical paper focused on proving fundamental sample complexity limits and algorithmic bounds. Consequently, no empirical datasets or benchmarks were used for training or evaluation.

Key Insights and Ideas

  • The TS-Packing Number Rules Online Learning: The authors show that the optimal mistake bound is tightly characterized by the totally-separable-packing (TS-packing) number. Unlike standard packing, TS-packing requires that every pair of points in a set can be linearly separated by a hyperplane that completely avoids the margins of all other points.
  • The Inevitable Curse of Dimension: The paper proves that for general networks, the TS-packing number scales exponentially with the input dimension ($d$). This means that without further constraints, an adversary can always force any online learner to make exponentially many mistakes ($\exp(d)$), making dimension-free learning impossible in the general case.
  • Pruning is Mathematically Justified: Under the "extended margin assumption" (where every neuron in every layer has a margin $\gamma$), uniform convergence guarantees that the vast majority of neurons are redundant. This provides a beautiful, foundational theoretical justification for the practical paradigm of neural network pruning.

Key Results

  • General Bound: The optimal mistake bound for a network with a first-layer margin $\gamma_1$ is tightly bounded by: $$\tilde{O}\left(\frac{\mathtt{TS}(d, \gamma_1)}{\gamma_1^2}\right)$$
  • Multi-Index Model: If the target network's output only depends on a low-dimensional projection of $k \ll d$ unknown orthonormal directions, the mistake bound drops to: $$\tilde{O}\left(\frac{\mathtt{TS}(k, \gamma_1)}{\gamma_1^2}\right) \leq \left(\frac{1.5}{\gamma_1}\right)^{O(k)}$$ This completely eliminates the dependence on the ambient dimension $d$.

  • Extended Margin Model: If all neurons across all $L$ layers maintain a margin $\gamma$, the mistake bound becomes entirely independent of both the dimension $d$ and the network's width: $$\tilde{O}\left(\frac{\log |Y|}{\gamma^{4L+2}}\right)$$

  • Agnostic Learning: Using an agnostic-to-realizable reduction, the authors extend their guarantees to noisy settings, achieving a standard regret bound of $\tilde{O}(\sqrt{MT})$, where $M$ is the realizable mistake bound.

Limitations and Future Work

  • Computational Complexity: The meta-learner requires maintaining and querying more than $g^g$ experts (where $g \geq 1/\gamma$). If the margin $\gamma$ is small, this algorithm is computationally inefficient. Developing a polynomial-time algorithm with similar mistake bounds remains a major open challenge.
  • Exponential Dependence on Depth: In the extended margin setting, the mistake bound scales exponentially with the network's depth $L$ ($\gamma^{-O(L)}$). The authors note it is currently unknown whether this exponential dependence on depth is an inherent trait or an artifact of their proof technique.
  • The Adaptation Penalty: While the adaptive algorithm successfully eliminates the need to know $\gamma$ and $b$ beforehand, it suffers a polynomial degradation, scaling the mistake bound to $O(M^4)$. Future work is needed to see if this can be optimized down to a constant or logarithmic overhead.

Summary updated

Abstract

We study online learning of feedforward neural networks with the sign activation function that implement functions from the unit ball in $\mathbb{R}^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 $\mathtt{TS}(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 $\mathtt{TS}(d,γ)$ many mistakes. We also give a quantitative lower bound of approximately $\mathtt{TS}(d,γ) \geq \max\{1/(γ\sqrt{d})^d, d\}$ when $γ\geq 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.
BibTeX
@inproceedings{daniely2025online,
  author = {Amit Daniely and Idan Mehalel and Elchanan Mossel},
  title = {{Online Learning of Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=oedSIxYWql},
}
Figure