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, pp 395–408

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.

Example instance for 1st/2nd-diff-constrained vectors — An example instance for the 1st/2nd-difference-constrained vector problem. The task is to find a continuous, piecewise-linear function that crosses the vertical lines within the blue bars (“value constraints”), enters a bar at a slope in the allowed range (“first-order constraints”, green semi-cirlces), and where consecutive slopes differ by an allowable amount (“second-order constraints”, red triangles). The dotted line is a possible solution for this instance.

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.