Apr, 2012

分布式学习，通信复杂度和隐私

PDF
TL;DR讨论分布式数据的 PAC 学习问题，分析了涉及的基本通信复杂性问题，包括教学维度和错误绑定。针对特定概念类别，如合取、奇偶函数和决策列表等，给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信，以及如何在不确定环境下实现低通信回归。同时，还考虑了隐私性，包括差分隐私和分布式隐私。
pac-learningcommunication complexityteaching-dimensionboostingprivacy
发现论文，激发创造
  • 多分布学习中 VC 类的样本复杂度

    多分布学习是 PAC 学习在具有多个数据分布的环境中的自然推广，本论文讨论了该问题的最新研究进展以及在统计学习中使用游戏动态的一些基本障碍。

    Jul, 2023

  • 具有次线性通信的分布式学习

    研究了在分布式学习中，如何在总通信次数亚线性的情况下通过镜像下降与随机稀疏化 / 量化迭代相结合的算法来实现线性模型的最优误差学习，从而探讨了高维环境下分布式学习的可行性。

    Feb, 2019

  • 私有的 PAC 学习可能比在线学习更困难

    根据合理的密码学假设，我们展示了一个概念类别，该类别允许在多项式时间内以多项式错误边界运行的在线学习器，但不存在计算效率高的差异隐私 PAC 学习器。

    Feb, 2024

  • 分布式分类与优化的高效协议

    本文提出了基于多项式权重更新的两方协议，并且展示了一般的算法设计方法来解决在分布式数据中的高效学习问题。

    Apr, 2012

  • 分布式凸优化的通信复杂度

    研究了分布式方法在凸学习与优化中所需要的通信效率的根本限制，在不同信息假设和函数类型条件下找到了现有算法已达到最坏复杂度的情况，同时也指出了仍有改进的余地，说明了当本地目标函数没有相似之处时（由于统计数据相似或其他原因），即使设备具有无限计算能力，也可能需要多次通信往返。

    Jun, 2015

  • 打破通信 - 隐私 - 准确性三难题

    该研究提出了一种基于 Kashin 表示和随机抽样的方案以及利用 Walsh-Hadamard 矩阵的递归结构来实现隐私和通信效率的联合优化编码和解码机制，对平均值估计和频率估计等问题进行了研究。

    Jul, 2020

  • 非均匀收敛下的最优 PAC 上界

    本研究提出一种新的框架，超越了传统统一收敛方法的限制，将排列不变预测器的交叉检验误差转化为高概率风险界，并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中，我们证明了该框架的优越性能。

    Apr, 2023

  • 私有学习器的样本复杂度表征

    本文给出了一个样本大小的组合特征，是私有概念类学习足够和必需的。我们介绍了概念类的概率表示概念，并证明了私有学习算法对于概念类 C 的样本复杂度意味着 RepDim（C）＝O (m)，并且存在一个样本复杂度 m = O（RepDim（C））的私有学习算法。

    Feb, 2014

  • 多分布学习的样本复杂度

    这篇论文研究多分布学习，给出了一个样本复杂度为 $\widetilde {O}((d+k)\epsilon^{-2}) \cdot (k/\epsilon)^{o (1)}$ 的算法，解决了 COLT 2023 的开放问题。

    Dec, 2023

  • 不同标签函数的协同学习

    研究一种协作 PAC 学习的变体，旨在学习每个数据分布的准确分类器，同时最小化从这些数据分布中所抽取的样本数总量。给出基于经验风险最小化算法的学习方法，并且分析依赖于增强的假设类的 VC 维度的上界。在计算效率方面，证明了在一般情况下，基于增强的假设类的 ERM 是 NP 难的，为不存在计算效率高的学习器提供了依据，但对于两种特殊情况，给出了既有样本效率又有计算效率的学习器。

    Feb, 2024