{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/116268"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/116268","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ganju, Atul"],"institution":"Cornell University","degree_name":"M.S., Computer Science","degree_level":"Master of Science","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Sridharan, Karthik"],"committee_members":["Stephens-Davidowitz, Noah"],"year":2024,"date_issued":"2024-08","date_published":"2024-08","updated_at":"2026-11-19T03:11:32Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/en7j-m584"],"render_values":[{"text":"https://doi.org/10.7298/en7j-m584","href":"https://doi.org/10.7298/en7j-m584","code":true}]},{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["16612013"],"render_values":[{"text":"16612013","href":null,"code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 12271","ProQuest Publication ID: 31489643"],"render_values":[{"text":"ProQuest Submission ID: 12271","href":null,"code":true},{"text":"ProQuest Publication ID: 31489643","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/116268","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/116268","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":"embargoed","embargo_until":"2026-09-03","access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F116268","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Sridharan, Karthik"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Stephens-Davidowitz, Noah"]},{"key":"dc:creator","label":"Author","values":["Ganju, Atul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-01-14T19:39:29Z"]},{"key":"dc:date.embargo","label":"Dc Date Embargo","values":["2026-09-03"]},{"key":"dc:date.issued","label":"Date","values":["2024-08"]},{"key":"dc:relation.uri","label":"Dc Relation URI","values":["https://newcatalog.library.cornell.edu/catalog/16612013"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Master of Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S., Computer Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["16612013"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/en7j-m584"]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 12271","ProQuest Publication ID: 31489643"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/116268"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"6ee12eff-7328-49f4-958f-1d7e4aac6b5d\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2024-08</PublicationDate> <DOI>https://doi.org/10.7298/en7j-m584</DOI> <Authors> <Author> <DisplayName>Ganju, Atul</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Ganju, Atul"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description","label":"Description","values":["32 pages"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dcterms:license","label":"Dcterms License","values":["https://hdl.handle.net/1813/59810.2"]},{"key":"dc:title","label":"Title","values":["ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["embargo"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"6ee12eff-7328-49f4-958f-1d7e4aac6b5d\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2024-08</PublicationDate> <DOI>https://doi.org/10.7298/en7j-m584</DOI> <Authors> <Author> <DisplayName>Ganju, Atul</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Ganju, Atul"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Sridharan, Karthik"],"dc:contributor.committeemember":["Stephens-Davidowitz, Noah"],"dc:creator":["Ganju, Atul"],"dc:date.accessioned":["2025-01-14T19:39:29Z"],"dc:date.embargo":["2026-09-03"],"dc:date.issued":["2024-08"],"dc:description":["32 pages"],"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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["16612013"],"dc:identifier.doi":["https://doi.org/10.7298/en7j-m584"],"dc:identifier.other":["ProQuest Submission ID: 12271","ProQuest Publication ID: 31489643"],"dc:identifier.uri":["https://hdl.handle.net/1813/116268"],"dc:language.iso":["en"],"dc:relation.uri":["https://newcatalog.library.cornell.edu/catalog/16612013"],"dcterms:license":["https://hdl.handle.net/1813/59810.2"],"dc:title":["ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["embargo"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Master of Science"],"thesis:degree_name":["M.S., Computer Science"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:11:32Z"}