📐 学习理论¶

🧪 ICML2026 · 45 篇论文解读

📌 同领域跨会议浏览： 🔬 ICLR2026 (294) · 🤖 AAAI2026 (3) · 🧠 NeurIPS2025 (25) · 🧪 ICML2025 (16)

🔥 高频主题： 对抗鲁棒 ×5

A Perturbation Approach to Unconstrained Linear Bandits: 本文重新审视 Abernethy 等人的扰动式 bandit linear optimization 思路，提出 PABLO 归约，把无约束线性 bandit 转成可调用任意 OLO 子程序的问题，并由此得到 comparator-adaptive 静态/动态 regret、高概率界以及若干下界讨论。
Active Learning with Low-Rank Structure for Data Selection: 针对"现有 coreset 数据选择假设数据有几何聚类结构、但很多现代数据集其实是全局代数（低秩）结构"的错配，本文提出基于低秩近似 + 残差敏感度采样的数据选择框架，用一个 \(\tilde{O}(k+1/\varepsilon^2)\) 大小的加权子集把全量平均损失逼近到 \((1\pm\varepsilon)\) 相对误差（外加正比于最优 rank-\(k\) 近似代价 \(\Phi_k\) 的可加项），在表格数据和 Llama3-8B / Qwen2.5-3B 微调上都优于均匀采样与聚类敏感度采样。
AI4SLT: Empirical Processes in Lean 4 for Formal Statistical Learning Theory: 这篇工作把"基于经验过程的统计学习理论（SLT）"第一次系统地在 Lean 4 里从零形式化：补齐了 Mathlib 缺失的高斯 Lipschitz 集中、Dudley 熵积分定理、以及最小二乘（含 \(\ell_1\) 约束）回归的尖锐速率，约 3 万行 Lean 代码、无 sorry/axiom，并且全程用"人定证明策略、AI（Claude Code + Opus-4.5）写战术证明"的人机协作完成。
Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy: 这篇理论文回答两个长期悬而未决的问题：在高维下高斯机制是不是加性噪声差分隐私的最优选择（答：当维度 \(T\to\infty\) 时，在固定均方误差下没有任何加性噪声能渐近超过高斯），以及在低维下有没有比高斯和 \(\ell_2\) 机制都更好的机制（答：有——作者提出三参数的 Spherical Generalized Gamma 噪声族，在某些低维设置下 MSE 比两者都低最多 15%，并给出它们的紧致组合，顺带解决了 Joseph et al. 关于 \(\ell_2\) 机制的一个 open question）。
Bandit Social Learning with Exploration Episodes: 本文研究"每个自私 agent 控制一小段连续决策（episode）"的老虎机式社会学习动态，证明即便 agent 在自己的 episode 内会自发探索，聚合层面的探索仍会失败——对任意 episode 长度 \(m\geq 2\)、任意聚合效用函数 \(f\)（sum/max/min 等），学习失败都以正概率发生，导致贝叶斯遗憾随时间线性增长。
Catastrophic Forgetting is Low-Rank: A Function-Space Theory for Continual Adaptation: 不再把灾难性遗忘当成"参数漂移"，而是在 NTK 体系下给出函数空间的闭式刻画：新任务训练通过跨任务核 \(K_{AB}\) 把旧任务预测拽偏，且这个"遗忘向量"在训练前就能精确预测，并集中在旧任务核 \(K_{AA}\) 的极少数特征模态上（1–6 个模态承载 50–90% 的遗忘能量），由此解释了为何参数空间正则器在共享头基准上会失效，并导出一个只保护脆弱子空间的谱正则化方法。
Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding: 本文提出条件核岭回归（Conditional KRR）框架，将一组非惩罚特征注入核方法中，通过残差核将其归约为标准 KRR，证明了归约代价为 \(\mathcal{O}(1/\sqrt{N})\)，并在硬阈值（top-k 本征函数）和软阈值（随机高斯特征）两种设定下验证了条件 KRR 优于标准 KRR 的充分条件。
CORE-MTL: Rethinking Gradient Balancing via Causal Orthogonal Representations: 作者把多任务学习里"负迁移"的根因从"梯度冲突"重新归到"共享表征里语义和噪声纠缠"，提出 CORE-MTL：双流编码器把表征拆成语义 \(\hat{Z}_s\) 和残差 \(\hat{Z}_r\)，用 CKA 独立性约束 + 反事实风格替换 + 反演渲染重构来落地"因果正交"，理论上给出比梯度平衡更紧的 OOD 上界，实验上在 NYUv2/Cityscapes 的 ID 与 GTA5→Cityscapes、Cityscapes-C 的 OOD 设定上同时压过 PCGrad/GradNorm/STCH/FairGrad 等十种 baseline。
Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference: 作者指出经典 Hoeffding Tree（HT）在数据流上分裂时使用的"固定样本量"集中不等式被它自己采用的"数据相关停止规则"破坏，于是用 testing-by-betting + Universal Portfolio 重写分裂判据，让单棵树和 Adaptive Random Forest 都能在任意停止时刻保持 Type-I 错误可控，同时在 12 个真实流上更准且树更小。
Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity: 为了在"挑选最优模型"时少花评测预算，作者把经典 Successive Rejects 老虎机算法改造成"同步版"SySRs——每阶段让所有存活模型在同一批测试样本上评测，从而像配对检验那样利用模型间相关性，得到一个无超参、且误差上界随模型相关性变紧的最优臂识别算法，在 15 个标准基准上用 ≤35% 的模型×样本对就能可靠选出最优模型、全面超越已有方法。
Efficiently Learning Drifting Halfspaces with Massart Noise: 在分布随时间漂移、标签又被 Massart 噪声污染的在线学习场景下，本文给出第一个多项式时间学习 \(\gamma\)-间隔半空间的算法，误差为 \(\eta+\tilde{O}(\Delta^{1/3}/\gamma)\)，并用低次多项式下界证明 \(\Delta^{1/3}\) 这个指数对高效算法来说是无法绕过的，从而揭示出一条信息-计算鸿沟。
Enhancing Conformal Prediction via Class Similarity: 本文给任意共形预测（CP）打分函数加一个"出组惩罚"项，惩罚那些与 top-1 预测类不同语义组的候选标签；理论证明该惩罚在保持覆盖率的前提下既能减少预测集里的语义组数、又能意外地缩小平均预测集大小，并进一步提出一个无需人工语义划分、直接用模型特征构造类相似度矩阵的自适应变体。
Estimating Correlation Clustering Cost in Node-Arrival Stream: 本文研究「节点到达」数据流模型下相关聚类（correlation clustering）代价的近似估计问题：作者提出 C4Approx 算法，用 \(O(n^{(3+\alpha)/4}\log n)\) 词的亚线性空间和常数遍数得到 \((O(1), n^{1-\alpha})\)-近似，并配套两个匹配下界证明多遍与加性误差都不可避免；在真实数据上仅存 2% 节点即达 Pivot 同等效果。
Expectation Consistency Loss: Rethink Confidence Calibration under Covariate Shift: ECL 证明在协变量漂移下完整对齐输入分布 \(P_s(X) = P_t(X)\) 并非校准的必要条件，只要"在每个置信度水平集上 \(P(Y_k=1|X)\) 的条件期望两域一致"即可，并据此构造一个对 canonical / class-wise / top-label 三类校准都通用、可微、且 mini-batch 梯度无偏的损失 ECL。
Finite-Width Neural Tangent Kernels from Feynman Diagrams: 把量子场论里的费曼图搬到神经网络分析中，给"NTK 的有限宽度统计修正"提供一套图形化计算规则，让原本极繁琐的逐层递归推导变成"画图 + 套规则翻译"，并据此证明了 NTK 的临界稳定性、ReLU 等尺度不变激活在对角线上无有限宽度修正，数值上在宽度 \(n\gtrsim 20\) 即与采样网络吻合。
Formalizing Learning from Language Feedback with Provable Guarantees: 本文为"从语言反馈中学习"（Learning from Language Feedback, LLF）这一 LLM 智能体常见但缺乏理论的决策范式建立了第一个形式化框架：在奖励潜在不可见的设定下给出可学习的充分假设、提出"迁移 eluder 维数"刻画其难度、证明信息丰富的语言反馈能比奖励学习指数级更快，并给出有理论保证的无悔算法 HELiX（在 Battleship、Minesweeper 上稳定胜过 CoT 提示基线）。
Geometric and Stochastic Analysis of Discontinuities in Sparse Mixture-of-Experts: 首次对稀疏专家混合（SMoE）中 Top-\(k\) 路由带来的"输入—输出映射不连续性"做严格的几何 + 随机分析——按"打平专家个数"给不连续面分阶，证明低阶（order-1）不连续面占据几乎全部"近不连续"体积、高阶面体积可忽略，并用扩散过程证明随机扰动几乎必然首次撞上 order-1 面；据此提出一个即插即用的 \(\ell_\infty\) 局部平滑机制 SmoothSMoE，在几乎不增算力的前提下让 SMoE 映射连续并提升语言/视觉任务性能。
Is Spurious Correlation Removal Always Learnable?: 这篇论文证明：去除谬误相关（spurious correlation）即使在不变结构"统计上可识别"的理想情形下，也可能"计算上不可学习"——存在一族多环境实例，穷举搜索用多项式样本就能恢复不变方向，但任何多项式时间算法要达到常数精度都会反推出一个被广泛相信困难的稀疏恢复问题；同时论文用一个"环境多样性"参数 \(\gamma\) 刻画了可识别性、minimax 率与样本复杂度相变。
Learning Credal Ensembles via Distributionally Robust Optimization: CreDRO 把「认知不确定性」重新定义为不同训练-测试分布偏移假设下模型之间的分歧，用分布鲁棒优化（DRO）给集成中每个成员分配不同的偏移强度来训练，再把它们的 softmax 转成类别概率区间、构成一个箱式 credal 集来量化不确定性，从而在 OOD 检测和医疗选择性分类上稳定超过现有 credal 方法。
Matroid Algorithms Under Size-Sensitive Independence Oracles: 作者提出「查询代价随查询集合大小线性增长」的尺寸敏感拟阵 oracle 模型，证明在该模型下找基、估计秩、估计划分数的最优查询代价都是 \(\tilde{\Theta}(n^2)\)，并对有界周长 \(c\) 的拟阵给出 \(\mathcal{O}(n^{2-1/c}\log n)\) 的最大权基算法突破二次下界。
MMD-Balls as Credal Sets: A PAC-Bayesian Framework for Epistemic Uncertainty in Test-Time Adaptation: 论文为 test-time adaptation 提供了第一份"目标风险 ≤ 源经验风险 + KL 复杂度 + MMD 分布偏移项"的 PAC-Bayes 上界，并把 MMD-球解读为 Walley 意义下的 credal set，从而用"上下风险区间"自然分离 aleatoric 与 epistemic 不确定性，给出"何时应当 adapt、何时该 abstain"的可计算判据。
Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness and Safety: 本文提出一种以 \(\|\theta_j-\beta\|_{\bm\Sigma_j}\)（矩阵加权范数）为正则项的鲁棒多任务线性回归估计器，用一个相对的"平衡度常数" \(B\) 取代了既往工作中刚硬的"每个任务二阶矩最小特征值 \(\Omega(1)\)"假设，在病态/低秩/带离群任务的高维场景下同时给出最小最大率（minimax）、自适应、和回退到独立任务学习（ITL）的安全保证。
On Regret Bounds of Thompson Sampling for Bayesian Optimization: 这篇论文系统补齐了高斯过程 Thompson 采样（GP-TS）在贝叶斯设定下的遗憾分析：先构造了一个反例证明 GP-TS 对失败概率 \(\delta\) 只能做到多项式依赖（拿不到 \(\log(1/\delta)\)），再给出累积遗憾二阶矩上界把 \(\delta\) 依赖收紧 \(1/\sqrt{\delta}\) 倍、首个期望宽容遗憾的多对数上界、以及在更宽松 Matérn 条件下的 \(\tilde O(\sqrt T)\) 高概率遗憾上界，让 GP-TS 在理论保证上基本追平了被研究得最透的 GP-UCB。
On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective: 本文首次为测试时自适应（TTA）建立可学习性理论框架，用 \((\epsilon,\delta)\)-Recovery Complexity 衡量分布漂移后模型把超额风险压到 \(\epsilon\) 所需时间，并配合 \((\epsilon,\rho)\)-TTA Learnability 把局部恢复推广到整条非平稳测试流，导出匹配阶的 minimax 上/下界，揭示了 TTA 的"适应速度—信息约束"内在权衡。
On the Robustness of Langevin Dynamics to Score Function Error: 这篇论文证明了一个反直觉的负面结果：即使分数函数的 \(L^2\)（乃至 \(L^p\)）估计误差任意小，Langevin 动力学在高维下仍可能在任何多项式时间内都采不出接近目标分布的样本（总变差距离高达 \(1-e^{-\Omega(d)}\)）；而同样条件下扩散模型却能多项式时间成功——这从一个新角度论证了「扩散模型比 Langevin 动力学更可靠」，并给出一条实用警告：用数据初始化时必须用没参与训练分数的新鲜样本。
Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits: 本文把"近因效应"引入流式多臂赌博机，提出滑动窗口流式 MAB 模型——只有最近 \(W\) 个臂有效——并系统刻画了纯探索与遗憾最小化在该模型下的内存复杂度边界：精确找最优臂需要 \(\Omega(W)\) 内存（几乎得存下整个窗口），但找 \(\varepsilon\)-近似最优臂只需 \(O(1/\varepsilon)\) 内存，且遗憾最小化在 \(\Theta(W)\) 内存处出现尖锐相变。
Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification: 在多项式逻辑斯蒂（MNL）bandit 的组合动作空间里首次给出计算可行的 G-optimal 实验设计——把 Frank–Wolfe 线性最大化谱写成 0–1 MILP 或多项式时间 Schur 补松弛——并据此造出第一个面向"线性效用 + 非均匀收益"的最佳组合识别算法，样本复杂度 \(\tilde{\mathcal{O}}(d\log N / \Delta^2)\)。
Parsimonious Learning-Augmented Online Metric Matching: 本文回答了 Im et al. (2022) 留下的公开问题：把"按动作预测的"在线度量匹配带进"节俭预测"框架——预测被昂贵地按 \(k\) 步一次发放——并通过 Follow-the-Prediction 框架 + 自动补齐"虚拟预测"的元算法，给出与已知下界基本匹配的确定性和随机性竞争比上界。
Performative Learning Theory: 本文把"预测会改变它想预测的结果"这一 performative prediction 现象首次嵌入统计学习理论，在样本、总体、以及二者都被预测扰动的三种情形下证明了泛化误差/泛化间隙/超额风险的上界，揭示出"改变世界"与"从世界学习"之间的根本权衡，以及最坏情况下"总体自我否定、样本自我实现"形成的经验回声室。
Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function: 本文用「实代数几何 + 一阶谓词逻辑量词消去」给多维超参数调参第一次给出可证明的 generalization bound，把过去只能处理一维标量超参的 Balcan 2025 框架推广到任意 \(p\) 维、双层验证损失、近似内层优化等多种实际场景，并配出第一条匹配上界的下界。
Quantum Algorithms for Triangle Cut Sparsification: 为「三角形割稀疏化」设计量子算法：先给出第一个有可证明加速的量子三角形枚举算法（融合重轻顶点划分、量子游走、Grover 三套路并取最优），再把它嵌进 Kapralov 等人的 motif 稀疏化框架并对后处理采样也做量子加速，从而以 \(\widetilde{O}(\sqrt{mn}/\varepsilon)\) 量级的额外开销构造出 \(\widetilde{O}(n/\varepsilon^2)\) 大小的 \(\varepsilon\)-三角形割稀疏子图，并配上匹配的 \(\Omega(n/\varepsilon^2)\) 大小下界。
Realizable Bayes-Consistency for General Metric Losses: 本文对"在一般（可能无界）度量损失下，假设类 \(\mathcal{H}\) 何时存在分布无关的强通用 Bayes 一致学习算法"这一开放问题在 realizable 情形下给出锐刻画——充分必要条件是 \(\mathcal{H}\) 不包含一种新的"无界 gap Littlestone 树"组合障碍。
Revenue Guarantees of No-Swap-Regret Dynamics in First Price Auctions: 在离散一价拍卖里证明：任意 \(\epsilon\)-近似相关均衡的收益至少是 \(v_2-\Theta(1/k)-\Theta(\epsilon k^2)\)（\(v_2\) 是次高估值），由此首次给出无交换遗憾竞拍者在一价拍卖中收益的多项式收敛速率——若用最优 \(O(\sqrt{kT})\) 交换遗憾算法，只需 \(O(k^5/\epsilon^2)\) 轮就能让时均收益逼近次高估值，把此前的拟多项式界 \(k^{O(\log k)}\) 大幅改进。
Robustness of Mixtures of Experts to Feature Noise: 在「总参数量对齐」的公平设定下，本文用一个分块对角的带噪线性回归模型证明：MoE 的稀疏专家激活相当于一个噪声滤波器，使它在特征噪声下比同等大小的稠密模型有更低的泛化误差、更强的扰动鲁棒性和更快的收敛速度。
Semi-Supervised Noise Adaptation: Transferring Knowledge from Noise Domain: 作者把"从高斯噪声生成的合成域"当作半监督迁移学习里的替代源域，先证明这种"无语义但有判别结构"的噪声能给目标域带来可量化的泛化界改进，再用三损失的 Noise Adaptation Framework（NAF）联合优化两域风险与分布差异，使 CIFAR-10 上 4-shot ResNet-18 比 ERM 提升 12.35%。
Sequential Kernel-based Conditional Independence Testing via Adaptive Betting: SKCI 提出一个序贯（可随时停止）的条件独立性检验：它把"投注式检验（testing-by-betting）"用在一个自归一化的核条件独立统计量上，再配一套"截断 + 移位"的高斯近似校准，使得即便 Model-X 假设里的条件分布 \(P_{A\mid C}\) 必须在线估计（而非精确已知）、估计有误差时，Type I error 也只轻微膨胀、同时保持高检验功效——在高维合成基准和真实公平性审计任务上都优于现有序贯 Model-X 方法。
Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering: 本文为有符号图上的"坏三角形覆盖"问题（Bad Triangle Transversal, BTT）给出两个仅需单次解 LP 的简洁 2-近似算法，证明在完全图上 BTT 与 Correlation Clustering、MinSTC、Cluster Deletion 同时具有 \(\tfrac{2137}{2136}\) 的 NP-难逼近下界，并构造了一种新的 pivot 流程把任意可行 BTT 覆盖转化为最多 \(\tfrac{3}{2}|F|\) 错误的聚类，从而把 BTT 与 CC 最优值的差距从 2 收紧到 \(3/2\)。
Task-Restricted Symmetries in Recurrent Weight Space: 论文用「有序实 Schur 坐标」把训练好的单层 tanh RNN 的循环矩阵拆成谱块与非正规耦合块，通过逐块置零做结构化消融，发现某些非正规耦合可以在几乎不改变任务行为的前提下被删掉（近似函数不变性），而另一些是任务关键方向——而且这种「可删/不可删」的画像随任务和训练解而变，并非循环权重空间的普适对称性。
The Data Manifold under the Microscope: 针对"流形拟合理论给的泛化/逼近界几乎无法在真实数据上验证"这个理论与实践的鸿沟，本文造了一个可控的几何基准框架：把 dSprites、COIL-20 这类数据集重做成沿变换轴密集规则网格采样的低维流形，再配上有限差分几何估计器，能在低内蕴维度下以接近真值的精度算出曲率、reach、体积，从而把 Genovese、Fefferman 等人的流形拟合界拿到"已知真值"的沙盒里做实测校准。
Towards Optimal Robustness in Learning-Augmented Paging: 本文为带预测的随机化在线调页提出统一的「相对预测预算」(RPB) 视角，并基于 OnlineMin 设计 RPB-OnOPT 框架，把可证的鲁棒竞争比从既有的 \(2H_k+O(1)\) 一举推到信息论下界附近的 \(H_k+O(1)\)，同时保持 1-一致性。
Tree-Structured Orthonormal Decomposition of the Aitchison Simplex: PolyILR 给任意（含多分叉）树结构构造出一组典范、完备、正交的 Aitchison 单纯形坐标系：每个内部节点贡献 \(k_u-1\) 个对比坐标，通过加权内积 + Helmert 对比 + 按子树大小展开，保证整体仍是合法的等距 ILR 基，让成分数据的每个坐标都对应树上一个具体位置。
Two-Layer Linear Auto-Regressive Models Estimate Latent States: 本文从理论上证明：在部分可观测线性动力系统的数据上用经验风险最小化训练一个两层线性自回归模型，其隐层激活会自发地（在相似变换意义下）逼近最优卡尔曼滤波器给出的潜在状态估计——模型从未被告知系统参数或状态，却"端到端"地学会了滤波，并给出了预测、参数与状态恢复三重有限样本保证。
Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions: 本文从参数空间几何的角度解释了 Transformer 为何学不会 Parity 这类"敏感"布尔函数：它证明随机初始化的 Transformer 几乎必然会计算出"含大量零敏感度字符串"的函数，而像 Parity、First 这种缺乏零敏感度字符串的函数所对应的参数只占整个参数空间的一个勒贝格测度零子集，随机初始化几乎必然错过，因而可证不可学。
Unraveling Syntax: Language Modeling and the Substructure of Grammars: 本文为「语言模型损失」和「上下文无关文法（CFG）的子结构」建立了一套基础定理，证明语言建模的 KL 散度可以沿子文法层级递归地线性分解；并通过在合成 PCFG 上训练小 transformer 发现：模型是并行地学习所有子文法的（不像儿童先掌握简单结构），而 PCFG 子文法预训练只对相对文法很小的模型有帮助，但能稳定地让内部表示更贴合文法的子结构。
When Sample Selection Bias Precipitates Model Collapse: 本文证明在低资源、数据孤岛场景下，被广泛当作「模型坍塌解药」的数据选择反而会加速坍塌——每个验证器只看到目标流形的局部偏置切片，会优先保留贴近本地参考的样本、剪掉全局相关的尾部模式，理论上把方差以幂律速率压成点质量；作者据此提出用多孤岛构造 Wasserstein 代理参考（测地插值 / 重心）在不共享原始数据的前提下做协作选择来缓解。