A Theory of Fault-Tolerant Learning
Authors: Changlong Wu, Yifan Wang, Ananth Grama
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we introduce a novel theoretical framework grounded in learning theory for dealing with faults. In particular, we propose a framework called faulttolerant PAC learning, aimed at identifying the most fault-tolerant models from a given hypothesis class (such as neural networks). We show that if faults occur randomly, fault-tolerant learning is equivalent to regular PAC learning. However, for adversarial faults, we show that the sample complexity of fault-tolerant PAC learning can grow linearly w.r.t. the number of perturbing functions induced by the faults, even for a hypothesis class with VC-dimension 1. We then provide a matching upper bound by restricting the number of perturbing functions. Finally, we show that the linear dependency on the number of perturbing functions can be substantially improved for deletion faults in neural networks. Our work provides a powerful formal framework and avenues for a number of future investigations on the precise characterization of fault-tolerant learning. |
| Researcher Affiliation | Academia | Changlong Wu 1 Yifan Wang 1 Ananth Grama 1 1Center for Science of Information, Department of Computer Science, Purdue University, West Lafayette, USA. Correspondence to: Changlong Wu <wuchangl@hawaii.edu>. |
| Pseudocode | No | The paper is theoretical and does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information for source code. |
| Open Datasets | No | The paper is theoretical and does not use specific datasets in its analysis. |
| Dataset Splits | No | The paper is theoretical and does not use datasets, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |