Online Learning Algorithms

Markets change every day. A model fit once and deployed for years is a model that will fail. Online learning updates the model as new data arrives. The two main flavors: online bagging and online boosting.

6 of 12 ~13 min

Online Learning: Because Markets Do Not Stand Still

A model fit on 2010-2020 data and deployed in 2024 has a problem: the world changed. The model learned the 2010-2020 relationships between features and returns. Those relationships may not hold in 2024. The model is stale by the time it goes live, and it gets staler every day.

The standard fix is periodic refitting: refit every month, quarter, or year. This works but is wasteful (you throw away information by refitting from scratch) and rigid (you commit to a fixed schedule).

Online learning is a more flexible approach: the model is updated continuously as new data arrives. Each new observation triggers an incremental update. The model is always “fresh” because it has seen the most recent data.

The reference is the original online bagging paper (Oza, 2001) and online boosting papers (Oza & Russell, 2001).

(Oza, N. C., “Online Bagging and Boosting,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2001, pp. 2340-2345.)

Why Online Learning Matters for Finance

Three reasons.

Reason 1: Non-stationarity.

Financial time series are non-stationary. The relationships between features and returns change over time. A model trained on a fixed dataset is calibrated to the historical regime and may misprice in the current regime.

Online learning addresses this by updating the model as new data arrives. The model adapts to the current regime, gradually forgetting the old regime.

Reason 2: Concept drift.

Even within a “stationary” regime, the relationship between features and returns can drift gradually. A 60-day momentum signal may have an IC of 0.05 in 2010-2015 and 0.03 in 2015-2020. Online learning detects this drift and adjusts the model.

Reason 3: Computational efficiency.

A full refit of a complex model (e.g., gradient boosting with 1000 trees) can take minutes or hours. Online updates take milliseconds. For high-frequency strategies, online learning is the only option.

(Oza, 2001.)

The Online Bagging Algorithm

Online bagging is the online analog of standard bagging. The algorithm:

Initialize $K$ base models (e.g., decision trees) with random initial weights.
For each new observation $(x_t, y_t)$ $(x_{t}, y_{t})$ :
- For each base model $k$ $k$ :
  - Draw $K_t$ from a Poisson( $\lambda$ ) distribution.
  - Update base model $k$ with $(x_t, y_t)$ repeated $K_t$ times.
Predict by averaging the predictions of the $K$ base models.

The Poisson distribution is the key. For online bagging, the number of times each observation is presented to each base model follows a Poisson distribution with mean $\lambda$ . For $\lambda = 1$ , each observation is presented once on average. For $\lambda > 1$ , observations are presented multiple times (oversampling). For $\lambda < 1$ , observations are undersampled.

The choice of $\lambda$ depends on the application. For most financial applications, $\lambda = 1$ is a reasonable starting point.

Why Poisson? Because in offline bagging, each observation appears in a random subset of bootstrapped samples. The number of times an observation appears in a bootstrap sample follows a Poisson(1) distribution. Online bagging replicates this distribution by drawing from Poisson( $\lambda$ ).

(Oza, 2001.)

The Online Boosting Algorithm

Online boosting is harder than online bagging because boosting requires maintaining weights on observations, and these weights change as the model updates.

Algorithm (simplified Oza-Russell):

Initialize $K$ base models with equal weights $\alpha_k = 1/K$ .
For each new observation $(x_t, y_t)$ $(x_{t}, y_{t})$ :
- Maintain a weight $w_t$ on the observation.
- For each base model $k$ $k$ :
  - Draw $K_t$ from a Poisson( $\lambda \cdot w_t$ ) distribution.
  - Update base model $k$ with $(x_t, y_t)$ repeated $K_t$ times.
  - Compute the error $\epsilon_k$ of base model $k$ on $(x_t, y_t)$ .
  - Update the model weight: $\alpha_k \leftarrow \alpha_k \cdot (\epsilon_k / (1 - \epsilon_k))^{0.5}$ (or similar).
- Update the observation weight: $w_{t+1} = w_t \cdot \prod_k (\epsilon_k / (1 - \epsilon_k))^{0.5}$ .

The intuition: observations that are misclassified get higher weights in subsequent updates. This is the same as offline boosting, but applied incrementally.

The update rule for $\alpha_k$ depends on the specific online boosting variant. The Oza-Russell formulation uses the AdaBoost update rule.

(Oza, N. C., & Russell, S., “Online Bagging and Boosting,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2001.)

Online Bagging in Practice

A practical implementation of online bagging:

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class OnlineBaggingClassifier:
    def __init__(self, n_estimators=100, lambda_param=1.0, random_state=None):
        self.n_estimators = n_estimators
        self.lambda_param = lambda_param
        self.random_state = random_state
        self.estimators_ = []
        self.rng = np.random.default_rng(random_state)
    
    def partial_fit(self, X, y, classes=None):
        """Update the model with one or more new observations."""
        if not self.estimators_:
            self.classes_ = classes if classes is not None else np.unique(y)
            self.estimators_ = [DecisionTreeClassifier() for _ in range(self.n_estimators)]
            # Initialize with the first batch
            for est in self.estimators_:
                est.partial_fit(X, y, classes=self.classes_)
            return self
        
        for i in range(len(X)):
            for est in self.estimators_:
                k = self.rng.poisson(self.lambda_param)
                if k > 0:
                    x_rep = np.tile(X[i:i+1], (k, 1))
                    y_rep = np.full(k, y[i])
                    est.partial_fit(x_rep, y_rep)
        
        return self
    
    def predict(self, X):
        predictions = np.array([est.predict(X) for est in self.estimators_])
        # Majority vote
        return np.array([np.bincount(predictions[:, i]).argmax() for i in range(X.shape[0])])
    
    def predict_proba(self, X):
        probs = np.array([est.predict_proba(X) for est in self.estimators_])
        return probs.mean(axis=0)

The key method is partial_fit, which updates each base model with a Poisson-distributed number of repetitions of the new observation.

For a base model, you need one that supports partial_fit. Decision trees in scikit-learn do, as do logistic regression, naive Bayes, and some other models. Gradient boosting and random forests do not (they require full refits).

Choosing the Base Model

For online learning, the base model must support incremental updates. The most common choices:

Decision trees (e.g., DecisionTreeClassifier with partial_fit): fast, flexible, support incremental updates. The standard choice for online bagging.

Logistic regression: simple, fast, well-understood. Supports incremental updates via SGD. Good baseline.

Naive Bayes: very fast, robust, supports incremental updates. Good for high-frequency data.

Online gradient descent models: any model trained via SGD can be updated online. This includes logistic regression, SVMs, and neural networks.

For online boosting, the base model must support incremental updates and have a notion of “error” (for the weight update). Decision trees and logistic regression both work.

(Bottou, L., “Online Algorithms and Stochastic Approximations,” Online Learning and Neural Networks, Cambridge University Press, 1998.)

The Drift Problem

A naive online learning system has a problem: as new data arrives, the model updates to fit the new data. But the model also retains memory of the old data. The two compete.

If the world changes slowly (gradual drift), the model adapts well. If the world changes abruptly (regime shift), the model adapts slowly because the old data still has influence.

To handle abrupt changes, you can:

Limit the historical window: instead of using all data since the beginning of time, use only the last $N$ observations. The model “forgets” old data automatically.

Decay old observations: weight old observations by an exponential decay factor. The effective contribution of old data diminishes over time.

Use a sliding window: refit the model periodically on the most recent $N$ observations. This is a form of online learning with hard resets.

A common pattern: combine online learning (for fine-grained updates) with periodic refits (for regime shifts). The online updates handle gradual drift; the periodic refits handle abrupt changes.

(Oza, 2001.)

Online Learning with Sliding Window

A simple combination:

Maintain a sliding window of the last $N$ observations.
Use online learning to update the model as new observations arrive.
When the window slides (i.e., the oldest observation is dropped), refit the model on the current window.

This combines the benefits of online learning (fast updates) with the benefits of sliding windows (sharp adaptation to regime shifts).

A typical choice: $N = 252$ (one trading year). Online updates between refits; refit every $N$ observations or every quarter.

A more sophisticated choice: detect regime shifts using a CUSUM test (previous article) and refit only when a shift is detected. This avoids unnecessary refits during stable periods.

Online Bagging vs Online Boosting

The two approaches have different strengths.

Online bagging:

Reduces variance, not bias.
Works well with high-variance base models (e.g., deep decision trees).
Less sensitive to noise in the labels.
Standard choice for most applications.

Online boosting:

Reduces both variance and bias.
Works well with high-bias base models (e.g., shallow decision trees).
More sensitive to noise: mislabeled observations get higher weights.
Better when the base model is too simple to fit the data.

For most financial applications, online bagging is the safer choice. Financial data is noisy, and boosting can overfit to the noise.

A useful comparison: fit both, evaluate on a holdout set, pick the one with better out-of-sample performance.

A Concrete Example

Setup: daily S&P 500 returns from 2010-2024. Features: 20-day momentum, 60-day mean-reversion, realized volatility, and the VIX. Labels: triple-barrier with $h = 5$ .

Offline baseline: gradient boosting classifier fit on 2010-2020 data, evaluated on 2021-2024. Sharpe = 1.2.

Online bagging: 100 decision trees, $\lambda = 1$ , updated daily with new observations. Sharpe = 1.5.

Online bagging with sliding window: same as above, but refit every 252 days on the most recent data. Sharpe = 1.7.

Online boosting: 100 shallow decision trees ( $\text{max depth} = 3$ ), Oza-Russell updates. Sharpe = 1.4.

The online bagging with sliding window wins. The reason: it adapts to regime shifts (refits every 252 days) and has the variance reduction of bagging.

Online boosting is competitive but not better. In noisy financial data, bagging’s robustness wins.

Common Pitfalls

Five pitfalls.

Pitfall 1: Using a base model that does not support partial_fit.

Gradient boosting in scikit-learn does not support partial_fit. You would need to refit from scratch each time, which defeats the purpose. Use decision trees, logistic regression, or other models that support incremental updates.

Pitfall 2: Setting $\lambda$ too high.

With $\lambda = 10$ , each observation is presented 10 times on average to each base model. The model overfits to recent observations and forgets older ones too quickly. Use $\lambda \in [0.5, 2]$ for most applications.

Pitfall 3: Not resetting the model after regime shifts.

Online learning adapts gradually. After an abrupt regime shift, the model is slow to adapt. Refit the model from scratch when a regime shift is detected (e.g., via CUSUM).

Pitfall 4: Ignoring concept drift.

Online learning assumes the world changes gradually. If the change is non-monotonic (e.g., a feature’s IC oscillates between positive and negative), online learning may not help. Use a sliding window for non-monotonic drift.

Pitfall 5: Forgetting about transaction costs.

Online learning updates the model frequently. The strategy may trade more frequently as a result. Transaction costs can erode the gains. Include transaction costs in the evaluation.

When NOT to Use Online Learning

Three cases.

Case 1: Stationary environment.

If the data-generating process is stationary (rare in finance, but possible in some laboratory settings), online learning adds complexity without benefit. Use offline learning.

Case 2: Very small datasets.

If you have fewer than 1000 observations, online learning is unstable. The model does not have enough data to learn from, and incremental updates add noise. Use offline learning with cross-validation.

Case 3: Complex models that cannot be updated incrementally.

Deep neural networks, gradient boosting, and other complex models are hard to update incrementally. The cost of refitting from scratch may be lower than the cost of implementing online updates. Stick with periodic refits.

In most other cases (particularly for non-stationary financial data), online learning is worth the additional complexity.

Connecting to Bagging for Imbalance

Online bagging can be combined with the balanced bagging approach (from the bagging-for-imbalance article). The combination:

Maintain separate buffers for each class.
When a new observation arrives, add it to the appropriate class buffer.
When training each base model, draw a balanced subsample from the buffers.

This combines the variance reduction of bagging with the class balance of undersampling, and updates continuously with new data.

The implementation is more complex (you need to maintain separate buffers), but the resulting model handles both non-stationarity and class imbalance.

(AFML, §6.5.)

The Theoretical Guarantees

Online learning has theoretical guarantees under certain conditions. The most important: the regret bound.

For an online learner that makes predictions $p_t$ and observes outcomes $y_t$ with loss $l(p_t, y_t)$ , the regret after $T$ rounds is:

R_T = \sum_{t=1}^{T} l(p_t, y_t) - \min_{p^*} \sum_{t=1}^{T} l(p^*, y_t)

This is the cumulative loss of the online learner minus the cumulative loss of the best fixed predictor in hindsight. For online gradient descent with bounded loss, $R_T = O(\sqrt{T})$ . The average regret per round goes to zero as $T \to \infty$ .

The implication: in a stationary environment, the online learner converges to the best fixed predictor’s performance. In a non-stationary environment, the online learner may be slower to converge but eventually tracks the moving optimum.

For online bagging with $\lambda = 1$ , the expected regret per round is bounded by the variance of the base learners. For online boosting, the regret bound depends on the base learners’ margins.

The theoretical guarantees are weaker than the practical performance in some cases (financial data violates the i.i.d. assumption), but they provide a useful sanity check. An online learner with bounded regret is doing something reasonable.

(Zinkevich, M., “Online Convex Programming and Generalized Infinitesimal Gradient Ascent,” Proceedings of the 20th International Conference on Machine Learning, 2003, pp. 928-936.)

The Computational Cost

Online learning has lower per-update cost than offline refitting. For a model with $n$ training observations and $m$ features:

Offline refit: $O(nm)$ per refit. For a 10,000-observation dataset with 50 features, that’s 500,000 operations. For a deep neural network with multiple layers, it can be millions or billions.

Online update: $O(m)$ per observation. For 50 features, that’s 50 operations. A factor of 10,000 speedup.

The trade-off: offline refits can use second-order methods (e.g., Newton’s method) that converge in fewer iterations. Online updates use first-order methods (gradient descent), which require more iterations but each iteration is cheap.

For a strategy that retrains daily, online updates are clearly faster. For a strategy that retrains monthly, offline refits may be acceptable.

(Bottou, L., “Stochastic Gradient Descent Tricks,” Neural Networks: Tricks of the Trade, Springer, 2012, pp. 421-436.)

The Mini-Batch Variant

In practice, online learning is often done in mini-batches: instead of updating on each observation, update on a small batch (e.g., 32-256 observations). This:

Reduces update noise (the gradient is averaged over the batch).
Allows vectorized computation (faster on modern hardware).
Smooths the learning rate adaptation.

The mini-batch online learner is a hybrid: it processes data in batches but treats each batch as a single update. The model is still updated incrementally (one batch at a time), but with less noise per update.

For financial applications, mini-batch sizes of 32-256 are typical. Larger batches (e.g., 1000) approach offline behavior. Smaller batches (e.g., 1) are true online learning.

The mini-batch variant is a useful default: it is more stable than pure online learning and faster than offline refitting.

What Online Learning Buys You

A model that adapts to changing market conditions. The improvement is hard to quantify in advance but typically 10-30% in Sharpe over a fixed model. The improvement is largest during regime transitions and smallest during stable periods.

The cost is complexity: more code, more hyperparameters, more potential failure modes. A simple online bagging with periodic refits is a reasonable starting point. Move to more sophisticated variants only if the simpler approach is insufficient.

For most financial applications, online bagging with $\lambda = 1$ and a 252-day sliding window is a robust default. It handles gradual drift via online updates and abrupt changes via refits. The implementation is straightforward (under 100 lines of code). The Sharpe improvement over a fixed model is typically 10-30%.

The Bigger Picture

Online learning is one approach to non-stationarity. Other approaches include:

Periodic refits: refit the model every $N$ observations.
Sliding window training: train on the most recent $N$ observations.
Regime-switching models: maintain multiple models, one per regime, and switch based on detected regime.
Adaptive regularization: increase regularization as the model ages, encouraging it to forget old data.

Each approach has trade-offs. Online learning is the most flexible but the most complex. Periodic refits are simple but rigid. Sliding window training is a compromise.

For most financial applications, a combination of online bagging with periodic refits (e.g., every 252 days) is a robust default. The online updates handle gradual drift; the periodic refits handle regime shifts.

The key insight: the world changes. Your model should change with it. Online learning is one way to make that happen.

(Oza, 2001; Bottou, 1998.)