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

会议: NeurIPS2026（Accepted）
arXiv: 2609.31458
代码: https://github.com/seojaehee02/nonparametric_ICL
领域: 学习理论
关键词: 上下文学习、非参数回归、流形混合、极小极大最优性、局部几何适应

一句话总结¶

本文给出复杂度随样本量增长的异质流形混合上的非参数上下文学习极小极大率，并证明结构知情 Transformer 能逼近达到该率的切空间局部多项式估计器；实际训练模型的最优性仍需要足够任务数和足够小的经验风险优化间隙。

研究背景与动机¶

非参数上下文学习（in-context learning，ICL）把一个 prompt 看成新任务的回归样本：模型读入带标签的上下文和无标签查询，在不更新参数的前向过程中估计新函数。已有理论已经解释了欧氏空间上的局部多项式回归，以及单一流形上的核式预测，但真实表示可能由不同内在维度、平滑度和概率质量的区域组成。只用环境维度或一个最大内在维度描述误差，会丢失“查询多常进入该区域”和“该区域究竟有多少上下文样本”这两个因素。

进一步的难点不是简单叠加几个固定流形。本文允许分量数量增加、混合质量变小、reach 和分量间距收缩，因此要同时控制局部窗口是否混入其他分量、估计坐标是否稳定，以及高阶回归能否继续利用函数平滑性。低阶核平均不足以处理任意正平滑度，而先估切空间再回归又会引入数据依赖的坐标误差。与此同时，证明 Transformer 可以表达估计器，并不等于证明 SGD 能找到它。

核心 idea：在局部几何仍可分辨的尺度条件下，先估计高阶局部几何，再在稳定切空间坐标中回归，把各分量的统计难度按查询概率加权，并将表达、跨任务泛化和优化误差分别计账。

方法详解¶

整体框架¶

输入是一个任务的带噪数值协变量和响应，以及带噪查询协变量；目标是生成查询的潜在点上的函数值，而不是查询的带噪标签。任务之间共享结构环境和采样规律，但各自抽取新的回归函数。本文依次建立聚合下界、达到下界的统计估计器、实现该估计器的 Transformer comparator，以及从有限预训练任务选择预测器的条件性风险上界。

这里的“oracle”需要分清两种信息。Algorithm 1 获得查询分量的内在维度、平滑度和带宽，但不直接获得切空间或函数；它从上下文协变量拟合切空间。Theorem 3 的 comparator 则使用指定结构模型，把流形相关的分量选择器、参数和候选网格编码到权重中，查询决定使用哪一组状态。其参数在采样 prompt 之前固定，跨函数共享，但可以随结构环境改变。

所以，局部几何适应是“在结构知情的构造中，对当前 prompt 的切空间和回归系数进行估计”，不是对完全未知环境、未知平滑度和未知混合质量的无先验适应性保证。本文核心是统计与表达能力分析，以下按证明对象解释，不把证明链条画成实际训练网络结构。

关键设计¶

1. 聚合局部难度：同时保留维度、平滑度和稀有程度

对查询所在的第 \(k\) 个分量，上下文中预期属于该分量的样本数是 \(N_k=n\pi_{k,n}\)，真正落入局部窗口的数量则只有 \(N_kh_k^{d_k}\)。带宽取 \(h_k=N_k^{-1/(2\alpha_k+d_k)}\)，使平方偏差与响应噪声方差同阶。聚合风险基准为

\[ \mathfrak{R}_n=\sum_{k=1}^{K_n}\pi_{k,n}(n\pi_{k,n})^{-2\alpha_k/(2\alpha_k+d_k)}. \]

小质量分量的条件回归更难，但查询也更少进入它。这个加权和同时保留两种效应，不能把“稀有”简单等同于“主导整体风险”。平衡且同质的混合退化为 \((n/K_n)^{-2\alpha/(2\alpha+d)}\)；当 \(K_n\asymp n^\eta\) 时，变为 \(n^{-(1-\eta)2\alpha/(2\alpha+d)}\)，但只适用于满足几何条件的序列，并要求 \(\eta\leq1-\kappa\)。

Assumption 3 把“增长但仍可处理”具体化。设 \(r_n=\max_k h_k\)，要求所有分量的有效样本量多项式增长，reach 和间距大于局部回归尺度，协变量扰动小于相应偏差尺度：

\[ N_k\geq n^\kappa,\qquad \tau_{0,n}\wedge\delta_{0,n}\geq a_{\rm sc}^{-1}r_n,\qquad \sigma_{k,n}\leq a_{\rm sc}h_k^{\alpha_k\vee1}. \]

其中 \(a_{\rm sc}\) 是依赖固定模型界的足够小常数，\(\kappa\in(0,1)\)。这排除了上下文中几乎看不到的极稀有分量，且推出 \(K_n\leq n^{1-\kappa}\)。局部图的导数界和图半径保持统一，允许缩小的是全局 reach、间距等尺度；不是任意几何退化都在结论内。

下界证明在每个分量自己的分辨率上放置不相交的小 bump，把所有分量装进同一个 Assouad 家族。采用零协变量扰动和合法的有界平滑响应噪声子模型，Hellinger 平移控制让相邻函数仍难以区分。关键是一次测试论证同时累加各分量贡献，而不是分别得到下界后擅自相加。

2. 高阶几何拟合：让坐标误差不破坏回归平滑性收益

对查询 \(x\)，先把位移缩放成 \(z_i=(X_i-x)/h_x\)。候选包含查询法向偏移、秩为查询维度的正交投影，以及描述局部曲面的高阶张量；在确定性的 \(n^{-1}\) 网格上评估局部图残差。几何拟合次数是 \(s_x=\lceil\alpha_x\rceil\)，回归次数是 \(p_x=\lceil\alpha_x\rceil-1\)，前者多一阶，因为缩放曲面图并除以带宽后，需把余项控制在相应回归分辨率内。

拟合只使用协变量。损失在环境空间的局部窗口内计算，对距最小损失小于 \(\Delta_{{\rm tan},n}=n^{-3}\) 的候选赋非负截断权重，归一化后平均其投影。平均结果未必仍是正交投影，所以再取前 \(d_x\) 个特征方向进行谱舍入；良好事件上的固定谱间隙使这一步稳定。候选网格大小对固定环境维度和阶数是样本量的多项式，但指数含环境维度，不能据此宣称高维计算便宜。

随后在估计投影下构造局部多项式特征。权重同时包含环境位移截断和投影位移核：前者避免远处点投影后“看起来很近”，在分离条件下保证单分量窗口；后者对窗口内部的局部位置平滑降权。加权正规方程的截距给出查询预测，最后裁剪到函数值界内。环境多项式在低维切空间上会冗余，因此用伪逆而不是假定环境 Gram 矩阵可逆；可识别多项式子空间上的正谱界足以确定截距。

令 \(\delta_x\) 是估计投影与生成潜在查询点处真实切空间投影的算子范数差。条件均方误差的关键传播关系是

\[ \mathbb{E}\bigl[(\widehat f_{\rm plug}^{\Pi}(x)-f(x^\star))^2\mid k,x^\star,\xi_{n+1}\bigr]\lesssim h_k^{2\alpha_k}+h_k^2\mathbb{E}[\delta_x^2\mid k,x^\star,\xi_{n+1}]+\sigma_{k,n}^2+\frac{1}{N_kh_k^{d_k}}. \]

为什么切空间估计中的对数代价不必污染最终统计率？比较多项式在归一化坐标中的 Lipschitz 常数带有一个带宽因子，因此坐标误差进入回归时被乘以带宽，平方后出现 \(h_k^2\mathbb E\delta_x^2\)。局部样本增长与扰动条件吸收这些项。证明还建立对真实投影邻域内所有投影统一成立的 Gram 事件，解决同一协变量既用于估几何又用于回归的依赖；响应噪声则可在给定这些协变量后分析。

3. 结构知情编译：用稳定坐标图和数值工作区实现估计器

理论 Transformer 的固定仿射输入接口用 \(n+1\) 行保存样本与查询，保护原始数据和行类型标记，额外坐标用作数值寄存器。结构选择器根据查询确定维度、阶数、带宽和质量归一化因子；局部图损失可由固定维度的加权多项式矩计算，因此不必对每个候选重新遍历全部样本。

通信使用均匀 softmax：把 query/key 置零，通过二元标记门控 value，再确定性缩放，实现精确查询广播与样本平均。局部化来自 FFN 计算的 value 截断，不来自 softmax 概率严格变成零。逐行 ReLU 算术模块完成候选比较、谱解码和多项式统计，再用两组多项式宽度的 scratch banks 编译到残差块中；一个头可以传整个寄存器向量，因此头数保持常数。

单个切空间不存在可全局连续选择的坐标基，于是构造使用多张坐标图。行列式阈值只给条件良好的图正权重；这些图都是同一投影子空间的正交坐标描述。约化回归字典大小由内在维度和回归阶数决定，各正权重图在良好事件上给出与环境伪逆相同的截距，所以图间平均没有改变目标估计器。按分量质量缩放 Gram 和响应向量，能维持固定正谱下界，而且该公共比例在求解时相消。

谱映射和逆矩阵解码器都全局有定义且有界，但只在良好谱域上承诺近似准确。零权重图即使矩阵奇异也只返回有界值，近似权重的微小泄漏由裁剪控制。对任意固定 \(A_0>0\)，Theorem 3 给出相对统计估计器的均方逼近误差 \(O(n^{-A_0})\)，深度 \(O(\log n)\)，宽度、工作区和参数幅度为多项式。精度提高会增大资源指数，几何部分仍保留环境维度成本。

这个结果是 comparator 的存在性构造。权重含结构模型知识，而不是从任意训练样本通过 SGD 学得该选择器的证明；一套权重统一适用于该环境内的任务函数和合法密度、扰动规律，不是统一适用于所有未知几何环境的一套权重。

4. 近经验风险最小化：把跨任务学习与任务内信息分开

预训练从同一结构环境抽取 \(\Gamma\) 个独立任务，每个任务提供一个含 \(n\) 个例子的 prompt 和查询响应；测试重新抽取函数。\(n\) 决定新函数在当前 prompt 中可被观察多少，\(\Gamma\) 决定选择一个上下文预测程序的跨任务统计代价。覆盖数分析针对有界参数的整个 softmax 类，query/key 参数可自由变化，并非只针对构造时使用均匀注意力的特殊权重。

若训练输出的经验风险与该类中的最小值之间不超过确定容差 \(\varepsilon_{{\rm opt},\Gamma}\)，Theorem 4 给出

\[ \mathbb{E}_{\mathcal D_\Gamma^{\rm tr}}R_{P,\rho_f}^{\star}(\widehat g_\Gamma)\lesssim\mathfrak{R}_n+n^{-A_0}+\frac{\mathfrak H_{n,\Gamma}^{\rm end}+1}{\Gamma}+\varepsilon_{{\rm opt},\Gamma}. \]

这里四项依次是任务内不可消除的统计误差、实现误差、有限任务复杂度和优化间隙；熵代理至多为 \(C_{\rm ent}n^{c_{\rm ent}}\{1+\log(e\Gamma)\}\)。Corollary 1 的充分条件是 \(A_0\geq2\alpha_{\max}/(2\alpha_{\max}+1)\)、\(\Gamma\gtrsim n^{c_{\rm ent}}\log(en)\mathfrak R_n^{-1}\)，以及 \(\varepsilon_{{\rm opt},\Gamma}\lesssim\mathfrak R_n\)。这些条件不是紧的必要任务量，也没有说明 AdamW 或 SGD 必然达到该容差。

相应下界对任意预训练预算成立，但量词是对任务分布取最坏情况：困难先验为每个新任务抽取独立函数索引，预训练不能补回当前函数缺失的标签。不能解释成所有任务分布都存在同样的误差下限；例如恒为零函数的任务分布有零潜在风险。

损失函数 / 训练策略¶

理论训练目标是查询带噪响应的平方损失，而风险目标是潜在函数值。条件均值为零的查询噪声令两者相差一个与预测器无关的噪声方差：

\[ R_Y(g)=R_{P,\rho_f}^{\star}(g)+\mathbb E\epsilon_{n+1}^2. \]

这允许用可观察标签训练，却不把不可约响应噪声误计入潜在预测误差。潜在查询点是数据生成中的点，未必等于观测查询在流形上的最近投影；论文不把有管状噪声的模型认定为普遍可识别。

实际实验使用 width 64、4 个 workspace blocks、每模块 4 头、32 个学习 workspace tokens、FFN width 256，共 286,401 个参数。每块是 workspace-to-context cross-attention、workspace self-attention 和 GELU FFN，禁用 LayerNorm/dropout，第一 workspace token 经仿射与 tanh 输出；不是理论的固定仿射接口、残差 ReLU 编译类。

各预算从头训练，seed 0，遍历任务池一次；25 个单 prompt 微批次累积为 batch 25。AdamW 初始学习率 \(3\times10^{-4}\)、weight decay \(10^{-4}\)、cosine 降至零、梯度范数裁剪 1；最终 checkpoint 用于测试。预算 100,000、200,000、500,000、1,000,000 对应 4,000、8,000、20,000、40,000 次更新，增加任务数也增加优化量，实验不能独立识别二者贡献。

实验关键数据¶

主实验¶

Appendix C 固定环境维度 64、上下文量 40,000、12 个分量，维度为 2/4/6/8，平滑度为 0.75/1.5/3。混合质量在 0.02–0.20，预期分量上下文数量为 800–8,000；椭球形状和采样密度均异质。协变量噪声半径按 \(h_k^{\alpha_k\vee1}/n\) 设置，响应噪声方差为 0.01；测试评估无噪潜在值。

LP-CV 基线获得查询分量的维度、平滑度、质量和真实潜在查询切空间，对每个分层单独验证带宽；它不是 Algorithm 1 的估计切空间 oracle。带宽倍率网格为 2/4/6/8/10/12/16/24，使用 1,200 个独立调参 prompts；所有方法共用 2,000 个测试 prompts。

下表 MSE 单位均为 \(10^{-3}\)；方括号为 95% percentile-bootstrap 区间。LP-CV 在每个预算均为 0.690 [0.645, 0.739]。

预训练任务数	Workspace MSE	Transformer / LP-CV	优化更新数
100,000	14.455 [13.619, 15.342]	20.948 [19.177, 22.776]	4,000
200,000	0.919 [0.849, 0.995]	1.332 [1.222, 1.461]	8,000
500,000	0.538 [0.503, 0.575]	0.780 [0.727, 0.837]	20,000
1,000,000	0.505 [0.472, 0.540]	0.733 [0.686, 0.782]	40,000

消融实验¶

本文没有模块移除消融；下面保留分量分析，不伪装为机制归因。预算为 1,000,000，MSE 单位仍为 \(10^{-3}\)，比值按未舍入值计算。

内在维度	平滑度	测试查询数	LP-CV MSE	Transformer MSE	比值
2	0.75	41	0.606	0.448	0.739
2	1.5	60	0.376	0.310	0.825
2	3	97	0.545	0.480	0.880
4	0.75	72	0.435	0.371	0.853
4	1.5	106	0.632	0.538	0.851
4	3	217	0.845	0.418	0.495
6	0.75	117	0.692	0.474	0.684
6	1.5	175	0.882	0.404	0.458
6	3	317	0.605	0.546	0.903
8	0.75	159	0.667	0.515	0.772
8	1.5	252	0.648	0.433	0.667
8	3	387	0.780	0.679	0.871

理论结果与实验的解释边界也可直接对照：

结论对象	已建立的结果	不能由此推出
所有可测 prompt 预测器	异质 Assouad 家族上的聚合下界	每个固定任务分布都同样困难
结构参数已知的统计估计器	估计切空间后仍达到聚合上界	维度、平滑度和质量完全未知也自动适应
结构知情 ReLU Transformer comparator	逆多项式均方逼近、对数深度和多项式资源	固定小网络能廉价完成该几何搜索
全有界参数类的 near ERM	统计、实现、任务量和优化四项风险界	SGD/AdamW 收敛到全类 near ERM
训练的 GELU workspace 模型	固定任务族上随联合预算增加而改善	已实证验证增长分量复杂度的渐近极小极大率

关键发现¶

在 500,000 个任务时，原文报告相对 LP-CV 降低 MSE 21.98%，相对 200,000 预算模型降低 41.45%；对应配对比值区间低于 1。
1,000,000 预算相对 LP-CV 降低 26.75%，相对 500,000 预算降低 6.10%。百分比和比值采用原文未舍入计算，不能由表中三位小数要求精确重算一致。
12 个分量的点估计均优于 LP-CV，但各分量只有 41–387 个查询，未报告分量置信区间，因此不能声称每个分量均有显著提升。
5,000 次 bootstrap 只描述固定 seed 0 模型和已选带宽下的测试 prompt 不确定性，不包括训练 seed 或带宽选择不确定性。固定上下文量、固定 12 分量的实验也没有检验随样本量增长的几何序列。

亮点与洞察¶

正确区分条件难度与总体难度。 有效样本量下降和查询概率下降同时进入基准，适合分析混合环境中的长尾区域，而不是仅用最坏维度描述整个任务。
几何误差传播比几何误差本身更关键。 带宽平方抑制切空间误差中的随机项，解释了为什么估计坐标仍可保留高阶平滑收益；这是比“切空间估计一致”更强的机制说明。
奇异不等于不可预测。 环境特征冗余产生零特征值，但截距仍在可识别子空间。多图约化求解把这种统计可识别性转换为稳定网络实现。
表达能力与训练成功分账。 Comparator、类容量、near-ERM 间隙各有独立角色，避免把一个可表达的最优统计程序误写成已经被常规训练自动学会。

局限与展望¶

结构选择器编码了几何及分量参数，未知平滑度、质量和环境迁移下的真正自适应仍未解决；前端表示学习也不在分析范围内。
极稀有分量、距离小于回归分辨率的分量以及过大协变量扰动被可行尺度条件排除，不能把结果外推到交叉流形或任意噪声。
工作区多项式资源的指数依赖环境维度和阶数，理论构造未提供实用的高维搜索或锐利资源复杂度保证。
实验明确未认证在上下文量 40,000 时 Assumption 3 的全部有限样本常数条件，经验模型也不是被证明的编译类。
单 seed、合成固定几何、任务量和更新量同步增加，限制了经验结论；后续应分别扫描上下文量、增长分量数和优化预算，并加入训练重复和真正的模块消融。

评分¶

新颖性: 4/5。聚合异质困难度与增长几何条件、估计坐标高阶回归的统一分析有清楚增量。
实验充分度: 4/5。协议、比较和测试不确定性完整，但固定几何与单 seed 不能验证渐近或优化保证。
写作质量: 4/5。结构信息、理论与经验架构及量词边界交代明确，构造附录较为繁复。
价值: 4/5。提供理解局部几何 ICL 的统计框架，比现阶段直接指导大模型训练更有理论价值。