The Complexity Dynamics of Grokking

• URL: http://arxiv.org/abs/2412.09810v1
• Date: Fri, 13 Dec 2024 02:57:59 GMT
• Title: The Complexity Dynamics of Grokking
• Abstract summary: We introduce a new measure of intrinsic complexity for neural networks based on the theory of Kolmogorov complexity.<n> Tracking this metric throughout network training, we find a consistent pattern in training dynamics, consisting of a rise and fall in complexity.<n>Based on insights from rate--distortion theory and the minimum description length principle, we lay out a principled approach to lossy compression of neural networks.
• Score: 21.075837465689887
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the phenomenon of generalization through the lens of compression. In particular, we study the complexity dynamics of neural networks to explain grokking, where networks suddenly transition from memorizing to generalizing solutions long after over-fitting the training data. To this end we introduce a new measure of intrinsic complexity for neural networks based on the theory of Kolmogorov complexity. Tracking this metric throughout network training, we find a consistent pattern in training dynamics, consisting of a rise and fall in complexity. We demonstrate that this corresponds to memorization followed by generalization. Based on insights from rate--distortion theory and the minimum description length principle, we lay out a principled approach to lossy compression of neural networks, and connect our complexity measure to explicit generalization bounds. Based on a careful analysis of information capacity in neural networks, we propose a new regularization method which encourages networks towards low-rank representations by penalizing their spectral entropy, and find that our regularizer outperforms baselines in total compression of the dataset.

Related papers

• A Compression Perspective on Simplicity Bias [20.205677906026924]
  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.
  arXiv  Detail & Related papers  (2026-03-26T19:02:49Z)
• The Inductive Bias of Convolutional Neural Networks: Locality and Weight Sharing Reshape Implicit Regularization [57.37943479039033]
  We study how architectural inductive bias reshapes the implicit regularization induced by the edge-of-stability phenomenon in gradient descent.<n>We show that locality and weight sharing fundamentally change this picture.
  arXiv  Detail & Related papers  (2026-03-05T04:50:51Z)
• Adversarial generalization of unfolding (model-based) networks [0.0]
  We study the adversarial generalization of unfolding networks when perturbed with $l$-norm constrained attacks.<n>This is the first theoretical analysis on the adversarial generalization of unfolding networks.<n>We present a series of experiments on real-world data, with results corroborating our derived theory.
  arXiv  Detail & Related papers  (2025-09-18T19:17:07Z)
• Network Sparsity Unlocks the Scaling Potential of Deep Reinforcement Learning [57.3885832382455]
  We show that introducing static network sparsity alone can unlock further scaling potential beyond dense counterparts with state-of-the-art architectures.<n>Our analysis reveals that, in contrast to naively scaling up dense DRL networks, such sparse networks achieve both higher parameter efficiency for network expressivity.
  arXiv  Detail & Related papers  (2025-06-20T17:54:24Z)
• Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis [36.24954635616374]
  We propose a shift toward algorithmic information theory, using Binarized Neural Networks (BNNs) as a first proxy.<n>We apply the Block Decomposition Method (BDM) and demonstrate it more closely tracks structural changes during training than entropy.<n>These results support the view of training as a process of algorithmic compression, where learning corresponds to the progressive internalization of structured regularities.
  arXiv  Detail & Related papers  (2025-05-27T02:51:36Z)
• A Two-Phase Perspective on Deep Learning Dynamics [0.0]
  We propose that learning in deep neural networks proceeds in two phases: a rapid curve fitting phase followed by a slower compression or coarse graining phase.<n>We empirically show that the associated timescales align in two rather different settings.<n>We argue that the second phase is not actively optimized by standard training algorithms and may be unnecessarily prolonged.
  arXiv  Detail & Related papers  (2025-04-17T06:57:37Z)
• Generalization emerges from local optimization in a self-organized learning network [0.0]
  We design and analyze a new paradigm for building supervised learning networks, driven only by local optimization rules without relying on a global error function. Our network stores new knowledge in the nodes accurately and instantaneously, in the form of a lookup table. We show on numerous examples of classification tasks that the networks generated by our algorithm systematically reach such a state of perfect generalization when the number of learned examples becomes sufficiently large. We report on the dynamics of the change of state and show that it is abrupt and has the distinctive characteristics of a first order phase transition, a phenomenon already observed for traditional learning networks and known as grokking.
  arXiv  Detail & Related papers  (2024-10-03T15:32:08Z)
• 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 with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK [86.45209429863858]
  We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime. We show that the neural networks possess a different limiting kernel which we call textitbias-generalized NTK We also study various properties of the neural networks with this new kernel.
  arXiv  Detail & Related papers  (2023-01-01T02:11:39Z)
• 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)
• Correlation between entropy and generalizability in a neural network [9.223853439465582]
  We use Wang-Landau Mote Carlo algorithm to calculate the entropy at a given test accuracy. Our results show that entropical forces help generalizability.
  arXiv  Detail & Related papers  (2022-07-05T12:28:13Z)
• How You Start Matters for Generalization [26.74340246715699]
  We show that the generalization of neural networks is heavily tied to their initializes. We make a case against the controversial flat-minima conjecture.
  arXiv  Detail & Related papers  (2022-06-17T05:30:56Z)
• Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks [13.518582483147325]
  We provide a rigorous analysis of the performance of neural networks in the context of transductive inference. We show that transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for block models.
  arXiv  Detail & Related papers  (2021-12-07T20:06:23Z)
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks [77.34726150561087]
  We show that a class of functions can be approximated by a complex-reaction network using the number of parameters. For empirical risk minimization, our theoretical result shows that the critical point set of complex-reaction networks is a proper subset of that of real-valued networks.
  arXiv  Detail & Related papers  (2021-08-15T10:13:49Z)
• A neural anisotropic view of underspecification in deep learning [60.119023683371736]
  We show that the way neural networks handle the underspecification of problems is highly dependent on the data representation. Our results highlight that understanding the architectural inductive bias in deep learning is fundamental to address the fairness, robustness, and generalization of these systems.
  arXiv  Detail & Related papers  (2021-04-29T14:31:09Z)
• Formalizing Generalization and Robustness of Neural Networks to Weight Perturbations [58.731070632586594]
  We provide the first formal analysis for feed-forward neural networks with non-negative monotone activation functions against weight perturbations. We also design a new theory-driven loss function for training generalizable and robust neural networks against weight perturbations.
  arXiv  Detail & Related papers  (2021-03-03T06:17:03Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Compressive Sensing and Neural Networks from a Statistical Learning Perspective [4.561032960211816]
  We present a generalization error analysis for a class of neural networks suitable for sparse reconstruction from few linear measurements. Under realistic conditions, the generalization error scales only logarithmically in the number of layers, and at most linear in number of measurements.
  arXiv  Detail & Related papers  (2020-10-29T15:05:43Z)
• Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics [50.83356836818667]
  We introduce a new theoretical framework to analyze deep learning optimization with connection to its generalization error. Existing frameworks such as mean field theory and neural tangent kernel theory for neural network optimization analysis typically require taking limit of infinite width of the network to show its global convergence.
  arXiv  Detail & Related papers  (2020-07-11T18:19:50Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

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.