Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 339 / 2 / c / iii / Solution

When $A$ has full row rank, projected gradient ascent with step $1/L$ has linear convergence and requiresiterations, up to the initial-error constant. The accelerated projected method of Nesterov requiresWithout full row rank, the general smooth-convex bounds are $O(L{R}^2/ϵ)$ and $O(\sqrt{L{R}^2/ϵ})$, respectively, when a dual optimum lies within distance $R$ of the initial point.