論文の概要: On the Effects of Data Heterogeneity on the Convergence Rates of
Distributed Linear System Solvers
- arxiv url: http://arxiv.org/abs/2304.10640v2
- Date: Fri, 16 Feb 2024 00:02:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-19 21:07:54.888989
- 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が現実シナリオにおいて最も効率的な手法であることを示す以外に,多くの新たな知見が得られた。
- 参考スコア(独自算出の注目度): 10.103350854870992
- 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) - Synergistic eigenanalysis of covariance and Hessian matrices for
enhanced binary classification [75.90957645766676]
本稿では, 学習モデルを用いて評価したヘッセン行列をトレーニングセットで評価した共分散行列の固有解析と, 深層学習モデルで評価したヘッセン行列を組み合わせた新しい手法を提案する。
我々のアプローチは、クラス間の平均距離を最大化し、クラス内の分散を最小化する能力を確立する形式的な証明によって裏付けられている。
論文 参考訳(メタデータ) (2024-02-14T16:10:42Z) - 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) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳(メタデータ) (2023-06-10T08:25:16Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳(メタデータ) (2021-11-29T15:10:09Z) - Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian
Modeling [68.69431580852535]
サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。
我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。
我々は2つの異なる社会問題に対してアルゴリズムを実行する。
論文 参考訳(メタデータ) (2021-07-07T03:57:22Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z) - A Method for Handling Multi-class Imbalanced Data by Geometry based
Information Sampling and Class Prioritized Synthetic Data Generation (GICaPS) [15.433936272310952]
本稿では,多ラベル分類問題における不均衡データ処理の問題について考察する。
特徴ベクトル間の幾何学的関係を利用する2つの新しい手法が提案されている。
提案手法の有効性は,汎用的なマルチクラス認識問題を解くことによって解析する。
論文 参考訳(メタデータ) (2020-10-11T04:04:26Z) - Communication-efficient distributed eigenspace estimation [31.69089186688224]
我々は,データ行列の先頭不変部分空間を計算するための通信効率のよい分散アルゴリズムを開発した。
提案アルゴリズムは局所解と参照解の間のプロクリスト距離を最小化する新しいアライメント方式を用いる。
本アルゴリズムは,集中型推定器と同様の誤差率を示す。
論文 参考訳(メタデータ) (2020-09-05T02:11:22Z) - Distributed Bayesian Matrix Decomposition for Big Data Mining and
Clustering [13.491022200305824]
本稿では,ビッグデータマイニングとクラスタリングのための分散行列分解モデルを提案する。
具体的には, 1) 加速度勾配降下, 2) 乗算器の交互方向法, 3) 統計的推論の3つの方法を採用する。
我々のアルゴリズムは、ビッグデータによく対応し、他の分散手法と比較して優れた、あるいは競合する性能を達成する。
論文 参考訳(メタデータ) (2020-02-10T13:10:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。