Apple Machine Learning Research
·
用户级私有随机凸优化的更快算法
💡
原文英文，约300词，阅读约需1分钟。
📝
内容提要
我们研究了在用户级差分隐私约束下的私有随机凸优化。现有算法在大规模机器学习中不够实用。为此，我们提出了一种新算法，提供了更优的风险和运行时间保证，且不需要严格假设。我们开发了线性时间算法，适用于任意平滑损失，并在非平滑损失下也达到了最佳风险。
🎯
关键要点
-
研究用户级差分隐私约束下的私有随机凸优化。
-
现有算法在大规模机器学习中不够实用，主要原因包括对损失函数平滑性参数的严格假设和计算速度慢。
-
提出新算法，提供更优的风险和运行时间保证，无需严格假设。
-
开发线性时间算法，适用于任意平滑损失，并在非平滑损失下也达到了最佳风险。
-
第一个算法在温和平滑假设下实现了线性时间和最佳风险。
-
第二个算法适用于任意平滑损失，达到最佳风险的计算量为(mn)^(9/8)。
-
第三个算法针对非平滑损失函数，最佳风险的计算量为n^(11/8)m^(5/4)。
-
算法不要求用户数量与参数空间维度呈多项式增长。
➡️
