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

Technisches Resümee: Informationstheoretische Schranken für die scharfe Kovarianzschätzung im vertikal gespaltenen verteilten Modell

Problemformulierung
Diese Arbeit untersucht den Minimax-Schätzfehler für die verteilte Kovarianzmatrix-Schätzung (Distributed Covariance Matrix Estimation, DCME) im vertikal gespaltenen (Feature-Split) Szenario. In diesem Modell beobachten $K=2$ Agenten denselben Satz von $m$ identisch und unabhängig verteilten (i.i.d.) Stichproben aus einer sub-Gaußschen Verteilung, wobei jedoch jeder Agent nur eine disjunkte Teilmenge der Koordinaten beobachtet. Konkret beobachtet Agent 1 die ersten $d_1$ Koordinaten und Agent 2 die verbleibenden $d_2$ Koordinaten.

Das primäre Schätzziel ist die Kreuzkovarianzmatrix $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}$. Die Diagonalelemente ($C_{11}$ und $C_{22}$) können lokal ohne Kommunikation geschätzt werden; daher wird die Kommunikationskosten durch die Notwendigkeit der Schätzung von $C_{21}$ getrieben. Die Agenten komprimieren ihre lokalen Daten in begrenzte Bit-Budgets $B_1$ und $B_2$ und übertragen diese an einen zentralen Server.

Die Arbeit konzentriert sich auf das Szenario, in dem die Kreuzkovarianzmatrix $C_{21}$ $s$-schärfe (sparse) ist, was bedeutet, dass sie höchstens $s$ Nicht-Null-Einträge enthält. Die zentrale Frage ist, ob diese strukturelle Sparsity das erforderliche Kommunikationsbudget und die Stichprobenkomplexität im Vergleich zum dichten (unstrukturierten) Fall reduzieren kann, im Gegensatz zum horizontal gespaltenen Setting, in dem zuvor gezeigt wurde, dass Sparsity die Kommunikationskosten für die Mittelwertschätzung nicht reduziert.

Methodik
Die Autoren verwenden einen informationstheoretischen Rahmen, um untere Schranken zu etablieren und ein passendes erreichbares Schema zu konstruieren.

1. Untere Schranken (Konverse):

   • Fanos Methode mit Hilfsrandomisierung: Der Beweis nutzt eine gemittelte Version der Fano-Ungleichung. Eine Hypothesenfamilie wird konstruiert, bei der die Kreuzkovarianzmatrizen durch signierte partielle Permutationsmatrizen gestört werden.
   • Sparse Packing: Ein wesentlicher kombinatorischer Beitrag ist die Konstruktion einer Packing-Menge für $s'$-scharfe signierte partielle Permutationsmatrizen (wobei $s' = s \wedge d_{\min}$). Die Autoren beweisen die Existenz einer großen Menge solcher Matrizen, die paarweise in der Hamming-Distanz getrennt sind, indem sie das probabilistische Argument von Raskutti et al. [2011] an die Einschränkung der partiellen Permutation anpassen.
   • Conditional Strong Data Processing Inequality (C-SDPI): Um die Korrelation zwischen den Daten der Agenten zu handhaben (da sie dieselben zugrunde liegenden Stichproben beobachten), stützt sich die Arbeit auf den C-SDPI-Rahmen, der von Rahmani et al. [2025] eingeführt wurde. Diese Ungleichung quantifiziert die Informationskontraktion durch einen zustandsabhängigen Kanal, wobei der Zustand die unbekannte Kreuzkovarianz ist. Die Autoren zeigen, dass das Mitteln über die zufälligen Support-Muster (via der Hilfsvariablen $W$) eine handhabbare Berechnung des C-SDPI-Koeffizienten ermöglicht.
   • Hypothesenseparation: Die Separation zwischen Hypothesen wird in der Frobenius-Norm gemessen, die mit der Hamming-Distanz der zugrunde liegenden scharfen Matrizen über eine Isometrie verknüpft ist.

2. Erreichbarkeit (Direkt):

   • Protokolldesign: Die Autoren schlagen ein verteiltes Protokoll vor, das Covering-Net-Quantisierung (für die dichten Teile der Daten) mit punktweiser Hard-Thresholding (zur Ausnutzung der Sparsity) kombiniert.
   • Schritte: Die Agenten schätzen lokal die Selbst-Kovarianzen und quantisieren diese. Für die Kreuzkovarianz subsamplen die Agenten ihre Datenvektoren und quantisieren diese mittels Covering-Nets. Der zentrale Server rekonstruiert die empirische Kreuzkovarianz und wendet ein Hard-Thresholding auf die Einträge an, wobei kleine Werte auf Null gesetzt werden.
   • Analyse: Die Fehleranalyse zerlegt die Verzerrung (Distortion) in Quantisierungsrauschen und statistisches Rauschen. Entscheidend ist, dass die Autoren Konzentrationsungleichungen für sub-exponentielle Produkte (die aus den Kreuzkovarianz-Termen resultieren) nutzen, um das statistische Rauschen zu begrenzen, was im dichten Fall nicht erforderlich ist.

Wesentliche Beiträge und Ergebnisse

• Sparsity reduziert die Kommunikation im vertikalen Split: Die Arbeit beweist, dass – anders als im horizontal gespaltenen Setting für die Mittelwertschätzung – Sparsity die Kommunikationskosten für die Kreuzkovarianzschätzung im vertikalen Split tatsächlich reduziert.
• Minimax untere Schranken:
  • Für die $s$-scharfe Kreuzkovarianzschätzung unter der Frobenius-Norm muss das Kommunikationsbudget pro Agent $B_k$ wie folgt skalieren:
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • Die Stichprobenkomplexität $m$ muss wie folgt skalieren:
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • Hierbei ist $s' = s \wedge d_{\min}$. Im 1-scharfen Fall ($s=1$) ergibt dies eine exponentielle Verbesserung der Dimensionsabhängigkeit, indem der Faktor von $d_1 d_2$ (dichte Rate) auf $\log(d_1 d_2)$ reduziert wird.
• Matching Erreichbarkeit: Das vorgeschlagene Protokoll erreicht die abgeleiteten unteren Schranken bis auf polylogarithmische Faktoren, was die Tightness der Schranken bestätigt.
• Kombinatorisches Lemma: Die Arbeit etabliert ein neues Packing-Resultat für $s'$-scharfe signierte partielle Permutationsmatrizen und zeigt die Existenz einer Menge der Größe etwa $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ mit einer paarweisen Hamming-Distanz von mehr als $s'/2$.

Bedeutung und Behauptungen
Die Arbeit behauptet, eine offene Frage zu klären, die von Rahmani et al. [2025] hinterlassen wurde, nämlich bezüglich des Einflusses von Sparsity im vertikal gespaltenen Modell. Die Autoren zeigen, dass der strukturelle Grund für die Verbesserung darin liegt, dass das vertikal gespaltene Framework keinen Mechanismus besitzt, um die Kommunikationsuntergrenze über das zu diktieren, was die Packing-Zahl vorgibt. Durch die Beschränkung des Hypothesenraums auf $s'$-scharfe Matrizen reduziert sich die Packing-Zahl (und damit die benötigte Information zur Unterscheidung von Hypothesen) von $\log |V| \sim d_1 d_2$ auf $\log |V| \sim s' \log(d_1 d_2 / s')$.

Dieses Ergebnis ist signifikant für verteilte Systeme, in denen die Kreuz-Agenten-Abhängigkeiten inhärent scharf sind, wie etwa in Multi-Omics-Studien (Korrelation verschiedener biologischer Merkmals-Sets) oder in der Finanzwelt (Verknüpfung von Transaktionshistorien mit Kreditdaten). Die Arbeit stellt fest, dass während der dichte Fall eine Kommunikation erfordert, die linear in der Produktdimension der Umgebung skaliert, der scharfe Fall eine Kommunikation ermöglicht, die mit der intrinsischen Dimension $s'$ skaliert, was erhebliche Effizienzgewinne bietet.

Die Autoren bleiben bescheiden hinsichtlich offener Probleme und weisen insbesondere darauf hin, dass ihr erreichbares Schema Vorwissen über das Sparsity-Niveau $s$ erfordert, um den Schwellenwert zu kalibrieren. Ob ein Protokoll dieselben Raten ohne Kenntnis von $s$ erreichen kann, bleibt eine offene Frage. Ebenso wird die Erweiterung dieser Ergebnisse auf andere strukturelle Annahmen (z. B. Low-Rank, Banded oder Group-Sparsity) als zukünftige Forschungsrichtung identifiziert.