Sparse Multi-Reference Alignment: Sample Complexity and Computational Hardness.
Tamir BendoryOscar MichelinAmit SingerPublished in: ICASSP (2022)
Keyphrases
- sample complexity
- theoretical analysis
- vc dimension
- lower bound
- pac learning
- upper bound
- learning problems
- generalization error
- learning algorithm
- special case
- active learning
- supervised learning
- sample complexity bounds
- pac learnability
- decision lists
- training examples
- high dimensional
- uniform convergence
- average case
- worst case
- np hard
- learning environment
- learning theory
- irrelevant features