Surrogate Loss Functions
The Perceptron can be placed inside the Online Gradient Descent framework.
From Natural Loss to Surrogate
A learning algorithm needs a loss function to judge predictions. The natural loss may express the learning goal directly, but natural loss functions are often not convex. This creates a central difficulty: when the loss is non-convex, implementing the empirical risk minimization rule is hard. Surrogate loss functions are introduced to provide a loss-based analysis with useful convex structure. The Perceptron is a central example because its mistake-driven update can be viewed as an instance of Online Gradient Descent.
| Learning view | Role in the analysis |
|---|---|
| Natural loss | Expresses the learning goal, but may be non-convex |
| 0-1 loss | A natural, non-convex loss function |
| Surrogate loss | Provides a loss used to connect the learning problem to convex analysis |
| Online Gradient Descent | Uses a round-specific subgradient to update the current hypothesis |
Online Gradient Descent State
Online Gradient Descent begins with the hypothesis w(1) = 0. At round t, the algorithm has a current hypothesis w(t), observes the current example xₜ and its label yₜ, obtains a subgradient vₜ for the round-specific loss, and forms the next hypothesis with w(t+1) = w(t) − ηvₜ. In the Perceptron analysis, the hypothesis class is all vectors in Rᵈ, so the projection step is vacuous. The Perceptron update is written without a learning-rate factor as w(t+1) = w(t) − vₜ, and the source explains that this is equivalent to the Online Gradient Descent form for every η > 0.
w(1) = 0 w(t+1) = w(t) − ηvₜ
The Perceptron Subgradient
vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0] yₜxₜ w(t+1) = w(t) − vₜ
Tracing One Selected Update
Suppose a round satisfies the Perceptron condition yₜ⟨w(t), xₜ⟩ ≤ 0. What subgradient and next hypothesis does the stated rule produce?
Select the indicator: Because the condition yₜ⟨w(t), xₜ⟩ ≤ 0 holds, the indicator in vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0]yₜxₜ selects the value 1.
Evaluate the subgradient: The subgradient becomes vₜ = −yₜxₜ.
Apply the update: Substituting this subgradient into w(t+1) = w(t) − vₜ gives the Perceptron update.
The round produces vₜ = −yₜxₜ and updates the hypothesis by w(t+1) = w(t) − vₜ.
Correct Rounds and Convexity
The surrogate loss used in the analysis is allowed to vary from one online round to another. On a round where the Perceptron is correct, the selected loss fₜ is defined to be convex and evaluates to zero at the current hypothesis: fₜ(w(t)) = ℓ(w(t), (xₜ, yₜ)) = 0. This matters because the Perceptron is being analyzed through Online Gradient Descent, a framework that uses subgradients of the round-specific losses. The correct-round case therefore supplies a convex surrogate with zero value at the current hypothesis.
Why Direct ERM Is Difficult
The source uses halfspaces as a hypothesis class for illustrating the difficulty of learning with a natural non-convex loss. The 0-1 loss is natural, but it is non-convex. Consequently, directly implementing the ERM rule is hard in this setting. The surrogate-loss approach changes the analysis: instead of relying only on the difficult natural loss, it introduces losses with convex structure so that an Online Gradient Descent analysis can be applied.
Treating the 0-1 loss as convex because it is a natural way to judge prediction errors.
The source identifies 0-1 loss as a natural, non-convex loss function.
Fix:
Separate the natural loss from the surrogate loss introduced for convex analysis.Assuming that the same surrogate loss must be used on every online round.
The online analysis permits a round-specific choice of fₜ.
Fix:
At round t, identify the current loss fₜ and use its corresponding subgradient.Forgetting the initialization of Online Gradient Descent.
The stated Online Gradient Descent procedure starts with w(1) = 0.
Fix:
Begin the sequence with the zero vector and then apply the round updates.
Practice the Update Chain
Explain the Perceptron analysis in four linked steps: identify the current hypothesis and labeled example, state the subgradient vₜ, write the next-hypothesis rule, and explain why a surrogate loss is used instead of relying directly on the natural 0-1 loss.
Hints
- Start with w(1) = 0 when describing Online Gradient Descent.
- Use vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0]yₜxₜ.
- Connect w(t+1) = w(t) − vₜ to the general Online Gradient Descent rule.
- Mention non-convexity and the difficulty of implementing ERM.
What do you think happens?
If the indicator condition in vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0]yₜxₜ is not selected on a round, what happens to the hypothesis?
Reveal answer
Answer: The subgradient is zero, so the hypothesis is left unchanged
When the indicator is not selected, vₜ = 0. Substituting into w(t+1) = w(t) − vₜ leaves w(t+1) equal to w(t) for that round.
Key Takeaways
- The Perceptron can be analyzed as Online Gradient Descent using a surrogate loss selected for each online round.
- Online Gradient Descent starts with w(1) = 0 and updates with w(t+1) = w(t) − ηvₜ.
- The Perceptron subgradient is vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0]yₜxₜ, and its update is w(t+1) = w(t) − vₜ.
- On correct rounds, the selected loss is convex and has value zero at the current hypothesis.
- The 0-1 loss is natural but non-convex, making direct ERM difficult; surrogate losses provide the convex structure used for efficient analysis.
Key Takeaways
- Surrogate losses connect the Perceptron's mistake-driven behavior to Online Gradient Descent.
- The online analysis may choose a different loss fₜ for each round.
- The Perceptron update follows from the subgradient vₜ = −1[yₜ⟨w(t), xₜ⟩ ≤ 0]yₜxₜ.
- Convexity is useful because convex problems can be learned efficiently, while direct ERM for non-convex losses is difficult.
- The natural 0-1 loss motivates introducing a convex surrogate for analysis.