- ICML通过耦合初始化限制神经网络的宽度 -- 一种最坏情况分析
通过将权重初始化为独立的高斯向量对,可以显著提高收敛分析和减少神经元的数量,同时改进了关于随机输入的类似技术,并证明了新的下界与某些假设下的最佳情况。
- 通过决策边界理解深度学习
发现决策边界变异性较低的神经网络具有更好的泛化性能;提出了算法 DB 变异性和(ε,η)- 数据 DB 变异性对决策边界变异性进行度量,并在理论上提出了两个基于算法 DB 变异性的下界。
- 强化学习中的计算统计差距
本文针对强化学习中的大状态空间问题,研究使用函数逼近的强化学习方法,并提出了寻找高效率算法的方案,同时探讨了计算难度与统计问题之间的关系。
- 联邦平均(局部 SGD)和连续视角的锐界
本文介绍了在联邦学习中最流行的算法之一 - 联邦平均(FedAvg),尽管其简单易用,但至今其收敛率仍未确定,并且该算法的收敛速度受限于其假设的条件。该研究通过提供一个匹配现有上限的 FedAvg 下限解决了已有的收敛速度问题,同时还证实了 - 基于未经校正的哈密顿退火的 MCMC 变分推断
提出了一种使用类似于 AIS(Annealed Importance Sampling)的 Uncorrected Hamiltonian MCMC 过程的框架,称为 Uncorrected Hamiltonian Annealing,它能 - ICML可解释的 k-Medians 和 k-Means 的近似最优算法
研究在可解释的 k - 中位数和 k - 均值问题中,提出了一种新的算法并分析了其竞争性和下界。
- 一种对深度阈值网络记忆容量的指数级提升
本篇论文证明了深度阈网络使用近似线性的神经元与权重便可实现存储数量为 n 在 d 维度的数据。同时,藉由将神经网络存储与纯几何问题上的超平面分离联系起来,论文也证明了一些新的下界。
- ICLR利用半空间在 $l_p$- 范数距离度量下改进浓度估计
通过理论分析、提出半空间方法,更加有效地测量数据集的浓缩程度,从而得到更紧密的原始鲁棒性下限,并证明这些更紧密的下限进一步排除了基于数据集浓缩的假说,该假说被认为是解释现有分类器使之易受到对抗攻击的可能原因。
- 训练深度为 2 的 ReLU 网络的紧硬度结果
本文研究基于 ReLU 激活函数的深度 2 神经网络在训练上的困难性,并证明了最小化给定训练集的二次损失函数下的权重和差异生成问题、K 个 ReLU 加权求和问题在现实情况下均为 NP 难问题;同时还针对该问题提出算法时间下限并进行上界分析 - 通过有向团树的因果 DAG 主动结构学习
本研究提出了针对因果有向无环图(DAGs)的干预设计的通用下限,并基于有向团树将 DAG 分解成可独立定向的组件,从而证明在任何 EC 中定向任何 DAG 所需的单节点干预数至少是每个基本图的链组件中最大团大小的一半的总和。另外,我们还提出 - 个性化联邦学习的下界和最优算法
本研究考虑了最近由 Hanzely 和 Richtarik (2020) 提出的个性化联邦学习的优化问题,并为该模型的通讯复杂度和本地预测通用复杂度建立了第一个下界。我们设计了几种最优方法来匹配这些下界,并通过大量的数字实验展示了我们的方法 - ICML使用梯度下降法学习单层神经网络的超多项式下界
利用梯度下降证明了学习单层神经网络的第一个超多项式下限,它包括使用小批量的梯度下降,需要锐利的激活函数和适用于特定查询的以前结果。与以前的结果不同,我们的结果适用于包括 ReLU 和 sigmoid 在内的广泛激活类别,并且围绕一种新型神经 - 带预测的加权页面在线算法
本文研究加权分页问题及其预测,提出 strong per request prediction (SPRP) 模型,证明结合固定的展望和下一个请求数的信息是不足以克服现有的下限。同时,我们还探讨了随着随着预测误差的增加,算法的缓慢衰退。通过 - TSSOS:一种利用项稀疏性的 Moment-SOS 层次
本文介绍了一个新的半定编程松弛分层方法,可利用输入多项式的项(或单项式)稀疏性,包括使用在一个迭代过程中生成的与原始数据中的术语相关的邻接图的连通分量的完成得到的块对角矩阵。该框架应用于计算多项式优化问题的下界。
- 利用生成模型进行压缩感知的下界
本文主要研究了基于生成模型的压缩感知问题,通过下界分析表明基于 L-Lipschitz 生成模型的压缩感知需要线性测量数至少是 k 乘以对数级别的,同时指出生成模型可以作为一种结构表示方法进行推广。作者还构造了一个具有 ReLU 激活的神经 - 随机梯度下降法的效果如何?
本研究探讨了随机梯度下降在平滑和强凸有限和优化问题上的性能,重点研究了包含在个体函数的随机排列中的启发式方法,给出了这些启发式方法的期望优化误差的下界,说明了它们的优势和劣势。
- ICLR图神经网络无法学习的内容:深度与宽度
该论文研究了图神经网络的表达能力,发现了其在深度和宽度受限时可能会失去很大一部分功效,同时提出了一种使分布式计算的经典结果得以重用的新技术,给出了各种图论问题的下界。
- 用于转导线性赌博机的连续实验设计
本文介绍了传导式线性赌博机问题,提供了该问题的上下界和算法,并给出其评估结果,特别地,提供了第一个实现信息论下界的非相似线性赌博机算法。
- ICML可微博弈的线性下界与条件数
提出了一种使用单一目标凸优化工具构建适用于各种问题的线性下界,特别是在 n 个玩家可微分对抗博弈中使用谱方法得到了线性下界。
- 基于 Oracle 的二阶段稳健优化算法
本文研究具有目标不确定性的二阶段鲁棒优化问题,提出了一种算法,通过交替求解基础确定性问题和对抗性问题来高效计算二阶段鲁棒问题的下界。该算法适用于线性和非线性目标函数,研究发现其在非线性目标函数下,具有更高的性能表现。同时作者还测试了基于列生