Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency
  through MUltistage Sampling Technique (MUST)
Xingyuan Zhao Fang Liu
Applying a randomized algorithm to a subset of a dataset rather than the
entire dataset is a common approach to amplify its privacy guarantees in the
released information. We propose a class of subsampling methods named
MUltistage Sampling Technique (MUST) for privacy amplification (PA) in the
context of differential privacy (DP). We conduct comprehensive analyses of the
PA effects and utility for several 2-stage MUST procedures, namely, MUST.WO,
MUST.OW, and MUST.WW that respectively represent sampling with (W), without
(O), with (W) replacement from the original dataset in stage I and then
sampling without (O), with (W), with (W) replacement in stage II from the
subset drawn in stage I. We also provide the privacy composition analysis over
repeated applications of MUST via the Fourier accountant algorithm. Our
theoretical and empirical results suggest that MUST.OW and MUST.WW have
stronger PA in $\epsilon$ than the common one-stage sampling procedures
including Poisson sampling, sampling without replacement, and sampling with
replacement, while the results on $\delta$ vary case by case. We also prove
that MUST.WO is equivalent to sampling with replacement in PA. Furthermore, the
final subset generated by a MUST procedure is a multiset that may contain
multiple copies of the same data points due to sampling with replacement
involved, which enhances the computational efficiency of algorithms that
require complex function calculations on distinct data points (e.g., gradient
descent). Our utility experiments show that MUST delivers similar or improved
utility and stability in the privacy-preserving outputs compared to one-stage
subsampling methods at similar privacy loss. MUST can be seamlessly integrated
into stochastic optimization algorithms or procedures that involve parallel or
simultaneous subsampling (e.g., bagging and subsampling bootstrap) when DP
guarantees are necessary.