Timezone: »

 
Poster
Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms
Vikas Garg · Tamar Pichkhadze

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #57
in Algorithms -- Structured Prediction »

We resolve the fundamental problem of online decoding with general nth 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. To our knowledge, our work is the first to analyze general Markov chain decoding under hard constraints on latency. We provide strong empirical evidence to illustrate the potential impact of our work in applications such as gene sequencing.

Keywords: Structured Prediction · Algorithms
[ Paper]  [ Slides] 

Author Information

Vikas Garg (MIT)
Tamar Pichkhadze (MIT)

More from the Same Authors