Summary
The paper looks at how well we can estimate sparse linear relationships from data while protecting each user's privacy in settings that shuffle user data. When no interaction is allowed between users and the server, the authors find a fundamental limit that ties the error to the problem's dimensions. They propose an algorithm that nearly matches this limit but still depends heavily on the number of dimensions. To improve this, the authors design a method with two rounds of interaction that first identifies which variables matter, then estimates their values, achieving nearly optimal accuracy without depending much on the number of variables. They also prove a lower bound showing their method is close to the best possible.
What this means in practice
- •For data privacy engineers: Build privacy-preserving analytics for sparse data that balance accuracy and user-level data protection using shuffled privacy models.
- •For machine learning system developers: Implement two-round interactive protocols for private sparse feature estimation to improve learning accuracy without needing trusted data curators.
Authors
Yan Zhang, Jiong Tuo, Meng Ding, Yuheng Ma, Di Wang
Abstract
Sparse linear regression is a fundamental problem in high-dimensional statistics, and its private counterparts leave a large gap between the central and the local model of differential privacy. Shuffled differential privacy (SDP) sits between the two, offering accuracy closer to the central model without the trust requirement of a central curator. This paper studies sparse linear regression under both non-interactive and interactive SDP protocols. In the non-interactive setting, any non-interactive $(ε,δ)$-SDP protocol is shown to incur an $\ell_2$-norm estimation error of $Ω( \frac{\sqrt{dk}}{nε} )$ with dimension $d$, sparsity $k$, and $n$ users, revealing an inherent dimensionality barrier. In addition, a non-interactive algorithm is proposed that achieves an $\ell_2$-norm upper bound of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{n}} + \frac{d\sqrt{k}}{nε})$. To overcome this barrier, we turn to the interactive user-level setting, where each user holds $m$ samples. A two-round interactive algorithm is developed that first recovers the support through a heavy hitter step and then estimates the parameter, achieving an error of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{nm}} + \frac{k}{n\sqrt{m}ε} )$ with no polynomial dependence on $d$. Furthermore, by extending the score attack framework to user-level data, a new lower bound $Ω( \sqrt{\frac{k\log(d/k)}{nm}} + \frac{k\log(d/k)}{n\sqrt{m}ε} )$ is established for any user-level $(ε,δ)$-DP, showing that the proposed algorithm is near-optimal with only a gap of the factor $\log(d/k)$.