Stochastic Optimization with Superquantile Constraints: A Fast Computational Approach
Ying Cui, University of California, Berkeley
We present an efficient and scalable second-order computational framework for solving large-scale optimization problems with superquantile constraints. Unlike empirical risk models, superquantile models have non-separable constraints that make typical first-order algorithms difficult to scale. We address the challenge by adopting a hybrid of the second-order semismooth Newton method and the augmented Lagrangian method, which takes advantage of the structured sparsity brought by the risk sensitive measures. The key to make the proposed computational framework scalable in terms of the number of training data is that the matrix-vector multiplication in solving the resulting Newton system can be computed in a reduced space due to the aforementioned sparsity. The computational cost per iteration for the Newton method is similar or even smaller than that of the first-order method. Our developed solver is expected to help improve the reliability and accuracy of statistical estimation and prediction, as well as control the risk of adverse events for safety-critical applications.