pith. sign in

arxiv: 2605.21843 · v2 · pith:5JSJHXNQnew · submitted 2026-05-21 · 🧮 math.OC

Spectral analysis of the logit mapping and implications for stochastic user equilibrium algorithms

Debojjal Bagchi , Stephen D. Boyles This is my paper

Pith reviewed 2026-05-22 05:31 UTC · model grok-4.3

classification 🧮 math.OC
keywords stochastic user equilibriumlogit mappingJacobian spectral analysismethod of successive averagesNewton methodpath-based algorithmstraffic networksconvergence rates
0
0 comments X

The pith

The Jacobian of the logit mapping decomposes into two matrices whose spectral properties establish linear convergence rates for stochastic user equilibrium algorithms.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper analyzes the Jacobian of the logit mapping in path-based stochastic user equilibrium to derive improved solution algorithms. It establishes that this Jacobian factors into one matrix that annihilates differences between feasible path flow vectors and a second matrix whose eigenvalues are all non-positive real numbers when link costs are monotone non-decreasing and separable. These properties are used to prove linear convergence of the method of successive averages with a fixed step size s at rate 1-s and to construct both an adaptive step-size variant and a Newton method that reformulates SUE as a root-finding problem. The resulting algorithms avoid dense Hessian operations and manifold projections, making large-scale computations practical.

Core claim

The Jacobian of the logit mapping decomposes into two matrices: one that annihilates differences of feasible path flow vectors, and another whose eigenvalues are all non-positive reals, provided link costs are monotone non-decreasing and separable. Using these properties, the method of successive averages with a small constant step-size s converges linearly at a rate 1-s. An adaptive constant step-size rule retains global convergence while achieving asymptotic linear convergence. A Newton-based method reformulates SUE as a root-finding problem that exploits the Jacobian structure for tractable computation without manifold optimization.

What carries the argument

Jacobian of the logit mapping, which decomposes into an annihilator of feasible path-flow differences and a second factor with non-positive real eigenvalues.

Load-bearing premise

Link costs must be monotone non-decreasing and separable to ensure the second Jacobian factor has only non-positive real eigenvalues.

What would settle it

A network example with monotone non-decreasing separable link costs where the second Jacobian factor has a positive or complex eigenvalue would disprove the spectral claim.

Figures

Figures reproduced from arXiv: 2605.21843 by Debojjal Bagchi, Stephen D. Boyles.

Figure 1
Figure 1. Figure 1: Convergence of RGAP (log scale) versus iteration for MSA with harmonic step-sizes and [PITH_FULL_IMAGE:figures/full_fig_p025_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Convergence rate of MSA for the Anaheim network across varying [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Convergence of RGAP (log scale) versus iteration for [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Runtimes (in seconds) to reach a RGAP level (log scale) [PITH_FULL_IMAGE:figures/full_fig_p032_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Braess network with one OD pair (O, D), three paths, and link cost functions shown on each link. Link l connecting nodes A and B is denoted as lAB. A.1 Computations of the Jacobian The Jacobian of path costs with respect to path flows, as defined in Equation (8), is J = C ′ (h) =   1 0 1 0 1 1 1 1 2   . We will use J := C ′ (h) as a shorthand throughout this example, consistent with Section 4.2. At ite… view at source ↗
read the original abstract

We analyze the Jacobian of the logit mapping for stochastic user equilibrium (SUE) and use it to develop two improved algorithms for path-based SUE. We show that the Jacobian decomposes into two matrices: one that annihilates differences of feasible path flow vectors, and another whose eigenvalues are all non-positive reals, provided link costs are monotone non-decreasing and separable. Using these properties, we first show that the method of successive averages (MSA) with a small constant step-size $s$ converges linearly at a rate $1-s$, with the largest admissible step-size depending on the eigenvalues of the Jacobian of the logit mapping. Building on this result, we develop an adaptive constant step-size rule that retains the global convergence of MSA while achieving asymptotic linear convergence. Our second algorithm is a Newton-based method using a reformulation of SUE as a root-finding problem. Unlike gradient-projection approaches that operate on the Hessian of the SUE objective function (a dense matrix), our method exploits the structure of the Jacobian of the logit mapping, making computations tractable and removing the need for manifold optimization. Numerical experiments show superlinear convergence on most tested networks, with our methods outperforming existing approaches on large networks or when demand is high. To our knowledge, this article is the first to report runtimes for logit-based SUE on networks as large as Chicago Regional and Philadelphia, providing a benchmark for future algorithmic development.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes the Jacobian of the logit mapping in path-based stochastic user equilibrium (SUE). It decomposes this Jacobian into an annihilator of differences between feasible path-flow vectors and a second factor whose eigenvalues are all real and non-positive when link costs are monotone non-decreasing and separable. These spectral properties are used to prove linear convergence of the method of successive averages (MSA) at rate 1-s for sufficiently small constant step-size s, to construct an adaptive constant step-size rule that preserves global convergence while achieving asymptotic linear rate, and to formulate a Newton-type root-finding method that exploits the Jacobian structure for tractability instead of operating on the dense Hessian of the SUE objective. Numerical tests report superlinear convergence on most instances and improved runtimes on large networks including Chicago Regional and Philadelphia.

Significance. If the eigenvalue result is rigorously established, the work supplies a concrete spectral foundation for step-size selection and algorithmic design in SUE, moving beyond heuristic tuning. The structural exploitation that avoids manifold optimization and dense Hessians is a practical advantage for large-scale instances, and the reported runtimes on Chicago Regional and Philadelphia supply a useful benchmark. The adaptive MSA rule and Newton variant could be adopted in transportation planning software once the supporting derivations are fully verified.

major comments (2)
  1. [Abstract and Jacobian analysis section] Abstract and the section deriving the Jacobian decomposition: the claim that the second factor has exclusively real non-positive eigenvalues rests on monotonicity and separability of link costs. The conversion from these assumptions to a real spectrum (via symmetry, diagonal dominance, or an explicit characteristic equation) is load-bearing for the subsequent linear-rate proofs and admissible-step-size bounds; the manuscript should exhibit the key matrix entries or the intermediate lemma that establishes this spectral property.
  2. [Numerical experiments section] Section on numerical experiments: superlinear convergence is asserted for most tested networks, yet the reported data tables or figures do not appear to include per-iteration error norms or iteration counts that would allow direct comparison of the proposed MSA-adaptive and Newton methods against standard baselines on the same instances.
minor comments (2)
  1. [Notation and preliminaries] Notation for the annihilator matrix and the second Jacobian factor should be introduced with a single consistent symbol set early in the paper to avoid later redefinition.
  2. [Abstract] The abstract states that the largest admissible step-size depends on the eigenvalues of the logit Jacobian; a brief remark on how these eigenvalues are computed or bounded in practice would help readers implement the constant-step MSA variant.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback on our manuscript. We address each major comment below, indicating where revisions will be made to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract and Jacobian analysis section] Abstract and the section deriving the Jacobian decomposition: the claim that the second factor has exclusively real non-positive eigenvalues rests on monotonicity and separability of link costs. The conversion from these assumptions to a real spectrum (via symmetry, diagonal dominance, or an explicit characteristic equation) is load-bearing for the subsequent linear-rate proofs and admissible-step-size bounds; the manuscript should exhibit the key matrix entries or the intermediate lemma that establishes this spectral property.

    Authors: We agree that an explicit derivation of the real non-positive spectrum is essential for rigor. The current manuscript states the result under the stated assumptions on link costs but does not isolate the intermediate steps. In the revision we will insert a dedicated lemma immediately after the Jacobian decomposition. The lemma will show that the second factor is similar to a symmetric matrix whose quadratic form is non-positive when link costs are monotone and separable, thereby establishing that all eigenvalues are real and non-positive. Key matrix entries (the diagonal blocks arising from the separable cost functions) will be displayed explicitly to make the symmetry argument transparent. revision: yes

  2. Referee: [Numerical experiments section] Section on numerical experiments: superlinear convergence is asserted for most tested networks, yet the reported data tables or figures do not appear to include per-iteration error norms or iteration counts that would allow direct comparison of the proposed MSA-adaptive and Newton methods against standard baselines on the same instances.

    Authors: The referee is correct that the current numerical section presents aggregate runtimes and final gaps but does not tabulate per-iteration residual norms or iteration counts for side-by-side comparison. We will add a new table (and, where space permits, a supplementary figure) that reports, for each method and each network, the number of iterations to reach a prescribed tolerance together with the evolution of the path-flow residual norm at selected iterations. This will enable direct quantitative comparison with the standard MSA and other baselines on the same instances, including the large networks already tested. revision: yes

Circularity Check

0 steps flagged

No circularity; spectral properties derived directly from monotonicity and separability assumptions

full rationale

The paper's central derivation decomposes the Jacobian of the logit mapping into an annihilator matrix plus a second factor whose eigenvalues are shown to be real and non-positive when link costs are monotone non-decreasing and separable. This follows from standard properties of monotone separable functions and does not reduce to a fitted parameter, self-definition, or self-citation chain. The MSA step-size bounds and Newton method are constructed from these independently established spectral facts rather than by renaming or smuggling prior results. No load-bearing step equates a prediction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the monotonicity and separability of link costs to obtain the eigenvalue sign property; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Link costs are monotone non-decreasing and separable
    Required to guarantee that the second factor of the Jacobian has only non-positive real eigenvalues.

pith-pipeline@v0.9.0 · 5786 in / 1162 out tokens · 35417 ms · 2026-05-22T05:31:05.238588+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.