Piecewise Linear Regression via a Difference of Convex Functions

Ali Siahkamari, Aditya Gangrade, Brian Kulis, Venkatesh Saligrama
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:8895-8904, 2020.

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 $f$ that may be represented as the difference $\phi_1 - \phi_2$ for a choice of \emph{convex} functions $\phi_1, \phi_2$. 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 $\ell_\infty$ 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-siahkamari20a, title = {Piecewise Linear Regression via a Difference of Convex Functions}, author = {Siahkamari, Ali and Gangrade, Aditya and Kulis, Brian and Saligrama, Venkatesh}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {8895--8904}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/siahkamari20a/siahkamari20a.pdf}, url = {https://proceedings.mlr.press/v119/siahkamari20a.html}, 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 $f$ that may be represented as the difference $\phi_1 - \phi_2$ for a choice of \emph{convex} functions $\phi_1, \phi_2$. 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 $\ell_\infty$ 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.} }
Endnote
%0 Conference Paper %T Piecewise Linear Regression via a Difference of Convex Functions %A Ali Siahkamari %A Aditya Gangrade %A Brian Kulis %A Venkatesh Saligrama %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-siahkamari20a %I PMLR %P 8895--8904 %U https://proceedings.mlr.press/v119/siahkamari20a.html %V 119 %X 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 $f$ that may be represented as the difference $\phi_1 - \phi_2$ for a choice of \emph{convex} functions $\phi_1, \phi_2$. 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 $\ell_\infty$ 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.
APA
Siahkamari, A., Gangrade, A., Kulis, B. & Saligrama, V.. (2020). Piecewise Linear Regression via a Difference of Convex Functions. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:8895-8904 Available from https://proceedings.mlr.press/v119/siahkamari20a.html.

Related Material