Multi-Reference Alignment in High Dimensions: Sample Complexity and Phase Transition.
Elad RomanovTamir BendoryOr OrdentlichPublished in: SIAM J. Math. Data Sci. (2021)
Keyphrases
- phase transition
- high dimensions
- sample complexity
- high dimensional
- theoretical analysis
- constraint satisfaction
- learning algorithm
- pac learning
- high dimensional data
- vc dimension
- learning problems
- active learning
- special case
- lower bound
- upper bound
- supervised learning
- generalization error
- training examples
- high dimensional spaces
- sample size
- np complete
- decision lists
- concept classes
- cellular automata
- worst case
- training data
- high dimensionality
- learning tasks
- constraint satisfaction problems
- random graphs
- feature space