Given a machine learning algorithm, what is the minimum size of the training set for it?
You can have a model with a single training example.  The real question should be, how good is your model with only a single training example. The answer? A learning algorithm $h(\theta)$ is an approximation of the actual relationship between your features and your target. However, the performance on how good $h(\theta)$ relies on good data. Your model is only as good as your data. If your data shows clear patterns, you can have a good model with a few data points. That's why Exploratory Data Analysis is essential. 

I'd recommend watching Statistical Learning theory on youtube, specifically the lecture "Is learning feasible". The class is offered by Caltech.