Piecewise Linear Regression via a Difference of Convex Functions

Ali Siahkamari, Aditya Gangrade, Brian Kulis, Venkatesh Saligrama

TL;DR

This paper introduces a novel piecewise linear regression method that leverages "difference of convex" (DC) functions. This approach allows for efficient, high-dimensional regression by reformulating the problem as a convex optimization task, achieving competitive accuracy and interpretability.

What Problem Does This Paper Address?

The paper tackles the challenge of multivariate nonparametric regression, where the goal is to learn a function $f$ from noisy data $(x_i, y_i)$ such that $y_i = f(x_i) + \epsilon_i$. Traditional methods for high-dimensional data often struggle with computational complexity or require strong assumptions about the function's structure. Piecewise linear regression, while interpretable, faces difficulties in defining partitions in higher dimensions. This work aims to bridge this gap by proposing a method that is both statistically robust and computationally efficient in high dimensions, by modeling functions as differences of convex functions (DC functions).

Methods

The core contribution is a new methodology for piecewise linear regression using DC functions. The authors represent these functions as the difference of two piecewise linear convex functions. A key innovation is the introduction of a new seminorm that regularizes the DC function, controlling its $\ell_\infty$-Lipschitz constant. This regularization allows the problem to be cast as a convex optimization problem, specifically a quadratic program, which can be solved efficiently even in high dimensions. The method is also shown to be agnostic to prior knowledge about the function and requires minimal parameter tuning. The paper also establishes theoretical connections between DC functions and popular models like ReLU neural networks, demonstrating their expressive power.

Datasets

The paper evaluates its method on both synthetic and real-world datasets.

Regression Tasks: * ROCK SAMPLES * ACETYLENE * MOORE * REACTION * CAR SMALL * CEREAL * BOSTON HOUSING * FOREST FIRES

Multi-class Classification Tasks: * BPD * IRIS * BALANCE SCALE * ECOLI * WINE * HEART DISEASE * IONOSPHERE

The authors note that the datasets were chosen to fit within the regime of $n \le 10^3$ and $d \le 10^2$, which is typical for nonparametric methods due to computational and sample complexity constraints.

Key Insights and Ideas

  • DC Functions as a Rich Class: The paper highlights that difference of convex (DC) functions form a very rich class, encompassing many commonly used functions and allowing for flexible modeling without strong prior assumptions.
  • Convex Optimization for Piecewise Linear Models: By representing piecewise linear functions as differences of convex functions and introducing a novel seminorm, the authors successfully transform a potentially non-convex problem into a convex optimization problem (quadratic programming). This is a significant algorithmic advantage.
  • Efficient High-Dimensional Regression: The proposed method is designed to scale well with dimensionality, overcoming a major hurdle for many existing nonparametric techniques.
  • Interpretability through Sparsity: The regularization imposed by the DC seminorm naturally leads to sparse representations of local features, enhancing the interpretability of the learned piecewise linear model.
  • Theoretical Connections: Demonstrating that ReLU networks can be represented by PLDC functions (and vice-versa) provides a strong theoretical foundation and links the proposed method to a widely used class of models.

Key Results

  • Competitive Performance: Empirically, the proposed DC function regression method demonstrates comparable or superior performance to existing methods like Multivariate Adaptive Regression Splines (MARS), K-Nearest Neighbors (KNN), and Multi-Layer Perceptrons (MLPs) on both synthetic and real-world regression and classification tasks.
  • Efficiency in High Dimensions: The method is shown to be efficiently implementable via quadratic programming, even in high-dimensional settings, which is a key advantage over many other nonparametric approaches.
  • Statistical Guarantees: The paper provides theoretical guarantees on the statistical viability of the method, showing it attains vanishing risk and adapts to low-dimensional structures in the data.
  • Lower Error Variance: On synthetic data, the DC function regression method exhibited lower error variance across multiple runs compared to competing methods.

Limitations and Future Work

  • Suboptimality Gap: While the method achieves near-minimax risk, there's a multiplicative gap (approximately $n^{4/d^2}$) that diverges polynomially with $n$. The authors suspect this suboptimality could be ameliorated by restricting the PLDC estimate to a smaller, precisely chosen number of hyperplanes ($K_n < n$). However, this would increase training costs, which they did not pursue.
  • Computational Cost: Although efficient for high dimensions, the worst-case complexity for solving the optimization problem can still be substantial ($O(d^2n^5)$). The authors mention that in practice, problems are solved faster, and they propose GPU implementations and ADMM optimizers for speedups.
  • Future Work: The authors suggest exploring restrictions to fewer hyperplanes to potentially close the suboptimality gap. Further investigation into the practical trade-offs between model complexity (number of hyperplanes) and computational cost is also implied.

Summary updated

Abstract

We present a new piecewise linear regression methodology that utilises fitting a\emph {difference of convex} functions (DC functions) to the data. These are functions that may be represented as the difference for a choice of\emph {convex} functions . The method proceeds by estimating piecewise-liner convex functions, in a manner similar to max-affine regression, whose difference approximates the data. The choice of the function is regularised by a new seminorm over the class of DC functions that controls the Lipschitz constant of the estimate. The resulting methodology can be efficiently implemented via Quadratic programming\emph {even in high dimensions}, and is shown to have close to minimax statistical risk. We empirically validate the method, showing it to be practically implementable, and to outperform existing regression methods in accuracy on real-world datasets.
BibTeX
@inproceedings{siahkamari2020piecewise,
  author = {Ali Siahkamari and Aditya Gangrade and Brian Kulis and Venkatesh Saligrama},
  title = {{Piecewise Linear Regression via a Difference of Convex Functions}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=qBoq1tYm4qM},
}
Figure