Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs

• URL: http://arxiv.org/abs/2602.14896v1
• Date: Mon, 16 Feb 2026 16:30:38 GMT
• Title: Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs
• Abstract summary: Methods like pruning, quantization, and knowledge distillation have been used to achieve massive reductions in the number of model parameters.<n>We take up the perspective of algorithmic complexity to explain this behavior.
• Score: 10.533982886956002
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large-scale deep learning models are well-suited for compression. Methods like pruning, quantization, and knowledge distillation have been used to achieve massive reductions in the number of model parameters, with marginal performance drops across a variety of architectures and tasks. This raises the central question: \emph{Why are deep neural networks suited for compression?} In this work, we take up the perspective of algorithmic complexity to explain this behavior. We hypothesize that the parameters of trained models have more structure and, hence, exhibit lower algorithmic complexity compared to the weights at (random) initialization. Furthermore, that model compression methods harness this reduced algorithmic complexity to compress models. Although an unconstrained parameterization of model weights, $\mathbf{w} \in \mathbb{R}^n$, can represent arbitrary weight assignments, the solutions found during training exhibit repeatability and structure, making them algorithmically simpler than a generic program. To this end, we formalize the Kolmogorov complexity of $\mathbf{w}$ by $\mathcal{K}(\mathbf{w})$. We introduce a constrained parameterization $\widehat{\mathbf{w}}$, that partitions parameters into blocks of size $s$, and restricts each block to be selected from a set of $k$ reusable motifs, specified by a reuse pattern (or mosaic). The resulting method, $\textit{Mosaic-of-Motifs}$ (MoMos), yields algorithmically simpler model parameterization compared to unconstrained models. Empirical evidence from multiple experiments shows that the algorithmic complexity of neural networks, measured using approximations to Kolmogorov complexity, can be reduced during training. This results in models that perform comparably with unconstrained models while being algorithmically simpler.

Related papers

• Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model [53.6316818897326]
  We propose a gradient-based algorithm for training a two-layer neural network in time.<n>We show that our algorithm learns a sparse representation that strongly aligns with the unknown signal $star$.<n>We extend our approach to the setting where $star$ is $k$-sparse for $k = o(sqrtd)$ by introducing a novel weight technique.
  arXiv  Detail & Related papers  (2026-06-13T09:34:39Z)
• A Rigorous, Tractable Measure of Model Complexity [12.424687747519037]
  We present a mathematically rigorous yet easy-to-parametric measure of model complexity that is based on the similarities between the model across inputs.<n>We prove that our measure of complexity generalizes model-specific complexity measures such as kernel length scale, number of neighbors, and number of trees.<n>We also use our measure to obtain new insights into the double descent phenomenon for random features, random forests, neural networks, and gradient boosting.
  arXiv  Detail & Related papers  (2026-05-20T13:37:38Z)
• Implicit Models: Expressive Power Scales with Test-Time Compute [17.808479563949074]
  Implicit models, an emerging model class, compute outputs by iterating a single parameter block to a fixed point.<n>We study this gap through a nonparametric analysis of expressive power.<n>We prove that for a broad class of implicit models, this process lets the model's expressive power scale with test-time compute.
  arXiv  Detail & Related papers  (2025-10-04T02:49:22Z)
• Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees [9.141919626212903]
  Graph-based semi-supervised learning is a powerful paradigm in machine learning for modeling and exploiting the underlying graph structure.<n>We propose a tunable architecture that interpolates graph convolutional neural networks (GCN) and graph attention networks (GAT) in every layer.
  arXiv  Detail & Related papers  (2025-02-18T15:16:23Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Neural Implicit Manifold Learning for Topology-Aware Density Estimation [15.878635603835063]
  Current generative models learn $mathcalM$ by mapping an $m$-dimensional latent variable through a neural network. We show that our model can learn manifold-supported distributions with complex topologies more accurately than pushforward models.
  arXiv  Detail & Related papers  (2022-06-22T18:00:00Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• $\mu$NCA: Texture Generation with Ultra-Compact Neural Cellular Automata [79.00163348781422]
  We study the problem of example-based procedural texture synthesis using highly compact models. We use differentiable programming to train a generative process, parameterised by a recurrent Neural Cellular Automata (NCA) rule.
  arXiv  Detail & Related papers  (2021-11-26T15:26:37Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.