Source-linked AI summary
The Cost of Missed States: Online Tracking with Current-Observation Resets
Hiroyasu Usami
TL;DR
The paper asks how online tracking performs when a retained state can be reset only to the current observation, despite access to the full observed history. It analyzes hard-radius and penalized objectives under this constraint, finding a horizon-linear hard-radius lower bound and a penalized lower bound that depends on increasingly fine grids.
Problem
Tracking with current-observation resets may differ from classical models that let representatives be states other than the current observation, even when the full history is available.
Source: §I · p. 1Method
The paper analyzes hard-radius and penalized tracking under current-observation resets, adapting a randomized nested-interval lower bound by prepending candidate centers for a legal offline reset.
Source: §I · p. 1, B. PENALIZED TRACKING · p. 3Results
For every T ≥ 5, a fixed five-point metric requires at least (T + 1)/2 expected online refreshes against two offline refreshes; the penalized lower bound uses increasingly fine grids.
Source: §I · p. 1Takeaways & Limitations
Current-observation resets can make missed states irrecoverable, while cumulative variation still controls the absolute cost of the anytime and clipped policies.
Source: §I · p. 1, A. AN ANYTIME POLICY · p. 6, §VII · p. 11
Abstract
from arXiv · showhide
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_\lambda$ for cumulative discrepancy plus a charge $\lambda>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\lambda$. 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_\lambda\le\lambda+4\sqrt{\lambda TV_T}$ without knowing the horizon or final variation. Clipping for a known horizon gives $J_\lambda\le\lambda 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.
I. INTRODUCTION
The paper studies tracking when a retained state can be replaced only by the current observation, even though the full observed history is available. It establishes a hard-radius refresh lower bound, contrasts it with historical resets, and develops results for penalized tracking, variation-based cost control, and output discrepancy.
II. MODEL AND OBJECTIVES
- The model permits keeping one retained state or replacing it with the current observation, while offline knows the future and obeys the same reset rule.The complete observed history remains available to the online policy.Source: §I · p. 1, §II · p. 2
A. A MISSED CENTER FORCES REPEATED REFRESHES
- For every T ≥ 5, a fixed five-point metric forces at least (T + 1)/2 expected online refreshes against exactly two offline refreshes, with a strict radius margin.The path visits at most four values, and its resolution stays fixed as T grows.Source: §I · p. 1, A. A MISSED CENTER FORCES REPEATED… · pp. 2–3
I. INTRODUCTION
- For penalized tracking, a candidate prefix makes the offline witness legal under current resets, yielding a lower bound for randomized causal policies even with a known horizon and V_T < 3λ.The construction uses finer grids as the requested ratio increases; on a fixed finite metric with positive minimum separation, refreshing whenever observations change is competitive.Source: §I · p. 1
- The anytime policy controls J_λ using T and V_T, while the known-horizon clipped policy gives J_λ ≤ λT and a factor-three comparison with the minimum of three analytical bounds.The anytime guarantee does not require knowing the horizon or final variation.Source: §I · p. 1
- For retained operators evaluated at the same current input, current-value diameter and readout sensitivity bound output discrepancy, including for squared-distance softmax.The paper also gives an example where RMS drift over the complete summary tends to zero while output discrepancy stays fixed.Source: §I · pp. 1–2
A. A MISSED CENTER FORCES REPEATED REFRESHES
- A causal policy with historical resets can install the center identified by the first suffix observation and serve the same family with exactly two refreshes.The lower bound relies on current-observation resets, which cannot recover a missed prefix center until it reappears.Source: §I · p. 1, §II · p. 2, A. A MISSED CENTER FORCES REPEATED… · p. 3
B. PENALIZED TRACKING
The penalized-tracking result adapts a randomized lower-bound construction to resets that can install only the current observation. Its lower bound requires a growing, increasingly fine grid, while fixed finite metrics with positive minimum separation admit a competitive policy.
B. PENALIZED TRACKING
- The lower bound applies to randomized causal policies on fixed paths, even with a known horizon and an additive allowance, but its grid grows with the requested ratio.The paths have V_T < 3λ, and the construction uses increasing precision.Source: B. PENALIZED TRACKING · pp. 3–4
- A candidate-center prefix makes the offline witness legal under current-observation resets, and every phase costs the online policy at least λ/16 in expectation while offline costs less than 7λ/2.With b > 56C phases, the construction yields the requested ratio for randomized causal policies, even when they know the horizon.Source: B. PENALIZED TRACKING · p. 3
- The construction prepends candidate centers to the Bienkowski and Schmid nested-interval argument so offline can install its eventual center when observed.The prefix spacing is δ = λ/M^2, keeping prefix distortion below λ/2.Source: B. PENALIZED TRACKING · p. 3
- On a fixed finite metric with minimum nonzero separation δ, refreshing initially and whenever observations change is max{1, 2λ/δ}-competitive for J_λ.These bounds are uniform in the horizon, but the best dependence on resolution remains undetermined.Source: B. PENALIZED TRACKING · p. 4
C. AN EXACT OFFLINE BENCHMARK
The section gives an exact offline benchmark for penalized tracking and describes a candidate-prefix construction used in a fixed-length random phase. The benchmark also accommodates certified hard-tolerance schedules, with conservatism limiting which schedules it includes.
C. AN EXACT OFFLINE BENCHMARK
- The offline oracle minimizes Jλ exactly by viewing each schedule as a partition of the observed path into refresh-delimited segments.Incremental segment-cost updates use O(T^2) distance evaluations and arithmetic operations, with O(T) auxiliary storage beyond the path.Source: C. AN EXACT OFFLINE BENCHMARK · p. 4
- Certified hard-tolerance schedules are represented by retaining only edges whose certificate stays within ε, then minimizing refresh count over that class.Conservative certificates can exclude schedules that satisfy the actual output tolerance.Source: C. AN EXACT OFFLINE BENCHMARK · p. 4
B A fixed-length random phase
- The candidate prefix exposes every center so offline can install the final center when observed, while each fixed-length phase repeats a uniformly chosen child interval’s left endpoint.Online’s conditional expected phase cost is at least λ/16, while offline’s total cost is below 7λ/2 including prefix and initialization.Source: Figure 2 · p. 5
IV. TRACKING UNDER BOUNDED VARIATION
Variation accounting bounds penalized tracking cost and refresh count, while an anytime threshold rule adapts to observed variation without knowing the horizon or final variation. An age cap adds a separate refresh-count term and can also tighten the discrepancy bound.
IV. TRACKING UNDER BOUNDED VARIATION
- The threshold rule refreshes when distance from the retained observation exceeds η, optionally also refreshing when the age reaches K.The policy refreshes initially; age is measured in the opportunity index.Source: §IV · p. 5
- The threshold-and-age policy controls refresh count through path variation and age, with the age contribution absent when no age rule is used.Drift refreshes are charged to disjoint variation intervals; age intervals each contain at least K planned steps.Source: §IV · p. 5
- With an age cap K and a rate bound d(zt,zs) ≤ ν(t−s), post-decision discrepancy is at most min{η, ν(K−1)}.The paper relates the variation argument to send-on-delta reporting and converts this discrepancy bound to output error through readout sensitivity.Source: §IV · p. 5
- Without an age constraint, the fixed-threshold cost bound follows by balancing distortion Tη against refresh charge λVT/η.The optimized fixed threshold requires final variation or a known upper bound; retaining only the initial state costs at most λ + (T−1)VT, while always refreshing costs λT.Source: §IV · p. 5
A. AN ANYTIME POLICY
- The anytime policy, without knowing T or final variation, satisfies Jλ ≤ λ + 4√(λTVT) at every finite horizon.Its distortion and refresh charge beyond initialization are each at most 2√(λTVT).Source: A. AN ANYTIME POLICY · p. 6
B. CLIPPED THRESHOLDS FOR A KNOWN HORIZON
For a known horizon, a clipped threshold based on cumulative observed variation adapts to unknown final variation. Its guarantees span low-, middle-, and high-variation regimes and compare within a factor of three to the minimum of three analytical bounds.
B. CLIPPED THRESHOLDS FOR A KNOWN HORIZON
- The single clipped policy, without knowing V in advance, gives Jλ ≤ λ + (T−1)V when V ≤ λ/T, a strict middle-regime bound, and Jλ ≤ λT when V > λT.The middle regime is λ/T < V ≤ λT; the global cap comes from the cost of refreshing at every opportunity.Source: B. CLIPPED THRESHOLDS FOR A KNOWN… · pp. 6–7
- The policy refreshes initially and thereafter when distance from the retained observation exceeds η(St), using observed cumulative variation rather than advance knowledge of V.For low variation, V ≤ λ/T, the initial-state discrepancy never exceeds the threshold and N = 1.Source: B. CLIPPED THRESHOLDS FOR A KNOWN… · pp. 6–7
- The clipped policy’s cost is at most a factor of three above the minimum of three analytical bounds.In the middle regime the comparison uses the square-root scale; the clipping also ensures cost no greater than always refreshing.Source: B. CLIPPED THRESHOLDS FOR A KNOWN… · p. 7
C. THE DISTORTION–REFRESH TRADE-OFF
The section analyzes the distortion–refresh trade-off on a finite ramp and gives a square-root-order lower bound matched by the threshold rule in a stated regime. It also reports path-family comparisons and shows that a fixed threshold can have an unbounded refresh-count ratio.
C. THE DISTORTION–REFRESH TRADE-OFF
- For a ramp with T observations and exactly N refreshes, optimal segment lengths differ by at most one, yielding the exact minimum distortion-plus-refresh cost.If two segment lengths differ by at least two, shifting one point from the longer to the shorter reduces distortion.Source: C. THE DISTORTION–REFRESH TRADE-OFF · p. 7
- When v ≤ λ ≤ vT², randomized causal policies face a square-root-order lower bound, and the threshold rule matches this worst-case order.The ramp lower bound also holds for offline schedules, so it describes a trade-off shared by all policies in the stated regime.Source: C. THE DISTORTION–REFRESH TRADE-OFF · p. 7
- On the two burst-and-plateau examples, the anytime and clipped policies reverse their cost ordering as the path variation changes.At V = 1/2 their costs are 7 and 5 against offline cost 11/4; at V = 2 their costs are 4 and 5 against offline cost 4.Source: C. THE DISTORTION–REFRESH TRADE-OFF · p. 7
- Across 288 seeded path–charge cases, all anytime and clipped costs satisfy their analytical bounds; clipped costs are lower in 23 cases, equal in 113, and higher in 152.The evaluations include 72 paths across random walks, burst–plateau processes, and switching regimes, with an exact offline oracle.Source: C. THE DISTORTION–REFRESH TRADE-OFF · p. 7
D. FIXED THRESHOLDS AND COMPETITIVE RATIOS
- Under the hard metric-radius constraint and without an effective age cap, a fixed threshold can have an unbounded refresh-count ratio against offline.Its variation accounting bound can still hold as the path variation grows; Theorem 2 gives a stronger separation for every feasible causal policy.Source: D. FIXED THRESHOLDS AND COMPETITIVE… · p. 7
A Burst followed by a plateau
The section illustrates threshold-based refresh decisions and develops bounds connecting retained-state drift to same-input output discrepancy. For mixtures, current-value diameter and readout sensitivity matter, while small logit changes alone do not ensure a fixed output-error tolerance.
B Distortion and refresh cost
- At V = 1/2, the strict anytime rule preserves equality at t = 32 and refreshes at t = 33; Figure 3 contrasts its decisions and costs with clipping and offline costs.Markers indicate refreshes, after which discrepancy is zero; costs include initialization.Source: Figure 3 · p. 8
V. FROM STATE DRIFT TO OUTPUT ERROR
- A known uniform bound on readout sensitivity and constructor variation supplies L for translating state drift into an output or loss-difference bound.A scalar loss that is Lℓ,t-Lipschitz adds the factor Lℓ,t.Source: §V · pp. 8–9
A. MIXTURE AND SOFTMAX BOUNDS
- Mixture output bounds use current-value diameter and readout sensitivity; without a bound on current-value sensitivity, arbitrarily small logit change cannot guarantee fixed output-error tolerance.The diameter is invariant under common translation of values, so a maximum value norm can be loose.Source: A. MIXTURE AND SOFTMAX BOUNDS · p. 9
B. SQUARED-DISTANCE SOFTMAX
For squared-distance softmax on the product of unit balls, the section bounds logit-gap change from concatenated-summary drift and converts that bound into a same-input output certificate.
B. SQUARED-DISTANCE SOFTMAX
- R ≤ 6ρ/ϑ on the product of unit balls, yielding an output discrepancy bound of LH,tWt tanh(3ρ/(2ϑ)).When every query and reference has norm exactly one, the coefficient 6 can be replaced by 2√6.Source: B. SQUARED-DISTANCE SOFTMAX · p. 9
- The coefficient 6 follows by bounding the gradient of each pairwise logit gap and integrating along a line segment in the product of unit balls.The resulting oscillation bound is |gij(z) − gij(z0)| ≤ 6ρ.Source: B. SQUARED-DISTANCE SOFTMAX · p. 9
A From state drift to same-input output error
Sensitivity assumptions convert state drift into same-input output bounds, with squared-distance softmax coefficients locally optimal. The section also shows that complete-coordinate RMS drift can shrink while output discrepancy remains fixed.
A From state drift to same-input output error
- L = 3M/(2ϑ) converts the full concatenated Euclidean metric trigger into a hard output tolerance when LH,tWt ≤ M.The bound uses tanh ξ ≤ ξ for ξ ≥ 0.Source: B Same output error, smaller RMS · p. 10
- For n = 2 and d ≥ 2, the constants 6 and 2√6 in the respective logit-oscillation bounds cannot be reduced as universal constants.Their sharpness is local with respect to concatenated Euclidean drift.Source: B Same output error, smaller RMS · p. 10
B Same output error, smaller RMS.
- Adding unused zero coordinates can make complete-coordinate RMS drift tend to zero while output discrepancy stays fixed, so no uniform vanishing output-error modulus follows from that RMS measure.The example uses current scalar values in [−1, 1] and an identity readout.Source: B Same output error, smaller RMS · p. 10
C. COMPUTATIONAL COST
The section gives a sequential cost accounting for refresh-based reuse and situates current-reset tracking among related online tracking models. Its conclusion distinguishes hard-radius and penalized lower bounds from variation-based absolute-cost guarantees and output certificates.
C. COMPUTATIONAL COST
- With no overlap between costs, the sequential model compares Cfr = B + Tc against Cca = B + Nc + Th + s.B is shared current-input and readout work; c is construction cost, h controller cost, and s additional state and initialization work.Source: C. COMPUTATIONAL COST · p. 10
VI. RELATED WORK
- The related tracking models differ in their allowed representatives, movement charges, and comparator rules, while the output certificate combines Hilbert-distance comparison with current-value diameter.Computing logit range and value diameter may itself be costly, and latency and energy also depend on overlap, transfers, batching, and memory access.Source: §VI · p. 11, C. COMPUTATIONAL COST · p. 11
VII. CONCLUSION
- The conclusion reports a fixed-five-point hard-radius lower bound, finer-grid noncompetitiveness for penalized tracking, a competitive fixed-finite-metric policy, and variation-based absolute-cost bounds.It also states that sensitivity assumptions yield same-input output bounds and that unused coordinates can conceal fixed output error.Source: §VII · p. 11
APPENDIX A LOCAL OPTIMALITY OF THE SOFTMAX COEFFICIENTS
The appendix establishes local sharpness of the softmax coefficients, including the two-category case and exact unit vectors.
APPENDIX A LOCAL OPTIMALITY OF THE SOFTMAX COEFFICIENTS
- For two categories, logit-change oscillation is |∆G|/ϑ; in the unit-ball case, the local coefficient approaches 6 as r increases to 1.A sufficiently small perturbation in the unit gradient direction makes |∆G|/ρ tend to 6r.Source: Appendix A · pp. 11–12
- The appendix also considers exact unit vectors, using a real parameter s near zero while keeping all vectors unit length.It measures ρ(s) from the base vectors (u0, a0, b0).Source: Appendix A · p. 12
- The two universal upper bounds are optimal: fixed scalar values +1 and −1 make the mixture's derivative attain the composed certificate's first-order coefficient.The mixture is tanh(G/(2ϑ)).Source: Appendix A · p. 12