Projection Algorithm with Extrapolations from the Past for Variational Inequalities

Projection-based methods for solving variational inequalities in Hilbert spaces often suffer from computational inefficiency, as many state-of-the-art algorithms require two evaluations of the operator per iteration-a significant drawback in large-scale applications, such as image restoration and machine learning. Additionally, while some methods theoretically achieve fast convergence, their practical performance is often hindered by the need for complex parameter tuning or restrictive assumptions. To address these limitations, we propose a novel projection algorithm that leverages extrapolation from past iterates to accelerate convergence while requiring only one operator evaluation per iteration. We prove weak and strong convergence, and establish non-asymptotic error bounds for the ergodic sequence, achieving an optimal $$\mathcal {O}(1/n)$$ O ( 1 / n ) convergence rate. Numerical experiments on image restoration and machine learning demonstrate that our method outperforms existing approaches in both speed and accuracy, offering a more efficient and practical solution. By eliminating the need for double operator evaluations and maintaining robust convergence guarantees, our work fills a critical gap in the literature, enabling broader applicability in real-world problems.