Randomized sampling: How confident are you?

At last year's consortium meeting, I described an inexact gradient method and sampling scheme for data fitting. The randomization method has good convergence properties, at least as measured by the distance to the solution––in expectation. But as one insightful critic rightly pointed out, we don't usually observe the expectation, at least not in a single run. In this talk I will characterize the convergence of the method in terms of bounds on the probability of being too far away from the solution.