Phase transitions for support recovery under local differential privacy (Q6062699)

Summary: We address the problem of variable selection in a high-dimensional but sparse mean model, under the additional constraint that only privatized data are available for inference. The original data are vectors with independent entries having a symmetric, strongly log-concave distribution on \(\mathbb{R}\). For this purpose, we adopt a recent generalization of classical minimax theory to the framework of local \(\alpha\)-differential privacy. We provide lower and upper bounds on the rate of convergence for the expected Hamming loss over classes of at most \(s\)-sparse vectors whose non-zero coordinates are separated from \(0\) by a constant \(a>0\). As corollaries, we derive necessary and sufficient conditions (up to log factors) for exact recovery and for almost full recovery. When we restrict our attention to non-interactive mechanisms that act independently on each coordinate our lower bound shows that, contrary to the non-private setting, both exact and almost full recovery are impossible whatever the value of \(a\) in the high-dimensional regime such that \(n \alpha^2/ d^2 \lesssim 1\). However, in the regime \(n\alpha^2 /d^2 \gg \log (d)\) we can exhibit a critical value \(a^*\) (up to a logarithmic factor) such that exact and almost full recovery are possible for all \(a\gg a^*\) and impossible for \(a\leq a^*\). We show that these results can be improved when allowing for all non-interactive (that act globally on all coordinates) locally \(\alpha\)-differentially private mechanisms in the sense that phase transitions occur at lower levels.