Skip to content
nonconvexcard

Tightness of the descent lemma

ProofBeginner⏱ 15 minFoundationssmoothnessdescent lemmatightness

Problem

The descent lemma states that for LL-smooth ff,

f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥22.f(y) \le f(x) + \langle \nabla f(x), y-x\rangle + \frac L2\|y-x\|_2^2 .

Exhibit a function for which this holds with equality for all x,yx,y, and deduce that the constant L/2L/2 cannot be improved. Then show that the step size η=1/L\eta = 1/L is exactly the minimiser of the right-hand side over steps of the form y=x−η∇f(x)y = x - \eta\nabla f(x).

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Markov and Chebyshev are attainedHigh-Dim ProbabilityProofFoundation15 min
When is the union bound tight?ProbabilityProofFoundation15 min
All directional derivatives exist, yet the function is not differentiableFoundationsProofIntermediate30 min
The per-stage quantile budget, and when it is tightAI SystemsProofIntermediate1 hour
The softmax Jacobian is a covarianceFoundationsProofIntermediate30 min