論文の概要: 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の性能について,未条件の最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
関連論文リスト
- A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression [22.917692982875025]
一階微分しか持たない関数を$f$で扱える新しいLyapunov関数を導入する。
一般の減少段数と定数段数の下で有限時間モーメント境界を導出する。
我々の結果は、特にオンライン統計手法に広く応用されている。
論文 参考訳（メタデータ） (2025-04-11T00:20:37Z) - New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Composition [11.530542389959347]
L-凸性(QC)、擬似成長(SmoothQG)、制限不等式(RSI)などの非次元設定における一階最適化の基本的限界を示す。
論文 参考訳（メタデータ） (2025-02-19T19:21:00Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
勾配観測における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) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う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 Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。