Concepts / Jensen's Inequality

Jensen's Inequality

Jensen's inequality enters because the objective function in this convergence analysis is convex.

  • Programming

From Iterates to a Solution

A Gradient Descent analysis produces a sequence of iterates rather than a single object appearing from nowhere. The convergence question is therefore: how can this sequence be turned into a solution whose quality can be measured? In this analysis, the iterates w(1), w(2), through w(T) are combined into their average, written w̄. The function value at w̄ is then compared with the function value at a reference vector w⋆.

Key point

The central quantity is the suboptimality gap f(w̄) - f(w⋆). The proof is organized around controlling this gap as the number of iterates increases.

Averaging the Iterates

Definition

The average iterate w̄ is formed by averaging the T iterates used in the analysis: w̄ = (1/T) times the sum of w(1), w(2), through w(T). This replaces the whole sequence with one vector whose function value can be evaluated.

w(1)first iteratew̄average iteratef(w̄) - f(w⋆)suboptimalityw(2)second iteratew(T)Tth iterateaveragedaveragedaveragedevaluated and compared
How do the individual iterates combine into w̄, and how is f(w̄) - f(w⋆) represented as the gap to the optimum?
Formula, step by step
  1. 1
    Start with the T iterates produced during the analysis.
  2. 2
    Add the iterates together.
  3. 3
    Scale the sum by 1/T to form their average.
  4. 4
    Use the resulting vector w̄ as the solution whose function value is compared with f(w⋆).

Convexity and Jensen's Role

Jensen's inequality enters because the objective function in this convergence analysis is convex. Its purpose is to connect the function value of the average iterate with the function values associated with the individual iterates. In the analysis, this connection lets the proof work with the averaged solution w̄ while still reasoning about the sequence w(1), ..., w(T).

Formula
f(w(1)), ...,f(w(T))individual function valuesw̄average of iteratesaverage functionvalue(1/T) sum f(w(t))f(w̄)function value at theaverageaverage function valuesJensen gives an upper comparisonevaluate
How does the function value at the average iterate relate to the average of the function values at the individual iterates?

The Reference Vector

The vector w⋆ is the reference point against which the averaged iterate is judged. The analysis measures how far the value f(w̄) is above the reference value f(w⋆). A bound such as ||w⋆|| ≤ B states that the chosen reference vector has norm no greater than B. Thus, B constrains the allowable reference vector used in the comparison; it is part of the setup of the convergence analysis.

Bnorm boundw⋆reference vector||w⋆||at most Bconstrainsmeasured by
What do w⋆ and the bound ||w⋆|| ≤ B represent geometrically, and how does the bound constrain the reference vector?
Key point

The reference vector is not the same thing as the averaged iterate. The analysis produces w̄ from the iterates and compares it with the separately chosen reference vector w⋆.

A Symbolic Proof Trace

Worked example

From a Sequence to a Suboptimality Target

Show the structure of the convergence-proof target for iterates w(1), ..., w(T), a reference vector w⋆, and a norm bound ||w⋆|| ≤ B.

  1. 1
    Form the solution

    Average w(1), ..., w(T) to obtain w̄. The analysis uses this averaged vector rather than selecting only one iterate.

  2. 2
    Apply convexity

    Because the objective is convex, use Jensen's inequality to relate f(w̄) to the average of f(w(1)), ..., f(w(T)).

  3. 3
    Choose the comparison

    Compare the value at the averaged iterate with the value at the reference vector w⋆, whose norm is bounded by B.

  4. 4
    State the target

    The quantity to control is f(w̄) - f(w⋆), the suboptimality of the averaged solution relative to the reference.

Result

The proof setup is a sequence of iterates, an averaged iterate, a convexity step, a bounded reference vector, and the target gap f(w̄) - f(w⋆).

convex-Lipschitz ffunction classw̄average iteratef(w̄) - f(w⋆)suboptimality targetconvergence ratefinal numerical boundw(1), ..., w(T)produced iteratesJensen's inequalityconvexity stepw⋆||w⋆|| ≤ Bsupportsaveragedevaluatedcomparison pointhelps analyzebounded in the completed proof
How do the assumptions, iterates, and intermediate inequalities flow into the final convergence-rate bound?

Function-Class Assumptions

The analysis is specifically framed for convex-Lipschitz functions. Convexity supplies the reason Jensen's inequality can be used when the iterates are averaged. The Lipschitz condition identifies the function class for which the convergence analysis is being carried out. These assumptions describe the setting of the proof; they are not themselves the final convergence-rate number.

convexenables Jensenfunction fobjective-joins conditionsLipschitzfunction-class conditiondescribesdescribes
How do convexity and the Lipschitz condition constrain the objective function used in the convergence analysis?

Common Analysis Mistakes

  • Common mistake

    Treating one selected iterate as the analyzed solution

    What it looks like

    Replacing w̄ with only w(T) without justification.

    Why it fails

    The described analysis defines the solution by averaging all T iterates.

    Do this instead

    Form w̄ from w(1), ..., w(T), then evaluate the suboptimality gap at w̄.

  • Common mistake

    Forgetting the reference value

    What it looks like
    Describing the objective only as f(w̄).
    Why it fails

    Suboptimality is measured by comparing f(w̄) with f(w⋆).

    Do this instead
    Use the complete gap f(w̄) - f(w⋆).
  • Common mistake

    Treating w⋆ as one of the produced iterates

    What it looks like
    Assuming w⋆ must equal w(1) or w(T).
    Why it fails

    The reference vector is the comparison point, while the iterates are the sequence produced during the analysis.

    Do this instead

    Keep the produced iterates, their average w̄, and the reference vector w⋆ conceptually separate.

  • Common mistake

    Interpreting ||w⋆|| ≤ B as the convergence rate

    What it looks like

    Reporting B as the final numerical guarantee.

    Why it fails

    The norm bound constrains the reference vector; it is part of the proof setup.

    Do this instead

    Use the bound as an assumption about w⋆ and separately derive or state any completed bound on f(w̄) - f(w⋆).

  • Common mistake

    Using Jensen's inequality without connecting it to convexity

    What it looks like

    Applying the averaging step while ignoring the function class.

    Why it fails

    The source identifies convexity as the reason Jensen's inequality is used.

    Do this instead

    Explicitly connect the convex objective assumption to the relationship between f(w̄) and the average of the individual function values.

Check Your Understanding

MEDIUM

A proof uses iterates w(1), ..., w(T), a convex-Lipschitz objective f, and a reference vector w⋆ satisfying ||w⋆|| ≤ B. Describe the four structural moves needed before a final convergence-rate bound can be stated.

Hints
  • Start by identifying the vector formed from all T iterates.
  • Name the inequality enabled by convexity.
  • Identify the quantity compared with f(w⋆).
  • Separate these setup steps from the numerical rate itself.

What do you think happens?

Before reading the reveal, what should be the analyzed solution when the proof explicitly averages w(1), ..., w(T)?

  • Only w(1)

  • Only w(T)

  • The average iterate w̄

  • The norm bound B

Reveal answer
Answer:

The average iterate w̄

The analysis replaces the sequence of iterates with their average and measures the resulting gap f(w̄) - f(w⋆).

Key Takeaways

  1. 1
    The convergence analysis is framed for convex-Lipschitz functions.
  2. 2
    The iterates w(1), ..., w(T) are combined into the average iterate w̄.
  3. 3
    Convexity motivates Jensen's inequality, which relates f(w̄) to the average of the individual function values.
  4. 4
    The reference vector w⋆ is the comparison point, and ||w⋆|| ≤ B constrains that vector.
  5. 5
    The proof target is the suboptimality gap f(w̄) - f(w⋆); the setup should not be confused with a final numerical convergence bound.

At a glance

  • Jensen's inequality is used because the objective function is convex.
  • The analysis evaluates the average iterate w̄ rather than only one selected iterate.
  • Suboptimality is represented by f(w̄) - f(w⋆), using w⋆ as the reference vector.
  • The condition ||w⋆|| ≤ B constrains the reference vector within the proof setup.
  • A convergence-proof setup identifies the assumptions and target; a final numerical rate requires the completed derivation.

Related Topics

Related concepts

More concepts starting with J