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 Summit....IPM 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 <minnesota...@gmail.com> 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 <debasish.da...@gmail.com> > 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 <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 > > > > > > > > > > > > > > > > > > > > >
