論文の概要: Asymptotic Convergence Rate and Statistical Inference for Stochastic
Sequential Quadratic Programming
- arxiv url: http://arxiv.org/abs/2205.13687v1
- Date: Fri, 27 May 2022 00:34:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 08:53:02.402071
- Title: Asymptotic Convergence Rate and Statistical Inference for Stochastic
Sequential Quadratic Programming
- Title（参考訳）: 確率的逐次二次計画における漸近収束率と統計的推論
- Authors: Sen Na, Michael W. Mahoney
- Abstract要約: 制約付き非線形最適化問題を解くために、逐次2次アルゴリズム(StoSQP)を適用する。
分布関数の収束度を定量的に測定するために、$(x_t, lambda_t)$に対してベリー・エスキーを確立する。
- 参考スコア（独自算出の注目度）: 59.36379287247961
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We apply a stochastic sequential quadratic programming (StoSQP) algorithm to
solve constrained nonlinear optimization problems, where the objective is
stochastic and the constraints are deterministic. We study a fully stochastic
setup, where only a single sample is available in each iteration for estimating
the gradient and Hessian of the objective. We allow StoSQP to select a random
stepsize $\bar{\alpha}_t$ adaptively, such that $\beta_t\leq \bar{\alpha}_t
\leq \beta_t+\chi_t$, where $\beta_t$, $\chi_t=o(\beta_t)$ are prespecified
deterministic sequences. We also allow StoSQP to solve Newton system inexactly
via randomized iterative solvers, e.g., with the sketch-and-project method; and
we do not require the approximation error of inexact Newton direction to
vanish. For this general StoSQP framework, we establish the asymptotic
convergence rate for its last iterate, with the worst-case iteration complexity
as a byproduct; and we perform statistical inference. In particular, with
proper decaying $\beta_t,\chi_t$, we show that: (i) the StoSQP scheme can take
at most $O(1/\epsilon^4)$ iterations to achieve $\epsilon$-stationarity; (ii)
asymptotically and almost surely, $\|(x_t -x^\star, \lambda_t -
\lambda^\star)\| = O(\sqrt{\beta_t\log(1/\beta_t)})+O(\chi_t/\beta_t)$, where
$(x_t,\lambda_t)$ is the primal-dual StoSQP iterate; (iii) the 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.
Moreover, we establish the Berry-Esseen bound for $(x_t, \lambda_t)$ to measure
quantitatively the convergence of its distribution function. We also provide a
practical estimator for the covariance matrix, from which the confidence
intervals of $(x^\star, \lambda^\star)$ can be constructed using iterates
$\{(x_t,\lambda_t)\}_t$. Our theorems are validated using nonlinear problems in
CUTEst test set.
- Abstract（参考訳）: 対象が確率的であり,制約が決定論的である制約付き非線形最適化問題を解くために,確率的逐次二次計画 (stosqp) アルゴリズムを適用する。
目的の勾配と Hessian を推定するために,各イテレーションで1つのサンプルしか利用できない,完全に確率的な設定について検討する。
例えば、$\beta_t\leq \bar{\alpha}_t \leq \beta_t+\chi_t$ であり、ここで$\beta_t$, $\chi_t=o(\beta_t)$ は決定論的順序である。
また、StoSQPは、例えばスケッチ・アンド・プロジェクト法のようなランダム化反復解法によってニュートンシステムの不正確な解法を許容し、不正確なニュートン方向の近似誤差は不要である。
この一般的なStoSQPフレームワークでは,その最終反復に対する漸近収束率を確立し,最悪の繰り返しの複雑さを副生成物として,統計的推論を行う。
特に、適切に崩壊する $\beta_t,\chi_t$ とすると、
(i)StoSQPスキームは、少なくとも$O(1/\epsilon^4)$繰り返して$\epsilon$-stationarityを達成することができる。
(ii)漸近的に、ほぼ確実に、$\|(x_t -x^\star, \lambda_t\lambda^\star)\| = O(\sqrt{\beta_t\log(1/\beta_t)})+O(\chi_t/\beta_t)$, ここで$(x_t,\lambda_t)$は、原始双対StoSQPイテレートである。
3) 1/\sqrt{\beta_t}\cdot (x_t -x^\star, \lambda_t - \lambda^\star)$ は非自明な共分散行列を持つ平均零ガウス分布に収束する。
さらに、その分布関数の収束を定量的に測定するために、$(x_t, \lambda_t)$ のberry-esseenバウンドを確立する。
また、共分散行列の実用的推定器を提供し、そこから$(x^\star, \lambda^\star)$の信頼区間を $\{(x_t,\lambda_t)\}_t$ を使って構築することができる。
我々の定理は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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。