論文の概要: 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-11-07 20:46:36.395475
• 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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})$に減少する。

関連論文リスト

• A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization [17.25924791071807]
  複雑な制約に対する新しい種類の下次アルゴリズムを提案する。 提案手法は, 2-of-the-artアルゴリズムよりもはるかに高速であることを示す。
  論文  参考訳（メタデータ） (2025-01-31T15:18:52Z)
• 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)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• 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)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• 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)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。