Nearly Optimal Differentially Private ReLU Regression

摘要

In this paper, we investigate one of the most fundamental non-convex learning problems-ReLU regression-in the Differential Privacy (DP) model. Previous studies on private ReLU regression heavily rely on stringent assumptions, such as constant-bounded norms for feature vectors and labels. We relax these assumptions to a more standard setting, where data can be i.i.d. sampled from O(1)-sub-Gaussian distributions. We first show that when ε = Õ(√(1/N)) and there is some public data, it is possible to achieve an upper bound of O(d^2/N^2 ε^2) for the excess population risk in (ϵ, δ)-DP, where d is the dimension and N is the number of data samples. Moreover, we relax the requirement of ϵ and public data by proposing and analyzing a one-pass mini-batch Generalized Linear Model Perceptron algorithm (DP-MBGLMtron). Additionally, using the tracing attack argument technique, we demonstrate that the minimax rate of the estimation error for (ε, δ)-DP algorithms is lower bounded by Ω(d^2/N^2 ε^2). This shows that DP-MBGLMtron achieves the optimal utility bound up to logarithmic factors. Experiments further support our theoretical results.