論文の概要: 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 には当てはまらない)。
関連論文リスト
- Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function [14.986031916712108]
勾配追跡手法の一点推定に基づくゼロ階分散最適化手法を提案する。
我々は,この手法が雑音条件下で数値関数と収束することを証明した。
論文 参考訳(メタデータ) (2024-10-08T11:45:45Z) - Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。
これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。
本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
論文 参考訳(メタデータ) (2024-08-14T03:27:48Z) - An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。
本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
論文 参考訳(メタデータ) (2024-07-05T08:53:06Z) - 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 [65.64276393443346]
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 [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。