Machine learning aims at dealing with uncertainty and making predictions about the future scenarios in the unknown environment. The core idea of coping with such uncertainty, or decision making without knowing the information of future input is very similar to another well-studied field in theoretical algorithm design, i.e. online algorithms with competitive analysis. Specifically, an online algorithm receives an input sequence of items, one at a time. To process each input item one-by-one, an online algorithm must immediately generate an output or make a decision with no idea about the whole input from the beginning. More precisely, online algorithms are somehow more inclined to develop a machine learning model in which new training data is gradually input over time to continuously train the model and further extend the strength of the existing model. This is also similar to the so-called incremental learning model. Another similar direction is the online learning model, which is also a variant of traditional machine learning problems. Online learning algorithms mainly learn from a stream of past events and make a prediction for each element one by one in the stream. Then the algorithm receives immediate feedback on each prediction and uses this feedback to improve its accuracy of subsequent predictions. (more details)