論文の概要: 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テストセットのベンチマーク非線形問題と線形・非線形制約回帰問題の両方において,本手法の性能を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。