A novel machine-learning algorithm based on single-shot measurements, named single-shot measurement learning, is demonstrated achieving the theoretical optimal accuracy. The method is at least as efficient as existing tomographic schemes and computationally much less demanding. The merits are attributed to the inclusion of weighted randomness in the learning rule governing the exploration of diverse learning routes. These advantages are explored experimentally by a linear-optical setup that is designed to draw the fullest potential of the proposed method. The experimental results show an unprecedented high level of accuracy for qubit-state learning and reproduction exhibiting (nearly) optimal infidelity scaling, O(N^{-0.983}), for the number N of unknown state copies, down to <10^{-5} without any compensation for experimental nonidealities. Extension to high dimensions is discussed with simulation results.