提出一种更高效的差分隐私坐标下降法，可提升隐私保护下的优化效率。
Differentially Private Random Block Coordinate Descent
- 基于随机块坐标选择与拟矩阵采样，实现差分隐私保护。
- 在相同隐私预算下，收敛速度优于经典方法，提升优化效率。
- 适合处理高维敏感数据的机器学习任务，如医疗或金融建模。
坐标下降（CD）方法因在高维问题求解中的有效性及任务分解能力而受到广泛关注。然而，传统CD方法并未针对数据隐私设计或分析，这在处理敏感信息时构成关键挑战。为此，已有如DP-CD（Mangold等，ICML 2022）等差分隐私CD方法提出，但其性能仍落后于非私有化版本。本文提出一种新的差分隐私随机块坐标下降方法，在每轮迭代中通过拟矩阵以不同概率选择多个坐标。该算法同时推广了DP-CD与经典DP-SGD，且保持相同的隐私效用保证。此外，我们证明重要性采样可进一步提升效用：由于方法利用了坐标光滑性常数的异质性，从而获得更优的收敛速率。
原文摘要 · Abstract (English)
Coordinate Descent (CD) methods have gained significant attention in machine learning due to their effectiveness in solving high-dimensional problems and their ability to decompose complex optimization tasks. However, classical CD methods were neither designed nor analyzed with data privacy in mind, a critical concern when handling sensitive information. This has led to the development of differentially private CD methods, such as DP-CD (Differentially Private Coordinate Descent) proposed by Mangold et al. (ICML 2022), yet a disparity remains between non-private CD and DP-CD methods. In our work, we propose a differentially private random block coordinate descent method that selects multiple coordinates with varying probabilities in each iteration using sketch matrices. Our algorithm generalizes both DP-CD and the classical DP-SGD (Differentially Private Stochastic Gradient Descent), while preserving the same utility guarantees. Furthermore, we demonstrate that better utility can be achieved through importance sampling, as our method takes advantage of the heterogeneity in coordinate-wise smoothness constants, leading to improved convergence rates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。