PAC-Learning for Strategic Classification
Authors: Ravi Sundaram, Anil Vullikanti, Haifeng Xu, Fan Yao
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce the novel notion of strategic VC-dimension SVC(H, R, c) which captures the learnability of any hypothesis class H when test data points strategic behaviors are induced by cost function c and preference values from any set R R. We prove that any strategic classification problem is agnostic PAC learnable by the empirical risk minimization paradigm with O ϵ 2[d + log( 1 δ ))] samples, where d =SVC(H, R, c). Conceptually, this result illustrates that SVC correctly characterizes the learnability of the hypothesis class H in our strategic setup. |
| Researcher Affiliation | Academia | 1Khoury College of Computer Science, Northeastern University, Boston, MA 02115 2Department of Computer Science, University of Virginia, Charlottesville, VA 22904 3Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA 22904. |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. It focuses on theoretical definitions, theorems, and proofs. |
| Open Source Code | No | The paper is theoretical and does not describe a software implementation or provide any information about open-source code being released. |
| Open Datasets | No | The paper is theoretical and discusses training data in a conceptual sense ("n uncontaminated training data points (x1, y1, r1), ..., (xn, yn, rn) drawn independently and identically (i.i.d.) from distribution D") but does not use or provide access to any specific public or open datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with actual datasets, therefore it does not specify training, validation, or test splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or system-level training settings. |