Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis

• URL: http://arxiv.org/abs/2605.15551v1
• Date: Fri, 15 May 2026 02:44:25 GMT
• Title: Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis
• Abstract summary: We introduce the Quantized Block Decomposition method (QuBD), which extends algorithmic complexity estimation to any $k$-ary object.<n>We show theoretically that QuBD yields a strictly tighter estimation gap with respect to true Kolmogorov-Chaitin-Solomonoff (KCS) complexity than binarization-based methods.
• Score: 9.735454755526954
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Training large-scale deep neural networks (DNNs) is resource-intensive, making model compression a practical necessity. The widely accepted ''learning as compression'' hypothesis posits that training induces structure in network weights, which enables compression. Measuring this structure through Kolmogorov-Chaitin-Solomonoff (KCS) complexity is appealing, but existing estimators based on the Coding Theorem Method (CTM) and the Block Decomposition Method (BDM) are limited to small binary objects and do not scale to modern DNNs. We introduce the Quantized Block Decomposition method (QuBD), which extends algorithmic complexity estimation to any $k$-ary object. QuBD first quantizes the network weights to a finite alphabet, then estimates the KCS complexity by aggregating per bit-plane CTM estimates. We show theoretically that QuBD yields a strictly tighter estimation gap with respect to true KCS complexity than binarization-based methods. Using QuBD, we study how the algorithmic complexity of neural network weights evolves during training, showing that it decreases as models learn, scales with data budget, increases during overfitting, follows the delayed generalization observed during grokking, and correlates with generalization performance. We further show that algorithmic information resides predominantly in the most significant bit-planes, which can serve as a practical diagnostic for determining appropriate post-training quantization levels. This work offers novel insights into learning mechanisms in DNNs by providing the first scalable, tractable estimates of KCS complexity for large, non-binary objects such as DNN weights.

Related papers

• Performance Analysis of Convolutional Neural Network By Applying Unconstrained Binary Quadratic Programming [0.0]
  Convolutional Neural Networks (CNNs) are pivotal in computer vision and Big Data analytics but demand significant computational resources when trained on large-scale datasets.<n>We propose a hybrid optimization method that combines Unconstrained Binary Quadratic Programming (UBQP) with Gradient Descent (SGD) to accelerate CNN training.<n>Our approach achieves a 10--15% accuracy improvement over a standard BP-CNN baseline while maintaining similar execution times.
  arXiv  Detail & Related papers  (2025-05-30T21:25:31Z)
• Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis [33.73453802399709]
  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)
• Physics-Inspired Binary Neural Networks: Interpretable Compression with Theoretical Guarantees [20.854288216118423]
  Many inverse problems admit algorithm-unrolled networks that naturally encode physics and sparsity.<n>We propose a Physics-Inspired Binary Neural Network (PIBiNN) that combines data-driven one-bit quantization with a single global scale.<n>This design yields compression rates below one bit per weight by exploiting structural zeros.
  arXiv  Detail & Related papers  (2025-02-04T00:53:10Z)
• Neural Network with Local Converging Input (NNLCI) for Supersonic Flow Problems with Unstructured Grids [0.9152133607343995]
  We develop a neural network with local converging input (NNLCI) for high-fidelity prediction using unstructured data. As a validation case, the NNLCI method is applied to study inviscid supersonic flows in channels with bumps.
  arXiv  Detail & Related papers  (2023-10-23T19:03:37Z)
• Information Bottleneck Analysis of Deep Neural Networks via Lossy Compression [37.69303106863453]
  The Information Bottleneck (IB) principle offers an information-theoretic framework for analyzing the training process of deep neural networks (DNNs) In this paper, we introduce a framework for conducting IB analysis of general NNs. We also perform IB analysis on a close-to-real-scale, which reveals new features of the MI dynamics.
  arXiv  Detail & Related papers  (2023-05-13T21:44:32Z)
• 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)
• Gradient Descent in Neural Networks as Sequential Learning in RKBS [63.011641517977644]
  We construct an exact power-series representation of the neural network in a finite neighborhood of the initial weights. We prove that, regardless of width, the training sequence produced by gradient descent can be exactly replicated by regularized sequential learning.
  arXiv  Detail & Related papers  (2023-02-01T03:18:07Z)
• A Comprehensive Survey on Model Quantization for Deep Neural Networks in Image Classification [0.0]
  A promising approach is quantization, in which the full-precision values are stored in low bit-width precision. We present a comprehensive survey of quantization concepts and methods, with a focus on image classification. We explain the replacement of floating-point operations with low-cost bitwise operations in a quantized DNN and the sensitivity of different layers in quantization.
  arXiv  Detail & Related papers  (2022-05-14T15:08:32Z)
• Compact representations of convolutional neural networks via weight pruning and quantization [63.417651529192014]
  We propose a novel storage format for convolutional neural networks (CNNs) based on source coding and leveraging both weight pruning and quantization. We achieve a reduction of space occupancy up to 0.6% on fully connected layers and 5.44% on the whole network, while performing at least as competitive as the baseline.
  arXiv  Detail & Related papers  (2021-08-28T20:39:54Z)
• 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)
• Neural Complexity Measures [96.06344259626127]
  We propose Neural Complexity (NC), a meta-learning framework for predicting generalization. Our model learns a scalar complexity measure through interactions with many heterogeneous tasks in a data-driven way.
  arXiv  Detail & Related papers  (2020-08-07T02:12:10Z)
• A Quantum Graph Neural Network Approach to Particle Track Reconstruction [1.087475836765689]
  We present an improved model with an iterative approach to overcome the low accuracy of the initial oversimplified Tree Network (TTN) model. We aim to leverage the capability of quantum computing to evaluate a very large number of states simultaneously and thus to effectively search a large parameter space.
  arXiv  Detail & Related papers  (2020-07-14T07:25:24Z)
• 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.