Name
Title | ||
|---|---|---|
Assessing stochastic algorithms for large scale nonlinear least squares problems using extremal probabilities of linear combinations of gamma random variables. |
Abstract | ||
|---|---|---|
This paper considers stochastic algorithms for efficiently solving a class of large scale nonlinear least squares (NLS) problems which frequently arise in applications. We propose eight variants of a practical randomized algorithm where the uncertainties in the major stochastic steps are quantified. Such stochastic steps involve approximating the NLS objective function using Monte Carlo methods, and this is equivalent to the estimation of the trace of corresponding symmetric positive semidefinite matrices. For the latter, we prove tight necessary and sufficient conditions on the sample size (which translates to cost) to satisfy the prescribed probabilistic accuracy. We show that these conditions are practically computable and yield small sample sizes. They are then incorporated in our stochastic algorithm to quantify the uncertainty in each randomized step. The bounds we use are applications of more general results regarding extremal tail probabilities of linear combinations of gamma distributed random variables. We derive and prove new results concerning the maximal and minimal tail probabilities of such linear combinations, which can be considered independently of the rest of this paper. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/14096311X | SIAM-ASA JOURNAL ON UNCERTAINTY QUANTIFICATION |
Keywords | Field | DocType |
randomized algorithms,inverse problems,Monte Carlo methods,trace estimation,gamma random variable,extremal probability,large scale simulation | Randomized algorithm,Linear combination,Stochastic optimization,Monte Carlo method,Mathematical optimization,Random variable,Matrix (mathematics),Non-linear least squares,Probabilistic logic,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 1 | 2166-2525 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Farbod Roosta-Khorasani | 1 | 102 | 9.25 |
| Gábor J. Székely | 2 | 23 | 2.96 |
| Uri M. Ascher | 3 | 375 | 113.62 |