Smithsonian / Smithsonian/layup
The LM gain ratio lags the step it controls by one iteration, and a rejected step is never rolled back
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 atniter56.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:
- Evaluate the objective at the initial state before the loop and initialise
chi2_prevwith it,
so iteration 0 is tested like any other. (HUGE_VALwould then only be reached if the initial
state itself is non-finite, which is worth handling explicitly.) - 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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