Online tracking costs rise sharply without future knowledge
The Cost of Missed States: Online Tracking with Current-Observation Resets
Data Structures and Algorithms
Summary
This work studies how tracking systems that update their state only based on the current observation face unavoidable costs when they can't look ahead. The authors show mathematically that for certain paths, an online tracker must refresh its state much more often than an offline tracker that knows the future. They develop bounds on these refresh costs and propose policies that give good guarantees even without knowing the total tracking time or variation in the data. Their findings clarify fundamental limits and efficient strategies for tracking with resets limited to the present observation.
What this means in practice
- •For embedded system designers: Design tracker components that must reset state only using current inputs while minimizing state refresh costs over unknown operation lengths.
- •For streaming data engineers: Develop monitoring algorithms that efficiently trade off update frequency and error without knowing future data or full variation ahead.
A theory result. No direct application yet.
Authors
Hiroyasu Usami
Abstract
An online tracker retains one state and may reset only to the current observation, although its complete observed history is available. Offline knows the future and obeys the same reset rule. Under a hard discrepancy radius, for every horizon $T\ge5$ and every feasible randomized causal policy, a fixed path on a known five-point metric requires at least $(T+1)/2$ expected refreshes, against exactly two offline refreshes with a strict radius margin. Missing the useful prefix center forces a refresh at every suffix observation. The path visits four values, with resolution fixed as $T$ grows. Write $J_λ$ for cumulative discrepancy plus a charge $λ>0$ per refresh, and $V_T$ for the sum of successive observation distances. A candidate prefix adapts Bienkowski and Schmid's randomized lower bound to this objective under current resets, even with a known horizon and $V_T<3λ$. This construction needs finer grids; a fixed finite metric with positive minimum separation instead admits a competitive policy for penalized tracking. An anytime policy satisfies $J_λ\leλ+4\sqrt{λTV_T}$ without knowing the horizon or final variation. Clipping for a known horizon gives $J_λ\leλT$ and a factor-three comparison with the minimum of three analytical bounds, without knowing final variation. Current-value diameter and readout sensitivity give same-input output bounds for mixtures, including squared-distance softmax.