Abstract
This paper addresses the challenge of achieving optimal convergence rates in convex regression, particularly in high dimensions ($d > 4$). By minimizing empirical risk over a specific class of max-affine functions, the authors prove that a partitioned least squares approach can achieve near-optimal rates. The proposed Partitioned Least Squares Estimator (PLSE) balances approximation and estimation errors, effectively mitigating the common issue of overfitting at the boundaries of the data domain.
Introduction
Convex regression—estimating an unknown convex function from noisy data—is a fundamental problem in econometrics, operations research, and reinforcement learning. However, standard Least Squares Estimators (LSEs) often suffer from two major issues:
- Boundary Overfitting: Without sufficient constraints, convex models can create extreme slopes at the edges of the data domain to fit noise, leading to high expected error.
- Dimensionality Challenges: In dimensions $d > 4$, the complexity of the convex function space makes it difficult for standard estimators to reach the theoretical minimax optimal rate of convergence.
This work introduces a new theoretical framework and the PLSE algorithm to resolve these long-standing questions.
Methodology
The core of the proposed approach is the use of max-affine functions to approximate convex targets. Any convex function can be represented as the maximum of a set of affine functions (planes).
The PLSE Algorithm
To avoid the overfitting inherent in using $n$ hyperplanes (one for each data point), the authors propose using a reduced number $K \approx n^{d/(d+4)}$. The algorithm utilizes:
- Voronoi Partitioning: $K$ center points are randomly selected from the data, and each observation is assigned to its nearest center.
- Quadratic Programming: The estimator finds the best max-affine function constrained by this partition. Crucially, it enforces boundedness and Lipschitz constraints to ensure stability.
Theoretical Risk Bounds
The authors develop a technical theorem for nonlinear least squares that extends classical chaining arguments to handle subgaussian noise. This provides tighter risk bounds and demonstrates that while standard LSEs are near-optimal for $d \leq 4$, explicit complexity control is required for higher dimensions.
Empirical Performance
The PLSE was tested on synthetic 8-dimensional datasets against several baselines, including standard LSE, Convex Adaptive Partitioning (CAP), and the Least-Squares Partition Algorithm (LSPA).
Full Quadratic Function
The "full quadratic" function $f(x) \propto \|x\|^2$ tests the model's ability to fit a symmetric, growing function.
Half Quadratic Function
The "half quadratic" function $f(x) \propto \|(x)_+\|^2$ includes both flat and high-growth regions, making it a sensitive test for overfitting.
Key Insights
- Complexity Balancing: The optimal convergence rate is achieved by finding the "sweet spot" between approximation error (fitting the shape) and estimation error (fitting the noise).
- Efficiency: PLSE is computationally faster than standard convex LSE because the reduced number of hyperplanes results in a Quadratic Program with fewer variables and constraints.
- Robustness: Empirical results show that PLSE remains stable in regions where standard LSE typically overfits, such as the flat side of the half-quadratic function.
Conclusion
The authors demonstrate that partitioned max-affine estimators can achieve near-optimal $O(n^{-4/(d+4)} \log n)$ convergence rates for convex regression. By combining randomized partitioning with constrained optimization, the PLSE provides a practical and theoretically sound solution for high-dimensional convex estimation. Future research may explore more sophisticated partitioning schemes and the relaxation of boundedness assumptions.
Summary updated