<p>We consider one-shot distributed learning based on the divide-and-conquer strategy by a simple arithmetic averaging of local estimates. The data may be originally stored on multiple machines and thus naturally partitioned, or manually partitioned to alleviate the computational burden. However, either due to the cost of using a large number of machines, or due to that (as is well known in the literature) there is a theoretical limit on the number of partitions one can use beyond which the performances will deteriorate significantly, the local sample size for each partition can still be very large. We use Nyström approximation on each machine/partition to reduce the computational burden of obtaining local estimates, which also facilitates communication of estimates between the machines. However, the open question is whether the optimal rate can still be achieved when Nyström approximation is carried out in a distributed manner. We establish the optimal rate in this setting incorporating <i>both the source condition and the capacity condition</i>, giving an affirmative answer to this question. Some numerical results are reported for illustration.</p>