I have new machine learning algorithm for classification which need 20 minutes for MNIST problem solving (handwritten digits recognition) on plain laptop. How fast is this in comparison with other algorithms? Please tell me about your experiences.
Twenty minutes is neither amazingly fast nor amazingly slow - it's fine.
I have performed quite a number of experiments with quite a few models on MNIST. Most memorable to me are the neural network architectures that I experimented with, and learning times for these models were generally over 20 minutes. More interesting than absolute time is the time complexity of your model, convergence rates of the learning approach, and any other theoretical guarantees that you can prove.
Also, it is possibly more interesting for researchers to know the classification performance of your model. What results do you get? Might be worth looking at the results that are listed here: http://yann.lecun.com/exdb/mnist/
The Best result till now is 1.7% test error rate (60k training patterns and 10k test patterns). I must mention that this is only early result, because till now theye were carried out only two tests.