[
https://issues.apache.org/jira/browse/SPARK-2426?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14243149#comment-14243149
]
Debasish Das commented on SPARK-2426:
-------------------------------------
[~mengxr] as per our discussion, QuadraticMinimizer and NNLS are both added to
breeze and updated with breeze DenseMatrix and DenseVector...Inside breeze I
did some interesting comparisons and that motivated me to port NNLS to breeze
as well...I added all the testcases for QuadraticMinimizer and NNLS as well
based on my experiments with MovieLens dataset...
Here is the PR: https://github.com/scalanlp/breeze/pull/321
To run the Quadratic programming variants in breeze:
runMain breeze.optimize.quadratic.QuadraticMinimizer 100 1 0.1 0.99
regParam = 0.1, beta = 0.99 is Elastic Net parameter
It will randomly generate quadratic problems with 100 variables, 1 equality
constraint and lower/upper bounds. This format is similar to PDCO QP generator
(please look into my Matlab examples)
0.5x'Hx + c'x
s.t Ax = B,
lb <= x <= ub
1. Unconstrained minimization: breeze luSolve, cg and qp(dposv added to breeze
through this PR)
Minimize 0.5x'Hx + c'x
||qp - lu|| norm 4.312577233496585E-10 max-norm 1.3842793578078272E-10
||cg - lu|| norm 4.167925029822007E-7 max-norm 1.0053204402282745E-7
dim 100 lu 86.007 qp 41.56 cg 102.627
||qp - lu|| norm 4.267891623199082E-8 max-norm 6.681460718027665E-9
||cg - lu|| norm 1.94497623480055E-7 max-norm 2.6288773824489908E-8
dim 500 lu 169.993 qp 78.001 cg 443.044
qp is faster than cg for smaller dimensions as expected. I also tried
unconstrained BFGS but the results were not good. We are looking into it.
2. Elastic Net formulation: 0.5 x'Hx + c'x + (1-beta)*L2(x) +
beta*regParam*L1(x)
beta = 0.99 Strong L1 regParam=0.1
||owlqn - sparseqp|| norm 0.1653200701235298 inf-norm 0.051855911945906996
sparseQp 61.948 ms iters 227 owlqn 928.11 ms
beta = 0.5 average L1 regParam=0.1
||owlqn - sparseqp|| norm 0.15823773098501168 inf-norm 0.035153837685728107
sparseQp 69.934 ms iters 353 owlqn 882.104 ms
beta = 0.01 mostly BFGS regParam=0.1
||owlqn - sparseqp|| norm 0.17950035092790165 inf-norm 0.04718697692014828
sparseQp 80.411 ms iters 580 owlqn 988.313 ms
ADMM based proximal formulation is faster for smaller dimension. Even as I
scale dimension, I notice similar behavior that owlqn is taking longer to
converge and results are not same. Look for example in dim = 500 case:
||owlqn - sparseqp|| norm 10.946326189397649 inf-norm 1.412726586317294
sparseQp 830.593 ms iters 2417 owlqn 19848.932 ms
I validated ADMM through Matlab scripts so there is something funky going on in
OWLQN.
3. NNLS formulation: 0.5 x'Hx + c'x s.t x >= 0
Here are compared ADMM based proximal formulation with CG based projected
gradient in NNLS. NNLS converges much nicer but the convergence criteria does
not look same as breeze CG but they should be same.
For now I ported it to breeze and we can call NNLS for x >= 0 and
QuadraticMinimizer for other formulations
dim = 100 posQp 16.367 ms iters 284 nnls 8.854 ms iters 107
dim = 500 posQp 303.184 ms iters 950 nnls 183.543 ms iters 517
NNLS on average looks 2X faster !
4. Bounds formulation: 0.5x'Hx + c'x s.t lb <= x <= ub
Validated through Matlab scripts above. Here are the runtime numbers:
dim = 100 boundsQp 15.654 ms iters 284 converged true
dim= 500 boundsQp 311.613 ms iters 950 converged true
5. Equality and positivity: 0.5 x'Hx + c'x s.t \sum_i x_i = 1, x_i >=0
Validated through Matlab scripts above. Here are the runtime numbers:
dim = 100 Qp Equality 13.64 ms iters 184 converged true
dim = 500 Qp Equality 278.525 ms iters 890 converged true
With this change all copyrights are moved to breeze. Once it merges, I will
update the Spark PR. With this change we can move ALS code to Breeze
DenseMatrix and DenseVector as well....
My focus next will be to get a Truncated Newton running for convex cost since
convex cost is required for PLSA, SVM and Neural Net formulations...
I am still puzzled that why BFGS/OWLQN is not working well for the
unconstrained case/L1 optimization. If TRON works well for unconstrained case,
that's what I will use for NonlinearMinimizer. I am looking more into it.
> 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.3.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 QuadraticMinimizer and Proximal algorithms in mllib.optimization
> 2. Integrate QuadraticMinimizer in mllib ALS
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
