On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
arXiv:1905.06030
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.
arXiv comment12 pages, 1 figure
References in corpus (8)
- Optimized first-order methods for smooth convex minimization
- Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- Generalizing the optimized gradient method for smooth convex minimization
- On the convergence analysis of the optimized gradient method
- Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
- Accelerated Proximal Point Method for Maximally Monotone Operators
- Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problems