Lower Bound on Weights of Large Degree Threshold Functions
Vladimir V. PodolskiiPublished in: Log. Methods Comput. Sci. (2013)
Keyphrases
- threshold functions
- lower bound
- low degree
- boolean functions
- upper bound
- decision lists
- linear threshold
- np hard
- worst case
- sample complexity
- lower and upper bounds
- concept classes
- optimal solution
- objective function
- linear combination
- machine learning
- linear classifiers
- pac learning
- uniform distribution
- error rate
- supervised learning