Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

Abstract

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the $K$ nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension $d\ge2$. In particular, for $d>4$, the population risk of our modified problem can be shown to have equivalent convergence rates as the original least square convex regression estimator of $\widetilde O(n^{-2/d})$ using neighborhoods sizes (i.e. $K=K_n$) of order $\widetilde O(n^{2(d-1)/(2d-1)})$ for general convex functions and $\widetilde O(n^{(d+1)/(d+2)})$ for strongly convex functions. To corroborate our theory, we implement iterative optimization methods to compare the prediction accuracy of the KNN relaxation with those of the full estimator across synthetic convex benchmarks. Our experiments demonstrate that KNN prediction risk approaches the full-estimator prediction risk at neighborhood sizes matching the theoretical scale.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning (Statistics)

• arXiv preprint · 1 November 2026

  Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization

  Penghao Wang, Mateo Díaz and Liwei Jiang
• arXiv preprint · 2 November 2026

  Conditional stopping guarantees for a folded parametrization of reduced Stokes vectors

  Hiroyasu Usami, Ayato Tsuboi and Keisuke Hara
• arXiv preprint · 1 November 2026

  Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm

  Sailesh Kamalahasan, Raghav Paladugu and Archana Khurana
• arXiv preprint · 2 November 2026

  Optimal Annuitization, Consumption, and Investment with Costly Capital Injections

  Yijie Huang, Xiaoqing Liang, Jie Xiong and 1 other
• arXiv preprint · 1 November 2026

  Dual Path Following for an Aerial Manipulator Under State and Input Constraints via Transverse Feedback Linearization

  Hamza Tariq and Adeel Akhtar

All new papers in Machine Learning (Statistics)