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.

• Google forecastability, this seems to be the term you're looking for. – Tim Jan 17 '17 at 10:55

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.

• Very interesting work indeed! – Daniel Dec 5 '13 at 0:05

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.

• Sorry, you misunderstood me. I am talking about the complexity of the data, not the learning algorithm. – Daniel Nov 21 '13 at 22:16
• In SLT people formalize proofs without making any assumptions on from what the distribution the data is coming from, right? – Daniel Nov 21 '13 at 22:26
• What I am saying is that, "are there any formalizing as in SLT, but with some assumption with the underlying distributions"? – Daniel Nov 21 '13 at 22:26
• @Daniel, Sorry about that. There are some results for "learning under the uniform distribution." Is this more like what you're looking for? Based on your edit, I think you might be conflating the distribution and the hypothesis/concept class. – alto Nov 21 '13 at 23:58
• thanks for your comment. Not really. Maybe something like this: nips.cc/Conferences/2013/Program/event.php?ID=3718 "It remains a huge challenge however, to characterize the types of data for which faster learning is possible, to define `easy data' in a generic way, let alone to design algorithms that automatically adapt to exploit it." I mostly meant, the efforts done for characterizing the types of data. – Daniel Nov 23 '13 at 0:33