标题： 具有随机投影的最优差分隐私核学习 显示英文标题

标题： Optimal differentially private kernel learning with random projection

摘要： 差分隐私已成为隐私保护学习算法发展中的基石。 本工作针对经验风险最小化（ERM）框架内的差分隐私核学习进行了优化。 我们提出了一种基于再生核希尔伯特空间中随机投影的新型差分隐私核ERM算法，该算法使用高斯过程。 在局部强凸性条件下，我们的方法对于平方损失和Lipschitz光滑凸损失函数都达到了极小极大最优的额外风险。 我们进一步表明，基于其他维度约简技术（如随机傅里叶特征映射或$\ell_2$正则化）的现有方法，其泛化性能次优。 我们的关键理论贡献还包括对基于目标扰动的私有线性ERM的无维度泛化界限的推导——这是首个不依赖于噪声梯度机制的此类结果。 此外，我们得到了现有差分隐私核ERM算法更精确的泛化界限。 实证评估支持我们的理论结论，证明了随机投影能够实现统计上高效且最优私有的核学习。 这些发现为差分隐私算法的设计提供了新的见解，并突显了维度约简在平衡隐私与效用中的核心作用。 显示英文摘要

摘要： Differential privacy has become a cornerstone in the development of privacy-preserving learning algorithms. This work addresses optimizing differentially private kernel learning within the empirical risk minimization (ERM) framework. We propose a novel differentially private kernel ERM algorithm based on random projection in the reproducing kernel Hilbert space using Gaussian processes. Our method achieves minimax-optimal excess risk for both the squared loss and Lipschitz-smooth convex loss functions under a local strong convexity condition. We further show that existing approaches based on alternative dimension reduction techniques, such as random Fourier feature mappings or $\ell_2$ regularization, yield suboptimal generalization performance. Our key theoretical contribution also includes the derivation of dimension-free generalization bounds for objective perturbation-based private linear ERM -- marking the first such result that does not rely on noisy gradient-based mechanisms. Additionally, we obtain sharper generalization bounds for existing differentially private kernel ERM algorithms. Empirical evaluations support our theoretical claims, demonstrating that random projection enables statistically efficient and optimally private kernel learning. These findings provide new insights into the design of differentially private algorithms and highlight the central role of dimension reduction in balancing privacy and utility.