We present a new piecewise linear regression methodology that utilizes
fitting a 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 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 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 have comparable
performance to existing regression/classification methods on real-world
datasets.

本文介绍了一种新的分段线性回归方法，利用凸函数差的拟合数据，通过分段凸函数的估计来近似数据。方法可以通过二次规划高效实现并在现实世界数据集上验证了它的可行性和性能。

分段线性回归与凸函数差分

Piecewise Linear Regression via a Difference of Convex Functions

Max-affine regression refers to a model where the unknown regression function
is modeled as a maximum of $k$ unknown affine functions for a fixed $k \geq 1$.
This generalizes linear regression and (real) phase retrieval, and is closely
related to convex regression. Working within a non-asymptotic framework, we
study this problem in the high-dimensional setting assuming that $k$ is a fixed
constant, and focus on estimation of the unknown coefficients of the affine
functions underlying the model. We analyze a natural alternating minimization
(AM) algorithm for the non-convex least squares objective when the design is
random. We show that the AM algorithm, when initialized suitably, converges
with high probability and at a geometric rate to a small ball around the
optimal coefficients. In order to initialize the algorithm, we propose and
analyze a combination of a spectral method and a random search scheme in a
low-dimensional space, which may be of independent interest. The final rate
that we obtain is near-parametric and minimax optimal (up to a poly-logarithmic
factor) as a function of the dimension, sample size, and noise variance. In
that sense, our approach should be viewed as a direct and implementable method
of enforcing regularization to alleviate the curse of dimensionality in
problems of the convex regression type. As a by-product of our analysis, we
also obtain guarantees on a classical algorithm for the phase retrieval problem
under considerably weaker assumptions on the design distribution than was
previously known. Numerical experiments illustrate the sharpness of our bounds
in the various problem parameters.

本文提出了一种 max-affine 回归模型，以及使用交替最小化的算法来解决估计未知字的问题，通过组合光谱方法和一个低维度随机搜索方案初始化算法。结果表明，我们的方法是直接可实现的，可以缓解维度诅咒问题。