### Abstract

We design a trust-region sequential quadratic programming (TR-SQP) method to find both **first- and second-order** stationary points for optimization problems with a stochastic objective and deterministic equality constraints. We name our method TR-SQP for STochastic Optimization with Random Models (TR-SQP-STORM). In each iteration, the algorithm constructs random models that require estimates of the objective value, gradient, and Hessian to satisfy adaptive accuracy conditions with a fixed probability. We introduce a novel reliability parameter, based on which we define reliable and unreliable iterations and adjust accuracy conditions accordingly. The reliability parameter equips the random models with extra flexibility to reduce the sample size at each step. To find first-order stationary points, we compute **gradient-steps** by employing the **adaptive relaxation technique** proposed by Fang et al., 2022. To find second-order stationary points, we design **eigen-steps** to explore the negative curvature of the reduced Lagrangian Hessian, with additional **second-order correctional steps** performed when necessary. Under reasonable assumptions, we establish both first- and second-order global convergence guarantees: with probability one, the TR-SQP-STORM iteration sequence converges to the first-order stationary point, with a subsequence converging to the second-order stationary point. We apply our method to a subset of problems in CUTEst set and on constrained Logistic regression problems to demonstrate its promising empirical performance.

Publication

*A short note is accepted by 2022 NeurIPS Higher-Order Optimization in Machine Learning (HOO) workshop*

###### MS in Computational and Applied Math (2021-2023)

Yuchen Fang is a master student in the Computational and Applied Math program at UChicago, working with Mladen Kolar and Sen Na on stochastic nonlinear optimization. He is also interested in numerical linear algebra, high-dimensional statistics, statistical learning, as well as mathematical finance.

###### Postdoc in Statistics and ICSI

Sen Na is a postdoctoral scholar in the Statistics department and ICSI at UC Berkeley. His research interests broadly lie in the mathematical foundations of data science, with topics including high-dimensional statistics, graphical models, semiparametric models, optimal control, and large-scale and stochastic nonlinear optimization. He is also interested in applying machine learning methods in biology, neuroscience, and engineering.

###### Professor in Statistics and ICSI, Amazon Scholar

Michael Mahoney is a Professor in the Statistics department and ICSI at UC Berkeley. He is also the director of the NSF/TRIPODS-funded Foundations of Data Analysis (FODA) Institute at UC Berkeley. He works on the algorithmic and statistical aspects of modern large-scale data analysis. Much of his recent research has focused on large-scale machine learning, including randomized matrix algorithms and randomized numerical linear algebra.

###### Associate Professor of Econometrics and Statistics

Mladen Kolar is an Associate Professor of Econometrics and Statistics at the University of Chicago Booth School of Business. His research is focused on high-dimensional statistical methods, graphical models, varying-coefficient models and data mining, driven by the need to uncover interesting and scientifically meaningful structures from observational data.