Jensen's Inequality
Gradient Descent convergence is analyzed here for convex-Lipschitz functions.
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⋆.
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
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/T) [w(1) + w(2) + ... + w(T)]
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).
f(w̄) ≤ (1/T) [f(w(1)) + f(w(2)) + ... + f(w(T))]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.
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
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.
Form the solution: Average w(1), ..., w(T) to obtain w̄. The analysis uses this averaged vector rather than selecting only one iterate.
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)).
Choose the comparison: Compare the value at the averaged iterate with the value at the reference vector w⋆, whose norm is bounded by B.
State the target: The quantity to control is f(w̄) - f(w⋆), the suboptimality of the averaged solution relative to the reference.
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⋆).
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.
Common Analysis Mistakes
Treating one selected iterate as the analyzed solution
The described analysis defines the solution by averaging all T iterates.
Fix:
Form w̄ from w(1), ..., w(T), then evaluate the suboptimality gap at w̄.Forgetting the reference value
Suboptimality is measured by comparing f(w̄) with f(w⋆).
Fix:
Use the complete gap f(w̄) - f(w⋆).Treating w⋆ as one of the produced iterates
The reference vector is the comparison point, while the iterates are the sequence produced during the analysis.
Fix:
Keep the produced iterates, their average w̄, and the reference vector w⋆ conceptually separate.Interpreting ||w⋆|| ≤ B as the convergence rate
The norm bound constrains the reference vector; it is part of the proof setup.
Fix:
Use the bound as an assumption about w⋆ and separately derive or state any completed bound on f(w̄) - f(w⋆).Using Jensen's inequality without connecting it to convexity
The source identifies convexity as the reason Jensen's inequality is used.
Fix:
Explicitly connect the convex objective assumption to the relationship between f(w̄) and the average of the individual function values.
Check Your Understanding
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)?
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
- The convergence analysis is framed for convex-Lipschitz functions.
- The iterates w(1), ..., w(T) are combined into the average iterate w̄.
- Convexity motivates Jensen's inequality, which relates f(w̄) to the average of the individual function values.
- The reference vector w⋆ is the comparison point, and ||w⋆|| ≤ B constrains that vector.
- The proof target is the suboptimality gap f(w̄) - f(w⋆); the setup should not be confused with a final numerical convergence bound.
Key Takeaways
- 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.