Estimating the average of a Lipschitz-continuous function from one sample

DOI10.1007/978-3-642-15775-2_19MaRDI QIDQ3586464zbMATH OpenOpenAlexFDO

Authors Abhimanyu Das, David Kempe

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.3804

Mathematics Subject Classification ID

Nonparametric inference (62G99) Roundoff error (65G50) Approximation algorithms (68W25)

Abstract: We study the problem of estimating the average of a Lipschitz continuous function $f$ defined over a metric space, by querying $f$ at only a single point. More specifically, we explore the role of randomness in drawing this sample. Our goal is to find a distribution minimizing the expected estimation error against an adversarially chosen Lipschitz continuous function. Our work falls into the broad class of estimating aggregate statistics of a function from a small number of carefully chosen samples. The general problem has a wide range of practical applications in areas as diverse as sensor networks, social sciences and numerical analysis. However, traditional work in numerical analysis has focused on asymptotic bounds, whereas we are interested in the emph{best} algorithm. For arbitrary discrete metric spaces of bounded doubling dimension, we obtain a PTAS for this problem. In the special case when the points lie on a line, the running time improves to an FPTAS. Both algorithms are based on approximately solving a linear program with an infinite set of constraints, by using an approximate separation oracle. For Lipschitz-continuous functions over $[0,1]$, we calculate the precise achievable error as $1-fracsqrt32approx0.134$, which improves upon the quarter which is best possible for deterministic algorithms.

Recommendations

• Optimal estimation of univariate black-box Lipschitz functions with upper and lower error bounds.
• Optimally adaptive integration of univariate Lipschitz functions
• An improved bound for learning Lipschitz functions
• Optimally Adaptive Integration of Univariate Lipschitz Functions
• Estimation of the Lipschitz constant of a function

This page was built for publication: Estimating the average of a Lipschitz-continuous function from one sample

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586464)