論文の概要: Iterative Pre-Conditioning for Expediting the Gradient-Descent Method:
The Distributed Linear Least-Squares Problem
- arxiv url: http://arxiv.org/abs/2008.02856v2
- Date: Fri, 6 Aug 2021 21:42:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 07:13:37.323780
- Title: Iterative Pre-Conditioning for Expediting the Gradient-Descent Method:
The Distributed Linear Least-Squares Problem
- Title（参考訳）: 勾配-descent法を迅速化する反復前条件法:分散線形最小二乗問題
- Authors: Kushal Chakrabarti, Nirupam Gupta, Nikhil Chopra
- Abstract要約: 本稿では,サーバエージェントネットワークにおけるマルチエージェント線形最小二乗問題について考察する。
エージェントの目標は、個々のローカルデータポイントを共有することなく、すべてのエージェントが保持する集合データポイントに最適に適合する線形モデルを計算することである。
本稿では,データ点の条件付けによる劣化効果を緩和する反復的プレコンディショニング手法を提案する。
- 参考スコア（独自算出の注目度）: 0.966840768820136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the multi-agent linear least-squares problem in a
server-agent network. In this problem, the system comprises multiple agents,
each having a set of local data points, that are connected to a server. The
goal for the agents is to compute a linear mathematical model that optimally
fits the collective data points held by all the agents, without sharing their
individual local data points. This goal can be achieved, in principle, using
the server-agent variant of the traditional iterative gradient-descent method.
The gradient-descent method converges linearly to a solution, and its rate of
convergence is lower bounded by the conditioning of the agents' collective data
points. If the data points are ill-conditioned, the gradient-descent method may
require a large number of iterations to converge.
We propose an iterative pre-conditioning technique that mitigates the
deleterious effect of the conditioning of data points on the rate of
convergence of the gradient-descent method. We rigorously show that the
resulting pre-conditioned gradient-descent method, with the proposed iterative
pre-conditioning, achieves superlinear convergence when the least-squares
problem has a unique solution. In general, the convergence is linear with
improved rate of convergence in comparison to the traditional gradient-descent
method and the state-of-the-art accelerated gradient-descent methods. We
further illustrate the improved rate of convergence of our proposed algorithm
through experiments on different real-world least-squares problems in both
noise-free and noisy computation environment.
- Abstract（参考訳）: 本稿では,サーバエージェントネットワークにおけるマルチエージェント線形最小二乗問題を考える。
この問題において、システムは複数のエージェントから構成され、それぞれがサーバに接続されたローカルデータポイントのセットを持つ。
エージェントの目標は、個々のローカルデータポイントを共有することなく、すべてのエージェントが保持する集団データポイントに最適な線形数学的モデルを計算することである。
このゴールは、原則として、従来の反復勾配差分法(英語版)のサーバエージェント変種を用いて達成できる。
勾配差分法は解に線形に収束し、その収束率はエージェントの集合データポイントの条件付けによって下界となる。
データポイントが不条件の場合、勾配拡散法は多数のイテレーションを収束させる必要がある。
本研究では,データ点のコンディショニングが勾配-希薄化法の収束率に与える影響を緩和する反復前処理手法を提案する。
提案した反復的事前条件付きプレコンディショニングにより,最小二乗問題に一意解が存在する場合の超線形収束を実現する。
一般に、収束は従来の勾配descent法や最先端加速勾配descent法と比較して、収束速度が向上した線形である。
さらに,ノイズフリー,ノイズの多い両計算環境における実世界の最小二乗問題に対する実験を通じて,提案アルゴリズムの収束率の改善について述べる。
関連論文リスト
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Over-the-Air Computation Aided Federated Learning with the Aggregation
of Normalized Gradient [12.692064367193934]
オーバー・ザ・エア(Over-the-air)は、フェデレートラーニング(FL)のための通信効率のよい解である。
このようなシステムでは、プライベート損失関数の反復手順を更新し、すべてのモバイルデバイスで送信する。
この問題を回避するため,局所勾配を正規化して増幅する手法を提案する。
論文 参考訳（メタデータ） (2023-08-17T16:15:47Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - On Asymptotic Linear Convergence of Projected Gradient Descent for
Constrained Least Squares [22.851500417035947]
この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。
本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
論文 参考訳（メタデータ） (2021-12-22T09:49:51Z) - On Accelerating Distributed Convex Optimizations [0.0]
本稿では,分散マルチエージェント凸最適化問題について検討する。
提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。
実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
論文 参考訳（メタデータ） (2021-08-19T13:19:54Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Accelerating Distributed SGD for Linear Regression using Iterative
Pre-Conditioning [0.966840768820136]
繰り返しプレコンディショニングされたグラディエント・ディフレッシュ法(IPSG)は,既存の分散アルゴリズムよりも高速に収束することを示した。
IPSG法の収束速度は、サーバベースネットワークにおける線形最小二乗問題を解くための顕著なアルゴリズムと比較して好意的に比較される。
論文 参考訳（メタデータ） (2020-11-15T18:09:13Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
論文 参考訳（メタデータ） (2020-07-13T17:39:35Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Iterative Pre-Conditioning to Expedite the Gradient-Descent Method [0.966840768820136]
本稿では,マルチエージェント分散最適化の問題について考察する。
そこで本研究では,勾配差分法による収束速度に対する問題条件付けの影響を大幅に軽減できる反復的事前条件付け手法を提案する。
論文 参考訳（メタデータ） (2020-03-13T16:30:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。