CoChat
Sign Up
PreprintCited by 0Machine Learning and AlgorithmsReinforcement Learning in RoboticsDomain Adaptation and Few-Shot Learning

On The Statistical Limits of Self-Improving Agents

Open access
Wang, Charles L., Dorchen, Keir, Jin, Peter·2025·arXiv
DOI 10.48550/arxiv.2510.04399arXiv 2510.04399
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper develops a learning-theoretic framework for self-improving agents, decomposing self-modification into five axes and proving that distribution-free PAC learnability is preserved if and only if the policy-reachable family remains uniformly capacity-bounded. It introduces a Two-Gate guardrail—validation improvement plus a capacity cap—that preserves this boundary and yields VC-rate guarantees.

Key findings

  • The five-axis decomposition is algorithmic, representational, architectural, substrate, and metacognitive. Under Assumptions A1–A7, for 0-1 loss, the effective family induced by representational self-modification is distribution-free PAC learnable iff there exists \(K < \infty\) such that \(\mathrm{VC}(G_{\mathrm{reach}}(u)) \le K\); if reachable capacity can grow without bound, utility-rational self-changes can make learnable tasks unlearnable.
  • The Two-Gate policy accepts an edit only if validation risk satisfies \(R_V(h_{\mathrm{new}}) \le R_V(h_{\mathrm{old}}) - [2\varepsilon_V + \tau]\) and \(H_{\mathrm{new}} \subseteq G_{K(m)}\) with \(\mathrm{VC}(G_{K(m)}) \le K(m)\). Then with probability at least \(1-\delta_V-\delta\), each accepted edit decreases true risk by at least \(\tau\), and \(R(h_T) \le \inf_{h\in H_T} R(h) + \tilde{O}\!\left(\frac{K(m)+\log(1/\delta)}{m}\right)\); for an \(\alpha_m\)-approximate ERM, an additional additive term \(\alpha_m\) appears.
  • Architectural self-modification reduces to the representational boundary: learnability holds iff \(\mathrm{VC}(G^Z_{\mathrm{reach}}(u)) \le K < \infty\). Metacognitive filtering gives the same boundary with \(\mathrm{VC}(G^{M,H}_{\mathrm{reach}}(u)) \le K < \infty\). Algorithmic edits cannot cure infinite VC; finite VC is sufficient with ERM, and a step-mass meta-policy gives \(\mathbb{E}[\mathrm{gap}] \le \frac{2LG}{m} M_T e^{\beta M_T}\), so \(M_T \le \Lambda(m)\) yields \(O(\Lambda(m)e^{\beta\Lambda(m)}/m)\), with \(\Lambda(m)=O(1)\) giving an \(O(1/m)\) expected generalization gap.
  • Substrate edits: Church-Turing equivalent substrates preserve distribution-free PAC learnability with the same sample complexity up to constant factors; a finite-state downgrade can destroy learnability even when the specification has finite VC dimension; stronger-than-Church-Turing substrates change the boundary only if they enlarge the induced reachable family.

Methods

  • Theoretical learning-theoretic analysis of supervised learning under an unknown distribution \(D\) over \(X \times Y\), with i.i.d. training \(S \sim D^m\) and independent validation \(V \sim D^{n_v}\), bounded loss \(\ell \in [0,1]\), and capacity measured by VC dimension or pseudodimension; axes are analyzed one at a time while holding others fixed.
  • Self-modification is formalized via a modification map \(\Phi\) and policy-reachable sets/envelopes; the paper proves boundary theorems, Two-Gate finite-sample safety, architectural-to-representational reduction, destruction under local unbounded representational power, step-mass stability, and substrate invariance/downgrade results.
  • No empirical experiments are reported; the results are theorems and propositions with proofs in appendices.

Limitations

  • The paper states that the main theorems are intentionally in the classical distribution-free PAC baseline: i.i.d. fixed distribution, bounded losses, and accepted hypotheses lying in a fixed capped reference family before validation is inspected. Nonstationary, adaptive, or interactive data are not covered and would require martingale concentration, online-to-batch conversion, covariate-shift or importance-weighting assumptions, reusable holdout methods, or explicit mixing and drift conditions.
  • The paper states that the five-axis decomposition analyzes one axis at a time; realistic multi-axis agents require a global cap on the jointly induced reachable family. It also states that Two-Gate is only as reliable as the capacity proxy, which may be conservative, loose, or difficult to maintain under composition, and that the gate-integrity regress is not fully solved.
  • Evident from the text: there is no empirical validation, and the compute scope is sample complexity rather than runtime unless limits are intrinsic to the substrate (A7). Validation reuse is safe only if the capped reference family, cap schedule, and thresholds are fixed ex ante before seeing \(V\); otherwise a fresh split or reusable holdout is required.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

DataCite · 10.48550/arxiv.2510.04399

Cites

0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 1 cited sources checked · 0 supported · 0 flagged

  • Findingreasoning

    Under Two-Gate with margin τ > 0, along any accepted trajectory the number of accepted edits is at most (R(h_0) - R^⋆)/τ, where R^⋆ = inf_{h∈G_K(m)} R(h) and h_0 is the initial accepted predictor.

    “Edit efficiency under margins.Under Two-Gate with margin τ > 0, along any accepted trajectory the number of accepted edits is at most R(h 0 ) -R ⋆ τ , R ⋆ = inf h∈G K(m) R(h), where h 0 denotes the initial accepted predictor on the trajectory.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.
  • Findingnone given

    For an α_m-approximate ERM, the right-hand side of Theorem 2 has an additional additive term α_m.

    “For an α m -approximate ERM, the right-hand side has an additional additive term α m .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.
  • Findingreasoning

    For any fit-monotone u, the effective family induced by architectural self-modification is distribution-free PAC learnable if and only if VC(G^Z_reach(u)) ≤ K < ∞.

    “Theorem 4. Architectural boundary via induced reachable family For any fit-monotone u, the effective family induced by architectural self-modification is distribution-free PAC learnable if and only if VC G Z reach (u) ≤ K < ∞.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.
  • Findingreasoning

    If reachable capacity can grow without bound, utility-rational self-changes can make learnable tasks unlearnable.

    “If reachable capacity can grow without bound, utility-rational self-changes can make learnable tasks unlearnable.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.
  • Findingown data

    Downgrading to a strictly weaker substrate, such as finite-state memory, can destroy PAC learnability even for problems learnable pre-switch.

    “Second, downgrading to a strictly weaker substrate, such as finite-state memory, can destroy PAC learnability even for problems learnable pre-switch.”
    • Also stated in: § Proposition 13. Finite-state downgrade can destroy learnability · plain
      “There exists a binary classification problem that is PAC learnable on a Church-Turing equivalent substrate but becomes not distribution-free PAC learnable after switching to a fixed finite-state substrate with bounded persistent memory, even when H has finite VC dimension as a specification.”
    Quote in the paperSubstantial claim
  • May combine two claims. 28
  • Classified as probably not a substantial claim. 12

  • May combine two claims.

    Findingreasoning

    If the degree sequence is globally capped, for example d_t ≤ d_max(m), then the reachable family remains capacity-controlled; if myopic utility keeps rewarding degree growth with no such cap, the reachable VC dimension can diverge even though each local edit appeared beneficial.

    “If the degree sequence is globally capped, for example d t ≤ d max (m), then the reachable family remains capacity-controlled.If myopic utility keeps rewarding degree growth with no such cap, the reachable VC dimension can diverge even though each local edit appeared beneficial.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    If the unfiltered reachable envelope satisfies VC(G_reach(u)) = ∞, then for a fixed sample size m, a metacognitive rule M such as Two-Gate with preserved gate integrity can confine every accepted class to a fixed envelope G_K(m) satisfying VC(G_K(m)) ≤ K(m), so G^M,H_reach(u) ⊆ G_K(m), yielding the stated finite-sample guarantee.

    “Restorative metacognition.Suppose the unfiltered reachable envelope satisfies VC(G reach (u)) = ∞.For a fixed sample size m, a metacognitive rule M , such as Two-Gate with preserved gate integrity, can confine every accepted class to a fixed envelope G K(m) satisfying VC(G K(m) ) ≤ K(m). Then G M,H reach (u) ⊆ G K(m) , yielding the stated finite-sample guarantee.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.

  • May combine two claims.

    Findingreasoning

    If VC(H) = ∞, then no distribution-free PAC guarantee is possible for any algorithmic procedure; in particular, algorithmic self-modification cannot restore distribution-free learnability.

    “Proposition 9.No algorithmic cure for infinite VC If VC(H) = ∞, then no distribution-free PAC guarantee is possible for any algorithmic procedure.In particular, algorithmic self-modification cannot restore distribution-free learnability.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.

  • May combine two claims.

    Findingreasoning

    For any fit-monotone u, every proof-triggered trajectory Z_0 → Z_1 → ... induces a representational trajectory H(Z_0) → H(Z_1) → ... over a fixed reference family, with ERM inside each accepted H(Z_t); consequently H^Z_reach(u) = {H(Z) : Z ∈ Z_reach(u)}.

    “Lemma 3. Architectural to representational reduction For any fit-monotone u, every proof-triggered trajectory Z 0 → Z 1 → • • • induces a representational trajectory H(Z 0 ) → H(Z 1 ) → • • • over a fixed reference family, with ERM inside each accepted H(Z t ).Consequently H Z reach (u) = {H(Z) : Z ∈ Z reach (u)}.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.

  • May combine two claims.

    Findingreasoning

    Under the stated conditions, E[R(ĥ) - R_S(ĥ)] ≤ (2LG/m) Σ_{t=1}^T η_t exp(β Σ_{s=t+1}^T η_s) ≤ (2LG/m) M_T e^{β M_T}; consequently, a metacognitive rule enforcing M_T ≤ Λ(m) guarantees E[gap] = O(Λ(m)e^{βΛ(m)}/m), and Λ(m) = O(1) yields an O(1/m) expected generalization gap.

    “Theorem 11.Algorithmic stability via step-mass Under the conditions above, E R( ĥ) -R S ( ĥ) ≤ 2LG m T t=1 η t exp β T s=t+1 η s ≤ 2LG m M T e βM T . Consequently, a metacognitive rule enforcing M T ≤ Λ(m) guarantees E[gap] = O Λ(m)e βΛ(m) m . In particular, Λ(m) = O(1) yields an O(1/m) expected generalization gap.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.
    • The authors state this as an assumption: For the stability meta-policy, ℓ(θ; z) is bounded, L-Lipschitz, and β-smooth in θ, with ∥∇_θ ℓ(θ; z)∥ ≤ G, and training examples are sampled uniformly from S.
    • The authors state this as an assumption: The schedule-selection rule is replacement-invariant: under shared randomness, two datasets differing in one example produce the same sequence of update maps and step sizes.

  • May combine two claims.

    Findingreasoning

    If a metacognitive rule enforces M T = t η t ≤ Λ(m), then E[gap] = O(Λ(m)e βΛ(m)/m). In particular, Λ(m) = O(1) gives an O(1/m) expected generalization gap.

    “If a metacognitive rule enforces M T = t η t ≤ Λ(m), then E[gap] = O Λ(m)e βΛ(m) m . In particular, Λ(m) = O(1) gives an O(1/m) expected generalization gap.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Findingreasoning

    Assume VC(H) ≤ K < ∞. Standard uniform-convergence bounds give... If ĥ is ERM in H, then R( ĥ) ≤ inf h∈H R(h) + Õ... Thus ERM/AERM preserves the PAC rate on a fixed finite-VC class.

    “Assume VC(H) ≤ K < ∞.Standard uniform-convergence bounds give, with probability at least 1 -δ, sup h∈H R(h) -R S (h) ≤ c 2 K+log(1/δ) m for a universal constant c 2 > 0. If ĥ is ERM in H, then R( ĥ) ≤ inf h∈H R(h) + Õ K+log(1/δ) m . Thus ERM/AERM preserves the PAC rate on a fixed finite-VC class.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingreasoning

    Assume Local-URP Z. For any capacity-bonus fit-monotone utility u, there exist a distribution D and sample size m such that the proof-trigger repeatedly accepts local architectural edits that increase capacity, the induced reachable envelope G Z reach (u) has infinite VC dimension, and distribution-free PAC learnability fails.

    “Assume Local-URP Z .For any capacity-bonus fit-monotone utility u, there exist a distribution D and sample size m such that the proof-trigger repeatedly accepts local architectural edits that increase capacity, the induced reachable envelope G Z reach (u) has infinite VC dimension, and distribution-free PAC learnability fails.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Local-URP Z holds.
    • The authors state this as an assumption: For destruction results, utility u is capacity-bonus fit-monotone.

  • May combine two claims.

    Findingreasoning

    With probability at least 1 -δ V -δ over (V, S), each accepted architectural edit decreases true risk by at least τ, and the terminal predictor obeys R(h S (Z T )) ≤ inf h∈H(Z T ) R(h) + Õ((K(m)+log(1/δ))/m).

    “Then with probability at least 1 -δ V -δ over (V, S): (i) each accepted architectural edit decreases true risk by at least τ ; and (ii) the terminal predictor obeys R(h S (Z T )) ≤ inf h∈H(Z T ) R(h) + Õ K(m)+log(1/δ) m .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The computable proxy B is envelope-valid.

  • May combine two claims.

    Findingreasoning

    If the unrestricted policy-reachable envelope has infinite VC dimension, a metacognitive filter M that approves only edits satisfying Two-Gate relative to a fixed envelope G K(m) with VC(G K(m)) ≤ K(m) confines the filtered reachable envelope to G K(m), so the Two-Gate finite-sample guarantee applies.

    “Suppose the unrestricted policy-reachable envelope has infinite VC dimension.For a fixed sample size m, define M to approve only edits satisfying Two-Gate relative to a fixed envelope G K(m) with VC(G K(m) ) ≤ K(m).This finite-sample confinement is conditional on gate integrity: either M is immutable, or every admissible edit to M must preserve the same capped-envelope invariant.Then G M,H reach (”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The computable proxy B is envelope-valid.

  • May combine two claims.

    Findingreasoning

    This is an expected replace-one stability bound. Standard stability-to-generalization transfer therefore gives E R( ĥ) -R S ( ĥ) ≤ 2LG/m ...

    “This is an expected replace-one stability bound.Standard stability-to-generalization transfer therefore gives E R( ĥ) -R S ( ĥ) ≤ 2LG m T t=1 η t exp β T s=t+1 η s ≤ 2LG m M T e βM T .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The schedule-selection rule is replacement-invariant.
    • The authors state this as an assumption: The hypothesis class H = {x → f θ (x) : θ ∈ Θ} is fixed throughout the algorithmic edits.

  • May combine two claims.

    Findingreasoning

    With probability at least 1-δ V -δ over (V, S), each accepted edit decreases true risk by at least τ, and the terminal predictor h T satisfies the oracle inequality R(h T ) ≤ inf h∈H T R(h) + Õ((K(m)+log(1/δ))/m).

    “With probability at least 1-δ V -δ over (V, S): (i) each accepted edit decreases true risk by at least τ ; and (ii) the terminal predictor h T satisfies the oracle inequality R(h T ) ≤ inf h∈H T R(h) + Õ K(m)+log(1/δ) m .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Training and validation samples are independent i.i.d. draws from a fixed distribution.
    • The authors state this as an assumption: Losses are bounded.
    • The authors state this as an assumption: Accepted hypotheses lie in a fixed capped reference family before validation is inspected.
    • The authors state this as an assumption: The reference family G K(m), the cap schedule K(m), and the margin parameters are fixed before inspecting V.
    • The authors state this as an assumption: The initial-class assumption H 0 ⊆ G K(m) holds.
    • The authors state this as an assumption: h S (H) is an ERM in H.

  • May combine two claims.

    Findingreasoning

    The Two-Gate guardrail-a validation margin together with a capacity cap-enforces this boundary and yields a terminal-class oracle-style guarantee.

    “We further gave a simple Two-Gate guardrail-a validation margin together with a capacity cap-that enforces this boundary and yields a terminal-class oracle-style guarantee.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    Assume Local-URP. Then for any capacity-bonus fit-monotone utility u, there exist a distribution D and sample size m such that the proof-trigger repeatedly accepts capacity-increasing local edits, the policy-reachable envelope has infinite VC dimension, and distribution-free PAC learnability fails.

    “Assume Local-URP.Then for any capacity-bonus fit-monotone utility u, there exist a distribution D and sample size m such that the prooftrigger repeatedly accepts capacity-increasing local edits, the policy-reachable envelope has infinite VC dimension, and distribution-free PAC learnability fails.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Local-URP holds.
    • The authors state this as an assumption: For destruction results, utility u is capacity-bonus fit-monotone.

  • May combine two claims.

    Interpretationreasoning

    The boundary and Two-Gate guarantees depend only on the capacity of the reachable family, not on explicit capacity rewards; even if u has no bonus term, any policy that permits capacity-increasing edits can cross the boundary unless a cap such as K(m) is enforced.

    “The boundary and Two-Gate guarantees depend only on the capacity of the reachable family, not on explicit capacity rewards.Even if u has no bonus term, any policy that permits capacityincreasing edits can cross the boundary unless a cap such as K(m) is enforced.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    The metacognitive axis primarily filters trajectories rather than directly enlarging the effective hypothesis family.

    “Role of this axis.This axis primarily filters trajectories rather than directly enlarging the effective hypothesis family.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    Church-Turing equivalent substrates preserve solvability up to simulation overhead, whereas strictly weaker substrates with finite memory can forfeit learnability of classes that are otherwise PAC-learnable.

    “Church-Turing equivalent substrates preserve solvability up to simulation overhead, whereas strictly weaker substrates with finite memory can forfeit learnability of classes that are otherwise PAC-learnable.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites Akbari & Harrison-Trainor, 2024

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning

    Tuning a learning rate, batch schedule, optimizer, or stopping rule while keeping H fixed is algorithmic; tuning depth, width, kernel features, regularization strength, retrieval size, number of experts, or any choice that changes the induced class is representational or architectural.

    “Hyperparameter tuning sits at the boundary between algorithmic and representational self-modification.Tuning a learning rate, batch schedule, optimizer, or stopping rule while keeping H fixed is algorithmic.Tuning depth, width, kernel features, regularization strength, retrieval size, number of experts, or any choice that changes the induced class is representational or architectural.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    From a PAC perspective, architecture matters through the hypothesis family it induces, so the architectural axis can be folded into the representational axis.

    “From a PAC perspective, architecture matters through the hypothesis family it induces.Thus the architectural axis can be folded into the representational axis; we keep it separate only because, in modern systems, architecture is often the operational handle by which the representational family is changed.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Study design and conductnone given

    If selection depends on labels or on V, standard importance-weighting or covariate-shift corrections must be used; otherwise guarantees may fail.

    “If selection depends on labels or on V , standard importance-weighting or covariate-shift corrections must be used; otherwise guarantees may fail.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.

  • May combine two claims.

    Study design and conductreasoning

    Because the deviation bound is uniform over the capped family, the safety and rate guarantees hold for every realized trajectory filtered by M; scheduling affects efficiency, not the boundary.

    “Scheduling and randomness.Because the deviation bound is uniform over the capped family, the safety and rate guarantees hold for every realized trajectory filtered by M .Scheduling affects efficiency, not the boundary.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.
    • The authors state this as an assumption: Loss is bounded, ℓ ∈ [0, 1].
    • The authors state this as an assumption: Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.
    • The authors state this as an assumption: When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.
    • The authors state this as an assumption: If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.
    • The authors state this as an assumption: We analyze one axis at a time while holding the others fixed.
    • The authors state this as an assumption: We study sample complexity, not runtime, unless limits are intrinsic to F.

  • May combine two claims.

    Interpretationreasoning

    Each axis induces a set of post-modification predictors, and the union of what the agent can reach under its decision rule is the only object that matters for distribution-free guarantees.

    “Each axis induces a set of post-modification predictors, and the union of what the agent can reach under its decision rule is the only object that matters for distribution-free guarantees.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    If the reachable family is controlled by a valid cap or proxy, distribution-free guarantees can be retained within the abstraction; if the family can expand without bound, validation gains on finite evidence alone do not imply learnability.

    “If the reachable family is controlled by a valid cap or proxy, distribution-free guarantees can be retained within the abstraction; if the family can expand without bound, validation gains on finite evidence alone do not imply learnability.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    If the agent may optimize the guardian, then the guardian must also be guarded; every admissible edit to M must itself certify that the post-edit reachable family remains uniformly capacity-bounded.

    “This reveals a simple regress: if the agent may optimize the guardian, then the guardian must also be guarded.In our framework, the natural resolution is recursive invariant preservation: every admissible edit to M must itself certify that the post-edit reachable family remains uniformly capacity-bounded.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    The algorithmic axis concerns policy-selected update dynamics within a fixed effective hypothesis family.

    “Role of this axis.This axis concerns policy-selected update dynamics within a fixed effective hypothesis family.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S2 (checkable).

    Interpretationreasoning

    For non-i.i.d., nonstationary, adversarial, or interactively collected data, the PAC statements should be read as baseline guarantees rather than direct deployment guarantees.

    “For non-i.i.d., nonstationary, adversarial, or interactively collected data, the PAC statements should be read as baseline guarantees rather than direct deployment guarantees.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given

    A pointwise bound VC(H(Z)) ≤ B(Z) for each individual architecture is not sufficient to establish the union bound for the proxy envelope.

    “A pointwise bound VC(H(Z)) ≤ B(Z) for each individual architecture is not sufficient to establish this union bound.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    Constraints on reachable capacity do not preclude improvement; they distinguish sustainable self-improvement from self-modification that outruns the evidence needed to justify it.

    “Such constraints do not preclude improvement; they instead distinguish sustainable self-improvement from self-modification that outruns the evidence needed to justify it.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    Algorithmic self-modification selects among training procedures but does not change H, hence does not change the lower bound.

    “Algorithmic self-modification selects among training procedures but does not change H, hence does not change the lower bound.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning

    The policy-reachable-envelope invariant remains the proposed structural object, but the proof technique must change outside the baseline.

    “The policy-reachable-envelope invariant remains the proposed structural object, but the proof technique must change.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    Modern deep learning often succeeds far beyond what worst-case PAC sample-complexity bounds would predict, often because of implicit regularization, favorable inductive biases, and benign data structure.

    “Modern deep learning often succeeds far beyond what worst-case PAC sample-complexity bounds would predict, often because of implicit regularization, favorable inductive biases, and benign data structure.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    This finite-sample confinement is conditional on gate integrity: either M is immutable, or every admissible edit to M must preserve the same capped-envelope invariant.

    “This finite-sample confinement is conditional on gate integrity: either M is immutable, or every admissible edit to M must preserve the same capped-envelope invariant.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    A fixed high-capacity model may still generalize well, but a self-modifying learner can repeatedly accept capacity-increasing edits on finite evidence, eventually entering regimes where no distribution-free guarantee remains available.

    “A fixed high-capacity model may still generalize well, but a self-modifying learner can repeatedly accept capacity-increasing edits on finite evidence, eventually entering regimes where no distribution-free guarantee remains available.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Interpretationreasoning

    The gap between a tractable upper bound B(•) and the true capacity of the induced family determines how conservative a Two-Gate policy must be in realistic systems.

    “The gap between a tractable upper bound B(•) and the true capacity of the induced family determines how conservative a Two-Gate policy must be in realistic systems.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Study design and conductreasoning

    The i.i.d. assumption is used only to invoke uniform convergence for the fixed capped reference families appearing in the main text.

    “The i.i.d.assumption is used only to invoke uniform convergence for the fixed capped reference families appearing in the main text.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Training and validation samples are independent i.i.d. draws from a fixed distribution.

  • Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing), S4 (based). May combine two claims.

    Interpretationnone given

    A computable upper bound B(•) may be conservative, loose, or difficult to maintain under composition.

    “A computable upper bound B(•) may be conservative, loose, or difficult to maintain under composition.”
    Quote in the paperNot a substantial claim
36 of 36

  • The authors state this as an assumption.

    Data ⟨x, y⟩ are i.i.d. from fixed D; training S ∼ D^m and validation V ∼ D^{n_v} are independent.

    “A1 Data ⟨x, y⟩ are i.i.d.from fixed D. Training S ∼ D m and validation V ∼ D nv are independent.”

  • The authors state this as an assumption.

    Loss is bounded, ℓ ∈ [0, 1].

    “A2 Loss is bounded, ℓ ∈ [0, 1].”

  • The authors state this as an assumption.

    Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.

    “A3 Capacity is any uniform-convergence notion, such as VC, pseudodimension, or VC-subgraph.We instantiate VC where convenient.”

  • The authors state this as an assumption.

    When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.

    “When a computable proxy B is used to certify a family of admissible edits, the resulting fixed envelope is assumed to have the stated capacity bound.”

  • The authors state this as an assumption.

    If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense; non Church-Turing substrates may alter this and are treated separately.

    “If the substrate F is Church-Turing equivalent, solvability and learnability are measured in the classical computable sense.Non Church-Turing substrates may alter this and are treated separately in Section 9.”

  • The authors state this as an assumption.

    We analyze one axis at a time while holding the others fixed.

    “We analyze one axis at a time while holding the others fixed.”

  • The authors state this as an assumption.

    We study sample complexity, not runtime, unless limits are intrinsic to F.

    “Compute scope.We study sample complexity, not runtime, unless limits are intrinsic to F .”

  • The authors state this as an assumption.

    For the stability meta-policy, ℓ(θ; z) is bounded, L-Lipschitz, and β-smooth in θ, with ∥∇_θ ℓ(θ; z)∥ ≤ G, and training examples are sampled uniformly from S.

    “Assume that ℓ(θ; z) is bounded, L-Lipschitz, and β-smooth in θ, with ∥∇ θ ℓ(θ; z)∥ ≤ G, and that training examples are sampled uniformly from S.”

  • The authors state this as an assumption.

    The schedule-selection rule is replacement-invariant: under shared randomness, two datasets differing in one example produce the same sequence of update maps and step sizes.

    “We additionally assume that the schedule-selection rule is replacement-invariant: under shared randomness, two datasets differing in one example produce the same sequence of update maps and step sizes.”

  • The paper relies on this without support.

    Current agentic systems increasingly revise parts of their own learning process in response to finite feedback.

    “Current agentic systems increasingly revise parts of their own learning process in response to finite feedback.”

  • The paper relies on this without support.

    Switching substrates changes how H, Z, and A are executed but not which hypotheses are definable nor which utilities are expressible.

    “Switching substrates changes how these are executed but not which hypotheses are definable nor which utilities are expressible.”

  • The authors state this as an assumption.

    Training and validation samples are independent i.i.d. draws from a fixed distribution.

    “The training and validation samples are independent i.i.d.draws from a fixed distribution”

  • The authors state this as an assumption.

    Losses are bounded.

    “losses are bounded”

  • The authors state this as an assumption.

    Accepted hypotheses lie in a fixed capped reference family before validation is inspected.

    “the accepted hypotheses lie in a fixed capped reference family before validation is inspected”

  • The authors state this as an assumption.

    The reference family G K(m), the cap schedule K(m), and the margin parameters are fixed before inspecting V.

    “The validation proof assumes that the reference family G K(m) , the cap schedule K(m), and the margin parameters are fixed before inspecting V .”

  • The authors state this as an assumption.

    Data are i.i.d.; loss lies in [0,1]; ERM/AERM is used as specified.

    “Data are i.i.d.; loss lies in [0, 1]; ERM/AERM is used as specified.”

  • The authors state this as an assumption.

    A substrate is a computational model hosting the same specification (H, Z, A) unless explicitly stated.

    “A substrate is a computational model hosting the same specification (H, Z, A) unless explicitly stated.”

  • The authors state this as an assumption.

    The schedule-selection rule is replacement-invariant.

    “The schedule-selection rule is replacement-invariant: under shared randomness, two samples differing in one example generate the same sequence of update types, projections, and step sizes.”

  • The authors state this as an assumption.

    The hypothesis class H = {x → f θ (x) : θ ∈ Θ} is fixed throughout the algorithmic edits.

    “The hypothesis class H = {x → f θ (x) : θ ∈ Θ} is fixed throughout the algorithmic edits.”

  • The authors state this as an assumption.

    Local-URP holds.

    “Assume Local-URP.”

  • The authors state this as an assumption.

    Local-URP Z holds.

    “Assume Local-URP Z .”

  • The authors state this as an assumption.

    The capacity gate guarantees all accepted H satisfy H ⊆ G K.

    “assume the capacity gate guarantees all accepted H satisfy H ⊆ G K .”

  • The authors state this as an assumption.

    The envelope G K is fixed independently of the validation sample.

    “The envelope G K is fixed independently of the validation sample; otherwise the uniform validation event must be replaced by an adaptive-validation argument.”

  • The authors state this as an assumption.

    The computable proxy B is envelope-valid.

    “where B is envelope-valid”

  • The authors state this as an assumption.

    The initial-class assumption H 0 ⊆ G K(m) holds.

    “Assume H 0 ⊆ G K(m) and that h S (H) is an ERM in H.”

  • The authors state this as an assumption.

    h S (H) is an ERM in H.

    “Assume H 0 ⊆ G K(m) and that h S (H) is an ERM in H.”

  • The authors state this as an assumption.

    Utility u is fit-monotone.

    “Fix a fit-monotone utility u and the proof-triggered decision rule.”

  • The authors state this as an assumption.

    For destruction results, utility u is capacity-bonus fit-monotone.

    “For the destruction results only, we use the stronger notion of a capacity-bonus fit-monotone utility”

  • The paper relies on this without support.

    Real autonomous agents may modify several components at once.

    “Real autonomous agents may modify several components at once: architectures, update rules, tool libraries, and metacognitive policies.”
29 of 29

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Adaptive validation reuse conflicts with the appendix's proposal restriction

    Minor

    The main text permits adaptive reuse of V across edits under fixed-family and fixed-threshold conditions. The appendix additionally requires a fresh split or reusable holdout if edit proposals are tuned using validation outcomes, a restriction absent from the main-text permission.

1 of 1

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 10

  1. Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2: 499-526, 2002.
  2. Qi Chen, Changjian Shui, and Mario Marchand. Generalization bounds for meta-learning: An information- theoretic analysis. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pp. 25878-25890, 2021.
  3. Matthias Feurer and Frank Hutter. Automl: A survey of the state of the art. In Automated Machine Learning, pp. 3-33. Springer, 2019.
  4. Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren. Automated Machine Learning: Methods, Systems, Challenges. Springer, 2019. Published in Transactions on Machine Learning Research (08/2026)
  5. Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1): 6765-6816, 2017.
  6. Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.
  7. Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
  8. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
  9. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2 edition, 2018.
  10. Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998.

Authors
Wang, C. L., Dorchen, K., & Jin, P.
Affiliations
Columbia University (US)
Venue
arXiv
Publisher
arXiv
Published
2025
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2510.04399
arXiv
2510.04399
OpenAlex
W4414971540
Cited by
0
References
0
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
Keywords
self-improving agents, self-modification, PAC learnability, VC dimension

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-24.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-24.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review