Convex Optimization
Regularization changes the optimization target by adding a term to the loss objective.
From Loss to Regularized Objective
Many learning problems begin by minimizing loss on a sample. Regularized loss minimization changes that target by adding a regularization term. The objective therefore contains two contributions: the loss contribution from the training examples and a regularization contribution. An optimization method must account for both parts rather than estimating only the loss from one example.
The important shift is not merely that an extra term appears in a formula. The optimization target itself has changed. A method that estimates only one example's loss contribution would omit part of the objective. Regularized loss minimization instead combines the current regularization contribution with information from a sampled loss.
Convexity and Strong Convexity
The regularized problem can be handled as a convex optimization problem when the loss function satisfies the stated convexity assumption. The resulting objective is convex, and in the given formulation it is λ-strongly convex. Strong convexity is the structural property that makes the objective fit the SGD variant being applied.
In the source's formulation, strong convexity ensures that the objective has a unique minimum. This gives the optimization problem a single minimizing point rather than merely a collection of possible minimizing points.
Building the Sampled Subgradient
At iteration t, the update direction is assembled in two pieces. First, evaluate the regularization contribution at the current parameter vector w(t), giving λw(t). Second, choose an example z uniformly at random from the sample S and choose a subgradient vₜ from the subgradient set of that example's loss at w(t). The two pieces are then added.
λw(t) + vₜOne Random Example, Two Contributions
Construct the estimate used for the regularized objective at iteration t.
Select an example: Choose z uniformly at random from the training sample S.
Select a loss subgradient: Choose vₜ ∈ ∂ℓ(w(t), z), a subgradient of the selected example's loss at the current vector.
Add regularization: Compute the regularization contribution λw(t) and add the sampled loss contribution vₜ.
Interpret the result: The combined quantity is an unbiased estimate of a subgradient for the regularized objective. It is not necessarily the exact subgradient for every particular sampled example.
The required estimate is λw(t) + vₜ, with z selected uniformly from S and vₜ ∈ ∂ℓ(w(t), z).
The Online Prediction Cycle
Online convex optimization studies a repeated prediction problem. At each time step, the learner chooses a vector from a hypothesis class. The environment then provides a domain element, and the learner suffers a loss determined by the chosen vector and that element. The order is therefore prediction, environment response, and incurred loss.
The framework requires both sides of the learning setup to have compatible structure. The available hypotheses must form a convex set, and the loss must be convex in its first argument, which is the learner's predicted vector. These assumptions are what place the repeated prediction problem inside online convex optimization.
Prediction Versus Competition
The learner's prediction vector is the vector selected at the current time step. Regret analysis introduces a different object: a competing vector w⋆ in the hypothesis class. The competing vector is used as a fixed reference for comparison across the sequence of rounds. It is not the learner's current prediction merely renamed.
Cumulative Regret
Regret = cumulative algorithm loss − cumulative loss of w⋆Regret compares the learner with the competing vector over multiple rounds. It is not determined by a single prediction or a single loss. First accumulate the learner's losses across the sequence. Then accumulate the losses that the competing vector would have incurred on the same sequence. Regret is the difference between those two cumulative quantities.
Interpreting a Regret Comparison
Compare an algorithm's sequence of losses with the losses of one competing vector w⋆.
Track the algorithm: At each round, record the loss caused by the learner's prediction vector.
Track the competitor: For the same sequence of environment responses, evaluate the loss associated with the fixed competing vector w⋆.
Accumulate both sequences: Add each sequence of losses across all rounds rather than comparing only one round.
Take the difference: Subtract the competitor's cumulative loss from the algorithm's cumulative loss.
The resulting difference is the regret relative to w⋆.
Mistakes in Applying the Framework
Using only the sampled loss subgradient
The regularized objective contains both a regularization contribution and a loss contribution.
Fix:
Add the regularization term and use λw(t) + vₜ.Selecting an example without the required sampling rule
The stated construction selects z uniformly at random from S.
Fix:
Choose z uniformly, then select vₜ ∈ ∂ℓ(w(t), z).Treating the estimate as exact for every sample
The source describes it as an unbiased estimate, not necessarily the exact subgradient for each sampled example.
Fix:
Distinguish an unbiased estimate from an exact per-example subgradient.Confusing the learner's vector with the competitor
w(t) is the learner's current prediction, while w⋆ is a competing vector used as a reference.
Fix:
Track the learner's prediction sequence separately from the fixed competing vector.Computing regret from one round
Regret is evaluated using cumulative losses across the sequence.
Fix:
Accumulate both loss sequences before taking their difference.
Practice the Two Settings
A regularized learning objective is being optimized at iteration t. Describe the complete construction of the stochastic subgradient estimate, including how z is selected and what vₜ represents. Then describe the three events in one online convex optimization round and explain what quantities must be accumulated to evaluate regret relative to w⋆.
Hints
- Start with the regularization contribution λw(t).
- The sampled example must be chosen uniformly from S.
- Regret compares cumulative learner loss with cumulative loss for the competing vector.
What do you think happens?
What should be included if an SGD step is intended to estimate a subgradient of the regularized objective rather than only one example's loss?
Reveal answer
Answer: λw(t) + vₜ
The estimate combines the regularization contribution at the current vector with a subgradient from a uniformly selected example.
Key Takeaways
- Regularized loss minimization changes the objective by combining a loss term with a regularization term.
- Under the stated convex-loss assumption, the regularized objective is convex; in the given formulation it is λ-strongly convex and has a unique minimum.
- The stochastic subgradient estimate is λw(t) + vₜ, where z is selected uniformly from S and vₜ ∈ ∂ℓ(w(t), z).
- Online convex optimization proceeds through prediction, environment response, and incurred loss.
- Regret compares cumulative learner loss with cumulative loss of a competing vector w⋆.
Key Takeaways
- Regularization adds a second contribution to the loss objective, so the optimization method must account for both loss and regularization.
- Convexity permits the regularized problem to be treated as convex optimization, while strong convexity gives the stated formulation a unique minimum.
- A uniformly sampled example produces the loss subgradient vₜ, which is combined with λw(t) to form an unbiased estimate.
- Online convex optimization follows the sequence prediction, environment response, and incurred loss.
- Regret is the difference between cumulative algorithm loss and cumulative loss of a competing vector w⋆.