A Lower Bound for Distribution-Free Monotonicity Testing.
Shirley HalevyEyal KushilevitzPublished in: APPROX-RANDOM (2005)
Keyphrases
- distribution free
- lower bound
- concept class
- vc dimension
- upper bound
- sample complexity
- concept classes
- learning theory
- large deviations
- normal distribution
- worst case
- membership queries
- optimal solution
- np hard
- pac learning
- concept learning
- learning algorithm
- linear programming
- uniform distribution
- euclidean space
- objective function