-approximation in the average case setting.

Wanting Lu Heping Wang

Published in: CoRR (2021)

Keyphrases

average case
worst case analysis
worst case
sample complexity bounds
uniform distribution
approximation algorithms
learning curves
vc dimension
competitive ratio
average case complexity
learning algorithm
decision trees
upper bound
boolean functions