Enhanced randomized Douglas-Rachford method: Improved probabilities and adaptive momentum
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911001538985984 |
|---|---|
| author | Guo, Liqi Xiang, Ruike Han, Deren Xie, Jiaxin |
| author_facet | Guo, Liqi Xiang, Ruike Han, Deren Xie, Jiaxin |
| contents | 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 and volume sampling into RDR, and establish stronger convergence guarantees compared to conventional i.i.d. sampling. Furthermore, we develop an adaptive momentum mechanism that dynamically adjusts step sizes and momentum parameters based on previous iterates, and prove that the resulting method achieves linear convergence in expectation with improved convergence bounds. Numerical experiments demonstrate that the enhanced RDR method consistently outperforms the original version, providing substantial practical benefits across a range of problem settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10261 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enhanced randomized Douglas-Rachford method: Improved probabilities and adaptive momentum Guo, Liqi Xiang, Ruike Han, Deren Xie, Jiaxin Numerical Analysis 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 and volume sampling into RDR, and establish stronger convergence guarantees compared to conventional i.i.d. sampling. Furthermore, we develop an adaptive momentum mechanism that dynamically adjusts step sizes and momentum parameters based on previous iterates, and prove that the resulting method achieves linear convergence in expectation with improved convergence bounds. Numerical experiments demonstrate that the enhanced RDR method consistently outperforms the original version, providing substantial practical benefits across a range of problem settings. |
| title | Enhanced randomized Douglas-Rachford method: Improved probabilities and adaptive momentum |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2506.10261 |