Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models

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.

Yuchen Fang

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.

Sen Na

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.

Michael W. Mahoney

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.

Mladen Kolar

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.