# Efficient Second-Order Shape-Constrained Function Fitting

Aug 2019 (Written: Feb 2019)

David Durfee, Yu Gao, Anup B. Rao, and Sebastian Wild:

Algorithms and Data Structures Symposium (WADS) 2019
in Z. Friggstad, JR. Sack, M. Salavatipour (Eds.): WADS 2019, LNCS 11646, Springer, 2019, 395-408

pdfdoiarxivslides |

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.