The Vertex Sample Complexity of Free Energy is Polynomial.
Vishesh JainFrederic KoehlerElchanan MosselPublished in: COLT (2018)
Keyphrases
- sample complexity
- free energy
- upper bound
- lower bound
- pac learning
- vc dimension
- theoretical analysis
- generalization error
- learning problems
- active learning
- learning algorithm
- belief propagation
- special case
- upper and lower bounds
- competitive learning
- fixed point
- supervised learning
- posterior distribution
- sample size
- training examples
- worst case
- data sets
- high dimensional
- machine learning