IPAB Workshop - 08/08/19

Title: When Timely Approximation beats Precise Estimation

Abstract: Computation plays a central role in solutions to many problems in computer science. Most computational models rely on approximation and are therefore assessed by a quantitative analysis of errors that they introduce. The rate at which error diminishes with increasing computational effort -- usually referred to as convergence rate -- is a popular criterion and unbiased models, those for which error vanishes asymptotically, are often preferred. However, for practical use, timeliness which is the minimum attainable error within a given time budget is crucial.

In this talk, I will try to strike a balance between theory and practice.  First I will provide an overview of recent work spanning applications in interactive robotics and computer graphics where timely estimation is important. Then, I will present a recent theoretical analysis of the effect of sample correlations on the error of Monte Carlo integration. Finally, I will motivate the need for a measure to predict errors arising from sampling, and provide a summary of ongoing work in this direction.