論文の概要: Stochastic Steffensen method
- arxiv url: http://arxiv.org/abs/2211.15310v1
- Date: Mon, 28 Nov 2022 13:45:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-29 20:45:23.796098
- Title: Stochastic Steffensen method
- Title(参考訳): 確率的シュテッフェンセン法
- Authors: Minda Zhao, Zehua Lai, and Lek-Heng Lim
- Abstract要約: シュテッフェンゼン法は第二微分を回避し、ニュートン法のような二次収束である。
適応最適化設定での使用を目的としたSteffensen法にインスパイアされた学習率を導入する。
- 参考スコア(独自算出の注目度): 13.19058156672392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Is it possible for a first-order method, i.e., only first derivatives
allowed, to be quadratically convergent? For univariate loss functions, the
answer is yes -- the Steffensen method avoids second derivatives and is still
quadratically convergent like Newton method. By incorporating an optimal step
size we can even push its convergence order beyond quadratic to $1+\sqrt{2}
\approx 2.414$. While such high convergence orders are a pointless overkill for
a deterministic algorithm, they become rewarding when the algorithm is
randomized for problems of massive sizes, as randomization invariably
compromises convergence speed. We will introduce two adaptive learning rates
inspired by the Steffensen method, intended for use in a stochastic
optimization setting and requires no hyperparameter tuning aside from batch
size. Extensive experiments show that they compare favorably with several
existing first-order methods. When restricted to a quadratic objective, our
stochastic Steffensen methods reduce to randomized Kaczmarz method -- note that
this is not true for SGD or SLBFGS -- and thus we may also view our methods as
a generalization of randomized Kaczmarz to arbitrary objectives.
- Abstract(参考訳): 一階法、すなわち、第一導関数のみが許される場合、二次収束することは可能であるか。
不定損失関数の場合、答えは yes である -- steffensen 法は第二導関数を避け、ニュートン法のように二次収束する。
最適なステップサイズを組み込むことで、収束順序を2次から1+\sqrt{2} \approx 2.414$まで押し上げることもできる。
このような高い収束順序は決定論的アルゴリズムの無意味なオーバーキルであるが、アルゴリズムが巨大なサイズの問題に対してランダム化されると、ランダム化は必ず収束速度を損なう。
steffensen法にインスパイアされた2つの適応学習率を導入する。確率的最適化設定での使用を意図しており、バッチサイズ以外にハイパーパラメータチューニングは不要である。
広範な実験により、既存のいくつかの一階法と比較できることがわかった。
二次目的に制限された場合、確率的シュテッフェンセン法はランダム化されたカッツマルツ法に還元される(これはSGD や SLBFGS には当てはまらない)。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates
and Practical Features [79.39965431772626]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳(メタデータ) (2023-04-23T20:05:09Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳(メタデータ) (2022-11-03T14:12:51Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - On the Second-order Convergence Properties of Random Search Methods [7.788439526606651]
本研究では,2次情報に依存しない標準的なランダム検索手法が2次定常点に収束することを証明する。
本稿では,関数評価のみに依存する負曲率の新しい変種を提案する。
論文 参考訳(メタデータ) (2021-10-25T20:59:31Z) - Second-order Neural Network Training Using Complex-step Directional
Derivative [41.4333906662624]
本稿では,2次ニューラルネットワークトレーニングのための数値アルゴリズムを提案する。
複素ステップ有限差分を用いてヘッセン計算の実践的障害に取り組む。
提案手法は,ディープラーニングと数値最適化のための新しいアルゴリズムを広範囲に導入すると考えられる。
論文 参考訳(メタデータ) (2020-09-15T13:46:57Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。