Fugu-MT 論文翻訳(概要): Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model

論文の概要: 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（参考訳）: 垂直分割分散モデルにおけるスパース共分散推定のための情報理論境界
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$スパースな下界を実現する。

関連論文リスト

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文参考訳（メタデータ） (2026-08-06T19:49:48Z)
Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression [12.805268849262243]
我々はPolyak-Ruppert averaged gradient descent (SGD)のオンライン共分散行列推定について検討した。この構造は、このボトルネックがSGDドリフトからヘッセンの情報をサブ線形に蓄積していることを明らかにする。
論文参考訳（メタデータ） (2026-04-12T20:49:33Z)
Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
ランダム化しきい値クエリのみに基づく適応型平均推定器を提案する。我々の推定器のサンプル複雑性は、余分な乗法的な$O(log(/))$ペナルティを持つ。しきい値クエリとより一般的な間隔クエリの両方において、任意の非適応推定器のサンプル複雑性は線形にスケールしなければならない。
論文参考訳（メタデータ） (2026-04-09T04:49:21Z)
High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文参考訳（メタデータ） (2026-02-01T17:05:31Z)
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)
Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
論文参考訳（メタデータ） (2024-04-18T17:57:53Z)
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)
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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