論文の概要: Variance reduced stochastic optimization over directed graphs with row
and column stochastic weights
- arxiv url: http://arxiv.org/abs/2202.03346v1
- Date: Mon, 7 Feb 2022 16:44:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-08 17:49:02.857087
- Title: Variance reduced stochastic optimization over directed graphs with row
and column stochastic weights
- Title(参考訳): 列と列の確率重み付き有向グラフ上の分散低減確率最適化
- Authors: Muhammad I. Qureshi, Ran Xin, Soummya Kar, Usman A. Khan
- Abstract要約: AB-SAGA は強凸関数上に分布する有限サムである。
一定のステップサイズでは、AB-SAGAは大域的最適値に線形収束することを示す。
- 参考スコア(独自算出の注目度): 18.53372294049107
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proposes AB-SAGA, a first-order distributed stochastic
optimization method to minimize a finite-sum of smooth and strongly convex
functions distributed over an arbitrary directed graph. AB-SAGA removes the
uncertainty caused by the stochastic gradients using a node-level variance
reduction and subsequently employs network-level gradient tracking to address
the data dissimilarity across the nodes. Unlike existing methods that use the
nonlinear push-sum correction to cancel the imbalance caused by the directed
communication, the consensus updates in AB-SAGA are linear and uses both row
and column stochastic weights. We show that for a constant step-size, AB-SAGA
converges linearly to the global optimal. We quantify the directed nature of
the underlying graph using an explicit directivity constant and characterize
the regimes in which AB-SAGA achieves a linear speed-up over its centralized
counterpart. Numerical experiments illustrate the convergence of AB-SAGA for
strongly convex and nonconvex problems.
- Abstract(参考訳): 本稿では,任意の有向グラフ上に分布する滑らかかつ強凸関数の有限和を最小化する一階分散確率最適化法 ab-saga を提案する。
AB-SAGAは、ノードレベルの分散還元を用いて確率勾配に起因する不確実性を除去し、その後、ノード間のデータ差に対処するためにネットワークレベルの勾配追跡を用いる。
有向通信による不均衡を解消するために非線形プッシュサム補正を用いる既存の方法とは異なり、AB-SAGAのコンセンサス更新は線形であり、行および列確率重みの両方を使用する。
一定のステップサイズでは、AB-SAGAは大域的最適値に線形収束することを示す。
我々は,AB-SAGAが中央集権的なグラフよりも直線的なスピードアップを達成する条件を,明示的な指向性定数を用いて定量化する。
数値実験は、強い凸問題と非凸問題に対するAB-SAGAの収束を示す。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳(メタデータ) (2023-05-28T06:33:37Z) - The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded
Gradients and Affine Variance [46.15915820243487]
AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。
AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。
論文 参考訳(メタデータ) (2022-02-11T17:37:54Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - Alternating minimization algorithms for graph regularized tensor
completion [8.26185178671935]
我々は、低ランクテンソル完備化(LRTC)に対するカノニカルポリアディック(CP)分解法を考える。
グラフ正規化の使用にはLRTCの学習精度のメリットが伴うが、同時に結合グラフラプラシア語を誘導する。
基礎となるCP分解モデルにおけるブロック構造を利用して, 効率の良い同期最小化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-08-28T23:20:49Z) - Push-SAGA: A decentralized stochastic algorithm with variance reduction
over directed graphs [18.53372294049107]
Push-SAGAはノードの有向ネットワークに対する有限一階法のための分散一階法である。
我々はPush-SAGAが滑らかで凸な問題に対して線形収束を実現することを示す。
論文 参考訳(メタデータ) (2020-08-13T18:52:17Z) - An improved convergence analysis for decentralized online stochastic
non-convex optimization [17.386715847732468]
本稿では,GT-Loakjasiewics(GT-Loakjasiewics)と呼ばれる手法が,GT-Loakjasiewics(GT-Loakjasiewics)が現在の収束率を満たすことを示す。
結果はすぐに適用できるだけでなく、現在知られている最高の収束率にも適用できる。
論文 参考訳(メタデータ) (2020-08-10T15:29:13Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳(メタデータ) (2020-05-15T21:14:22Z) - GradientDICE: Rethinking Generalized Offline Estimation of Stationary
Values [75.17074235764757]
対象ポリシーの状態分布とサンプリング分布の密度比を推定するグラディエントDICEを提案する。
GenDICEはそのような密度比を推定するための最先端技術である。
論文 参考訳(メタデータ) (2020-01-29T22:10:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。