Efficient Second-Order Shape-Constrained Function Fitting

This paper describes a novel dynamic-programming algorithm for testing whether a given set of points $(x_1,y_1),\ldots,(x_n,y_n)$ can be explained by a (discrete) function that must satisfy bounds on its (discrete) first- and second-order derivatives.

The DP algorithm can thus find, e.g., a *convex* regression function
with $L_\infty$ error at most OPT + ε in time $O(n \log (U/\varepsilon))$,
where $U$ captures the universe size of numbers in the input.

This is a generalization of the more restricted isotonic regression, where the regression function only has to be increasing, i.e., only has to satisfy bounds on first-order derivatives.