A Unified Model and Dimension for Interactive Estimation
This work provides a foundational framework that unifies and improves analyses for interactive learning models, benefiting researchers in machine learning theory.
The paper tackles the problem of interactive learning by introducing a unified framework called interactive estimation, which subsumes statistical-query learning and structured bandits, and presents an algorithm with polynomial regret and PAC generalization bounds in a new dissimilarity dimension.
We study an abstract framework for interactive learning called interactive estimation in which the goal is to estimate a target from its "similarity'' to points queried by the learner. We introduce a combinatorial measure called dissimilarity dimension which largely captures learnability in our model. We present a simple, general, and broadly-applicable algorithm, for which we obtain both regret and PAC generalization bounds that are polynomial in the new dimension. We show that our framework subsumes and thereby unifies two classic learning models: statistical-query learning and structured bandits. We also delineate how the dissimilarity dimension is related to well-known parameters for both frameworks, in some cases yielding significantly improved analyses.