Technical Summary: Multiple Testing of Linear Forms for Noisy Matrix Completion

1. Problem Statement

The paper addresses the challenge of performing multiple hypothesis testing within the framework of noisy matrix completion. While matrix completion techniques are well-established for estimating low-rank matrices from sparse observations (e.g., in recommender systems), the statistical inference of specific entries or linear combinations of entries remains difficult, particularly when controlling for multiple testing errors.

The core problem is formulated as testing a family of null hypotheses regarding linear forms of an unknown low-rank matrix $M \in \mathbb{R}^{d_1 \times d_2}$:
$$H_{0,T}: \langle M, T \rangle = \theta_T \quad \text{vs.} \quad H_{a,T}: \langle M, T \rangle \neq \theta_T$$
where $T$ represents a test matrix (e.g., $e_i e_j^\top$ for a specific entry, or differences between entries). The observations follow a trace regression model $Y = \langle M, X \rangle + \xi$, where $X$ is sampled uniformly from an orthonormal basis and $\xi$ is sub-Gaussian noise.

The authors highlight two primary challenges specific to this setting:

1. Bias-Variance Tradeoff: Standard estimators for matrix entries often suffer from bias or inflated variance, making it difficult to construct test statistics with sharp asymptotic normality.
2. Intricate Dependence: Due to the low-rank structure, the estimated entries are highly dependent. This dependence complicates the control of the False Discovery Rate (FDR), as standard methods often assume independence or weak dependence among test statistics.

2. Methodology

The proposed framework consists of three main components: a novel individual test statistic, a symmetric data aggregation scheme, and a whitening/screening procedure for highly correlated cases.

2.1. Improved Individual Test Statistic

To address the bias-variance tradeoff, the authors propose a three-step procedure to estimate $\langle M, T \rangle$:

1. Gradient Descent Initialization: An initial rank-$r$ estimator $\hat{M}^{\text{init}}$ is obtained via gradient descent.
2. Bias Correction: A debiased estimator $\hat{M}^{\text{unbs}}$ is constructed by adding a correction term based on the residuals of the initial estimate.
3. Incoherence-Assisted Low-Rank Projection: Unlike standard SVD projection, the authors project the debiased estimator onto the tangent space of the low-rank manifold using the singular vectors of the initial estimator ($\hat{U}^{\text{init}}, \hat{V}^{\text{init}}$). This step, defined as $\hat{M} = \hat{U}\hat{U}^\top \hat{M}^{\text{unbs}} \hat{V}\hat{V}^\top$, reduces variance while maintaining bias control.

The resulting test statistic $W_T$ is shown to converge to a standard normal distribution at a rate faster than existing methods (e.g., Xia and Yuan, 2021; Chen et al., 2019), both marginally and jointly. The variance is characterized by $\|P_M(T)\|_F$, where $P_M$ is the projection onto the tangent space of the low-rank manifold at $M$.

2.2. Symmetric Data Aggregation (SDA)

To control the FDR in the presence of dependence, the authors employ a data splitting and symmetric aggregation strategy:

1. Splitting: The data is split into two independent subsets, $D_1$ and $D_2$.
2. Independent Statistics: Two independent test statistics, $W_T^{(1)}$ and $W_T^{(2)}$, are constructed from $D_1$ and $D_2$ respectively.
3. Aggregation: A new statistic is formed by multiplication: $W_T^{\text{rank}} = W_T^{(1)} W_T^{(2)}$.
4. Thresholding: Under the null hypothesis, $W_T^{\text{rank}}$ is approximately symmetric about zero. The threshold $L$ is chosen such that the ratio of negative to positive statistics below and above $L$ controls the False Discovery Proportion (FDP). Specifically, $L$ is the smallest value satisfying:
   $$\frac{|\{T : W_T^{\text{rank}} < -L\}|}{|\{T : W_T^{\text{rank}} > L\}| \vee 1} \leq \alpha$$

This approach leverages the symmetry of the null distribution to estimate the number of false discoveries without requiring explicit knowledge of the dependence structure, provided the dependence is not too strong.

2.3. Whitening and Screening

For scenarios where test statistics are strongly correlated (e.g., testing an entire row or block), the SDA method alone may fail. The authors propose a whitening and screening procedure:

1. Correlation Estimation: An estimate of the correlation matrix $R$ of the test statistics is derived from the initial estimator.
2. Whitening: The statistics are transformed using $R^{-1/2}$ to decorrelate them.
3. Screening: A Lasso estimator is applied to the whitened statistics to select a subset of potential signals (support set $A$).
4. Aggregation: The SDA procedure is then applied only to the selected subset $A$. This reduces the effective dependence and improves FDR control in highly correlated settings.

3. Key Contributions and Results

3.1. Theoretical Guarantees

• Sharp Asymptotics: The paper proves that the proposed test statistic $W_T$ achieves asymptotic normality with a convergence rate controlled by the sample size $n$ and signal-to-noise ratio (SNR), independent of the dimension $d_1, d_2$ under certain conditions. This is faster than previous bounds involving $\sqrt{\log(d_1)/d_2}$.
• Minimax Optimality: The length of the confidence interval derived from the method is shown to be minimax optimal.
• FDR Control:
  • Weak Dependence: Under the condition that the proportion of strongly correlated pairs ($\beta_s$) is small relative to the number of strong signals ($\eta_n$), the SDA method asymptotically controls the FDP at level $\alpha$.
  • Strong Dependence: With the whitening and screening procedure, FDR control is maintained even when the initial statistics are highly correlated, provided the signal strength is sufficient.
• Robustness: The framework is extended to handle heterogeneous noise (where variance depends on the observation location) and non-uniform sampling, though the latter requires additional assumptions for rigorous proof.

3.2. Numerical Experiments

• Simulation: The authors demonstrate that their variance estimator leads to a more accurate asymptotic normal approximation compared to existing methods, particularly for smaller sample sizes.
• Data Aggregation: In simulations, the multiplicative aggregation (SDA) outperforms other aggregation schemes (minimum, addition) and the standard Benjamini-Hochberg (BH) procedure in terms of both power and FDR control, especially in weakly dependent settings.
• Correlation Handling: In highly correlated settings (e.g., row-wise comparisons), the whitening and screening method successfully controls FDR where simple aggregation fails, while maintaining higher power than conservative alternatives like factor-adjusted testing.
• Real Data:
  • MovieLens: Applied to user-movie ratings, the method effectively controlled the FDP in entry-wise comparisons, outperforming BH and other aggregation methods.
  • Rossmann Sales: Demonstrated the method's utility in a dense, real-world sales dataset with masked entries, showing superior ROC curves compared to BH.

4. Significance and Claims

The paper claims to provide a general framework for multiple testing in noisy matrix completion, addressing a gap where existing methods either lack sharp asymptotic properties or fail to handle the complex dependence structures inherent in low-rank matrix estimation.

Key claims include:

• Novelty of Statistic: The proposed test statistic offers sharper asymptotics and faster convergence rates than prior works (Chen et al., 2019; Xia and Yuan, 2021), enabling valid inference with nearly optimal sample size requirements.
• Effective FDR Control: The symmetric data aggregation scheme provides a robust mechanism for FDR control that does not rely on the independence assumption, provided the dependence is not overwhelming.
• Practical Utility: The method is shown to be effective in practical recommender system scenarios, such as determining which items to recommend to ensure a certain percentage of relevance (FDR control).
• Extensibility: The framework is adaptable to heterogeneous noise and can be extended to tensor completion, though the latter presents additional technical challenges regarding singular subspace perturbations.

The authors remain modest regarding the scope, noting that establishing non-asymptotic bounds for non-uniform sampling without structural assumptions remains an open direction for future work. They also acknowledge that while the method is powerful, it relies on the underlying matrix being consistently recoverable (i.e., satisfying incoherence and SNR conditions).