The Sample Complexity of Level Set Approximation

Francois Bachoc · Tommaso Cesari · Sébastien Gerchinovitz

Keywords: [ Online Learning ] [ Learning Theory and Statistics ]

[ Abstract ]
Wed 14 Apr 6 a.m. PDT — 8 a.m. PDT
Oral presentation: Theory and Methods of Learning
Wed 14 Apr 8:15 a.m. PDT — 9:15 a.m. PDT


We study the problem of approximating the level set of an unknown function by sequentially querying its values. We introduce a family of algorithms called Bisect and Approximate through which we reduce the level set approximation problem to a local function approximation problem. We then show how this approach leads to rate-optimal sample complexity guarantees for Hölder functions, and we investigate how such rates improve when additional smoothness or other structural assumptions hold true.

Chat is not available.