BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T132540Z
UID:Seminar-networks-651@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20191017T130000
DTEND:20191017T140000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Sebastien Wild: Efficient Second-Order Shape-Constrained Function Fitting\n\nWe 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[nlog(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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=651
LOCATION:
END:VEVENT
END:VCALENDAR