Convex Optimization

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.

Programming

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.

How does adding a regularization term change the original loss objective and the optimization target?

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.

Key point

How does strong convexity shape the objective and support the convergence behavior of the chosen SGD variant?

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.

Formula

Worked example

One Random Example, Two Contributions

Construct the estimate used for the regularized objective at iteration t.

1
Select an example
Choose z uniformly at random from the training sample S.
2
Select a loss subgradient
Choose vₜ ∈ ∂ℓ(w(t), z), a subgradient of the selected example's loss at the current vector.
3
Add regularization
Compute the regularization contribution λw(t) and add the sampled loss contribution vₜ.
4
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.

Result

The required estimate is λw(t) + vₜ, with z selected uniformly from S and vₜ ∈ ∂ℓ(w(t), z).

How does randomly selecting one training example produce a subgradient estimate whose expectation matches the full objective subgradient?

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.

What happens, in order, when the learner makes a prediction, the environment reveals a response, and the learner incurs a 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.

How are the learner's prediction vector and the fixed competing vector different, and where does each appear in the loss comparison?

Cumulative Regret

Rule

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.

How does regret accumulate over time as the algorithm's losses are compared with the losses of a competing hypothesis?

Worked example

Interpreting a Regret Comparison

Compare an algorithm's sequence of losses with the losses of one competing vector w⋆.

1
Track the algorithm
At each round, record the loss caused by the learner's prediction vector.
2
Track the competitor
For the same sequence of environment responses, evaluate the loss associated with the fixed competing vector w⋆.
3
Accumulate both sequences
Add each sequence of losses across all rounds rather than comparing only one round.
4
Take the difference
Subtract the competitor's cumulative loss from the algorithm's cumulative loss.

Result

The resulting difference is the regret relative to w⋆.

Mistakes in Applying the Framework

Common mistake
Using only the sampled loss subgradient
What it looks like
Using vₜ as the complete estimate for the regularized objective.
Why it fails
The regularized objective contains both a regularization contribution and a loss contribution.
Do this instead
Add the regularization term and use λw(t) + vₜ.
Common mistake
Selecting an example without the required sampling rule
What it looks like
Choosing an arbitrary example z from S.
Why it fails
The stated construction selects z uniformly at random from S.
Do this instead
```
Choose z uniformly, then select vₜ ∈ ∂ℓ(w(t), z).
```
Common mistake
Treating the estimate as exact for every sample
What it looks like
Assuming λw(t) + vₜ is the exact subgradient for every selected example.
Why it fails
The source describes it as an unbiased estimate, not necessarily the exact subgradient for each sampled example.
Do this instead
Distinguish an unbiased estimate from an exact per-example subgradient.
Common mistake
Confusing the learner's vector with the competitor
What it looks like
Treating w(t) and w⋆ as the same vector in regret analysis.
Why it fails
w(t) is the learner's current prediction, while w⋆ is a competing vector used as a reference.
Do this instead
Track the learner's prediction sequence separately from the fixed competing vector.
Common mistake
Computing regret from one round
What it looks like
Comparing only the current learner loss with the current competitor loss.
Why it fails
Regret is evaluated using cumulative losses across the sequence.
Do this instead
Accumulate both loss sequences before taking their difference.

Practice the Two Settings

MEDIUM

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.

Your attempt (not saved)

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?

Only λw(t)
Only vₜ
λw(t) + vₜ
Only the competing vector w⋆

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

1
Regularized loss minimization changes the objective by combining a loss term with a regularization term.
2
Under the stated convex-loss assumption, the regularized objective is convex; in the given formulation it is λ-strongly convex and has a unique minimum.
3
The stochastic subgradient estimate is λw(t) + vₜ, where z is selected uniformly from S and vₜ ∈ ∂ℓ(w(t), z).
4
Online convex optimization proceeds through prediction, environment response, and incurred loss.
5
Regret compares cumulative learner loss with cumulative loss of a competing vector w⋆.

At a glance

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⋆.

Related concepts

More concepts starting with C