2019/05/06 by Durfee, David, Gao, Yu, Rao, Anup B. +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.1905.02149
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted-L∞ norm. We give a single algorithm that works for a variety of commonly studied shape constraints including monotonicity, Lipschitz-continuity and convexity, and more generally, any shape constraint expressible by bounds on first- and/or second-order differences. Our algorithm computes an approximation with additive error ε in O(n log (U)/(ε) ) time, where U captures the range of input values. We also give a simple greedy algorithm that runs in O(n) time for the special case of unweighted L∞ convex regression. These are the first (near-)linear-time algorithms for second-order-constrained function fitting. To achieve these results, we use a novel geometric interpretation of the underlying dynamic programming problem. We further show that a generalization of the corresponding problems to directed acyclic graphs (DAGs) is as difficult as linear programming.