• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
【24h】

Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

机译：私人经验风险最小化：高效算法和严格错误界限

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Convex empirical risk minimization is a basic tool in machine learning and statistics. We provide new algorithms and matching lower bounds for differentially private convex empirical risk minimization assuming only that each data point's contribution to the loss function is Lipschitz and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex.Our algorithms run in polynomial time, and in some cases even match the optimal non-private running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for (ε, 0)- and (ε,δ)-differential privacy, perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median.
机译：凸经验风险最小化是机器学习和统计中的基本工具。我们仅假设每个数据点对损失函数的贡献为Lipschitz且优化域是有界的，从而为差分私有凸经验风险最小化提供了新的算法和匹配的下界。我们提供了一套单独的算法，并针对其中损失函数也很强凸的情况设置了匹配的下限。我们的算法以多项式时间运行，在某些情况下甚至匹配最佳的非私有运行时间（根据测量甲骨文的复杂性）。我们为（＆epsi ,, 0）-和（＆epsi ,,δ）-差分隐私提供了单独的算法（以及下限），也许令人惊讶，这两种情况下用于设计最佳算法的技术是完全不同的。我们的下限甚至适用于非常简单，平滑的函数族，例如线性和二次函数。这意味着在每个数据点对损失函数的贡献是平滑的附加假设下，可以使用先前工作中的算法来获得最佳错误率。我们表明，平滑任意损失函数（以应用先前的技术）的简单方法不会产生最佳错误率。尤其是，对于诸如训练支持向量机和高维中值之类的问题，最优算法以前是未知的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号