2
$\begingroup$

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:

  1. “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:

  1. “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.

Improve this question
$\endgroup$
3
  • $\begingroup$ its highly dataset specific.... $\endgroup$
    – vzn
    May 8, 2015 at 17:00
  • $\begingroup$ @vzn pardon? not sure I understood your comment. $\endgroup$
    – Charlie Parker
    May 8, 2015 at 17:43
  • $\begingroup$ 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... $\endgroup$
    – vzn
    May 8, 2015 at 17:53

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.