If a learning algorithm is Pac Learnable and it runs in Polynomial time, it's Efficiently PAC Learnable

Calculating the runtime

Runtime of a learning algorithm can be seen in two parts

1. The number of oracle calls
   1. Translation: The size of the dataset it needs
2. How long it processes each datapoint

Intuition

If we make the problem harder:

• Make the target concept a difficult one
• Choose a bullshit distribution that does not help the learning
• Ask for higher confident level $\delta$
• Ask for better accuracy
  The algorithm CAN learn it anyway (that's the definition of PAC learnable).
  But it may need:
• A bigger dataset to train (more calls to oracle)
• Process the dataset more (maybe go through more epochs)