Tightness of the descent lemma
ProofBeginner⏱ 15 minFoundationssmoothnessdescent lemmatightness
Problem
The descent lemma states that for -smooth ,
Exhibit a function for which this holds with equality for all , and deduce that the constant cannot be improved. Then show that the step size is exactly the minimiser of the right-hand side over steps of the form .
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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Markov and Chebyshev are attained | High-Dim Probability | Proof | 15 min | ||
| When is the union bound tight? | Probability | Proof | 15 min | ||
| All directional derivatives exist, yet the function is not differentiable | Foundations | Proof | 30 min | ||
| The per-stage quantile budget, and when it is tight | AI Systems | Proof | 1 hour | ||
| The softmax Jacobian is a covariance | Foundations | Proof | 30 min |