<p>I want to do sparse high dimensional (a few thousand features) least squares regression with a few hundred thousands of examples. I'm happy to use non fancy optimisation - stochastic gradient descent is fine.</p>

<p>Does anyone know of any software already implemented for doing this, so I don't have to write to my own?</p>

<p>Kind regards.</p>

While I don't know for sure, this strikes me as the kind of thing that
LAPACK
(linear algebra package) would be able to provide support for.  They are typically interested in large matrix math, incluing sparse matrices and out-of-core sizes.  The basic version is FORTRAN, but there are ports of the libraries for C and other languages.
As LAPACK uses BLAS (basic linear algebra subprograms) for many of its underlying calls, you will probably also want to check out
Sparse BLAS
.