Mirror descent on the simplex beats Euclidean projection

ProofGraduate⏱ 1 hourAdvanced Optimizationmirror descententropysimplexdimension dependence

Problem

Consider minimising a convex $f$ over the probability simplex $\Delta_d$ with $\|\nabla f\|_\infty\le G_\infty$ .

Show that projected subgradient descent gives a rate $O\big(G_2R_2/\sqrt T\big)$ with $R_2 = \max_x\|x-x_0\|_2$ and $G_2 = \max\|\nabla f\|_2$ , and bound $G_2$ by $\sqrt d\,G_\infty$ .
Show that mirror descent with the negative entropy $\Phi(x) = \sum_ix_i\log x_i$ gives $O\big(G_\infty\sqrt{\log d}/\sqrt T\big)$ .
Quantify the improvement at $d = 10^6$ .

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
Lipschitz constants depend on the norm	Foundations	Numerical	Beginner	15 min
The proximal operator of the l1 norm	Advanced Optimization	Proof	Beginner	15 min
Concave impurity gives non-negative information gain	Classical ML	Proof	Intermediate	30 min
The Frank–Wolfe duality gap certificate	Advanced Optimization	Proof	Intermediate	30 min
The irreducible loss is the conditional entropy	LLMs	Proof	Intermediate	30 min