- 具有时序反馈图的对抗在线学习
基于分区策略,本研究提出了一种新的学习算法,用于预测与专家建议的问题并同时受限于反馈图结构,证明对于传递反馈图,该算法可以高效实现且达到最优遗憾界(与一个常数因子定量相近)的预测性能优化。
- 多层次最优臂识别
在本文中,我们研究多信度最佳臂识别问题,通过提出一种以梯度为基础的方法,我们找到了具有渐近最优成本复杂度的解决方案,并针对每个臂还提出了最优保真度的概念。
- 流式随机多臂赌博机中的记忆 - 遗憾权衡理解
在 $P$ 次流式模型中研究随机多臂赌博机问题,通过设计一种算法,给出了关于 $m,n$ 和 $P$ 的最优遗憾度量的完整刻画,同时提出了一个上界和下界,结果在 $n$ 和 $P$ 方面具有紧密性。
- 像 Transformer 一样进行计数:将时间计数逻辑编译成 Softmax Transformers
基于序列变换器的计算能力,提出了时序计数逻辑 Kt 和 C-RASP 变种,并证明它们可以编译为具有未限制输入大小的未来掩码软注意力变换器,从而形成了迄今为止已知的形式表达能力下界。
- 并行提升的成本
在这篇论文中,我们研究了用于学习的弱到强增强算法的并行成本,结果表明即使是对增强的轻微并行化也需要训练复杂度指数级增长,我们证明了这个上限并且给出了一些补充的结果和权衡,首次提供了并行性和增强所需总工作之间的权衡。
- 最大边际自由度的上界
这篇文章研究了核岭回归中的低秩逼近和替代方法,通过引入降维算法和核函数的正则性,探讨了降维逼近的有效维度与正则化参数的增长关系,并证明了对于合适的核函数,这种增长是渐近对数的,从而使得低秩逼近成为纽斯特伦方法。
- 神经网络中的深度分离:将维度分离出来与准确性
证明了在满足条件的情况下,当用深度为 2 和深度为 3 的神经网络来近似一个在 [0,1]^d 上与 Lipschitz 目标函数的 constant 精度相等的分布时,存在指数级的差距。
- 二元感知机容量的注记
解决二进制感知器容量 αc 的问题,作者给出并证明了一个上界 αc < .847。
- 关于学习增强的多选项滑雪租赁的最佳一致性 - 鲁棒性权衡
本研究解决了学习增强的多选项滑雪租借问题,提出了最佳算法来匹配已知的下界,为随机算法提供了第一个非平凡的下界并呈现了一个改进的随机算法。
- 常数轮次学习的时间 - 空间下界
对于每个常数 q,我们证明了在样本流上进行 q 次遍历的任何奇偶性学习算法都需要 Ω(n2) 的内存大小或至少需要 2Ω(n) 个样本数量,并且这是对于任何 q≥3 的第一个非平凡的下界。与先前的工作类似,我们的结果适用于具有许多近似正交概 - 标签噪声:纠正一次修正
训练神经网络分类器在带有标签噪声的数据集上存在过拟合的风险,为了解决这个问题,研究人员探索了更加稳健的替代损失函数,然而,许多这些替代方法都是启发式的,仍然容易受到过拟合或欠拟合的影响。在本研究中,我们提出了一种更直接的方法来应对标签噪声引 - 流式赌博问题的紧凑内存遗憾下界
这篇论文研究了流式赌博机问题,建立了时间上界、臂数、游戏轮数的算法紧确的最劣后悔下限,并证明了与分析算法复杂度上限的样本复杂性分析问题的关系。
- 循环和非循环因果模型的统一试验设计方法
本文提出了一种实验设计方法,可以学习含有循环或非循环的因果图,并且在保证最差情况下的唯一识别因果图所需实验数量最少。
- CVPR基于结构互信息最大化的无监督心脏分割域适应
本文介绍了一种名为 UDA-VAE ++ 的无监督域适应框架,该框架利用互信息的估计值和全局估计器、局部估计器以及先验信息匹配估计器之间的结构互信息估计(SMIE)块,提出了一种新的下限来解决心脏分割问题,并通过一种创新的顺序重新参数化方案 - 基于 Lewis 加权子采样的 L1 回归
考虑了只观察到少量标签时,寻找 l1 回归的近似解的问题。我们表明,根据其 Lewis 权重对 X 进行采样并输出经验最小化器可在概率 1-δ 下成功地进行,其中 m>O(1/ε²dlog (d/εδ))。我们还给出了相应的下界。
- 非凸强凹 Min-Max 优化的复杂度下界
我们通过使用第一阶 oracle 及条件数,提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界,这既适用于确定性 oracle 也适用于随机 oracle,并提供了各自的下界,并 - 线性赌博机中的 Pareto 最优模型选择
本文是一篇关于线性臂选模型选择的研究,提出了一种 Pareto 最优算法,能实现基于已知维度的较小假设集来平衡探索和开发,并且能够匹配模型选择问题的最低界限。
- 分散式訓練中的最優複雜度
本文利用随机非凸设置提供了关于迭代复杂度的紧密下界,并针对现有的分散式训练算法的已知收敛速度之间的理论差距进行了实证比较,提出了 DeTAG,一种实用的闲话式分布式算法。
- 图探索竞争问题的改进下界
通过访问顶点并返回起始位置的单一代理器的边权无向图探索,我们在 competitive ratio 上获得了 10/3 的改进下界,这与 Dobrev 的下限相比较,也适用于平面图。
- 极小极大优化的近似最优算法
本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法,其梯度复杂度为 O(kappa_x kappa_y^0.5),匹配了已有的最优下界,可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。