Jun, 2024

通过懒惰算法实现私密在线学习

PDF
TL;DR我们研究了私密在线学习的问题，特别是专家预测（OPE）和在线凸优化（OCO）。我们提出了一种将惰性在线学习算法转化为私密算法的新方法。我们通过使用现有的惰性算法解决这些问题，将我们的转化应用于差分隐私 OPE 和 OCO。我们的最终算法在高隐私水平 ε≪1 下获得显著改进的后悔，对于 DP-OPE 为√(Tlogd) + (T^(1/3) log (d))/ε^(2/3)，对于 DP-OCO 为√T + (T^(1/3)√d)/ε^(2/3)。我们通过对 DP-OPE 进行下界的研究，进一步补充了我们的结果，表明这些速率对于一类自然的低转换私密算法来说是最优的。
private online learningonline predictiononline convex optimizationdifferential privacyregret
发现论文，激发创造
  • 改进的差分隐私和惰性在线凸优化

    研究目标为（ε, δ）- 差分隐私在线凸优化（OCO），通过引入强对数凹密度的抽样，提升维度因子并消除平滑性要求，进而改进了（ε）非常小的情况下 Agarwal 等人的结果，达到了该领域已知的最佳速率。

    Dec, 2023

  • 差分隐私在线学习

    本文研究了在在线凸规划框架下使用差分隐私作为正式隐私度量的隐私保护算法，提供了将在线算法转换为具有良好隐私保护性能的算法框架，特别是针对在线线性回归问题，提出一种具有 $log^{1.5} T$ 的担保损失差别隐私算法。

    Sep, 2011

  • 分散式在线凸优化的近优遗憾

    我们在分散的在线凸优化中（D-OCO），通过仅使用本地计算和通信来最小化一系列全局损失函数的一组本地学习器。我们首先开发了一种新颖的 D-OCO 算法，将凸函数和强凸函数的遗憾边界分别降低到 O (nρ^{−1/4}√T) 和 O (nρ^{−1/2} log T)。通过设计一种在线加速的谣言策略并巧妙利用特定网络拓扑的谱特性，我们进一步提高了凸函数和强凸函数的下界为 Ω(nρ^{−1/4}√T) 和 Ω(nρ^{−1/2})。

    Feb, 2024

  • 关于私人在线凸优化：在 $l_p$ 几何和高维情境赌徒中的最优算法

    研究了使用差分隐私保护的在线随机凸优化问题，提出了一种具有递归梯度的私有在线 Frank-Wolfe 算法，可在线性时间内实现最优超额风险，并证明递归梯度的方差缩减结果在非平稳场景下也有理论保证。同时，该算法也被扩展到 p=1 的情况，可实现几乎与维度无关的超额风险。

    Jun, 2022

  • 关于差分隐私在线学习中错误增长的下界透视

    对差分隐私在线学习算法提供了下界，表明广泛类别的（ε, δ）- 差分隐私在线算法 — 当满足 log T≤O (1/δ) 时，算法产生的错误数量的期望呈 Ω(log (T/δ)) 增长，与非隐私在线学习不同，其中错误数量与 T 无关。据我们所知，这是首次为差分隐私在线学习确定下界的结果，并在一定程度上解决了 Sanyal 和 Ramponi（2022）中的疑问。

    Feb, 2024

  • 分布式在线优化中处理延迟反馈：一种无投影的方法

    本研究中，我们在边缘学习方面进行了调查，探讨了在线凸优化问题下的对抗性延迟反馈，提出了两种无投影算法，用于集中式和分布式环境中，通过与现有方法在真实世界问题上的比较，我们理论上和实验证明了算法的性能，实现了延迟环境中 OCO 问题的 O (√B) 的后悔界。

    Feb, 2024

  • 随机约束下的在线凸优化

    本文研究带随机约束的在线凸优化问题，提出了一种算法，能够达到预期和高概率的收益掉队和约束违反值等性能保证，并在真实数据中心调度问题上进行了实验验证。

    Aug, 2017

  • 线性约束在线凸优化的乐观安全性

    在线凸优化（OCO）的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例，我们提供了一种算法来解决该问题，其后悔值为 O (√T)。这比之前最佳后悔边界 O (T^2/3) 有所改进，并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后，我们将该问题重新表述为随时间变化的随机线性约束下的 OCO 问题，并证明了我们的算法在这样的设置中具有相同的后悔保证，并且预期上不违反约束。这对于 OCO 在随时间变化的随机约束下的文献做出了贡献，其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有 O (√T) 的后悔和 O (√T) 的违规。此外，我们提供了更加高效的算法版本，并通过与基准算法进行了数值实验比较。

    Mar, 2024

  • 黑暗中的游戏：带有对抗性约束的无悔学习

    我们研究了经典的在线凸优化（OCO）框架的一种推广，通过考虑额外的长期对抗性约束。我们提出了一种元策略，能够同时达到亚线性的累积约束违规和亚线性的遗憾，通过将约束问题转化为递归构建的一系列代理代价函数的标准 OCO 问题的黑盒减缩。我们展示了通过使用任何享有标准数据相关遗憾上界的自适应 OCO 策略求解代理问题，可以达到最优性能界限。通过一种新的基于李雅普诺夫的证明技术，我们揭示了遗憾和某些顺序不等式之间的联系，通过一种新颖的分解结果。最后，我们强调了在在线多任务学习和网络控制问题中的应用。

    Oct, 2023

  • 基于 PDE 的无约束在线学习最优策略

    通过解偏微分方程生成新的势函数，得到一种新的算法，该算法的任何时候的失误上限达到了最佳损失后悔权衡，且避免了不实用的加倍技巧。

    Jan, 2022