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