Online Gradient Descent

The Perceptron can be placed inside the Online Gradient Descent framework.

Programming

The Online Learning Loop

Online Gradient Descent is a repeated prediction-and-update process for online convex learning problems. At the beginning of round t, the learner has a current hypothesis w(t) and uses it to make a prediction. The learner then receives the round's data item, forms a loss function for that round, selects a subgradient, and updates the hypothesis before the next round.

How do prediction, round-specific loss, subgradient, and hypothesis update occur in sequence during one iteration?

Initialization and Update

Online Gradient Descent starts with the zero hypothesis, w(1) = 0. For a sequence of round-specific functions f₁ through fᵀ, the general update is w(t+1) = w(t) − ηvₜ, where η is positive and vₜ is the subgradient selected for round t. In the Perceptron analysis, the hypothesis class is all vectors in Rᵈ, so the projection step is vacuous.

Formula

The Perceptron update has the form w(t+1) = w(t) − vₜ. The source explains that this is equivalent to the Online Gradient Descent form for every η greater than zero. This equivalence lets the Online Gradient Descent theorem be used in the Perceptron analysis.

From Loss to Perceptron Update

The Perceptron is analyzed by selecting a surrogate loss function for the current online round and then using its subgradient in the update. The selected subgradient is vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0] yₜxₜ. The indicator is active when the current example satisfies yₜ⟨w(t), xₜ⟩ ≤ 0, so the subgradient contains the labeled example direction yₜxₜ on that condition. Substituting this subgradient into w(t+1) = w(t) − vₜ gives the Perceptron update.

Formula

Formula, step by step

1
Start with the current hypothesis w(t).
2
Evaluate the current example through yₜ⟨w(t), xₜ⟩.
3
Use the round-specific loss to select vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0] yₜxₜ.
4
Subtract vₜ from w(t) to obtain the next hypothesis.

How does the loss incurred on a particular example produce the Perceptron subgradient and determine the direction and size of the update?

Correct Rounds and Convexity

Convexity matters because the Perceptron is being analyzed through Online Gradient Descent. On a round where the Perceptron is correct, the selected surrogate loss fₜ is convex and evaluates to zero at the current hypothesis: fₜ(w(t)) = ℓ(w(t), (xₜ, yₜ)) = 0. Thus, the correct-round case supplies a convex surrogate whose value at the current hypothesis is zero.

Why does convexity combine with a zero current loss on a correct round in the Perceptron analysis?

Two Update Steps

The algorithm's two update expressions should be read separately. First, the current hypothesis and the selected subgradient produce an intermediate Online Gradient Descent update, w(t+1) = w(t) − ηvₜ. Second, the algorithm performs the stated selection over the hypothesis class H for the next-round choice. In the Perceptron analysis, H consists of all vectors in Rᵈ, so the projection step is vacuous. The first step changes the current vector using the round's subgradient; the second describes how the next hypothesis is selected within H.

What changes in the intermediate hypothesis and in the next-round hypothesis at each of the algorithm's two update steps?

Symbolic Round Trace

Worked example

One Symbolic Iteration

Trace one round of Online Gradient Descent when the learner begins with w(t), receives z(t), and obtains subgradient v(t).

1
Prediction
Use the hypothesis available at the start of the round, w(t), to make the prediction.
2
Receive data
After the prediction, receive the round's data item z(t).
3
Form the loss
Use z(t) to construct the loss function for the current round, f(t).
4
Select a subgradient
Obtain the current subgradient v(t) from the round-specific loss.
5
Intermediate update
Apply the Online Gradient Descent update w(t) − ηv(t).
6
Select over H
Use the algorithm's second update step to select the next hypothesis over H.

Result

The dependency order is prediction, data receipt, loss formation, subgradient selection, intermediate update, and selection over H.

How does Online Gradient Descent receive an example, make a prediction, observe the outcome, and adapt its hypothesis before the next round?

Regret Against H

Online Gradient Descent is designed to solve online convex learning problems while adapting after each round. Its theoretical guarantee is stated as a regret bound that holds for every w⋆ in H. The important quantifier is every: the statement is not limited to one specially chosen competitor. It provides a comparison guarantee for each fixed competing hypothesis in the hypothesis class.

How does the cumulative loss of Online Gradient Descent compare with the cumulative loss associated with any fixed competing hypothesis in H over many rounds?

Common Tracing Mistakes

Common mistake
Using the newly received example to define the prediction that was already made.
What it looks like
Treating z(t) as available before the round-t prediction.
Why it fails
The prediction uses the value available at the start of the round. The data item is received afterward.
Do this instead
Write the order as prediction, data receipt, loss formation, subgradient selection, and update.
Common mistake
Using one identical surrogate loss for every online round.
What it looks like
Assuming the same loss function must be used for all examples.
Why it fails
The online analysis permits a round-specific surrogate loss fₜ.
Do this instead
Index the current loss by t and construct it from the current round's data.
Common mistake
Leaving the Perceptron subgradient separate from Online Gradient Descent.
What it looks like
Writing vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0] yₜxₜ but not connecting it to the update.
Why it fails
The subgradient is the quantity used in the Online Gradient Descent update.
Do this instead
Substitute vₜ into w(t+1) = w(t) − vₜ to see the Perceptron form.
Common mistake
Treating the two update steps as one unexplained operation.
What it looks like
Jumping directly from w(t) to w(t+1) without identifying the intermediate update and selection over H.
Why it fails
The source emphasizes that the two update expressions must be traced separately.
Do this instead
First apply the subgradient update, then account for selection over the hypothesis class.

Practice Trace

MEDIUM

Write the six stages of one symbolic Online Gradient Descent round in order. Include the current hypothesis, the received data item, the round-specific loss, the selected subgradient, the intermediate update, and the selection over H.

Hints

The prediction happens before the data item is received.
The current loss is constructed from the current round's data.
The subgradient is used before the next-round hypothesis is selected.

Your attempt (not saved)