論文の概要: Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming

• arxiv url: http://arxiv.org/abs/2205.13687v3
• Date: Thu, 3 Aug 2023 22:50:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-07 16:50:46.841167
• Title: Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming
• Title（参考訳）: Sketched Sequential Quadratic Programmingによる制約付き確率最適化の統計的推定
• Authors: Sen Na, Michael W. Mahoney
• Abstract要約: この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。 最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。 また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
• 参考スコア（独自算出の注目度）: 59.36379287247961
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider statistical inference of equality-constrained stochastic nonlinear optimization problems. We develop a fully online stochastic sequential quadratic programming (StoSQP) method to solve the problems, which can be regarded as applying Newton's method to the first-order optimality conditions (i.e., the KKT conditions). Motivated by recent designs of numerical second-order methods, we allow StoSQP to adaptively select any random stepsize $\bar{\alpha}_t$, as long as $\beta_t\leq \bar{\alpha}_t \leq \beta_t+\chi_t$, for some control sequences $\beta_t$ and $\chi_t=o(\beta_t)$. To reduce the dominant computational cost of second-order methods, we additionally allow StoSQP to inexactly solve quadratic programs via efficient randomized iterative solvers that utilize sketching techniques. Notably, we do not require the approximation error to diminish as iteration proceeds. For the developed method, we show that under mild assumptions (i) computationally, it can take at most $O(1/\epsilon^4)$ iterations (same as samples) to attain $\epsilon$-stationarity; (ii) statistically, its primal-dual sequence $1/\sqrt{\beta_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. Additionally, we establish the almost-sure convergence rate of the iterate $(x_t, \lambda_t)$ along with the Berry-Esseen bound; the latter quantitatively measures the convergence rate of the distribution function. We analyze a plug-in limiting covariance matrix estimator, and demonstrate the performance of the method both on benchmark nonlinear problems in CUTEst test set and on linearly/nonlinearly constrained regression problems.
• Abstract（参考訳）: 等式制約付き確率的非線形最適化問題の統計的推測を考察する。 本稿では,一階最適条件(すなわち kkt 条件)にニュートン法を適用することができる完全オンライン確率的逐次二次計画法(stosqp)を開発した。 最近の数値二階法の設計により、stosqp は$\beta_t\leq \bar{\alpha}_t \leq \beta_t+\chi_t$ の制御列に対して$\beta_t$ と $\chi_t=o(\beta_t)$ の任意のランダムステップを適応的に選択できる。 また,2次法の計算コストを抑えるために,スケッチ手法を用いた効率的なランダム化反復解法を用いて,StoSQPが2次プログラムを不正確に解くことを可能にする。 特に、イテレーションが進むにつれて近似誤差を減少させる必要はない。 開発した手法では 軽度の仮定の下で (i)計算上、最大$o(1/\epsilon^4)$イテレーション(サンプルと同じ)を要し、$\epsilon$-stationarityを得ることができる。 (II)統計的には、その原始双対列 $1/\sqrt{\beta_t}\cdot (x_t - x^\star, \lambda_t - \lambda^\star)$ は、下層のスケッチ分布に依存する非自明な共分散行列を持つ平均零ガウス分布に収束する。 さらに, 繰り返し値$(x_t, \lambda_t)$ とberry-esseenバウンドの近似収束率を定式化し, 分布関数の収束率を定量的に測定した。 我々は,プラグイン制限共分散行列推定器を解析し,CUTEstテストセットのベンチマーク非線形問題と線形・非線形制約回帰問題の両方において,本手法の性能を示す。

関連論文リスト

• Online Covariance Matrix Estimation in Sketched Newton Methods [7.441891256588546]
  ランダム化されたスケッチ技術を利用して各イテレーションで近似したニュートンステップを実行するオンラインスケッチNewton法について検討する。 また、制約された問題に対する推定器の拡張についても論じ、回帰問題に対する優れた性能を示す。
  論文  参考訳（メタデータ） (2025-02-10T23:11:02Z)
• Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
  パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。 これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
  論文  参考訳（メタデータ） (2024-12-05T10:38:29Z)
• 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)
• 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)

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

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