acceptodds
Under review as a conference paper at ICLR 2027

Horizon-Independent Inference from Sparse Markov Observations

Abstract

We study horizon-independent inference: maximum-likelihood estimation of monotone degrading Markov systems from sparse -step observations whose computational cost is independent of the maximum observation horizon . This is a challenging regime: multi-step probabilities are complex functions of the parameters, making likelihood optimization intractable as grows under standard formulations. We exploit the monotone bidiagonal structure to derive a parameterized diagonalization whose factors are closed-form in the unknown stay-probabilities ( is the sink state), enabling each -step entry to be evaluated in time with algebraically exact analytic gradients — reducing total cost from to , where is the number of distinct observed tuples. While the strongest baseline fails beyond , BDS scales to in single-digit seconds. Synthetic evaluations show below MAPE with a few thousand observations; real-world results confirm interpretable recovery and competitive predictive accuracy.

Primary area:
learning on time series and dynamical systems
Keywords:
Markov chain estimation, parameterized diagonalization, sparse long-horizon observations, horizon-independent inference, degradation modeling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GtrUOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper is about estimating Markov transition probabilities for monotone degradation processes from sparse observations collected over heterogeneous intervals. It proposes BDS, which uses an explicit spectral decomposition of the upper-bidiagonal matrix to evaluate the transition needed by the likelihood. The authors also provides the computational complexity of the method. Experiments on synthetic data, NASA battery data, and XJTU-SY bearing data compare BDS with general matrix, banded matrix, and EM-based methods.

Critical strengths

1: The studied computational problem: learning degradation dynamics from sparse, heterogeneous, long-horizon observations is very important.

2:There are experiments on both synthetic benchmarks and two real-world datasets, demonstrating practical scalability of the algorithm.

Critical weaknesses

1: Theorem 4.1 is just a special factorization of the classical Opitz/divided-difference formula for functions of upper-bidiagonal matrices. Key prior work by Opitz, de Boor, Higham, Davis, Descloux, and Van Loan is not cited.

2: The diagonalization underlying Theorem 4.1 fails at repeated transition probabilities. Since 1−pi>01-p_i>0, the transition matrix is an unreduced upper-bidiagonal matrix. Its eigenvector recurrence implies that every eigenspace is one-dimensional; hence any repeated diagonal eigenvalue makes the matrix defective. Consequently, no invertible eigenvector matrix UU exists such that Pˉ=UDU−1\bar P=UDU^{-1}.

3: The baseline comparison is unfairly weak. BDS is compared with naive divided differences and generic dense eigendecomposition, rather than an optimized structured implementation of the classical bidiagonal/divided-difference formula. Thus, the paper does not establish that the proposed method improves upon existing structured methods.

4: The O(T2+TH)O(T^2+TH) bound is established theoretically. However, the reported implementation uses ForwardDiff, for which the manuscript itself gives a per-gradient cost of (O(T3+T2H)(O(T^3+T^2H). Therefore, the experiments do not implement or empirically validate the headline O(T2+TH)O(T^2+TH) gradient complexity.

Questions for authors

See the weakness part.

Reviewer_caaTOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies maximum-likelihood estimation of monotone upper-bidiagonal Markov chains from sparse observations separated by heterogeneous and potentially very large horizons. It derives an explicit parameterized eigendecomposition and uses it to evaluate selected entries of PnP^n, likelihoods, and a theoretically proposed reverse-mode gradient with arithmetic cost independent of the maximum horizon. The framework is extended to absorbing failures, wider jumps, basis-function parameterizations, belief-distribution inputs, and downstream duration and replacement calculations, with synthetic and real-data experiments. The structured computation is potentially useful, but the mathematical novelty is overstated and the numerical, implementation, and statistical evidence does not fully support the central claims.

Critical strengths
  1. The paper identifies a useful computational regime: after shared preprocessing, only the transition entries appearing in the sufficient statistics need to be evaluated, avoiding construction of every intermediate matrix power.
  2. The explicit eigenvector recurrences and inverse relation are carefully derived for pairwise-distinct stay probabilities, and the supplement is unusually extensive about structural extensions, numerical pathologies, and experimental ablations.
Critical weaknesses
  1. The main algebraic novelty is not adequately distinguished from classical matrix-function theory. For an upper-bidiagonal matrix BB, the Opitz/divided-difference identity give f(B){ij}=\prod{k=i}^{j-1}B_{k,k+1}, so f(z)=znf(z)=z^n directly yields the required entries of PnP^n, including confluent interpretations for repeated diagonal values. This is standard prior work; see de Boor's divided-difference exposition, Higham's work on bidiagonal matrices, and Parlett's classical triangular matrix-function recurrence. The submission does not clearly isolate what is novel beyond specializing these identities, expressing them as a parameterized diagonalization, and amortizing selected-entry queries.

  2. The headline O(T2+TH)O(T^2+TH) gradient complexity is not demonstrated by the evaluated implementation. The experiments use ForwardDiff, for which the appendix gives O(T3+T2H)O(T^3+T^2H) cost. The claimed reverse-mode/explicit-adjoint gradient is described only as a computational-graph argument: it is not implemented, timed, memory-profiled, or numerically validated. The baselines are also weak—BSS uses sequential powers and EIG-FD forms dense powers while finite-differencing parameters—so the speed tables do not compare against a strong confluent-divided-difference, Schur–Parlett, or reverse-mode repeated-squaring implementation.

  3. Numerical completeness is not established. The main theorem assumes pairwise-distinct pip_i, while clustered values make the spectral factors individually singular or severely ill-conditioned; the paper's own tables show errors exceeding 10210^2 in difficult regimes. The appendix displays a closed form for the fully coincident case and asserts an O(h2)O(h^2) substitution for general collision patterns, but does not provide a complete derivation, pseudocode, or forward/backward error bound for multiple partial clusters or near-collisions. Log-space arithmetic prevents underflow of individual factors but not cancellation among signed terms, and the proposed large-hop matrix-power fallback is left for future work and would reintroduce horizon dependence.

  4. The belief-distribution objective appears inconsistent with the predictive model stated immediately before it. The text defines a mixed prediction y^j=∑ax2ay^j(a)\hat y_j=\sum_a x_{2a}\hat y_j^{(a)}, but Equation (8) minimizes ∑ax2aKL(y∥y^(a))\sum_a x_{2a}\mathrm{KL}(y\|\hat y^{(a)}), rather than KL(y∥∑ax2ay^(a))\mathrm{KL}(y\|\sum_a x_{2a}\hat y^{(a)}). These objectives are generally unequal. Unless the action/usage category is observed rather than latent, the belief-distribution experiment therefore does not optimize the stated predictive distribution.

  5. The statistical and empirical claims are underdeveloped. No identifiability condition is provided for which collections of (x,y,n)(x,y,n) determine all stay probabilities, and there is no consistency, uncertainty, finite-sample, or optimization analysis. The large-horizon simulation changes the underlying chain with NN by sending pi→1p_i\to1, keeping hop counts small; the appendix reports approximately 0.18–0.37 relative error on the scientifically meaningful advance rates 1−pi1-p_i despite small MAPE on pip_i. The real-data evidence uses one battery and pooled snippets from 15 bearings, lacks independent-unit generalization and uncertainty quantification, and floors structurally impossible test events at 10−1910^{-19}.

Questions for authors
  1. Can the authors derive their transition-entry formula explicitly from the Opitz/divided-difference identity and state precisely what remains novel?
  2. Will the authors implement and benchmark the actual O(T2+TH)O(T^2+TH) reverse-mode gradient, including memory usage and comparison with stable confluent-divided-difference and Schur–Parlett methods?
  3. What is the complete algorithm for arbitrary disjoint repeated or near-repeated eigenvalue clusters, and what numerical error guarantee does it satisfy?
  4. Which belief model is intended in Section 4.3—a latent mixture or an observed action category—and should Equation (8) instead place the mixture inside the KL divergence?
  5. Can the experiments use a fixed underlying chain as the horizon increases, report error on 1−pi1-p_i, and evaluate generalization on held-out physical units?
Reviewer_StgiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors study "decaying" Markov Chains where we can only advance states. Given observations of every N-th step, they try to reconstruct the underlying transition matrix. They parameterize the transition matrix with the stay probabilities, and derive a closed-from symbolic expression for the Eigendecomposition of the transition matrix. That allows them to find the MLE more efficiently (memory and running time) compared to baselines, and it is independent of N. They showcase this via an experimental evaluation.

Critical strengths

The authors introduce an interesting and novel idea for an important problem, and they showcase empirically that their algorithm outperforms naive baselines. The closed-form solution for the Eigendecomposition is genuinely new. The authors are rigorous in their experimental evaluation and truthfully report benefits and shortcomings of their method.

Critical weaknesses
  1. The presentation could be improved. At the introduction, it would be good to fully and formally define the exact problem setting. That'd help readers also to appreciate the difficulty more. The notation is also a bit odd. For example, x1x_1 and yy are both states but use different symbols, but x2x_2 is a usage-level, so of different type.
  2. Some straightforward baselines aren't reported. For example, I only need to square log N times to obtain the full power, which is basically independent of N. Also, another separate baseline would be, when using true auto-diff, that the memory will not blow up to T^2 because we only need Jacobian-vector products and we never need to materialize the full bidiagonal matrix (but would probably need N multiplication). I don't mean to say that these are particularly good ideas or that they will outperform the author's method, but I'd at least expect a discussion about these.
  3. Kalbfleisch & Lawless (1985) already used an Eigendecomposition for the continuous version of this problem, which is also essentially independent of the horizon. The authors could mention this to put "the first horizon-independent method" into better perspective.
Questions for authors
  1. Could you state results of Weakness (2) or argue why it would not be a good idea. Once this is done, I'm happy to increase my score.
  2. For experiments on real-world data, the GSS baseline outperforms the author's method in terms of accuracy. The authors state that this might be because the decaying Markovian assumption might be violated. Is it possible to derive closed-form solutions for Eigendecompositions of slightly more permissive Markovian priors, which would fit the real-world data better but still preserve the performance guarantee of the bidiagonal form?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.