English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider interactive learning in the realizable setting and develop ageneral framework to handle problems ranging from best arm identification toactive classification. We begin our investigation with the observation thatagnostic algorithms \emph{cannot} be minimax-optimal in the realizable setting.Hence, we design novel computationally efficient algorithms for the realizablesetting that match the minimax lower bound up to logarithmic factors and aregeneral-purpose, accommodating a wide variety of function classes includingkernel methods, H{\"o}lder smooth functions, and convex functions. The samplecomplexities of our algorithms can be quantified in terms of well-knownquantities like the extended teaching dimension and haystack dimension.However, unlike algorithms based directly on those combinatorial quantities,our algorithms are computationally efficient. To achieve computationalefficiency, our algorithms sample from the version space using Monte Carlo"hit-and-run" algorithms instead of maintaining the version space explicitly.Our approach has two key strengths. First, it is simple, consisting of twounifying, greedy algorithms. Second, our algorithms have the capability toseamlessly leverage prior knowledge that is often available and useful inpractice. In addition to our new theoretical results, we demonstrateempirically that our algorithms are competitive with Gaussian process UCBmethods.

Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers