論文の概要: Variance Reduced Coordinate Descent with Acceleration: New Method With a
Surprising Application to Finite-Sum Problems
- arxiv url: http://arxiv.org/abs/2002.04670v1
- Date: Tue, 11 Feb 2020 20:42:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 02:49:07.953036
- Title: Variance Reduced Coordinate Descent with Acceleration: New Method With a
Surprising Application to Finite-Sum Problems
- Title(参考訳): 加速度による分散低減座標降下--有限サム問題への驚くべき応用による新しい方法
- Authors: Filip Hanzely, Dmitry Kovalev and Peter Richtarik
- Abstract要約: 本稿では,ASVRCDによる分散低減座標降下の高速化版を提案する。
SEGAやSVRCDのような他の分散化座標降下法と同様に、本手法は非分離正則化や非滑らかな正則化を含む問題に対処できる。
- 参考スコア(独自算出の注目度): 20.26621024877966
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an accelerated version of stochastic variance reduced coordinate
descent -- ASVRCD. As other variance reduced coordinate descent methods such as
SEGA or SVRCD, our method can deal with problems that include a non-separable
and non-smooth regularizer, while accessing a random block of partial
derivatives in each iteration only. However, ASVRCD incorporates Nesterov's
momentum, which offers favorable iteration complexity guarantees over both SEGA
and SVRCD. As a by-product of our theory, we show that a variant of Allen-Zhu
(2017) is a specific case of ASVRCD, recovering the optimal oracle complexity
for the finite sum objective.
- Abstract(参考訳): 本稿では,ASVRCDによる確率分散低減座標降下の高速化版を提案する。
SEGAやSVRCDのような他の分散化座標降下法と同様に、各イテレーションで部分微分のランダムブロックにアクセスしながら、非分離および非滑らかな正規化器を含む問題に対処することができる。
しかし、ASVRCDはネステロフの勢いを取り入れており、SEGAとSVRCDの両方に対して良好なイテレーションの複雑さを保証する。
我々の理論の副産物として、Allen-Zhu (2017) の変種がASVRCDの特定の場合であることが示され、有限和の目的に対して最適なオラクル複雑性を回復する。
関連論文リスト
- Cluster truncated Wigner approximation for bond-disordered Heisenberg spin models [0.0]
クラスタートリニケートウィグナー近似(cTWA)は、結合非秩序なハイゼンベルクスピン鎖のクエンチダイナミクスとパワー-ロー相互作用に応用される。
当初導入されたガウス近似に基づくスキームの代替として、初期ウィグナー関数の離散サンプリングスキームを開発する。
論文 参考訳(メタデータ) (2024-07-01T18:00:06Z) - ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳(メタデータ) (2023-12-04T19:00:07Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient
Methods [73.35353358543507]
SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。
本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。
本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
論文 参考訳(メタデータ) (2022-02-15T09:17:39Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳(メタデータ) (2021-12-24T17:21:04Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - SVRG Meets AdaGrad: Painless Variance Reduction [34.42463428418348]
一般的なVR手法であるSVRGの完全適応型を提案する。
AdaSVRGはSVRGの内部ループでAdaGradを使用し、ステップサイズの選択に堅牢にします。
AdaSVRGのロバスト性と有効性を検証し、他の「ツインフリー」VR手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2021-02-18T22:26:19Z) - Linearly Converging Error Compensated SGD [11.436753102510647]
本稿では、任意の圧縮と遅延更新を伴う分散SGDの変種を統一的に解析する。
我々のフレームワークは、量子化されたSGD、ErrorCompensated SGD、SGDの様々な変種をカバーするのに十分である。
我々は、分散還元や任意のサンプリングと誤りフィードバックと量子化を組み合わせたSGDの新しい変種を開発する。
論文 参考訳(メタデータ) (2020-10-23T10:46:31Z) - Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
コミュニケーションのボトルネックは、大規模なディープラーニングにおいて重要な問題である。
非効率な分散問題に対する誤りフィードバックよりも優れた収束性を示す分散誤差フィードバック(DEF)アルゴリズムを提案する。
また、DEFよりも優れた境界を示すDEFの一般化を加速するDEFAを提案する。
論文 参考訳(メタデータ) (2020-04-11T03:50:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。