Is Complexity an Illusion?

• URL: http://arxiv.org/abs/2404.07227v4
• Date: Thu, 30 May 2024 13:38:42 GMT
• Title: Is Complexity an Illusion?
• Abstract summary: We show that all constraints can take equally simple forms, regardless of weakness. If function is represented using a finite subset of forms, then we can force a correlation between simplicity and generalisation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Simplicity is held by many to be the key to general intelligence. Simpler models tend to "generalise", identifying the cause or generator of data with greater sample efficiency. The implications of the correlation between simplicity and generalisation extend far beyond computer science, addressing questions of physics and even biology. Yet simplicity is a property of form, while generalisation is of function. In interactive settings, any correlation between the two depends on interpretation. In theory there could be no correlation and yet in practice, there is. Previous theoretical work showed generalisation to be a consequence of "weak" constraints implied by function, not form. Experiments demonstrated choosing weak constraints over simple forms yielded a 110-500% improvement in generalisation rate. Here we show that all constraints can take equally simple forms, regardless of weakness. However if forms are spatially extended, then function is represented using a finite subset of forms. If function is represented using a finite subset of forms, then we can force a correlation between simplicity and generalisation by making weak constraints take simple forms. If function is determined by a goal directed process that favours versatility (e.g. natural selection), then efficiency demands weak constraints take simple forms. Complexity has no causal influence on generalisation, but appears to due to confounding.

Related papers

• Benign interpolation and Occam's razor [0.688204255655161]
  We show that modern deep learning methods generalize well even when they fit their training data perfectly.<n>We argue that this new appeal to simplicity creates an explanatory gap.<n>Lacking a provable connection to generalization, it is the name "simplicity" that does the work used to do, making a substantive and unargued assumption look like the application of a familiar methodological principle.
  arXiv  Detail & Related papers  (2026-08-04T09:34:47Z)
• Data Augmentation: A Fourier Analysis Perspective [52.00584777952869]
  We show that partial data augmentation can achieve the same statistical benefits as full augmentation in terms of generalization and sample complexity.<n>Our results provide a theoretical explanation for why partial augmentation can retain the statistical benefits of full augmentation despite enforcing symmetry only approximately.
  arXiv  Detail & Related papers  (2026-06-23T10:54:14Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• The Existential Theory of Research: Why Discovery Is Hard [11.62669179647184]
  We show that no method can guarantee universally simple explanations, arbitrarily compressed observations, and efficient exact inference.<n> representation mismatch alone can inflate intrinsic simplicity into apparent complexity.<n>The results suggest that scientific difficulty is not accidental, but a structural consequence of the geometry and complexity of inference.
  arXiv  Detail & Related papers  (2026-04-15T10:49:28Z)
• The Universality Lens: Why Even Highly Over-Parametrized Models Learn Well [4.2466572124752995]
  We study a Bayesian mixture with log-loss and (almost) uniform prior over an expansive hypothesis class.<n>Key result shows that the learner's regret is not determined by the overall size of the hypothesis class.<n>Results apply broadly across online, batch, and supervised learning settings.
  arXiv  Detail & Related papers  (2025-06-09T11:32:31Z)
• Ineq-Comp: Benchmarking Human-Intuitive Compositional Reasoning in Automated Theorem Proving on Inequalities [46.111273938884295]
  We study provers' ability to recognize that the given problem simplifies by applying a known inequality such as AM/GM.<n>Although these problems remain easy for humans, we find that most provers -- including Goedel, rewriting, and Kimina-7B -- struggle significantly.<n>Our results expose a persisting gap between the behavior of current AI provers and human intuition.
  arXiv  Detail & Related papers  (2025-05-19T03:56:05Z)
• Lean Formalization of Generalization Error Bound by Rademacher Complexity [5.114451899552168]
  We formalize the generalization error bound using the Rademacher complexity for the Lean 4 theorem prover based on the probability theory in the Mathlib 4 library.<n>We also present the formalization of generalization error bound for $L2$-regularization models.
  arXiv  Detail & Related papers  (2025-03-25T12:40:43Z)
• A Complexity-Based Theory of Compositionality [53.025566128892066]
  In AI, compositional representations can enable a powerful form of out-of-distribution generalization.<n>Here, we propose a definition, which we call representational compositionality, that accounts for and extends our intuitions about compositionality.<n>We show how it unifies disparate intuitions from across the literature in both AI and cognitive science.
  arXiv  Detail & Related papers  (2024-10-18T18:37:27Z)
• Understanding Simplicity Bias towards Compositional Mappings via Learning Dynamics [20.720113883193765]
  We study the uniqueness of compositional mappings through different perspectives. This property explains why models having such mappings can generalize well. We show that the simplicity bias is usually an intrinsic property of neural network training via gradient descent.
  arXiv  Detail & Related papers  (2024-09-15T06:37:12Z)
• Skews in the Phenomenon Space Hinder Generalization in Text-to-Image Generation [59.138470433237615]
  We introduce statistical metrics that quantify both the linguistic and visual skew of a dataset for relational learning. We show that systematically controlled metrics are strongly predictive of generalization performance. This work informs an important direction towards quality-enhancing the data diversity or balance to scaling up the absolute size.
  arXiv  Detail & Related papers  (2024-03-25T03:18:39Z)
• Discovering modular solutions that generalize compositionally [55.46688816816882]
  We show that identification up to linear transformation purely from demonstrations is possible without having to learn an exponential number of module combinations. We further demonstrate empirically that meta-learning from finite data can discover modular policies that generalize compositionally in a number of complex environments.
  arXiv  Detail & Related papers  (2023-12-22T16:33:50Z)
• On the Complexity of Bayesian Generalization [141.21610899086392]
  We consider concept generalization at a large scale in the diverse and natural visual spectrum. We study two modes when the problem space scales up, and the $complexity$ of concepts becomes diverse.
  arXiv  Detail & Related papers  (2022-11-20T17:21:37Z)
• Unifying local and global model explanations by functional decomposition of low dimensional structures [0.0]
  We consider a global explanation of a regression or classification function by decomposing it into the sum of main components and interaction components. Here, q denotes the highest order of interaction present in the decomposition.
  arXiv  Detail & Related papers  (2022-08-12T07:38:53Z)
• Evading the Simplicity Bias: Training a Diverse Set of Models Discovers Solutions with Superior OOD Generalization [93.8373619657239]
  Neural networks trained with SGD were recently shown to rely preferentially on linearly-predictive features. This simplicity bias can explain their lack of robustness out of distribution (OOD) We demonstrate that the simplicity bias can be mitigated and OOD generalization improved.
  arXiv  Detail & Related papers  (2021-05-12T12:12:24Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• Coupling-based Invertible Neural Networks Are Universal Diffeomorphism Approximators [72.62940905965267]
  Invertible neural networks based on coupling flows (CF-INNs) have various machine learning applications such as image synthesis and representation learning. Are CF-INNs universal approximators for invertible functions? We prove a general theorem to show the equivalence of the universality for certain diffeomorphism classes.
  arXiv  Detail & Related papers  (2020-06-20T02:07:37Z)
• Random thoughts about Complexity, Data and Models [0.0]
  Data Science and Machine learning have been growing strong for the past decade. We investigate the subtle relation between "data and models" Key issue for appraisal of relation between algorithmic complexity and algorithmic learning is to do with concepts of compressibility, determinism and predictability.
  arXiv  Detail & Related papers  (2020-04-16T14:27:22Z)

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.