# A Computational Framework for Multivariate Convex Regression and its Variants

arXiv: https://arxiv.org/abs/1509.08165 · HTML: https://mlsanity.com/paper/1509.08165/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2015.

## Built on by (most cited first, 16 of 16)

- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Data-Driven Sample Average Approximation with Covariate Information](https://mlsanity.com/paper/2207.13554/) (2022)
- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Handling Hard Affine SDP Shape Constraints in RKHSs](https://mlsanity.com/paper/2101.01519/) (2021)
- [Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning](https://mlsanity.com/paper/2303.04833/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Solving Prior Distribution Mismatch in Diffusion Models via Optimal Transport](https://mlsanity.com/paper/2410.13431/) (2024)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [Convex Smoothed Autoencoder-Optimal Transport model](https://mlsanity.com/paper/2101.05679/) (2021)
- [OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression](https://mlsanity.com/paper/2105.13271/) (2021)
- [Exploiting Concavity Information in Gaussian Process Contextual Bandit Optimization](https://mlsanity.com/paper/2503.10836/) (2025)
- [Convex Regression with a Penalty](https://mlsanity.com/paper/2509.19788/) (2025)
- [An Efficient Minimax Optimal Estimator For Multivariate Convex Regression](https://mlsanity.com/paper/2205.03368/) (2022)
- [Estimating a Function and Its Derivatives Under a Smoothness Condition](https://mlsanity.com/paper/2405.10126/) (2024)
- [Identifiable Convex-Concave Regression via Sub-gradient Regularised Least Squares](https://mlsanity.com/paper/2506.18078/) (2025)
- [Structure-Preserving Reconstruction of Convex Lipschitz Functionals on Hilbert Spaces from Finite Samples](https://mlsanity.com/paper/2605.08559/) (2026)

## Abstract (arXiv)

We study the nonparametric least squares estimator (LSE) of a multivariate convex regression function. The LSE, given as the solution to a quadratic program with O(n2) linear constraints (n being the sample size), is difficult to compute for large problems. Exploiting problem specific structure, we propose a scalable algorithmic framework based on the augmented Lagrangian method to compute the LSE. We develop a novel approach to obtain smooth convex approximations to the fitted (piecewise affine) convex LSE and provide formal bounds on the quality of approximation. When the number of samples is not too large compared to the dimension of the predictor, we propose a regularization scheme --- Lipschitz convex regression --- where we constrain the norm of the subgradients, and study the rates of convergence of the obtained LSE. Our algorithmic framework is simple and flexible and can be easily adapted to handle variants: estimation of a non-decreasing/non-increasing convex/concave (with or without a Lipschitz bound) function. We perform numerical studies illustrating the scalability of the proposed algorithm.