Nonlinear Inference Learning for Differentially Private Massive Data

The paper is very difficult to understand, as it relies on the theory of nonlinear expectations that is not properly explained in the paper, and is used as if the readers were very familiar with the theory. As a result, it is not possible to tell why the $\hat{\theta}^{dp}_k$ estimator is defined the way it is, or whether this definition makes any sense. The explanation in Sections 2.3 and 3 need to be dramatically expanded, and the relevant parts of the underlying theory need to be explicitly introduced to account for the audience at an ML conference. Some of the notation is also not defined:

• $F$ in Section 2.1
• $n_k$, $\mathcal{F}_k$, $\Sigma$ in Section 2.3
• $S_0$ and $\lambda_0$ in Section 2.3, needed to calculate $\xi_1$
• $\overline{\lambda}$ and $\underline{\lambda}$ in Section 3

The sensitivity of $\hat{\theta}_k$ in the experiment is not correct. The datapoints in the experiment are sampled from a Gaussian, so they could be any real numbers, making the sensitivity infinite. Getting a finite sensitivity would be possible by clipping the datapoints, but that is not mentioned in the paper. Definition 1 also has this problem, as it is possible for the sensitivity to be infinite.

The paper does not make a clear connection to large-scale datasets, despite advertising it in the abstract and introduction. The related work that is discussed in the introduction is also mostly related to large-scale data analysis, and overlooks work on DP statistical inference. Two especially relevant works are Covington et al. (2021) and Evans et al. (2023), which propose similar DP inference methods that also use the bag of little bootstraps. These seem to solve the same problem the paper's method does, and should be compared with experimentally.

References:

• Covington et al. "Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy" arXiv 2021
• Evans et al. "Statistically Valid Inferences from Privacy-Protected Data" American Political Science Review 2023

Minor comments:

• "Gaussian differential privacy" refers to another definition of DP, not $(\epsilon, \delta)$-DP with the Gaussian mechanism. Replacing the phrase with "Gaussian mechanism" or something similar would be less confusing.
• $\delta = 0.01$ is very large compared to commonly used $\delta$ values. $\delta = 1 / n$ for $n$ datapoints allows mechanisms that are clearly non-private, so it is recommended to use $\delta \ll 1 / n$. Also, $\epsilon$ is typically the value that is varied to investigate different privacy strengths, not $\delta$.
• Font size in all figures is too small.
• Figures 4 and 5 referenced in Section 4 are missing.

1. Weak motivation. The motivation for the proposed algorithm is not convincing. It is claimed, in the last paragraph of Section 2.2, that there are two reasons for considering the paper's new algorithm: (1) dependence across bootstrap estimates, and (2) heteroskedasticity of Gaussian noise terms due to unequal sensitivities of the bags. It is unclear whether the proposed algorithm addresses either issue. The bootstrap estimates continue to be dependent in the proposed algorithm: the dependence is inherent to the bootstrap method/sampling with replacement, whether or not differential privacy is required. In fact, the very reason why Peng's central limit theorem is needed in the asymptotic analysis is the dependence across bootstrap estimates. For hetereoskedasticity, the additive noise terms in the proposed method remain heteroskedastic, just to a lesser degree: their variances are now one of the two values defined at the bottom of page 4, rather than B different values.

2. Questionable utility. On the point of turning B different noise variances into two different values, it raises further concerns about the proposed method’s utility. As the paper observes below Theorem 1, the resultant noise variances are guaranteed to be greater than their counterparts in the naive method. Then, it seems that the only gain from using the more sophisticated method proposed in this paper, is that there is a clean expression of asymptotic distribution. After all, the amount of noise added in the proposed method is greater than those in the naive method, and there is unlikely to be any improvement in statistical accuracy (unless the authors are able to prove that there is an improvement, either theoretically or numerically). Without justifying the benefit of using a more sophisticated method, the paper would read like studying a sophisticated method for the sake of studying it.

1. This paper lacks a detailed analysis of the proposed mechanism's computational complexity, which may limit its scalability to large datasets.

2. The paper does not consider addressing the impact of the proposed privacy-preserving mechanism on the utility of the data. In other words, it needs to evaluate how much information is lost because of the mechanism. Further studies are required to assess the trade-off between privacy and utility in the proposed mechanism.

1. The contributions of the paper are overstated. 'Pioneering differential privacy in static massive data' is not a fair claim; this is a subject that has received considerable prior attention in the literature. Moreover, the use of BLB in DP algorithms is not itself new, see both 'Statistically Valid Inferences from Privacy Protected Data' Evans et al. (2023) and 'Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy' Covington et al. (working paper). Both these papers use BLB within the sample-and-aggregate framework thus bypassing some of the theoretical problems this paper addresses, it is not clear why this approach was not taken in this paper?

2. More generally, the paper is lacking many relevant citations on statistical inference with DP.

3. The introduction needs to be re-written to convey the key ideas behind the methodology and how it contrasts to existing solutions.

4. Algorithm 1 seems incomplete, in particular it would be useful to map the computation steps to formulas, currently it would not be possible to implement this approach by looking at Algorithm 1 alone.

5. The simulation study is also very limited, showing just a small illustrative example of the method in a very simple setting. The evaluation metrics are also weak, why is the coverage and the validity of the variance estimate not shown? It also seems important to demonstrate the usefulness of the method for more sophisticated estimands since gaussian mean estimation with DP is already a well studies problem in the DP literature. If on the contrary the paper wants to claim this is a better method, than comparisons to existing algorithms should be given.