Modern machine learning (ML) processes massive data. The thesis tackles two algorithmic challenges arising from large-scale ML—robustness to noisy training data and memory-efficiency of the learning algorithms. Motivated by the first, I propose (i) the fastest algorithm for learning the mean of high-dimensional heavy-tailed distribution, (ii) a unified analysis framework for robust estimation, and (iii) efficient and robust algorithm for privately estimating high dimensional Gaussian. For memory-efficiency, I give the first sub-linear space algorithm for online prediction, the most classic problem in sequential learning.