Research map / Learning theory and algorithms / Sample complexity
A Theory of Fault-Tolerant Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a learning-theoretic framework (fault-tolerant PAC learning) and derives sample complexity bounds for random and adversarial faults, including polynomial bounds for threshold neural networks under deletion faults.
Problem
Learning models that remain accurate under hardware faults (random or adversarial perturbations of parameters) lacks formal theoretical foundations; it is unclear how fault type affects sample complexity of learning.
Approach
Model faults as a map from each hypothesis index to a set of perturbation distributions over indices, define faulty loss as a sup over those distributions, and define fault-tolerant PAC learnability on this risk. Random faults reduce to regular PAC learning of a convex-hull class, while adversarial faults are characterized by the size of the fault set, with a polynomial bound for threshold network
Key results
- For random fault types with |U(w)|=1, fault-tolerant PAC learnability is equivalent to regular PAC learning with sample complexity O((VC(H)+log(1/δ))/ϵ²).
- There exists a VC-dimension-1 class where adversarial fault-type sample complexity grows linearly in the fault-set size B (lower bound Ω(B)).
- For fault sets of size at most B, the upper bound is Õ(B·VC(H)+log(1/δ))/ϵ²) for adversarial faults; for threshold neural networks under deletion faults, sample complexity is polynomial in network size and independent of the number of deletion subsets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use random faults instead of adversarial faults | Fault-tolerant PAC learning · Random fault-types | sample complexity | No clear effect |
| Bound random fault-type size to |U(w)| = 1 | Fault-tolerant PAC learning · Random fault-types | sample complexity | Helped |
| Allow adversarial faults with size at most B | Fault-tolerant PAC learning · Adversarial fault-types | sample complexity: M(1/8, 1/7; Hf, U) ≥ Ω(B) | Hurt |
| Bound the size of a general fault-type by B | Fault-tolerant PAC learning · Adversarial fault-types | sample complexity | Helped |
| Restrict the bounded-size fault-type to adversarial faults | Fault-tolerant PAC learning · Adversarial fault-types | sample complexity | Helped |
| Use an edge-deletion-specific analysis instead of the generic bound based on |S| | Fault-tolerant PAC learning · Feed-forward neural networks with deletion faults | sample complexity | Helped |
Surprising findings
- Threshold neural networks under deletion faults admit polynomial sample complexity independent of the number of possible deletion sets, even though the fault set can be exponentially large.
Limitations
- Results are purely statistical; computational efficiency of the fault-tolerant ERM rule is left as future work.
- Analysis of deletion faults is limited to threshold activation networks; ReLU and other fault types (neuron activation faults, precision errors) are not covered.
Experimental setup
Metrics: sample complexity fault-tolerant regret
Builds on: PAC learning adversarially robust PAC learning (Montasser et al., 2019) Rademacher complexity
Closest papers by meaning
- Fault Tolerance in Iterative-Convergent Machine Learning (ICML 2019 · similarity 0.86)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.84)
- Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.84)
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.83)
- Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss (NeurIPS 2024 · similarity 0.82)
- The Role of Randomness in Stability (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.