論文の概要: On the Effects of Data Heterogeneity on the Convergence Rates of
Distributed Linear System Solvers
- arxiv url: http://arxiv.org/abs/2304.10640v1
- Date: Thu, 20 Apr 2023 20:48:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-24 16:35:06.205312
- Title: On the Effects of Data Heterogeneity on the Convergence Rates of
Distributed Linear System Solvers
- Title（参考訳）: 分散線形系ソルバの収束率に及ぼすデータ不均質性の影響について
- Authors: Boris Velasevic, Rohit Parasnis, Christopher G. Brinton, Navid Azizan
- Abstract要約: 一組の機械の助けを借りて線形方程式の大規模系を解く問題を考察する。
アルゴリズムの2つのクラスを比較し、各クラスから最も効率的なメソッドに特に焦点をあてる。
分析の結果,APCが現実シナリオにおいて最も効率的な手法であることを示す以外に,多くの新たな知見が得られた。
- 参考スコア（独自算出の注目度）: 5.850373399231512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the fundamental problem of solving a large-scale system of linear
equations. In particular, we consider the setting where a taskmaster intends to
solve the system in a distributed/federated fashion with the help of a set of
machines, who each have a subset of the equations. Although there exist several
approaches for solving this problem, missing is a rigorous comparison between
the convergence rates of the projection-based methods and those of the
optimization-based ones. In this paper, we analyze and compare these two
classes of algorithms with a particular focus on the most efficient method from
each class, namely, the recently proposed Accelerated Projection-Based
Consensus (APC) and the Distributed Heavy-Ball Method (D-HBM). To this end, we
first propose a geometric notion of data heterogeneity called angular
heterogeneity and discuss its generality. Using this notion, we bound and
compare the convergence rates of the studied algorithms and capture the effects
of both cross-machine and local data heterogeneity on these quantities. Our
analysis results in a number of novel insights besides showing that APC is the
most efficient method in realistic scenarios where there is a large data
heterogeneity. Our numerical analyses validate our theoretical results.
- Abstract（参考訳）: 線形方程式の大規模系を解く基本的な問題を考える。
特に,タスクマスターは,各方程式のサブセットを持つ機械の集合の助けを借りて,分散/フェデレーション方式でシステムを解くことを意図した設定を考える。
この問題を解決する方法はいくつかあるが、プロジェクションベースの手法の収束率と最適化ベースの手法との厳密な比較は欠落している。
本稿では,これらの2種類のアルゴリズムを,各クラスから最も効率的な手法,すなわち最近提案された Accelerated Projection-Based Consensus (APC) と Distributed Heavy-Ball Method (D-HBM) に着目して分析・比較する。
この目的のために,我々はまず,角不均一性と呼ばれるデータ不均一性の幾何学的概念を提案し,その一般性について議論する。
この概念を用いて、解析したアルゴリズムの収束率を限定して比較し、クロスマシンと局所データの両方がそれらの量に与える影響を捉える。
我々の分析は、APCが大規模なデータ不均一性が存在する現実的なシナリオにおいて最も効率的な方法であることを示す以外に、多くの新しい洞察をもたらす。
我々の数値解析は理論的な結果を検証する。
関連論文リスト
- Quantized Hierarchical Federated Learning: A Robust Approach to
Statistical Heterogeneity [3.8798345704175534]
本稿では,コミュニケーション効率に量子化を組み込んだ新しい階層型フェデレーション学習アルゴリズムを提案する。
最適性ギャップと収束率を評価するための包括的な分析フレームワークを提供する。
この結果から,本アルゴリズムはパラメータの範囲で常に高い学習精度を達成できることが判明した。
論文 参考訳（メタデータ） (2024-03-03T15:40:24Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Distributed Linear Regression with Compositional Covariates [5.085889377571319]
大規模合成データにおける分散スパースペナル化線形ログコントラストモデルに着目する。
2つの異なる制約凸最適化問題を解くために2つの分散最適化手法を提案する。
分散化されたトポロジでは、通信効率の高い正規化推定値を得るための分散座標ワイド降下アルゴリズムを導入する。
論文 参考訳（メタデータ） (2023-10-21T11:09:37Z) - Comparison of Single- and Multi- Objective Optimization Quality for
Evolutionary Equation Discovery [77.34726150561087]
進化的微分方程式の発見は、より優先順位の低い方程式を得るための道具であることが証明された。
提案した比較手法は、バーガーズ方程式、波動方程式、コルテヴェーグ・ド・ブリーズ方程式といった古典的なモデル例で示される。
論文 参考訳（メタデータ） (2023-06-29T15:37:19Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳（メタデータ） (2021-03-05T04:42:32Z) - Communication-efficient distributed eigenspace estimation [31.69089186688224]
我々は,データ行列の先頭不変部分空間を計算するための通信効率のよい分散アルゴリズムを開発した。
提案アルゴリズムは局所解と参照解の間のプロクリスト距離を最小化する新しいアライメント方式を用いる。
本アルゴリズムは,集中型推定器と同様の誤差率を示す。
論文 参考訳（メタデータ） (2020-09-05T02:11:22Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
[1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。
我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。
また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
論文 参考訳（メタデータ） (2020-04-17T12:47:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。