技术摘要：可实现性约束下的适应性

问题陈述

本文研究了在函数族的一致逼近背景下，**上下文学习（ICL）与代理学习（Agentic Learning）**的理论极限。核心问题是：在何种情况下，与任务的顺序适应性交互比固定、预定义的查询提供真正的优势？当学习机制受到可实现性约束（具体而言，通过有界大小的 ReLU 神经网络实现）时，这种优势如何变化？

作者形式化了两个比较维度：

1. 查询策略：固定查询（上下文）vs. 适应性查询（代理）。
2. 表示约束：一般函数（无限制）vs. ReLU 可实现函数（由有界大小的 ReLU 网络实现）。

由此产生四个不同的机制：

• ICG：一般上下文学习。
• AG：一般代理学习。
• ICR：ReLU 可实现的上下文学习。
• AR：ReLU 可实现的代理学习。

目标是刻画在这些机制下，在样本和计算预算相等的情况下，各机制相对于彼此的逼近能力。

方法论

作者在紧集域 $X \subseteq \mathbb{R}^d$ 上采用一致逼近框架。他们定义了一个任务族 $\mathcal{T}$，并通过最坏情况下的均匀误差（$L_\infty$ 范数）来衡量性能。

定义

• 上下文学习者（$\Psi_{IC}$）：使用一组固定的 $N$ 个查询点 $x_1, \dots, x_N$，以及一个将上下文 $C_N = \{(x_i, f(x_i))\}$ 和新输入 $x$ 映射到预测值的预测器。
• 代理学习者（$\Psi_{A}$）：顺序选择查询点。第 $n$ 个查询 $x_n$ 由基于先前上下文 $C_{n-1}$ 的映射 $q_n$ 确定。
• 可实现性：如果学习者的查询映射和最终预测器均由具有有界权重数量（$m$）的 ReLU 神经网络实现，则称该学习者是“可实现的”。

比较指标

本文定义关系 $R_1 \leq R_2$，如果对于每个任务族和预算，机制 $R_2$ 的最坏情况误差不大于机制 $R_1$ 的误差。严格不等式（$R_1 < R_2$）表示严格优势。

作者确立了基线单调性：
$$ICG \leq AG \quad \text{且} \quad ICR \leq AR$$
这是因为代理总是可以选择忽略适应性并模仿固定查询策略。核心贡献在于确定这些不等式何时是严格的，以及可实现性如何改变它们。

主要贡献与结果

本文分离出四种不同的逼近场景，每种场景均由显式构造的任务族证明。这些场景揭示了适应性与表示约束之间的相互作用并非微不足道。

1. 适应性揭示更多信息（优势在可实现性下依然存在）

• 任务族：立方路径任务（$\mathcal{T}^{path}_{d,L}$）。任务由嵌套的二分立方体序列定义。
• 机制：适应性代理可以执行二分搜索（在一维中）或广义搜索，以逐层识别隐藏的立方体路径。
• 结果：
  • 一般情况：$ICG < AG$。固定查询会错过适应性查询可以顺序揭示的信息。
  • 可实现情况：$ICR < AR$。适应性策略（查询子立方体的中心并使用残差）可以精确地由 ReLU 网络实现。
• 推论：在此场景中，适应性的信息论优势对 ReLU 网络的约束具有鲁棒性。

2. 可实现性产生适应性优势

• 任务族：尖点值族（$\mathcal{T}^{val}_{N,m}$）。任务由位于已知位置并携带系数的固定“帽子”组成，以及一个位于位置 $q^*$ 并携带值 $g_m(s)$ 的“移动帽子”，其中 $g_m$ 是一个难以逼近的函数。
• 机制：
  • 一般情况：$ICG = AG$。固定和适应性学习者都可以从上下文中读取位置$q^*$，然后计算$g_m(s)$（因为它们是无限制的）。
  • 可实现情况：$ICR < AR$。ReLU 上下文学习者必须在内部逼近难以处理的映射 $s \mapsto g_m(s)$，这在有界权重下是不可能的。然而，ReLU 代理可以直接在位置 $q^*$（它是通过适应性确定的）查询值 $g_m(s)$，从而绕过内部计算的需求。
• 推论：可实现性约束可以创造一种场景，即使在没有约束的设置中适应性没有优势，在此场景下适应性也严格优越。

3. 可实现性消除适应性优势

• 任务族：地址尖峰族（$\mathcal{T}^{addr}_{N,m}$）。类似于尖点值族，但移动帽子的位置 $q^*(s)$ 由一个难以逼近的函数 $g_m(s)$ 决定。隐藏位 $\beta$ 位于 $q^*(s)$。
• 机制：
  • 一般情况：$ICG < AG$。无限制代理可以从静态系数计算$q^*(s)$ 并查询隐藏位。
  • 可实现情况：$ICR = AR$。为了找到信息丰富的查询点$q^(s)$，代理必须逼近难以处理的映射$s \mapsto q^(s)$。由于代理的查询映射也受限于具有有界权重的 ReLU 网络，它无法比上下文学习者更好地计算位置。确定在哪里查询所需的“困难计算”抵消了适应性的好处。
• 推论：表示约束可以消除一般设置中存在的适应性优势。

4. 无优势

• 场景：对于单例任务族或特定的平凡情况，适应性不会产生改进（$ICG = AG$且$ICR = AR$）。

意义与主张

本文声称提供了关于适应性如何与架构约束相互作用的概念性分类。其主要意义在于证明：

1. 适应性并非普遍优越：其优势取决于任务族的具体结构和学习者的计算能力。
2. 可实现性是一个关键变量：从无限制到 ReLU 可实现设置的转变不仅仅是性能缩放；它定性改变了上下文学习与代理学习之间的关系。
   • 优势可以幸存（立方路径）。
   • 优势可以涌现（尖点值）。
   • 优势可以消失（地址尖峰）。

作者强调，这些结果源自最坏情况下的均匀逼近理论，隔离了信息获取和表示能力的核心现象，而不依赖于统计假设或噪声模型。他们进一步指出，他们的结果可以通过从 ReLU MLP 的标准转换扩展到 Transformer 架构，表明这些理论限制同样适用于现代大型语言模型。

该工作扩展了关于 MLP 非适应性逼近的经典结果，论证了信息获取的结构（适应性）在确定学习极限方面，与函数类复杂度一样起着核心作用。