List of papers on Runtime and Statistical Tradeoffs on Machine Learning I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having more data actually help the algorithms run faster? Or maybe not run faster but yield better results.

Let me give you two papers with such examples:


“SVM Optimization: Inverse Dependence on Training Set Size”, Shalev-Shwartz,
Srebro.


This first example discusses how the runtime of SVM optimization should decrease as the training data increases in a theoretical (and empirical) framework.

A second example:


“More Data Speeds up Training Time in Learning Halfspaces over Sparse Vectors”,
Daniely, Linial, Shalev-Shwartz.


On how we get computational speed ups as data increases when learning halfspaces over sparse vectors.

I was wondering if there were other interesting papers on the same or similar spirit as the two above.
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).