Coronavirus disease (COVID-19) has rapidly become a global health concern after its first known detection in December 2019. As a result, accurate and reliable advance warning system for the early diagnosis of COVID-19 has now become a priority. The detection of COVID-19 in early stages is not a straightforward task from chest X-ray images according to expert medical doctors because the traces of the infection are visible only when the disease has progressed to a moderate or severe stage. In this study, our first aim is to evaluate the ability of recent state-of-the-art Machine Learning techniques for the early detection of COVID-19 from chest X-ray images. Both compact classifiers and deep learning approaches are considered in this study. Furthermore, we propose a recent compact classifier, Convolutional Support Estimator Network (CSEN) approach for this purpose since it is well-suited for a scarce-data classification task. Finally, this study introduces a new benchmark dataset called Early-QaTa-COV19, which consists of 175 early-stage COVID-19 Pneumonia samples (very limited or no infection signs) labelled by the medical doctors and 1579 samples for control (normal) class. A detailed set of experiments shows that the CSEN achieves the top (over 98.5%) sensitivity with over 96% specificity. Moreover, transfer learning over the deep CheXNet fine-tuned with the augmented data produces the leading performance among other deep networks with 97.14% sensitivity and 99.49% specificity.