Is this the same as stochastic gradient descent?

The update can coincide, but online timing and regret analysis differ from assumptions about randomly sampled data.

Must losses be independent?

Not in the general online convex formulation, although particular statistical interpretations may assume independence.

Does projection always change the update?

No. A proposed point already inside the feasible set projects to itself.

AI Glossary / Mathematics and optimization / Advanced

Online gradient descent

Definition

Online gradient descent is a method that updates a decision or model using the gradient of the loss revealed after each round. It takes a step against that gradient and, when necessary, projects the result back into the allowed set. Its central challenge is choosing today's decision before knowing today's complete loss information.

What it means

An online learner repeatedly decides, receives feedback, and updates. Unlike fitting one fixed dataset repeatedly, it is evaluated on decisions made as information arrives. The prediction issued before a label becomes available remains part of its performance record, even if the model subsequently improves.

The word “online” describes this timing, not an internet connection. Online gradient descent can operate on a recorded sequence replayed in chronological order. Its relationship to stochastic gradient descent depends on the setting: sampled independent examples give a stochastic interpretation, while online convex optimization can allow a much broader sequence of losses.

How it works

Let w_t be the current decision, C the feasible set, and g_t the gradient of the newly observed loss at w_t. The update is w_(t+1) = projection_C(w_t − η_t g_t), where η_t is a positive learning rate. Projection selects the closest feasible point in the usual Euclidean version.

Feedback must provide enough information to obtain the gradient. Merely observing the reward of one selected action is a different, more restricted feedback problem; it does not automatically reveal the gradient this update needs.

For convex losses, bounded gradients, and a bounded convex feasible set, suitable step sizes give useful regret guarantees. Regret compares cumulative loss with a specified alternative, commonly the best single feasible decision chosen in hindsight. Such a comparison does not mean the learner predicts every outcome correctly or matches the best changing decision at every round.

Three practical examples

1. Demand forecasting: update a linear predictor after the actual demand corresponding to its earlier forecast becomes available.

2. Resource allocation: revise a continuous allocation using the observed gradient of a convex operating-cost model, while projecting onto capacity constraints.

3. Combining advisers: adjust continuous weights assigned to several prediction sources, respecting the requirement that weights are nonnegative and sum to one.

Think of it this way

Think of adjusting a thermostat after observing how uncomfortable the previous setting was. The feedback changes the next setting, and permitted temperature limits restrict the adjustment. This illustrates sequential correction and constraints. Real thermostat dynamics may involve delay, nonlinear effects, and feedback that does not directly reveal a convex-loss gradient, so the analogy is not an automatic control guarantee.

Worked example

Consider a prediction w constrained to [0, 2]. Each round reveals a target y and incurs half the squared error: loss = (w − y)²/2. Its gradient is w − y. Start at w_1 = 0 and use learning rate 1/2.

For target 1, the loss is 1/2 and the gradient is −1. The next prediction is 0 − (1/2)(−1) = 1/2.

For target 3, the loss is (1/2 − 3)²/2 = 25/8. The update gives 1/2 − (1/2)(−5/2) = 7/4, which remains feasible.

For target 0, the loss is (7/4)²/2 = 49/32. The next prediction becomes 7/8. The three incurred losses total 165/32 = 5.15625.

The best fixed prediction in hindsight is the target mean, 4/3, which lies inside the interval. Its cumulative loss is 7/3. Regret is therefore 165/32 − 7/3 = 271/96, approximately 2.823. The final updated prediction is not substituted into earlier rounds. This short, hand-checked illustration demonstrates accounting, not an asymptotic guarantee or an optimal learning-rate choice.

Illustrative case study

Fictional case: Cedar Dispatch updates a demand predictor whenever a completed delivery period supplies its true count. Analysts initially update immediately using provisional counts, then overwrite those counts later. Their evaluation accidentally credits the model with information unavailable at forecast time.

The team rebuilds the replay around actual label-arrival times. It records each forecast before updating, caps permitted parameter changes through its chosen feasible set, and compares cumulative loss with a frozen baseline. It also monitors recent loss because a good comparison with one fixed model can conceal difficulty after a sudden distribution change. No measured company improvement is claimed here.

Common misconceptions and mistakes

A smaller learning rate is not automatically better: it reduces each reaction but can make adaptation slow. Projection is also not arbitrary clipping unless the feasible set makes clipping the correct Euclidean projection.

Do not assume the classical convex regret result applies unchanged to a deep neural network. Nonconvexity, delayed labels, estimated gradients, and changing constraints require their own analysis. Low regret against a fixed comparator also does not establish fairness, calibration, or operational reliability.

Business use

For a business, the useful question is whether feedback arrives soon enough and contains the information needed for meaningful updates. Record the loss, feasible set, gradient construction, step-size schedule, and comparator explicitly. Evaluate in time order, retain a rollback model, and separate the cost of computing an update from the cost of serving a prediction.

Check your understanding

A decision constrained to [0, 2] proposes an updated value of 2.8. What is its Euclidean projection?

Answer: 2, the closest allowed value. This changes the next decision; it does not revise losses already incurred.

Related terms

Learn next

trace a chronological sequence with delayed labels, then study projected gradient descent and the distinction between fixed-comparator regret and tracking a changing comparator.

Sources

Primary source: Martin Zinkevich, “Online Convex Programming and Generalized Infinitesimal Gradient Ascent,” especially the decision timing, assumptions, and greedy-projection update: https://www.cs.cmu.edu/~maz/publications/ICML03.pdf . The original paper was opened and these passages read. This article uses the broader online convex meaning; independent sampling is a special setting. The numerical example and fictional case are original.

Previous: Online expectation maximization Next: Online inference