Efficient Second-Order Shape-Constrained Function Fitting


Durfee, David, Gao, Yu, Rao, Anup B and Wild, Sebastian ORCID: 0000-0002-6061-9177 (2019) Efficient Second-Order Shape-Constrained Function Fitting .

Warning
There is a more recent version of this item available.
[thumbnail of 1905.02149v2.pdf] Text
1905.02149v2.pdf - Submitted version
Download (720kB) | Preview

Abstract

We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted-L∞$$L_{\infty }$$ 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 ϵ$$\epsilon $$ in OnlogUϵ$$O\left( n \log \frac{U}{\epsilon } \right) $$ 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∞$$L_{\infty }$$ 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.

Item Type: Conference Item (Unspecified)
Additional Information: accepted for WADS 2019; (v2 fixes various typos)
Uncontrolled Keywords: 46 Information and Computing Sciences
Depositing User: Symplectic Admin
Date Deposited: 15 Aug 2019 14:38
Last Modified: 13 May 2025 17:20
DOI: 10.1007/978-3-030-24766-9_29
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3051854
Disclaimer: The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.

Available Versions of this Item

Altmetric
CORE (COnnecting REpositories)