Efficient Learning Algorithm (PAC-learning)

Definition

Efficient Learning Algorithm (PAC-learning)

A learning algorithm $\mathcal{A}$ is called efficient if the $\mathcal{A}$ uses polynomially many samples and runs in polynomial time.