= Solution
When $A$ has full row rank, projected gradient ascent with step $1/L$ has linear convergence and requires
$$
\boxed{k=O\left(\frac L\mu\log\frac1\epsilon\right)}
$$
iterations, up to the initial-error constant. The accelerated projected method of <Nesterov accelerated gradient method>[Nesterov] requires
$$
\boxed{k=O\left(\sqrt{\frac L\mu}\log\frac1\epsilon\right).}
$$
Without full row rank, the general smooth-convex bounds are $O(LR^2/\epsilon)$ and $O(\sqrt{LR^2/\epsilon})$, respectively, when a dual optimum lies within distance $R$ of the initial point.
Back to article page
