In Chapter 4 we discussed algorithms for linear regression that read the entire problem. Here we discuss sampling-based approaches, which access only a subset of the data. These are particularly useful when observing entries of the data is expensive (as in active regression) or when the problem is too large to process all at once (as with stochastic gradient descent and randomized Kaczmarz methods).
This chapter is still in progress.