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. .

This is the latest version of this item.

[img] Text
1905.02149v2.pdf - Submitted version
Download (720kB) | Preview
[img] Text
durfee-gao-rao-wild-2019-1.pdf - Author Accepted Manuscript
Download (602kB) | Preview

Abstract

We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted-$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 $\varepsilon$ in $O\left(n \log \frac{U}{\varepsilon} \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_{\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 or Workshop Item (Unspecified)
Additional Information: accepted for WADS 2019; (v2 fixes various typos)
Uncontrolled Keywords: cs.DS, cs.DS, cs.LG
Depositing User: Symplectic Admin
Date Deposited: 21 Oct 2019 15:05
Last Modified: 19 Jan 2023 00:21
DOI: 10.1007/978-3-030-24766-9_29
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3058949

Available Versions of this Item

Dimensions
Altmetric
CORE (COnnecting REpositories)