新智元报道
编辑：David 拉燕 好困
【新智元导读】ICML 2022杰出论文揭晓！复旦、上交、厦大等中国高校上榜，吴恩达、Jeff Dean等获时间检验奖荣誉提名。｜还在纠结会不会错过元宇宙和web3浪潮？清华大学科学史系副教授胡翌霖，这次给你讲个透！
又一AI顶会开奖了！
刚刚，ICML2022官网公布了本届大会的杰出论文和时间检验奖。
中国学者收获颇丰，来自复旦大学、厦门大学、上海交通大学等国内高校参与的多项工作入选杰出论文。
本届大会的时间检验奖。授予一篇关于对支持向量机进行破坏性攻击的论文。
值得一提的是，Quoc Le、Jeff Dean、吴恩达等大牛的关于「大规模非监督学习构建高阶特征」的论文获得时间选择奖荣誉提名。
杰出论文（Outstanding Papers）
Monarch: Expressive Structured Matrices for Efficient and Accurate Training
作者：Tri Dao, Beidi Chen, Nimit Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, Christopher Re
发文单位：斯坦福大学、纽约州立大学布法罗分校、密歇根大学
论文链接：https://arxiv.org/pdf/2204.00595.pdf
摘要：
大型神经网络在许多领域都很出色，但训练和微调成本很高。一个流行的方法是用结构化的权重矩阵（如稀疏的、低等级的、傅里叶变换的）来代替密集的权重矩阵，以减少计算/内存需求。然而这些方法并没有被广泛采用。
为了解决这些问题，我们提出了一类矩阵（Monarch），它具有硬件效率（为了更好地利用硬件，它们被参数化为两个块对角矩阵的乘积）和表现力（它们可以代表许多常用的变换）。
Solving Stackelberg Prediction Game with Least Squares Loss via Spherically Constrained Least Squares Reformulation
作者：Jiali Wang, Wen Huang, Rujun Jiang, Xudong Li, Alex Wang
发文单位：复旦大学、厦门大学、卡内基梅隆大学
论文链接：https://arxiv.org/pdf/2206.02991.pdf
摘要：
本文探讨了SPG-LS的另一种重新表述。通过一个新的非线性变量变化，将SPG-LS重写为球形约束最小二乘法（SCLS）问题。
本文应用了两种著名的方法来解决这个新的重构，即Krylov子空间方法和黎曼尼信任区域方法。这两种算法都是无因子化的，因此适合解决大规模的问题。在合成数据集和真实世界数据集上的数值结果表明，配备了SCLS重构的SPG-LS的求解速度比现有技术水平要快几个数量级。
Adversarially Trained Actor Critic for Offline Reinforcement Learning
作者：Ching-An Cheng, Tengyang Xie, Nan Jiang, Alekh Agarwal
发文单位：微软研究院、伊利诺伊大学厄巴纳-香槟分校、谷歌研究院
论文链接：https://arxiv.org/pdf/2202.02446.pdf
摘要：
本文提出Adversarially Trained Actor Critic (ATAC)，这是一种基于相对悲观主义概念的离线强化学习（RL）的新型无模型算法。ATAC被设计成一个双人的Stackelberg游戏。一个政策执行者与一个经过对抗性训练的价值评论者竞争，后者找到数据一致的场景，其中执行者不如数据收集行为政策。
与现有的工作相比，本文的框架既提供了一般函数近似的理论保证，又提供了可扩展到复杂环境和大数据集的深度RL实现。在D4RL基准测试中，ATAC在一系列连续控制任务上始终优于最先进的离线RL算法。
Stable Conformal Prediction Sets
作者：Eugene Ndiaye
发文单位：佐治亚理工大学
论文链接：https://arxiv.org/pdf/2112.10224.pdf
摘要：
当人们观察到一连串的变量( x1, y1 ), ..., ( xn, yn )时，共形预测是一种方法，它可以通过假设数据的分布是可交换的，来估计给定x n 1的置信集。但这种集合的计算在一般情况下是不可行的。
本文中将共形预测技术与算法稳定性边界相结合，得出了一个可通过单一模型拟合计算的预测集。我们进行了一些数值实验，说明了当样本量足够大时，本文的估计是严密的。
Do Differentiable Simulators Give Better Policy Gradients?
作者：Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, Russ Tedrake
发文单位：麻省理工学院
论文链接：https://arxiv.org/pdf/2202.00817.pdf
摘要：
可微分模拟器通过用基于一阶梯度的估计取代随机目标的零阶梯度估计，为强化学习提供更快的计算时间。然而，目前还不清楚是什么因素决定了这两个估计器在涉及物理系统的长视距规划和控制的复杂景观中的性能。
我们表明，某些物理系统的特征，如刚度或不连续性，可能会损害一阶估计器的功效，并通过偏差和方差的角度分析这一现象。我们还提出了一个α阶梯度估计器，α∈[0，1]，它正确地利用了精确梯度，将一阶估计的效率与零阶方法的鲁棒性结合起来。
Learning inverse folding from millions of predicted structures
作者：Chloe Hsu, Robert Verkuil, Jason Liu, Zeming Lin, Brian Hie, Tom Sercu, Adam Lerer, Alexander Rives
发文单位：加州大学伯克利分校、Facebook AI、纽约大学
论文链接：https://www.biorxiv.org/content/10.1101/2022.04.10.487779v1.full.pdf
摘要：
本文通过使用AlphaFold2预测1200万个蛋白质序列的结构，将训练数据增加了近三个数量级。通过这些额外数据的训练，一个具有不变的几何输入处理层的序列到序列的转化器在结构保持的骨架上实现了51%的原生序列恢复，对埋藏的残基实现了72%的恢复，比现有的方法整体提高了近10个百分点。
Learning Mixtures of Linear Dynamical Systems
作者：Yanxi Chen, H. Vincent Poor
发文单位：普林斯顿大学
论文链接：https://proceedings.mlr.press/v162/chen22t/chen22t.pdf
摘要：
本文研究了从无标签的短样本轨迹中学习多个线性动态系统（LDS）的混合物的问题，每个样本由一个LDS模型生成。尽管混合模型对时间序列数据具有广泛的适用性，但现有文献中基本没有附带端到端的性能保证的学习算法。
我们开发了一个两阶段的元算法，保证有效地恢复每个真实的LDS模型，其误差为Oe( p d/T)，其中T为总样本量。我们用数值实验验证了我们的理论研究，证实了所提出的算法的有效性。
Causal Conceptions of Fairness and their Consequences
作者：Hamed Nilforoshan, Johann Gaebler, Ravi Shroff, Sharad Goel
发文单位：斯坦福大学、纽约大学、哈佛大学
论文链接：https://arxiv.org/pdf/2207.05302.pdf
摘要：
本文将流行的算法公平的因果定义归纳为两大类：（1）那些限制决策对反事实差异的影响的定义；以及（2）那些限制受法律保护的特征，如种族和性别，对决策的影响的定义。
本文通过分析和经验表明，这两个系列的定义（几乎总是）--在计量理论的意义上--导致强烈的帕累托支配的决策政策，这意味着有一个替代的、不受约束的政策受到每个利益相关者的青睐，其偏好来自一个大的、自然的类别。
事实上，在一个突出的因果公平定义下，我们证明所产生的政策要求以相同的概率录取所有学生，而不考虑学术资格或团体成员。我们的结果强调了因果公平的常见数学概念的形式限制和潜在的不利后果。
Active fairness auditing
作者：Tom Yan, Chicheng Zhang
发文单位：卡内基梅隆大学、亚利桑那大学
论文链接：https://arxiv.org/abs/2206.08450
摘要：
各个行业的公司对机器学习（ML）的快速普及带来了重大的监管挑战。其中一个挑战是可扩展性：监管机构如何有效地审计这些ML模型，确保它们是公平的？
在本文中，我们启动了对基于查询的审计算法的研究，该算法可以以一种查询有效的方式估计ML模型的人口平价。我们提出了一个最佳的确定性算法，以及一个实用的随机化的、具有可比性保证的Oracle效率算法。此外，本文在理解随机化主动公平性估计算法的最佳查询复杂性方面取得了进展。
Understanding Dataset Difficulty with V-Usable Information
作者：Kawin Ethayarajh, Yejin Choi, Swabha Swayamdipta
发文单位：斯坦福大学、艾伦人工智能研究所、华盛顿大学
论文链接：https://arxiv.org/pdf/2110.08420.pdf
摘要：
估算一个数据集的难度通常包括将最先进的模型与人类进行比较；性能差距越大，数据集就越难。然而，这种比较对给定分布中的每个实例有多难，或者什么属性使数据集对一个给定的模型来说是困难的，提供的理解很少。为了解决这些问题，我们将数据集的难度--相对于一个模型的V来说--定义为缺乏V的可用信息，其中较低的值表示V的数据集更难。
我们进一步引入点式V信息（PVI）来衡量单个实例的难度--相对于一个给定的分布。虽然标准的评估指标通常只对同一数据集的不同模型进行比较，但V型信息和PVI也允许反过来：对于一个给定的模型V，我们可以比较不同的数据集，以及同一数据集的不同实例/片断。此外，我们的框架允许通过输入的转换来实现不同输入属性的可解释性，我们用它来发现广泛使用的NLP基准中的注释假象。
G-Mixup: Graph Data Augmentation for Graph Classification
作者：Xiaotian Han, Zhimeng Jiang, Ninghao Liu, Xia Hu
发文单位：德克萨斯农工大学、佐治亚大学、莱斯大学
论文链接：https://arxiv.org/pdf/2202.07179.pdf
摘要：
Mixup通过在两个随机样本之间插值特征和标签，在提高神经网络的泛化和鲁棒性方面显示出优越性。传统上，Mixup可以在规则的、网格状的和欧几里得数据上工作，如图像或表格数据。然而，直接采用Mixup来增强图的数据是具有挑战性的，因为不同的图通常1）有不同数量的节点；2）不容易对齐；3）在非欧氏空间有独特的类型。
为此，我们提出了G-Mixup，通过插值不同类别的图的生成器（即graphon）来增强图的分类。具体来说，我们首先使用同一类别中的图来估计一个graphon。然后，我们不直接操作图形，而是在欧几里得空间中插值不同类别的图元，以获得混合图元，其中合成图元是通过基于混合图元的采样产生的。广泛的实验表明，G-Mixup极大地提高了GNN的泛化和稳健性。
The Importance of Non-Markovianity in Maximum State Entropy Exploration
作者：Mirco Mutti, Riccardo De Santi, Marcello Restelli
发文单位：米兰理工大学、博洛尼亚大学、苏黎世联邦理工学院
论文链接：https://arxiv.org/pdf/2202.03060.pdf
摘要：
在最大状态熵探索框架中，代理人与无奖励环境互动，以学习一个政策，使其诱导的预期状态访问熵最大化。
在本文中，我们认为非马尔科夫性对于有限样本制度下的最大状态熵探索反而是最重要的。特别是，我们将目标重塑为在一次试验中诱导状态访问的预期熵。我们表明，非马尔科夫确定性策略的类别对于引入的目标来说是足够的，而马尔科夫策略在一般情况下遭受非零遗憾。然而，我们证明寻找最佳非马尔科夫政策的问题是NP-hard。尽管有这个否定的结果，我们讨论了以可操作的方式解决这个问题的途径，以及非马尔科夫探索如何在未来的工作中有利于在线强化学习的样本效率。
Minimum Cost Intervention Design for Causal Effect Identification
作者：Sina Akbari, Jalal Etesami, Negar Kiyavash
发文单位：瑞士洛桑联邦理工学院（College of Management of Technology, EPFL）
论文链接：https://arxiv.org/pdf/2205.02232.pdf
摘要：
在这项工作中，我们考虑的问题是以最小的成本设计干预措施的集合，以确定所需的效果。首先，我们证明这个问题是NP-hard的，随后提出一种算法，可以找到最优解或对数因子的近似解。这是通过在我们的问题和最小命中集问题之间建立联系来实现的。此外，我们提出了几个多项式时间启发式算法来解决这个问题的计算复杂性。尽管这些算法有可能在次优的解决方案上绊倒，但我们的模拟表明，它们在随机图上实现了小的遗憾。
Privacy for Free: How does Dataset Condensation Help Privacy?
作者：Tian Dong, Bo Zhao, Lingjuan Lyu
发文单位：上海交通大学、爱丁堡大学、Sony AI
论文链接：https://arxiv.org/pdf/2206.00240.pdf
摘要：
为了防止无意中的数据泄露，研究界采用了能够产生不同隐私数据的数据生成器进行模型训练。然而，出于对数据隐私的考虑，现有的解决方案要么存在昂贵的训练成本，要么存在较差的泛化性能。因此，我们提出了一个问题：训练效率和隐私是否可以同时实现。在这项工作中，我们首次发现，原本为提高训练效率而设计的数据集浓缩（DC）也是一个更好的解决方案，可以取代传统的数据生成器来生成私有数据，从而免费提供隐私。
为了证明DC的隐私优势，我们建立了DC和差分隐私之间的联系，并在理论上证明了线性特征提取器（然后扩展到非线性特征提取器），一个样本的存在对通过DC从n(n m)个原始样本合成的m个样本上训练的网络的参数分布影响有限（O（m/n））。我们还通过发起基于损失的和最先进的基于似然的成员推理攻击，实证验证了DC合成数据的视觉隐私和成员隐私。我们认为这项工作是数据高效和保护隐私的机器学习的一个里程碑。
Bayesian Model Selection, the Marginal Likelihood, and Generalization
作者：Sanae Lotfi, Pavel Izmailov, Gregory Benton, Micah Goldblum, Andrew Wilson
发文单位：纽约大学
论文链接：https://arxiv.org/pdf/2202.11678.pdf
摘要：
如何在与观察完全一致的假说之间进行比较？边际似然（又称贝叶斯证据）代表了从先验产生我们观察结果的概率，它为这个基础性问题提供了一种独特的方法，自动编码了奥卡姆剃刀。尽管已经观察到边际似然可以过度拟合，并且对先验假设很敏感，但它对超参数学习和离散模型比较的局限性还没有被彻底研究。
我们首先重温了边际似然对于学习约束和假设检验的吸引人的特性。然后，我们强调了使用边际似然作为泛化的代理的概念和实际问题。也就是说，我们展示了边际似然如何与泛化负相关，对神经结构搜索有影响，并可能导致超参数学习中的欠拟合和过拟合。我们通过条件边际似然提供了部分补救措施，我们表明条件边际似然与泛化更加一致，对大规模的超参数学习，如深度核学习，具有实际价值。
Test of Time Award （时间检验奖）
本届时间检验奖授予了十年前ICML的一篇论文，该论文对机器学习领域产生了实质性影响，包括研究和实践。
作者：Battista Biggio, Blaine Nelson, Pavel Laskov
发文单位：卡利亚里大学、杜宾根大学
论文链接：https://arxiv.org/pdf/1206.6389.pdf
摘要：
我们研究了针对支持向量机（SVM）的一系列毒化攻击。这种攻击注入特别制作的训练数据，增加SVM的测试误差。这些攻击的核心动机是，大多数学习算法假设其训练数据来自一个自然或良好的分布。然而，这一假设在安全敏感的环境中通常并不成立。
正如我们所证明的，一个聪明的对手可以在一定程度上预测SVM的决策函数因恶意输入而发生的变化，并利用这种能力来构建恶意数据。拟议的攻击使用梯度上升策略，其中梯度是根据SVM的最优解的属性计算的。这种方法可以被核化，即使对于非线性核，也能在输入空间构建攻击。我们通过实验证明，我们的梯度上升程序能够可靠地识别出非凸验证误差面的良好局部最大值，从而显著增加分类器的测试误差。
另有两篇论文获得时间检验奖荣誉提名。其中一篇是Quoc Le、Jeff Dean、吴恩达等大牛的关于「大规模非监督学习构建高阶特征」的论文。
参考资料：
https://icml.cc/virtual/2022/awards_detail
