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 constantbounded 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)-subGaussian distributions. We first show that when (formual presented) and there is some public data, it is possible to achieve an upper bound of (formual presented) 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 minibatch 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 (formual presenetd). This shows that DP-MBGLMtron achieves the optimal utility bound up to logarithmic factors. Experiments further support our theoretical results.