6 edited tags
5 added 104 characters in body

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 solving machine learning problemsdata (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.

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 have different levels of hardness. Are there any works on formalizing the hardness of solving machine learning problems (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.

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.

4 edited title

# On the hardness of learningdata to learn

3 edited title
2 added 93 characters in body
1