# what is the simplest possible online learning model / algorithm

Let me define my vernacular here: I'm looking to understand what the simplest online learning algorithm is.

By 'online' I just mean it doesn't have to see all the past observations in order to update its model. When it sees a new observation (or gets feedback that a previous prediction was violated) it updates its model without some large batch processing of data/observations it's already seen.

By simple, I'm not sure exactly what I mean. I mean fewest computational steps I suppose. or easiest to understand...

I thought perhaps some simplest recommender system would qualify as the simplest - hello world - version of online learning but I don't know for sure.

What would you say is the simplest online learning algorithm?

EDIT: someone suggested the averaging algorithm is the simplest possible online learning algorithm as it can be calculated incrementally (as long as you know the current average and number of observations). Allow me to make my question a little more clear. I want a model that learns, not a static algorithm. 'Average' is a calculation, it's an algorithm. A model, in this sense, is distinct from a static algorithm in that it has what you might call internal variables that change based upon what it has seen. It has an internal state. Without 'state', a "model" is just static calculations. There are no 'internal state' or 'hidden variables' or 'weights and biases' to the Averaging calculation. In essence, there is no learning. I know this kind of question is quite general and it's asked in layman terms which doesn't help it be specific. Thank you for your patience.

• I don't think you are correct about averaging. The state at stage (observation) $i$ is $(n_i, S_i)$, where $n_i$ is the number of observations at stage $i$ and $S_i$ is the sum of the observations at stage $i$. The state evolves by $n_{i+1} = n_i + 1$, $S_{i+1} = S_i + X_i$, where $X_i$ is the $i^{th}$ observation. Mar 9, 2020 at 20:59
• @jbowman I stand corrected I guess. Mar 9, 2020 at 21:10
• In the enlarged sense expressed in your edit, one of the simplest possible models is to store the value of the first observation and output that forever after. Because it truly depends on the observations, it "learns;" and under some very broad assumptions about the process, it can work better than any "static process" or procedure that does not respond to the observations at all. I hope this example illustrates why the question "simplest possible" is not likely to lead to interesting or useful answers.
– whuber
Mar 10, 2020 at 10:51