PaperlayerView exact revision on arXiv

Source-linked AI summary

On The Statistical Limits of Self-Improving Agents

Charles L. Wang, Keir Dorchen, Peter Jin

arXiv:2510.04399v3cs.AIcs.LG

TL;DR

The paper asks when self-modifying agents can preserve distribution-free learning guarantees while selecting changes from finite evidence. It analyzes their reachable predictor families and proves that learnability is preserved exactly when capacity remains uniformly bounded. A validation-improvement gate paired with a capacity cap provides a guardrail, within the stated assumptions and scope.

  • Problem

    Self-modification selected on finite evidence raises the question of when utility-improving changes preserve the statistical conditions required for learning.

    Source: §1 · p. 1, §3 · p. 4

  • Method

    The paper analyzes self-modification through five axes and the policy-reachable family of predictors, then gives a Two-Gate rule combining validation improvement with a capacity cap.

    Source: §1 · p. 2

  • Results

    Distribution-free PAC learnability is preserved if and only if the policy-reachable envelope has uniformly bounded capacity, and Two-Gate enforces this boundary with a terminal-class oracle-style guarantee.

    Source: §1 · p. 2, §12 · p. 15

  • Takeaways & Limitations

    Safe self-improvement requires structural constraints on reachable families in addition to favorable objectives.

    Source: §12 · p. 15

    The analysis treats one modification axis at a time; multi-axis guarantees require a global capacity cap on the jointly induced reachable family.

    Source: §10 · p. 14

Abstract

from arXiv · show

We develop a learning-theoretic framework for analyzing self-improving agents by decomposing self-modification into five axes. Within this framework, we prove a sharp boundary: under standard i.i.d. assumptions, distribution-free PAC learnability is preserved if and only if the policy-reachable family remains uniformly capacity-bounded. If reachable capacity can grow without bound, utility-rational self-changes can make learnable tasks unlearnable. We further introduce a simple Two-Gate guardrail -- a validation-improvement requirement plus a capacity cap -- that preserves this boundary and yields standard VC-rate guarantees. The broader implication is that self-modification must be constrained not only by objectives, but also by structural conditions that preserve the statistical prerequisites for learning. As AI systems become increasingly intelligent and autonomous, this framework provides a foundation for the statistical theory of self-improvement.

1 Introduction

The paper asks when self-modification selected on finite evidence preserves learnability, and identifies the capacity of the policy-reachable family as the governing invariant. It frames this question across five modification axes and under standard PAC assumptions.

1 Introduction

  • Finite-evidence self-changes can select the learner itself, so the paper studies when they preserve the conditions for generalization and proves a boundary based on reachable-family capacity.The policy-reachable envelope is uniformly capacity-bounded if and only if distribution-free PAC learnability is preserved.Source: §1 · pp. 1–2

2.1 Decision-theoretic self-modification and safety

  • Decision-theoretic and safety work studies utility-improving modifications and their pathologies, while leaving post-modification generalization as an open learning-theoretic question.The paper directly studies when self-changes preserve learning conditions.Source: §2.1 · p. 3

2.2 Modern mechanisms for self-improvement

  • Modern self-improvement mechanisms traverse several modification axes; validation gains alone do not ensure safety when the policy can keep changing its candidate family.The reachable family must remain bounded relative to available data.Source: §2.2 · p. 3

2.3 Learning theory for adaptive systems

  • The framework makes explicit the structural object that adaptive-learning analyses typically hold fixed: the family reachable under self-modification.This reframes the generalization question for agents that can modify their own learning mechanisms.Source: §2.3 · p. 4

3 Setup and Five-Axis Decomposition

  • The setup treats the five axes as changes that expand effective hypothesis families or filter trajectories, with the union of reachable predictors determining distribution-free guarantees.The analysis assumes i.i.d. data and independent training and validation samples, and studies one axis at a time unless a joint family is defined.Source: §3 · pp. 4–6

4 A Simple Multi-Axis Example

A polynomial-class example separates changes to the learning procedure from changes to what it can represent. The example shows why finite-evidence utility gains need a capacity bound.

4 A Simple Multi-Axis Example

  • The example selects an update rule from a finite menu using finite evidence and may also increase the polynomial degree when utility improves.The update rule is chosen from candidate algorithms; representation growth is a distinct modification.Source: §4 · pp. 6–7
  • Switching optimizers changes how the learner traverses a class, while increasing polynomial degree changes the functions it can represent.A global degree cap keeps the reachable family capacity-controlled; without one, repeated utility-rewarded growth can make its VC dimension diverge.Source: §4 · p. 7
  • A coding agent’s test-driven edits can similarly enlarge its reachable program family faster than finite evidence can support.The polynomial example abstracts the question of which predictors or policies become reachable after modification.Source: §4 · p. 7

5 Representational Self-Modification MH

The representational self-modification analysis characterizes learnability through the capacity of the union of reachable hypothesis classes. Its Two-Gate rule combines validation improvement with a fixed capacity-controlled envelope.

5 Representational Self-Modification MH

  • The policy-reachable envelope is the effective predictor family over which policy-dependent class selection occurs, and the analysis assumes its capped reference family is fixed before validation.Validation-set tuning of the cap or thresholds requires a fresh split or reusable holdout.Source: §5 · pp. 7–8
  • The effective family induced by representational self-modification is distribution-free PAC learnable if and only if its policy-reachable envelope has uniformly bounded capacity.Sufficiency follows from a VC upper bound; necessity follows from the VC lower bound when the envelope has infinite VC dimension.Source: §5 · p. 8
  • Two-Gate accepts an edit only under a validation-improvement condition while keeping the incumbent and accepted candidates inside a fixed capacity-capped envelope.The stated guarantees include a true-risk decrease of at least τ per accepted edit and a terminal-class oracle-style bound.Source: §5 · p. 8
  • With local unbounded representational power, a capacity-bonus fit-monotone utility can repeatedly approve capacity-increasing edits without sacrificing empirical fit, yielding an infinite-VC envelope.Under that condition, distribution-free PAC learnability fails.Source: §5 · p. 8

6 Architectural Self-Modification MZ

Architectural edits matter statistically through the hypothesis classes they induce. The same reachable-family capacity boundary and Two-Gate logic therefore apply to architectural self-modification.

6 Architectural Self-Modification MZ

  • Architectural self-modification is reducible to representational self-modification because each architecture induces a hypothesis class and each edit induces a trajectory through those classes.Thus learnability depends on whether the classes reachable through architectural edits remain capacity-bounded.Source: §6 · p. 9
  • The induced architectural family is distribution-free PAC learnable if and only if its policy-reachable envelope has bounded capacity.The architectural boundary follows by applying the general reachable-envelope criterion to the induced family.Source: §6 · p. 9
  • A capacity proxy must bound the union of admissible architectural classes, since bounding each architecture individually does not bound their union.An envelope-valid proxy and a capacity gate restricting edits to the capped reference family allow the Two-Gate conclusions to apply.Source: §6 · p. 10
  • With local unbounded representational power, a capacity-bonus fit-monotone utility can repeatedly accept capacity-increasing architectural edits, producing an infinite-VC envelope and loss of distribution-free PAC learnability.Each local step raises utility, so the proof-trigger fires repeatedly.Source: §6 · p. 10

7 Metacognitive Self-Modification MM

Metacognitive filters select and screen self-modifications, and PAC learnability is preserved exactly when the filtered policy-reachable envelope remains capacity-bounded. Two-Gate can enforce this condition, but its own integrity must be protected.

7 Metacognitive Self-Modification MM

  • The metacognitive rule M chooses which candidate edit to evaluate, when to evaluate it, and whether to accept it using finite evidence.M may also randomize.Source: §7 · pp. 10–11
  • PAC learnability is preserved under metacognitive filtering if and only if the filtered reachable envelope remains uniformly capacity-bounded.The filter may randomize, and the boundary applies to fit-monotone utility functions.Source: §7 · p. 11
  • Two-Gate accepts edits only when validation improvement clears margin τ and the next class stays inside a capped envelope.With probability at least 1−δV−δ, each accepted edit reduces true risk by at least τ.Source: §7 · p. 11
  • Two-Gate's guarantee depends on gate integrity: the metacontroller must remain fixed or preserve the same capped reachable-family invariant when modified.The paper suggests immutability, external enforcement, or a recursively applied meta-gate to protect it.Source: §7 · p. 11
  • A metacognitive rule can confine an otherwise infinite-capacity reachable envelope to a fixed finite-capacity envelope for finite-sample guarantees.If K(m) grows with sample size m, these are a sequence of finite-sample guarantees, not one fixed-capacity PAC claim.Source: §7 · p. 11
  • With margin τ > 0, accepted edits are bounded in number because each reduces true risk by at least τ; scheduling affects efficiency, not the learnability boundary.The risk reductions telescope along any accepted trajectory, and deviation bounds hold uniformly over the capped family.Source: §7 · pp. 11–12

8 Algorithmic Self-Modification MA

Algorithmic self-modification changes update rules while holding the effective hypothesis family fixed. The paper shows that capacity still governs PAC learnability, while a step-mass cap can control generalization during training-dynamics changes.

8 Algorithmic Self-Modification MA

  • Switching update rules remains online or continual learning, but selecting among them using finite evidence can overfit the choice and degrade long-run performance.The setting holds H, architecture, substrate, and metacognitive rule fixed while the update rule, optimizer, schedule, or stopping rule may change.Source: §8 · p. 12
  • Changing a learning rate or optimizer is algorithmic, while changing depth, width, or other choices that alter the induced class is representational or architectural.If the agent can modify the candidate set itself, validation-based improvement is certified only when the reachable family remains capacity-controlled.Source: §8 · p. 12
  • For finite VC(H), ERM or AERM preserves PAC, and ERM over H has a finite-sample guarantee when VC(H) ≤ K.The procedure may be self-modified while continuing to output ERM over H.Source: §8 · p. 12
  • When VC(H) is infinite, no algorithmic procedure has a distribution-free PAC guarantee, so algorithmic self-modification cannot restore learnability.Algorithmic edits do not change the capacity boundary.Source: §8 · p. 12
  • A step-mass cap provides a stability meta-policy for keeping the generalization gap small during algorithmic self-modification.Under the stated bounded, smooth-loss and replacement-invariant schedule assumptions, Λ(m) = O(1) yields an O(1/m) expected generalization gap.Source: §8 · pp. 12–13

9 Substrate Self-Modification MF

The substrate analysis distinguishes changes in computation from changes in the reachable hypothesis family, while the later sections identify the assumptions and global capacity controls needed for the framework’s guarantees. The conclusion presents bounded reachable capacity as the boundary for distribution-free PAC learnability under self-modification.

9 Substrate Self-Modification MF

  • Church–Turing equivalent substrates preserve distribution-free PAC learnability with the same sample complexity up to constant factors, though computation may differ.The theorem holds when switching between equivalent substrates.Source: §9 · p. 13
  • A fixed finite-state substrate with bounded persistent memory can make a previously learnable problem not distribution-free PAC learnable, even when H has finite VC dimension.This is an existence result for a binary classification problem.Source: §9 · p. 13
  • A stronger-than-Church–Turing substrate leaves classical PAC learnability unchanged unless it enlarges the effective reachable hypothesis family.When that family expands, the Section 5 policy-reachable capacity boundary applies.Source: §9 · p. 14

10 Limitations and Scope

  • The guarantees use fixed-distribution i.i.d. data and bounded losses; adaptive, interactive, or changing-distribution data require concentration tools suited to their data-generating process.The stated baseline also assumes independent validation data where used and one-axis-at-a-time analysis unless a joint reachable envelope is defined.Source: §10 · p. 14
  • For agents modifying several axes simultaneously, guarantees require a global capacity cap on the jointly induced reachable family, not separate assurances for each component.The analysis treats axes individually unless a joint reachable envelope is explicitly defined.Source: §10 · p. 14

11 Outlook

  • Two-Gate’s practical reliability depends on a computable capacity proxy that remains valid under composition, and designing such proxies is an open problem.A proxy may be conservative, loose, or difficult to maintain under composition.Source: §10 · p. 14, §11 · p. 15
  • Capacity control preserves worst-case guarantees when self-modification can accept capacity-increasing edits on finite evidence; it does not claim that fixed high-capacity models fail.The outlook frames sustainable self-improvement as constraining reachable capacity relative to available data.Source: §11 · pp. 14–15

12 Conclusion

  • The conclusion states that distribution-free PAC guarantees are preserved if and only if reachable capacity is uniformly bounded, with Two-Gate enforcing the boundary through a validation margin and capacity cap.The guardrail yields a terminal-class oracle-style guarantee.Source: §12 · p. 15

A Appendix

For representational self-modification, distribution-free PAC learnability holds exactly when the policy-reachable envelope has finite VC dimension. The proofs use fixed-family uniform convergence under i.i.d. sampling and specify where validation and joint-edit assumptions matter.

B Definitions

C Assumption Scope and Use in the Proofs

  • The proofs invoke i.i.d. sampling for uniform-convergence events on fixed capped reference families, and the validation family, cap, and margins must be fixed before inspecting validation data.If validation outcomes tune the family, cap, thresholds, or edits, the text calls for a fresh split, reusable holdout, or explicit adaptive-data analysis.Source: C Assumption Scope and Use in the Proofs · pp. 19–20
  • For non-i.i.d., nonstationary, adversarial, or interactively collected data, the PAC statements are baseline guarantees, and the proof technique must change.The text names martingale bounds, online-to-batch conversion, mixing assumptions, shift corrections, and importance weighting as possible replacements for VC uniform-convergence events.Source: C Assumption Scope and Use in the Proofs · p. 20
  • Separate caps on individual modification axes suffice for simultaneous edits only if they also bound the joint reachable envelope.The one-axis proofs hold other state components fixed; combined edits require defining the joint envelope induced by the combined policy.Source: C Assumption Scope and Use in the Proofs · p. 20

D Full Proofs for Representational Self-Modification

  • Representational edits select hypothesis classes using finite evidence, while the learner performs ERM or approximate ERM within an accepted class.An edit is executed only when an immediate utility increase is formally provable from finite evidence.Source: D Full Proofs for Representational… · p. 20

D.1 Sharp policy-level boundary

  • Finite VC dimension of the policy-reachable envelope is necessary and sufficient for distribution-free PAC learnability under the theorem’s assumptions.When its dimension is bounded by K, the stated sample requirement is m = ˜O((K + log(1/δ))/ϵ^2); infinite VC dimension rules out a distribution-free sample-complexity function, even in the realizable case.Source: §D.1 · p. 21

D.2 Finite-sample safety of the Two-Gate policy

The Two-Gate policy combines a capacity cap with a validation-improvement requirement; its guarantee controls accepted edits and the terminal predictor. The appendix also extends the boundary and guardrail arguments to architectural self-modification.

D.2 Finite-sample safety of the Two-Gate policy

  • With probability at least 1−δV−δ, each accepted edit decreases true risk by at least τ, and the terminal predictor satisfies the stated oracle inequality.The policy requires both a capacity gate and validation improvement; approximate ERM adds an αm term to the oracle bound.Source: §D.2 · pp. 21–22

D.3 Destruction under Local-URP

  • Under Local-URP, a capacity-bonus fit-monotone utility can drive repeated capacity-increasing edits, yielding an infinite-VC reachable envelope and loss of distribution-free PAC learnability.The proof-trigger fires because edits preserve or improve empirical fit while the capacity bonus strictly increases utility.Source: §D.3 · p. 22

E Full Proofs for Architectural Self-Modification

  • The architectural boundary follows by reducing proof-triggered architecture trajectories to trajectories over their induced hypothesis classes.The resulting effective architectural family is distribution-free PAC learnable if and only if its reachable envelope has finite VC dimension.Source: E Full Proofs for Architectural… · p. 23
  • Under architectural Local-URP, capacity-bonus fit-monotone utility can likewise produce repeated capacity-increasing edits and an infinite-VC reachable envelope, so distribution-free PAC learnability fails.The proof establishes that the induced envelope’s VC dimension grows without bound along the trajectory.Source: E Full Proofs for Architectural… · p. 23
  • The proxy-cap Two-Gate result guarantees risk-decreasing accepted edits and a terminal-predictor oracle inequality, but compares against the terminal class rather than the larger envelope.A pointwise bound on each individual architecture’s VC dimension alone does not establish a bound on the union envelope.Source: E Full Proofs for Architectural… · pp. 23–24

F Full Proofs for Metacognitive Self-Modification

Metacognitive filtering preserves distribution-free PAC learnability exactly when the filtered policy-reachable envelope has finite VC dimension. A fixed-cap filter can confine an otherwise unbounded envelope at a given sample size, but growing caps do not establish one fixed-capacity PAC guarantee.

F Full Proofs for Metacognitive Self-Modification

  • For any fit-monotone utility and metacognitive filter, distribution-free PAC learnability holds if and only if the filtered reachable envelope has finite VC dimension.The proof applies the representational boundary to the filtered effective reachable predictor family.Source: F Full Proofs for Metacognitive… · p. 24
  • A filter approving only Two-Gate edits within a fixed capped envelope gives the finite-sample guarantee when the cap invariant is preserved.If K(m) grows with sample size, these are guarantees for a sequence of sample-size-dependent envelopes, not a single fixed-capacity PAC claim.Source: F Full Proofs for Metacognitive… · p. 24

G Full Proofs for Algorithmic Self-Modification

Algorithmic self-modification can select training procedures but leaves a fixed hypothesis class unchanged, so it cannot remove the infinite-VC lower bound. For finite-VC classes, ERM/AERM retains the PAC rate; the stability result additionally relies on replacement-invariant schedule selection.

G.1 No algorithmic cure for infinite VC

  • With an infinite-VC fixed hypothesis class, selecting among training procedures does not remove the classical distribution-free PAC lower bound.The stated algorithmic setting uses a fixed class and replacement-invariant schedules, excluding schedule choices that change sensitively under a one-example replacement.Source: G Full Proofs for Algorithmic… · p. 24, §G.1 · p. 25

G.2 ERM/AERM on finite VC

  • On a fixed finite-VC class, ERM/AERM preserves the PAC rate.The result follows from standard uniform-convergence bounds for classes with VC dimension at most K.Source: §G.2 · p. 25

G.3 Proof of Thm. 11: stability via step-mass

  • Replacement invariance makes the coupled schedule identical on neighboring samples; without it, additional scheduler stability control is required.The assumption holds when schedules depend on randomness or evidence independent of the training sample, not when one-example replacements alter the schedule.Source: G Full Proofs for Algorithmic… · p. 24, §G.3 · p. 26
  • When Λ(m) = O(1), the expected generalization gap is O(1/m).The proof bounds expected replace-one stability and transfers that bound to generalization.Source: §G.3 · p. 26

H Full Proofs for Substrate Self-Modification

Under i.i.d. data and bounded loss, CT-equivalent substrates preserve distribution-free PAC sample complexity, while finite-state downgrades can destroy learnability. For beyond-CT substrates, PAC guarantees depend on whether the edit changes the reachable hypothesis family.

H.1 CT-invariance (Thm. 12)

  • CT-equivalent substrates preserve the same PAC sample complexity because bounded-overhead simulation leaves the learner’s input-output behavior unchanged; runtime may differ.The assumptions specify i.i.d. data, loss in [0, 1], and ERM/AERM as specified.Source: §H.1 · p. 26, H Full Proofs for Substrate… · p. 26

H.2 Finite-state downgrade impossibility (Prop. 13)

  • For N persistent states and m>N, indistinguishable samples can yield conflicting threshold predictions, causing constant error and ruling out PAC guarantees for ϵ<c/2 despite VC dimension 1.The error occurs with probability at least 1/2; the threshold class has VC dimension 1 and is PAC-learnable on CT-equivalent substrates.Source: §H.2 · p. 26

H.3 Beyond-CT substrates (Prop. 14)

  • If a beyond-CT substrate edit leaves the measurable hypothesis family unchanged, PAC sample-complexity guarantees remain unchanged; when it enlarges the reachable collection, preservation is assessed through its predictor envelope’s VC dimension.A finite-state substrate has a fixed number of persistent states available across training and prediction, independent of m.Source: §H.2 · p. 26, §H.3 · p. 27

Related papers

Loading 2510.04399v3…