Piecewise Polynomial Regression of Tame Functions via Integer Programming
This work addresses the challenge of approximating complex functions in machine learning and optimization, though it appears incremental as it builds on existing concepts of tame functions and piecewise polynomials.
The paper tackles the problem of approximating tame functions, which are nonsmooth and nonconvex functions relevant in areas like deep neural networks and mixed-integer programs, by using piecewise polynomial functions; it provides bounds on approximation quality and introduces a mixed-integer programming formulation for regression, showing promising computational results.
Tame functions are a class of nonsmooth, nonconvex functions, which feature in a wide range of applications: functions encountered in the training of deep neural networks with all common activations, value functions of mixed-integer programs, or wave functions of small molecules. We consider approximating tame functions with piecewise polynomial functions. We bound the quality of approximation of a tame function by a piecewise polynomial function with a given number of segments on any full-dimensional cube. We also present the first mixed-integer programming formulation of piecewise polynomial regression. Together, these can be used to estimate tame functions. We demonstrate promising computational results.