On the hardness of data to learn Almost in all texts which are discussing theorems of statistical learning, they assume analyzing arbitrary unknown distribution (the worst case). But in practice different problems (different data) have different levels of hardness, for example linear separable data is easier to learn than the data that are less (or not) separable by hyperplanes. 
Are there any works on formalizing the hardness of data (similar to the stuff done in complexity theory)
Note: I am not sure if the same as analyzing VC-dimension or not, but I think it is not. 
 A: The notion of instance hardness may address what you are looking for. Instance hardness posits that each instance in a data set has a hardness property indicating the likelihood that it will be misclassified by a supervised learning algorithm. In a sense, instance hardness looks at the hardness of each individual rather than the hardness of the data. However, instance hardness can be aggregated to essentially characterize the the hardness of the data set. As with all aggregation methods, though, some information is lost when the data is aggregated. Hopefully this may give you some direction.
A: Statistical learning theory typically deals with sample complexity, i.e., how many samples do I need to produce a hypothesis having low error with high probability. More concretely, if $S$ is a set of samples and $h_S$ is the hypothesis returned by some learning algorithm when given $S$ as input, then typically one looks to produce statements of the form
$$
P(\text{err}(h_S)\le \epsilon) \ge 1 - \delta
$$
if $|S| \ge m$ for some $m = \text{poly}(1/\epsilon, 1/\delta)$.
In the above we completely ignored how $h_S$ was generated. Computational Learning Theory is the field which deals with these types of computational issues. One may, for example, require the algorithm that produces $h_S$ to run in time $\text{poly}(1/\epsilon, 1/\delta)$, notice that the above is a necessary condition for this to be possible. Other common things studied are what happens if the algorithm has access to different information (membership queries allow the learning algorithm to query an oracle for the label of points it chooses), how many mistakes does a learner make in an online learning, what happens if the feedback is limited like in reinforcement learning, etc. 
There is a lot more and it is a fascinating field, but rather than list them I'll point you to the book An Introduction to Computational Learning Theory by Kearns and Vazirani, which is a great introduction to the subject.
