Smithsonian / Smithsonian/layup

The LM gain ratio lags the step it controls by one iteration, and a rejected step is never rolled back

Open
#584 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
10
Forks
2
Avg merge
1d 43m
Merged PRs (30d)
58

Description

⚠️ TWO CORRECTIONS. (1) The diagnosis and suggested fix below are superseded by this correction — the real defect is that the LM gain ratio lags the step it controls by one iteration and a rejected step is never rolled back, and the two-line fix proposed at the end would break every fit. (2) The 17/17 statistic below is circular and is replaced by this one (68.8% vs 17.5%, OR 10.4, p=1.3e-5) — those 17 objects were selected for the very behaviour the statistic then tested. The issue rests on the unselected measurement in this comment.

orbit_fit.cpp initialises the Levenberg-Marquardt loop with

double chi2_prev = HUGE_VAL;                                                    // :1182
...
double rho = (chi2_prev - obj) / (dX.transpose() * (lambda * dX - grad)).norm(); // :1257
if (rho > rho_accept)   // rho_accept = 0.1                                      // :1259

On iteration 0, chi2_prev is HUGE_VAL, so the numerator is +inf and rho is enormous for
any finite step. The gain-ratio test passes unconditionally, and the first LM step is always
accepted, however bad it is.

A standard LM evaluates the objective at x0 before entering the loop, so the first step is
tested like every other one. Here the test is vacuous exactly once — on the step taken from the
initial guess, which for a short-arc fit is the step most likely to be catastrophic.

Measurement

Fitting MPC unnumbered designations, we have 17 objects where the fit diverges immediately. We
compared them against 19 objects drawn from the same population of failed fits that do not
diverge:

n first step increases χ² median χ² ratio, step 0
diverging fits 17 17/17 (100%) 860.6 (max 35,089×)
controls 19 2/19 (11%) 0.608

Every one of the 17 takes a χ²-increasing first step and is not allowed to refuse it. The controls
behave the way a working LM should, which is what makes this look causal rather than incidental.

A second, interacting problem

converged(dX, eps, chi2_d) at :1294 is called outside the accept/reject branches, so it also
runs after a rejected step. Once λ has grown enough that dX is small, the convergence test
passes on a step that was just rejected, and the fit returns flag = 0 at a state it never
accepted.

Two cases from the same set:

  • K16J88R — reports converged at niter 56.
  • K07VF0O — residual RMS bit-identical at 519.3769″ from step 1 through step 65, then reports
    flag = 0.

Combined with the above, a fit can take one unconditionally-accepted bad step, fail to improve for
sixty more, and still report success.

This is distinct from #477 (the convergence test being absolute rather than scale-invariant),
though the two compound: #477 makes converged easier to satisfy, and :1294 lets it be satisfied
at a rejected state.

Suggested fix

Two changes, both small:

  1. Evaluate the objective at the initial state before the loop and initialise chi2_prev with it,
    so iteration 0 is tested like any other. (HUGE_VAL would then only be reached if the initial
    state itself is non-finite, which is worth handling explicitly.)
  2. Test convergence only after an accepted step — move the converged(...) call at :1294
    into the accept branch, or gate it on the step having been accepted.

(1) alone has a clean before/after test: all 17 of the above should stop diverging, and the 19
controls should be unaffected since only 2 of them take a χ²-increasing first step at all.

Line numbers are against main at 8fbc702.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in orbit_fit.cpp around lines 1182, 1257, and 1294, and trace the Levenberg–Marquardt accept/reject loop. Reproduce the behavior for K16J88R and K07VF0O, then verify that the initial step is evaluated against the initial objective and convergence is reported only after an accepted step.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
data
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.