論文の概要: Stochastic Gradient Methods with Preconditioned Updates
- arxiv url: http://arxiv.org/abs/2206.00285v1
- Date: Wed, 1 Jun 2022 07:38:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-02 13:41:22.974122
- Title: Stochastic Gradient Methods with Preconditioned Updates
- Title（参考訳）: 事前条件付き更新による確率勾配法
- Authors: Abdurakhmon Sadiev, Aleksandr Beznosikov, Abdulla Jasem Almansoori,
Dmitry Kamzolov, Rachael Tappenden, Martin Tak\'a\v{c}
- Abstract要約: このような問題に対する既存のアルゴリズムは、問題のスケールが悪く、あるいは条件が不適切である場合、しばしばうまく機能しない。
ここでは、ヘッセン曲率の対角線を近似する2つのSARアプローチに基づくプレコンディショナーを含む。
理論的複雑性保証が提示され、滑らかさとPL条件の両方を仮定すると収束が証明される。
- 参考スコア（独自算出の注目度）: 55.69352761176367
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work considers non-convex finite sum minimization. There are a number of
algorithms for such problems, but existing methods often work poorly when the
problem is badly scaled and/or ill-conditioned, and a primary goal of this work
is to introduce methods that alleviate this issue. Thus, here we include a
preconditioner that is based upon Hutchinson's approach to approximating the
diagonal of the Hessian, and couple it with several gradient based methods to
give new `scaled' algorithms: {\tt Scaled SARAH} and {\tt Scaled L-SVRG}.
Theoretical complexity guarantees under smoothness assumptions are presented,
and we prove linear convergence when both smoothness and the PL-condition is
assumed. Because our adaptively scaled methods use approximate partial second
order curvature information, they are better able to mitigate the impact of
badly scaled problems, and this improved practical performance is demonstrated
in the numerical experiments that are also presented in this work.
- Abstract（参考訳）: この仕事は非凸有限和最小化を考える。
このような問題に対するアルゴリズムは数多く存在するが、既存の手法は、問題がひどくスケールしたり、不調になったりした場合にうまく動作せず、この問題を緩和する手法を導入することが本研究の主な目的である。
ここでは、ハッチンソンのヘッセン対角法を近似するアプローチに基づくプレコンディショナーを包含し、新しい「スケールされた」アルゴリズムを与えるための勾配に基づくいくつかの方法: {\tt Scaled SARAH} と {\tt Scaled L-SVRG} を結合する。
滑らかさ仮定の下での理論的複雑性保証が提示され、滑らかさとPL条件の両方を仮定した場合に線形収束が証明される。
適応的にスケールした手法は近似的な部分的な2次曲率情報を利用するため, スケールの悪い問題の影響を軽減することができ, また, この改良された実用性は, 本研究で示された数値実験で実証される。
関連論文リスト
- An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - 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) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - A Scalable Second Order Method for Ill-Conditioned Matrix Completion
from Few Samples [0.0]
低ランク行列補完のための反復アルゴリズムを提案する。
ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
論文 参考訳（メタデータ） (2021-06-03T20:31:00Z) - AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods [7.486132958737807]
適応性に対する暗黙的アプローチによる適応分散低減手法を提案する。
有限サム最小化問題に対する収束保証を提供し,局所幾何が許せばサラよりも高速に収束できることを示す。
このアルゴリズムはステップサイズを暗黙的に計算し、関数の局所リプシッツ滑らかさを効率的に推定する。
論文 参考訳（メタデータ） (2021-02-19T01:17:15Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Adaptive Gradient Methods Converge Faster with Over-Parameterization
(but you should do a line-search) [32.24244211281863]
データを補間するのに十分なパラメータ化モデルを用いて、スムーズで凸的な損失を簡易に設定する。
一定のステップサイズと運動量を持つ AMSGrad がより高速な$O(1/T)$レートで最小値に収束することを証明する。
これらの手法により,タスク間の適応勾配法の収束と一般化が向上することを示す。
論文 参考訳（メタデータ） (2020-06-11T21:23:30Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。