論文の概要: Iterative Pre-Conditioning to Expedite the Gradient-Descent Method
- arxiv url: http://arxiv.org/abs/2003.07180v2
- Date: Sun, 29 Mar 2020 04:04:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-24 01:40:53.573212
- Title: Iterative Pre-Conditioning to Expedite the Gradient-Descent Method
- Title（参考訳）: グラディエント・ディフレッシュ法における反復前処理
- Authors: Kushal Chakrabarti, Nirupam Gupta and Nikhil Chopra
- Abstract要約: 本稿では,マルチエージェント分散最適化の問題について考察する。
そこで本研究では,勾配差分法による収束速度に対する問題条件付けの影響を大幅に軽減できる反復的事前条件付け手法を提案する。
- 参考スコア（独自算出の注目度）: 0.966840768820136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the problem of multi-agent distributed optimization. In
this problem, there are multiple agents in the system, and each agent only
knows its local cost function. The objective for the agents is to collectively
compute a common minimum of the aggregate of all their local cost functions. In
principle, this problem is solvable using a distributed variant of the
traditional gradient-descent method, which is an iterative method. However, the
speed of convergence of the traditional gradient-descent method is highly
influenced by the conditioning of the optimization problem being solved.
Specifically, the method requires a large number of iterations to converge to a
solution if the optimization problem is ill-conditioned.
In this paper, we propose an iterative pre-conditioning approach that can
significantly attenuate the influence of the problem's conditioning on the
convergence-speed of the gradient-descent method. The proposed pre-conditioning
approach can be easily implemented in distributed systems and has minimal
computation and communication overhead. For now, we only consider a specific
distributed optimization problem wherein the individual local cost functions of
the agents are quadratic. Besides the theoretical guarantees, the improved
convergence speed of our approach is demonstrated through experiments on a real
data-set.
- Abstract（参考訳）: 本稿では,マルチエージェント分散最適化の問題を考える。
この問題では、システムには複数のエージェントがあり、各エージェントはそのローカルコスト関数しか知らない。
エージェントの目的は、すべてのローカルコスト関数の集約の共通最小値を計算することである。
原則として、この問題は、反復的手法である従来の勾配拡散法(gradient-descent method)の分散変種を用いて解くことができる。
しかし, 従来の勾配差分法の収束速度は, 最適化問題の条件付けの影響を強く受けている。
具体的には、最適化問題が不調な場合には、多数のイテレーションを解に収束させる必要がある。
本稿では,この問題の条件付けが勾配-発光法の収束速度に与える影響を著しく軽減できる反復前条件付け手法を提案する。
提案するプリコンディショニング手法は,分散システムで容易に実装でき,計算処理と通信のオーバーヘッドが最小限である。
現時点では、エージェントの個々の局所コスト関数が二次的である特定の分散最適化問題のみを考える。
理論的保証に加えて,本手法の収束速度の向上は実データを用いた実験によって実証される。
関連論文リスト
- Over-the-Air Computation Aided Federated Learning with the Aggregation
of Normalized Gradient [12.692064367193934]
オーバー・ザ・エア(Over-the-air)は、フェデレートラーニング(FL)のための通信効率のよい解である。
このようなシステムでは、プライベート損失関数の反復手順を更新し、すべてのモバイルデバイスで送信する。
この問題を回避するため,局所勾配を正規化して増幅する手法を提案する。
論文 参考訳（メタデータ） (2023-08-17T16:15:47Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。
我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文 参考訳（メタデータ） (2022-09-27T09:27:29Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - On Accelerating Distributed Convex Optimizations [0.0]
本稿では,分散マルチエージェント凸最適化問題について検討する。
提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。
実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
論文 参考訳（メタデータ） (2021-08-19T13:19:54Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Iterative Pre-Conditioning for Expediting the Gradient-Descent Method:
The Distributed Linear Least-Squares Problem [0.966840768820136]
本稿では,サーバエージェントネットワークにおけるマルチエージェント線形最小二乗問題について考察する。
エージェントの目標は、個々のローカルデータポイントを共有することなく、すべてのエージェントが保持する集合データポイントに最適に適合する線形モデルを計算することである。
本稿では,データ点の条件付けによる劣化効果を緩和する反復的プレコンディショニング手法を提案する。
論文 参考訳（メタデータ） (2020-08-06T20:01:18Z) - A Multi-Agent Primal-Dual Strategy for Composite Optimization over
Distributed Features [52.856801164425086]
目的関数を滑らかな局所関数と凸(おそらく非滑らか)結合関数の和とするマルチエージェント共有最適化問題について検討する。
論文 参考訳（メタデータ） (2020-06-15T19:40:24Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。