論文の概要: 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の性能について,未条件の最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
関連論文リスト
- Accelerated stochastic approximation with state-dependent noise [7.623467689146604]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。
このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。
SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文 参考訳(メタデータ) (2023-07-04T06:06:10Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳(メタデータ) (2023-05-28T06:33:37Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳(メタデータ) (2022-10-23T23:23:23Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic
Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。
問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。
また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文 参考訳(メタデータ) (2021-09-07T17:21:09Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Stochastic Compositional Gradient Descent under Compositional
constraints [13.170519806372075]
目的関数と制約関数が凸であり,関数の合成として表される制約最適化問題について検討する。
この問題は、公平な分類/回帰とキューシステムの設計に生じる。
提案手法は最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
論文 参考訳(メタデータ) (2020-12-17T05:38:37Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳(メタデータ) (2020-12-07T19:14:49Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。