Technical Summary: A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input

Problem Statement

The paper addresses the problem of differentially private (DP) estimation of the second-moment matrix (equivalently, the covariance matrix) of a dataset in high-dimensional space ($\mathbb{R}^d$). While estimating this matrix is fundamental to machine learning and statistics, existing DP approaches often rely on restrictive assumptions, such as the input data being drawn from a Gaussian distribution or having well-conditioned eigenvalues.

The authors focus on a more general setting where the input data may exhibit significant variance differences across axes (large condition numbers) and may contain outliers. In such scenarios, standard concentration bounds often fail, and traditional DP algorithms (e.g., those relying on per-point bounded leverage scores) may incur prohibitive sample complexity or fail entirely if outliers possess high leverage. The core challenge is to achieve strong privacy-utility trade-offs for worst-case inputs that satisfy a specific structural property, without assuming the underlying distribution is Gaussian.

Methodology

The Subsamplability Assumption

The central theoretical contribution is the formalization of $(m, \alpha, \beta)$-subsamplability. A dataset $X$ is defined as $(m, \alpha, \beta)$-subsamplable if a random subsample of size $m$ (or larger) preserves the spectral structure of the original second-moment matrix $\Sigma$ up to a multiplicative factor of $(1 \pm \alpha)$ with probability at least $1 - \beta$.

• This assumption is weaker than standard matrix concentration bounds, which require such preservation for any $\alpha, \beta$ with a sufficiently large $m$. Here, the authors only require the existence of some $\alpha, \beta$ and a corresponding $m$.
• This property allows the algorithm to handle distributions with outliers, provided the outliers do not dominate the global spectral structure of random subsamples.

Algorithmic Framework

The authors propose a recursive algorithmic framework, building upon the approach of Kamath et al. (2019) but adapting it to the subsamplable setting rather than the Gaussian setting. The algorithm operates under the zero-Concentrated Differential Privacy (zCDP) framework.

1. Initialization: The algorithm assumes the input is bounded in $L_2$-norm by $R$ and that the second-moment matrix $\Sigma$ satisfies $I \preceq \Sigma \preceq R^2 I$. This is achieved by estimating the range $R$ and the minimum eigenvalue $\lambda_{\min}$ using existing DP tools.
2. Recursive Preconditioning:
   • In each iteration, noise is added to the empirical second-moment matrix to ensure privacy.
   • The algorithm identifies the subspace $V$ corresponding to large eigenvalues (those $\ge \psi \kappa$, where $\kappa$ is the current upper bound on eigenvalues).
   • A linear transformation $\Pi$ is applied to shrink the projection of data points onto $V$ by a factor of $\eta$ (specifically $\eta = 1/2$).
   • Crucially, unlike the Gaussian case where all points shrink uniformly, the authors must handle points whose norms exceed the new bound after transformation. They define a "tail set" $P_{tail}$ containing points that violate the subsamplability bounds.
   • The algorithm applies a shrinking function $S$ to points in $P_{tail}$ to force them into the new radius bound ($\sqrt{3/7}R$).
3. Tail Analysis: The analysis proves that points requiring shrinking belong to $P_{tail}$, which constitutes only a small fraction ($\approx \beta/m$) of the dataset. Furthermore, removing or shrinking these points does not significantly degrade the lower bound of the second-moment matrix of the remaining "good" data.
4. Termination: The recursion continues until the condition number $\kappa$ is reduced to a constant ($O(m)$). At this stage, simple noise addition suffices to achieve a $(1 \pm \gamma)$-approximation.

Baseline Comparison

The paper establishes a baseline using the Subsample-and-Aggregate framework (Nissim et al., 2007) combined with the convex semimetric space techniques of Ashtiani & Liaw (2022). This baseline provides a $(1 \pm 2\alpha)$-approximation but requires significantly higher sample complexity, particularly when dealing with outliers.

Key Contributions and Results

1. Recursive Algorithm for Subsamplable Inputs: The authors present a recursive algorithm that achieves a $(1 \pm \gamma)$-approximation of the second-moment matrix for any $(m, \alpha, \beta)$-subsamplable input. The algorithm satisfies $\rho$-zCDP.
2. Handling Outliers: The method is shown to be robust to a noticeable fraction of outliers. Specifically, for a mixture of a well-behaved distribution $D$ and an $\eta$-fraction of outliers, the algorithm succeeds provided the outliers' second-moment matrix $\Sigma_{out}$ satisfies $\Sigma_{out} \preceq O(1/\eta)\Sigma_D$.
3. Improved Sample Complexity:
   • For general distributions (including heavy-tailed ones), the proposed algorithm achieves a sample complexity of roughly $\tilde{O}\left(\frac{d}{\gamma^2} + \frac{d^{3/2}}{\gamma\sqrt{\rho}}\right)$.
   • In contrast, the Subsample-and-Aggregate baseline requires $\tilde{O}\left(\frac{d^2}{\epsilon \gamma^3}\right)$, which is significantly higher, especially in the presence of outliers where the baseline's requirement on the outlier fraction $\eta$ is much stricter ($\eta = O(1/m)$ vs. the proposed method's tolerance).
4. Formalization of Subsamplability: The paper provides a rigorous definition of subsamplability and demonstrates how it serves as a tractable proxy for controlling tail behavior without requiring strict Gaussian assumptions.

Significance and Claims

The authors claim that their work bridges the gap between private estimation for well-behaved (Gaussian) inputs and the more challenging reality of general, potentially heavy-tailed distributions with outliers.

• Robustness: The algorithm is tailored for second-moment estimation in regimes with large condition numbers, where previous methods (such as Brown et al., 2023) may incur significant errors if outliers correlate with directions of small eigenvalues.
• Weaker Assumptions: By relying on subsamplability rather than uniform leverage score bounds, the method tolerates the presence of multiple outliers, provided they do not dominate the overall spectrum of random subsamples.
• Utility: The paper demonstrates that strong utility guarantees (arbitrary $(1 \pm \gamma)$ approximation) are achievable even when the input range is significantly greater than the minimum eigenvalue, a scenario where standard DP techniques often struggle.

The authors explicitly note that while their analysis requires a bound on the $\beta$ parameter (related to the failure probability of subsampling) dependent on the range $R$, this is a trade-off that allows for handling well-behaved distributions with outliers. They identify replacing this dependency with an $O(1)$ bound as an interesting open problem. The work does not propose experimental validation on real-world datasets but provides theoretical guarantees and sample complexity bounds for specific distributional models, including truncated Pareto distributions and uniform distributions over convex ellipsoids.