Subgradient Regularized Multivariate Convex Regression at Scale

arXiv2005.11588MaRDI QIDQ6341288

Author name not available (Why is that?)

Publication date: 23 May 2020

Abstract: We present new large-scale algorithms for fitting a subgradient regularized multivariate convex regression function to $n$ samples in $d$ dimensions -- a key problem in shape constrained nonparametric regression with widespread applications in statistics, engineering and the applied sciences. The infinite-dimensional learning task can be expressed via a convex quadratic program (QP) with $O(nd)$ decision variables and $O(n^2)$ constraints. While instances with $n$ in the lower thousands can be addressed with current algorithms within reasonable runtimes, solving larger problems (e.g., $napprox10^4$ or $10^5$) is computationally challenging. To this end, we present an active set type algorithm on the dual QP. For computational scalability, we perform approximate optimization of the reduced sub-problems; and propose randomized augmentation rules for expanding the active set. Although the dual is not strongly convex, we present a novel linear convergence rate of our algorithm on the dual. We demonstrate that our framework can approximately solve instances of the convex regression problem with $n=10^5$ and $d=10$ within minutes; and offers significant computational gains compared to earlier approaches.

Has companion code repository: https://github.com/wenyuC94/ConvexRegression

This page was built for publication: Subgradient Regularized Multivariate Convex Regression at Scale

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341288)