Online Gradient Descent

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.

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.

w(1) = 0

w(t+1) = w(t) − ηvₜ

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.

vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0] yₜxₜ

w(t+1) = w(t) − vₜ

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.

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.

Symbolic Round Trace

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.

Common Tracing Mistakes

• Using the newly received example to define the prediction that was already made.

  The prediction uses the value available at the start of the round. The data item is received afterward.

  Fix: Write the order as prediction, data receipt, loss formation, subgradient selection, and update.

• Using one identical surrogate loss for every online round.

  The online analysis permits a round-specific surrogate loss fₜ.

  Fix: Index the current loss by t and construct it from the current round's data.

• Leaving the Perceptron subgradient separate from Online Gradient Descent.

  The subgradient is the quantity used in the Online Gradient Descent update.

  Fix: Substitute vₜ into w(t+1) = w(t) − vₜ to see the Perceptron form.

• Treating the two update steps as one unexplained operation.

  The source emphasizes that the two update expressions must be traced separately.

  Fix: First apply the subgradient update, then account for selection over the hypothesis class.

Practice Trace

Key Takeaways

1. Online Gradient Descent repeatedly predicts, receives data, forms a round-specific loss, selects a subgradient, and updates its hypothesis.
2. It starts with w(1) = 0 and uses the general update w(t+1) = w(t) − ηvₜ.
3. The Perceptron subgradient is vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0] yₜxₜ, producing the Perceptron update w(t+1) = w(t) − vₜ.
4. On correct rounds, the selected surrogate loss is convex and has value zero at the current hypothesis.
5. The regret guarantee is stated for every competing hypothesis w⋆ in H.