[mlpack] Fix MVU+LRSDP in GSoC 2018

[kaiqiang Xu]

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 <rickllykqxu at gmail.com> 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 <ryan at ratml.org>:
>
>> 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?"
>> ryan at ratml.org |   - Mike LaFontaine
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://knife.lugatgt.org/pipermail/mlpack/attachments/20180326/9eb3c115/attachment.html>