A Resilient Distributed Boosting Algorithm
Authors: Yuval Filmus, Idan Mehalel, Shay Moran
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result, formally stated in Theorems 2.2 and 2.3 asserts the following: for every VC class, if the minimal error of an hypothesis satisfies OPT polylog n, then a simple robust variant of classical boosting learns it with poly(d, k, log |S|, log n) communication complexity. Conversely, when OPT / polylog n, there exist one-dimensional VC classes for which any learning algorithm has super-polylogarithmic communication complexity. We prove the upper bound in Section 4 and the lower bound in Section 5. |
| Researcher Affiliation | Collaboration | 1The Henry and Marilyn Taub Faculty of Computer Science, Technion, Haifa, Israel 2Faculty of Mathematics, Technion, Haifa, Israel 3Google Research, Israel. |
| Pseudocode | Yes | Figure 1. A boosting protocol that may get stuck when the input sample is not realizable. Figure 2. A resilient improper, deterministic learning protocol. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It is a theoretical paper presenting algorithms, but no implementation details or links are provided. |
| Open Datasets | No | The paper does not provide concrete access information for a publicly available or open dataset. It refers to 'training data' and 'input sample S' in a theoretical context, but does not mention specific dataset names, links, DOIs, repositories, or formal citations for data. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) needed to reproduce data partitioning. The paper is theoretical and does not describe experimental setups with data splits. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) used for running its experiments. The paper is theoretical and does not describe an experimental setup. |
| Software Dependencies | No | The paper does not provide specific ancillary software details (e.g., library or solver names with version numbers) needed to replicate the experiment. The paper is theoretical and does not describe a software implementation or its dependencies. |
| Experiment Setup | No | The paper does not contain specific experimental setup details (concrete hyperparameter values, training configurations, or system-level settings). The paper is theoretical and focuses on algorithm design and proofs, not empirical evaluations. |