論文の概要: Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods
- arxiv url: http://arxiv.org/abs/2211.01832v1
- Date: Thu, 3 Nov 2022 14:12:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-04 13:00:46.269300
- Title: Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods
- Title(参考訳): Extra-Newton: 雑音適応型2次法の最初のアプローチ
- Authors: Kimon Antonakopoulos, Ali Kavis, Volkan Cevher
- Abstract要約: 本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
- 参考スコア(独自算出の注目度): 57.050204432302195
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work proposes a universal and adaptive second-order method for
minimizing second-order smooth, convex functions. Our algorithm achieves
$O(\sigma / \sqrt{T})$ convergence when the oracle feedback is stochastic with
variance $\sigma^2$, and improves its convergence to $O( 1 / T^3)$ with
deterministic oracles, where $T$ is the number of iterations. Our method also
interpolates these rates without knowing the nature of the oracle apriori,
which is enabled by a parameter-free adaptive step-size that is oblivious to
the knowledge of smoothness modulus, variance bounds and the diameter of the
constrained set. To our knowledge, this is the first universal algorithm with
such global guarantees within the second-order optimization literature.
- Abstract(参考訳): 本研究では,二階滑らかな凸関数を最小化する普遍的かつ適応的な二階法を提案する。
このアルゴリズムは、oracleのフィードバックが分散$\sigma^2$で確率的であるときに$o(\sigma / \sqrt{t})$収束を達成し、決定論的オラクルで$o(1 / t^3)$に収束し、ここで$t$は反復数である。
この方法は、oracle aprioriの性質を知らずにこれらのレートを補間するものであり、これは、滑らかさのモジュラリティ、分散境界、制約付き集合の直径の知識に従わないパラメータフリー適応ステップサイズによって実現される。
我々の知る限りでは、これは二階最適化文献にそのような大域的保証を持つ最初の普遍的アルゴリズムである。
関連論文リスト
- Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳(メタデータ) (2023-07-04T16:55:41Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - 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) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳(メタデータ) (2022-02-09T06:05:38Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳(メタデータ) (2021-11-01T15:43:36Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳(メタデータ) (2020-10-22T22:54:54Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳(メタデータ) (2020-08-24T15:57:50Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。