Can Gaussian Process be fit incrementally?
I think with GPR, the computational cost increases on an order of N^3, so the amount of time with more data increases drastically.

I don't think the current version of sklearn's GPR implements the kind of incremental fit you are expecting. With larger data and iterations, I suggest implementing your own version on a GPU or somethings since GPR implementation is not that difficult.