  Gaussian Process Regression and Kernel Ridge Regression are popular
nonparametric regression approaches. Unfortunately, they suffer from high
computational complexity rendering them inapplicable to the modern massive
datasets. To that end a number of approximations have been suggested, some of
them allowing for a distributed implementation. One of them is the divide and
conquer approach, splitting the data into a number of partitions, obtaining the
local estimates and finally averaging them. In this paper we suggest a novel
computationally efficient fully data-driven algorithm, quantifying uncertainty
of this method, yielding frequentist $L_2$-confidence bands. We rigorously
demonstrate validity of the algorithm. Another contribution of the paper is a
minimax-optimal high-probability bound for the averaged estimator,
complementing and generalizing the known risk bounds.
