# Convex Regression with a Penalty

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 44 references that are in the map.
- First posted on arXiv 24 Sep 2025.

## Builds on (most cited first, 5 of 5)

- [A Computational Framework for Multivariate Convex Regression and its Variants](https://mlsanity.com/paper/1509.08165/) (2015)
- [Subgradient Regularized Multivariate Convex Regression at Scale](https://mlsanity.com/paper/2005.11588/) (2020)
- [An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems](https://mlsanity.com/paper/2012.04862/) (2020)
- [On Univariate Convex Regression](https://mlsanity.com/paper/1608.04167/) (2016)
- [Overfitting Reduction in Convex Regression](https://mlsanity.com/paper/2404.09528/) (2024)

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

- [Near-optimal Delta-convex Estimation of Lipschitz Functions](https://mlsanity.com/paper/2511.15615/) (2025)

## Abstract (arXiv)

A common way to estimate an unknown convex regression function f0: Omega subset ℝd rightarrow ℝ from a set of n noisy observations is to fit a convex function that minimizes the sum of squared errors. However, this estimator is known for its tendency to overfit near the boundary of Omega, posing significant challenges in real-world applications. In this paper, we introduce a new estimator of f0 that avoids this overfitting by minimizing a penalty on the subgradient while enforcing an upper bound sn on the sum of squared errors. The key advantage of this method is that sn can be directly estimated from the data. We establish the uniform almost sure consistency of the proposed estimator and its subgradient over Omega as n rightarrow ∞ and derive convergence rates. The effectiveness of our estimator is illustrated through its application to estimating waiting times in a single-server queue.