On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities

arXiv1905.06030MaRDI QIDQ6318779FDOQ6318779

Publication date: 15 May 2019

Abstract: This paper investigates the optimal ergodic sublinear convergence rate of the relaxed proximal point algorithm for solving monotone variational inequality problems. The exact worst case convergence rate is computed using the performance estimation framework. It is observed that, as the number of iterations getting larger, this numerical rate asymptotically coincides with an existing sublinear rate, whose optimality is unknown. This hints that, without further assumptions, sublinear convergence rate is likely the best achievable rate. A concrete example is constructed, which provides a lower bound for the exact worst case convergence rate. Amazingly, this lower bound coincides with the exact worst case bound computed via the performance estimation framework. This observation motivates us to conjecture that the lower bound provided by the example is exactly the worse case iteration bound, which is then verified theoretically. We thus have established an ergodic sublinear convergence rate that is optimal in terms of both the order of the sublinear rate and all the constants involved.

This page was built for publication: On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities

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