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

기술 요약: 수직 분할 분산 모델에서의 희소 공분산 추정을 위한 정보 이론적 경계

문제 정식화
본 논문은 수직 분할(특징 분할, vertical-split/feature-split) 설정에서의 분산 공분산 행렬 추정(DCME)에 대한 미니맥스 추정 오차를 조사한다. 이 모델에서 $K=2$인 에이전트들은 동일한 $m$개의 독립 항등 분포(i.i.d.) 샘플로부터 추출된 $d$차원 서브 가우시안 분포를 관찰하지만, 각 에이전트는 서로 겹치지 않는 좌표의 부분 집합만을 관찰한다. 구체적으로, 에이전트 1은 첫 $d_1$개의 좌표를 관찰하고, 에이전트 2는 나머지 $d_2$개의 좌표를 관찰한다.

주요 추정 대상은 교차 공분산 행렬(cross-covariance matrix) $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}$이다. 대각 블록($C_{11}$ 및 $C_{22}$)은 통신 없이 로컬하게 추정될 수 있으므로, 통신 비용은 $C_{21}$을 추정하기 위한 필요성에 의해 결정된다. 에이전트들은 제한된 비트 예산 $B_1$과 $B_2$로 자신의 로컬 데이터를 압축하여 중앙 서버로 전송한다.

본 논문은 교차 공분산 행렬 $C_{21}$이 **$s$-희소(s-sparse)**한 경우, 즉 최대 $s$개의 0이 아닌 성분을 포함하는 경우에 초점을 맞춘다. 핵심 질문은 이러한 구조적 희소성이 (희소성이 통신 비용을 줄이지 못한다고 이전에 밝혀진 수평 분할 설정과 대조적으로) 통신 예산 및 샘플 복잡도를 줄일 수 있는지 여부이다.

방법론
저자들은 하한(lower bounds)을 설정하고 이에 부합하는 달성 가능한 스킴(achievable scheme)을 구축하기 위해 정보 이론적 프레임워크를 사용한다.

1. 하한 (Converse):

   • 보조 무작위성을 이용한 파노의 방법(Fano's Method with Auxiliary Randomness): 증명에는 평균화된 버전의 파노 부등식이 사용된다. 교차 공분산 행사가 부호가 있는 부분 치환 행렬(signed partial permutation matrices)에 의해 섭동(perturbation)된 가설 패밀리가 구성된다.
   • 희소 패킹(Sparse Packing): $s'$-희소 부호 부분 치환 행렬($s' = s \wedge d_{\min}$)에 대한 패킹 집합을 구성하는 것이 핵심적인 조합론적 기여이다. 저자들은 부분 치환 제약 조건에 맞게 Raskutti 등[2011]의 확률적 논증을 적응시켜, 해밍 거리(Hamming distance) 상에서 서로 분리된 커다란 집합의 존재를 증명한다.
   • 조건부 강한 데이터 처리 부등식(C-SDPI): 에이전트 간의 상관관계(동일한 기저 샘플을 관찰하므로)를 처리하기 위해, 본 논문은 Rahmani 등[2025]이 도입한 C-SDPI 프레임워크에 의존한다. 이 부등식은 미지의 교차 공분산이 상태(state)인 상태-의존적 채널을 통한 정보 수축을 정량화한다. 저자들은 무작위 서포트 패턴(보조 변수 $W$를 통해)에 대해 평균을 취함으로써 계산 가능한 C-SDPI 계수를 도출한다.
   • 가설 분리: 가설 간의 분리는 푸로베니우스 노름(Frobenius norm)에서 측정되며, 이는 기저의 희소 행렬과 해밍 거리 사이의 등거리 사상(isometry)과 연결된다.

2. 달성 가능성 (Direct):

   • 프로토콜 설계: 저자들은 커버링-넷 양자화(covering-net quantization)(밀집한 부분의 데이터를 위해)와 성분별 하드 임계값 처리(entry-wise hard thresholding)(희소성을 활용하기 위해)를 결합한 분산 프로토콜을 제안한다.
   • 단계: 에이전트들은 로컬 자기 공분산을 추정하고 이를 양자화한다. 교차 공분산의 경우, 에이전트들은 데이터를 서브샘플링하고 커버링 넷을 사용하여 데이터 벡터를 양자화한다. 중앙 서버는 경험적 교차 공분산을 재구성한 후, 작은 값들을 0으로 설정하는 하드 임계값을 적용한다.
   • 분석: 오차 분석은 양자화 노이즈와 통계적 노이즈로 분해된다. 결정적으로, 저자들은 교차 공분산 항에서 발생하는 서브 엑스포넨셜 곱(sub-exponential products)에 대한 집중 부등식을 활용하여 통계적 오차를 제한하며, 이는 밀집한 경우에는 필요하지 않은 과정이다.

주요 기여 및 결과

• 수직 분할에서 희소성이 통신을 감소시킴: 본 논문은 평균 추정에서의 수평 분할 설정과 달리, 수직 분할에서의 교차 공분산 추정에서는 희소성이 통신 비용을 줄인다는 것을 증명한다.
• 미니맥스 하한:
  • 푸로베니우스 노름 하의 $s$-희소 교차 공분산 추정을 위해, 에이전트당 통신 예산 $B_k$는 다음과 같이 스케일링되어야 한다:
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • 샘플 복잡도 $m$은 다음과 같이 스케일링되어야 한다:
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • 여기서 $s' = s \wedge d_{\min}$이다. 1-희소($s=1$) 사례의 경우, 이는 차원 의존성을 $d_1 d_2$(밀집한 비율)에서 $\log(d_1 d_2)$로 줄임으로써 지수적인 개선을 제공한다.
• 일치하는 달성 가능성: 제안된 프로토콜은 로그 다항식 인자(polylogarithmic factors) 차이 내에서 유도된 하한을 달성하여 경계의 타이트함(tightness)을 확인한다.
• 조합론적 보조정리: 본 논문은 $s'$-희소 부호 부분 치환 행렬에 대한 새로운 패킹 결과를 확립하며, 크기가 대략 $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$이고 쌍별 해밍 거리가 $s'/2$보다 큰 집합의 존재를 보여준다.

의의 및 주장
본 논문은 희소성이 수직 분할 모델에 미치는 영향에 관한 Rahmani 등[2025]의 미결 과제를 해결한다고 주장한다. 저자들은 희소성이 개선되는 구조적 이유가 수직 분할 프레임워크가 패킹 수(packing number)가 규정하는 것 이상으로 통신 하한을 부풀리는 메커니즘이 결여되어 있기 때문임을 입증한다. 가설 공간을 $s'$-희소 행렬로 제한함으로써, 패킹 수(및 따라서 가설을 구별하기 위해 필요한 정보량)가 $\log |V| \sim d_1 d_2$에서 $\log |V| \sim s' \log(d_1 d_2 / s')$로 감소한다.

이 결과는 다중 오믹스 연구(서로 다른 생물학적 특징 집합 간의 상관관계)나 금융(거래 기록과 신용 기록의 연결)과 같이 교차 에이전트 의존성이 본질적으로 희소한 분산 시스템에서 매우 중요하다. 본 논문은 밀집한 경우가 주변 차원의 곱에 선형적인 통신을 요구하는 반면, 희소한 경우는 통신이 고유 차원 $s'$에 따라 스케일링될 수 있어 상당한 효율성 이득을 제공한다고 언급한다.

저자들은 향-후 과제에 대해 겸허한 태도를 유지하며, 특히 제안된 달성 가능 스킴이 임계값을 조정하기 위해 희소도 $s$에 대한 사전 지식을 필요로 한다는 점을 명시한다. $s$를 모르는 상태에서 동일한 비율을 달성할 수 있는 프로토콜이 존재하는지는 여전히 열린 문제이다. 마찬가지로, 이러한 결과들을 다른 구조적 가정(예: 저계수(low-rank), 밴드(banded) 또는 그룹 희소성)으로 확장하는 것이 향후 연구 방향으로 식별되었다.