論文の概要: 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テストセットの非線形問題を用いて検証される。
関連論文リスト
- Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳(メタデータ) (2023-11-05T03:33:44Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳(メタデータ) (2021-02-15T07:10:33Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - Coordinate Methods for Matrix Games [41.821881312775496]
我々は,MathcalX max_yinmathY ytop A x$ の $min_x 形式の双線形サドル点問題を解くための主対座標法を開発した。
提案手法は,既存のサブ線形手法を,各項目の複雑性とサンプルの複雑さの観点から限界に推し進める。
論文 参考訳(メタデータ) (2020-09-17T17:55:03Z) - Fast and Near-Optimal Diagonal Preconditioning [46.240079312553796]
左か右の対角線再スケーリングにより$mathbfA$の条件数を改善する方法を示す。
構造化混合パッキングと半定値プログラムを対象とし,$widetildeO(textnnz(mathbfA) cdot textpoly(kappastar))$ timeに対して,$mathbfA$の定数係数最適スケーリングを計算する。
論文 参考訳(メタデータ) (2020-08-04T17:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。