Why doesn't classifier accuracy increase linearly with k in k-fold validation? I am experimenting with WEKA and I'm trying to understand the impact of k in cross-fold validation.  It seems reasonable to me that the higher k is, the more accurate the classifier will be (with respect to the train/test data, that is).  
This doesn't seem to be the case when I am varying that parameter.  Why not?
 A: k-fold cross classification is about estimating the accuracy, not improving the accuracy.  Increasing the k can improve the accuracy of the measurement of your accuracy (yes, think Inception), but it does not actually improve the original accuracy you are trying to measure.
Most implementations of k-fold cross validation give you an estimate of how accurately they are measuring your accuracy: such as a Mean and Std Error of AUC for a classifier.  If the Std Error of your AUC estimate is large compared to the difference in your Mean AUC between a couple models or hyper-parameter choices then you probably haven't increased k enough.
A common alternative to increasing the k would be to do repeated cross validation where the stratification is repeated with different random samplings.  It should reach similar conclusions.  From a theoretical point of view, increasing your k a lot gets you closer to a true AIC, and repeating the sampling a lot gets you closer to a true BIC.  There's seldom an absolute reason to believe one to be better than the other.
In some automated frameworks like WEKA, you might be using the k-fold cross validation to choose a hyper-parameter: let's say the amount of ridge in a ridge regression.  As long as k is large enough, the estimated ridge parameter should already be near optimal.  Increasing the k will not give you material gains in accurately estimating the ridge parameter.  It is possible that if k is too small and your training data is too small, that increasing k would give you a better estimate of the truly optimal ridge parameter, but there is a natural limit that will be quickly approached.
It is also true that the estimated accuracy from k-fold cross validation on your training set will not always match the resulting accuracy on a validation set.  Often times the sets are different in some way.  Other times you've tortured the training set by trying 3-4 machine learning techniques and picked the "best" one, as judged by k-fold cross validation.  Due to random chance that best method will almost always have over-performed on the training set.
