apache/incubator-spark — pull request #452 by ajtulloch (2014-01-16 17:58:07+00:00)
Title: [MLlib] Generic ADMM implementation (with L1-regularized logistic regression example)

Summary:

This diff implements the Alternating Direction Method of
Multipliers (ADMM) for solving distributed convex optimization problems
in MLlib, following Boyd et. al. in
http://www.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf.

The core is a generic optimization driver at
mllib/optimization/ADMMOptimizer.scala, which takes an instance of an
ADMMUpdater. Individual inference algorithms (sparse logistic
regression, lasso regression, SVMs, etc) implement the ADMM updater
interface.

This diff includes an implementation of this interface for sparse
logistic regression, following the equations given in (8.2.2) of Boyd
et. al. To solve the L^2 regularized logistic regression problem
subproblem in the mappers, we use the implementation of L-BFGS given in
ScalaNLP/breeze (Apache 2.0 licensed).

Implementing other inference algorithms (e.g. SVM as in 8.2.3 of Boyd
et. al) is trivial - see https://github.com/ajtulloch/admmlrspark/
for (preliminary) implementations of SVM and lasso regression.

This implementation isn't heavily optimized for performance - though
that should be easy to improve - although each component is fairly well
tested.

I'm not sure if anyone is working on ADMM in Spark (it seems like a nice
generic optimization procedure to have in the framework), but if this is
already being taken care of, or someone else would prefer to take this
on, let me know.

TODO

- Further testing, performance improvements
- Algorithmic improvements (over-relaxation, multiple (x, u) updates
per z update, etc from Section (3.4) in Boyd et. al.
- Implement and Java, Python bindings.

NB: this is the first non-trivial Scala/Java code I've ever written, so
it's most likely unidiomatic, unperformant, etc.

Test Plan:
- QuickCheck verification of most of the pure functions, and
verification that convexity etc holds for the objective/gradient
functions in the sparse LR case.

- QuickCheck verification that the sparse logistic regression recovers
data of the form 'a + bx' for varying values of a and b in the case
where the regularizer is zero.

- Planning on adding QuickCheck tests to verify we have correct
behaviour as regularization strength changes, since I'm not overly
confident in the correctness of that code yet.

Reviewers:

CC: