Abstract: Fast and accurate magnitude estimation is essential for earthquake early warning system(EEWs). The magnitude estimation methods based on a single characteristic parameter of  the initial wave is widely used in EEWs. However, the empirical formula of magnitude established by a single characteristic parameter cannot sufficiently utilize information related to the magnitude in the first arrival wave, which greatly limits the effectiveness of magnitude estimation. this study has proposed a new approach (GPR-M) based on Gaussian process regression to estimate magnitude that includes 10 characteristic parameters in the time domain, frequency domain, and time-frequency domain of initial wave. GPR-M is trained and tested using a large number of surface strong earthquake records in Japan, and compared with the maximum predominant period τ^p_max method and the peak displacement P_d method. The results show that the accuracy of GPR-M is significantly better than τ^p_max and P_d in estimating magnitude with and without hypocentral distance in both cases. In addition, the generalization ability test of GPR-M trained by Japanese data using Chile's surface strong motion records shows that GPR-M has better generalization ability than τ^p_max and P_d. GPR-M can effectively improve the accuracy of magnitude estimation for EEWs without being affected by regional differences..