<p>We explored the Runtime-Accuracy tradeoff in the context of nearest neighbors in a 2010 COLT paper [journal version]:
<a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867374" rel="nofollow">http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867374</a></p>

<p>Roughly speaking, your dataset has margin $\gamma$ if every pair of opposite-labaled points is at least $\gamma$ apart in distance. You can also <b>impose</b> 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?</p>

<p>We continued this line of research in last year's NIPS paper:
<a href="http://papers.nips.cc/paper/5528-near-optimal-sample-compression-for-nearest-neighbors.pdf" rel="nofollow">http://papers.nips.cc/paper/5528-near-optimal-sample-compression-for-nearest-neighbors.pdf</a></p>

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

CC BY-SA 3.0
2015-05-06T08:19:24.793Z
2015-05-06T08:19:24.793Z
Aryeh
<p>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.</p>

<p>Let me give you two papers with such examples:</p>

<ol>
<li><a href="http://icml2008.cs.helsinki.fi/papers/266.pdf" rel="nofollow">“SVM Optimization: Inverse Dependence on Training Set Size”, Shalev-Shwartz,
Srebro.</a></li>
</ol>

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

<p>A second example:</p>

<ol start="2">
<li><a href="http://papers.nips.cc/paper/4905-more-data-speeds-up-training-time-in-learning-halfspaces-over-sparse-vectors.pdf" rel="nofollow">“More Data Speeds up Training Time in Learning Halfspaces over Sparse Vectors”,
Daniely, Linial, Shalev-Shwartz.</a></li>
</ol>

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

<p>I was wondering if there were other interesting papers on the same or similar spirit as the two above.</p>

CC BY-SA 3.0
2015-05-08T17:00:38.650Z
its highly dataset specific....
vzn
CC BY-SA 3.0
2015-05-08T17:43:21.780Z
@vzn pardon? not sure I understood your comment.
Charlie Parker
CC BY-SA 3.0
2015-05-08T17:53:06.580Z
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
<ds.algorithms><reference-request><machine-learning><big-list>
List of papers on Runtime and Statistical Tradeoffs on Machine Learning
Charlie Parker
# List of papers on Runtime and Statistical Tradeoffs on Machine Learning

(Asked by: username_0 on 2015-05-05)

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.](http://icml2008.cs.helsinki.fi/papers/266.pdf)

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:

2. [“More Data Speeds up Training Time in Learning Halfspaces over Sparse Vectors”,
   Daniely, Linial, Shalev-Shwartz.](http://papers.nips.cc/paper/4905-more-data-speeds-up-training-time-in-learning-halfspaces-over-sparse-vectors.pdf)

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.

**Tags:** ds.algorithms, reference-request, machine-learning, big-list

> **Comments:**
> **username_1**: its highly dataset specific....  
> **username_0**: @username_1 pardon? not sure I understood your comment.  
> **username_1**: 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...  

---

## 1 answers

### Answer by username_2 on 2015-05-06. Score: 1

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


---

