The cost of each iteration of RNM scales cubically with the size of the block due to matrix inversion. [1]} demonstrate numerically that for small blocks the optimization time decreases but at some point it starts to increase again. They surmise that the improvement is obtained only as long as the inversion cost is dominated by
the other fixed per-iteration costs such as fetching from memory. However, whether the only possible speedup stems from this has remained unclear. We answer this question for determinantal sampling by deriving the optimal subset size in the case of kernel ridge regression. We show that when the eigenvalue decay is sufficiently rapid, then the gain in convergence rate can dominate the cost of inversion even for larger block sizes.
