Machine learning tasks are often formulated as complex optimization problems, where the objective function can be non-differentiable, non-continuous, non-unique, inaccurate, dynamic, and have many local optima, making conventional optimization algorithms fail. Evolutionary Algorithms (EAs), inspired by Darwin's theory of evolution, are general-purpose randomized heuristic optimization algorithms, mimicking variational reproduction and natural selection. EAs have yielded encouraging outcomes for solving complex optimization problems (e.g., neural architecture search) in machine learning. However, due to the heuristic nature of EAs, most outcomes to date have been empirical and lack theoretical support, encumbering their acceptance to the general machine learning community. In this paper, I will review the progress towards theoretically grounded evolutionary learning, from the aspects of analysis methodology, theoretical perspectives and learning algorithms. Due to space limit, I will include a few representative examples and highlight our contributions. I will also discuss some future challenges.