Asymptotic Convergence Rate and Statistical Inference for Stochastic Sequential Quadratic Programming
Asymptotic Convergence Rate and Statistical Inference for Stochastic Sequential Quadratic Programming
复制标题
DOI：
10.48550/arxiv.2205.13687
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sen Na;Michael W. Mahoney
中科院分区：
文献类型：
--
作者：
Sen Na;Michael W. Mahoney
我们应用随机顺序二次规划（StoSQP）算法来解决约束非线性优化问题，其中目标是随机的，约束是相等且确定的。我们研究了完全随机的设置，其中每次迭代中只有一个样本可用于估计目标的梯度和 Hessian 矩阵。我们允许 StoSQP 自适应地选择随机步长 ᾱt，使得 βt ≤ ᾱt ≤ βt +χt，其中 βt、χt = o(βt) 是预先指定的确定性序列。我们还允许 StoSQP 通过随机迭代求解器不精确地求解牛顿系统，例如使用草图和投影方法；并且我们不需要不精确的牛顿方向的近似误差消失（因此，每次迭代的计算成本不会爆炸）。对于这个通用的 StoSQP 框架，我们建立了其最后一次迭代的渐近收敛率，并将最坏情况的迭代复杂度作为副产品；我们进行统计推断。特别是，在温和的假设和适当的衰减序列 βt、χt 下，我们表明： (i) StoSQP 方案最多可以花费 O(1/·) 迭代来实现平稳性； (ii) 渐进且几乎肯定地， ‖(xt−x,λt−λ)‖ = O( √ βt log(1/βt))+O(χt/βt)，其中 (xt,λt) 是原始 StoSQP 迭代； (iii) 序列 1/ √ βt · (xt−x,λt−λ) 收敛到具有非平凡协方差矩阵的均值零高斯分布。此外，我们建立了 (xt,λt) 的 Berry-Esseen 界来定量测量其分布函数的收敛性。我们还为协方差矩阵提供了一个实用的估计器，可以使用迭代 {(xt,λt)}t 来构造 (x,λ) 的置信区间（或区域）。我们所有的定理都使用 CUTEst 测试集中的非线性问题进行验证。
We apply a stochastic sequential quadratic programming (StoSQP) algorithm to solve constrained nonlinear optimization problems, where the objective is stochastic and the constraints are in equality and 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 ᾱt adaptively, such that βt ≤ ᾱt ≤ βt +χt, where βt, χt = o(β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 (thus, the per-iteration computational cost does not blow up). 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, under mild assumptions and with proper decaying sequences βt, χt, we show that: (i) the StoSQP scheme can take at most O(1/ ) iterations to achieve -stationarity; (ii) asymptotically and almost surely, ‖(xt−x,λt−λ)‖ = O( √ βt log(1/βt))+O(χt/βt), where (xt,λt) is the primaldual StoSQP iterate; (iii) the sequence 1/ √ βt · (xt−x,λt−λ) converges to a mean zero Gaussian distribution with a nontrivial covariance matrix. Furthermore, we establish the Berry-Esseen bound for (xt,λ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 (or regions) of (x,λ) can be constructed using the iterates {(xt,λt)}t. All our theorems are validated using nonlinear problems in CUTEst test set.