Hi, I am coming up with an iterative solver for Equality and bound constrained quadratic minimization...
I have the cholesky versions running but cholesky does not scale for large dimensions but works fine for matrix factorization use-cases where ranks are low.. Minimize 0.5x'Px + q'x s.t Aeq x = beq lb <= x <= ub Based on your decomposition you will end up using linear CG in x-update or NLCG/BFGS with bounds...I am not sure which one is better unless I see both of them running on datasets.... I am hoping we can re-use the solver for SVM variants... Could you please point to some implementation references for Nystrom approximations or kernel mappings ? Thanks. Deb On Sat, Jun 28, 2014 at 11:26 AM, Tom Vacek <minnesota...@gmail.com> wrote: > What flavor of SVM are you trying to support? LSSVM doesn't need a bound > constraint, but most other formulations do. There have been ideas for > bound-constrained CG, though bounded LBFGS is more common. I think code > for Nystrom approximations or kernel mappings would be more useful. > > > On Fri, Jun 27, 2014 at 5:42 PM, Debasish Das <debasish.da...@gmail.com> > wrote: > > > Thanks David...Let me try it...I am keen to see the results first and > later > > will look into runtime optimizations... > > > > Deb > > > > > > > > > > > > On Fri, Jun 27, 2014 at 3:12 PM, David Hall <d...@cs.berkeley.edu> > wrote: > > > > > I have no ideas on benchmarks, but breeze has a CG solver: > > > > > > > > > https://github.com/scalanlp/breeze/tree/master/math/src/main/scala/breeze/optimize/linear/ConjugateGradient.scala > > > > > > > > > > > > https://github.com/scalanlp/breeze/blob/e2adad3b885736baf890b306806a56abc77a3ed3/math/src/test/scala/breeze/optimize/linear/ConjugateGradientTest.scala > > > > > > It's based on the code from TRON, and so I think it's more targeted for > > > norm-constrained solutions of the CG problem. > > > > > > > > > > > > > > > > > > > > > > > > > > > On Fri, Jun 27, 2014 at 5:54 PM, Debasish Das < > debasish.da...@gmail.com> > > > wrote: > > > > > > > Hi, > > > > > > > > I am looking for an efficient linear CG to be put inside the > Quadratic > > > > Minimization algorithms we added for Spark mllib. > > > > > > > > With a good linear CG, we should be able to solve kernel SVMs with > this > > > > solver in mllib... > > > > > > > > I use direct solves right now using cholesky decomposition which has > > > higher > > > > complexity as matrix sizes become large... > > > > > > > > I found out some jblas example code: > > > > > > > > https://github.com/mikiobraun/jblas-examples/blob/master/src/CG.java > > > > > > > > I was wondering if mllib developers have any experience using this > > solver > > > > and if this is better than apache commons linear CG ? > > > > > > > > Thanks. > > > > Deb > > > > > > > > > >
