Fugu-MT 論文翻訳(概要): Sparse Normal Means Estimation with Sublinear Communication

論文の概要: Sparse Normal Means Estimation with Sublinear Communication

arxiv url: http://arxiv.org/abs/2102.03060v1
Date: Fri, 5 Feb 2021 08:52:25 GMT
ステータス: 処理完了
システム内更新日: 2021-02-08 14:45:58.377332
Title: Sparse Normal Means Estimation with Sublinear Communication
Title（参考訳）: サブリニア通信によるスパースノーマル平均推定
Authors: Chen Amiraz, Robert Krauthgamer, Boaz Nadler
Abstract要約: 通信制約のある分散環境における正規平均推定の問題点を考察する。信号対雑音比(SNR)がわずかに高くなると、$mu$のサポートはより少ない通信で正確に回復できることを示す。
参考スコア（独自算出の注目度）: 13.257075075199781
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the problem of sparse normal means estimation in a distributed setting with communication constraints. We assume there are $M$ machines, each holding a $d$-dimensional observation of a $K$-sparse vector $\mu$ corrupted by additive Gaussian noise. A central fusion machine is connected to the $M$ machines in a star topology, and its goal is to estimate the vector $\mu$ with a low communication budget. Previous works have shown that to achieve the centralized minimax rate for the $\ell_2$ risk, the total communication must be high - at least linear in the dimension $d$. This phenomenon occurs, however, at very weak signals. We show that once the signal-to-noise ratio (SNR) is slightly higher, the support of $\mu$ can be correctly recovered with much less communication. Specifically, we present two algorithms for the distributed sparse normal means problem, and prove that above a certain SNR threshold, with high probability, they recover the correct support with total communication that is sublinear in the dimension $d$. Furthermore, the communication decreases exponentially as a function of signal strength. If in addition $KM\ll d$, then with an additional round of sublinear communication, our algorithms achieve the centralized rate for the $\ell_2$ risk. Finally, we present simulations that illustrate the performance of our algorithms in different parameter regimes.
Abstract（参考訳）: 通信制約のある分散環境におけるスパース正規平均推定の問題点を考察する。マシンには$m$があり、それぞれに$k$-sparseベクター$\mu$が付加ガウス雑音によって崩壊する様子をd$次元で観察していると仮定する。中央融合マシンはスタートポロジー内の$m$マシンに接続されており、その目標は低通信予算で$\mu$のベクトルを推定することである。以前の研究では、$\ell_2$リスクの集中的なミニマックスレートを達成するためには、総通信は高い必要があります - 少なくとも次元$d$の線形。しかし、この現象は非常に弱い信号で起こります。信号対雑音比(SNR)がわずかに高くなると、$\mu$のサポートはより少ない通信で正確に回復できることを示す。具体的には、分散スパース正規平均問題に対する2つのアルゴリズムを提案し、あるSNRしきい値を超えると、高い確率で、次元$d$のサブ線形な全通信で正しいサポートを回復することを示す。さらに、通信は信号強度の関数として指数関数的に減少する。さらに$KM\ll d$の場合、追加のサブ線形通信で、我々のアルゴリズムは$\ell_2$リスクの集中レートを達成する。最後に,様々なパラメータ領域におけるアルゴリズムの性能を示すシミュレーションを提案する。

関連論文リスト

Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-03-07T15:03:50Z)
Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文参考訳（メタデータ） (2023-05-10T20:29:29Z)
Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。グラフの構造は知られており、ノードは$N$である。頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-08-26T16:21:31Z)
DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文参考訳（メタデータ） (2022-07-26T08:47:54Z)
Settling the Communication Complexity for Distributed Offline Reinforcement Learning [10.315054389907031]
オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。各マシンが送信できる情報の総数(ビット数)には予算の制約がある。文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
論文参考訳（メタデータ） (2022-02-10T06:27:07Z)
High-Dimensional Inference over Networks: Linear Convergence and Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文参考訳（メタデータ） (2022-01-21T01:26:08Z)
Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文参考訳（メタデータ） (2021-10-24T04:03:00Z)
Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文参考訳（メタデータ） (2021-07-22T14:25:16Z)
Communication-efficient SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
論文参考訳（メタデータ） (2021-06-09T01:10:34Z)
Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文参考訳（メタデータ） (2020-12-15T18:56:46Z)
Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文参考訳（メタデータ） (2020-10-16T08:10:02Z)

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

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