# 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?