betaFeedback

WorksMathematics

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)O(n^2) supporting-hyperplane constraints creating a computational bottleneck as the sample size nn increases. We study a KK-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the KK nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension d≥2d\ge2. In particular, for d>4d>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 O~(n−2/d)\widetilde O(n^{-2/d}) using neighborhoods sizes (i.e. K=KnK=K_n) of order O~(n2(d−1)/(2d−1))\widetilde O(n^{2(d-1)/(2d-1)}) for general convex functions and O~(n(d+1)/(d+2))\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.

Introduction

We study the problem of estimating an unknown convex regression function from nn independent, identically distributed (i.i.d) observations. Convex regression arises in a wide range of areas, including economics [2, 36], operations research [3, 20, 16], statistical learning [37, 24], and engineering [15]. In economics, for example, concavity restrictions arise naturally in models of utility, consumer preferences, and production technologies. [1, 35, 9, 7, 17, 3]. In financial engineering, convexity restrictions arise in option-pricing problems [2]. In operations research and dynamic programming, convexity or concavity of value functions and response surfaces often follows from structural assumptions on costs, transitions, or performance measures [34, 25].

Early work on convex and concave regression focused primarily on the one-dimensional setting establishing consistency, rates of convergence, and limit-distribution results [19, 18, 29, 10]. More recent work has extended both the finite-dimensional characterization and the statistical theory of least-squares convex regression to multivariate data [33, 27, 26, 14]. In parallel, substantial effort has been devoted to scalable optimization methods for solving the associated quadratic program whose solution serves as the natural convex regression estimator. This quadratic program minimizes the empirical squared error over the space of max-affine functions nn subgradients, with each subgradient constraint encoded by n−1n-1 inequalities, thus resulting in O(n2)O(n^2) constraints. In this paper, we consider a less studied alternative approach where, instead of aiming to solve the full constrained problem, we analyze a reduced formulation in which o(n2)o(n^2) constraints are retained. The central question we address is:

Under what conditions can the convex regression constraints be reduced, and by how much, while preserving the same statistical convergence rate for population risk? Our main results shows that, under reasonable assumptions, we can retain only O~(n2(d−1)/(2d−1))\widetilde{O}(n^{2(d-1)/(2d-1)}) constraints per subgradient for general convex functions and O~(n(d+1)/(d+2))\widetilde{O}(n^{(d+1)/(d+2)}) constraints per subgradient for strongly convex functions while achieving the same statistical convergence rate as the full convex regression estimator for d>4d > 4. Because our reduced problem relies of only keeping localized constraints from the full problem, one can substantially decrease the computational burden without sacrificing asymptotic statistical efficiency.

Related work

Convex regression belongs to the broader class of shape-restricted regression methods, which impose qualitative constraints on the regression function. Standard examples include isotonic regression, where the fitted function is constrained to be monotone with respect to a given order, and convex or concave regression, where the fitted function is constrained by a global curvature condition ([5, 31, 13]). Isotonic regression yields estimators that are typically piecewise constant, while convex regression yields a piecewise affine estimator whose fitted values can be represented through supporting hyperplanes. Foundational work on convex and concave least-squares regression goes back to Hildreth [19] and Hanson and Pledger [18], with later work developing consistency, limit theory, and finite-dimensional characterizations in both one-dimensional and multivariate settings ([29, 10, 33, 27]).

One line of work in shape-restricted regression studies the statistical complexity of the associated least-squares estimators. For isotonic and related shape-restricted problems, risk bounds and adaptation properties have been studied by Chatterjee et al. [8]; Guntuboyina and Sen [13]. For convex regression, analogous questions require controlling the size of the class of convex functions. Metric entropy bounds provide one way to quantify this complexity, and such bounds play a central role in the empirical-process arguments used to derive statistical rates ([11]). In the one-dimensional setting, Guntuboyina and Sen [12] prove global risk bounds and adaptation results for the convex least-squares estimator, showing that the estimator can adapt to functions that are well approximated by piecewise affine convex functions. In multiple dimensions, Lim [26] and Han and Wellner [14] study convergence rates, minimax benchmarks, and risk bounds for multivariate convex regression. Han and Wellner [14] study global minimax rates and risk bounds for bounded multivariate convex least-squares estimators, showing that the attainable rates depend strongly on the geometry of the support. Their analysis indicates that the bounded least square estimation problem is nearly rate-optimal only in low dimensions, motivating the use of sieved adaptive estimators in higher dimensions. Kur, Gao, Guntuboyina, and Sen [21] later make the high-dimensional suboptimality of the convex LSE precise, proving that for d≥5d \ge5 the least square error (LSE) has risk of order Θ~(n−2/d)\widetilde{\Theta}(n^{-2/d}) over several standard convex function classes, while the minimax rate is n−4/(d+4)n^{-4/(d+4)}. Such a suboptimality was only true when d>5d > 5 with convex regression leading to optimal estimators for d≤5d \le5. This gap motivated the study of alternative convex estimators and more structured formulations. In this direction, Balázs, György, and Szepesvári [4] consider least-squares estimators over max-affine function classes, where the estimator is constrained to be the maximum of a finite number of affine functions. Under boundedness and Lipschitz assumptions, they obtain near-optimal minimax rates up to logarithmic factors, but provide no polynomial-time guarantee for the required optimization over affine partitions. In contrast, Kur and Putterman [22] attain near-minimax rates in polynomial time by combining local affine fits on candidate simplices and their estimated errors into a globally convex estimator.

The usual multivariate convex least-squares estimator admits a finite-dimensional formulation with one fitted value and one subgradient vector per observation, together with pairwise supporting-hyperplane constraints. This formulation is a convex quadratic program, but it contains O(n2)O(n^2) linear inequality constraints, which makes solving the problem difficult for large samples sizes ([33, 27, 30]). A parallel line of work in convex regression focuses on ease of computation. Lee et al. [23] developed more efficient algorithms for convex nonparametric least squares in production analysis. Mazumder, Choudhury, Iyengar, and Sen [30] propose a scalable augmented-Lagrangian and ascent descent method of multipliers (ADMM)-based frameworks for computing the multivariate convex LSE and its variants. Lin, Sun, and Toh [28] develop a proximal augmented-Lagrangian method combined with semismooth Newton subproblem solvers and a practical constraint-generation strategy. Bertsimas and Mundru [6] study sparse convex regression and develop cutting-plane methods for large-scale instances. These methods improve the computational tractability of convex regression, but they are primarily designed to solve, approximate, or regularize the full convex regression problem. Tangentially, Hannah and Dunson [16] constructed globally convex estimators by fitting local linear models on adaptively selected partitions and then combining them into a max-affine convex function, closely aligning with the statistical work of Balazs [4].

The use of constraint localization within regression problems is a less studied phenomenon within academic literature. To the best of our knowledge, no such methods have been theoretically studied in the literature for either convex or isotonic regression. In more classical regression settings, K-nearest-neighbor regression has been used to predict new data by constructing a weighted average of the learned training outcomes of the nearest neighbors.

Setup and Framework

Notation

We use ∥⋅∥2\lVert\cdot\rVert_{2} for the Euclidean norm of a vector and ∥⋅∥F\lVert\cdot\rVert_{F} for the Frobenius norm of a matrix. For a function f:Ω→Rf:\Omega\to\mathbb{R}, we write ∥f∥∞=sup⁡x∈Ω∣f(x)∣\lVert f\rVert_{\infty}=\sup_{x\in\Omega}|f(x)| and ∥f∥n2=n−1∑i=1nf(Xi)2\lVert f\rVert_{n}^{2}=n^{-1}\sum_{i=1}^{n}f(X_i)^2. We denote its Lipschitz constant with respect to Euclidean distance by Lip⁡(f)\operatorname{Lip}(f). For a scalar aa, we use [a]+=max⁡{a,0}[a]_{+}=\max\{a,0\} and [a]−=max⁡{−a,0}[a]_{-}=\max\{-a,0\} for its positive and negative parts, respectively. For positive sequences an,bna_n,b_n, the notation an=o(bn)a_n=o(b_n) means that an/bn→0a_n/b_n\to0 and an=O(bn)a_n=O(b_n) implies that an/bn→Ca_n/b_n\to C for some constant C≥0C\ge0. The notation O~(⋅)\widetilde{O}(\cdot) suppresses logarithmic factors in nn.

Setting

We consider a setting where our samples are drawn uniformly on a convex compact body Ω⊂Rd\Omega\subset\mathbb{R}^{d} for d≥2d\ge2 with a nonempty interior. We denote P\mathbb{P} for the uniform probability measure on Ω\Omega and denote the diameter of the convex body be denoted as DΩD_{\Omega}. For values B,L>0B,L>0, we denote by FB,L(Ω)\mathcal{F}_{B,L}(\Omega) the class of convex functions on Ω\Omega with ∥f∥∞≤B\lVert f\rVert_{\infty}\le B and Lip⁡(f)≤L\operatorname{Lip}(f)\le L. We assume the following assumptions on our setting:

Assumption 2.1. For n>1n>1, our observations satisfy

Yi=f0(Xi)+ξifor Xi∼iidP and f0∈FB,L(Ω).(1)Y_i=f_0(X_i)+\xi_i\quad\text{for }X_i\mathrel{\overset{\mathrm{iid}}{\sim}}\mathbb{P}\text{ and }f_0\in\mathcal{F}_{B,L}(\Omega). \tag*{(1)}

where the errors ξ1,…,ξn\xi_1,\ldots,\xi_n are mutually independent and are also independent of the X=(X1,…,Xn)X=(X_1,\ldots,X_n).

Assumption 2.2. Each error ξi\xi_i has mean 00 and is subgaussian with variance proxy σ2\sigma^2:

E[etξi]≤eσ2t2/2for t∈R, i≤n,(2)\mathbb{E}[e^{t\xi_i}]\le e^{\sigma^2t^2/2}\quad\text{for }t\in\mathbb{R},\ i\le n, \tag*{(2)}

For a matrix of subgradients G=(g1,…,gn)∈Rn×dG=(g_1,\ldots,g_n)\in\mathbb{R}^{n\times d} and values θ=(θ1,θ2,…,θn)∈Rn\theta=(\theta_1,\theta_2,\ldots,\theta_n)\in\mathbb{R}^{n}, we denote a supporting hyperplane residual between XiX_i and XjX_j as

rji(θ,G)=θi−θj−gjT(Xi−Xj)r_{ji}(\theta,G)=\theta_i-\theta_j-g_j^{\mathsf{T}}(X_i-X_j)

which measures how much each value θi\theta_i is above the hyperplane generated from point XjX_j. We collect the function bounds in

C={(θ,G):∣θi∣≤B, ∥gi∥2≤L ∀i}.\mathcal{C}=\{(\theta,G):|\theta_i|\le B,\ \lVert g_i\rVert_2\le L\ \forall i\}.

Given an edge set WW, we define CW\mathcal{C}_{W} as the subset of C\mathcal{C} satisfying rji(θ,G)≥0r_{ji}(\theta,G)\ge0 for every (j,i)∈W(j,i)\in W. For different edge sets WW, this leads to different feasible sets for our least square formulation. Let the full edge set be EF={(j,i):j≠i}E_F=\{(j,i):j\ne i\}. For a value 1≤K≤n−11\le K\le n-1, we write NK(j)\mathcal{N}_{K}(j) for the Euclidean KK nearest observations to XjX_j and subsequently denote the KNN edge set as EK={(j,i):i∈NK(j)}E_K=\{(j,i):i\in\mathcal{N}_{K}(j)\}.

To mitigate the commonly known problem of blowup of gradients near the boundary of Ω\Omega present in convex regression, we introduce a regularized version of our least square objective

Φn(θ,G)=12∥θ−Y∥22+μn2∥G∥F2.\Phi_n(\theta,G)=\frac{1}{2}\lVert\theta-Y\rVert_2^2+\frac{\mu_n}{2}\lVert G\rVert_F^2.

The full convex regression and KNN convex regression problem are subsequently defined as

(θF,GF)=arg⁡min⁡CEFΦn,(θK,GK)=arg⁡min⁡CEKΦn,(3)(\theta_F,G_F)=\mathop{\arg\min}_{\mathcal{C}_{E_F}}\Phi_n,\qquad(\theta_K,G_K)=\mathop{\arg\min}_{\mathcal{C}_{E_K}}\Phi_n, \tag*{(3)}

respectively. For out-of-sample prediction, we use the standard max-affine predictors defined by:

References

  1. [1]Afriat, S. N. (1967). The construction of utility functions from expenditure data. *International Economic Review*, 8(1):67–77.
  2. [2]Aït-Sahalia, Y. and Duarte, J. (2003). Nonparametric option pricing under shape restrictions. *Journal of Econometrics*, 116(1–2):9–47.
  3. [3]Allon, G., Beenstock, M., Hackman, S. T., Passy, U., and Shapiro, A. (2007). Nonparametric estimation of concave production technologies by entropic methods. *Journal of Applied Econometrics*, 22(4):795–816.DOI
  4. [4]Balázs, G., György, A., and Szepesvári, C. (2015). Near-optimal max-afe estimators for convex regression. In *Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics*, volume 38 of *Proceedings of Machine Learning Research*, pages 56–64. PMLR.
  5. [5]Barlow, R. E., Bartholomew, D. J., Bremner, J. M., and Brunk, H. D. (1972). *Statistical Inference under Order Restrictions: The Theory and Application of Isotonic Regression*. John Wiley & Sons, London.
  6. [6]Bertsimas, D. and Mundru, N. (2021). Sparse convex regression. *INFORMS Journal on Computing*, 33(1):262–279.DOI
  7. [7]Blundell, R. W., Browning, M., and Crawford, I. A. (2003). Nonparametric Engel curves and revealed preference. *Econometrica*, 71(1):205–240.
  8. [8]Chatterjee, S., Guntuboyina, A., and Sen, B. (2015). On risk bounds in isotonic and other shape restricted regression problems. *The Annals of Statistics*, 43(4):1774–1800.DOI
  9. [9]Famulari, M. (1995). A household-based, nonparametric test of demand theory. *The Review of Economics and Statistics*, 77(2):372–382.DOI
  10. [10]Groeneboom, P., Jongbloed, G., and Wellner, J. A. (2001). Estimation of a convex function: Characterizations and asymptotic theory. *The Annals of Statistics*, 29(6):1653–1698.
  11. [11]Guntuboyina, A. and Sen, B. (2013). Covering numbers for convex functions. *IEEE Transactions on Information Theory*, 59(4):1957–1965. https://arxiv.org/abs/1204.0147.
  12. [12]Guntuboyina, A. and Sen, B. (2015). Global risk bounds and adaptation in univariate convex regression. *Probability Theory and Related Fields*, 163(1–2):379–411.arxiv.org/abs/1305.1648
  13. [13]Guntuboyina, A. and Sen, B. (2018). Nonparametric shape-restricted regression. *Statistical Science*, 33(4):568–594.arxiv.org/abs/1709.05707
  14. [14]Han, Q. and Wellner, J. A. (2016). Multivariate convex regression: Global risk bounds and adaptation. arXiv preprint arXiv:1601.06844.arxiv.org/abs/1601.06844
  15. [15]Hannah, L. A. and Dunson, D. B. (2012). Ensemble methods for convex regression with applications to geometric programming based circuit design. In *Proceedings of the 29th International Conference on Machine Learning*, pages 369–376, Edinburgh, Scotland.arxiv.org/abs/1206.4645
  16. [16]Hannah, L. A. and Dunson, D. B. (2013). Multivariate convex regression with adaptive partitioning. *Journal of Machine Learning Research*, 14(102):3261–3294.
  17. [17]Hanoch, G. and Rothschild, M. (1972). Testing the assumptions of production theory: A nonparametric approach. *Journal of Political Economy*, 80(2):256–275.DOI
  18. [18]Hanson, D. L. and Pledger, G. (1976). Consistency in concave regression. *The Annals of Statistics*, 4(6):1038–1050.
  19. [19]Hildreth, C. (1954). Point estimates of ordinates of concave functions. *Journal of the American Statistical Association*, 49(267):598–619.DOI
  20. [20]Keshavarz, A., Wang, Y., and Boyd, S. (2011). Imputing a convex objective function. In *2011 IEEE International Symposium on Intelligent Control*, pages 613–619.DOI
  21. [21]Kur, G., Gao, F., Guntuboyina, A., and Sen, B. (2024). Convex regression in multidimensions: Suboptimality of least squares estimators. *The Annals of Statistics*, 52(6):2791–2815. https://arxiv.org/abs/2006.02044.
  22. [22]Kur, G. and Putterman, E. (2022). An efficient minimax optimal estimator for multivariate convex regression. In Loh, P.-L. and Raginsky, M., editors,* Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1510–1546. PMLR.
  23. [23]Lee, C.-Y., Johnson, A. L., Moreno-Centeno, E., and Kuosmanen, T. (2013). A more efficient algorithm for convex nonparametric least squares. European Journal of Operational Research, 227(2):391–400.DOI
  24. [24]Liao, Z., Dai, S., and Kuosmanen, T. (2024). Convex support vector regression. European Journal of Operational Research, 313(3):858–870.
  25. [25]Lim, E. (2010). Response surface computation via simulation in the presence of convexity. In Proceedings of the 2010 Winter Simulation Conference, pages 1246–1254.
  26. [26]Lim, E. (2014). On convergence rates of convex regression in multiple dimensions. INFORMS Journal on Computing, 26(3):616–628.
  27. [27]Lim, E. and Glynn, P. W. (2012). Consistency of multidimensional convex regression. Operations Research, 60(1):196–208.DOI
  28. [28]Lin, M., Sun, D., and Toh, K.-C. (2022). An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems. Mathematical Programming Computation, 14(2):223–270.
  29. [29]Mammen, E. (1991). Nonparametric regression under qualitative smoothness assumptions. The Annals of Statistics, 19(2):741–759.
  30. [30]Mazumder, R., Choudhury, A., Iyengar, G., and Sen, B. (2019). A computational framework for multivariate convex regression and its variants. Journal of the American Statistical Association, 114(525):318–331.
  31. [31]Robertson, T., Wright, F. T., and Dykstra, R. L. (1988). Order Restricted Statistical Inference. John Wiley & Sons, Chichester.
  32. [32]Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
  33. [33]Seijo, E. and Sen, B. (2011). Nonparametric least squares estimation of a multivariate convex regression function. The Annals of Statistics, 39(3):1633–1657.
  34. [34]Smith, J. E. and McCardle, K. F. (2002). Structural properties of stochastic dynamic programs. Operations Research, 50(5):796–809.
  35. [35]Varian, H. R. (1982). The nonparametric approach to demand analysis. Econometrica, 50(4):945–973.
  36. [36]Varian, H. R. (1984). The nonparametric approach to production analysis. Econometrica, 52(3):579–597.
  37. [37]Wang, Y. and Ni, H. (2012). Multivariate convex support vector regression with semidefinite programming. Knowledge-Based Systems, 30:87–94.

Paper details

vlnc:W_36374hty
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

generative AI tools

View statement
Looking for related papers…
Contents