From the source
Apple researchers show that private selection under standard noisy aggregation primitives inherently needs Ω(√d/ε) samples, then propose a new Sparse Vector Technique primitive to close the gap.
- The paper argues the limitation is inherent to the aggregation model rather than an artifact of particular algorithms.
- Adding an SVT primitive yields an ε-differentially private selection algorithm with additive error O(log(dn)/ε), matching the central model when n is polynomially bounded in d.
- The authors say the algorithm uses a near-optimal expected O(d log* d) SVT queries and that, with existing shuffle-model lower bounds, this establishes an exponential separation between the SVT model and shuffle or aggregation-based models.
- They also demonstrate the model's applicability to F_p loss minimization, heavy-hitter identification and sparse mean estimation.