Neuron Block Dynamics for XOR Classification with Zero-Margin

Guillaume Braun, Masaaki Imaizumi

TL;DR

This paper tackles a fundamental challenge in deep learning theory: understanding how neural networks learn in "zero-margin" classification scenarios, where data points are not clearly separated. The authors introduce a novel "neuron block dynamics" framework to show that even without clear margins, networks can learn by organizing neurons into coherent groups, leading to robust generalization.

What Problem Does This Paper Address?

Deep learning theory has made significant strides in explaining how neural networks learn, particularly in regression tasks or classification problems with a clear "margin" (i.e., data points are well-separated). However, real-world data often lacks such clear separation, leading to "zero-margin" classification problems. In these scenarios, many data points lie very close to the decision boundary, making traditional theoretical analyses based on worst-case scenarios and margins insufficient. This paper aims to bridge this gap by analyzing a simplified, yet challenging, zero-margin classification problem: the Gaussian XOR problem.

Methods

The core contribution is the development of a "neuron block dynamics" framework. Instead of tracking individual neurons, which can be noisy and chaotic in zero-margin settings, the authors propose analyzing the collective behavior of groups of neurons. They show that neurons naturally self-organize into four distinct "blocks" aligned with specific directions. The analysis then focuses on how these blocks evolve together, demonstrating a coherent, low-dimensional dynamic. This block-level perspective allows them to derive generalization guarantees without relying on traditional margin assumptions, instead using an "average-case" analysis that distinguishes reliable predictions from error-prone regions. The paper also introduces an "oracle approximation" to simplify the analysis of these block dynamics.

Datasets

The paper primarily uses a synthetic dataset: Gaussian XOR. Inputs are drawn from an isotropic Gaussian distribution, and labels are generated by the XOR function $f^*(x) = -\text{sgn}(x_1x_2)$. This setup is chosen for its simplicity in capturing the essential challenges of zero-margin nonlinear classification. The authors also mention experiments with MNIST digits 4 and 9 to illustrate the real-world relevance of overlapping classes and briefly discuss experiments with uniform inputs, Gaussian XOR inputs, non-isotropic Gaussian inputs, and nonlinear decision boundaries to test the robustness of their findings.

Key Insights and Ideas

  • Neurons form coherent blocks: In the zero-margin XOR problem, individual neurons don't learn in isolation. Instead, they rapidly self-organize into four distinct, balanced blocks. This emergent structure is key to learning.
  • Block dynamics are simpler than individual neuron dynamics: By analyzing the collective behavior of these blocks, the authors can derive more robust theoretical guarantees than by looking at individual neurons.
  • Generalization without margins: The paper demonstrates that neural networks can generalize effectively even when there's no clear margin, by focusing on average-case behavior and identifying regions of reliable prediction.
  • Two-phase learning: The training process exhibits a distinct two-phase dynamic: an initial phase of individual neuron growth followed by a phase of coordinated block growth.

Key Results

  • The paper provides a theoretical guarantee that a two-layer neural network trained with SGD can learn the Gaussian XOR function in the zero-margin setting.
  • The analysis shows that the expected loss on a fresh input can be bounded by $O(\log \log d / \sqrt{d})$, where $d$ is the input dimension.
  • The authors demonstrate that points sufficiently far from the decision boundary are classified correctly with high probability.
  • Numerical experiments confirm the predicted two-phase block dynamics and show robustness to variations in input distributions.

Limitations and Future Work

  • The theoretical analysis is primarily focused on the Gaussian XOR problem with isotropic inputs. Extending the block-dynamic framework to more complex decision boundaries and general input distributions is a natural next step.
  • The paper acknowledges that the convergence rate is slower than in the positive-margin Boolean XOR setting, which is attributed to the inherent difficulty of the zero-margin regime.
  • The authors suggest that the block-level analysis framework could be valuable for understanding neural network training in other challenging classification regimes.

Summary updated

Abstract

The ability of neural networks to learn useful features through stochastic gradient descent (SGD) is a cornerstone of their success. Most theoretical analyses focus on regression or on classification tasks with a positive margin, where worst-case gradient bounds suffice. In contrast, we study zero-margin nonlinear classification by analyzing the Gaussian XOR problem, where inputs are Gaussian and the XOR decision boundary determines labels. In this setting, a non-negligible fraction of data lies arbitrarily close to the boundary, breaking standard margin-based arguments. Building on Glasgow’s (2024) analysis, we extend the study of training dynamics from discrete to Gaussian inputs and develop a framework for the dynamics of neuron blocks. We show that neurons cluster into four directions and that block-level signals evolve coherently, a phenomenon essential in the Gaussian setting where individual neuron signals vary significantly. Leveraging this block perspective, we analyze generalization without relying on margin assumptions, adopting an average-case view that distinguishes regions of reliable prediction from regions of persistent error. Numerical experiments confirm the predicted two-phase block dynamics and demonstrate their robustness beyond the Gaussian setting.
BibTeX
@inproceedings{braun2026neuron,
  author = {Guillaume Braun and Masaaki Imaizumi},
  title = {{Neuron Block Dynamics for XOR Classification with Zero-Margin}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=vtMOjOW6Gp},
}
Figure