Re: Linear CG solver
Hey, We're actually working on similar ideas in the AMPlab with spark - for example we've got some image classification pipelines built on this idea - http://www.eecs.berkeley.edu/~brecht/papers/07.rah.rec.nips.pdf Approximating kernel methods via random projections hit with nonlinearity. Additionally, block coordinate descent seems to work pretty well for these scenarios where you end up with lots of features. An advantage of this approach in spark is that you can avoid materializing the whole data matrix if you're working on a subset of columns at a time. We're hoping to have some code out for public consumption later in the summer. - Evan > On Jun 28, 2014, at 12:12 PM, Tom Vacek wrote: > > What is your general solver? IPM or simplex or something else? I have > seen a lot of attempts to apply iterative solvers for the subproblems on > those without much luck because the conditioning of the linear systems gets > worse and worse near the optimum. IPOPT (interior point method) has an > LBFGS subproblem solver built in, so maybe it's worth a try to see if the > approach would meet your needs. Methods more amenable to iterative > subproblem solvers might be augmented Lagrangian, nonlinear rescaling, or > Murty's ( > http://www.researchgate.net/publication/250180549_A_New_Practically_Efficient_Interior_Point_Method_for_Quadratic_Programming) > methods. > > This blog post gives a decent introduction to the kernel approximation > topic: > http://peekaboo-vision.blogspot.com/2012/12/kernel-approximations-for-efficient.html. > Missing is mention of the research into how to choose the best set of > prototype vectors. (I believe Kmeans on the data is practically best.) In > the approximation domain, "Fastfood" by Smola, et al. is a neat idea. > That's something I've thought about for MLLib, but I think the numeric > support is lacking in Java land. > > > On Sat, Jun 28, 2014 at 1:47 PM, Debasish Das > wrote: > >> 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 >> 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 >>> 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 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 >>
Re: Linear CG solver
Thanks Tom for the pointers... I have a IPM running on the JVM which uses SOCP formulation for the quadratic program I wrote above We are going to show the details of it at the SummitIPM runtimes and accuracy give a baseline for the problem that we are solving... Now we are trying to see how to come up with efficient versions for cases where the constraints are not that many or not very complicated...which is what most ML problems have...The idea is to use ADMM decomposition for them... If the constraints are LP style complex, it is better to use the IPM with the SOCP directly... Let me look into the blog and update you more...with jblas and breeze-netlib-java I doubt there is any numerics that we cannot do on JVM !...With these packages we call BLAS libraries from fortran...Missing is sparse linear algebra from Tim Davis which will be exposed to the JVM in the IPM package that I built... On Sat, Jun 28, 2014 at 12:12 PM, Tom Vacek wrote: > What is your general solver? IPM or simplex or something else? I have > seen a lot of attempts to apply iterative solvers for the subproblems on > those without much luck because the conditioning of the linear systems gets > worse and worse near the optimum. IPOPT (interior point method) has an > LBFGS subproblem solver built in, so maybe it's worth a try to see if the > approach would meet your needs. Methods more amenable to iterative > subproblem solvers might be augmented Lagrangian, nonlinear rescaling, or > Murty's ( > > http://www.researchgate.net/publication/250180549_A_New_Practically_Efficient_Interior_Point_Method_for_Quadratic_Programming > ) > methods. > > This blog post gives a decent introduction to the kernel approximation > topic: > > http://peekaboo-vision.blogspot.com/2012/12/kernel-approximations-for-efficient.html > . > Missing is mention of the research into how to choose the best set of > prototype vectors. (I believe Kmeans on the data is practically best.) In > the approximation domain, "Fastfood" by Smola, et al. is a neat idea. > That's something I've thought about for MLLib, but I think the numeric > support is lacking in Java land. > > > On Sat, Jun 28, 2014 at 1:47 PM, Debasish Das > wrote: > > > 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 > > 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 > > > 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 matri
Re: Linear CG solver
What is your general solver? IPM or simplex or something else? I have seen a lot of attempts to apply iterative solvers for the subproblems on those without much luck because the conditioning of the linear systems gets worse and worse near the optimum. IPOPT (interior point method) has an LBFGS subproblem solver built in, so maybe it's worth a try to see if the approach would meet your needs. Methods more amenable to iterative subproblem solvers might be augmented Lagrangian, nonlinear rescaling, or Murty's ( http://www.researchgate.net/publication/250180549_A_New_Practically_Efficient_Interior_Point_Method_for_Quadratic_Programming) methods. This blog post gives a decent introduction to the kernel approximation topic: http://peekaboo-vision.blogspot.com/2012/12/kernel-approximations-for-efficient.html. Missing is mention of the research into how to choose the best set of prototype vectors. (I believe Kmeans on the data is practically best.) In the approximation domain, "Fastfood" by Smola, et al. is a neat idea. That's something I've thought about for MLLib, but I think the numeric support is lacking in Java land. On Sat, Jun 28, 2014 at 1:47 PM, Debasish Das wrote: > 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 > 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 > > 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 > > 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 > > > > > > > > > > > > > > >
Re: Linear CG solver
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 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 > 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 > 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 > > > > > > > > > >
Re: Linear CG solver
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 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 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 > > 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 > > > > > >
Re: Linear CG solver
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 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 > 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 > > >
Re: Linear CG solver
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 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 >
