First-order algorithms converge faster than O(1/k) on convex problems

MaRDI QIDQ6311428zbMATH OpenFDO

Authors Ching-pei Lee, Stephen J. Wright

Publication date 20 December 2018

Abstract: It is well known that both gradient descent and stochastic coordinate descent achieve a global convergence rate of $O(1/k)$ in the objective value, when applied to a scheme for minimizing a Lipschitz-continuously differentiable, unconstrained convex function. In this work, we improve this rate to $o(1/k)$. We extend the result to proximal gradient and proximal coordinate descent on regularized problems to show similar $o(1/k)$ convergence rates. The result is tight in the sense that a rate of $O(1/k^{1+epsilon})$ is not generally attainable for any $epsilon>0$, for any of these methods.

This page was built for publication: First-order algorithms converge faster than $O(1/k)$ on convex problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311428)