提出一种无需矩阵求逆的在线优化推断方法,可实时构建有效置信区间。
Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling
- 基于随机压缩的拟牛顿法构造迭代解,避免显式矩阵运算。
- 理论证明其统计量渐近分布不依赖未知参数,可用于构造置信区间。
- 适合大规模在线学习中需实时决策且无历史数据存储的场景。
约束型随机非线性优化问题因其能建模物理、经济和生物等复杂现实场景而受到广泛关注。随着数据规模持续增长,在线推断方法对实现无需存储历史数据的实时决策至关重要。本文提出一种基于随机压缩的随机序贯二次规划(SSQP)的在线推断方法。该方法在每步用二次模型近似目标函数,线性模型近似约束条件,并通过随机压缩求解器近似求解子问题。在此基础上,我们设计了一种新的随机缩放方法:基于SSQP迭代序列构造检验统计量,其极限分布不含未知参数。相比现有方法,本方法具备两大优势:(i) 可构造渐近有效的置信区间;(ii) 矩阵自由,计算仅涉及原-对偶迭代变量 $(\boldsymbol{x}_t, \boldsymbol{\lambda}_t)$,无需矩阵求逆。我们在非线性约束回归问题上通过数值实验验证了理论,并展示了随机缩放方法优于现有推断方法的性能。
原文摘要 · Abstract (English)
Constrained stochastic nonlinear optimization problems have attracted significant attention for their ability to model complex real-world scenarios in physics, economics, and biology. As datasets continue to grow, online inference methods have become crucial for enabling real-time decision-making without the need to store historical data. In this work, we develop an online inference procedure for constrained stochastic optimization by leveraging a method called Sketched Stochastic Sequential Quadratic Programming (SSQP). As a direct generalization of sketched Newton methods, SSQP approximates the objective with a quadratic model and the constraints with a linear model at each step, then applies a sketching solver to inexactly solve the resulting subproblem. Building on this design, we propose a new online inference procedure called random scaling. In particular, we construct a test statistic based on SSQP iterates whose limiting distribution is free of any unknown parameters. Compared to existing online inference procedures, our approach offers two key advantages: (i) it enables the construction of asymptotically valid confidence intervals; and (ii) it is matrix-free, i.e. the computation involves only primal-dual SSQP iterates $(\boldsymbol{x}_t, \boldsymbolλ_t)$ without requiring any matrix inversions. We validate our theory through numerical experiments on nonlinearly constrained regression problems and demonstrate the superior performance of our random scaling method over existing inference procedures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。