論文の概要: Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model

• arxiv url: http://arxiv.org/abs/2606.07124v1
• Date: Fri, 05 Jun 2026 10:25:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.691655
• Title: Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model
• Title（参考訳）: 垂直分割分散モデルにおけるスパース共分散推定のための情報理論境界
• Authors: Jing Yee Tan, Guangyue Han,
• Abstract要約: 相互共分散の$C_21$に対して$s$-sparsityを要素的に課すことで、必要な通信やサンプルの複雑さを低減できることを示す。 被覆ネット量子化とエントリーワイドのハードしきい値化に基づくマッチングスキームを構築し,ポリ対数因子までの$s$スパースな下界を実現する。
• 参考スコア（独自算出の注目度）: 10.026496861838448
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the minimax estimation error for distributed covariance matrix estimation in the vertical-split (feature-split) setting, where two agents each observe different coordinates of $m$ i.i.d. sub-Gaussian samples and communicate a limited number of bits to a central server. While Rahmani et al. [2025] established nearly tight bounds for dense (unstructured) cross-covariance matrices, we investigate whether imposing elementwise $s$-sparsity on the cross-covariance $C_{21}$ can reduce the required communication and sample complexity. In contrast to the horizontal-split setting, where Braverman et al. [2016] showed that sparsity does not reduce communication cost for mean estimation, we prove that sparsity does help for cross-covariance estimation in the vertical split. Specifically, we establish minimax lower bounds showing that the communication budget per agent scales as $B_k = Ω(σ^4 d_k\, s' \log(d_1 d_2/s')/\varepsilon^2)$ and the sample complexity for cross-covariance estimation as $m = Ω(σ^4\, s' \log(d_1 d_2/s')/\varepsilon^2)$, where $s' = s \wedge d_{\min}$. For the $1$-sparse case, this yields an exponential improvement from $d_1 d_2$ to $\log(d_1 d_2)$ compared to the dense rate. Our lower bounds are established via Fano's method with an explicit sparse packing using a Varshamov--Gilbert-type argument for signed partial permutation matrices combined with the Conditional Strong Data Processing Inequality of Rahmani et al. [2025]. We show the bounds are tight with a matching achievable scheme, based on covering-net quantization and entry-wise hard thresholding, that attains the $s$-sparse lower bound up to polylogarithmic factors.
• Abstract（参考訳）: 垂直分割(Feature-split)設定における分散共分散行列推定の最小値推定誤差について検討し、各エージェントがそれぞれ$m$,d.sub-Gaussianサンプルの異なる座標を観測し、限られたビット数を中央サーバに伝達する。 ラーマニら[2025]は、密度(非構造)なクロス共分散行列のほぼ密接な境界を確立する一方で、クロス共分散の$C_{21}$に$s$スパーシティを要素的に課すことで、必要な通信とサンプルの複雑さを低減できるかどうかを調査する。 水平スプリット設定とは対照的に、Bravermanらによる2016年の研究では、平均推定における通信コストの減少は、スプリットが垂直分割における相互共分散推定に有効であることを証明している。 具体的には、エージェントごとの通信予算が$B_k = Ω(σ^4 d_k\, s' \log(d_1 d_2/s')/\varepsilon^2)$, $m = Ω(σ^4\, s' \log(d_1 d_2/s')/\varepsilon^2)$, $s' = s \wedge d_{\min}$であることを示す。 1ドルスパースの場合、これは高密度な速度と比較して、$d_1 d_2$から$\log(d_1 d_2)$への指数的な改善をもたらす。 符号付き部分置換行列に対するVarshamov-Gilbert型引数とRahmaniらによる条件付き強データ処理の不等式を併用した,明示的なスパースパッキングによるFano法により,下界が確立される。 有界線は、被覆ネット量子化とエントリーワイドのハードしきい値に基づく整合可能なスキームと密接な関係を示し、これはポリ対数因子までの$s$スパースな下界を実現する。

関連論文リスト

• Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
  1ビット通信制約を用いた分散平均推定問題について検討する。 私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
  論文  参考訳（メタデータ） (2025-09-26T06:22:57Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction [5.414308305392762]
  ガウス分布の平均ベクトルのロバストな推定問題について検討する。 スペクトル次元減少(SDR)に基づく推定器を導入し,その誤差に基づいて有限標本上限を確立する。 SDR推定器の分解点が、分解点の最大値である1/2$に等しいことを証明した。
  論文  参考訳（メタデータ） (2022-04-05T16:29:09Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。