Why the subgradient method needs averaging

ProofAdvanced⏱ 30 minOptimizationsubgradientaveragingnon-smoothcounterexample

Problem

Prove the $O(1/\sqrt T)$ bound for the averaged iterate of the subgradient method.
Give a convex Lipschitz function and a starting point for which the last iterate does not converge to the minimiser, no matter how many steps are taken with a fixed step size.

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

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

Problem	Field	Type	Difficulty	Time
Pairwise independence does not imply independence	Probability	Proof	Foundation	15 min
The exact step-size threshold on a quadratic	Optimization	Proof	Beginner	15 min
A variable with all moments finite that is not sub-Gaussian	High-Dim Probability	Proof	Intermediate	30 min
All directional derivatives exist, yet the function is not differentiable	Foundations	Proof	Intermediate	30 min
Linear convergence under strong convexity	Optimization	Proof	Intermediate	30 min