论文标题
在当地差异隐私下支持恢复的阶段过渡
Phase transitions for support recovery under local differential privacy
论文作者
论文摘要
我们在高维但稀疏的平均模型中解决了可变选择的问题，这是在仅私有化数据可用于推断的附加约束下。原始数据是具有对称，强烈的log-conconcave分布的独立条目，上面是$ \ mathbb {r} $。为此，我们将最近对经典最小值理论的概括用于本地$α-$差异隐私的框架。我们提供了最高限制损失的收敛速度的下限和上限，最多$ s $ s $ -sparse向量的非零坐标从$ 0 $分开，而不是常数$ a> 0 $。作为推论，我们得出了必要和充分的条件（最终到对数因素），以确切恢复和几乎完全恢复。当我们将注意力限制为在每个协调下独立起作用的非相互作用机制时，我们的下限表明，与非私有化的环境相反，无论是在高维度中的$ a $ a $的价值，所以$nα^2/ d^2/ d^2^2^2 \ silysim 1 $不可能确切和几乎完全恢复。但是，在制度$nα^2/d^2 \ gg \ log（d）$中，我们可以表现出关键值$ a^*$（达到对数因素），因此所有$ a \ gg a^*$的精确且几乎是完全恢复的，对于$ a \ a \ leq a^*$不可能。我们表明，在允许所有非相互作用（全球在所有坐标上起作用）局部$α-$差异化机制时，可以改善这些结果，从而在较低级别上发生相变。
We address the problem of variable selection in a high-dimensional but sparse mean model, under the additional constraint that only privatised 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 generalisation of classical minimax theory to the framework of local $α-$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 α^2/ d^2\lesssim 1$. However, in the regime $nα^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 $α-$differentially private mechanisms in the sense that phase transitions occur at lower levels.
