論文の概要: Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming
- arxiv url: http://arxiv.org/abs/2205.13687v4
- Date: Sat, 13 Apr 2024 21:08:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 00:46:46.592426
- Title: Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming
- Title（参考訳）: Sketched Sequential Quadratic Programmingによる制約付き確率最適化の統計的推定
- Authors: Sen Na, Michael W. Mahoney,
- Abstract要約: 制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
- 参考スコア（独自算出の注目度）: 53.63469275932989
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider online statistical inference of constrained stochastic nonlinear optimization problems. We apply the Stochastic Sequential Quadratic Programming (StoSQP) method to solve these problems, which can be regarded as applying second-order Newton's method to the Karush-Kuhn-Tucker (KKT) conditions. In each iteration, the StoSQP method computes the Newton direction by solving a quadratic program, and then selects a proper adaptive stepsize $\bar{\alpha}_t$ to update the primal-dual iterate. To reduce dominant computational cost of the method, we inexactly solve the quadratic program in each iteration by employing an iterative sketching solver. Notably, the approximation error of the sketching solver need not vanish as iterations proceed, meaning that the per-iteration computational cost does not blow up. For the above StoSQP method, we show that under mild assumptions, the rescaled primal-dual sequence $1/\sqrt{\bar{\alpha}_t}\cdot (x_t - x^\star, \lambda_t - \lambda^\star)$ converges to a mean-zero Gaussian distribution with a nontrivial covariance matrix depending on the underlying sketching distribution. To perform inference in practice, we also analyze a plug-in covariance matrix estimator. We illustrate the asymptotic normality result of the method both on benchmark nonlinear problems in CUTEst test set and on linearly/nonlinearly constrained regression problems.
- Abstract（参考訳）: 制約付き確率非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するためにStoSQP法を適用し、Karush-Kuhn-Tucker(KKT)条件にニュートン法を適用したと見なすことができる。
それぞれの反復において、StoSQP法は2次プログラムを解くことでニュートン方向を計算し、次に適切な適応ステップサイズ $\bar{\alpha}_t$ を選択して、原始二元イテレートを更新する。
提案手法の計算コストを抑えるため,反復的スケッチ解法を用いて各反復における二次的プログラムを不正確に解いた。
特に、反復が進むにつれてスケッチ解決器の近似誤差が消える必要はない。
上述のStoSQP法では、微妙な仮定で、再スケールされた原始-双対列 $1/\sqrt {\bar{\alpha}_t}\cdot (x_t - x^\star, \lambda_t - \lambda^\star)$ が、下層のスケッチ分布に依存する非自明な共分散行列を持つ平均零ガウス分布に収束することを示す。
実際に推論を行うため,プラグイン共分散行列推定器も解析する。
本稿では、CUTEstテストセットにおけるベンチマーク非線形問題と線形・非線形制約回帰問題の両方について、この手法の漸近正規性結果について述べる。
関連論文リスト
- Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳（メタデータ） (2024-09-24T04:39:47Z) - Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。
これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。
本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
論文 参考訳（メタデータ） (2024-08-14T03:27:48Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳（メタデータ） (2021-06-22T07:24:17Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - An Adaptive Stochastic Sequential Quadratic Programming with
Differentiable Exact Augmented Lagrangians [17.9230793188835]
本稿では,客観的・決定論的等式を考慮した非線形最適化プログラムの解法について考察する。
本稿では,微分可能な拡張ラグランジアンをメリット関数として用いた逐次二次計画法(SQP)を提案する。
提案アルゴリズムは,行探索手順と1行探索手順を許容する最初のSQPである。
論文 参考訳（メタデータ） (2021-02-10T08:40:55Z) - Coordinate Methods for Matrix Games [41.821881312775496]
我々は,MathcalX max_yinmathY ytop A x$ の $min_x 形式の双線形サドル点問題を解くための主対座標法を開発した。
提案手法は,既存のサブ線形手法を,各項目の複雑性とサンプルの複雑さの観点から限界に推し進める。
論文 参考訳（メタデータ） (2020-09-17T17:55:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。