PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers

Jaehee Seo, Jisu Kim

arXiv:2609.31458v1stat.MLcs.LGmath.STstat.TH

TL;DR

Existing nonparametric ICL theory has mainly treated Euclidean domains or single manifolds, leaving unknown heterogeneous local geometry as an open prediction setting. The paper proves matching aggregate minimax bounds and constructs an oracle estimator and transformer for growing manifold mixtures. Under its local-regime assumptions, the estimator attains the benchmark and near-ERM prediction has a fresh-task generalization bound.

  • Problem

    Nonparametric ICL theory has largely focused on Euclidean domains or single manifolds, while optimal prediction with unknown heterogeneous local geometry remains an open question.

    Source: §1 · p. 2

  • Method

    The paper models growing heterogeneous manifold mixtures, derives an aggregate minimax benchmark, and constructs an oracle tangent local-polynomial estimator with a transformer realization.

    Source: §1.1 · p. 2

  • Results

    The oracle estimator attains the aggregate benchmark, and every measurable near ERM in the specified architecture class receives a fresh-task generalization bound under the stated assumptions.

    Source: §3.2 · p. 6, §5 · p. 9

  • Takeaways & Limitations

    The results identify conditions under which a geometry-first in-context predictor can attain the aggregate minimax rate.

    Source: §6 · p. 10

    Even with sufficient pretraining and knowledge of the hard task law, a matching lower bound holds worst-case over task distributions because each new task still provides only n prompt examples.

    Source: §5 · p. 10

Abstract

from arXiv · show

Transformers have become a central architecture for in-context learning (ICL), particularly through their state-of-the-art performance in large language models. This success motivates understanding how transformers exploit task-relevant structure in geometrically heterogeneous data. However, existing nonparametric ICL theory has largely focused on Euclidean domains or single-manifold models. To address this gap, we study the prediction problem under unknown local geometry, modeled by sample size-dependent mixtures of manifolds with heterogeneous dimensions, smoothness, and sampling masses. Under local separation and small-perturbation conditions, we establish a minimax lower bound capturing the aggregate difficulty of the components and construct an oracle tangent local-polynomial estimator with a matching upper bound. This estimator is connected to a structure-informed, two-stage softmax transformer with a geometric preconditioner and chartwise reduced local-polynomial solvers. The transformer achieves negligible approximation error relative to the minimax rate with logarithmic depth and polynomial size. Finally, we derive an in-context generalization bound for near empirical risk minimizers over this class. Together, these results identify conditions under which the resulting predictor exploits local geometry and attains the aggregate minimax rate.

1 Introduction

The paper asks whether nonparametric in-context prediction can remain optimal when local geometry is unknown and heterogeneous. It models that setting with growing mixtures of manifolds and gives matching statistical bounds, a transformer realization, and a generalization result.

1 Introduction

  • The paper targets the gap between nonparametric ICL theory on Euclidean domains or a single manifold and prediction with unknown, heterogeneous local geometry.The motivating question is whether transformers can still attain optimality in that setting.Source: §1 · p. 2
  • The model allows manifold components to differ in dimension, smoothness, and sampling mass, with geometric scales that may vary with sample size.The regression scale remains locally resolvable.Source: §1 · p. 2

1.1 Contribution

  • The paper establishes an aggregate minimax lower bound and a matching upper bound for an oracle tangent local-polynomial estimator.Its oracle supplies dimension, smoothness, and bandwidth, while the tangent and task function are not supplied.Source: §1.1 · p. 2
  • A structure-informed transformer approximates the estimator with negligible oracle-approximation error, logarithmic depth, and polynomial size.The construction uses geometric preconditioning and chartwise reduced regression.Source: §1.1 · p. 2
  • The paper derives a fresh-task risk bound for near empirical risk minimizers and states that prior guarantees do not uniformly extend to its setting.The related results it contrasts use a single manifold and Hölder exponents in (0, 1].Source: §1.1 · p. 2
  • Appendix C reports performance gains as pretraining meta-sample size increases and compares the transformer with an oracle-tangent local-polynomial estimator.Source: §1.1 · p. 2

2 Problem setup

The setup models noisy observations of latent points drawn from a sample-size-dependent mixture of heterogeneous manifolds. Local separation, regularity, and perturbation restrictions make componentwise regression at the chosen bandwidth feasible.

Mixture geometry

  • Each sample-size-dependent mixture may contain components with different dimensions, smoothness, masses, reach, separation, and perturbation scales.Local chart regularity is uniformly controlled even as reach and separation may shrink.Source: §2 · p. 3, Figure 1 · p. 4

Tasks and observations

  • Observed covariates and responses are noisy versions of latent covariates and task-function values, and prediction targets the latent query response.The latent covariate and response-noise assumptions include bounded perturbations and mean-zero response noise.Source: §2 · p. 3

Feasible local regime

  • The feasible local regime requires enough local samples, prevents other components from entering the regression window, and keeps covariate perturbations below the regression bias scale.The resulting number of components is at most n^(1−κ), with polynomially increasing local counts.Source: §2 · p. 3

Scope

  • The representation map may be fixed and learned, but learning that map is outside the analysis.Source: §2 · p. 4

Identifiability

  • The tubular-noise model may be non-identifiable, but the stated bounds hold uniformly over admissible latent laws defining the target and risk.Different latent/noise pairs can induce the same observed covariate distribution.Source: §2 · p. 4

Reading the scales

  • The bandwidth balances squared approximation bias and response-noise variance using the component effective sample size and local volume scale.Reach stabilizes the local graph, while separation keeps other components out of its fit.Source: §2 · p. 4

3 Minimax rate and oracle estimation

The minimax benchmark aggregates the componentwise difficulty of the heterogeneous mixture, and an oracle tangent local-polynomial estimator attains that benchmark. It estimates local geometry from the prompt before fitting regression in projected coordinates.

3.1 Minimax lower bound

  • The target minimax rate averages component difficulties according to smoothness, dimension, and effective sample size nπk,n.For balanced components with common dimension and smoothness, the rate is (n/Kn)^(−2α/(2α+d)); for Kn ≍ n^η it is n^(−(1−η)2α/(2α+d)) under the geometric assumptions.Source: §3.1 · p. 4
  • Theorem 1 lower-bounds risk by the aggregate benchmark, with one testing construction contributing at each component's own resolution.The bound applies to measurable predictors of the observed prompt.Source: §3.1 · p. 5

3.2 Oracle tangent local-polynomial estimator

  • The oracle supplies the query component's dimension, smoothness, polynomial degrees, and bandwidth, while the estimator fits its tangent and regression coefficients from the prompt.A polynomial graph fit estimates the tangent before regression in projected coordinates.Source: §3.2 · p. 5
  • The estimator averages near-minimizing geometric candidates, spectrally rounds their projectors, and uses ambient localization with projected kernel weights for local polynomial regression.The ambient cutoff prevents projection from hiding large displacements; the fitted intercept estimates the query value.Source: §3.2 · pp. 5–6
  • For smoothness above one, higher-order terms fit local variation while the intercept estimates the function at the query; smoothness at most one reduces to local averaging.Source: §3.2 · p. 6
  • Theorem 2 gives the oracle estimator a matching upper bound Rn, attaining the aggregate minimax benchmark under the stated assumptions.The proof controls regression uniformly over nearby tangent projectors and averages componentwise bounds over the query label.Source: §3.2 · pp. 6–7

4 Transformer realization

The construction encodes geometric selection, tangent estimation, and chartwise regression as internal stages of a fixed-interface transformer. Its approximation error is small enough to preserve the oracle estimator’s statistical rate, using logarithmic depth and polynomial resources.

4 Transformer realization

  • The fixed interface packs each sample and query into rows, preserves raw data and row markers, and clips the scalar readout to [−LF, LF].Extra coordinates store intermediate geometric and regression computations.Source: §4 · p. 7
  • A structural-model-dependent selector uses the query to set the component state, after which geometric summaries produce tangent and chart states and chartwise regression solves local normal equations.A bounded decoder approximates the inverse on well-conditioned inputs; these are stages of one forward pass.Source: §4 · pp. 7–8
  • All coordinate charts avoid discontinuities from choosing one frame globally, while positive-weight charts yield stable coordinates for the same projected covariate and polynomial space.On the regression good event, chartwise fitted intercepts agree with the ambient pseudoinverse intercept.Source: §4 · p. 8
  • Theorem 3 gives a transformer approximation with logarithmic depth and polynomially bounded workspace, FFN width, and parameter bound; its sufficiently accurate implementation preserves the oracle target’s statistical rate.The construction is fixed by the structural model and n; its resource constants depend on A0 and fixed model and construction bounds.Source: §4 · p. 9

5 In-context generalization

The generalization analysis separates the information in each prompt from the number of pretraining tasks. It bounds near empirical-risk minimizers over the architecture class while distinguishing the oracle comparator, class complexity, and optimization tolerance.

5 In-context generalization

  • Tasks share the structural model and sampling law, while n measures information within a task and Γ counts independent training tasks.The target task draws a fresh function and prompt independently of the training tasks.Source: §5 · p. 9
  • Every measurable near ERM in the fixed architecture satisfies the stated generalization bound, with an entropy proxy controlled by the architecture envelope and log(eΓ).The tolerance enters the bound explicitly; its value measures the achieved empirical-risk gap.Source: §5 · p. 9
  • The bound separates in-context error, implementation error, finite-task complexity, and optimization tolerance, using a bounded square-loss oracle inequality and parameter covering of the full softmax class.Conditional mean-zero query noise permits training against the noisy response while evaluating against the latent target.Source: §5 · p. 10
  • The comparator supports a sufficient pretraining sample-complexity bound, but minimax optimality is worst-case over task distributions; a point mass at the zero function has an identically zero-risk predictor.More training tasks can reduce procedure-selection cost, while a new function is still observed through only n examples in its prompt.Source: §5 · p. 10

6 Discussion

The discussion connects a heterogeneous local-difficulty benchmark to a geometry-first estimator and its transformer realization. The accompanying overview separates the predictor’s interface from its internal computation, while related work and a numerical illustration situate the construction.

6 Discussion

  • The benchmark links heterogeneous local difficulty to one geometry-first estimator, realized through higher-order tangent fitting, stable reduced regression, and an architecture-compatible single forward pass.The near-ERM guarantee separates representation from statistical learning.Source: §6 · p. 10

A Construction overview

  • Figure 2 distinguishes the fixed input/output interface from internal computations: uniform softmax attention copies and averages numerical registers, and row-wise ReLU networks compute statistical modules.The displayed sequence has n + 1 rows and polynomially many workspace coordinates, ending in a clipped scalar readout.Source: A Construction overview · p. 14, Figure 2 · p. 14

B Extended related work

  • Prior work covers single-manifold settings or Euclidean local-polynomial ICL; this analysis addresses regression in estimated coordinates across a growing mixture, without uniformly extending all prior guarantees.The cited comparisons differ in perturbation models and structural assumptions.Source: B Extended related work · p. 15

C Numerical illustration

  • The numerical illustration compares a trained softmax workspace predictor with an oracle-tangent local-polynomial estimator across four pretraining budgets and heterogeneous mixture geometry; Appendix C reports gains as the meta-sample grows.The experiment varies pretraining prompts from 100,000 to 1,000,000 and combines heterogeneity in dimension, smoothness, mass, shape, and design density.Source: C Numerical illustration · p. 16

C.1 Data and task generation

The experiment constructs a twelve-component mixture spanning dimensions and smoothness levels, with component-specific geometry, densities, masses, and perturbations. It then trains and evaluates a softmax workspace predictor under a specified pretraining and checkpoint protocol.

C.1 Data and task generation

  • The experiment fixes ambient dimension 64, context size 40,000, and twelve components covering dimensions 2, 4, 6, and 8 and smoothness levels 0.75, 1.5, and 3.Component probabilities determine the expected context counts listed for each dimension–smoothness pair.Source: §C.1 · p. 16
  • Component geometry uses fixed simplex-separated centers and component-specific frames, anisotropy, and density tilt; the resulting volumes, density constants, reach, separation, and latent-point norms are bounded as reported.The reported minimum reach is 0.22938, and the conservative separation lower bound is 1.10143.Source: §C.1 · p. 16
  • Each task independently draws one function per component, shared across all context and query points; functions are deterministically bounded by 0.75, with ridge-knot smoothness classes C0,0.75, C1,0.5, and C2,1.Source: §C.1 · pp. 16–17

C.2 Empirical architecture and optimization

  • The empirical predictor uses four workspace blocks, 32 learned workspace tokens, four attention heads per module, and FFN width 256; its 286,401 parameters define a learned GELU model distinct from the theoretical residual-ReLU construction.A context encoder maps a 130-dimensional vector to width 64, and the readout predicts in [−1, 1].Source: §C.2 · p. 17
  • For each pretraining budget, training starts from scratch, visits the indexed task pool once, and selects the final scheduled checkpoint for testing.Validation uses 96 fixed tasks; increasing Γ changes both the number of distinct prompts and the optimization budget.Source: §C.2 · pp. 17–18

C.3 Geometry-informed local-polynomial benchmark

The geometry-informed LP-CV benchmark fits a local polynomial using query-component structure and a true tangent basis. The test protocol compares it with transformer checkpoints on shared prompts and quantifies test-prompt uncertainty.

C.3 Geometry-informed local-polynomial benchmark

  • LP-CV uses the query component’s dimension, smoothness, mixture mass, and true tangent basis to select local polynomial features and fit context responses.Its bandwidth is tuned separately for each of 12 dimension-smoothness strata using disjoint validation prompts.Source: §C.3 · p. 18
  • The fit uses ℓ1 cutoffs, a pseudoinverse with a relative eigenvalue threshold of 10−8, and a nearest-context fallback when no point has positive weight.The intercept is clipped to [−1, 1], and all context points enter the weight rule and fallback.Source: §C.3 · p. 18

C.4 Test protocol and uncertainty

  • All methods use the same 2,000 test prompts, with latent regression values as targets and noisy query responses used for training and tuning.Transformer and LP-CV risk intervals use percentile bootstrap resampling; paired resamples are used for their risk ratio.Source: §C.4 · p. 18
  • The reported intervals quantify test-task variation conditional on fitted models and selected bandwidths, not training-seed or bandwidth-selection uncertainty.The risk-ratio interval uses the same resampled prompt indices for numerator and denominator.Source: §C.4 · p. 18

C.5 Results and interpretation

Across the tested budgets, transformer test MSE declines and is below LP-CV at the larger budgets; component-wise estimates favor the transformer in all twelve components at Γ = 1,000,000. The appendix also fixes notation and mathematical conventions.

C.5 Results and interpretation

  • At Γ = 1,000,000, transformer MSE is 0.505 × 10−3, 26.75% below LP-CV and 6.10% below the Γ = 500,000 model.Table 1 reports latent-target test MSE in units of 10−3 and risk relative to LP-CV, whose MSE is 0.690 [0.645, 0.739] at every budget.Source: Table 1 · p. 19, §C.5 · p. 19
  • At Γ = 1,000,000, transformer MSE point estimates are lower than LP-CV’s in all twelve components, but component query counts range from 41 to 387 and intervals are absent.Table 2 reports component-wise point estimates and the number of test queries per component.Source: Table 2 · p. 19, §C.5 · p. 19
  • The comparison combines increases in distinct pretraining prompts and optimizer updates; theory concerns a residual-ReLU architecture, while experiments use a workspace architecture and specified task distribution.The comparison illustrates learned prediction at fixed context size and heterogeneous geometry.Source: §C.5 · p. 19

D Mathematical preliminaries

  • The appendix sets conventions for asymptotic notation, polynomial features, matrix norms, localization, and regularity classes, with constants uniform over admissible component sequences unless stated otherwise.It defines operator, Frobenius, and max norms, positive eigenvalue extrema, pseudoinverse, image, and positive-semidefinite matrix ordering.Source: D Mathematical preliminaries · p. 20, §D.1 · p. 20

D.2 Hölder classes and manifolds

The appendix defines regular embedded manifolds through uniformly controlled local charts and specifies Hölder smoothness through derivatives in those charts. Positive reach gives local geometric control, while the auxiliary appendix develops consequences of the geometric assumptions.

D.2 Hölder classes and manifolds

  • The α-Hölder class is defined through continuous bounded derivatives up to order ⌈α⌉−1 and a Hölder condition on derivatives of that order.On manifolds, the class is defined by pulling functions back through tangent-normal charts with uniform regularity.Source: §D.2 · pp. 20, 22
  • The reach is the shortest distance from the manifold to its medial axis, the set where nearest-point projection is not unique; a narrow bottleneck reduces reach.Positive reach is used as a regularity condition for geometric inference.Source: Figure 3 · p. 21, §D.2 · p. 21
  • A regular embedded manifold is locally a graph with controlled smoothness; its tangent and normal spaces, tangent projection, and intrinsic length metric are specified.The regularity definition uses a chart radius and bounds on graph-map regularity that do not depend on reach.Source: §D.2 · p. 21
  • For sufficiently small ρ proportional to the smaller of reach and chart radius, nearby manifold points have intrinsic distance at most twice their Euclidean distance.The local volume comparison is proportional to r^d, with constants depending only on dimension.Source: §D.2 · p. 21

E Auxiliary details

  • Appendix E proves local consequences of positive reach and records consequences of Assumption 3 for effective sample sizes, bandwidths, and component-count growth..Source: E Auxiliary details · p. 22

E.1 Proof of Lemma D.1

The appendix establishes local chart control, fixes uniform constants for the component sequence, and builds auxiliary testing tools used in the minimax lower-bound proof.

E.1 Proof of Lemma D.1

  • The local-geometry proof chooses a radius proportional to the smaller of reach and chart scale, then uses chart regularity and the reach inequality to control nearby points.It also develops volume and distance estimates in tangent-normal coordinates.Source: §E.1 · pp. 22–23

E.2 Constant-explicit version of Assumption 3

  • The constant-explicit assumptions select a uniform localization scale and imply component bandwidths fit within that scale for sufficiently large n.The component perturbations and separations are also bounded relative to the scale margins.Source: §E.2 · p. 24

F.1 Submodel for lower bound

  • The lower-bound submodel sets covariate perturbations to zero and uses symmetric bounded noise while retaining component reach and separation conditions.The construction is presented as a submodel sufficient for proving the lower bound.Source: §F.1 · p. 24

F.2 Auxiliary lemmas

  • The auxiliary lemmas provide a finite bump packing with disjoint supports and bounds linking function separation to observation-law distances.The section invokes an L2 form of Assouad’s lemma and bounds Hellinger distance using L2 function distance.Source: §F.2 · pp. 25–26

F.3 Proof of Theorem 1

  • The proof transfers the Assouad lower bound from the constructed finite family to the original prediction problem.It does so by relating conditional prediction risk to L2 risk under the fixed latent design.Source: §F.3 · p. 31

F.4 Lower bound with independent pretraining tasks

This section shows that the lower bound for the independent-pretraining experiment persists for every number of training tasks and develops the tangent local-polynomial estimator’s upper-bound argument. Supporting results cover polynomial coercivity, perturbation and approximation control, tangent-projector estimation, and uniform regression stability using component-pure windows contained in local charts.

F.4 Lower bound with independent pretraining tasks

  • For every number of independent training tasks, a worst-case task distribution preserves the lower bound, even when the learner is given the underlying distribution and model.The hard prior may depend on sample size but is fixed independently of realized training data; for a fixed task distribution, the lower bound can differ, and a point mass at the zero function has zero latent prediction risk.Source: §F.4 · p. 31

G Tangent local polynomial estimator

  • The upper-bound proof combines local purity, polynomial coercivity and concentration, projector estimation, and a uniform Gram event to derive componentwise and aggregate rates.The Gram event holds uniformly over nearby projectors, so it applies to the estimated projector; a final bias–variance argument combines the relevant controls.Source: G Tangent local polynomial estimator · p. 31

G.1 Standing notation and scale consequences

  • The regression polynomial degree is p_k, while the tangent graph fit uses s_k=p_k+1 to obtain a graph Taylor remainder of order h_k^s_k.The degree choice uses the supplied C^s_k,1 regularity condition.Source: §G.1 · pp. 31–32

G.2 Auxiliary lemmas

  • Uniformly bounded singular values connect ambient and intrinsic polynomial features, while polynomial Gram matrices remain coercive under sufficiently small perturbations.The bounds also hold in an averaged form for perturbation kernels supported on a sufficiently small ball.Source: §G.2 · pp. 35–36
  • For Hölder regression functions, a degree-⌈α⌉−1 polynomial approximates the function locally, and its ambient-feature representation is O(h)-Lipschitz on fixed balls.The approximation is constructed from the Taylor polynomial at zero, with the stated Lipschitz property for the ambient polynomial representation.Source: §G.2 · pp. 35–36
  • For bounded perturbations b and e, the loss-induced discrepancy satisfies ∥Fb,e(t) − F0(t)∥ ≤ C(∥b∥ + ∥e∥).The uniform bound follows from a bounded Jacobian on a fixed Euclidean ball.Source: §G.2 · p. 37

G.3 Tangent projector estimation

  • The tangent-projector argument obtains a spectral gap of at least 3/4 and applies the Davis–Kahan sin-Θ theorem [38, Theorem 1] to bound projector error.The argument uses local window conditions and a tangent-estimation event; the stated bound is obtained after expanding ϵtan.Source: §G.3 · pp. 38, 41

G.4 Regression stability

  • Under the standing assumptions, Assumption 3, and window condition (23), Lemma G.6 establishes uniform regression stability on an event Ereg.The regression window contains only observations from component k and lies within the local chart at x⋆.Source: §G.4 · pp. 41–42

G.5 Proof of Theorem 2

This section closes the proof of Theorem 2 by developing transformer-approximation components and uniform error controls, including approximation and compilation primitives, a weighted-sum readout, and structural geometric summaries. It also establishes coverage of perturbed non-PSD matrices and eigenvalues outside [0, 1], and gives conditions for normalized weights and admissible charts.

G.5 Proof of Theorem 2

  • The proof combines deterministic and stochastic error controls and averages over the query component, with little-o bounds uniform over components, admissible models, and conditioned query values.The asymptotic conclusion holds uniformly once the feasible-scale assumptions are satisfied.Source: §G.5 · pp. 45, 47

H Transformer approximation

  • The transformer construction compiles row-wise ReLU networks and attention-based copying and averaging, with polynomially many coordinates for intermediate states and structural parameters independent of task functions and prompts.The prompt supplies only the sample pairs and query covariate.Source: H Transformer approximation · p. 47

H.1 Architecture-compatible approximation primitives

  • Fixed-dimensional Lipschitz maps admit ReLU approximants with logarithmic depth and polynomial width and parameter magnitudes, while row-wise ReLU networks compile exactly into residual transformer blocks.Copying or averaging bounded vectors can be inserted with one active attention head per operation.Source: §H.1 · pp. 47–49

H.2 Embedding and readout maps

  • The readout approximates the clipped exact weighted sum uniformly within n^-Eread, using logarithmic depth, polynomial size, and fixed parameters.The multiplication map is applied to clipped chart weights and predictions.Source: §H.2 · p. 49

H.3 Structural selection and geometric summaries

  • Under Assumptions 1–3, exact structural selection on the query support uses O(log n) depth, polynomial width, and polynomially bounded parameters.The construction also gives polynomial bounds for grid size and a polynomial Lipschitz bound for the averaged tangent projector; spectral decoding and safe chart maps are bounded and Lipschitz on their specified domains.Source: §H.3 · pp. 50–51

G.5 Proof of Theorem 2

  • Approximation (39) also covers perturbed non-PSD matrices and eigenvalues outside [0, 1], with decoder inputs clipped to the chosen cube.Source: §H.3 · p. 51
  • For an exact rank-d orthogonal projector, the denominator in (39) is at least one, so the weights sum to one.Source: §H.3 · p. 51
  • For charts with J(P) > 0, λmin(A_J(P)) ≥ det A_J(P) > τ_d.Source: §H.3 · p. 51
  • The chart construction distinguishes dimension-compatible branches and requires orthonormal coordinates and an invertible regression Gram matrix.Source: §H.3 · p. 51

H.4 Implementation of the geometric block

The geometric block forms query-local chart coordinates and weights through averaged moments and decoded projectors. The regression decoder aggregates chartwise polynomial statistics and returns a bounded prediction, including on inputs where some branches are singular.

H.4 Implementation of the geometric block

  • The implementation uses logarithmic depth, fixed head count, and polynomially bounded dimensions and parameter magnitudes.The stated geometric-block output bounds include 0 ≤ ωj,x ≤ 1, ∥ui,j(x)∥∞ ≤ Ru,n, and 0 ≤ Wi,j(x) ≤ RW,n.Source: §H.4 · p. 52
  • Query-local features are averaged into moments, which are decoded into projectors and safe chart states before chart coordinates and weights are produced.The construction uses the query and bandwidth to form localized row features and selects dimension- and degree-specific outputs.Source: §H.4 · p. 52

H.5 Globally defined regression decoder

  • Each chart aggregates weighted polynomial regression statistics, then applies a globally defined decoder that clips its output to [−LF, LF].The inverse is evaluated on well-conditioned branches; the decoder remains defined on singular inputs as well.Source: §H.5 · p. 53
  • Compact localization acts through computed value coordinates before uniform-softmax averaging, with approximate contributions controlled by module-error bounds.Every attention probability is positive, but the ideal localized value is zero outside the cutoff.Source: §H.5 · p. 53

H.6 Model size and error propagation

This section controls end-to-end approximation error while making the accuracy–resource tradeoff explicit, and develops an entropy-based route to in-context generalization for bounded transformer classes. It gives an entropy bound for the end-to-end architecture with polynomial dependence on n and logarithmic dependence on Γ, with constants uniform over the listed model quantities.

H.6 Model size and error propagation

  • The compiled transformer uses polynomially bounded module domains and widths, with a fixed number of stages and logarithmic depth.Communication acts on logical registers under a deterministic polynomial envelope, and propagated module error can be made O(n^-A0/2).Source: §H.6 · p. 54

H.7 End-to-end approximation

  • The end-to-end approximation argument controls geometric and regression failures with probability O(n^-A0), uniformly over the stated distributions and functions.The regression stability condition is required on positive-weight charts; clipped predictions bound error on the failure event.Source: §H.7 · p. 55, §H.8 · p. 56

H.8 Proof of Theorem 3

  • For every fixed A0 > 0, the constructed predictor has squared error O(n^-A0) uniformly over the stated model class.The same parameter vector works across the allowed distributions and regression functions, independently of the prompt.Source: §H.8 · p. 56

H.9 Explicit dependence on the approximation exponent

  • For each fixed A0, inverse-polynomial accuracy is achievable with logarithmic depth and resource exponents or depth constants affine in A0.The construction uses a fixed number of chart branches and nonlinear stages; its polynomial workspace exponents may depend on ambient dimension.Source: §H.6 · p. 54, §H.9 · pp. 56–57

I In-context generalization

  • The appendix bounds the full bounded-parameter softmax transformer class’s covering number, then applies a bounded square-loss oracle inequality to near empirical-risk minimizers.The resulting entropy term is polynomial in n and logarithmic in the number of training tasks Γ.Source: I In-context generalization · p. 57

I.1 Covering number and entropy bound

  • Under the polynomial architecture envelope, the bounded softmax transformer class admits a polynomial entropy bound, with depth O(log n) and uniform bounds over its parameter cube.The sensitivity argument allows query and key matrices to vary freely, and the net covers the image of the full parameter cube.Source: §I.1 · pp. 57, 59

I.2 End-to-end class and entropy proxy

  • The end-to-end class uses a fixed embedding and readout, with the readout truncating every predictor to [−LF, LF].Under the bounded-response condition, the observed responses are bounded by LF + Bϵ almost surely.Source: §I.2 · p. 59
  • Theorem 3’s end-to-end architecture admits an entropy bound scaling as n^c(1 + log(eΓ)), with constants uniform in n, K_n, Γ, P, ρ_f, and f.The constants may additionally depend on A_0, the fixed head count, and the polynomial architecture exponents.Source: §I.2 · p. 60

I.3 Empirical process bound

This appendix develops bounded least-squares empirical-process and near-ERM bounds, then applies them to the end-to-end predictor and states a sufficient regime for Theorem 4 and Corollary 1.

I.3 Empirical process bound

  • Lemma I.2 formulates a bounded least-squares empirical-process result for i.i.d. samples with bounded responses and bounded prediction classes.Source: §I.3 · p. 60
  • The near-ERM oracle inequality is uniform in n, K_n, Γ, P, and ρ_f, with C depending only on B_Y, L_F, and fixed construction constants.The lemma assumes bounded responses and a condition on fresh query-response noise.Source: §I.3 · p. 61
  • Theorem I.1 applies under Theorem 3's hypotheses to a class containing the constructed end-to-end predictor, with the specified model and function-class assumptions.Source: §I.3 · p. 62

I.4 Proofs of Theorem 4 and Corollary 1

  • Theorem 4 follows from Theorem I.1 and Corollary I.1, with the conditional mean-zero query-noise condition following from the i.i.d. task construction and Assumption 2.Source: §I.4 · p. 63
  • A fixed A0≥λmax is sufficient, and when εopt,Γ ≲ R_n the stated task-count regime is Γ0≤n^C log(en).Source: §I.4 · p. 63

Related papers

Loading 2609.31458v1…