A Optimal K-priors for GLMs

We present theoretical results to show that K-priors with limited memory can achieve low gradientreconstruction error. We will discuss the optimal K-prior which can theoretically achieve perfect reconstruction error. Note that the prior is difficult to realize in practice since it requires all past training-data inputs X. Our goal here is to establish a theoretical limit, not to give practical choices. Our key idea is to choose a few input locations that provide a good representation of the training-data inputs X.