We revisit the input perturbations framework for differential privacy where
noise is added to the input $A\in \mathcal{S}$ and the result is then projected
back to the space of admissible datasets $\mathcal{S}$. Through this framework,
we first design novel efficient algorithms to privately release pair-wise
cosine similarities. Second, we derive a novel algorithm to compute $k$-way
marginal queries over $n$ features. Prior work could achieve comparable
guarantees only for $k$ even. Furthermore, we extend our results to $t$-sparse
datasets, where our efficient algorithms yields novel, stronger guarantees
whenever $t\le n^{5/6}/\log n\,.$ Finally, we provide a theoretical perspective
on why \textit{fast} input perturbation algorithms works well in practice. The
key technical ingredients behind our results are tight sum-of-squares
certificates upper bounding the Gaussian complexity of sets of solutions.

重新审视了差分隐私的输入扰动框架，介绍了有效算法用于保护隐私的发布余弦相似度和计算多特征边际查询，扩展结果适用于稀疏数据集，提供理论视角解释快速输入扰动算法在实践中的良好表现。