Online Learning: Incremental Updates

The Batch Bottleneck

A UPI fraud-detection model has to answer one question in under 200 milliseconds: is this specific transaction, arriving right now, fraudulent? It cannot say "let me retrain on today's data and get back to you tomorrow." Fraud rings do not wait for tomorrow either. A ring that starts probing small, low-value transactions at 2 a.m. today will shift to daytime, high-value transfers the moment the 2 a.m. pattern starts getting blocked. The distribution the model is trying to learn is not fixed. It is drifting under the model's feet, deliberately, in response to the model itself.

Every model you have built so far in this course, from a decision tree on the Titanic dataset to a feedforward network on MNIST, follows the same recipe: collect a dataset, assume the examples are drawn i.i.d. (independently and identically distributed) from some fixed underlying distribution, run gradient descent over the whole dataset for many epochs, freeze the weights, deploy. This is batch learning, and it has a hard requirement baked into its mathematics: the full training set must be available before a single gradient step happens, and the distribution generating that set must not change between training and deployment.

Both requirements fail for a live UPI stream. You cannot wait for "the full dataset" because transactions never stop arriving; there is no last row. And the distribution of fraud patterns is non-stationary by design, because it is adversarial. Retraining a batch model from scratch every hour on the last hour's data is not just expensive (a fresh pass over millions of rows, each hour, forever); it also throws away everything the model learned in every previous hour, unless you keep re-including old data, which brings back the "wait for it all" problem.

Online learning is the paradigm built for exactly this situation: the model consumes one example at a time, in the order it arrives, updates its parameters immediately using only that example, and is ready to serve the very next prediction with the updated parameters. No epoch, no shuffled pass over a fixed dataset, no waiting.

From Batch Risk Minimization to a Sequential Protocol

You already know the batch objective from your deep learning foundations: empirical risk minimization (ERM). Given a fixed dataset {(x_i, y_i)} for i = 1..N drawn i.i.d. from distribution D, and a loss function L, batch training finds

w* = argmin_w  (1/N) Σ_{i=1}^{N} L(w; x_i, y_i)

Gradient descent computes the true gradient of this sum (or mini-batch SGD approximates it with a random subset) and takes steps toward w*. The theoretical guarantee, "gradient descent converges to a minimizer of the population risk," depends on D being fixed and on being allowed to revisit the data across multiple epochs.

Online learning does not use this framework at all. Instead it is defined as a repeated game played over rounds t = 1, 2, 3, ..., with no assumption that examples are i.i.d. or that any distribution is fixed:

1. The environment reveals a new input x_t (the incoming transaction's features).
2. The model, using its current parameters w_t, must commit to a prediction ý_t before the true label is known.
3. The true label y_t is revealed (the transaction is later confirmed fraud or legitimate, by a chargeback, a user report, or a rules engine).
4. The model suffers loss L(ý_t, y_t) and performs one parameter update to produce w_{t+1}, using only round t's data.
5. Round t's raw data is never revisited. The model moves to round t+1.

This predict-before-you-know protocol, not "small batch size," is the defining feature. It is what makes online learning the right tool for a live stream: each update costs a fixed, small amount of work (one forward pass, one backward pass, one parameter update), completely independent of how many transactions have already been processed. Formally, memory and compute per round are O(d) where d is the number of parameters, never O(N) where N is the size of history.

The Update Rule: Online Gradient Descent

The workhorse update for online learning is a direct sequential analogue of gradient descent, applied to one example instead of a batch. For a model with weight vector w and bias b, learning rate η, and loss L computed on the single example seen at round t:

w_{t+1} = w_t - η · ∇_w L(w_t; x_t, y_t)
b_{t+1} = b_t - η · ∇_b L(w_t; x_t, y_t)

For binary classification with a logistic (sigmoid) output and cross-entropy loss, this gradient has a famously clean closed form. Let z = w · x + b, ý = σ(z) = 1 / (1 + e^{-z}), and L = -[y log ý + (1-y) log(1-ý)]. Differentiating through the sigmoid and the cross-entropy (a derivation you can redo from your neural-network chapter: the sigmoid derivative σ'(z) = σ(z)(1-σ(z)) cancels exactly against the 1/ý(1-ý) that falls out of the cross-entropy derivative) gives:

∇_w L = (ý - y) · x
∇_b L = (ý - y)

So the entire update, per transaction, is: compute the prediction error (ý_t - y_t), a single scalar, and nudge every weight in proportion to that error times the corresponding feature value. This is cheap enough to run on every one of millions of daily transactions with no batching at all.

Worked Trace: Three Transactions, One Evolving Model

Take a deliberately small logistic regression fraud scorer with two features: x1 = transaction amount, z-scored against the user's usual spend, and x2 = hour-of-day, z-scored against the user's usual active hours. A large positive x1 means an unusually large amount; a negative x2 means an unusual hour relative to when this user normally transacts. Initialize w = (0, 0), b = 0, learning rate η = 0.1. Three transactions stream in, in order.

Round 1. x_1 = (2.0, -1.0) (large amount, unusual late-night hour), confirmed fraud, y_1 = 1.

z = 0(2.0) + 0(-1.0) + 0 = 0
ý = σ(0) = 0.5000
error = ý - y = 0.5 - 1 = -0.5000

With no prior knowledge, the model is maximally unsure (probability exactly 0.5), which is the correct starting point for a fresh weight vector of all zeros.

Round 2. x_2 = (-0.3, 0.2) (small, typical amount at a normal hour), legitimate, y_2 = 0. Weights carried in from round 1: w = (0.10000, -0.05000), b = 0.05000.

z = 0.1(-0.3) + (-0.05)(0.2) + 0.05 = -0.03 - 0.01 + 0.05 = 0.01000
ý = σ(0.01) = 0.50250
error = 0.50250 - 0 = 0.50250

Round 3. x_3 = (1.8, 1.5): a large amount, but now at a normal-looking daytime hour, still confirmed fraud, y_3 = 1. This is the fraud ring adapting to avoid the "unusual hour" signal that flagged round 1. Weights carried in: w = (0.11507, -0.06005), b = -0.00025.

z = 0.11507(1.8) + (-0.06005)(1.5) + (-0.00025) = 0.20713 - 0.09008 - 0.00025 = 0.11681
ý = σ(0.11681) = 0.52917
error = 0.52917 - 1 = -0.47083

The full trace, with every quantity independently verified by running the exact update rule in code (below), is:

Watch the w2 column (the weight on hour-of-day): it starts at 0, moves negative (-0.05, then -0.06005) as the model learns "unusual hour correlates with fraud" from round 1, and then flips positive (+0.01057) after round 3, because that round showed fraud at a normal hour. Three updates is nowhere near enough data to trust this number, but the direction of movement is the entire point: the model revised its belief about which feature matters, in one step, using only the one example that contradicted it. A batch model trained once on rounds 1 and 2 would keep predicting "night hour = fraud signal" until someone noticed the accuracy drop and manually triggered a retrain.

The Python below implements exactly this update rule. It was run to produce the numbers in the table above, confirming the hand derivation to five decimal places.

import math

def sigmoid(z):
    return 1 / (1 + math.exp(-z))

class OnlineLogisticRegression:
    def __init__(self, n_features, lr=0.1):
        self.w = [0.0] * n_features
        self.b = 0.0
        self.lr = lr

    def predict_proba(self, x):
        z = sum(wi * xi for wi, xi in zip(self.w, x)) + self.b
        return sigmoid(z)

    def partial_fit(self, x, y):
        ý = self.predict_proba(x)
        error = ý - y
        for i in range(len(self.w)):
            self.w[i] -= self.lr * error * x[i]
        self.b -= self.lr * error
        return ý

stream = [((2.0, -1.0), 1), ((-0.3, 0.2), 0), ((1.8, 1.5), 1)]
model = OnlineLogisticRegression(n_features=2, lr=0.1)

for x, y in stream:
    yhat = model.partial_fit(x, y)
    print(round(yhat, 5), [round(v, 5) for v in model.w], round(model.b, 5))

# Output:
# 0.5     [0.1, -0.05]      0.05
# 0.5025  [0.11507, -0.06005]  -0.00025
# 0.52917 [0.19982, 0.01057]   0.04683

Notice what partial_fit does not do: it never loops over previous examples, never stores the full history, and never needs to know N, the eventual size of the stream. Each call is O(d) in the number of features. That is the property that makes it deployable directly inside a transaction-processing pipeline rather than a nightly batch job.

The Predict-Reveal-Update Loop, and How Drift Shows Up Geometrically

The diagram below shows the five-step loop from the protocol above running forever on the left, and, on the right, what round 3's update actually did to the model's decision boundary in feature space: the line where w · x + b = 0, which separates predicted-fraud from predicted-legitimate. After rounds 1 and 2, the boundary leans one way (tuned to "unusual hour = risk"); the single contradicting example in round 3 swings it to a visibly different orientation.

Regret: How Do You Judge an Online Learner Without a Fixed Distribution?

Batch learning theory measures success by how close the trained weights come to the population risk minimizer, which presupposes a fixed population. Online learning has no such thing to aim at, so it needs a different yardstick, and the standard one is regret. Over T rounds, define

R_T = Σ_{t=1}^{T} L(w_t; x_t, y_t)  -  min_w  Σ_{t=1}^{T} L(w; x_t, y_t)

The first term is the total loss the online model actually suffered, updating its weights round by round as it went. The second term is the total loss the single best fixed weight vector, chosen with hindsight after seeing all T rounds, would have suffered. Regret is the gap between "learning as you go" and "the best you could have done if you'd known the whole stream in advance and picked one fixed model." Crucially, this definition makes no assumption that the x_t, y_t pairs are i.i.d. or stationary; the comparison class is just "any fixed weight vector," which is exactly the right comparison for a fraud model competing against what a perfectly-tuned static model could have achieved on that same, possibly drifting, stream.

The foundational result (Zinkevich, 2003) is that for convex losses with bounded gradients, online gradient descent with a shrinking step size (e.g. η_t ∝ 1/√t) achieves R_T = O(√T). Divide both sides by T: average regret per round is O(1/√T), which goes to zero as T → ∞. In words: the online learner's average per-round performance converges to that of the best fixed model in hindsight, without ever assuming the data came from a stable distribution. This is the theoretical justification for why "just keep updating on every example" is a mathematically sound strategy for a live fraud feed, not merely a computationally convenient hack.

Why Online Learning Exists: Concept Drift

The scenario that makes online learning necessary, rather than merely convenient, is concept drift: the mapping from features to labels changes over time. Round 3 in the worked trace is a miniature example of drift, where P(fraud | hour) flips sign. Real UPI fraud drift is driven by adversaries adapting to whatever the current model flags, by genuinely new attack techniques (SIM-swap fraud looks different from QR-code phishing), and by legitimate behavior shifting too (festival-season spending spikes that look, feature-wise, like anomalies but are not fraud).

A batch model handles drift only by being retrained, which means someone (or some scheduled job) has to detect that performance degraded, assemble fresh labeled data, and push a new model, all of which takes time during which the stale model keeps making the old mistakes. An online model is, by construction, always training on the freshest available signal, so it starts correcting the moment contradicting examples arrive, as round 3 demonstrated: one example moved w2 by more than its entire prior magnitude.

Two refinements sharpen this further, both worth knowing by name even though a full derivation is beyond this chapter. Exponential decay weighting multiplies the learning rate's effective influence of older examples by a factor γ < 1 per round, so a mistake from six months ago has negligible pull on today's weights while yesterday's mistake still matters. Explicit drift detectors (such as ADWIN, the adaptive windowing algorithm) monitor the model's recent error rate statistically and trigger a partial or full parameter reset when the error distribution shifts significantly, rather than relying on the update rule alone to react gradually.

Misconception: "Online Learning Is Just SGD With Batch Size 1"

The update-rule arithmetic in this chapter looks identical to a single step of stochastic gradient descent as you learned it for training a neural network offline, and that similarity misleads many students into treating "online learning" as just a synonym for "SGD with batch size 1." It is not, and the difference is not cosmetic.

When you train a network offline with SGD, batch size 1 or otherwise, you are still solving the ERM problem: you have a fixed, finite dataset, you assume it is a representative i.i.d. sample from some distribution, you shuffle it and pass over it repeatedly across epochs, and your goal is convergence toward the population risk minimizer w*. Batch size 1 there is a computational choice about how the gradient is estimated at each step; the underlying protocol is still "revisit a fixed dataset until convergence."

True online learning, in the sense this chapter defines it, has no fixed dataset to revisit (each example is used exactly once, in arrival order, and then discarded), no i.i.d. assumption (regret is defined against an adversarial or arbitrary sequence, not a stationary distribution), and a predict-before-you-know constraint that offline SGD never faces (a training example's label is always already known when you compute its gradient; a live transaction's fraud label is not known until after the model has already had to decide whether to block it). The correct way to distinguish them: ask whether the model is allowed to see an example's true label more than once, and whether the model must act on x_t before y_t exists. If both answers are "no revisits, must act first," it is genuinely online learning; if the "stream" is actually a shuffled, finite, already-labeled dataset being fed through in chunks, it is offline mini-batch training wearing a different name.

Active Recall

Attempt every question before reading the worked answer beneath it.

1. Why can't a fraud-detection system on a live UPI feed simply run standard batch gradient descent, re-triggered every few minutes?
2. Starting from w = (0.2, -0.1), b = 0.05, η = 0.1, a new transaction x = (1, 1) arrives with true label y = 0. Compute the updated w and b after one online update.
3. State, in your own words, what regret R_T measures, and what an O(√T) regret bound guarantees as T → ∞.
4. Why is online learning specifically suited to environments with concept drift, in a way a once-trained batch model is not?
5. True or false, with justification: "An online learner is mathematically the same thing as an offline neural network trained with SGD at batch size 1."
6. An online fraud model has been running for six months when a festival season causes a sudden, temporary spike in typical transaction amounts. Will its decision boundary adapt instantly? Name one concrete technique to make it adapt faster.

Answers.

1. Batch gradient descent requires a complete pass over the entire accumulated dataset to compute one exact gradient step, which means its cost per update grows with the total amount of data seen so far, and it needs that data assembled and available before it can begin. A live feed never has a "complete" dataset (transactions keep arriving), so there is no point at which batch GD's precondition is satisfied; running it "every few minutes" still means reprocessing an ever-growing history each time, which is both wasteful and increasingly slow, whereas an online update touches only the single newest example and costs a fixed amount of work no matter how much history exists.

2. z = 0.2(1) + (-0.1)(1) + 0.05 = 0.15. ý = σ(0.15) ≈ 0.53743. error = 0.53743 - 0 = 0.53743. Updated weights: w1 = 0.2 - 0.1(0.53743)(1) ≈ 0.14626, w2 = -0.1 - 0.1(0.53743)(1) ≈ -0.15374, b = 0.05 - 0.1(0.53743) ≈ -0.00374.

3. Regret is the gap between the total loss the online model actually accumulated while learning as it went, and the total loss the single best fixed model (chosen with full hindsight of every round) would have accumulated on that same sequence. An O(√T) bound guarantees that average regret per round, R_T/T, goes to zero as T grows, meaning the online learner's long-run average performance approaches that of the best fixed hypothesis in hindsight, with no assumption that the data ever came from a stable distribution.

4. Because its parameters are never frozen: every new example, including ones that contradict the pattern learned from older examples, immediately nudges the weights, so the model's decision boundary tracks whatever the current relationship between features and labels is. A batch model's weights are fixed at deploy time by definition, so once the true relationship shifts away from what was true during training, its predictions degrade silently until someone detects the drop and manually retrains and redeploys it.

5. False. Offline SGD, even at batch size 1, operates on a fixed, already-fully-labeled dataset that is shuffled and typically revisited across multiple epochs, targeting convergence to the ERM minimizer under an i.i.d. assumption. Genuine online learning processes each example exactly once as it arrives live, must commit to a prediction before the true label is available, makes no i.i.d. or stationarity assumption, and is evaluated by regret against the best fixed hypothesis in hindsight rather than by convergence to a population risk minimizer.

6. No, not instantly: each update moves the weights by only η times that single example's gradient, so a handful of festival-season transactions will nudge the boundary but not relocate it in one step, and if the shift is genuinely temporary this gradualness is actually desirable (it prevents the model from overreacting to a few outliers). To make it adapt faster when a real, sustained shift is detected: apply exponential decay weighting so recent examples dominate the effective gradient more than old ones, or add an explicit drift detector (such as ADWIN) that monitors the rolling error rate and triggers either a temporarily raised learning rate or a partial weight reset once it flags a statistically significant change.

Think About It

Think about this: How would you explain online learning: incremental updates to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where online learning: incremental updates is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting online learning: incremental updates to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind online learning: incremental updates, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.