Near Optimal Stochastic Solution to Uncertain Least Squares Problems

In this paper, we present a recursive algorithm for the solution of uncertain least-square problems in a stochastic setting. The algorithm aims at minimizing the expected value with respect to the uncertainty of the least-square residual, and returns with high probability an ε-suboptimal solution in a pre-specified number of iterations. The proposed technique is based on minimization of the empirical mean and on uniform convergence results derived from learning theory inequalities. Comparisons with gradient algorithms for stochastic optimization are also discussed in the paper