Average case analysis of learning algorithms Typically analysis of learning algorithms is in the worst-case setting, for example regret bounds in online learning, or generalisation error bounds in classification. Whilst worst case performance is clearly an important question, it seems that average case analysis would be much more indicative of an algorithm's real-world performance. Is such analysis even possible? What assumptions would needed to make it work?
 A: The answer to your question depends on your setting.
If you have two algorithms that perform the same task you might consider training the algorithms on some data and then test them on another set of data to get an error rate and compare them.  There are several cross validation techniques to separate training data from test data in an effective  manner when you have limited data (and please note that you cannot use your training data to test the algorithms).
Steven Salzberg presents an excellent paper on how to use hypothesis testing for comparing algorithms that classify data: On Comparing Classifiers: Pitfalls to Avoid and a Recommended Approach.
On the other hand if you do not have another algorithm to benchmark against you might consider running the experiment several times to get your error rate.  If you assume that your algorithm has a probability p of classifying correctly and each classification is independent from the others, then you have a Binomial distribution.  Given enough results, you can attempt to infer p and its confidence intervals using a tool such as R or Matlab.  For example you might find out that the maximum likelihood estimate for p is 0.9 and you might be 95% sure that p lies between some interval that contains 0.9.
