Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems
By Mengdi Wang, Dimitri P. Bertsekas. 2014
17 citations recorded by the source corpus.
We consider linear systems of equations, Ax = b, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {xk} that converge to a solution as long as there exists at least one solution. This convergence property can be impaired when these methods are implemented with stochastic simulation, as is often done in important classes of large-scale problems. We introduce additional conditions and novel algorithmic stabilization schemes under which {xk} converges to a solution when A is singular and may also be used with substantial benefit when A is nearly singular.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Doina Precup
- Sergey Levine
- Martha White
- A. Mahmood
- Richard S. Sutton
- Yoshua Bengio
- Csaba Szepesvari
- Shimon Whiteson
In Computational Theory and Mathematics
- Csaba Szepesvari
- A. Mahmood
- Doina Precup
- Richard S. Sutton
- Martha White
- Ahmed Touati
- Pierre-Luc Bacon
- Pascal Vincent
In Numerical Analysis
Citations in the corpus
- An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, background): “In particular, we conjecture that it is sufficient to assure convergence (under appropriate step-size conditions) of the estimated values for all states s with nonzero emphasis, m(s) (cf. Wang & Bertsekas 2013).”
- Convergent Tree-Backup and Retrace with Function Approximation (2017, background): “Wang et al. (2017) studied also the same version as Liu et al.”
- Linear Stochastic Approximation: How Far Does Constant Step-Size and Iterate Averaging Go? (2018, methodology): “In the former scenario, and under a further assumption that the null-space of AP is diagonalizable (see [25]), the null space can be discarded after applying an appropriate linear transformation U (as in Theorem 1) to a obtain a reduced linear system ÃP θ̃ = b̃P .”