論文の概要: Almost-sure convergence of iterates and multipliers in stochastic
sequential quadratic optimization
- arxiv url: http://arxiv.org/abs/2308.03687v1
- Date: Mon, 7 Aug 2023 16:03:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-08 12:53:50.761833
- Title: Almost-sure convergence of iterates and multipliers in stochastic
sequential quadratic optimization
- Title(参考訳): 確率的逐次2次最適化におけるイテレートと乗数のほぼ確実収束
- Authors: Frank E. Curtis, Xin Jiang, and Qi Wang
- Abstract要約: 等式制約付き連続最適化問題の解法が近年注目されている。
収束保証は、ゼロを測定するための勾配の期待値に制限されている。
また,SQPアルゴリズムにより生成した予備値,ラグランジュ測度,ステーション測度に対する新たなほぼ収束保証を証明した。
- 参考スコア(独自算出の注目度): 21.022322975077653
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic sequential quadratic optimization (SQP) methods for solving
continuous optimization problems with nonlinear equality constraints have
attracted attention recently, such as for solving large-scale data-fitting
problems subject to nonconvex constraints. However, for a recently proposed
subclass of such methods that is built on the popular stochastic-gradient
methodology from the unconstrained setting, convergence guarantees have been
limited to the asymptotic convergence of the expected value of a stationarity
measure to zero. This is in contrast to the unconstrained setting in which
almost-sure convergence guarantees (of the gradient of the objective to zero)
can be proved for stochastic-gradient-based methods. In this paper, new
almost-sure convergence guarantees for the primal iterates, Lagrange
multipliers, and stationarity measures generated by a stochastic SQP algorithm
in this subclass of methods are proved. It is shown that the error in the
Lagrange multipliers can be bounded by the distance of the primal iterate to a
primal stationary point plus the error in the latest stochastic gradient
estimate. It is further shown that, subject to certain assumptions, this latter
error can be made to vanish by employing a running average of the Lagrange
multipliers that are computed during the run of the algorithm. The results of
numerical experiments are provided to demonstrate the proved theoretical
guarantees.
- Abstract(参考訳): 非線形等式制約による連続最適化問題の解法である確率逐次2次最適化法(SQP)は,非凸制約による大規模データ適合問題の解法など,近年注目されている。
しかし、制約のない設定から一般的な確率勾配法に基づいて構築された、最近提案されたそのような方法のサブクラスに対して、収束保証は、定常測度の期待値のゼロへの漸近収束に制限されている。
これは、(目的からゼロへの勾配の)ほとんど余剰収束を保証するような制約のない設定が確率的勾配に基づく手法で証明されるのとは対照的である。
本稿では,本サブクラスにおける確率的sqpアルゴリズムによって生成された主イテレート,ラグランジュ乗算器,定常測度に対する新たな近似収束保証を証明した。
ラグランジュ乗算器の誤差は、原始反復点から原始定常点までの距離と最新の確率勾配推定における誤差によって境界付けられることが示されている。
さらに、ある仮定に従うと、この後者の誤差はアルゴリズムの実行中に計算されるラグランジュ乗算器の実行平均を利用することで消滅させることができる。
理論的な保証を実証するために数値実験の結果が得られた。
関連論文リスト
- On the Last-Iterate Convergence of Shuffling Gradient Methods [25.831462008050387]
対象値に関して勾配法をシャッフルする際の最終点収束率を示す。
我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
論文 参考訳(メタデータ) (2024-03-12T15:01:17Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Low-Rank Tensor Completion via Novel Sparsity-Inducing Regularizers [30.920908325825668]
低ランクテンソル完備化問題において、l1-ノルムを緩和するため、非ランクサロゲート/正則化器が提案されている。
これらの正則化器は核ランク復元に適用され,乗算器法に基づく効率的なアルゴリズムが提案されている。
論文 参考訳(メタデータ) (2023-10-10T01:00:13Z) - A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。
提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
論文 参考訳(メタデータ) (2023-04-28T15:30:43Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - A Sequential Quadratic Programming Method with High Probability
Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.535271349350579]
制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。
1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
論文 参考訳(メタデータ) (2023-01-01T21:46:50Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - 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) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。