[Slightly OT] SVD etc on Map/Reduce?

["Philipp K. Janert" <ja...@ieee.org>]

This is slightly off-topic for this list and in any case
incredibly naive, but here we go...

Can you point me to some resources for algorithms
that implement "standard" linear algebra operations
(mostly operator splittings) efficiently (!) on M/R?

I can think of naive ways to do this, but they seems
very inefficient; I can think of clever ways to do this,
but they would be approximate and probably yield
only a partial decomposition. 

Any standard literature I should know?

Best,

		Ph.

Re: [Slightly OT] SVD etc on Map/Reduce?

[Ted Dunning <te...@gmail.com>]

On Fri, Jan 15, 2010 at 8:05 PM, Philipp K. Janert <ja...@ieee.org> wrote:

> > > So, I am wondering whether people in the numerical
> > > analysis community have started to think in this
> > > direction and what they have come up with so far
> > > (if anything).
> >
> > I don't think that the numerical analysis community has turned their
> > attention much to map-reduce yet.
>
> One other major consumer of large, sparse matrix
> operations are people dealing with partial differential
> equations.


Yes.  And to the degree that large parallel relaxation methods would work
for their solution, map-reduce would be a natural answer.  Relaxation
techniques are, of course, simply a power method in disguise.


> And the Linear Programming/Optimization
> people also have algorithmically non-trivial, large
> problems, that might (just might) be amenable to M/R.
>

These techniques might work, but my guess is that it would require
substantially different techniques than are currently used.  There are a
fair number of restatements of linear programming as some form of gradient
descent, but these techniques can be very difficult to parallelize using
map-reduce.  The Pegasos algorithm for SVM is an example of a projection
technique and SVM is essentially a form of constrained quadratic
optimization.  It is not clear how to parallelize the Pegasos algorithm.
The SGD family are another example.  L-1 regularized logistic regression can
be restated as a linearly constrained optimization problem (was originally
stated that way, actually), but the gradient descent algorithm currently
used is inherently difficult to parallelize to any great degree.  Both
Pegasos and SGD can use multi-core machines and may be able to use GPU's
well, but larger scale parallelism is really hard to do for either.  Happily
both algorithms are really, really fast on sequential machines.  The future
may involve just be solving a gazillion different gradient descent problems
at the same time.


> On the other hand, I would not expect physics
> simulations to work well - the communication
> overhead will kill you (it did not work very well on
> the Cray, back in the day, and the problems have
> not changed.)


The problems haven't, but the techniques for some kinds of physics
simulations have changed dramatically.  Quasi-static electromagnetic
propagation problems can be cast as approximately low rank matrix problems
which can probably be handled using map-reduce derived decompositions.

There has been some interesting work in facilitating n-body computations on
map-reduce architectures:
ftp://ftp.cs.washington.edu/tr/2009/06/UW-CSE-09-06-01.PDF

Remember also that hadoop isn't the only map-reduce architecture around.
There are now MPI-based implementations.  The virtues of map-reduce still
apply where-ever you need simple robust parallel architecture (if your
algorithm fits).




-- 
Ted Dunning, CTO
DeepDyve

Re: [Slightly OT] SVD etc on Map/Reduce?

["Philipp K. Janert" <ja...@ieee.org>]

Thanks for the info.

[snip]

> > So, I am wondering whether people in the numerical
> > analysis community have started to think in this
> > direction and what they have come up with so far
> > (if anything).
>
> I don't think that the numerical analysis community has turned their
> attention much to map-reduce yet.

One other major consumer of large, sparse matrix
operations are people dealing with partial differential
equations. And the Linear Programming/Optimization
people also have algorithmically non-trivial, large
problems, that might (just might) be amenable to M/R.

On the other hand, I would not expect physics 
simulations to work well - the communication 
overhead will kill you (it did not work very well on 
the Cray, back in the day, and the problems have 
not changed.)

>
> > This is not a question about Mahout, and I admit that
> > it is therefore a little OT for this list, on the other hand,
> > I would assume that the members of this list would be
> > the first people to know about progress in this area...
>
> It is entirely on-topic.  The biggest news I know of is the stochastic
> decomposition stuff that I mentioned before.

I see. Thanks again for the info.

Best,

		Ph.

Re: [Slightly OT] SVD etc on Map/Reduce?

[Ted Dunning <te...@gmail.com>]

On Fri, Jan 15, 2010 at 6:59 AM, Philipp K. Janert <ja...@ieee.org> wrote:

>
> Computational Linear Algebra is an incredibly
> well established field.
>

Indeed.


> Now we have M/R as a real option for day-to-day
> work.
>

Yes.


> But I could imagine that the best way to use M/R
> to do computational Linear Algebra might not
> consist of "naive" adaptions of classical algorithms
> to M/R, but in the development of different algos,
> that take advantage of M/R, or in the rediscovery
> of existing algos that are of little importance in
> classical applications, but that all of a sudden
> make a lot of sense in a M/R context.
>

Absolutely.

Another thing that is happening is that the important problems are different
at the scale of map-reduce.  Once upon a time, solving 300x300 dense systems
was very important.  That makes no sense on a large cluster because the
overhead dominates the computation.  Better to use a single core of what is
now a single machine.

Right now, the major driver of numerical computation by users of map-reduce
clusters is machine learning on sparse data.  For that problem, approximate
SVD is a very important problem.  This has implications in graph algorithms,
search and recommendations at the least.  The traditional approach to this
is Lanczos' algorithm or other Krylov subspace technique.  These algorithms
are very difficult to parallelize at the level of map-reduce on
shared-nothing processors.

On the other hand, the stochastic decomposition algorithms appear ideally
suited to map-reduce.

This is exactly an example of what you hypothesize above ... poorly known
algorithms or facts suddenly gain new prominence in a new computational
paradigm.

Counter example of well-known algorithms that port very well to map-reduce
with few changes are all the flavors of the E-M algorithm.  K-means for
instance is very easy to port and runs very well in a distributed
environment.

Other algorithms for which no map-reduce efficient parallel is known include
stochastic gradient descent, the Pegasos fast SVM algorithm,
Rao-Blackwellized Gibb's sampling for Latent Dirichlet Allocation, many
Metropolis algorithms and many others.  The problems are often not the
obvious compute/communicate ratio in these problems, but rather that since
the algorithms are highly iterative, it is difficult to get different
processors to do sufficiently distinct work so that their efforts add up to
significantly more than what one highly threaded machine could do.


So, I am wondering whether people in the numerical
> analysis community have started to think in this
> direction and what they have come up with so far
> (if anything).
>

I don't think that the numerical analysis community has turned their
attention much to map-reduce yet.


> This is not a question about Mahout, and I admit that
> it is therefore a little OT for this list, on the other hand,
> I would assume that the members of this list would be
> the first people to know about progress in this area...
>

It is entirely on-topic.  The biggest news I know of is the stochastic
decomposition stuff that I mentioned before.

Re: [Slightly OT] SVD etc on Map/Reduce?

["Philipp K. Janert" <ja...@ieee.org>]

Let me try to clarify:

Computational Linear Algebra is an incredibly 
well established field.

Now we have M/R as a real option for day-to-day
work.

But I could imagine that the best way to use M/R
to do computational Linear Algebra might not 
consist of "naive" adaptions of classical algorithms
to M/R, but in the development of different algos,
that take advantage of M/R, or in the rediscovery
of existing algos that are of little importance in 
classical applications, but that all of a sudden 
make a lot of sense in a M/R context.

So, I am wondering whether people in the numerical
analysis community have started to think in this
direction and what they have come up with so far
(if anything).

This is not a question about Mahout, and I admit that
it is therefore a little OT for this list, on the other hand, 
I would assume that the members of this list would be 
the first people to know about progress in this area...

Best,

		Ph.





On Thursday 14 January 2010 10:26:17 pm Ted Dunning wrote:
> On Thu, Jan 14, 2010 at 10:09 PM, Philipp K. Janert <ja...@ieee.org> wrote:
> > > If you mean matrix factorization, take a look at this:
> > > http://arxiv.org/abs/0909.4061v1
> >
> > That seems to support my earlier hunch that
> > efficient implementations of such factorizations
> > on M/R would likely be approximate only or
> > partial (ie yielding the largest of the eigenvalues,
> > not necessarily the entire spectrum).
>
> For very large sparse problems, approximate decompositions are generally
> preferred.  Due to limited accuracy in the input, only the first several
> eigenvectors can be extracted at all.  Moreover, many important problems
> have very large apparent dimensionality, but limited actual rank.   Neither
> of these characteristics is a characteristic of map-reduce in the
> slightest.
>
>  > It is the common sense of those on this mailing list that these kinds of
>  >
> > > algorithms could be done using map-reduce.
> >
> > I am not sure what you are trying to tell me here.
>
> I am trying to say that we don't yet have working implementations.  There
> should be a k-means implementation that use these techniques before long.
> You would be very welcome to try your hand at some other of the algorithms
> and I am sure that you would have quite a lot of support from the mailing
> list.
>
> You comments puzzle me, though.  Do you have an application in mind?  Was
> there something you were particularly looking for?

Re: [Slightly OT] SVD etc on Map/Reduce?

[Ted Dunning <te...@gmail.com>]

On Thu, Jan 14, 2010 at 10:09 PM, Philipp K. Janert <ja...@ieee.org> wrote:

> > If you mean matrix factorization, take a look at this:
> > http://arxiv.org/abs/0909.4061v1
>
> That seems to support my earlier hunch that
> efficient implementations of such factorizations
> on M/R would likely be approximate only or
> partial (ie yielding the largest of the eigenvalues,
> not necessarily the entire spectrum).
>

For very large sparse problems, approximate decompositions are generally
preferred.  Due to limited accuracy in the input, only the first several
eigenvectors can be extracted at all.  Moreover, many important problems
have very large apparent dimensionality, but limited actual rank.   Neither
of these characteristics is a characteristic of map-reduce in the slightest.


 > It is the common sense of those on this mailing list that these kinds of
> > algorithms could be done using map-reduce.
>
> I am not sure what you are trying to tell me here.


I am trying to say that we don't yet have working implementations.  There
should be a k-means implementation that use these techniques before long.
You would be very welcome to try your hand at some other of the algorithms
and I am sure that you would have quite a lot of support from the mailing
list.

You comments puzzle me, though.  Do you have an application in mind?  Was
there something you were particularly looking for?

-- 
Ted Dunning, CTO
DeepDyve

Re: [Slightly OT] SVD etc on Map/Reduce?

["Philipp K. Janert" <ja...@ieee.org>]

On Thursday 14 January 2010 10:04:17 pm you wrote:
> What do you mean by operator splittings?
>
> If you mean matrix factorization, take a look at this:
> http://arxiv.org/abs/0909.4061v1

That seems to support my earlier hunch that 
efficient implementations of such factorizations
on M/R would likely be approximate only or 
partial (ie yielding the largest of the eigenvalues,
not necessarily the entire spectrum).

>
> It is the common sense of those on this mailing list that these kinds of
> algorithms could be done using map-reduce.

I am not sure what you are trying to tell me here.

>
> On Thu, Jan 14, 2010 at 7:57 PM, Philipp K. Janert <ja...@ieee.org> wrote:
> > Can you point me to some resources for algorithms
> > that implement "standard" linear algebra operations
> > (mostly operator splittings) efficiently (!) on M/R?

Re: [Slightly OT] SVD etc on Map/Reduce?

[Ted Dunning <te...@gmail.com>]

What do you mean by operator splittings?

If you mean matrix factorization, take a look at this:
http://arxiv.org/abs/0909.4061v1

It is the common sense of those on this mailing list that these kinds of
algorithms could be done using map-reduce.

On Thu, Jan 14, 2010 at 7:57 PM, Philipp K. Janert <ja...@ieee.org> wrote:

> Can you point me to some resources for algorithms
> that implement "standard" linear algebra operations
> (mostly operator splittings) efficiently (!) on M/R?
>



-- 
Ted Dunning, CTO
DeepDyve