論文の概要: Towards Quantifying the Preconditioning Effect of Adam
- arxiv url: http://arxiv.org/abs/2402.07114v1
- Date: Sun, 11 Feb 2024 06:21:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 17:33:02.350549
- Title: Towards Quantifying the Preconditioning Effect of Adam
- Title(参考訳): アダムのプレコンディショニング効果の定量化に向けて
- Authors: Rudrajit Das, Naman Agarwal, Sujay Sanghavi, Inderjit S. Dhillon
- Abstract要約: 二次関数に対するアダムの事前条件効果を詳細に解析する。
我々は、アダムがヘッセンの条件数への依存を緩和できる程度に定量化する。
以上の結果から, 十分に非対角ヘッセン系では, アダムは勾配降下よりも悪くなる可能性が示唆された。
- 参考スコア(独自算出の注目度): 36.91196231006288
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There is a notable dearth of results characterizing the preconditioning
effect of Adam and showing how it may alleviate the curse of ill-conditioning
-- an issue plaguing gradient descent (GD). In this work, we perform a detailed
analysis of Adam's preconditioning effect for quadratic functions and quantify
to what extent Adam can mitigate the dependence on the condition number of the
Hessian. Our key finding is that Adam can suffer less from the condition number
but at the expense of suffering a dimension-dependent quantity. Specifically,
for a $d$-dimensional quadratic with a diagonal Hessian having condition number
$\kappa$, we show that the effective condition number-like quantity controlling
the iteration complexity of Adam without momentum is $\mathcal{O}(\min(d,
\kappa))$. For a diagonally dominant Hessian, we obtain a bound of
$\mathcal{O}(\min(d \sqrt{d \kappa}, \kappa))$ for the corresponding quantity.
Thus, when $d < \mathcal{O}(\kappa^p)$ where $p = 1$ for a diagonal Hessian and
$p = 1/3$ for a diagonally dominant Hessian, Adam can outperform GD (which has
an $\mathcal{O}(\kappa)$ dependence). On the negative side, our results suggest
that Adam can be worse than GD for a sufficiently non-diagonal Hessian even if
$d \ll \mathcal{O}(\kappa^{1/3})$; we corroborate this with empirical evidence.
Finally, we extend our analysis to functions satisfying per-coordinate
Lipschitz smoothness and a modified version of the Polyak-\L ojasiewicz
condition.
- Abstract(参考訳): アダムのプレコンディショニング効果を特徴づけ、どのようにして悪条件の呪いを和らげるかを示す、顕著な研究結果がある。
本研究では,2次関数に対するアダムの事前条件付け効果を詳細に解析し,アダムがヘッシアンの条件数依存性をどの程度緩和できるかを定量化する。
私たちの重要な発見は、Adamが条件数に悩まされることが少なく、次元に依存した量に悩まされることである。
具体的には、条件数$\kappa$を持つ対角ヘシアンを持つ$d$次元二次体に対して、運動量のないアダムの反復複雑性を制御する実効条件数のような量が$\mathcal{O}(\min(d, \kappa))$であることを示す。
対角的に支配的なヘッシアンに対して、対応する量に対して$\mathcal{o}(\min(d \sqrt{d \kappa}, \kappa))$ が与えられる。
したがって、$d < \mathcal{O}(\kappa^p)$ where $p = 1$ for a diagonal Hessian and $p = 1/3$ for a diagonally dominant Hessian とすると、Adam は GD ($\mathcal{O}(\kappa)$dependent を持つ) を上回りうる。
負の面では、Adam は $d \ll \mathcal{O}(\kappa^{1/3})$ であっても十分に非対角ヘッセンに対して GD よりも悪い可能性があることを示唆している。
最後に,Polak-\L ojasiewicz条件の修正版とコーディネート毎のリプシッツ滑らか度を満たす関数に解析を拡張した。
関連論文リスト
- A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP
hierarchies [37.29025597886073]
多次元スケーリング(MDS)は、$n$オブジェクト間のペアワイドな相似性を低次元空間に埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
我々の分析は、低次元ユークリッド空間の幾何学を利用して、アスペクト比$Delta$への指数的依存を避けることができる。
論文 参考訳(メタデータ) (2023-11-29T17:42:05Z) - Provable Adaptivity in Adam [87.29083241928804]
我々はアダムが局所的な滑らかさ条件に適応し、アダムの強調適応性を正当化できると主張している。
我々の結果は、適応的でないものよりも適応的勾配法の利点に光を当てるかもしれない。
論文 参考訳(メタデータ) (2022-08-21T14:57:47Z) - Adam Can Converge Without Any Modification on Update Rules [24.575453562687095]
バニラ・アダムは依然として非常に人気があり、実際はうまく機能している。
我々は、$beta$が大きければ、Adamは臨界点の近傍に収束することを示す。
我々の発散結果は収束結果と同一の設定を考慮し、$beta$を増大させるときに発散から収束への相転移を示す。
論文 参考訳(メタデータ) (2022-08-20T08:12:37Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳(メタデータ) (2022-08-19T18:00:34Z) - Understanding AdamW through Proximal Methods and Scale-Freeness [57.47324825501137]
Adam は $ell$ regularizer Adam-$ell$ の一般化である。
AdamWは、Adam-$ell$の更新ルールからAdam-$ell$の勾配を分離する。
我々はAdamWがAdam-$ell$よりも有利であることを示し、ネットワークの勾配が複数のスケールを示すことを期待する度合いを示す。
論文 参考訳(メタデータ) (2022-01-31T21:00:55Z) - Adam$^+$: A Stochastic Method with Adaptive Variance Reduction [56.051001950733315]
Adamはディープラーニングアプリケーションに広く使われている最適化手法である。
我々はAdam$+$(Adam-plusと発音する)という新しい方法を提案する。
画像分類,言語モデリング,自動音声認識など,さまざまなディープラーニングタスクに関する実証研究により,Adam$+$がAdamを著しく上回ることを示した。
論文 参考訳(メタデータ) (2020-11-24T09:28:53Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳(メタデータ) (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。