論文の概要: Efficient Federated Low Rank Matrix Completion

• arxiv url: http://arxiv.org/abs/2405.06569v2
• Date: Mon, 30 Sep 2024 21:41:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-02 16:31:38.310724
• Title: Efficient Federated Low Rank Matrix Completion
• Title（参考訳）: 効率的なフェデレート低ランクマトリックスコンプリート
• Authors: Ahmed Ali Abbasi, Namrata Vaswani,
• Abstract要約: 低階行列完備化(LRMC)問題を解くために,AltGDと最小化(AltGDmin)と呼ばれるソリューションを開発し,解析する。 我々の理論的保証は、AltGDminがフェデレートされた環境で最も通信効率の良いソリューションであることを示唆している。 私たちは、AltMinのサンプル複雑性の保証を改善するために、我々の補題をどのように利用できるかを示します。
• 参考スコア（独自算出の注目度）: 18.471262688125645
• License:
• Abstract: In this work, we develop and analyze a Gradient Descent (GD) based solution, called Alternating GD and Minimization (AltGDmin), for efficiently solving the low rank matrix completion (LRMC) in a federated setting. LRMC involves recovering an $n \times q$ rank-$r$ matrix $\Xstar$ from a subset of its entries when $r \ll \min(n,q)$. Our theoretical guarantees (iteration and sample complexity bounds) imply that AltGDmin is the most communication-efficient solution in a federated setting, is one of the fastest, and has the second best sample complexity among all iterative solutions to LRMC. In addition, we also prove two important corollaries. (a) We provide a guarantee for AltGDmin for solving the noisy LRMC problem. (b) We show how our lemmas can be used to provide an improved sample complexity guarantee for AltMin, which is the fastest centralized solution.
• Abstract（参考訳）: 本研究では,低階行列補完 (LRMC) をフェデレート環境で効率的に解くために,Alternating GD and Minimization (AltGDmin) と呼ばれるGDベースのソリューションを開発し,解析する。 LRMCは$n \times q$ rank-$r$ matrix $\Xstar$を、$r \ll \min(n,q)$のときのエントリのサブセットから復元する。 我々の理論的保証は、AltGDminがフェデレートされた環境では最も通信効率のよい解であり、LRMCの反復解の中では2番目に高いサンプル複雑性を持つことを示している。 また,2つの重要な関係性も証明した。 (a)ノイズの多いLRMC問題を解くためにAltGDminを保証します。 b)最も高速な集中型ソリューションであるAltMinのサンプル複雑性保証を改善するために,我々のレムマをどのように利用できるかを示す。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities [25.153506493249854]
  min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。 また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-05T00:26:10Z)
• Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processes [1.0445957451908694]
  マルコフ決定過程(MDP)における無限地平面割引報酬の最大化のための最適なサンプル複雑性理論を考える。 多くの関心の応用において、最適ポリシー(または全てのポリシー)は混合を誘導する。 我々の分析は、一般状態空間 MDP の RL 問題の研究に使用できるため、独立した関心を持つ再生型アイデアに基礎を置いている。
  論文  参考訳（メタデータ） (2023-02-15T05:43:17Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach [6.952045528182883]
  スパースプラス低ランク分解問題(SLR)について検討する。 SLRはオペレーションリサーチと機械学習の基本的な問題である。 本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
  論文  参考訳（メタデータ） (2021-09-26T20:49:16Z)
• A Wasserstein Minimax Framework for Mixed Linear Regression [69.40394595795544]
  マルチモーダル分布は、学習タスクにおいてクラスタ化されたデータをモデル化するために一般的に使用される。 混合線形回帰問題に対する最適輸送ベースフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-06-14T16:03:51Z)
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
  生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。 状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-13T17:18:11Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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