Nov, 2023

局部 Borsuk-Ulam 定理，稳定性和可复现性

PDF
TL;DR使用并改编拓扑学中的 Borsuk-Ulam 定理来推导对列表可复制和全局稳定学习算法的限制，在组合学和拓扑学中进一步展示了我们方法的适用性，并发现在无初始假设能力类设置下，列表可复制和全局稳定学习均不可能。
borsuk-ulam theoremlearning algorithmscombinatoricstopologyagnostic pac setting
发现论文，激发创造
  • 可复现学习的计算景观

    我们研究算法可复现性的计算方面，这是由 Impagliazzo、Lei、Pitassi 和 Sorrell [2022] 引入的稳定性概念。通过一系列与可学习性的统计联系的最新研究，如在线学习、私有学习和 SQ 学习，我们旨在更好地理解可复现性与这些学习范式之间的计算联系。我们的第一个结果表明，存在一个概念类，其 PAC 学习可复现且高效，但在标准的密码学假设下，不存在这个类的高效在线学习者。随后，我们设计了一个高效的可复现学习算法，用于在边际分布与均匀分布之间差异很大的情况下 PAC 学习奇偶函数，进展了 Impagliazzo 等人 [2022] 提出的问题。为了获得这个结果，我们设计了一个可复现的提升框架，受 Blanc、Lange、Malik 和 Tan [2023] 的启发，以黑盒方式将均匀边际分布上的高效可复现 PAC 学习器转化为任意边际分布上的可复现 PAC 学习器，其样本和时间复杂度依赖于分布复杂度的某个度量。最后，我们证明任何纯 DP 学习器都可以在准确性、置信度参数的多项式时间内转化为一个可复现学习器，并且与底层假设类的表示维度成指数关系。

    May, 2024

  • 学习中的可复制性和稳定性

    本文研究了机器学习中的可复制性问题，提出了全局稳定性和列表可复制性的概念，并表明在除一些特殊情况外，大多数算法必须具有一定的随机性以实现可复制性。

    Apr, 2023

  • 均匀稳定算法的更严格界限

    这篇论文研究了学习理论中有关稳定算法的泛化界，通过构造一个弱相关随机变量的集中不等式，得到了一般性的集中界，使得上已知的高概率上界的泛化界水平得到了提高。

    Oct, 2019

  • 可复制学习中的清单和证书复杂度

    本研究探讨了可复制的学习算法，在考虑可行的可复制性观念和证明可复制性的基础上，设计了一些用于特定学习问题的算法，其列表和证明的复杂度是最优的，并提出了相应的不可能性结果。

    Apr, 2023

  • 稀疏随机图上本地算法的限制

    本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小，而且通过聚类属性，我们强调了在随机图上的局部算法存在局限性。

    Apr, 2013

  • 信息论泛化界的统一框架

    文中提出了一种利用概率去相关引理、对测度空间中的的概率测度进行对称化、配对和链化等技术来获得学习算法信息论泛化界限的一般性方法，进而得到新的期望值和高概率条件下泛化误差的上界，特别地，还包括了基于互信息、条件互信息、随机链和 PAC-Bayes 不等式等现有泛化界限的特例。此外，Fernique-Talagrand 上界也是一个特例。

    May, 2023

  • 一般 Lovasz 局部引理的构造性证明

    本文提出并改进了一种构建性的方法以直接适用于贯穿 Lovasz Local Lemma 的大部分应用，此方法需要的约束条件基于有界出现可满足性问题。

    Mar, 2009

  • 测试者学习半空间的通用算法

    本研究提出了一种普适性的半空间测试学习算法，它可以在所有满足 Poincaré 不等式的分布上获得较小误差，具体实现是使用 sum-of-squares 算法检查分布的超对称性。

    May, 2023

  • 未标记样本压缩方案及其在广泛和最大类别中的应用

    该论文研究了机器学习中的组合概念和立体几何领域的拓扑概念之间的联系，并引入了 VC 维和样本压缩方案等概念，提出了一些新的构造和结论。

    Dec, 2018

  • 从价值到算法：松弛和本地化

    通过最小值极大分析推导出在线学习算法来应对困难的学习问题，利用本地顺序 Rademacher 复杂性与相关算法实现更快速的在线学习，并引入随机化方法以及其他的方法来完善算法性能。

    Apr, 2012