A Compression Perspective on Simplicity Bias

• URL: http://arxiv.org/abs/2603.25839v1
• Date: Thu, 26 Mar 2026 19:02:49 GMT
• Title: A Compression Perspective on Simplicity Bias
• Abstract summary: We show how simplicity bias governs feature selection in neural networks.<n>We identify distinct data regimes where increasing data promotes robustness by ruling out trivial shortcuts.<n>We validate our theory on a semi-synthetic benchmark showing that the feature selection of neural networks follows the same trajectory of solutions as optimal two-part compression.
• Score: 20.205677906026924
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep neural networks exhibit a simplicity bias, a well-documented tendency to favor simple functions over complex ones. In this work, we cast new light on this phenomenon through the lens of the Minimum Description Length principle, formalizing supervised learning as a problem of optimal two-part lossless compression. Our theory explains how simplicity bias governs feature selection in neural networks through a fundamental trade-off between model complexity (the cost of describing the hypothesis) and predictive power (the cost of describing the data). Our framework predicts that as the amount of available training data increases, learners transition through qualitatively different features -- from simple spurious shortcuts to complex features -- only when the reduction in data encoding cost justifies the increased model complexity. Consequently, we identify distinct data regimes where increasing data promotes robustness by ruling out trivial shortcuts, and conversely, regimes where limiting data can act as a form of complexity-based regularization, preventing the learning of unreliable complex environmental cues. We validate our theory on a semi-synthetic benchmark showing that the feature selection of neural networks follows the same trajectory of solutions as optimal two-part compressors.

Related papers

• Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensions [7.2136602534376015]
  We investigate the interplay between data structure in feature learning for the most popular ICA algorithm, FastICA, and gradient descent (SGD)<n>We show that vanilla online SGD outperforms FastICA, and prove that the optimal sample complexity $ngtrsim d2$ can be reached by smoothing the loss.
  arXiv  Detail & Related papers  (2025-03-31T09:46:47Z)
• Explainable Neural Networks with Guarantees: A Sparse Estimation Approach [11.142723510517778]
  This paper introduces a novel approach to constructing an explainable neural network that harmonizes predictiveness and explainability.<n>Our model, termed SparXnet, is designed as a linear combination of a sparse set of jointly learned features.<n>Our research paves the way for further research on sparse and explainable neural networks with guarantee.
  arXiv  Detail & Related papers  (2025-01-02T12:10:17Z)
• Hierarchical Simplicity Bias of Neural Networks [0.0]
  We introduce a novel method called imbalanced label coupling to explore and extend this simplicity bias across hierarchical levels. Our approach demonstrates that trained networks sequentially consider features of increasing complexity based on their correlation with labels in the training set.
  arXiv  Detail & Related papers  (2023-11-05T11:27:03Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  This paper provides the first theoretical characterization of joint edge-model sparse learning for graph neural networks (GNNs) It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy.
  arXiv  Detail & Related papers  (2023-02-06T16:54:20Z)
• Overcoming Simplicity Bias in Deep Networks using a Feature Sieve [5.33024001730262]
  We propose a direct, interventional method for addressing simplicity bias in deep networks. We aim to automatically identify and suppress easily-computable spurious features in lower layers of the network. We report substantial gains on many real-world debiasing benchmarks.
  arXiv  Detail & Related papers  (2023-01-30T21:11:13Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• Neural networks trained with SGD learn distributions of increasing complexity [78.30235086565388]
  We show that neural networks trained using gradient descent initially classify their inputs using lower-order input statistics. We then exploit higher-order statistics only later during training. We discuss the relation of DSB to other simplicity biases and consider its implications for the principle of universality in learning.
  arXiv  Detail & Related papers  (2022-11-21T15:27:22Z)
• Learning an Invertible Output Mapping Can Mitigate Simplicity Bias in Neural Networks [66.76034024335833]
  We investigate why diverse/ complex features are learned by the backbone, and their brittleness is due to the linear classification head relying primarily on the simplest features. We propose Feature Reconstruction Regularizer (FRR) to ensure that the learned features can be reconstructed back from the logits. We demonstrate up to 15% gains in OOD accuracy on the recently introduced semi-synthetic datasets with extreme distribution shifts.
  arXiv  Detail & Related papers  (2022-10-04T04:01:15Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• A Scaling Law for Synthetic-to-Real Transfer: A Measure of Pre-Training [52.93808218720784]
  Synthetic-to-real transfer learning is a framework in which we pre-train models with synthetically generated images and ground-truth annotations for real tasks. Although synthetic images overcome the data scarcity issue, it remains unclear how the fine-tuning performance scales with pre-trained models. We observe a simple and general scaling law that consistently describes learning curves in various tasks, models, and complexities of synthesized pre-training data.
  arXiv  Detail & Related papers  (2021-08-25T02:29:28Z)
• Parsimonious Inference [0.0]
  Parsimonious inference is an information-theoretic formulation of inference over arbitrary architectures. Our approaches combine efficient encodings with prudent sampling strategies to construct predictive ensembles without cross-validation.
  arXiv  Detail & Related papers  (2021-03-03T04:13:14Z)

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.