Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
Authors: Farnam Mansouri, Yuxin Chen, Ara Vartanian, Jerry Zhu, Adish Singla
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | To better understand the connections between these different batch and sequential models, we develop a novel framework which captures the teaching process via preference functions Σ. In our framework, each function σ P Σ induces a teacher-learner pair with teaching complexity as TDpσq. We show that the above-mentioned teaching models are equivalent to specific types/families of preference functions in our framework. This equivalence, in turn, allows us to study the differences between two important teaching models, namely σ functions inducing the strongest batch (i.e., non-clashing) model and σ functions inducing a weak sequential (i.e., local preference-based) model. Finally, we identify preference functions inducing a novel family of sequential models with teaching complexity linear in the VC dimension of the hypothesis class: this is in contrast to the best known complexity result for the batch models which is quadratic in the VC dimension. We show that the well-studied teaching models in batch setting corresponds to specific families of σ functions in our framework (see 4 and Table 1). We study the differences in the family of σ functions inducing the strongest batch model [KSZ19] and functions inducing a weak sequential model [CSMA 18] ( 5.2) (also, see the relationship between Σgvs and Σlocal in Figure 1). We identify preference functions inducing a novel family of sequential models with teaching complexity linear in the VCD of the hypothesis class. We provide a constructive procedure to find such σ functions with low teaching complexity ( 5.3). |
| Researcher Affiliation | Academia | Farnam Mansouri Yuxin Chen Ara Vartanian Xiaojin Zhu Adish Singla Max Planck Institute for Software Systems (MPI-SWS), {mfarnam, adishs}@mpi-sws.org, University of Chicago, chenyuxin@uchicago.edu, University of Wisconsin-Madison, {aravart, jerryzhu}@cs.wisc.edu |
| Pseudocode | Yes | Algorithm 2 Recursive procedure for constructing σlvs achieving TDX,H,h0pσlvsq ď VCDp H, Xq |
| Open Source Code | No | The paper does not contain any statement about making its source code publicly available, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper uses theoretical constructs like "Warmuth hypothesis class" and "ground set of unlabeled instances X" as examples for its theoretical framework, but does not refer to or provide access information for any publicly available or open dataset used in empirical training. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with data; therefore, it does not provide specific dataset split information (train/validation/test splits). |
| Hardware Specification | No | The paper does not provide any specific hardware details used for running experiments, as it is a theoretical paper without empirical evaluations. |
| Software Dependencies | No | The paper does not provide any specific ancillary software details, such as library names with version numbers, as it is a theoretical paper without software implementations discussed in detail. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments; therefore, it does not provide specific experimental setup details like hyperparameter values or training configurations. |