Piece-wise linear isotonic regression

Technical Summary: Piece-wise Linear Isotonic Regression

Problem Statement
Isotonic regression offers a flexible, tuning-free method for estimating monotonic functions without imposing global curvature constraints (e.g., concavity). However, the standard Isotonic Nonparametric Least Squares (INLS) estimator produces a step function. While robust and consistent, this step function is inherently non-differentiable. Consequently, it cannot provide meaningful marginal properties essential for economic and operational analysis, such as shadow prices or elasticities. Standard smoothing techniques, such as global convex interpolation, are unsuitable because they would reimpose the global curvature constraints (like concavity) that the INLS estimator was specifically designed to relax, thereby erasing local non-convexities (e.g., S-shaped curves) identified in the data.

Methodology
The authors propose a novel Piece-wise Linear Isotonic Regression framework, termed CC-INLS (Conditionally Convex INLS), to bridge the gap between the step-function nature of INLS and the need for continuous, differentiable marginal estimates. The methodology proceeds in three stages:

1. Anchor Point Identification: The process begins with the standard INLS estimation, which yields a step function with constant fitted values over specific blocks of observations. The authors define a set of "anchor points" representing these blocks. Two strategies are employed for determining the coordinate vector of each anchor:

   • Vertices: The component-wise minimums of the observations within a block.
   • Centroids: The mean or median of the observations within a block.

2. Conditional Convexity Formulation: To smooth the step function while preserving local non-convexities, the authors adapt the concept of conditional convexity (originally from deterministic frontier analysis in Data Envelopment Analysis). A set of points is conditionally convex if the local linear facets used for interpolation do not "dominate" any existing anchor point. This ensures that the smoothing process respects local shape variations, such as inflection points in S-shaped curves, rather than bridging over them with a globally concave surface.

3. Bilevel Programming and Single-Level Reformulation: The smoothing process is formulated as a bilevel optimization problem:

   • Leader Problem: Constructs a prediction for a given input by finding a convex combination of anchor points that maximizes the response value while ensuring the selected anchors form a valid local facet.
   • Follower Problem: Acts as a rigorous test to verify that the proposed facet does not dominate any other existing anchor points (i.e., it does not cross over local non-convexities).

   To make the problem computationally tractable, the authors reformulate this bilevel structure into a single-level Mixed-Integer Linear Programming (MILP) problem. This is achieved by:

   • Linearizing the exact coplanarity conditions using Big-M constraints and binary selection variables.
   • Replacing the follower problem with its strong duality conditions (equating primal and dual objectives), thereby avoiding the need for complex Karush-Kuhn-Tucker (KKT) conditions.

Key Contributions

• Novel Smoothing Framework: The paper introduces a method to recover continuous, piece-wise linear regression surfaces from INLS step functions without imposing global curvature constraints.
• Marginal Property Recovery: The approach enables the direct calculation of marginal properties (shadow prices, elasticities) in non-convex settings, a capability previously unavailable with standard isotonic estimators.
• Computational Efficiency: By leveraging strong duality to collapse the bilevel problem into a single-level MILP, the method allows for exact computation using standard solvers (e.g., CPLEX, Gurobi).
• Shape Preservation: The use of conditional convexity ensures that local non-convexities (e.g., S-shaped patterns) identified by the initial INLS step are preserved rather than smoothed out.

Results
The authors evaluate the CC-INLS estimator through Monte Carlo simulations and an empirical application:

• Monte Carlo Simulations:

  • Scenarios: The study tests the estimator on both non-convex (logistic/S-shaped) and globally concave (Cobb-Douglas) data-generating processes across univariate and multivariate settings with varying noise levels.
  • Performance: The CC-INLS estimators (both vertex and centroid variants) consistently outperform the standard unsmoothed INLS step function in terms of out-of-sample Root Mean Squared Error (RMSE).
  • Bias Reduction: The proposed smoothing techniques effectively mitigate the strong negative bias inherent in the unsmoothed INLS estimator.
  • Robustness: The choice between vertex and centroid anchor points has a negligible impact on predictive accuracy, suggesting the primary gain stems from the conditional convexity principle itself.
  • Multivariate Gains: The improvement in precision is particularly pronounced in multivariate settings and high-noise environments.

• Empirical Application (Finnish Municipalities):

  • The method is applied to estimate agglomeration economies by modeling the relationship between municipality population and job availability.
  • The CC-INLS estimator provided accurate out-of-sample predictions and successfully generated continuous regression curves.
  • Crucially, the application demonstrated the ability to estimate scale elasticities nonparametrically, a task impossible with the step-function INLS.

Significance and Claims
The paper claims that the CC-INLS framework addresses a fundamental limitation of isotonic regression: the inability to evaluate marginal effects due to non-differentiability. By integrating conditional convexity, the authors demonstrate that it is possible to construct a continuous, monotonic, piece-wise linear surface that strictly preserves local shape variations and non-convexities.

The authors assert that this approach not only facilitates the calculation of shadow prices and elasticities but also systematically improves overall estimation precision compared to the standard INLS estimator. They note that the method is robust across different functional forms (both non-convex and concave) and data dimensionalities. While the paper acknowledges that computational burden scales with sample size and dimensionality, it posits that the single-level MILP reformulation makes the approach practically viable for standard datasets. The study concludes that the conditional convexity principle is a robust tool for shape-preserving smoothing in nonparametric regression.