  This article considers stochastic algorithms for efficiently solving a class
of large scale non-linear 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 semi-definite (SPSD) 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.
