Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms
This addresses the challenge of efficient online decoding for applications like genome sequencing, offering near-optimal solutions with theoretical guarantees, though it is incremental in improving existing online methods.
The paper tackles the problem of online decoding with nth-order ergodic Markov chain models, providing deterministic and randomized algorithms that achieve near-optimal performance compared to offline algorithms, even with small latency, and empirically show over 30% improvement in decoding agreement on genome sequence data.
We resolve the fundamental problem of online decoding with general $n^{th}$ order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whose performance is close to that of the optimal offline algorithm even when latency is small. Our algorithms admit efficient implementation via dynamic programs, and readily extend to (adversarial) non-stationary or time-varying settings. We also establish lower bounds for online methods under latency constraints in both deterministic and randomized settings, and show that no online algorithm can perform significantly better than our algorithms. Empirically, just with latency one, our algorithm outperforms the online step algorithm by over 30\% in terms of decoding agreement with the optimal algorithm on genome sequence data.