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(n2) 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≥2. 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 Õ(n−2/d) using neighborhoods sizes (i.e. K=Kn) of order Õ(n2(d−1)/(2d−1)) for general convex functions and Õ(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.
Related
- Curvature measures and volume preserving flows in h-convex geometry
- Embedding Linear Codes into Optimal Self-Orthogonal Codes Based on Constraint-Preserving Genetic Algorithms
- Constraint Preserving AFD-WENO Schemes for Relativistic Hydrodynamics with General Equations of State
- Convex-SKM-Net: Low-Latency Block Halfspace Corrections for Neural Convex Constraint Satisfaction
- Admissibility-Preserving Constraint Lifting for Conditional Deadbeat Control of Discrete-Time Nonlinear Systems
BibTeX
@misc{senapati2026convex,
title = {{Convex Regression at Scale: Geometry-Preserving Constraint Sparsification}},
author = {Anish Senapati and Jose Blanchet},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01744},
eprint = {2611.01744},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01744},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Convex Regression at Scale: Geometry-Preserving Constraint Sparsification
AU - Anish Senapati
AU - Jose Blanchet
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01744
UR - https://arxiv.org/abs/2611.01744
AB - 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≥2. 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 Õ(n^−2/d) using neighborhoods sizes (i.e. K=K_n) of order Õ(n^2(d−1)/(2d−1)) for general convex functions and Õ(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.
ER -