論文の概要: High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise

• arxiv url: http://arxiv.org/abs/2503.19091v1
• Date: Mon, 24 Mar 2025 19:23:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-26 16:50:37.603504
• Title: High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise
• Title（参考訳）: 重音を用いた信頼関係確率的逐次二次計画法の高確率複素性境界
• Authors: Yuchen Fang, Javad Lavaei, Katya Scheinberg, Sen Na,
• Abstract要約: 本稿では,TR-SSQP(Trust-Region Sequential Quadratic Programming)法を提案する。 一階および二階の$epsilon$-stationary点を特定するための高確率複雑性境界を確立する。 より弱い雑音条件下では,本手法は高確率な1次繰り返し複雑性境界を実現する。
• 参考スコア（独自算出の注目度）: 24.211570934025566
• License:
• Abstract: In this paper, we consider nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method and establish its high-probability iteration complexity bounds for identifying first- and second-order $\epsilon$-stationary points. In our algorithm, we assume that exact objective values, gradients, and Hessians are not directly accessible but can be estimated via zeroth-, first-, and second-order probabilistic oracles. Compared to existing complexity studies of SSQP methods that rely on a zeroth-order oracle with sub-exponential tail noise (i.e., light-tailed) and focus mostly on first-order stationarity, our analysis accommodates irreducible and heavy-tailed noise in the zeroth-order oracle and significantly extends the analysis to second-order stationarity. We show that under weaker noise conditions, our method achieves the same high-probability first-order iteration complexity bounds, while also exhibiting promising second-order iteration complexity bounds. Specifically, the method identifies a first-order $\epsilon$-stationary point in $\mathcal{O}(\epsilon^{-2})$ iterations and a second-order $\epsilon$-stationary point in $\mathcal{O}(\epsilon^{-3})$ iterations with high probability, provided that $\epsilon$ is lower bounded by a constant determined by the irreducible noise level in estimation. We validate our theoretical findings and evaluate the practical performance of our method on CUTEst benchmark test set.
• Abstract（参考訳）: 本稿では,確率的目的と決定論的等式制約による非線形最適化問題を考察する。 本稿では,Trust-Regstic Stochastic Sequential Quadratic Programming (TR-SSQP)法を提案する。 我々のアルゴリズムでは、正確な目的値、勾配、およびヘッセンは直接アクセスできないが、ゼロ階、第1階、第2階の確率的オラクルによって推定できると仮定する。 SSQP法は,ゼロ階の尾のノイズ(すなわち光尾のノイズ)に頼り,主に一階の定常性に焦点をあてる既存の複雑性研究と比較して,ゼロ階のオラクルにおける既約および重尾のノイズを許容し,解析を二階の定常性に著しく拡張する。 より弱い雑音条件下では,本手法は同じ高確率な1次繰り返し複雑性境界を達成できると同時に,有望な2次繰り返し複雑性境界を示す。 具体的には、$\epsilon$-stationary point in $\mathcal{O}(\epsilon^{-2})$ iterationsと$\epsilon$-stationary point in $\mathcal{O}(\epsilon^{-3})$ iterations with high probability, if $\epsilon$ is lower bounded by a constant by the irreducible noise level in Estimation。 CUTEstベンチマークテストセットにおいて,提案手法の有効性を検証し,その有効性を検証した。

関連論文リスト

• Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Extensions to Distributed Optimization and Comparison Oracle [77.3806516979843]
  SignSGDは, 高い精度で, 最適な試料量$tildeO(varepsilon-frac3kappa - 2kappa 1right)を達成できることを示す。 また、2つの異なる点における関数値を比較することしかできないオラクルを用いて、符号演算子のゼロ階最適化への応用についても検討する。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees [1.2562458634975162]
  既存の方法は典型的には$epsilon$-stochasticの固定点を見つけることを目的としている。 多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$epsilon$-stochasticの定常点が望ましくない可能性がある。
  論文  参考訳（メタデータ） (2024-09-16T00:26:42Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
  一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。 完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。 MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-26T05:34:21Z)
• 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)
• 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 Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• 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)

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

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