# 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:

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:

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.

• its highly dataset specific.... – vzn May 8 '15 at 17:00
• @vzn pardon? not sure I understood your comment. – Charlie Parker May 8 '15 at 17:43
• its generally highly algorithm and data dependent. it can be empirically studied & is done so in most ML applications. the 1st paper seems to disregard (individual) iteration time and simply count iterations of the algorithm instead as "training time" which seems is a bit misleading to equate to "run time"... think iteration count is maybe not linearly related to runtime... – vzn May 8 '15 at 17:53

## 1 Answer

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).