A Unified Model and Dimension for Interactive Estimation

Nataly Brukhim, Miro Dudik, Aldo Pacchiano, Robert Schapire

Research output: Contribution to journalConference articlepeer-review


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 is used to derive learnability bounds 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.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
StatePublished - 2023
Externally publishedYes
Event37th Conference on Neural Information Processing Systems, NeurIPS 2023 - New Orleans, United States
Duration: Dec 10 2023Dec 16 2023

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'A Unified Model and Dimension for Interactive Estimation'. Together they form a unique fingerprint.

Cite this