Hello, After I went through all the issues about MVU and LR-SDP, in particular, #370 <https://github.com/mlpack/mlpack/issues/370>, I find that LR-SDP is really a tough guy. It is necessary to summarise experiences of @rcurtin and @stephentu. I will dig into it, read source code and update my proposal.
Best regards, Kaiqiang On Sat, Mar 24, 2018 at 7:05 AM, kaiqiang Xu <[email protected]> wrote: > Hi, Ryan > > Sorry to borther you directly by mistake in last email. > I modified proposal and emphasize approaches. Now it has been submited to > GSoC. Can you check it and give me some feedback if available? > > Best regards, > > Kaiqiang > > > 2018-03-23 22:41 GMT+08:00 Ryan Curtin <[email protected]>: > >> On Fri, Mar 23, 2018 at 04:21:36PM +0800, kaiqiang Xu wrote: >> > I have read the papers recommended under ideas-page, and been >> fascinated by >> > their formulations, variants(e.g. MFNN) and implementions. >> > >> > Firstly, MVU/MFNU is a powerful method to reduce high dimensional data >> > which can be viewed as a more general PCA version. The paper mentions >> that >> > MVU/MFNU need to deal with all-nearst neighbor computation and >> > optimization. Especially, a technique based on dual-tree and L-BFGS to >> > solve the non-convex formulation of MVU allows MVU more scable. >> > >> > Secondly, SDPs is a definination to a class of optimization problems, >> and >> > interior point method applying to it is fast and converged. But >> scalability >> > is an issue. So taking advantage of low rank property of matrix, the >> > low-rank reformulation of SDPs can be solve via Burer-Monoteiro method. >> > Especially, in some conditions, the Burer-Monoteiro can get global >> optimal. >> > >> > Is there any error with respect to above summary? I'm glad to hear your >> > advice. >> > >> > Here I formulate some ideas: >> > >> > 1. >> > >> > Guarantee the correctness of MVU, which optimized by convex >> optimization >> > techniques. >> > 2. >> > >> > Check the correctness of implementation of LRSDP. Design several >> special >> > problem, such as the Lovasz theta SDP, the maximum cut SDP >> relaxation and >> > etc. Solving them by LRSDP and the spectral bundle method of >> Helmberg as >> > well as dual-scaling interior-point method of Benson mentioned in >> paper *A >> > Nonlinear Programming Algorithm for Solving Semidefinite Programs via >> > Low-rank Factorization* . >> > 3. >> > >> > Check the convergence of LRSDP under conditions mentioned in *The >> > non-convex Burer–Monteiro approach works on smooth semidefinite >> programs* >> > . In paper it should go convergence. Some special case should be >> created to >> > test this idea. >> > 4. >> > >> > Concatenate MVU and LRSDP, small dataset should be prepared to test. >> > Disable parameter auto-tunning, then check the convergence and >> compare its >> > result with idea(1) or other tools. If there is any problem >> happended, dig >> > into the optimization section. Hand computation is needed. My >> intrests in >> > optimization makes me never afraid of computation. >> > 5. >> > >> > if idea(4) is convinced, a big dataset should be employed to MVU and >> > LRSDP. Some extreme case may happened such as traping into local >> minima. >> > Here the paper applying MVU to time speach dataset may help me out. >> > >> > How do you think of the ideas above? Can you give me advice? Obviously I >> > have great passion to solve it. Later hours I will submit my draft of >> > proposal to GSoC, may you can give me some feedback. >> > >> > The paper *Local Minima and Convergence in Low-Rank Semidefinite >> > Programming* is very hard to understand. I will go through it with my >> > professor occupied optimization. I believe I can come up with new ideas >> and >> > improve my plan. >> >> Hi Kaiqiang, >> >> It sounds like you have formulated a good plan. I would suggest making >> your approach clear in your proposal, especially with what you will do >> if MVU+LRSDP does not converge (since I do not expect it to converge). >> >> Thanks, >> >> Ryan >> >> -- >> Ryan Curtin | "Wha' happened?" >> [email protected] | - Mike LaFontaine >> > >
_______________________________________________ mlpack mailing list [email protected] http://knife.lugatgt.org/cgi-bin/mailman/listinfo/mlpack
