Shape-Constrained Regression Using Sum of Squares Polynomials.

The article focuses on shape-constrained regression using sum-of-squares estimators (SOSEs), a hierarchy of semidefinite programs (SDPs) designed to fit multivariate polynomials to data while guaranteeing shape constraints such as convexity or monotonicity over a box. It establishes that SOSEs are consistent estimators of the underlying shape-constrained function and proves that sum-of-squares-convex and sum-of-squares-monotone polynomials are dense in the sets of convex and monotone polynomials, respectively. The paper also classifies the computational complexity of convex and monotone polynomial regression, showing NP-hardness for degree three or higher, while demonstrating that SOSEs often achieve near-optimal training error efficiently for fixed hierarchy levels. Applications include improved production function estimation in economics, real-time prediction of optimal values in conic programming for inventory management contract negotiation, and optimal transport maps for color transfer, highlighting SOSEs’ computational advantages in settings with many data points but low feature dimension.