In mobile cloud computing (MCC), offloading compute-intensive parts of a mobile application onto the cloud is an attractive method to enhance application performance. To make good offloading decisions, history-based machine-leing techniques are proposed to predict application performance under various offloading schemes. However, the data sparsity problem is common in a realistic MCC scenario but is rarely the conc of existing work. In this paper, we employ a two-phase hybrid framework to predict performance for cloud-enhanced mobile applications, which is designed to be robust to the data sparsity. By training several multi-layer neural networks with historical execution records, the first phase automatically predicts some intermediate parameters for each execution of an application. The models leed by these neural networks can be shared among different applications, thus alleviating the data sparsity. Based on these predicted intermediate parameters and the application topology, the second phase deterministically calculates the estimated values of the performance metrics. The deterministic algorithm can partially guarantee the prediction accuracy of newly published applications even with no execution records. We evaluate our approach with a cloud-enhanced object recognition application and show that our approach can precisely predict the application performance and is robust to data sparsity.