Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling
Xinchen Du, Wanrong Zhu, Wei Biao Wu, Sen Na · 2025
Read Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling by Xinchen Du, Wanrong Zhu, Wei Biao Wu, Sen Na (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18327.txt.
Introduction
Xinchen Du and co-authors develop, in a 2025 paper, a way to draw sound statistical conclusions while a constrained learning problem is still being solved step by step. Modern data sets are too large to store and re-scan, so online methods must judge uncertainty on the fly. Their base solver sketches the problem at each step, fitting a simple curved model to the goal and flat models to the constraints. On top of it they build a trick called random scaling.
The trick turns the solver's own iterates into a test statistic whose long-run behavior needs no unknown quantities. That yields confidence intervals that hold up as data grows, without ever inverting a matrix. Tests on nonlinear regression problems with constraints beat older online methods. The authors present the method as practical inference for streaming optimization.
Catalog record
| CREATOR | Xinchen Du, Wanrong Zhu, Wei Biao Wu, Sen Na |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 144 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18327
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling Xinchen Du, Wanrong Zhu, Wei Biao Wu, Sen Na Abstract 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 Adaptive Inexact Stochastic Sequential Quadratic Programming (AI-SSQP). As a generalization of (sketched) Newton methods to constrained problems, AI-SSQP approximates the objective with a quadratic model and the constraints with a linear model at each step, then applies a randomized sketching solver to inexactly solve the resulting subproblem, along with an adaptive random stepsize to update the primal-dual iterates. Building on this design, we first establish the asymptotic normality guarantee of averaged AI-SSQP and observe that the averaged iterates exhibit better statistical efficiency than the last iterates, in terms of a smaller limiting covariance matrix. Furthermore, instead of estimating the limiting covariance matrix directly, we study a new online inference procedure called random scaling . Specifically, we construct a test statistic by appropriately rescaling the averaged iterates, such that the limiting distribution of the test statistic 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 and statistically efficient confidence intervals, while existing procedures based on the last iterates are less efficient and rely on a plug-in covariance estimator that is inconsistent ; and (ii) it is matrix-free , i.e., the computation involves only primal-dual iterates themselves without any matrix inversions, making its computational cost match that of advanced first-order methods for unconstrained problems. We validate our theoretical findings through numerical experiments on nonlinearly constrained regression problems and demonstrate the superior performance of random scaling over existing inference procedures. 1 Introduction We consider the following constrained stochastic optimization problem: \min_{{\bm{x}}\in\mathbb{R}^{d}}\;\;f({\bm{x}})=\mathbb{E}_{\xi\sim{\mathcal{P}}}[F({\bm{x}};\xi)],\quad\text{s.t.}\;\;c({\bm{x}})={\bm{0}}, (1) where f:\mathbb{R}^{d}\rightarrow\mathbb{R} is the objective function, F({\bm{x}},\xi) is a noisy measurement of f({\bm{x}}) with randomness \xi following distribution {\mathcal{P}} , and c:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m} denotes the equality constraints. Problem ( 1 ) arises in various applications across science, economics, and engineering, such as portfolio allocation ( Fan et al., 2012 ; Du et al., 2022 ) , computer vision ( Roy et al., 2018 ) , PDE-constrained optimization ( Rees et al., 2010 ; Kouri et al., 2014 ) , constrained deep neural networks ( Chen et al., 2018 ) , physics-inspired neural networks ( Cuomo et al., 2022 ) , natural language processing ( Nandwani et al., 2019 ) , and constrained maximum likelihood estimation ( Geyer, 1991 ; Chatterjee et al., 2016 ) . In practice, Problem ( 1 ) can be interpreted as a constrained model parameter estimation problem, where \xi denotes the data sample, f({\bm{x}}) denotes the expected loss, and the (primal) solution {\bm{x}}^{\star}=\mathop{\mathrm{argmin}}_{c({\bm{x}})=\bm{0}}f({\bm{x}}) denotes the true model parameter. Let \mathcal{L}({\bm{x}},{\bm{\lambda}})=f({\bm{x}})+{\bm{\lambda}}^{\top}c({\bm{x}}) be the Lagrangian function, where {\bm{\lambda}}\in\mathbb{R}^{m} is the dual vector associated with equality constraints; and let {\bm{\lambda}}^{\star} denote the dual solution. In this paper, our goal is to conduct online statistical inference for the primal-dual solution ({\bm{x}}^{\star},{\bm{\lambda}}^{\star}) . Using the classic offline method via sample average approximation (SAA), one can find the solution to the following problem: \min_{{\bm{x}}\in\mathbb{R}^{d}}\;\;\widehat{f}_{t}({\bm{x}})=\frac{1}{t}\sum_{i=1}^{t}F({\bm{x}};\xi_{i}),\quad\text{s.t.}\;\;c({\bm{x}})={\bm{0}}, (2) where \xi_{1},\xi_{2},\cdots,\xi_{t} are observed i.i.d data from \mathcal{P} . It is well known that the minimizer (\widehat{{\bm{x}}}_{t},\widehat{{\bm{\lambda}}}_{t}) of ( 2 ), also called constrained M -estimator , exhibits \sqrt{t} -consistency and asymptotic normality, allowing us to perform statistical inference. In particular, under proper regularity conditions, we have that as t\rightarrow\infty ( Shapiro et al., 2014 , Chapter 5) , \sqrt{t}\cdot(\widehat{{\bm{x}}}_{t}-{\bm{x}}^{\star},\widehat{{\bm{\lambda}}}_{t}-{\bm{\lambda}}^{\star})\stackrel{{\scriptstyle d}}{{\longrightarrow}}\mathcal{N}\left({\bm{0}},\;\Xi^{\star}\right), (3) where the limiting covariance is given by \Xi^{\star}=(\nabla^{2}\mathcal{L}({\bm{x}}^{\star},{\bm{\lambda}}^{\star}))^{-1}\text{cov}(\nabla\mathcal{L}({\bm{x}}^{\star},{\bm{\lambda}}^{\star};\xi))(\nabla^{2}\mathcal{L}({\bm{x}}^{\star},{\bm{\lambda}}^{\star}))^{-1} (see Section 3.2 for details). However, offline methods often have to deal with large batches of samples, leading to significant computational and memory cost. In recent years, a growing body of literature has focused on developing and analyzing online methods for solving the above constrained stochastic optimization problems and performing the underlying inference tasks. One simple online method is projection-based Stochastic Gradient Descent (SGD). Davis et al. (2019) proved almost-sure convergence for projection-based SGD, while Duchi and Ruan (2021) and Davis et al. (2024) established asymptotic normality guarantees for its iterates. However, the projection operator, which plays a key role in these methods, can be computationally expensive in practice, especially for nonlinear equality constraints in ( 1 ). To circumvent this difficulty, researchers have developed alternative constrained optimization methods, including penalty methods, barrier methods, augmented Lagrangian methods, and sequential quadratic programming methods ( Bertsekas, 1997 ; Bertsekas, 2014 ; Nocedal and Wright, 2006 ) . More recently, various stochastic sequential quadratic programming (SSQP) methods, which generalize stochastic Newton methods for unconstrained problems, have been proposed to efficiently solve constrained problems in an online fashion; see Berahas et al. (2021) ; Berahas et al. (2024) ; Na et al. (2022) ; Na et al. (2023) ; Fang et al. (2024) ; Curtis et al. (2024) and references therein. For the purpose of statistical inference, Na and Mahoney (2025) considered an Adaptive Inexact SSQP (AI-SSQP) scheme, where at each step the method employs an iterative sketching solver to inexactly solve the SQP quadratic subproblem and selects a suitable random stepsize (inspired by stochastic line search) to update the primal-dual iterate ({\bm{x}}_{t},{\bm{\lambda}}_{t}) . The authors demonstrated that AI-SSQP iterates exhibit the following asymptotic normality property (see Section 3.2 for details) ( Na and Mahoney, 2025 , Theorem 5.6) : \sqrt{1/\bar{\alpha}_{t}}\cdot(\bm{x}_{t}-\bm{x}^{\star},\bm{\lambda}_{t}-\bm{\lambda}^{\star})\stackrel{{\scriptstyle d}}{{\longrightarrow}}\mathcal{N}(0,\widetilde{\Xi}^{\star}), (4) where {\bar{\alpha}}_{t} is the random stepsize and the limiting covariance \tilde{\Xi}^{\star} (given by ( 23 )) is determined by the underlying sketching distribution. AI-SSQP methods offer advantages over projection-based methods by linearizing nonlinear constraints, thereby eliminating the need for costly projection operators. Additionally, the sketching solver introduces a trade-off between computational and statistical efficiency. In particular, when the sketching solver is suppressed and the quadratic subproblem is solved exactly, the AI-SSQP iterates achieve primal-dual asymptotic minimax efficiency , with the limiting covariance \tilde{\Xi}^{\star} reducing to the optimal covariance \Xi^{\star} achieved by the constrained M -estimator (\widehat{{\bm{x}}}_{t},\widehat{{\bm{\lambda}}}_{t}) in ( 3 ). The primal component of this covariance also matches that obtained by projection-based methods in Duchi and Ruan (2021) ; Davis et al. (2024) . To facilitate online inference via asymptotic normality, a suitable covariance matrix estimator is typically required. Jiang et al. (2025) analyzed a batch-means covariance estimator originally developed for SGD methods ( Chen et al., 2020 ; Zhu et al., 2021 ) , and demonstrated that the same estimator applies to projected SGD methods with the same convergence rate. However , due to the nonlinearity and nonconvexity of the problem, the convergence analysis of the batch-means estimator was conducted only under light-tailed gradient noise, a stronger condition than that required for asymptotic normality of projected SGD. Kuang et al. (2025) designed a batch-free covariance estimator for stochastic Newton methods and established an improved convergence rate under strong convexity. Their analysis also does not apply to nonlinear problem ( 1 ). In fact, Na and Mahoney (2025) introduced a plug-in covariance estimator for \widetilde{\Xi}^{\star} in ( 4 ) within the