SGD Provably Prioritizes a Shortcut Spurious Feature in the XOR Model

• URL: http://arxiv.org/abs/2606.30444v2
• Date: Fri, 03 Jul 2026 00:43:45 GMT
• Title: SGD Provably Prioritizes a Shortcut Spurious Feature in the XOR Model
• Abstract summary: We provide the first theoretical characterization of spurious feature learning for two-layer ReLU neural networks trained by online minibatch SGD on the logistic loss.<n>We show that SGD learns the spurious feature first, and exponentially fast. Moreover, the optimization dynamics couple the spurious and signal features, with a stronger spurious component inhibiting signal feature learning.
• Score: 10.516362851373982
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural networks are known to be susceptible to over-reliance on spurious correlations. However, the precise mechanism by which models exploit shortcut features is not fully understood, and algorithms to mitigate this behavior rely on as yet unjustified assumptions about the learned representations. In this work, we provide the first end-to-end theoretical characterization of spurious feature learning for two-layer ReLU neural networks trained by online minibatch SGD on the logistic loss. We consider data drawn from the high-dimensional Boolean hypercube with a quadratic signal function (namely XOR) and a linear spurious correlation. We show that SGD learns the spurious feature first, and exponentially fast. Moreover, the optimization dynamics couple the spurious and signal features, with a stronger spurious component inhibiting signal feature learning. Our analysis reveals precise phase transitions in the learning dynamics. In the first phase, alignment between the signs of the spurious feature and second-layer weight drives rapid growth of the spurious feature. In the second phase, large majority group margin slows learning and the signal feature remains suppressed. When the spurious correlation is maximally strong, we show theoretically that the spurious feature dominates even at the sample complexity threshold where XOR would be learned in isolation (i.e., if the spurious feature was absent). In contrast, when the correlation strength is constant, we provide preliminary empirical evidence that the model can eventually learn the XOR signal, although the spurious feature is not forgotten.

Related papers

• Why Some Models Resist Unlearning: A Linear Stability Perspective [7.446140380340418]
  We frame unlearning through the lens of linear coherence stability.<n>We decompose coherence along three axes: within the retain set, within the forget set, and between them.<n>To further link data properties to forgettability, we study a two layer ReLU CNN under a signal plus noise model.<n>For empirical geometry, we show that Hessian tests and CNN heatmaps align closely with the predicted boundary, mapping the stability gradient based unlearning as a function of verification, mixing, and data/model alignment.
  arXiv  Detail & Related papers  (2026-02-03T01:47:26Z)
• Complexity Matters: Dynamics of Feature Learning in the Presence of Spurious Correlations [13.119576365743624]
  We study the dynamics of feature learning under spurious correlations. We demonstrate that our findings justify the success of retraining the last layer to remove spurious correlation. We also identify limitations of popular debiasing algorithms that exploit early learning of spurious features.
  arXiv  Detail & Related papers  (2024-03-05T23:54:00Z)
• Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression [53.15502562048627]
  Recent work has built the connection between self-supervised learning and the approximation of the top eigenspace of a graph Laplacian operator. This work delves into a statistical analysis of augmentation-based pretraining.
  arXiv  Detail & Related papers  (2023-06-01T15:18:55Z)
• Identifying Spurious Biases Early in Training through the Lens of Simplicity Bias [25.559684790787866]
  We show that examples with spurious features are provably separable based on the model's output early in training. We propose SPARE, which identifies spurious correlations early in training and utilizes importance sampling to alleviate their effect.
  arXiv  Detail & Related papers  (2023-05-30T05:51:36Z)
• How Spurious Features Are Memorized: Precise Analysis for Random and NTK Features [19.261178173399784]
  We consider spurious features that are uncorrelated with the learning task. We provide a precise characterization of how they are memorized via two separate terms. We prove that the memorization of spurious features weakens as the generalization capability increases.
  arXiv  Detail & Related papers  (2023-05-20T05:27:41Z)
• Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning [47.904127007515925]
  We study a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction. We prove that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic approximation guarantees as their counterparts. Notably, these are the first finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling.
  arXiv  Detail & Related papers  (2023-01-03T04:09:38Z)
• Multi-scale Feature Learning Dynamics: Insights for Double Descent [71.91871020059857]
  We study the phenomenon of "double descent" of the generalization error. We find that double descent can be attributed to distinct features being learned at different scales.
  arXiv  Detail & Related papers  (2021-12-06T18:17:08Z)
• Understanding Self-supervised Learning with Dual Deep Networks [74.92916579635336]
  We propose a novel framework to understand contrastive self-supervised learning (SSL) methods that employ dual pairs of deep ReLU networks. We prove that in each SGD update of SimCLR with various loss functions, the weights at each layer are updated by a emphcovariance operator. To further study what role the covariance operator plays and which features are learned in such a process, we model data generation and augmentation processes through a emphhierarchical latent tree model (HLTM)
  arXiv  Detail & Related papers  (2020-10-01T17:51:49Z)
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory [110.99247009159726]
  Temporal-difference and Q-learning play a key role in deep reinforcement learning, where they are empowered by expressive nonlinear function approximators such as neural networks. In particular, temporal-difference learning converges when the function approximator is linear in a feature representation, which is fixed throughout learning, and possibly diverges otherwise.
  arXiv  Detail & Related papers  (2020-06-08T17:25:22Z)
• Optimal Learning with Excitatory and Inhibitory synapses [91.3755431537592]
  I study the problem of storing associations between analog signals in the presence of correlations. I characterize the typical learning performance in terms of the power spectrum of random input and output processes.
  arXiv  Detail & Related papers  (2020-05-25T18:25:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.