論文の概要: Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees
- arxiv url: http://arxiv.org/abs/2409.09906v3
- Date: Thu, 10 Oct 2024 12:30:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-11 14:28:54.418547
- Title: Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees
- Title(参考訳): 強い収束保証をもつ確率的非凸最適化のための可変化一階法
- Authors: Zhaosong Lu, Sanyou Mei, Yifeng Xiao,
- Abstract要約: 既存の方法は典型的には$epsilon$-stochasticの固定点を見つけることを目的としている。
多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$epsilon$-stochasticの定常点が望ましくない可能性がある。
- 参考スコア(独自算出の注目度): 1.2562458634975162
- License:
- Abstract: In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an $\epsilon$-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy $\epsilon$. However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, making such an $\epsilon$-stochastic stationary point potentially undesirable due to the risk of significant constraint violations. To address this issue, we propose single-loop variance-reduced stochastic first-order methods, where the stochastic gradient of the stochastic component is computed using either a truncated recursive momentum scheme or a truncated Polyak momentum scheme for variance reduction, while the gradient of the deterministic component is computed exactly. Under the error bound condition with a parameter $\theta \geq 1$ and other suitable assumptions, we establish that these methods respectively achieve a sample and first-order operation complexity of $\widetilde O(\epsilon^{-\max\{\theta+2, 2\theta\}})$ and $\widetilde O(\epsilon^{-\max\{4, 2\theta\}})$ for finding a stronger $\epsilon$-stochastic stationary point, where the constraint violation is within $\epsilon$ with certainty, and the expected violation of first-order stationarity is within $\epsilon$. For $\theta=1$, these complexities reduce to $\widetilde O(\epsilon^{-3})$ and $\widetilde O(\epsilon^{-4})$ respectively, which match, up to a logarithmic factor, the best-known complexities achieved by existing methods for finding an $\epsilon$-stochastic stationary point of unconstrained smooth stochastic optimization problems.
- Abstract(参考訳): 本稿では,決定論的に制約された確率的最適化問題のクラスについて検討する。
既存の方法は、通常$\epsilon$-stochastic固定点を見つけることを目的としている。
しかし、多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$\epsilon$-stochasticな定常点が、重大な制約違反のリスクのために望ましくない可能性がある。
そこで本研究では, 確率成分の確率勾配を, 確率成分の傾きを正確に計算しながら, 再帰的モーメントスキームか, 縮退的ポリアクモーメントスキームのいずれかを用いて計算する, 単一ループ分散帰納確率一階法を提案する。
パラメータ $\theta \geq 1$ などの適切な仮定で誤差境界条件の下では、これらの手法がそれぞれ$\widetilde O(\epsilon^{-\max\{\theta+2, 2\theta\}})$と$\widetilde O(\epsilon^{-\max\{4, 2\theta\}})$のサンプルと1次演算の複雑さを達成し、より強い$\epsilon$-stochastic定常点を見つけるための$\epsilon$-stochastic定常点(英語版)は$\epsilon$内であり、期待される1次定常性は$\epsilon$内である。
$\theta=1$の場合、これらの複雑さは、それぞれ$\widetilde O(\epsilon^{-3})$と$\widetilde O(\epsilon^{-4})$に減少する。
関連論文リスト
- Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳(メタデータ) (2024-06-27T18:38:42Z) - A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳(メタデータ) (2024-05-24T21:09:19Z) - Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。
また、勾配法のようなベースラインよりも2~3$times$早く収束できることも示している。
論文 参考訳(メタデータ) (2023-10-21T00:03:54Z) - Almost-sure convergence of iterates and multipliers in stochastic
sequential quadratic optimization [21.022322975077653]
等式制約付き連続最適化問題の解法が近年注目されている。
収束保証は、ゼロを測定するための勾配の期待値に制限されている。
また,SQPアルゴリズムにより生成した予備値,ラグランジュ測度,ステーション測度に対する新たなほぼ収束保証を証明した。
論文 参考訳(メタデータ) (2023-08-07T16:03:40Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。