Piecewise Polynomial Regression of Tame Functions via Integer Programming

Tame functions are a class of nonsmooth, nonconvex functions that appear in a wide range of applications: in training deep neural networks with all common activations, as value functions of mixed-integer programs, or as wave functions of small molecules. We consider approximating tame functions with piecewise polynomial functions. We present a theoretical bound on the approximation quality of a tame function by a piecewise polynomial function. We also present mixed-integer programming formulations of piecewise polynomial regression and demonstrate promising computational results.