scalanlp/breeze — pull request #321 by debasish83 (2014-11-01 02:42:35+00:00)
Title: [WIP] Quadratic Minimization solver using ADMM based Proximal Algorithm

@dlwh @mengxr

Refactoring the QuadraticMinimizer implementation for integration into Spark mllib ALS. The solver is used to solve Quadratic minimization using several constraints (positivity, bounds, elastic net, equality and bounds).

More details are in the following Spark JIRA and PR:

Spark JIRA https://issues.apache.org/jira/browse/SPARK-2426
Spark PR https://github.com/apache/spark/pull/2705

I also refactored NNLS to breeze since NNLS can also solve x'Hx + c'x s.t x >= 0 and it is a special case of the features that ProximalMinimizer supports.

I used jblas since that's what mllib ALS uses and so in this cleanup we also want to move ALS to breeze matrices and therefore I will clean it up.

Matlab comparisons of the proximal solver is presented over here. We are at par with MOSEK till ranks ~ 1000 but due to ADMM we have the luxury of moving x-solve to each worker later once we validate the solver.
https://github.com/debasish83/ecos/blob/master/README.md

In scala version the runtime numbers can be obtained as follows:

run-class breeze.optimize.quadratic.ProximalMinimizer 1000 1 1.0 0.99

rank=1000, equality=1.0 lambda=1.0 beta=0.99
L1regularization = lambda*beta L2regularization = lambda*(1-beta)
Generating randomized QPs with rank 1000 equalities 1
sparseQp 88.423 ms iterations 45 converged true
posQp 181.369 ms iterations 121 converged true
boundsQp 175.733 ms iterations 121 converged true
Qp Equality 2805.564 ms iterations 2230 converged true

The next steps are the following:

1. Refactor using breeze code style
2. Use breeze dense/sparse matrices
3. Move tests from main to test
4. Iterative version taking DiffFunction and not dense gram so that we can scale to large ranks and handle convex functions in mllib ALS (KL divergence loss, hinge loss, huber loss)

For 4, I will need BFGS/CG core but that's not really critical for recommendation use-cases. Basically lot of code will be re-used from breeze.optimize. Also we have a baseline direct solver for comparisons which is critical for the iterative solver validation.