[jira] [Commented] (SPARK-2426) Quadratic Minimization for MLlib ALS

["Debasish Das (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/SPARK-2426?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14095232#comment-14095232 ] 

Debasish Das commented on SPARK-2426:
-------------------------------------

Hi Xiangrui,

The branch is ready for an initial review. I will do lot of clean-up this week.

https://github.com/debasish83/spark/commits/qp-als

optimization/QuadraticMinimizer.scala is the placeholder for all QuadraticMinimization. 

Right now we support 5 features:

1. Least square
2. Least square with positivity
3. Least square with bounds : generalization of positivity
4. Least square with equality and positivity/bounds for LDA/PLSA
5. Least square + L1 constraint for sparse NMF

There are lot many regularization in Proximal.scala which can be re-used in mllib updater...L1Updater is an example of Proximal algorithm.

I feel we should move NNLS into QuadraticMinimizer as well and clean ALS.scala as you have suggested before...

QuadraticMinimizer is optimized for direct solve right now (cholesky / lu based on problem we are solving)

The CG core from NNLS should be used for iterative solve when ranks are high...I need a different variant of CG for Formulation 4 so NNLS CG is not sufficient for all the formulations.

Right now I am experimenting with ADMM rho and lambda values so that the NNLS iterations are at par with Least square with positivity. 

I will publish results from the comparisons.

I will also publish comparisons with PDCO, ECOS (IPM) and MOSEK with ADMM variants used in this branch...

For recommendation use-case, I expect to produce Jellylish L1 ball projection results on netflix/movielens dataset using Formulation 5.

Thanks.
Deb

> Quadratic Minimization for MLlib ALS
> ------------------------------------
>
>                 Key: SPARK-2426
>                 URL: https://issues.apache.org/jira/browse/SPARK-2426
>             Project: Spark
>          Issue Type: New Feature
>          Components: MLlib
>    Affects Versions: 1.0.0
>            Reporter: Debasish Das
>            Assignee: Debasish Das
>   Original Estimate: 504h
>  Remaining Estimate: 504h
>
> Current ALS supports least squares and nonnegative least squares.
> I presented ADMM and IPM based Quadratic Minimization solvers to be used for the following ALS problems:
> 1. ALS with bounds
> 2. ALS with L1 regularization
> 3. ALS with Equality constraint and bounds
> Initial runtime comparisons are presented at Spark Summit. 
> http://spark-summit.org/2014/talk/quadratic-programing-solver-for-non-negative-matrix-factorization-with-spark
> Based on Xiangrui's feedback I am currently comparing the ADMM based Quadratic Minimization solvers with IPM based QpSolvers and the default ALS/NNLS. I will keep updating the runtime comparison results.
> For integration the detailed plan is as follows:
> 1. Add ADMM and IPM based QuadraticMinimization solvers to breeze.optimize.quadratic package.
> 2. Add a QpSolver object in spark mllib optimization which calls breeze
> 3. Add the QpSolver object in spark mllib ALS



--
This message was sent by Atlassian JIRA
(v6.2#6252)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org