Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

Anish Senapati, Jose Blanchet

Nov 1, 2026arXiv:2611.01744v1

stat.MLcs.LGmath.OC

Scorecard· 16/16

5.0/10 impact

Rigorous, novel-question theory paper with clean results, but loose bounds, weak computational savings in high d, and no runtime or real-data evidence limit reach.

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.

AI Impact Assessments

(1 model)

Core Contribution

The paper studies a K-nearest-neighbor (KNN) relaxation of multivariate convex least-squares regression. For each point j, only the supporting-hyperplane constraints toward its K nearest neighbors are kept, instead of all n−1. This cuts the O(n²) constraints to O(nK). The central question is how small K can be while the population-risk rate of the full estimator is preserved. It is, as far as the authors know, the first theoretical treatment of constraint localization in shape-restricted regression.

The main results are:

General convex, bounded-Lipschitz truths: K ≍ Õ(n^{2(d−1)/(2d−1)}) for d>4 preserves the rate Õ(n^{−2/d}). Analogous exponents are given for d≤4, where the target rate is n^{−4/(d+4)}.

Strongly convex truths: K ≍ Õ(n^{(d+1)/(d+2)}) suffices. Here the result is stronger. With high probability every active full constraint lies within a shrinking radius, so the KNN and full solutions coincide exactly, and the sparsification discrepancy is O(r_n²) = o(r_n).

Experiments: Synthetic benchmarks (quadratic, half-quadratic, max-affine, and a Kur et al. hard-grid construction) across d=2–15 and n up to 3000. Risk ratios approach 1 at K well below the theoretical scale.

The proof technique for the general case is the more original part. It builds approximately straight chains of retained short edges with controlled direction turning, which gives a residual bound r_ji ≥ −κ‖x_i−x_j‖². It then restores full feasibility by mixing with a small fixed quadratic and applies first-order optimality. The strongly convex case uses a screening argument based on the midpoint gap and a uniform approximation from L² error.

Methodological Rigor

The appendices are detailed. They cover covering-radius and ball-count lemmas, a chaining bound with entropy exponent d/2, the regularization comparison, and the path and quadratic-restoration arguments. The overall structure looks sound. Several caveats apply:

Rates are only sufficient conditions, with an unjustified benefit: Only upper bounds are given, and no lower bounds on the K needed. In low dimension (d<4) the full LSE is already minimax-optimal, so the paper says nothing about whether the KNN estimator is optimal. For d>4 the preserved rate n^{−2/d} is the known suboptimal LSE rate. The paper therefore preserves a suboptimal rate, though that rate is what practitioners actually obtain.

Weak computational payoff in the general case: For d>4, K approaches n^{1−O(1/d)}. For d=5 the exponent is 8/9, and as d grows it approaches n. The saving is therefore marginal in precisely the regime where the rate result holds. The strongly convex exponent (d+1)/(d+2) is also close to 1 for large d. There is no computational complexity analysis or timing comparison.

Regularization and assumptions: Assumption 2.3 ties the regularization to the target rate. Uniform design on a convex body is restrictive. Experiments use unspecified or sensitivity-tested constants, and the constant C_K is not calibrated.

Experimental design: Experiments compare statistical risk only, with no wall-clock or memory measurements, which is the stated motivation. The dimensions and sample sizes (n≤3000) are small. The "theoretical bands" are drawn with an arbitrary constant. Results show KNN reaches parity at K far below theory, which suggests the bounds are loose. Table 2 shows huge ratios at small K (e.g., 1.33e3), and the max-affine case remains above 1 at larger K. The results are also reported as ratios without error bars in the main text.

Details and presentation: Some proof details are sloppy (e.g., typos in the main text such as "Fsc ⊂ Fsc", the Table 1 d<4 exponents versus the corollary). The AI-use statement notes AI assistance in proofs and code.

Potential Impact

The practical value is plausible but unproven. The result justifies a heuristic that practitioners may already use informally: KNN-based constraint pruning in large-scale convex nonparametric least squares, relevant to productivity analysis, operations research, and economics. The paper does not show end-to-end speedups, does not test on real data, and still relies on the Lin–Sun–Toh solver for the full comparison. Methodologically, the path-chaining and quadratic-restoration devices could be reused for other shape-constrained problems (isotonic regression, Lipschitz regression, other constraint-sparsification settings). The strongly-convex exact-recovery result is a clean statement that active constraints are local.

Timeliness

Convex regression scalability is an established but niche concern. The paper builds on recent work (Kur et al. 2024 on LSE suboptimality) and on solver advances. The need for scalable shape-constrained estimation is real, but the community is small, and this paper does not address the minimax-suboptimality issue or provide a new estimator.

Strengths

It poses a clean, new question and gives rigorous guarantees in all fixed dimensions d≥2.

It offers a dual-regime analysis, with exact recovery under strong convexity.

The proofs are self-contained, and the chaining construction is non-trivial.

Experiments span dimensions and truths, including a stress test built from a lower-bound construction.

Limitations

The bounds are loose, as the authors' own experiments show.

The savings are weak for large d.

There are no lower bounds, no timing or real-data results, and the design is restricted to uniform sampling.

It preserves a suboptimal rate rather than improving statistical performance.

The scope is narrow and the contribution is moderately incremental.

Overall, this is a solid, narrowly scoped theory-plus-simulation paper with limited expected reach.

Rating:5/ 10

Significance 4.5Rigor 6.5Novelty 6Clarity 6

Generated Nov 3, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

5.0/10 impact

Rigorous, novel-question theory paper with clean results, but loose bounds, weak computational savings in high d, and no runtime or real-data evidence limit reach.