FAQ

Why does the diagonal iteration beat Newton–Krylov, when the diagonal it preconditions with is exact, and diagonally preconditioned CG normally beats damped Jacobi on an SPD system?

Section 4 puts Newton–Krylov two orders of magnitude behind the damped coordinate iteration. But the slopes preconditioning that iteration are the Laplacian's own diagonal. Diagonally preconditioned CG beats damped Jacobi on an SPD system, so the ordering should flip — unless one Jacobian–vector product costs a lot more than one sweep. And separately: the page hedges that the per-iteration slope isn't quite the exact derivative — does that show up as bounded oscillation, or as growing error?

Wall clock vs. iteration count

PCG does win on iteration count. It loses on wall clock because of what each iteration costs. Measured in three rounds (research/experiments/exp23_newton_cg). Round 1: unpreconditioned CG on raw share residuals, where tiny-share coordinates are invisible to both the residual and the Jacobian, so the step goes into weakly determined tail directions — 387s, not converged, vs. 3.7s for the production sweep at \(n=200\). Round 2: adds a diagonal preconditioner but keeps an only-approximately-symmetric Jacobian–vector product and no null-space projection — diverges outright. Round 3: symmetrized log-residual Newton system, the exact integration-by-parts Jacobian–vector product (genuinely symmetric), the null vector projected out, PCG preconditioned by the same own-log-slope diagonal the production sweep uses. First version to converge at all, and on the easy case it reaches a residual an order of magnitude tighter than the diagonal iteration — at roughly sixty times the wall clock:

The diagonal iteration's own-slope preconditioner is a byproduct of the forward pass it already has to run to get the shares — free. Each PCG iteration needs an exact Jacobian–vector product instead.

Since a CG iteration and a sweep both cost one pass over the tie edges, the comparison collapses to inner CG count times Newton steps against sweep count. Losing the clock while winning iterations puts the whole cost in that inner count, and it should split by regime. Jacobi on a Laplacian sets the count by the spectral gap, so if it's flat while sweeps grow with field size, the verdict flips before you reach a million. Does it move with field size across the exp23 variants?

Does the ratio move with field size?

A CG iteration and a sweep don't cost the same one pass. Measured directly at \(n=200\), one IBP-form JVP takes 11.5× as long as one forward pass with slopes. Measured across \(n=200\) to \(n=12{,}800\):

Both operations are \(O(n)\) at fixed \(L\), and the ratio between them is flat across a 64× range in \(n\). The per-call cost gap doesn't close with field size.

The sweep count doesn't move either, at least on the easy problem. Production Jacobi's iteration count, same problem family, same tolerance:

That is consistent with the spectral-gap story: this correlation structure comes from a rank-2 factor model, so the tie-density graph's effective diameter doesn't grow with \(n\), and neither does the sweep count needed to converge.

What isn't flat is the hybrid solver itself. At \(n=200\) it converges in 8 Newton steps and 15 total JVPs. Run unmodified on the same easy problem at \(n=3{,}200\) — same 10-Newton-step, 5-inner-CG-iteration budget — it does not converge: 10 Newton steps, 20 JVPs, residual stuck at 2.4e-1 against a 1e-8 tolerance. Wall clock at that size: production Jacobi 46.8s, the hybrid 515.6s and still short of tolerance. The gap doesn't narrow going from \(n=200\) to \(n=3{,}200\); it widens.

Whether that is the outer Newton step count genuinely growing with \(n\), or the trust-region and step-acceptance constants in run_newton_cg3.py being tuned for \(n=200\) and not rescaled, isn't separated by this run. Exp23 only ever ran round 3 at \(n=200\) before this; at \(n=3{,}200\) the unmodified hybrid fails to converge, so the flat-inner-count mechanism doesn't get a chance to produce a flip here.

Bounded chatter, or growing error?

Because the diagonal iteration re-evaluates the field (and therefore the slope) every step, it is a fixed-point iteration, not a linearize-once-and-solve method: an inexact slope changes the rate of convergence, not where it converges to — the same reason Sinkhorn scaling converges under an approximate row/column normalization (the diagonal iteration is the hard-max analogue of that construction).

Write the tie-density Laplacian as \(L = D - W\) (Section 3's \(J = -B^\top W_e B\), diagonal and off-diagonal parts). Jacobi splitting for \(Lv = r\) has sweep matrix \(M = D^{-1}W\). Because \(L\)'s rows sum to zero, \(D^{-1}W\) is row-stochastic, so with the exact diagonal its spectrum sits in \([-1, 1]\) — the top eigenvalue is exactly 1, on the all-ones (gauge) direction that inversion projects out anyway, matching Section 4's remark that only ability contrasts are identified. On the contrast subspace, an eigenvalue reaches \(-1\) only in the degenerate limit of a bipartite tie-density graph — two clusters of contestants whose photo-finishes are almost all cross-cluster and almost never within-cluster. That is a 2-dimensional race: two contestants, one edge, sweep matrix \([[0,1],[1,0]]\), spectrum exactly \(\{+1,-1\}\). With the exact diagonal an undamped sweep can only chatter (period-2, bounded), never grow: an eigenvalue at −1 is a geometry fact about how bipartite the tie structure is, not a symptom of an inexact derivative. Growth needs the diagonal to be underestimated, which pushes a contrast eigenvalue past −1.

On exp23's hard case (strong correlation, a small-cluster structure close to the bipartite limit above), the production diagonal iteration run alone stalls at a fixed residual (1.1e-4) against its iteration cap rather than diverging — bounded, consistent with the geometry story above. But the same hard instance, run as the fallback sweep inside round 3's hybrid solver, does diverge (residual 6e+2) despite an accept-test meant to reject a step that makes things worse. That divergence isn't attributed to either story yet; the experiment's own README flags it as the next engineering item (Levenberg regularization and a fallback that's stable on the hard set).

Sources: the exp23 README for the three-round, \(n=200\) comparison; the field-size numbers above are run_field_size_scaling.py in the same directory. The equilibrium notes give the Sinkhorn framing of the diagonal iteration as a fixed point.