Re: [mlpack] MVU Bug Fix GSOC
Hey Ryan, Sorry for the ambiguity. Basically what I did was just a shortlist of the major past topics related to LRSDP on Github. I didn't realise that the sparse and dense constraint is already implemented, which is great. By "detail constraints" I basically want to say is that it would be helpful to have some dataset that is guaranteed to not have any saddle point, i.e. having only local and global minima so that we can check the convergence of the LRSDP on problems not involving saddle point. Maybe it shouldn't be implemented as a constraint but just as something to keep in mind during the generation of the data. since sparse and dense constraints have already been implemented in MUV SDP then yeah I think a variadic template wouldn't be quite of help in this case. I haven't give much thought to this over the past few days as I was caught up with coursework and hackathon, but I will look further into the code base and give a detailed suggestion on whether it is possible to further constraint the question or pass on some useful information to the SDP class this week. Best Regards, Daniel Li From: Ryan Curtin <r...@ratml.org> Sent: 02 April 2018 16:18:17 To: LI Xuran Cc: mlpack@lists.mlpack.org Subject: Re: [mlpack] MVU Bug Fix GSOC On Mon, Mar 26, 2018 at 08:23:20PM +, LI Xuran wrote: > >I took a quick look at your proposal and I think it is relatively clear > >and sufficiently detailed. I am not clear on exactly what you mean by > >"5. it might also be useful to write an algorithm to pre-process the > >dataset to make it smoother and convex"---note that the LRSDP algorithm > >breaks the convexity of SDPs and it is a nonconvex optimization. > > Thanks a lot for the feedback! Yeah, you are right about the LRSDP is > a nonconvex optimization, what I intend to say is that during the > process of sample generation, it might be helpful if we can have some > constraints (say convex and closed? I am not too sure about the detail > constraints yet but there is a theorem in the paper of local minima > specifying it ) on the data to guarantee that an optimal solution can > always be reached on the sample created, both by LRSDP and a dual > solver. > > I 've gone through the rest of papers and Posts about LRSDP on Github > during the past few days, as I am interested in what effort have been > made to debug it. Do you think the following ideas would be helpful > to the debug project: > > 1. refactor the SDP class to allow detail constraints specified in input. > 2. create variable template to specify linear/sparse/dense > constraints on input or A(constraint matrix) and support evaluation > of Tr(A_i * UU^T) > > > I didn't add these two to my proposal, but if you think implementing > those would be useful than I can also look into it and take it as a > part of the project. Maybe I can try to approach it during the > community bound. Hi Daniel, I realize my response is past the deadline here, so the proposal can't be modified. Still I did want to ask for a little clarification of what you mean to be sure I understand correctly. For the refactoring you are proposing, can you tell me what more of what you mean by "allow detail constraints specified in input"? I think the MVU SDP can be expressed only with sparse and dense constraints, which we already have implemented. So I'm not sure what advantage using variadic templates would get us; can you clarify that please? Thanks, Ryan -- Ryan Curtin| "Happy premise #2: There is no giant foot trying r...@ratml.org | to squash me." - Kit Ramsey The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ mlpack mailing list mlpack@lists.mlpack.org http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
Re: [mlpack] MVU Bug Fix GSOC
Hey Ryan, Just an update on what I 've done with the project over the weekend. I watched some videos on youtube about how to decide whether a solution is a saddle point in a multivariable function...but it would take some hard work to generalize that method to nonlinear case. I've gone over the codebase of methods/mvu and optimizer over the weekend. I find the template initialization a bit confusing with lots of <<<>>> but the other parts are mostly fine. I will need to spend some time matching the algorithm suggested in the paper with the actual code we have but this shouldn't be hard. And currently I don't think any further constraints to the SDP class are needed. Best Regards Daniel Li From: Ryan Curtin <r...@ratml.org> Sent: 04 April 2018 20:53:52 To: LI Xuran Cc: mlpack@lists.mlpack.org Subject: Re: [mlpack] MVU Bug Fix GSOC On Wed, Apr 04, 2018 at 10:01:11AM +, LI Xuran wrote: > Hey Ryan, > > Sorry for the ambiguity. Basically what I did was just a shortlist of > the major past topics related to LRSDP on Github. I didn't realise > that the sparse and dense constraint is already implemented, which is > great. > > By "detail constraints" I basically want to say is that it would be > helpful to have some dataset that is guaranteed to not have any saddle > point, i.e. having only local and global minima so that we can check > the convergence of the LRSDP on problems not involving saddle point. > Maybe it shouldn't be implemented as a constraint but just as > something to keep in mind during the generation of the data. > > since sparse and dense constraints have already been implemented in > MUV SDP then yeah I think a variadic template wouldn't be quite of > help in this case. I haven't give much thought to this over the past > few days as I was caught up with coursework and hackathon, but I will > look further into the code base and give a detailed suggestion on > whether it is possible to further constraint the question or pass on > some useful information to the SDP class this week. Hi Daniel, I hope the hackathon was enjoyable. Thanks for the clarifications here, I think I understand better now. I think it may be difficult to devise an LRSDP problem that has no saddle points (and prove that it has no saddle points). Thanks, Ryan -- Ryan Curtin| "Bye-bye, goofy woman. I enjoyed repeatedly r...@ratml.org | throwing you to the ground." - Ben Jabituya The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ mlpack mailing list mlpack@lists.mlpack.org http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
Re: [mlpack] MVU Bug Fix GSOC
Hi Ryan, >I took a quick look at your proposal and I think it is relatively clear >and sufficiently detailed. I am not clear on exactly what you mean by >"5. it might also be useful to write an algorithm to pre-process the >dataset to make it smoother and convex"---note that the LRSDP algorithm >breaks the convexity of SDPs and it is a nonconvex optimization. Thanks a lot for the feedback! Yeah, you are right about the LRSDP is a nonconvex optimization, what I intend to say is that during the process of sample generation, it might be helpful if we can have some constraints (say convex and closed? I am not too sure about the detail constraints yet but there is a theorem in the paper of local minima specifying it ) on the data to guarantee that an optimal solution can always be reached on the sample created, both by LRSDP and a dual solver. I 've gone through the rest of papers and Posts about LRSDP on Github during the past few days, as I am interested in what effort have been made to debug it. Do you think the following ideas would be helpful to the debug project: 1. refactor the SDP class to allow detail constraints specified in input. 2. create variable template to specify linear/sparse/dense constraints on input or A(constraint matrix) and support evaluation of Tr(A_i * UU^T) I didn't add these two to my proposal, but if you think implementing those would be useful than I can also look into it and take it as a part of the project. Maybe I can try to approach it during the community bound. Thanks again and Best Regards. Daniel Li The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ mlpack mailing list mlpack@lists.mlpack.org http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
Re: [mlpack] MVU Bug Fix GSOC
Dear Ryan, I am currently working on my proposal for the Fixes to MVU and low-rank semidefinite programs and have come up with the following ideas: 1.generate random simple dataset, and compare normal MVU with MVU +LRSDP on it. do visualization of the procedure and the result in 2d/3d. 2. write unit tests and substitution for the original code in mlpack's MVU implementation and check their correctness over processing of the above datasets. 3. base on the observation of the result of 1 and 2, create datasets that particularly points out the issue ... and check step by step on that sample 4.(or maybe datasets with a special property such that it should always converge by an implementation of MVU + LRSDP and check if the expected result is met ) do you think any of the above ideas worth a try? Thanks! Daniel Li From: LI Xuran Sent: 17 March 2018 17:47:09 To: mlpack@lists.mlpack.org Subject: MVU Bug Fix GSOC Hello Ryan, I am Daniel Li, a second-year student studying Artificial in the University of Edinburgh. I write fluent c++ code and is interested in taking up the quest to fix bugs regarding MVU and semidefinite programming in mlpack. I've read about scalable semidefinite manifold learning and other articles and set up mlpack on my own computer. Could you give me some advice as for where to start my research on the project as I familiar myself with the code base? Also is it a good idea to implement the MVU with dual-tree algorithm to compare with the current version of MVU using LRSDP? Thanks! Daniel Li The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ mlpack mailing list mlpack@lists.mlpack.org http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
[mlpack] MVU Bug Fix GSOC
Hello Ryan, I am Daniel Li, a second-year student studying Artificial in the University of Edinburgh. I write fluent c++ code and is interested in taking up the quest to fix bugs regarding MVU and semidefinite programming in mlpack. I've read about scalable semidefinite manifold learning and other articles and set up mlpack on my own computer. Could you give me some advice as for where to start my research on the project as I familiar myself with the code base? Also is it a good idea to implement the MVU with dual-tree algorithm to compare with the current version of MVU using LRSDP? Thanks! Daniel Li The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ mlpack mailing list mlpack@lists.mlpack.org http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
Re: [mlpack] MVU Bug Fix GSOC
Hi Ryan, Thanks a lot for the advice and sorry for late reply. I spent the past two days to went through most of the papers and it really helps. Apart from the previous idea: 1.generate random simple dataset, and compare normal MVU using mlpack Primal dualsolver on it. compare it with the result of MVU +LRSDP. 2.write unit tests and substitution for the original code in LRSDP, check their correctness over processing of the above datasets. I also have some new ideas coming up: 1.it is mentioned in multiple papers that the selection of parameters for the penalty, knn, and learning rate etc is critical for the convergence of the algorithm. Thus, I think it would be helpful to either implement a dynamical parameter adjusting algorithm or to check manually on the variables in the cases where the algorithm is not convergent. 2. there are several propositions and characteristics that a functioning LRSDP should meet mentioned in the papers.(i.e.nonzero duality gap and XS==0 for optimal solution etc) I am making a list of these properties and the goal is that to implement tests to check that these properties would be met in each iteration. 3. a not recommended alternative would be to change the implementation in LRSDP, for example, change the optimization criteria to search for the maximum distance of furthest neighbor, or to integrate a dual approach into the original code. The attractiveness of such action is that it would provide a theoretical guarantee that the algorithm would converge and have an optimal result(while by using LRSDP alone we only have optimal results on most cases), but I don't quite like it because it might bring side effects and deficiency on runtime. Also, I think it is not guaranteed to work as it was only proposed as an alternative in the papers. So I am currently thinking of taking up this approach as a last alternative if no bug is found in previous sections. So that is all I had for now, Would you think some of it worth a try? I will read the rest of the pdf tomorrow, and change my proposal according to your suggestion. Best Wishes, Daniel Li From: LI Xuran Sent: 18 March 2018 20:15:57 To: mlpack@lists.mlpack.org Subject: Re: MVU Bug Fix GSOC Dear Ryan, I am currently working on my proposal for the Fixes to MVU and low-rank semidefinite programs and have come up with the following ideas: 1.generate random simple dataset, and compare normal MVU with MVU +LRSDP on it. do visualization of the procedure and the result in 2d/3d. 2. write unit tests and substitution for the original code in mlpack's MVU implementation and check their correctness over processing of the above datasets. 3. base on the observation of the result of 1 and 2, create datasets that particularly points out the issue ... and check step by step on that sample 4.(or maybe datasets with a special property such that it should always converge by an implementation of MVU + LRSDP and check if the expected result is met ) do you think any of the above ideas worth a try? Thanks! Daniel Li From: LI Xuran Sent: 17 March 2018 17:47:09 To: mlpack@lists.mlpack.org Subject: MVU Bug Fix GSOC Hello Ryan, I am Daniel Li, a second-year student studying Artificial in the University of Edinburgh. I write fluent c++ code and is interested in taking up the quest to fix bugs regarding MVU and semidefinite programming in mlpack. I've read about scalable semidefinite manifold learning and other articles and set up mlpack on my own computer. Could you give me some advice as for where to start my research on the project as I familiar myself with the code base? Also is it a good idea to implement the MVU with dual-tree algorithm to compare with the current version of MVU using LRSDP? Thanks! Daniel Li The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ mlpack mailing list mlpack@lists.mlpack.org http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
