Best Free Knot Linear Spline Approximation and its Application to Neural Networks

Abstract The problem of fixed knot approximation is convex and there are several efficient approaches to solve this problem, yet, when the knots joining the affine parts are also variables, finding conditions for a best Chebyshev approximation remains an open problem. It was noticed before that piecewise linear approximation with free knots is equivalent to neural network approximation with piecewise linear activation functions (for example ReLU). In this paper, we demonstrate that in the case of one internal free knot, the problem of linear spline approximation can be reformulated as a mixed-integer linear programming problem and solved efficiently using, for example, a branch and bound type method. We also present a new sufficient optimality condition for a one free knot piecewise linear approximation. The results of numerical experiments are provided. These results support our theoretical findings and illustrate the extension of the approximation classical results, developed for convex problems (polynomial and fixed knot polynomial spline approximation). All the results are developed for the Chebyshev (uniform) norm. In addition, this study extends previous results obtained for $l_{p}$ norms (with $p<\infty $) to address an existing gap in the literature.