List of papers on Runtime and Statistical Tradeoffs on Machine Learning
We explored the Runtime-Accuracy tradeoff in the context of nearest neighbors in a 2010 COLT paper [journal version]:
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867374

Roughly speaking, your dataset has margin $\gamma$ if every pair of opposite-labaled points is at least $\gamma$ apart in distance. You can also impose a desired margin by counting the violating pairs as sample error (this is analogous to the SVM setting where it may be advantageous to impose a margin that's bigger than the data margin, at the expense of some violations). Unlike SVM, the metric margin very much affects the algorithmic runtimes. We also have margin-based generalization bounds. Thus, one can answer questions such as: if my runtime is on a certain budget, what sort of accuracy can I expect?

We continued this line of research in last year's NIPS paper:
http://papers.nips.cc/paper/5528-near-optimal-sample-compression-for-nearest-neighbors.pdf

where we showed that the margin also allows for the sample to be compressed (in fact, nearly optimally).