Back to search

Cornell University

ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION

Abstract

dc:description.abstract

Characterizing the learnability of interactive learning has posed to be a challenge for the longest time. It was not untill recently that a unifying theory of interactive learning was presented, where it was shown a single quantity is both necessary and sufficient for sample-efficient learning. However, learnability results for this setting rely on overly optimistic assumptions about the hypothesis class and simultaneously are not model-dependent. The focus of this dissertation is to address both these issues. In the first half of the dissertation, we attempt to understand how to adapt the model-independent results to characterize learnability for interactive learning in a way which adapts to the problem instance. Then, in the second half of the dissertation, we first work towards understanding the necessity of the assumption used to prove these learnability results and then try to relax these assumptions and find more practical alternatives that still provide us with similar information and guarantees. The work in this dissertation can be seen as progress in developing theoretical guarantees that have practical implications in algorithm choice and design for interactive learning and classification.

Degree

thesis:*
Name thesis:degree_name
M.S., Computer Science
Level thesis:degree_level
Master of Science
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ganju, Atul
Chair dc:contributor.chair
  • Sridharan, Karthik
Committee member dc:contributor.committeemember
  • Stephens-Davidowitz, Noah

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16612013
Dc Identifier Other
ProQuest Submission ID: 12271
ProQuest Publication ID: 31489643

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ganju, Atul. ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION. Master of Science thesis, Cornell University, 2024. https://hdl.handle.net/1813/116268