Solving a practical machine learning problem I am currently doing my Phd in computational biology at Stanford. I get the data I need to answer the questions I am interested in. The data sets are sometimes "large" and these large problems take longer time periods to solve (a couple of days sometimes).
That being said I was wondering how machine learning on extremely massive data sets works? Suppose google wants to solve $Ax = b$ where $A$ has 10 billion rows, finding any gradients seems prohibitive. If google actually ran these  simulations for as long as it takes (my equivalent of a couple of days), the solution maybe worthless before it arrives. This problem will be accentuated while training neural networks or implementing more complicated methods. What are practical solutions to this problem? 
I have seen statements like "We pick representative samples...". This is an absurd statement in my opinion because when p >> n, nothing is representative since the systems are under-determined. Any help on what 'representative' in these cases will also help.
 A: 
I have seen statements like "We pick representative samples...". This
  is an absurd statement...

I agree with you on this. And I don't think representative sampling is what they do (anymore). My understanding is that they analyse big data with distributed computing, using technology like Hadoop, Spark, and MLLib. I am sure they write their proprietary and complex machine learning / analysis libraries on top of these.
The algorithms for these "distributable" systems are coded differently than how you and I would code them in e.g. R, Matlab or Python. They need to be scalable and parallelisable, which is an issue for some algorithms. MLLib, for instance, currently only supports some very basic algorithms (list available on their website). 
A: Beyond subsampling and divide-and-conquer distributed computing, both important and useful, there are many other ways of solving such problems. To name just a couple, parallel coordinate descent (iterate on each variable independently, combine solutions later), and online methods, like stochastic gradient descent (SGD).
Have a look at https://github.com/JohnLangford/vowpal_wabbit for quite a widely used approach to online learning with SGD. Also Alex Smola has done quite a bit of work on large-scale learning.
A: Massively parallel matrix inversion is actually doable with open source software such as MUMPS, although I'm not sure how it would scale to 10bio rows. It's used for large scale finite elements in automotive so it's industrial strength for sure.
As for the class of algorithms used, it's a multifrontal approach (divide the matrix into zones that don't 'interfere' with each other in the sense of cholesky-like outer product updates, solve each part and gather rectangular 'interference' updates). Much more details on the mumps website, http://mumps.enseeiht.fr/ .
Now if you're just doing linear regression, the result will be x = (AtA)-1At b and you can probably parallelize the computation of the covar matrix (AtA) and the error term efficiently to run on different machines and then aggregate the results. This supposes A has only a few columns.
A: Thank you all for your comments. Turns out Apache spark does L1 penalized regressions. I found links to training videos here which some of you may find helpful. 
Turns out the folk at Google who seriously studied this problem and founded the Map-Reduce architecture were Jeff Dean and Sanjay Ghemawat, both of whom have become silicon-valley rockstars. Jeff Dean has his own Chuck Norris persona!!!
http://www.quora.com/What-are-all-the-Jeff-Dean-facts?share=1
