  We propose to approximate a (possibly discontinuous) multivariate function f
(x) on a compact set by the partial minimizer arg miny p(x, y) of an
appropriate polynomial p whose construction can be cast in a univariate sum of
squares (SOS) framework, resulting in a highly structured convex semidefinite
program. In a number of non-trivial cases (e.g. when f is a piecewise
polynomial) we prove that the approximation is exact with a low-degree
polynomial p. Our approach has three distinguishing features: (i) It is
mesh-free and does not require the knowledge of the discontinuity locations.
(ii) It is model-free in the sense that we only assume that the function to be
approximated is available through samples (point evaluations). (iii) The size
of the semidefinite program is independent of the ambient dimension and depends
linearly on the number of samples. We also analyze the sample complexity of the
approach, proving a generalization error bound in a probabilistic setting. This
allows for a comparison with machine learning approaches.
