論文の概要: Retrospective Approximation for Smooth Stochastic Optimization
- arxiv url: http://arxiv.org/abs/2103.04392v1
- Date: Sun, 7 Mar 2021 16:29:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-11 00:00:00.574520
- Title: Retrospective Approximation for Smooth Stochastic Optimization
- Title（参考訳）: Smooth Stochastic Optimizationのレトロスペクティブ近似
- Authors: David Newton, Raghu Bollapragada, Raghu Pasupathy, Nung Kwan Yip
- Abstract要約: 我々は,普遍近似問題サイズパラダイムとしてふりかえり近似(ra)を提案する。
線形探索準探索によるRAの性能について,不条件最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
- 参考スコア（独自算出の注目度）: 1.0323063834827415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider stochastic optimization problems where a smooth (and potentially
nonconvex) objective is to be minimized using a stochastic first-order oracle.
These type of problems arise in many settings from simulation optimization to
deep learning. We present Retrospective Approximation (RA) as a universal
sequential sample-average approximation (SAA) paradigm where during each
iteration $k$, a sample-path approximation problem is implicitly generated
using an adapted sample size $M_k$, and solved (with prior solutions as "warm
start") to an adapted error tolerance $\epsilon_k$, using a "deterministic
method" such as the line search quasi-Newton method. The principal advantage of
RA is that decouples optimization from stochastic approximation, allowing the
direct adoption of existing deterministic algorithms without modification, thus
mitigating the need to redesign algorithms for the stochastic context. A second
advantage is the obvious manner in which RA lends itself to parallelization. We
identify conditions on $\{M_k, k \geq 1\}$ and $\{\epsilon_k, k\geq 1\}$ that
ensure almost sure convergence and convergence in $L_1$-norm, along with
optimal iteration and work complexity rates. We illustrate the performance of
RA with line-search quasi-Newton on an ill-conditioned least squares problem,
as well as an image classification problem using a deep convolutional neural
net.
- Abstract（参考訳）: 確率的一階オラクルを用いてスムーズな(そして潜在的に非凸な)目的を最小化する確率的最適化問題を考察する。
このような問題は、シミュレーション最適化からディープラーニングまで、多くの設定で発生します。
本論文では,各イテレーションで$k$のサンプルパス近似問題を適応したサンプルサイズ$M_k$を用いて暗黙的に生成し,行探索準ニュートン法のような「決定論的方法」を用いて,適応した誤差許容度$\epsilon_k$に(事前の解法で)解決する,普遍的な逐次サンプル平均近似(SAA)パラダイムとして,Retrospective Approximation (RA) を提案する。
RAの主な利点は、最適化を確率的近似から切り離すことであり、既存の決定論的アルゴリズムを修正なしで直接採用できるため、確率的コンテキストのためのアルゴリズムを再設計する必要性が軽減される。
2つめの利点は、RAが並列化に寄与する明らかな方法である。
m_k, k \geq 1\}$ および $\{\epsilon_k, k\geq 1\}$ の条件を特定し、ほぼ確実に $l_1$-norm での収束と収束を保証し、最適なイテレーションと作業の複雑さ率を提供する。
線形探索準ニュートンを用いたRAの性能について,未条件の最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
関連論文リスト
- Near-Optimal High-Probability Convergence for Non-Convex Stochastic
Optimization with Variance Reduction [17.408563601880253]
大規模分散における非還元最適化のための新しいアルゴリズムを提案する。
我々のアルゴリズムは$(T$delta)/分散の速度で収束することを示す。
これは最高の結果を得るための最初の高い確率のイテレーションです。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic
Minimax Optimization [14.719077076351377]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
論文 参考訳（メタデータ） (2022-08-11T16:55:26Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳（メタデータ） (2020-10-22T22:54:54Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - 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) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳（メタデータ） (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。