Statistical Properties of Nonparametric MLE under Laplace Noise

Problem Statement

The paper addresses the problem of recovering an unknown latent distribution $g_0$ from locally differentially private (LDP) observations. In the LDP setting, individual data points $\theta_i$ are privatized before release via an additive Laplace mechanism: $X_i = \theta_i + Z_i$, where $Z_i \sim \text{Lap}(0, b)$. The analyst observes only the privatized samples $X_1, \dots, X_n$, which are drawn from the convolution of the latent distribution and the Laplace kernel.

This setup creates a deconvolution problem where the goal is to estimate $g_0$ nonparametrically. The central tension identified is the trade-off between privacy and utility: stronger privacy (larger noise scale $b$) makes the inversion of the convolution less stable, complicating the recovery of the latent distribution. The paper focuses on the Nonparametric Maximum Likelihood Estimator (NPMLE) for this problem, specifically analyzing its computational tractability and statistical convergence rates under the 1-Wasserstein distance.

Methodology

1. Computational Reformulation (Support Reduction)
The authors first tackle the infinite-dimensional nature of the NPMLE optimization over the space of probability measures $\mathcal{P}([-a, a])$.

• Support Characterization: Leveraging the specific shape of the Laplace kernel (non-differentiable at the origin, strictly convex and decreasing on $(0, \infty)$), the authors prove that the support of any NPMLE solution must be contained within the set of observations projected onto the latent domain $[-a, a]$.
• Finite-Dimensional Reduction: This result reduces the optimization problem from searching over all mixing distributions to a strictly convex optimization over mixture weights assigned to the $n$ projected observations.
• Algorithm: Based on this reduction, the authors propose an Expectation-Maximization (EM) algorithm (Algorithm 1) that iteratively updates weights for the fixed support points, guaranteeing convergence to the unique global maximizer of the reduced log-likelihood.

2. Statistical Analysis (Deconvolution Inequality)
To analyze the convergence rate, the authors develop a new deconvolution inequality tailored to the Laplace mechanism.

• Metric: Estimation error is measured using the 1-Wasserstein distance ($W_1$), which is appropriate because the NPMLE is discrete even if the true $g_0$ is continuous.
• Inversion Argument: Adapting the frequency-splitting strategy from prior work (specifically [30]), the authors derive a bound on $W_1(g, g_0)$ in terms of the $L_1$ error of the privatized density estimates ($\|m_g - m_{g_0}\|_1$).
• Explicit Dependence: The derived inequality explicitly tracks the dependence on the noise scale $b$ and the support radius $a$. It involves balancing a smoothing bias term against high-frequency terms, leading to an optimized bandwidth choice.

3. Convergence Rates
The authors combine the deconvolution inequality with a Hellinger convergence rate for the privatized density (derived via convex-class maximum likelihood arguments) to establish the convergence rate of the NPMLE for the latent distribution.

Key Results

1. Consistency under Growing Noise
The paper establishes that the NPMLE remains consistent even when the privacy noise level $b_n$ increases with the sample size $n$.

• Sufficient Condition: The estimator is consistent ($W_1(\hat{g}_n, g_0) \to 0$ in probability) if the noise scale grows slower than $n^{3/16}(\log n)^{-1/2}$.
• Convergence Rate: For fixed $a$ and $b$, the convergence rate is $O_p(n^{-3/16}\sqrt{\log n})$. When $b_n$ grows, the rate is dominated by terms involving $b_n n^{-3/16}\sqrt{\log n}$.

2. Impossibility Result (Converse)
The authors provide a lower bound demonstrating the limits of recovery under high noise.

• Impossibility Regime: If the noise scale $b_n$ grows at a rate of $\Omega(\sqrt{n})$ (equivalently, if the privacy budget $\epsilon_n$ decays faster than $n^{-1/2}$), no estimator based on the privatized samples can achieve uniform consistency over the class of bounded distributions $\mathcal{P}([-a, a])$.
• This establishes a sharp gap between the sufficient condition for consistency ($n^{3/16}$) and the necessary condition for impossibility ($n^{1/2}$).

3. Empirical Findings
Numerical experiments validate the theoretical scaling behaviors:

• Error Behavior: The 1-Wasserstein error decreases as sample size $n$ increases and as the privacy budget $\epsilon$ increases.
• Support Size: Unlike Gaussian mixtures, where the NPMLE support size is known to be $O(\log n)$, the empirical active support size for Laplace mixtures grows polynomially with $n$ (faster than logarithmic) within the tested range.
• Noise Scaling: Experiments confirm that when the noise growth exponent $\alpha$ (where $b_n \propto n^\alpha$) exceeds $3/16$, the convergence slows, and at $\alpha = 1/2$, the error no longer decays, aligning with the impossibility result.

Significance and Claims

The paper claims to provide the first likelihood-based framework for recovering latent distributions from Laplace-privatized continuous data, explicitly characterizing the privacy-utility trade-off.

• Computational Contribution: It resolves the computational intractability of the NPMLE under Laplace noise by proving that the support is restricted to the projected observation set, enabling efficient EM algorithms.
• Statistical Contribution: It derives explicit convergence rates for the NPMLE under the 1-Wasserstein distance, linking the recovery rate directly to the privacy noise scale.
• Theoretical Limits: It identifies a specific regime ($n^{3/16}$ vs. $n^{1/2}$) where consistent recovery is possible versus impossible, highlighting the statistical cost of local differential privacy.

The authors note that while their analysis closes the gap between the existence of a consistent estimator and the impossibility of one, the precise optimal rate between $n^{-3/16}$ and $n^{-1/2}$ remains an open question. Additionally, they highlight that the behavior of the NPMLE support size under Laplace noise differs fundamentally from the Gaussian case, suggesting distinct geometric properties of the likelihood function.