Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model

Resumen Técnico: Límites de Información Teórica para la Estimación de Covarianza Dispersa en el Modelo Distribuido de División Vertical

Formulación del Problema
Este artículo investiga el error de estimación minimax para la estimación de la matriz de covarianza distribuida (DCME) en el escenario de división vertical (división de características). En este modelo, $K=2$ agentes observan el mismo conjunto de $m$ muestras independientes e idénticamente distribuidas (i.i.d.) de una distribución subgaussiana, pero cada agente observa solo un subconjunto disjunto de las coordenadas. Específicamente, el Agente 1 observa las primeras $d_1$ coordenadas y el Agente 2 observa las $d_2$ coordenadas restantes.

El objetivo principal de la estimación es la matriz de cocovarianza $C_{21} = \mathbb{E}[(X_2 - \mathbb{E}X_2)(X_1 - \mathbb{E}X_1)^\top] \in \mathbb{R}^{d_2 \times d_1}$. Los bloques diagonales ($C_{11}$ y $C_{22}$) pueden estimarse localmente sin comunicación; por lo tanto, el costo de comunicación está impulsado por la necesidad de estimar $C_{21}$. Los agentes comprimen sus datos locales en presupuestos de bits limitados $B_1$ y $B_2$ y los transmiten a un servidor central.

El artículo se centra en el escenario donde la matriz de cocovarianza $C_{21}$ es dispersa en $s$ (o $s$-sparse), lo que significa que contiene como máximo $s$ entradas no nulas. La cuestión central es si esta dispersión estructural puede reducir el presupuesto de comunicación y la complejidad de muestreo en comparación con el caso denso (no estructurado), contrastando esto con el escenario de división horizontal donde previamente se demostró que la dispersión no reduce los costos de comunicación para la estimación de la media.

Metodología
Los autores emplean un marco de información teórica para establecer límites inferiores y construir un esquema de alcanzabilidad coincidente.

1. Límites Inferiores (Converso):

   • Método de Fano con Aleatoriedad Auxiliar: La prueba utiliza una versión promediada de la desigualdad de Fano. Se construye una familia de hipótesis donde las matrices de cocovarianza son perturbadas por matrices de permutación parcial con signo.
   • Empaquetamiento Disperso (Sparse Packing): Una contribución combinatoria clave es la construcción de un conjunto de empaquetamiento para matrices de permutación parcial con signo de $s'$-dispersas (donde $s' = s \wedge d_{\min}$). Los autores demuestran la existencia de un gran conjunto de tales matrices que están separadas entre sí en distancia de Hamming, adaptando el argumento probabilístico de Raskutti et al. [2011] a la restricción de permutación parcial.
   • Desigualdad de Procesamiento de Datos Fuertes Condicional (C-SDPI): Para manejar la correlación entre los datos de los agentes (ya que observan la misma muestra subyacente), el artículo se apoya en el marco de C-SDPI introducido por Rahmani et al. [2025]. Esta desigualdad cuantifica la contracción de información a través de un canal dependiente del estado, donde el estado es la cocovarianza desconocida. Los autores muestran que el promedio sobre los patrones de soporte aleatorios (a través de la variable auxiliar $W$) permite un cálculo tratable del coeficiente de C-SDPI.
   • Separación de Hipótesis: La separación entre hipótesis se mide en la norma de Frobenius, vinculada a la distancia de Hamming de las matrices dispersas subyacentes mediante una isometría.

2. Alcanzabilidad (Directa):

   • Diseño de Protocolo: Los autores proponen un protocolo distribuido que combina la cuantización por red de cobertura (para las partes densas de los datos) con el umbralización dura elemento a elemento (para explotar la dispersión).
   • Pasos: Los agentes estiman localmente las autocovarianzas y las cuantifican. Para la cocovarianza, los agentes submuestrean y cuantizan sus vectores de datos utilizando redes de cobertura. El servidor central reconstruye la cocovarianza empírica y aplica un umbral duro a las entradas, estableciendo en cero aquellos valores pequeños.
   • Análisis: El análisis del error descompone la distorsión en ruido de cuantización y ruido estadístico. Crucialmente, los autores utilizan desigualdades de concentración para productos subexponenciales (derivados de los términos de cocovarianza) para acotar el error estadístico, algo que no es necesario en el caso denso.

Contribuciones Clave y Resultados

• La Dispersión Reduce la Comunicación en la División Vertical: El artículo demuestra que, a diferencia del escenario de división horizontal para la estimación de la media, la dispersión sí reduce el costo de comunicación para la estimación de la cocovarianza en la división vertical.
• Límites Inferiores Minimax:
  • Para la estimación de la cocovarianza $s$-dispersa bajo la norma de Frobenius, el presupuesto de comunicación por agente $B_k$ debe escalar como:
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • La complejidad de muestreo $m$ debe escalar como:
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • Aquí, $s' = s \wedge d_{\min}$. En el caso de 1-dispersión ($s=1$), esto produce una mejora exponencial en la dependencia de la dimensión, reduciendo el factor de $d_1 d_2$ (tasa densa) a $\log(d_1 d_2)$.
• Alcanzabilidad Coincidente: El protocolo propuesto alcanza los límites derivados hasta factores polilogarítmicos, confirmando la firmeza (tightness) de los límites.
• Lema Combinatorio: El artículo establece un nuevo resultado de empaquetamiento para matrices de permutación parcial con signo de $s'$-dispersas, mostrando la existencia de un conjunto de tamaño aproximadamente $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ con distancia de Hamming mutua mayor a $s'/2$.

Significado y Reivindicaciones
El artículo afirma resolver una pregunta abierta dejada por Rahmani et al. [2025] sobre el impacto de la dispersión en el modelo de división vertical. Los autores demuestran que la razón estructural de la mejora es que el marco de división vertical carece de un mecanismo para inflar el límite de comunicación más allá de lo que dicta el número de empaquetamiento. Al restringir el espacio de hipótesis a matrices de $s'$-dispersas, el número de empaquetamiento (y, por tanto, la información requerida para distinguir las hipótesis) se reduce de $\log |V| \sim d_1 d_2$ a $\log |V| \sim s' \log(d_1 d_2 / s')$.

Este resultado es significativo para sistemas distribuidos donde las dependencias entre agentes son inherentemente dispersas, como en estudios de multi-ómica (correlacionando diferentes conjuntos de características biológicas) o finanzas (vinculando historiales de transacciones con registros de crédito). El artículo señala que, mientras que el caso denso requiere una comunicación lineal en el producto de la dimensión ambiente, el caso disperso permite una comunicación que escala con la dimensión intrínseca $s'$, ofreciendo ganancias de eficiencia sustanciales.

Los autores mantienen la modestia respecto a problemas abiertos, específicamente señalando que su esquema de alcanzabilidad requiere el conocimiento previo del nivel de dispersión $s$ para calibrar el umbral. Si un protocolo puede alcanzar las mismas tasas sin conocer $s$ sigue siendo una pregunta abierta. Del mismo modo, la extensión de estos resultados a otras suposiciones estructurales (por ejemplo, de bajo rango, de banda o de dispersión de grupo) se identifica como una dirección para trabajos futuros.