In this work, we investigate the problem of public data-assisted
non-interactive LDP (Local Differential Privacy) learning with a focus on
non-parametric classification. Under the posterior drift assumption, we for the
first time derive the mini-max optimal convergence rate with LDP constraint.
Then, we present a novel approach, the locally private classification tree,
which attains the mini-max optimal convergence rate. Furthermore, we design a
data-driven pruning procedure that avoids parameter tuning and produces a fast
converging estimator. Comprehensive experiments conducted on synthetic and real
datasets show the superior performance of our proposed method. Both our
theoretical and experimental findings demonstrate the effectiveness of public
data compared to private data, which leads to practical suggestions for
prioritizing non-private data collection.

在本研究中，我们通过公共数据辅助的非交互式 LDP（局部差分隐私）学习，重点研究非参数分类问题。在后验漂移假设下，我们首次推导了在 LDP 约束下的极小极大收敛速度。然后，我们提出了一种新颖的方法，即局部隐私分类树，它达到了极小极大收敛速度。此外，我们设计了一种数据驱动的修剪程序，避免了参数调整，并产生了一个快速收敛的估计器。对合成和真实数据集进行的全面实验证明了我们提出方法的卓越性能。无论是我们的理论发现还是实验结果都证明了与私有数据相比，公共数据的有效性，并提出了优先考虑非私有数据收集的实际建议。