Statistical-Query Lower Bounds via Functional Gradients.
Surbhi GoelAravind GollakotaAdam R. KlivansPublished in: CoRR (2020)
Keyphrases
- lower bound
- statistical queries
- concept class
- upper bound
- noise tolerant
- learning theory
- uniform distribution
- concept classes
- lower and upper bounds
- objective function
- optimal solution
- np hard
- worst case
- sample complexity
- pac model
- pac learning
- vc dimension
- upper and lower bounds
- target concept
- feature selection
- target function
- positive examples
- positive and negative
- theoretical analysis
- classification noise