Learning from almost nothing: How neural networks survive heavy input corruption

Technical Summary: Learning from Almost Nothing

Problem Statement
The paper addresses the problem of learning from imperfect data, specifically focusing on attribute noise (corruption of input features) while keeping labels intact. While label noise has received significant analytical attention, attribute noise—common in real-world scenarios due to sensor errors or missing features—has been less explored theoretically. The central question is whether neural networks can learn a coherent classification rule and generalize to clean test data when trained on inputs that are severely corrupted, to the point where the signal is nearly indistinguishable from random noise to human observers.

Methodology
The authors employ a dual approach combining empirical experimentation with analytical derivation using the Neural Tangent Kernel (NTK) framework.

1. Empirical Setup:

   • Models: Multi-layer perceptrons (MLPs) with 3 hidden layers and varying widths (128 to 2048).
   • Datasets: MNIST, Fashion-MNIST, and KMNIST.
   • Corruption Models: Two types of input corruption are tested:
     • Replacement Noise: Each pixel is independently replaced with uniform noise with probability $p$.
     • Additive Noise: Each pixel is a convex combination of the clean pixel and independent noise.
   • Training: Networks are trained on corrupted inputs with clean labels using cross-entropy or mean-squared error (MSE) loss.
   • Evaluation: Performance is measured on clean test sets and, in some cases, on simultaneously corrupted test sets.

2. Analytical Framework:

   • The authors analyze the infinite-width limit of MLPs using the NTK description, where training with MSE loss is equivalent to kernel regression.
   • They perform a mean-field-inspired expansion in the "heavy-corruption regime" (where the signal strength $\epsilon = 1-p$ is small and the feature dimension $d$ is large).
   • The derivation involves expanding the NTK and the resulting predictor around the pure-noise fixed point ($\epsilon = 0$), treating the surviving signal as a linear perturbation.
   • A symmetry argument based on permutation invariance at the pure-noise limit is used to explain the universality of the resulting decision rule.

Key Contributions and Results

1. Empirical Robustness:

   • Experiments demonstrate that MLPs remain remarkably robust to attribute noise. Even when training inputs are >90% corrupted (e.g., $p=0.9$), networks achieve test accuracy far above random chance (e.g., ~70–80% on MNIST), despite the training images being nearly unrecognizable to humans.
   • The standard deviation of test accuracy exhibits a non-monotonic behavior with respect to corruption probability, peaking at intermediate noise levels rather than at maximum noise.
   • When both training and testing data are corrupted, optimal performance occurs when the corruption level of the training set matches that of the test set ($p_{train} \approx p_{test}$), suggesting the model learns to generalize within the specific corrupted distribution.

2. The Centroid Decision Rule:

   • The primary theoretical finding is that in the high-noise limit, the complex non-linear network collapses to a simple, universal nearest-class-mean (centroid) classifier.
   • The leading-order decision rule for a test point $x_*$ is to assign it to the class $i$ that maximizes the overlap with the centered empirical mean (centroid) of the clean training data:
     $$i^* = \arg\max_i \frac{1}{d} \sum_{k=1}^d x_{k*} (\bar{x}^i_k - \bar{x}_k)$$
     where $\bar{x}^i_k$ is the mean of class $i$ and $\bar{x}_k$ is the global mean.
   • This rule is universal: it holds regardless of network depth, activation function, or the specific distribution of the noise (provided it is i.i.d.), depending only on the first two moments of the noise distribution.

3. Analytical Validation:

   • The derived analytical form (Eq. 13/16) matches the behavior of finite-width networks (width 2048) with high precision ($R^2 > 0.96$) in the high-noise regime ($p \approx 0.97$).
   • The model accurately predicts both the mean logit outputs and the fluctuations that determine classification accuracy.
   • A derived Signal-to-Noise Ratio (SNR) scaling law suggests that accuracy improves with the surviving signal fraction $(1-p)$, feature dimension $d$, and the number of training examples per class $N/C$.

Significance and Claims
The paper claims that the surprising robustness of neural networks to heavy input corruption is not due to a complex denoising or feature-recovery mechanism. Instead, it arises because the network effectively aggregates the weak, surviving class information into a prototype-based decision rule.

• Simplicity from Complexity: Despite the architectural complexity and nonlinearity of deep networks, the learned rule in the high-noise limit becomes simple, interpretable, and linear (template matching against class centroids).
• Universality via Symmetry: The authors attribute the universality of this rule to the permutation symmetry of the pure-noise kernel. At the pure-noise limit, training examples are exchangeable; the leading-order response to a small signal breaking this symmetry is forced to depend on centered class averages.
• Analytical Tractability: The work identifies a rare regime where neural network learning can be described in unusually explicit terms, providing a tractable fixed point (pure noise) from which to derive the leading-order corrections to the predictor.

The authors maintain modesty regarding the scope, noting that while the decision rule is universal, the accuracy depends on the geometry of the specific dataset (i.e., whether the clean class centroids contain sufficient discriminative information). They do not claim this applies to all datasets or arbitrary corruption levels, but rather establishes a generic leading-order behavior for MLPs in the high-attribute-noise regime.