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 PhD student in the mathematics department at UC Berkeley. He was a master student in the Computational and Applied Math program at UChicago, where he worked with Mladen Kolar and Sen Na on stochastic nonlinear optimization. His research interests include numerical linear algebra, high-dimensional statistics, statistical learning, and mathematical finance.

Sen Na

Assistant Professor in ISyE

Sen Na is an Assistant Professor in the School of Industrial and Systems Engineering at Georgia Tech. Prior to joining ISyE, he was a postdoctoral researcher 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 to 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.