論文の概要: On Accelerating Distributed Convex Optimizations
- arxiv url: http://arxiv.org/abs/2108.08670v1
- Date: Thu, 19 Aug 2021 13:19:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-20 14:36:59.362021
- Title: On Accelerating Distributed Convex Optimizations
- Title（参考訳）: 分散凸最適化の高速化について
- Authors: Kushal Chakrabarti, Nirupam Gupta, Nikhil Chopra
- Abstract要約: 本稿では,分散マルチエージェント凸最適化問題について検討する。
提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。
実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a distributed multi-agent convex optimization problem. The
system comprises multiple agents in this problem, each with a set of local data
points and an associated local cost function. The agents are connected to a
server, and there is no inter-agent communication. The agents' goal is to learn
a parameter vector that optimizes the aggregate of their local costs without
revealing their local data points. In principle, the agents can solve this
problem by collaborating with the server using the traditional distributed
gradient-descent method. However, when the aggregate cost is ill-conditioned,
the gradient-descent method (i) requires a large number of iterations to
converge, and (ii) is highly unstable against process noise. We propose an
iterative pre-conditioning technique to mitigate the deleterious effects of the
cost function's conditioning on the convergence rate of distributed
gradient-descent. Unlike the conventional pre-conditioning techniques, the
pre-conditioner matrix in our proposed technique updates iteratively to
facilitate implementation on the distributed network. In the distributed
setting, we provably show that the proposed algorithm converges linearly with
an improved rate of convergence than the traditional and adaptive
gradient-descent methods. Additionally, for the special case when the minimizer
of the aggregate cost is unique, our algorithm converges superlinearly. We
demonstrate our algorithm's superior performance compared to prominent
distributed algorithms for solving real logistic regression problems and
emulating neural network training via a noisy quadratic model, thereby
signifying the proposed algorithm's efficiency for distributively solving
non-convex optimization. Moreover, we empirically show that the proposed
algorithm results in faster training without compromising the generalization
performance.
- Abstract（参考訳）: 本稿では,分散マルチエージェント凸最適化問題について検討する。
このシステムには複数のエージェントが含まれており、それぞれに複数のローカルデータポイントと関連するローカルコスト関数がある。
エージェントはサーバに接続されており、エージェント間通信はありません。
エージェントの目標は、ローカルデータポイントを明かすことなく、ローカルコストの集約を最適化するパラメータベクトルを学ぶことである。
エージェントは従来の分散勾配差分法を用いてサーバと協調してこの問題を解くことができる。
しかし, 集約コストが不調な場合, 勾配差分法 (i) は多くの繰り返しを収束させる必要があり, (ii) プロセスノイズに対して非常に不安定である。
本稿では,コスト関数の条件付けが分散勾配の収束率に与える影響を緩和する反復的プレコンディショニング手法を提案する。
従来のプリコンディショニング技術とは異なり,提案手法のプレコンディショナーマトリックスは分散ネットワーク上での実装を容易にするために更新される。
分散環境では,提案アルゴリズムは従来型および適応型勾配偏光法よりも収束率の向上とともに線形に収束することを示す。
さらに、集約コストの最小化が一意である特別な場合、我々のアルゴリズムは超直線的に収束する。
本アルゴリズムは,実ロジスティック回帰問題を解くための分散アルゴリズムよりも優れた性能を示し,ノイズ2次モデルによるニューラルネットワークの学習をエミュレートし,非凸最適化を分散的に解くアルゴリズムの効率を示す。
さらに,提案アルゴリズムが一般化性能を損なうことなく,より高速な学習を実現することを示す。
関連論文リスト
- Optimizing the Optimal Weighted Average: Efficient Distributed Sparse Classification [50.406127962933915]
ACOWAは、小さなランタイムの増加とともに、顕著に優れた近似品質を達成するための追加の通信を可能にする。
その結果、ACOWAは経験的リスク最小化に忠実で、他の分散アルゴリズムよりもかなり高い精度で解が得られることがわかった。
論文 参考訳（メタデータ） (2024-06-03T19:43:06Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent [7.6860514640178]
分散強化学習のための新しいゼロ階最適化アルゴリズムを提案する。
これにより、各エージェントはコンセンサスプロトコルを使わずに、コスト評価を独立してローカル勾配を推定できる。
論文 参考訳（メタデータ） (2021-07-26T18:11:07Z) - A Distributed Training Algorithm of Generative Adversarial Networks with
Quantized Gradients [8.202072658184166]
本稿では,量子化勾配を用いた分散GAN学習アルゴリズムDQGANを提案する。
この新しい方法は、OMDアルゴリズムと呼ばれる特定の単一マシンアルゴリズムに基づいてGANを訓練し、一般的な$delta$-approximate圧縮器を満たす任意の勾配圧縮手法に適用できる。
理論的には、DQGANアルゴリズムの1次定常点への非漸近収束を確立し、提案アルゴリズムが線形高速化を実現することを示す。
論文 参考訳（メタデータ） (2020-10-26T06:06:43Z) - Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
センサローカライゼーションの現実問題において,ネットワークトポロジと異なるアルゴリズムの収束率の関係について検討する。
また、ADMMと持ち上げマルコフ連鎖の間の興味深い関係を示すとともに、その収束を明示的に特徴づける。
論文 参考訳（メタデータ） (2020-09-05T21:44:39Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳（メタデータ） (2020-05-05T18:08:23Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z) - A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to
Balance Communication Overhead, Computational Complexity, and Convergence
Rate [28.167294398293297]
通信負荷の少ない分散勾配降下法(SGD)を提案する。
各イテレーションにおける計算複雑性を低減するために、ワーカノードは、方向微分をゼロ階勾配推定で近似する。
論文 参考訳（メタデータ） (2020-03-27T14:02:15Z) - Iterative Pre-Conditioning to Expedite the Gradient-Descent Method [0.966840768820136]
本稿では,マルチエージェント分散最適化の問題について考察する。
そこで本研究では,勾配差分法による収束速度に対する問題条件付けの影響を大幅に軽減できる反復的事前条件付け手法を提案する。
論文 参考訳（メタデータ） (2020-03-13T16:30:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。