提出在线求解约束优化的新方法,实现高效且精准的统计推断。
Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming
- 基于随机二次规划,通过梯度滑动平均消除方向偏差。
- 全局几乎必然收敛,局部渐近正态性达到最优协方差下界。
- 无需投影算子,适合非线性约束的实际问题,如金融配置与公平学习。
我们研究带有等式和不等式约束的随机优化问题的在线统计推断。这类问题广泛存在于统计学与机器学习中,涵盖约束 $M$-估计、物理信息模型、安全强化学习与算法公平性。本文提出一种随机序列二次规划(SSQP)方法,其中步长方向通过依次对目标函数进行二次逼近、对约束进行线性逼近得到。尽管可获得总体梯度的无偏估计,但约束随机问题的关键挑战在于步向量方向存在偏差。为此,我们在 SSQP 中引入类似动量的梯度滑动平均技术以去偏。我们证明该方法实现全局几乎必然收敛,并在哈杰克-莱卡姆意义下具有最优的原始-对偶极限协方差矩阵。此外,我们提供了可直接使用的协方差矩阵估计器。据我们所知,该方法是首个无需依赖投影算子(通常对非线性问题不可行)即可实现原始-对偶渐近最小极大最优性的完全在线方法。通过在基准非线性问题、受限广义线性模型及使用合成与真实数据的组合投资问题上的大量实验,验证了方法在效率与实际推断方面的优越性能。
原文摘要 · Abstract (English)
We study online statistical inference for the solutions of stochastic optimization problems with equality and inequality constraints. Such problems are prevalent in statistics and machine learning, encompassing constrained $M$-estimation, physics-informed models, safe reinforcement learning, and algorithmic fairness. We develop a stochastic sequential quadratic programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing a quadratic approximation of the objective and a linear approximation of the constraints. Despite having access to unbiased estimates of population gradients, a key challenge in constrained stochastic problems lies in dealing with the bias in the step direction. As such, we apply a momentum-style gradient moving-average technique within SSQP to debias the step. We show that our method achieves global almost-sure convergence and exhibits local asymptotic normality with an optimal primal-dual limiting covariance matrix in the sense of Hájek and Le Cam. In addition, we provide a plug-in covariance matrix estimator for practical inference. To our knowledge, the proposed SSQP method is the first fully online method that attains primal-dual asymptotic minimax optimality without relying on projection operators onto the constraint set, which are generally intractable for nonlinear problems. Through extensive experiments on benchmark nonlinear problems, as well as on constrained generalized linear models and portfolio allocation problems using both synthetic and real data, we demonstrate superior performance of our method, showing that the method and its asymptotic behavior not only solve constrained stochastic problems efficiently but also provide valid and practical online inference in real-world applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。