Relationship between structural or statistical properties and hardness of classification I am trying to understand the relationship between structural or statistical properties of training dataset and hardness of classification in the  context of binary classification with SVM using RBF kernel. I would like to predict the hardness without actually trying to classify the dataset. The obvious properties are the size of the dataset and features. What other meta-properties indicate that an SVM using RBF kernel will result in low accuracy and/or extremely expensive computation?
 A: The RBF kernel is local in the feature space, so it can only work well if a nearest neighbour predictor also works fairly well. It is often worth trying Nearest Neighbour first - if its results are dreadful then I question whether I have the right feature set.
But if you are going to use an SVM, it does not feel right to me to start with feature engineering then use assume the RBF is appropriate. Instead, design a problem-relevant kernel function. This will be equivalent to some set of features, by Mercer's Theorem, but what that set is does not really matter - you get the predictions directly by building an SVM with your kernel function.
A: The idea of using properties of a dataset to decide on classifier characteristics is called metalearning
I do not know much about metalearning itself, nor any specific aspects of metalearning for SVMs and classification hardness
A search on Google Scholar points to https://link.springer.com/article/10.1007/s10462-013-9406-y (open access) as a recent and well cited survey of metalearning.
I know of one result on metalearning-like results for SVM: the mean distance between classes is a good heuristic value for the $\gamma$ hyperparameter for the RBF SVM (both behind paywall):

*

*Analysis of the Distance Between Two Classes for Tuning SVM Hyperparameters


*Empirical comparison of cross-validation and internal metrics for tuning SVM hyperparameters
