Strong convexity implies the Polyak–Lojasiewicz inequality

ProofIntermediate⏱ 30 minOptimizationpl inequalitystrong convexitylinear convergence

Problem

Prove that $\mu$ -strong convexity implies

\|\nabla f(x)\|_2^2 \ge 2\mu\big(f(x)-f^\star\big) \quad\text{for all }x .

Then give an example of a non-convex function satisfying the PL inequality, showing PL is strictly weaker than strong convexity.

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

Hints — 0 of 2 revealed

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
Every norm is convex, and the operator norm is a supremum of linear functions	Optimization	Proof	Beginner	15 min
Existence and uniqueness of the minimiser	Optimization	Proof	Beginner	15 min
First-order characterisation of convexity	Optimization	Proof	Beginner	30 min
Separating convexity, strong convexity, smoothness and Lipschitzness	Optimization	Proof	Intermediate	30 min
NTK convergence is a PL inequality abyss	DL Theory	Proof	Graduate	1 hour