This is actually a pretty complex question that has to do with many facets of how information entropy is carried in a dataset and how your learning algorithms will make use of the information.
Machine Learning is Optimization
Machine learning at its core is just finding the ideal parameter values in order for a specific function to be represented. This means you will use the data in your dataset and some framework in order to tune these parameters. Learning is an iterative process, as you can see providing one instance to your algorithm will not result in very good results. However, there comes a point when you have provided sufficient data that the information contained in that subset is representative of the information contained in the entire dataset.
You can see this in practice, when training your model you will notice that performance starts to converge to a specific value. If you had infinite data this value would not get any better. This is caused by limitations in your data and not your model (machine learning algorithm). This is the best the specific model you are using can do with that kind of data.
How to get better performance?
Assuming you still have more data but performance is no longer improving, you will want to consider a more complex model. This model will likely be able to extract information from your dataset that is too subtle for your simpler model. This is why deep learning outperforms most classical machine learning algorithms when big data is available. Deep learning makes use of very high complexity to approximate functions very accurately, however, the tradeoff is that a lot of data is needed.
Actually my dataset is quite limited, can I improve my performance?
You actually can! This goes back to the core of machine learning, the dataset you are using. The dataset you have constructed has a certain information entropy based on the features you selected. By increasing the information entropy in your dataset, the complexity of your model can be reduced and this will lead to better performance.
Intuitively, if you are trying to classify dog/cat, but your dataset contains information about the weather the day the measurements were taken, this will reduce the entropy of the information for classifying dog/cat, thus obscuring your other features and reducing performance.
Furthermore, sometimes you may overlook the importance of a certain feature, or overlooking the potential of performing transformations to your features to better suit your model. For example, if you are using linear regression to determine points on 2 circles (radius=1, radius=4). Performing linear regression on the Cartesian plane will lead to very poor results, essentially 50%. However, transforming your $x, y$ coordinates into polar coordinates will lead to 100% performance as they will be perfectly separable. This is a simple application of the kernel trick.