Enhanced randomized Douglas-Rachford method for linear systems: Improved probabilities and adaptive momentum

Abstract

Randomized iterative methods have gained recent interest in machine learning and signal processing for solving large-scale linear systems. One such example is the randomized Douglas-Rachford (RDR) method, which updates the iterate by reflecting it through two randomly selected hyperplanes and taking a convex combination with the current point. In this work, we enhance RDR by introducing improved sampling strategies and an adaptive heavy-ball momentum scheme. Specifically, we incorporate without-replacement sampling and volume sampling into RDR and establish linear convergence in expectation for both schemes. For without-replacement sampling, we further establish a larger one-step descent than that of conventional RDR. For volume sampling, the convergence rate explicitly incorporates geometric information, and a tighter comparison with RDR is obtained under additional structural assumptions. Furthermore, we develop an adaptive momentum mechanism that determines the relaxation and momentum parameters directly from the iteration information without manual tuning. We establish linear convergence in expectation for the resulting method. Numerical experiments demonstrate the effectiveness of the proposed methods across a range of problem settings.

arXiv commentto appear in IMA Journal of Numerical Analysis