On Detecting Regularity of Functions: A Probabilistic Analysis

We study the problem of detecting the regularity degree deg(f{hook}) = max{k: k ≤ r, f{hook} ∈ C^k} of functions based on a finite number of function evaluations. Since it is impossible to find deg(f{hook}) for any function f{hook}, we analyze this problem from a probabilistic perspective. We prove that when the class of considered functions is equipped with a Wiener-type probability measure, one can compute deg(f{hook}) exactly with super exponentially small probability of failure. That is, we propose an algorithm which, given n function values at equally spaced points, might propose a value different than deg(f{hook}) only with probability O((n^-1 ln n)^{(n - r)/4}). Hence, regularity detection is easy in the probabilistic setting even though it is unsolvable in the worst case setting.