SGD and subgradients of maximum functions

A Contest Among Labels

A multiclass SVM treats prediction as a competition among possible labels. For an input, it assigns a score to each input-label pair, then selects the label with the greatest score. The learned vector w and the class-sensitive feature mapping Ψ together produce these scores.

Prediction by Argmax

The prediction rule examines every candidate label in the label set. It evaluates the score associated with each pair consisting of the new input and one candidate label. The argmax operation returns the label whose score is greatest. Thus, the prediction is one selected label, not a collection of separate binary decisions.

The Generalized Hinge

This maximum is central because training must respond to the alternative that places the greatest demand on the current model. The objective combines the average generalized hinge contribution over the training examples with a regularization term λ ‖w‖². The parameter λ is positive and controls the regularization term in the stated learning problem.

Why SGD Looks for a Maximizer

The generalized hinge is not treated as an ordinary smooth expression because it contains a maximum function. In the SGD approach, the procedure first finds a label y in the label set Y that achieves the maximum in the generalized hinge definition. A subgradient result for maximum functions then supplies the basis for obtaining subgradient information.

From Maximizer to Weight Update

For one training example, SGD follows a compact sequence. It considers the correct label and the alternative labels, evaluates the generalized-hinge quantities, locates a label that achieves the maximum, and uses the resulting subgradient information in the learning step. The regularization term is part of the overall objective, so the learning problem balances regularization with average generalized hinge loss.

Common Reasoning Errors

• Choosing a label without comparing all candidate labels.

  The multiclass SVM prediction rule compares the score for every possible class and selects the greatest score.

  Fix: List the candidate-label scores and apply the argmax rule.

• Treating the generalized hinge as if it had no maximum.

  The subgradient information depends on the label selected by the maximum-function step.

  Fix: First locate a maximizing label, then use the subgradient result for the maximum.

• Confusing the prediction label with the training maximizer.

  Prediction compares candidate labels for a new input, whereas training examines alternatives for a labeled training pair.

  Fix: Identify whether the task is prediction or generalized-hinge evaluation before interpreting the maximum.

• Ignoring regularization when describing the learning objective.

  The stated objective combines regularization with the average generalized hinge contribution.

  Fix: Mention both the regularization term λ ‖w‖² and the average generalized hinge loss.

Practice the Trace

Key Takeaways

1. A multiclass SVM scores every input-label pair and predicts the label with the greatest score.
2. The generalized hinge evaluates alternative labels for each training pair and uses a maximum to find the most demanding alternative.
3. Because the generalized hinge contains a maximum, SGD first locates a maximizing label before using subgradient information.
4. The learning objective balances the regularization term λ ‖w‖² with average generalized hinge loss.
5. Prediction and training both involve maxima, but they apply those maxima in different contexts.