Improved Algorithms for Collaborative PAC Learning
Authors: Huy Nguyen, Lydia Zakynthinou
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we design new algorithms for both the realizable and the non-realizable setting, having sample complexity only O(ln(k)) times the worst-case sample complexity for learning a single task. The sample complexity upper bounds of our algorithms match previous lower bounds and in some range of parameters are even better than previous algorithms that are allowed to output different classifiers for different tasks. |
| Researcher Affiliation | Academia | Huy Lê Nguy ên College of Computer and Information Science Northeastern University Boston, MA 02115 hu.nguyen@northeastern.edu Lydia Zakynthinou College of Computer and Information Science Northeastern University Boston, MA 02115 zakynthinou.l@northeastern.edu |
| Pseudocode | Yes | Algorithm R1 Initialize: i [k] w(0) i := 1; t := 5 log(k) ; ϵ := ϵ/6; δ := δ/(3t); for r = 1 to t do D(r 1) 1 Φ(r 1) Pk i=1 w(r 1) i Di , where Φ(r 1) = Pk i=1 w(r 1) i ; Draw a sample set S(r) of size mϵ /16,δ from D(r 1); f (r) OF(S(r)); Gr TEST(f (r), k, ϵ , δ ); Update: w(r) i = ( 2w(r 1) i , if i / Gr w(r 1) i , otherwise ; end for return f R1 = maj({f (r)}t r=1) Procedure TEST(f (r), k, ϵ , δ ) for i = 1 to k do Draw a sample set Ti of size O 1 ϵ ln k δ from Di; end for return {i | err Ti(f (r)) 3 |
| Open Source Code | No | No statement or link regarding the release of open-source code for the methodology described in the paper was found. |
| Open Datasets | No | The paper is theoretical and discusses 'drawing from a distribution of samples' and 'sample complexity' in the context of PAC learning, but does not use or provide access information for any specific public or open dataset for training purposes. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with data, therefore, it does not specify training, validation, or test dataset splits. It refers to 'samples' in a theoretical sense, not as part of a concrete dataset. |
| Hardware Specification | No | The paper is theoretical and describes algorithms and proofs; it does not mention any specific hardware used for running experiments or computations. |
| Software Dependencies | No | The paper is theoretical, focusing on algorithm design and theoretical sample complexity bounds. It does not mention any specific software components or their versions required for implementation or reproduction. |
| Experiment Setup | No | The paper is theoretical, proposing new algorithms and proving their sample complexity. It does not describe an experimental setup with hyperparameters or system-level training settings, as it does not report empirical results. |