Research map / Bandits and online learning / Online convex optimization and games
Online Learning of Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes online mistake bounds for sign-activation neural networks via a margin condition and the totally-separable-packing number, and gives improved bounds under a multi-index model and an everywhere-margin assumption.
Problem
Online learning of feedforward sign-activation neural networks mapping the unit ball to a finite label set in the realizable setting; the mistake bound seemingly depends on input dimension d, and the paper asks when dimension-free bounds are possible.
Approach
Characterizes the optimal mistake bound by the (d,gamma)-totally-separable-packing number of the first-layer margin, builds a meta-learner that runs multiclass weighted majority over experts that each pick a small set of first-layer neurons (via perceptron-simulating neurons) and label the induced regions, and removes dimension dependence under a multi-index assumption or a margin-everywhere assum
Key results
- Upper bound of order TS(d,gamma_1)/gamma_1^2 (up to logs) on mistakes for any sign network, with a matching lower bound Omega(TS(d,eps)+1/eps^2) for some nets and sequences.
- Under the multi-index model with k relevant directions, mistake bound roughly (1.5/gamma)^(k+2), i.e. dimension-free in d.
- Under an everywhere-margin assumption, mistake bound O~(log|Y| / gamma^(4L+2)), exponential in depth L but independent of d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the target to depend on k unknown orthonormal directions rather than the full d-dimensional input | Online neural-network learning · Multi-index model, realizable online learning | mistake bound: \tilde{O} \mleft( \frac{\mathtt{TS}(k,\gamma_1)}{\gamma_1^2} \mright) | Helped |
| Assume all neurons in all layers classify every ingoing input with margin γ | Online neural-network learning · Extended margin assumption, realizable online learning | mistake bound: \tilde{O} \mleft(\frac{\log |\mathcal{Y}|}{\gamma^{4L+2}} \mright) | Helped |
| Allow an adversary to alter labels and apply the agnostic-to-realizable reduction | Online neural-network learning with realizable mistake bound M · Agnostic online learning | regret: \tilde{O} \mleft( \sqrt{M T} \mright) | Helped |
Surprising findings
- Dimension-free mistake bounds are almost always impossible: TS(d,gamma) >= max{1/(gamma sqrt d)^d, d} for gamma >= 1/2, so some nets force exp(d) mistakes.
Limitations
- Upper and lower bounds differ by roughly a quadratic factor in 1/gamma in the worst case.
- Dependence on depth L is exponential in the everywhere-margin bound and it is open whether this is necessary.
- Results are for sign activations and deterministic learners in the realizable setting; extension to other activations is argued informally.
Experimental setup
Metrics: mistake bound
Baselines: Lipschitz-activation online regret bound (joined Theorem 8 and Proposition 15 of
Builds on: Perceptron algorithm Weighted Majority algorithm uniform convergence (VC theory) agnostic-to-realizable reduction
Closest papers by meaning
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.87)
- Optimal Mistake Bounds for Transductive Online Learning (NeurIPS 2025 · similarity 0.87)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.85)
- Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.84)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.84)
- Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.