Graph-based Discriminators: Sample Complexity and Expressiveness
Authors: Roi Livni, Yishay Mansour
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the expressiveness of families of k-ary functions, compared to the classical hypothesis class H, which is k = 1. We show a separation in expressiveness of k + 1-ary versus k-ary functions. This demonstrate the great beneļ¬t of having k 2 as distinguishers. For k 2 we introduce a notion similar to the VC-dimension, and show that it controls the sample complexity. We proceed and provide upper and lower bounds as a function of our extended notion of VC-dimension. |
| Researcher Affiliation | Collaboration | Roi Livni Tel Aviv University rlivni@tauex.tau.ac.il Yishay Mansour Tel Aviv University and Google mansour.yishay@gmail.com |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with validation splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |