标签
该论文证明了所有在总变差距离下可学习的分布类也都是可私有学习的，从而证实了Ashtiani的一个猜想，即在(ε,δ)-差分隐私约束下，只要目标误差可以任意小，有限样本下的可学习性依然成立。
论文提出 Halve-Then-Greedy（HTG）算法，用于固定预算下的自适应实验设计，以最大化推荐设计均值超过目标的后验概率，并证明了近最优的实例相关样本复杂度界。
哈佛大学研究人员提出了一种关于规模泛化的统计学习理论，证明了域内学习与跨规模学习在样本复杂度上存在指数级差距，并给出了与维度无关的缩放定律及与之匹配的极小极大下界。
该论文研究了当用户偏好存在异质性时，通过成对比较按照总体平均效用对模型进行排序所需的重复比较次数。作者提出了一种 Russian Roulette 式的 MLE 算法，仅需每上下文 O(log 1/Δ) 次（期望 O(1) 次）重复比较即可恢复排序，并证明了该对数级依赖是最优的。
一篇新论文《Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation Learning》提出了MA-BC方法，该方法仅在观测到的专家动作不存在分歧时才汇集专家示范数据，并给出了在具有不同目标的专家处进行学习时样本复杂度的上界和下界。
该论文为大模型推理中基于束搜索的测试时扩展提供了理论保证，证明了朴素束搜索样本复杂度的下界，并提出了置信度过滤束搜索（CF-Beam），将覆盖率依赖从二次降低到接近线性，在长程任务上表现优于 Best-of-N 等序列级方法。
本文引入稀疏先验以提升分布学习的理论保证，表明在稀疏先验下，样本复杂度以 Ω(√(k/n)) 的规模缩放，而非 O(n^{-1/Θ(d)})，从而缓解维度灾难。
本文解决了经验风险最小化对于二元分类是否相对智能的问题，探讨了在未标注数据中具有二次复杂度增长的半监督学习，并证明了某些学习者的不可处理性结果。
本文引入了一种跨模型映射，用于认证必须在协变量偏移下同时满足自动化下限和风险上限的选择性预测器，推导了可行性边界和双资源样本复杂度权衡。
本文研究了动力系统辨识中的自适应对称性发现，表明已知对称性可缩短辨识所需的轨迹长度，并提出了一种从单条轨迹中学习未知对称群的方法，以达到与已知对称性情形相同的优化长度。
This paper studies the sample complexity of policy learning under the mu-resets interaction protocol in reinforcement learning, resolving a question about the role of policy realizability and showing horizon dependence is exponential under all-policy concentrability and sqrt-exponential under pushforward concentrability.
本文回答了Hanneke、Moran和Waknine提出的一个开放问题，证明了直接和的不可知PAC学习曲线并非仅由单实例学习曲线和因子数量决定，从而提供了一种速率分离。
本文研究了鲁棒平均奖励马尔可夫决策过程的样本复杂度，在总变差不确定集下通过插入式归约导出了极小极大最优学习率。
This paper studies the sample complexity of multicalibration for a sequence of properties that are sequentially identifiable, establishing matching upper and lower bounds up to logarithmic factors.
本文提出了一种无Hessian矩阵的基于超梯度的双层强化学习算法，实现了最先进的样本复杂度，并在收敛性分析中去除了PL条件假设。
本文提出了改进的算法用于学习截断布尔乘积分布，利用布尔函数分析中的影响力概念，实现了与未截断情况下的极小极大率相匹配的样本复杂度。
本文介绍了分级大型语言模型（GLLMs），这是一种代数框架，对 Transformer 表示施加层次化分级，理论上可提高语言层次结构的样本效率，同时保持推理复杂度不变。该框架提供了几何与信息论角度的论证，并概述了一种分级选择流程，该流程在配套手稿中得到验证。
介绍了一种名为VRDQ的分布式Q学习算法，用于在静态和时变网络上进行多智能体强化学习，该算法具有有限时间收敛保证，在样本复杂度上实现线性加速，且仅需Õ(1)次通信。
本文研究了基于噪声成对比较的固定置信度top-k识别问题，并开发了一种渐近最优算法，该算法最小化期望比较次数。
本文研究了固定置信度下的最佳臂识别问题，其中昂贵的奖励观测与来自生成模型的廉价但相关的代理分数配对。提出了PROBE算法，该算法使用控制变量调整和残差方差的上界证书，以实现接近神谕的样本复杂度。