We consider the differentially private estimation of multiple quantiles (MQ) of a distribution from a dataset, a key building block in modern data analysis. We apply the recent non-smoothed Inverse Sensitivity (IS) mechanism to this specific problem. We establish that the resulting method is closely related to the recently published ad hoc algorithm JointExp. In particular, they share the same computational complexity and a similar efficiency. We prove the statistical consistency of these two algorithms for continuous distributions. Furthermore, we demonstrate both theoretically and empirically that this method suffers from an important lack of performance in the case of peaked distributions, which can degrade up to a potentially catastrophic impact in the presence of atoms. Its smoothed version (i.e. by applying a max kernel to its output density) would solve this problem, but remains an open challenge to implement. As a proxy, we propose a simple and numerically efficient method called Heuristically Smoothed JointExp (HSJointExp), which is endowed with performance guarantees for a broad class of distributions and achieves results that are orders of magnitude better on problematic datasets.
翻译:我们认为,从数据集(现代数据分析中的一个关键组成部分)对多种量的分布进行不同的私人估计(MQ),这是现代数据分析中的一个关键组成部分。我们应用了最近的非移动反反感(IS)机制来应对这一具体问题。我们确定,由此产生的方法与最近出版的特设算法United Expt 密切相关。特别是,它们具有相同的计算复杂性和类似效率。我们证明这两种算法在统计上的一致性,用于连续分布。此外,我们从理论上和从经验上证明,在最高峰的分布中,这种方法因业绩严重不足而受到损害,在原子存在的情况下,这种分布可能退化为潜在的灾难性影响。其平滑的版本(即对产出密度应用最大内核)将解决这一问题,但仍然是有待执行的公开挑战。作为一个代理,我们提出了一种简单和数字效率高的方法,称为Heuristicist-lumed Compute Explex(HSUID),该方法为广泛的分布提供业绩保障,并取得在有问题数据集上更好的数量级的结果。