BUG. LMNN loops when a bad update is calculated.

[all2187]

There seems to be a relatively large bug in the code for LMNN. In lines 157-164 we have:

# update step size
  if delta_obj > 0:
    # we're getting worse... roll back!
    learn_rate /= 2.0
    df = df_old
    a1 = a1_old
    a2 = a2_old
    objective = objective_old

But in an iteration the objective is calculated as (line 149-150):

objective = total_active * (1-reg)
      objective += G.flatten().dot(L.T.dot(L).flatten())

Where none of total_active, reg, G, or L depend on the learn_rate. Since that is the only thing changed when the above error occurs, the result of the iteration following the roll back will be the same as teh one that caused the roll back. Hence as soon as lines 157 to 164 are executed, the algorithm will just keep halving the learning rate and re calculating the same values until the max iteration is hit (as can be seen below):

The solution most likely is to either make the calculation of the new objective dependent on the learning rate, or revert L to its previous value also (as in the value it had when the previous iteration that did not cause a roll back started).

[fabienpesquerel]

This is a major issue ! I completely agree with all2187 on what he wrote above, thanks for reporting (although I do not understand why, even an unoptimized quick fix, nothing has been done to this day) .

I did something like below on my local version of this repository and it works just fine now. The thing is that it can get worst a every now and then but that is not an issue if the learn_rate parameters is set correctly at the beginning of the loop.

      if delta_obj > 0:
        # we're getting worse... roll back!
        learn_rate /= 2.0
        df = df_old
        a1 = a1_old
        a2 = a2_old
        objective = objective_old
        # the learning rate has been halfed      # ++++++
        L -= learn_rate * 2 * L.dot(G)           # ++++++
      else:
        # update L
        L -= learn_rate * 2 * L.dot(G)
        learn_rate *= 1.01

One solution to do a correct set up of the learn_rate parameter would be to compute the gradient at the initial point, compute the value of the objective function at the initial point and then loop the first step while the new objective value is greater than the initial one. This would avoid to compute to many bad values if we are initially close to the optimum relatively to the initial learn_rate parameter.

[wdevazelhes]

I just proposed a quick fix in this PR: . It stores L and G in addition to what was already stored (df, a1 and a2), at the last "good" point (meaning the last time a point had a better objective than all the previous points), and gets back to this point if the update worsens the objective, as suggested by @all2187. I am not very familiar with LMNN so I may have missed something, but I guess it should fix the problem.