Kaczmarz and Gauss-Seidel Algorithms with Volume Sampling
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913868124520448 |
|---|---|
| author | Entezari, Alireza Banerjee, Arunava Kalantari, Leila |
| author_facet | Entezari, Alireza Banerjee, Arunava Kalantari, Leila |
| contents | The method of Alternating Projections (AP) is a fundamental iterative technique with applications to problems in machine learning, optimization and signal processing. Examples include the Gauss-Seidel algorithm which is used to solve large-scale regression problems and the Kaczmarz and projections onto convex sets (POCS) algorithms that are fundamental to iterative reconstruction. Progress has been made with regards to the questions of efficiency and rate of convergence in the randomized setting of the AP method. Here, we extend these results with volume sampling to block (batch) sizes greater than 1 and provide explicit formulas that relate the convergence rate bounds to the spectrum of the underlying system. These results, together with a trace formula and associated volume sampling, prove that convergence rates monotonically improve with larger block sizes, a feature that can not be guaranteed in general with uniform sampling (e.g., in SGD). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_06931 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Kaczmarz and Gauss-Seidel Algorithms with Volume Sampling Entezari, Alireza Banerjee, Arunava Kalantari, Leila Numerical Analysis Optimization and Control 52C35, 65F10, 15A18, 52A38 The method of Alternating Projections (AP) is a fundamental iterative technique with applications to problems in machine learning, optimization and signal processing. Examples include the Gauss-Seidel algorithm which is used to solve large-scale regression problems and the Kaczmarz and projections onto convex sets (POCS) algorithms that are fundamental to iterative reconstruction. Progress has been made with regards to the questions of efficiency and rate of convergence in the randomized setting of the AP method. Here, we extend these results with volume sampling to block (batch) sizes greater than 1 and provide explicit formulas that relate the convergence rate bounds to the spectrum of the underlying system. These results, together with a trace formula and associated volume sampling, prove that convergence rates monotonically improve with larger block sizes, a feature that can not be guaranteed in general with uniform sampling (e.g., in SGD). |
| title | Kaczmarz and Gauss-Seidel Algorithms with Volume Sampling |
| topic | Numerical Analysis Optimization and Control 52C35, 65F10, 15A18, 52A38 |
| url | https://arxiv.org/abs/2111.06931 |