Online learning · machine learning

On this page 8

Online learning is the machine learning paradigm in which a model updates its parameters incrementally, one example or one small batch at a time, as new data arrives in sequence. Instead of fitting once to a fixed training set, the learner makes a prediction, observes the true outcome, suffers a loss, and adjusts immediately, so the model is always a current summary of the stream it has seen.

Within classic machine learning, online learning is the natural choice when data is too large to store, arrives continuously, or changes its statistical behavior over time. It is a training regime rather than a model family: logistic regression, linear SVMs, Naive Bayes classifiers, k-means clustering and even some decision trees all have online variants. In education, the same phrase means distance learning over the internet; that meaning is unrelated and is not covered here.

How the online update loop works

Online learning works as a repeated predict, observe, update cycle. At round t the learner receives an input, outputs a prediction with its current parameters, then receives the label and computes a loss. A single update rule moves the parameters in a direction that would have reduced that loss, and the example can then be discarded.

The most common update rule is online stochastic gradient descent, where the weights move by the learning rate multiplied by the gradient of the loss on the latest example. Because each step uses one sample, memory cost is constant and the time per update scales only with the number of features, not with the history of the stream.

The table below shows the components of one update round and what each contributes.

ComponentRole in the updateTypical choice
Incoming exampleSupplies the features for one roundOne record or a mini-batch of 1 to 512
PredictionOutput of the current model before the label is knownProbability, score or class
Loss functionMeasures the error on that exampleLog loss, hinge loss, squared error
Learning rateControls the size of each stepFixed, decaying or adaptive
Parameter updateAdjusts weights toward lower lossGradient step, often with regularization
Components of a single online update

Theoretical guarantees and the notion of regret

Online learning is analyzed through regret, the gap between the cumulative loss of the learner and the cumulative loss of the best fixed model in hindsight. A good algorithm has regret that grows sublinearly with the number of rounds, which means its average loss per round converges to that of the best fixed model.

For convex losses, online gradient descent with a step size proportional to one over the square root of t achieves regret on the order of the square root of T; with strongly convex losses the bound improves to the logarithm of T. These guarantees hold even when the data is chosen adversarially, which is why the framework is called online convex optimization. Methods such as follow the regularized leader, the perceptron, passive-aggressive algorithms and multiplicative weights all fit this framework.

Online learning compared with batch and mini-batch training

Online learning differs from batch learning mainly in when and how often the model changes. Batch training reads the full dataset, often many times, and produces a frozen model; online training never revisits old data and never stops adapting. Mini-batch training sits between them and is the standard regime for deep networks.

PropertyBatch learningMini-batch trainingOnline learning
Data accessEntire dataset availableDataset revisited in chunksSingle pass over a stream
Memory useGrows with data sizeBounded per batchConstant
Model freshnessStale until retrainedStale until retrainedUpdated after every example
Sensitivity to orderNoneLow with shufflingHigh
Typical accuracy on static dataHighestClose to batchSlightly lower without multiple passes
Training regimes side by side

Online learning is also distinct from incremental learning in the broader sense, which may retrain periodically on accumulated data, and from continual learning in neural networks, which focuses on avoiding the loss of earlier skills. The shared concern of all three is concept drift, the change of the data distribution over time.

Algorithms with established online variants

Many classic algorithms have well-studied online forms, and the choice depends on the task and the speed of the stream. The next table lists common options.

TaskOnline algorithmKey property
Binary classificationOnline logistic regressionCalibrated probabilities, cheap updates
Large-margin classificationPassive-aggressive classifierUpdates only when the margin is violated
Click predictionFTRL-ProximalProduces sparse weights with L1 regularization
ClusteringSequential k-meansMoves the nearest centroid toward each point
Classification on streamsHoeffding treeSplits once enough evidence has accumulated
Text classificationOnline Naive BayesUpdates word counts in place
Common online algorithms by task

Ensemble methods also adapt: online bagging replaces bootstrap sampling with Poisson-weighted updates, and adaptive random forests replace trees whose accuracy degrades. These designs keep the benefits of ensemble learning without storing the stream.

Configuring an online learner in production

Configuring an online learner means choosing a learning rate schedule, a validation method and a drift policy. Standard cross-validation does not fit a stream, so practitioners use progressive validation, also called prequential evaluation, in which each example is first used for testing and then for training.

SituationRecommended choiceReason
Stable distributionDecaying learning rateConverges toward the best fixed model
Gradual driftConstant small learning rateKeeps the model responsive to recent data
Sudden driftDrift detector with resetDetectors such as ADWIN or DDM trigger relearning
Very many sparse featuresPer-coordinate adaptive ratesRare features receive larger steps
Features on different scalesRunning mean and variance scalingFeature scaling must also be online
Decision guide for common configuration choices

Preprocessing must follow the same rule as the model: every transformation has to be incremental. One-hot encoding needs a policy for unseen categories, often feature hashing, and feature scaling must use running statistics rather than values computed on a full dataset.

Limitations and common mistakes

The main weakness of online learning is its sensitivity to noise, order and bad data. Because every example changes the model immediately, a burst of mislabeled or malicious records can shift predictions within minutes, a risk known as data poisoning.

  • Learning rate too high: the model oscillates and forgets useful patterns after a few unusual examples.
  • Learning rate too low: the model reacts to drift so slowly that it behaves like a stale batch model.
  • Non-shuffled input: streams sorted by time or class produce biased intermediate models.
  • Delayed labels: outcomes such as fraud confirmation may arrive days later, so updates must be joined to the correct predictions.
  • Missing safeguards: production systems usually keep a shadow model and rollback snapshots to recover from sudden degradation.

The simple explanation

Online learning is a way for a computer model to keep learning while it works. A traditional model studies a large pile of examples once and then stops. An online model looks at each new example as it arrives, checks how wrong its guess was, and adjusts a little straight away.

It is similar to a driver who corrects the steering wheel constantly rather than planning the whole route in advance. The benefit is that the model stays current when the world changes. The cost is that it can also be pushed off course by a run of unusual or wrong examples, so it needs careful settings and monitoring.

How it is used in practice

A mid-sized online advertising platform serves about 50 million ad impressions per day and must predict the probability of a click for each one. Retraining a batch model every night left it up to 24 hours behind new campaigns, so the team switched to online logistic regression trained with FTRL-Proximal on hashed features, updating the weights as soon as each click or non-click is logged.

The team evaluates the model with progressive validation, tracking log loss over a sliding one-hour window, and stores a weight snapshot every 15 minutes. When a holiday campaign changed user behavior sharply, the online model adapted within hours, while the old nightly model would have waited a full day. Calibration error on new campaigns fell noticeably, and a drift alarm with automatic rollback protected the system from a bot traffic spike that otherwise would have corrupted the weights.