acceptodds
Under review as a conference paper at ICLR 2027

Exact Minimum-Event Explanations under Localized Observation Uncertainty

Abstract

Changepoint detectors, trend filters and perception pipelines routinely propose sparse event explanations of time series. We study how to verify such proposals exactly: given interval-valued observations of a scalar trajectory whose velocity jumps are nonnegative, capped and confined to labelled timing windows, can at most k events explain them? The budget query is NP-complete in general. We identify a shared-endpoint reset: across an interval with exactly observed endpoints and a timing window that opens at its start, the full set of feasible outgoing velocities is one interval, whatever the incoming set. The reset confines combinatorial branching to uncertainty blocks of maximum length β and gives an exact algorithm in 2^β·poly(n, β, L) time with rational witness recovery; assuming the Exponential Time Hypothesis, no 2^o(β) algorithm exists. A five-interval construction shows why exactness is needed: a complete-history first-moment flow relaxation with full-horizon fractional lookahead accepts two events although every compatible trajectory needs three. In the verified comparisons, every ACCEPT has a rational witness and every REJECT an exact certificate. On 24 retail-log windows fixed before inference, local inference settles 666 of 672 budget queries versus 540 for a bound-based baseline; on two taxi-log panels it matches enumeration and a certifying MILP cascade at about 28% less CPU than enumeration. At fixed block size two, a separate prospective synthetic panel with n up to 130 yields 14 of 16 certified budget decisions, retaining two call-limited UNKNOWNs. Exact certificates also expose over-counting and model-inconsistent proposals from ℓ1 relaxations and trend filtering. We report null comparisons and a downstream pilot without local-inference gains.

Primary area:
learning theory
Keywords:
minimum-event inference, interval observations, fixed-parameter tractability, exact certificates, dynamic programming, convex relaxation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_i89xOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Given uncertain measurements over time, what is the fewest events that could explain them? The propsed idea finds a possible explanation. Under specific timing rules, perfectly measured checkpoints simplify the search. Computation then depends mainly on the longest stretch of uncertainty, making some otherwise difficult problems manageable.

Critical strengths

The method provides checkable mathematical evidence for its answers. The authors also clearly report unresolved cases and unsuccessful experiments. It resolves 666 of 672 retail queries, but those are small, constructed tasks. It is roughly 28% faster than exhaustive search on taxi tests, yet about as fast as another certifying optimization approach.

Critical weaknesses

The useful speed guarantee relies on restrictive assumptions: changes only increase the signal’s slope, and suitable exact checkpoints separate uncertain stretches. When every measurement is uncertain, the search can still become exponentially expensive.

Questions for authors

See above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer i89x (part 1/2)

Thank you for the accurate summary, and for valuing the checkable certificates and the complete reporting of unresolved cases; the revision keeps both. Neither assumption you name is needed for exact answers; they only bound the running time. The first can be dropped, and the second holds by itself, with high probability, when uncertainty falls at random rather than by design. Long uncertain stretches contain the NP-complete cases of the problem, and even there our method returns exact answers within seconds on inputs with thousands of labels. The retail evidence is now far larger, and once the algorithm is evaluated without a solver, it is faster than verified branch-and-bound on every query that both certify.

Notation: nn is the number of labels (sampling intervals), and β\beta is the length of the longest run of intervals that touch an uncertain observation; the cost of the algorithm is 2β2^\beta times a polynomial. Local DP is our implementation of Algorithm 1; its solver-free implementation evaluates every step by exact polygon operations in rational arithmetic, without an LP solver (Appendices S and V).

Exact answers do not depend on either assumption. With the enlarged blocks of Corollary 11, Algorithm 1 returns the exact minimum, with a rational witness and an exact exclusion, on every input of the model. The two assumptions only bound its running time.

"Changes only increase the signal's slope." The reset does not need this.

  • With jumps of either sign, the slopes that can leave an exactly observed interval whose timing window opens at its start still form one interval containing the chord slope. The algorithm carries over, with 3β3^\beta in place of 2β2^\beta (Proposition 18 and Corollary 19, Appendix U).
  • Our implementation of signed jumps agrees with certified enumeration on 1,800 random signed instances and returns the exact minimum on signed inputs with n=4,096n = 4{,}096 in under 22 CPU seconds.

"Suitable exact checkpoints separate uncertain stretches." Checkpoints need not be designed: random uncertainty keeps the uncertain stretches short, and long stretches cost far less in practice than in the worst case.

  • Random uncertainty keeps stretches short. If each sample is uncertain independently with probability ρ\rho, then β\beta grows only logarithmically in nn: with probability at least 1−δ1-\delta, 2β<(n/δ)c2^\beta < (n/\delta)^c, where the exponent cc is about 0.67 at ρ=0.1\rho = 0.1, 1.04 at ρ=0.2\rho = 0.2 and 1.51 at ρ=0.3\rho = 0.3, so the cost is polynomial with high probability (Proposition 16, Appendix T). For example, at n=4,096n = 4{,}096 with one sample in five uncertain, β<20\beta < 20 with probability at least 0.99 (Table 28).
  • Sparse uncertainty makes the expected work linear, and bursts or random timing restrictions do not change the picture. When fewer than about 19 % of samples are uncertain on average (ρ<0.19\rho < 0.19), the expected number of subproblems the algorithm enumerates grows at most linearly in nn. The same logarithmic bound holds when uncertain samples come in bursts and when intervals with a positive lower timing end occur at random (Corollary 17).
  • In practice the cost is far below the worst case. On 192 random inputs with nn from 512 to 16,384 and up to half of the samples uncertain, blocks reached 49 intervals, enough for 2492^{49} event patterns in the worst case. Yet because the algorithm discards any reachable set contained in another one reached with no more events, it never stored more than 55 polygons, and it finished in at most 36 CPU seconds, with time growing about linearly in nn (Appendix V.2, Table 31).
  • Timing windows that do not open at the interval start are handled too. Corollary 11 covers them and is now implemented; all 48 test decisions agree with enumeration (Appendix G.5, Table 19).

"When every measurement is uncertain, the search can still become exponentially expensive." Our bound confines the exponential cost to the uncertain stretches, and in practice exact answers come quickly even with no exact checkpoint at all (Appendix V.5, Table 34). Inputs in which every interval touches an uncertain observation are exactly those of the NP-completeness proof (Proposition 5), so no exact method, MILP and verified branch-and-bound included, is known to be efficient on all of them.

  • On random inputs in which every sample is uncertain, with nn up to 4,096, the method returns the exact minimum in at most 10 seconds and never stores more than 13 polygons.
  • On the retail log with every checkpoint quantized, it certifies all 32 inputs of 1 and 7 days (up to 1,008 labels) in at most 40 seconds.
  • It also solves the six contracts of our downstream pilot whose 24 or 48 samples are all uncertain, and proves that the MILP's sparse models for them are minimal.
AuthorsOpenReview ↗

Response to Reviewer i89x (part 2/2)

"666 of 672 … small, constructed tasks." The retail evidence is now complete, faithful to the model and large.

  • All 672 retail queries are now decided: the solver-free evaluation settles the six that were open (Appendix V.4, Table 33).
  • The log-derived queries are exact instances of the model. Integrated arrival counts satisfy constraints (1)–(3) exactly, with one jump per occupied ten-minute bin, and checkpoints (the observed values at bin boundaries) are released either exactly or as quantization cells, the interval obtained by rounding a value, as for low-precision telemetry (§6, Appendix I). Every window was fixed before solving.
  • The evidence is large. From the same public log we certified exact minima for 128 new inputs with 12–96 labels (32 windows, four release regimes each, as in the submission; each in under 0.2 seconds) and for 48 inputs of 1, 7 and 28 days with up to 4,032 labels (each in under 5 seconds), against 6 labels in the submission (Appendix V.3, Table 32).
  • Exact minima also show what standard tools get wrong: on 188 inputs, the ℓ1\ell_1 relaxation (minimizing the total jump size) proposes more events than necessary on every input (median 1.8 times the minimum), and ℓ1\ell_1 trend filtering (fitting a piecewise-linear signal with a penalty on the total slope change) returns a signal that no compatible trajectory realizes on 166 of them (Appendix V.7, Table 36).

"About as fast as another certifying optimization approach." Evaluated without an LP solver, Local DP is clearly faster than verified branch-and-bound, and the gap grows with the input. Already on the six-label taxi inputs of the submission, Local DP used slightly less CPU than the certifying MILP cascade and never needed the enumeration fallback, which the cascade needed 6 and 9 times (Table 8). The evidence (Appendix W; CPU seconds, separate runs on the same server):

  • Faster on every query, and increasingly so. On 180 real-log and random inputs not built for this comparison, Local DP used less CPU than verified branch-and-bound (exact SCIP 10.1, whose rejections carry VIPR certificates, machine-checkable proofs of infeasibility) on all 349 queries both certified, with the same answers. The median ratio of SCIP's time to ours grows with the input, from 3.4 at 12 labels to 38 at 96 labels on retail windows, and from 6.4 at n=32n = 32 to 151 at n=256n = 256 on random inputs.
  • It answers where verified branch-and-bound runs out of time. At n=512n = 512 and 1,0241{,}024, SCIP certifies no infeasible budget within 600 seconds; our method needs under 0.6 seconds. On a panel built to stress the cheap bounds, SCIP needs 18–47 seconds to certify the infeasible budgets at n=66n = 66 and does not finish at n=130n = 130 within 600 seconds; our method needs under 0.1 seconds on both.
  • One run answers every budget. One Local DP run returns the minimum, and with it the answer for every budget; a solver answers one budget per run.
  • The two approaches also work together. On the downstream contracts, the MILP finds a sparse model and Local DP certifies that it is minimal.
  • It is the same algorithm. The solver-free implementation reproduces all 3,406 certified facts of the submission's experiments (Appendix V.4).

In short, the two assumptions bound only the running time, never the exactness: the reset holds for jumps of either sign, random uncertainty keeps the uncertain stretches short with high probability, and even with no exact checkpoint the method answers exactly within seconds on inputs with thousands of labels. Evaluated without a solver, the method certifies both sides of the budget question, a witness when kk events suffice and an exact exclusion when they do not, at thousands of labels in seconds, and it used less CPU than verified branch-and-bound on every query that both certified.

We hope that our responses address all of your concerns, and we would be grateful if you would take them into account in your final assessment.

Reviewer_HYoROpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a verification method to decide whether at most k events can model a trajectory with non-negative, capped velocity jumps. The papers contributions is an analysis of the problem and its properties, a formulation of an approach to the problem and its analysis and an experimental investigation.

Critical strengths

The setting is interesting and worth investigating.

Critical weaknesses

As is, the paper is very hard to understand. It is unclear what the paper is proposing or analyzing, and major concepts are not well explained. The readability is quite low and it is very hard, borderline impossible, to understand what is going on, despite being generally familiar with the topic of time-series.

This starts in the introduction, e.g.: "can at most k events explain everything that was observed? An exact answer has two sides. A compatible trajectory with at most k events certifies that the budget suffices; showing that it is too small requires excluding every such trajectory. Convex relaxations can accept explanations that no trajectory realizes, and floating-point solvers can report infeasibility without proof. We ask when both sides can be certified exactly and efficiently." First off, it is unclear what it means for an k events to "explain" what was observed. Then, what does it mean for a trajectory to be compatible? the reader is left confused and without explanation. But more crucially, what are these convex relaxations? No literature is being cited and a definition is also not given. Also, the vague term "floating-point solvers" is also just stated, without any citation, reference etc. It also continues with similarly vague sentences, like "a forward dynamic program must carry, for each budget, the set of velocities reachable by a compatible prefix, which is a union of intervals contributed by different support patterns." (page 2). No explanation of what the forward dynamic program is, which budget is mean, what the explanation of the compatible prefix ("which is a union of intervals contributed by different support patterns") is also lacking. Similarly, the sentence afterwards is also hard to understand, which reads "Our main positive result is a reset that removes this branching at exactly observed intervals", is it unclear what branching in this context refers to, and it is not defined in the section. Also, what the word "reset" here refers to is not clear.

More crucially though, this inaccuracy is also in section 3 (MODEL AND EXACT EXPLANATIONS), where exactness is crucial since it should formally state the problem. For example, it starts like this: "There are n≥1 labelled intervals of duration D>0 and sampled positions p0,...,pn, from which known acceleration has been subtracted. Interval i carries a jump 0 ≤ji ≤J in velocity at delay τi ∈[li,ui] ⊆[0,D] from its start. With wiw_i the velocity entering interval I and ri=(D−τi)jir_i = (D−τ_i)j_i, compatibility is equivalent to (statements)". It is unclear what the label of these labelled intervals are, whether the duration is meant as the total time? What is mean with "from which known acceleration has been subtracted.", it is not a formal statement. It is not clear how the rir_i comes into the picture and finally what is meant with "compatibility is equivalent to (..)". Is this a definition, like some form of compatibility (to what?)? What is the motivation and interpretation here? This needs a proper formalization, where crucial concepts are not brushed over in prose.

Defintion 1 needs an interpretation and example, as it is crucial, but as is it is very hard to parse, like "OPT is its minimum cardinality", the minimum over what? it needs to better formalized. Mathematical definitions should not be stated in vague prose and appending definition in front of it does not formalize a unspecific statement.

The next sentence is again hard to parse: "Support counts labelled events: two events at adjacent window endpoints of intervals iand i+ 1 count twice". What is a "labelled event"? What is the difference to a jump? Which window does this example here refer to? It then continues with "For an allowed mask S, setting ji=ri=0j_i = r_i = 0 outside S gives a rational LP that is feasible exactly when a physical trajectory supported within S exists;" It is not clear what S refers to here, what is this mask? But then, even more crucially, what is meant with the rational LP, is this a rational linear program? How is it defined? How does it arise from S? it is totally unclear and this in the main definition section of the paper leaves the reader confused and without a good grasp of the problem. The LP needs to be properly defined.

It also continues with vague sentences like "The support of the trajectory that generated an input is only an upper bound, and an unfinished computation certifies nothing." It is not clear with "unfinished computation" refers to in this sentence.

These were excerpts from the question of section 3, but without section 3 the reader lacks the basis to understand the algorithm. Sections 4 and 5 continue similarly.

Finally, a major crucial problem is that in figure 5 the method proposed is never really formally stated. It reads like a loose collection of theorems, but a complexity results needs an algorithm. And for reproducibility we also need an algorithm. It is unclear where the method proposed enters, what it is and how to compute it.

Questions for authors

What are the unclear definitions and statements mentioned in the weakness section?

Furthermore:

  • page 3: "strengthen convex relaxations of event inference" => what convex relaxations is this referring to? This is crucial as the convex relaxation is repeated throughout the paper but never defined.
  • page 3: "Inactive arcs preserve H and force ji=ri=0j_i = r_i = 0; active arcs append I and increment c, with c ≤k." => the previous definition was a graph, it is not clear what an 'arc' should be
  • page 3: "Each incoming-head and outgoing-tail copy is given its own lookahead LP" What is this LP? How is it defined?
  • page 3: "Conservation relates averages." What is meant with this sentence, this is not a scientific, precise statement and hard to interpret.
  • page 3: I belief theorem 2 is not really a theorem, as it is just an definition of an example. It does not appear to adhere to the generally agreed example/proposition/theorem hierarchy
  • page 4: the proof sketch is very vague, and it is not clear what the reader learns from it.
  • page 4: "The counterexample (Figure 2) separates missing continuous correlation from insufficient discrete memory." what is meant with continous correlation? I do not see randomness here? What is the discrete memory referring to?
  • page 4, prop 3: what is a perspective copy, fixed history prefix polyhedron and how does "flow" relate to the concepts? what is meant by a flow?
  • page 4: "A physical trajectory embeds directly. Conversely, normalize a terminal arc with positive flow" It is unclear what this means, what does it mean to embed directly, into what? What is mean with "normalize" "terminal arc" and "positive flow"
  • page 4: "The comparator can require exponentially many histories and prefix copies." It is unclear what the "comparator" is and what these copies are.
6 comments
AuthorsOpenReview ↗

Response to Reviewer HYoR (part 1/4)

Thank you for the detailed list of passages and questions; we used it as a checklist for the revision, and we are glad you find the setting worth investigating. We have made the presentation clearer and more explicit: §3 now states the problem formally, the method appears in the main text as an explicit algorithm, and every term you flagged is defined in the main text. The theorems, their proofs and every reported answer are unchanged. Below we first give a high-level summary of the paper (Part 1) and then answer your concerns one by one (Part 2). The page "Changes in this revision" (p. 13) maps each concern to its location and gives the old-to-new numbering.

Part 1: The paper in brief

The problem we tackle. Many methods explain data by a few discrete events; we ask whether such an explanation can be correct. A quantity grows at a constant rate, apart from a known trend, except at events, where the rate increases by a bounded amount, and each measurement is known only up to an interval. Can at most kk events produce a curve that passes through every measured interval (§1, §3)?

What existing tools miss. A "yes" is shown by one such curve, but a "no" must rule out every curve (Example 4, p. 4, shows both on three measurements). Convex relaxations, such as an ℓ1\ell_1 penalty on the rate changes, can over-count events or accept a number that no curve achieves; floating-point mixed-integer solvers report "infeasible" without a proof; and enumerating event placements takes exponential time, as the problem is NP-complete in general (Proposition 5).

Our method. A dynamic program scans the measurements in time order and keeps, for each number of events used so far, the exact set of reachable states (value and rate), computed in exact arithmetic. Our key observation (Lemma 6) is that a time step measured exactly at both ends, under a condition on when events may occur, merges all event histories into one, so the exponential cost is confined to the longest stretch of inexact measurements (Theorem 7, Algorithm 1). Every answer comes with a checkable certificate: a curve for "yes", an exact proof for "no".

Contributions.

  • An exact algorithm with certificates, exponential only in the longest stretch of inexact measurements (Theorem 7).
  • A proof that exact sets are needed: a natural convex relaxation that tracks the complete event history still accepts too few events (Proposition 8).
  • Proof-of-concept experiments on synthetic and log-derived inputs, with every answer checked exactly: the method settles questions that cheaper bounds leave open, scales to long inputs, and is faster than an exact mixed-integer solver that also proves its answers (§6, Appendices V–W).

Part 2: Main concerns

1. What the paper proposes. The revised introduction states the problem, the method and the contributions along the lines of Part 1. Its first paragraph defines trajectories, events, compatibility and the budget query, and names the relaxations and solvers it refers to, with citations; a new paragraph, "Questions and contributions" (p. 2), walks through the argument section by section.

  • What it means for kk events to "explain" the data, and what a "compatible" trajectory is.

    A trajectory is a signal whose rate of change (its velocity) jumps up only at events, and it is compatible if it passes through every observation interval. "At most kk events explain the data" means that a compatible trajectory with at most kk events exists. Formally, a compatible trajectory is a solution of constraints (1)–(3), and its events are its positive jumps (Lemma 1, Definition 2).

  • Which "convex relaxations" and which "floating-point solvers" are meant (also your question on p. 3).

    A convex relaxation replaces the event count, which is not convex, by a convex surrogate. We mean the ℓ1\ell_1 relaxation (minimum total jump size), the linear relaxation of a mixed-integer program with one on/off variable per interval, and the flow relaxation of §5. The floating-point solvers are linear-programming (LP) and mixed-integer (MILP) solvers such as HiGHS, whose "infeasible" status is not a proof. The introduction now cites both.

AuthorsOpenReview ↗

Response to Reviewer HYoR (part 2/4)

2. The problem is stated formally in §3 (pp. 3–5). §3 now defines the model in continuous time, derives the constraints in a lemma, defines the minimum OPT\mathrm{OPT} and the budget query, defines the linear program for a fixed set of allowed jump positions and the three possible outputs, and works an example by hand.

  • Labels, the duration DD, and "known acceleration has been subtracted".

    x(t)x(t) is the signal, and label ii is the sampling interval [iD,(i+1)D][iD, (i+1)D], so DD is the sampling period, not the total time. Subtracting the known acceleration γ\gamma means working with pi=x(iD)−γ(iD)2/2p_i = x(iD) - \gamma (iD)^2/2. Table 1 collects the notation.

  • Where rir_i comes from, and whether "compatibility is equivalent to (1)–(3)" is a definition.

    It is a lemma with a proof (Lemma 1). A jump jij_i at delay τi\tau_i adds (D−τi)ji(D - \tau_i) j_i to the change in value over the interval, and naming this product rir_i makes the constraints linear. Compatibility means passing through every observation interval.

  • Definition 1 (the minimum over what, with an interpretation and an example), and "labelled event" versus jump and which window.

    OPT\mathrm{OPT} is the minimum, over all solutions of (1)–(3), of the number of intervals with a positive jump ji>0j_i > 0, or +∞+\infty if there is no solution (Definition 2). An event is such a positive jump, labelled by its interval ii. The window is the timing window [li,ui][l_i, u_i] of each interval, so a jump at the very end of interval ii and one at the very start of interval i+1i+1 count as two events. Example 4 works a two-label case by hand.

  • The mask SS, the "rational LP", and "unfinished computation".

    SS is the set of labels allowed to jump, and PSP_S is the linear program given by (1)–(3) plus ji=ri=0j_i = r_i = 0 outside SS, with rational data; it has a solution exactly when a trajectory with jumps only inside SS exists (Definition 3). A method returns ACCEPT with a checked trajectory, REJECT with an exact proof, or UNKNOWN if it stops at a time or call limit before producing either. An unfinished computation is an UNKNOWN and is never counted as an answer.

3. The method is stated as an explicit algorithm (§4, Algorithm 1, p. 6). Algorithm 1 states the input, the sets it stores, each update and the output; Theorem 7 (p. 7) gives its running time, and Appendix C proves it. The submission stated the method as a five-step procedure within the proof of the main theorem (its Appendix C); the revision moves it into the main text and adds a figure of one update step (Figure 16, Appendix S). For reproducibility, the supplementary material contains a reference implementation (about 500 lines of standard-library Python) and a script that reproduces Example 4 and the minimum of three in Proposition 8.

  • "Forward dynamic program", "budget", "union of intervals contributed by different support patterns", "branching" and "reset" (p. 2).

    These terms describe Algorithm 1. A prefix is the part of a trajectory up to the current sample; its state is its position and velocity there, and its pattern is the set of earlier labels that carry an event. The forward dynamic program scans the labels from left to right and keeps, for each budget level (an upper bound on the events used so far), the set of states that prefixes can reach. For one pattern this set is a convex polygon, and an exactly observed sample cuts it to one interval of velocities; the stored set is the union of these intervals, and branching is the growth in their number. The reset (Lemma 6) merges them into a single interval at every exactly observed interval whose timing window opens at its start (§4, Figure 3).

AuthorsOpenReview ↗

Response to Reviewer HYoR (part 3/4)

4. The relaxation section (now §5, after the algorithm) shows that exact sets are needed, and defines every term it uses. A natural cheaper alternative to exact sets is a convex relaxation that sends one unit of flow through a layered graph whose nodes record the sample index and the complete history of earlier events. On explicit inputs that need three events it accepts two (Proposition 8), because it may replace one state by a weighted mix of two states whose average slope is right, although no compatible signal with that history reaches either.

  • "Arc", "flow" and the perspective form (p. 3).

    Layer ii of the graph holds the nodes for sample ii; a source node precedes the first layer and a sink follows the last, and an arc joins a node of layer ii to a node of layer i+1i+1. A flow places nonnegative mass on the arcs, and the perspective form of (1)–(3) multiplies every bound by that mass. A physical trajectory is one source–sink path of mass 1 (§5, p. 7).

  • "Own lookahead LP" and "conservation relates averages" (p. 3).

    Each end of an arc gets an LP over the remaining intervals in which the number of events is relaxed to fractional values. Conservation requires the mass-weighted sum of the outgoing states to equal the incoming state, so only their average velocity is preserved.

  • Theorem 2 is "not a theorem", and its proof sketch is vague (pp. 3–4).

    It is now Proposition 8. It covers every member of the family (each rational parameter λ\lambda strictly between 0 and 1) and proves that no two-event trajectory exists, which shows that remembering every event history is not enough. Appendix B states the two facts the proof uses and writes out every witness.

  • "Continuous correlation" (there is no randomness) and "discrete memory" (p. 4).

    There is no randomness; we renamed the term state–prefix association: each continuous state must be reachable by a prefix whose events are those recorded in the node's history HH. Discrete memory is HH.

  • Proposition 3 (now Proposition 9): "fixed-history prefix polyhedron", "perspective copy", "embeds directly", "normalize a terminal arc with positive flow", and the "comparator" and its "copies" (p. 4).

    The fixed-history prefix polyhedron Qi,HQ_{i,H} is the set of prefixes through sample ii with jumps only in HH, and a perspective copy is Qi,HQ_{i,H} scaled by an arc's mass. Attaching a copy to every outgoing arc gives the comparator, a flow formulation that is exact but can be exponentially large, which Algorithm 1 avoids. In the proof, "embeds directly" means that a physical trajectory is itself a feasible flow, a single path of mass 1; a terminal arc is an arc across the last label, and normalizing it divides its variables by its mass (Proposition 9).

Reviewer_vAoHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the minimum-event explanation problem under localized observation uncertainty. The authors show that the problem is NP-complete in general and propose an exact algorithm with complexity 2βpoly(n,β,L)2^\beta \mathrm{poly}(n,\beta,L) by exploiting the shared-endpoint reset structure, where β\beta denotes the length of the longest uncertainty block. Experiments show that the proposed method works on several synthetic and log-based datasets and is more efficient than exhaustive enumeration in some cases.

Critical strengths
  1. The paper discusses how to obtain reliable and verifiable sparse event explanations under observation uncertainty. The authors clearly explain why approximate or purely numerical solutions may not be sufficiently reliable.
  2. The authors clearly distinguish between ACCEPT, REJECT, and UNKNOWN outcomes, report both successful and unsuccessful experimental results, and provide a relatively thorough discussion of the method’s limitations.
Critical weaknesses
  1. The applicability of the method is relatively limited. The core algorithm relies on localized uncertainty and the shared-endpoint reset condition. When uncertainty extends over long consecutive regions, or when more intervals have positive timing lower bounds, $\beta$ can approach nn, causing the exponential complexity advantage to largely disappear. How effective would the proposed method generalize to settings where these structural assumptions do not hold?

  2. The experiments do not demonstrate a sufficiently strong practical advantage. The Retail experiments are relatively small-scale, and although Local DP is faster than exhaustive enumeration on the Taxi experiments, its computational cost is comparable to that of the certifying MILP cascade. In addition, Local DP does not show benefits in the downstream sparse surrogate experiment.

Questions for authors
  1. The theoretical framework can handle more general timing windows by enlarging the blocks, but cases with positive timing lower bounds are still marked as N/A in the current implementation. Is this mainly an implementation limitation, or would such cases also significantly reduce the scalability of the method in practice?

  2. In the Taxi experiments, Local DP is faster than exhaustive enumeration, but its computational cost is very close to that of the certifying MILP cascade. Could the authors clarify what types of problem settings are expected to show a clearer advantage of Local DP over the certifying MILP approach?

4 comments
AuthorsOpenReview ↗

Response to Reviewer vAoH (part 1/3)

Thank you for the careful reading and for two concrete questions, which led to our most informative new experiments. We now state the model and the algorithm more explicitly in the main text. On the substance, the new results answer both weaknesses and both questions. The advantage over a certifying MILP is now clear: the method proves that no sparser explanation exists in cases the MILP cascade leaves open, it needs less time than the strongest certifying solver on every query both answer, and the gap is largest on the largest inputs. Every previously not-applicable cell is now decided, and the method stays fast well beyond its structural assumptions. The retail experiments are now large, and in the downstream experiment the method proves that the MILP's models use the fewest slope changes possible.

Below, nn is the number of labels (sampling intervals) and β\beta is the length of the longest block, a run of intervals that touch an uncertain observation; the cost of the algorithm is 2β2^\beta times a polynomial. Local DP is our implementation of Algorithm 1; its solver-free implementation evaluates every step by exact polygon operations in rational arithmetic, without an LP solver (Appendices S and V).

Presentation. The revision presents §3 as a formal model with a worked example and states the algorithm in the main text as Algorithm 1, with a figure (see the general comment).

W1: when the structural assumptions weaken. The method remains effective well beyond them.

  • Random rather than designed uncertainty keeps blocks short. If each sample is uncertain independently with probability ρ\rho, the longest block grows only logarithmically in nn: with probability at least 1−δ1-\delta, 2β<(n/δ)c2^\beta < (n/\delta)^c, with exponent cc about 0.67 at ρ=0.1\rho = 0.1, 1.04 at ρ=0.2\rho = 0.2 and 1.51 at ρ=0.3\rho = 0.3. When fewer than about 19 % of samples are uncertain on average (ρ<0.19\rho < 0.19), the expected number of subproblems the algorithm enumerates grows at most linearly in nn. This is Proposition 16 (Appendix T), with proof.
  • Bursts and positive lower timing ends barely change this. β\beta stays logarithmic in nn with high probability when uncertain samples come in bursts, and when intervals with a positive lower timing end occur at random (Corollary 17). At ρ=0.1\rho = 0.1, the exponent cc rises only from 0.67 to 0.75 when one interval in ten has such an end, and to 0.92 when one in four has.
  • Long uncertain regions are cheap in practice. On 192 random inputs with nn from 512 to 16,384 and up to half of the samples uncertain, independently or in bursts, blocks reached 49 intervals. The algorithm discards any reachable set contained in another one reached with no more events, and it never kept more than 55 sets at a time. All 192 inputs were solved exactly, in at most 36 CPU seconds, and the time grew about linearly with nn (Appendix V.2, Table 31).
  • Even with no exact observation at all (β=n\beta = n), exact answers are often quick. On random inputs in which every sample is uncertain, with nn from 64 to 4,096, the method returns the exact minimum for all 24, in at most 10 seconds, and never stores more than 13 polygons. On the retail log with every checkpoint quantized, it certifies all 32 inputs of 1 and 7 days in at most 40 seconds. It also solves the six contracts of our downstream pilot whose 24 or 48 samples are all uncertain (Appendix V.5, Table 34).
  • Jumps of either sign are covered too. The reset also holds when jumps may have either sign, with 3β3^\beta in place of 2β2^\beta (Proposition 18, Corollary 19); signed jumps are implemented and tested up to n=4,096n = 4{,}096.

Our running-time bound is a worst-case bound; the results above show how far typical inputs are from it.

Q1: positive lower timing bounds. The theory already covered these cases, and they are now implemented and decided; when such intervals occur at random, blocks stay logarithmic in nn (Appendix G.5; Appendix K, Table 19).

  • Corollary 11 (Corollary 9 in the submission) absorbs an interval whose timing window has a positive lower end into the neighbouring block. We implemented it.
  • On the 16 cells previously marked not applicable, Local DP now returns 11 ACCEPT and 5 REJECT, each agreeing with exact enumeration.
  • On 16 new cells in which such an interval would otherwise act as a reset, it decides all 16, again in agreement with enumeration; on 16 control cells with zero lower ends its decisions are unchanged. The solver-free implementation needs no special case for timing windows and reproduces all 48 decisions.
  • When such intervals occur at random, the longest enlarged block is still logarithmic in nn with high probability (Corollary 17). On the new cells where absorption lengthens blocks from two to three intervals, Local DP used 8.8 CPU seconds in total, against 55.0 for exact enumeration.
AuthorsOpenReview ↗

Response to Reviewer vAoH (part 2/3)

W2 and Q2: where Local DP is clearly better than the certifying MILP cascade. Local DP shows a clear advantage on the tested infeasible-budget queries, and its advantage grows with the input.

On the taxi panels Local DP already used slightly less CPU than the certifying MILP cascade, and never needed its enumeration fallback. The cascade fell back to enumeration 6 and 9 times (Table 8). With six labels per input, most of each execution's cost, about a quarter of a CPU second, is process start-up, imports and setup; the solver-free implementation solves all 24 cases of a taxi panel in 0.06 CPU seconds of solve time in total (Appendix V.4).

Where the advantage is clear.

  • Local DP certifies "no" answers that the MILP cascade leaves open. A MILP proves "yes" with one solution, but its "infeasible" status is a floating-point claim. A certified "no" needs enumeration or verified branch-and-bound, whose certificate is the whole search tree (Cheung et al., 2017); here those certificates reached 750 MB. Local DP proves "yes" and "no" in the same scan. On the regime panel below, the certifying MILP cascade certifies at most 2 of the 12 infeasible budgets; Local DP certifies all 12.
  • The gap grows with the input. For a fixed block length, Local DP's cost is polynomial in nn (Theorem 7) and grew about linearly in our runs. The median ratio of the CPU time of verified branch-and-bound to ours grows with the input: from 3.4 at 12 labels to 38 at 96 labels on retail windows, from 6.4 at n=32n = 32 to 151 at n=256n = 256 on random inputs, and from 9 at n=18n = 18 to 431 at n=130n = 130 on the regime panel (Appendix W, Tables 37–38).
  • One run answers every budget. One Local DP run returns the minimum, and with it the answer for every budget; a MILP answers one budget per run.

A direct test confirms this on budgets that cheap bounds leave open (Appendix W.1, Table 37). We froze a panel of budgets that the LP-relaxation bound and block-cap leave open: three families with longest block β\beta of 2 or 4 intervals and nn from 18 to 194 labels, each input queried at the largest infeasible budget (k=OPT−1k = \mathrm{OPT} - 1) and at the minimum (k=OPTk = \mathrm{OPT}). We ran verified branch-and-bound: exact SCIP 10.1, whose rejections carry VIPR certificates (machine-checkable proofs of infeasibility) checked by viprchk, with witnesses checked in exact arithmetic. CPU seconds, separate runs on the same server:

Queries (count)Local DP, solver-freeExact SCIP + VIPR
Infeasible, β=2\beta = 2, n=18n = 18–3434 (4)4 REJECT, 0.01–0.03 s4 REJECT, 0.2–0.9 s
Infeasible, β=2\beta = 2, n=66n = 66 (2)2 REJECT, 0.04 s2 REJECT, 18–47 s
Infeasible, β=2\beta = 2, n=130n = 130 (2)2 REJECT, 0.06 snone in 600 s
Infeasible, β=4\beta = 4, n=26n = 26 (1)REJECT, 0.06 sREJECT, 1.3 s
Infeasible, β=4\beta = 4, n=50n = 50–194194 (3)3 REJECT, 0.08–0.27 snone in 600 s
Feasible (12)12 ACCEPT, 0.02–0.26 s11 ACCEPT
  • Local DP decides all 24 queries. Verified branch-and-bound certifies 7 of the 12 infeasible budgets.
  • On the infeasible budgets at n=66n = 66, SCIP required more than a hundred times as much CPU time as Local DP; at n=130n = 130 (β=2\beta = 2), and from n=50n = 50 at β=4\beta = 4, it is the only certifying method that rejects them.

The same holds on 180 further inputs not built for the comparison (Appendix W.2, Table 38): 128 retail-log inputs (12–96 labels), 48 inputs with random uncertainty (n=32n = 32–256256) and four larger random inputs (n=512n = 512 and 1,0241{,}024), each at k=OPT−1k = \mathrm{OPT} - 1 and k=OPTk = \mathrm{OPT}.

  • Wherever verified branch-and-bound certifies an answer, it confirms ours: 349 certified answers, no disagreement, and Local DP used less CPU on every one.
  • Local DP needs at most 0.21 seconds on every input up to n=256n = 256 and at most 0.55 seconds at n=512n = 512 and 1,0241{,}024. Verified branch-and-bound needs up to 100 seconds per query on the 96-label retail inputs; at n=256n = 256 it certifies 9 of the 12 infeasible budgets, and at n=512n = 512 and 1,0241{,}024 none of the four, even in 600 seconds.
  • Across all three comparison panels (788 certified query records), Local DP used less CPU on every query.

It is the same algorithm, and it is correct. Re-solving all ten main experiment panels of the submission reproduces all 3,406 certified facts and decides every query on which the submitted Local DP returned UNKNOWN (§6.5, Appendix V.4); the solver-free implementation also agrees with certified enumeration on 7,800 random instances.

Local DP's advantage is therefore clearest where certification matters most: proving that no sparser explanation exists, on inputs beyond a few dozen labels.

AuthorsOpenReview ↗

Response to Reviewer vAoH (part 3/3)

W2: "The Retail experiments are relatively small-scale." They no longer are. We built new windows from the same public retail log with the same release rule, froze them before solving, and certified the exact minimum for every one (Appendix V.3, Table 32). A label is one ten-minute sampling interval; each window is released in four regimes, as in the submission.

SetLabels per inputInputs (windows × 4 regimes)Exact minima certifiedLargest CPU time
Submission6128128—
New, within one day12–961281280.15 s
New, 1 day14416160.2 s
New, 7 days1,00816161.2 s
New, 28 days4,03216164.9 s

The 28-day windows have 672 times as many labels as those in the submission.

W2: "Local DP does not show benefits in the downstream sparse surrogate experiment." It now does (Appendix V.6, Table 35).

  • With the solver-free implementation, Local DP returns the exact minimum number of slope changes for all 12 contracts of that experiment; six of them have no exactly observed sample at all.
  • In every contract, the minimum equals the number of slope changes in the MILP's candidate. The MILP found those candidates but could not show that no model with fewer slope changes exists; Local DP certifies that they are minimal. The two methods are complementary: the MILP finds a sparse candidate, and Local DP proves that none sparser exists.
  • The minimum is also an exact yardstick for other fits: on the 24-sample contracts the pilot's greedy sparsifier keeps 5 or 6 slope changes where the minimum is 2 to 4, and on the 48-sample contracts it returns the dense model, with 8 slope changes, where the minimum is 2 to 5.

Exact minima also show how far standard heuristics are from the true count. With certified minima at this scale, we repeated the audit of §6.4 on 188 inputs with 12 to 4,096 labels (the 176 retail inputs above and 12 random inputs; Appendix V.7, Table 36). Each cell counts inputs. ℓ1\ell_1 trend filtering fits a piecewise-linear signal with a penalty on the total slope change, and λ\lambda is the weight of that penalty.

HeuristicExact countOver-countNo compatible trajectory
ℓ1\ell_1 relaxation (minimum total jump size)0188 (median 1.8 times the minimum, up to 2.3)0
Reweighted ℓ1\ell_19179 (median 1.3 times)0
ℓ1\ell_1 trend filtering, λ=0.01\lambda = 0.01 or 0.10.1022166
ℓ1\ell_1 trend filtering, λ=1\lambda = 1010178
  • On the 28-day retail windows the ℓ1\ell_1 relaxation proposes about 1.9 times the certified minimum.
  • No heuristic ever proposed fewer events than the certified minimum.
  • Our scalable implementation of the audit reproduces all 640 categories of the submitted audit.

In short, the method answers exactly the two questions that matter for certified event inference, whether a sparse explanation exists and whether a sparser one is impossible, at scales well beyond the submission and faster than the strongest certifying alternative; where a MILP finds a good model, our method certifies that it is minimal.

We hope that our responses address all of your concerns; if you find that the main ones have been resolved, we would be grateful if you would consider re-evaluating your score.

AuthorsOpenReview ↗

Follow-up on our response to Reviewer vAoH

Dear Reviewer vAoH,

Thank you again for your careful reading and your two concrete questions. As the discussion period closes today, we would like to follow up on our response. Below is a brief summary of how we addressed each of your concerns and questions; please see our earlier replies for the full details.

  • Presentation. The revision presents the model formally with a worked example and states the algorithm in the main text as Algorithm 1, with a figure.
  • Beyond the structural assumptions (W1). When samples are uncertain at random, the longest block grows only logarithmically in nn, also with bursts and with positive lower timing ends, so the cost is polynomial with high probability (Proposition 16, Corollary 17). All 192 random inputs with up to 16,384 labels and up to half of the samples uncertain were solved exactly in at most 36 CPU seconds. Even with no exact observation (β=n\beta = n), exact minima for up to 4,096 labels take at most 10 seconds.
  • Positive lower timing bounds (Q1). These cases are now implemented: all 16 previously not-applicable cells are decided, and all 48 test decisions agree with exact enumeration.
  • Advantage over the certifying MILP (W2, Q2). Local DP certifies all 12 infeasible budgets of the regime panel, where the MILP cascade certifies at most 2. It used less CPU than verified branch-and-bound on all 788 certified query records, with a median speed-up reaching 431 times at n=130n = 130, and it answers in under a second on inputs where verified branch-and-bound runs out of time.
  • Retail scale (W2). Exact minima are now certified on retail windows of up to 4,032 labels, 672 times as many as in the submission, each in under 5 seconds.
  • Downstream experiment (W2). Local DP returns the exact minimum for all 12 contracts and certifies that the MILP's sparse models use the fewest slope changes possible.

The revised PDF includes these results. We would be happy to clarify anything that remains unclear.

In light of our responses and revisions, we would be grateful if you could reconsider your rating and recommendation.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of responses, new results and the revision (part 1)

We thank the reviewers for their careful reading, and for finding the setting worth investigating (HYoR) and the checkable certificates and transparent reporting valuable (i89x, vAoH). Following the reviews, we now state the model and the algorithm more explicitly in the main text. The reviews also asked whether the method reaches beyond small, structured inputs and whether it has a practical advantage over a certifying optimization solver. It does on both counts: its assumptions can be relaxed by short extensions of the submitted proofs, and, evaluated exactly and without any LP solver, the same algorithm handles inputs far larger than in the submission and answers queries on which verified branch-and-bound runs out of time. The main results and their proofs stand as submitted.

What the paper does. The paper asks whether at most kk velocity jumps can explain position observations known only up to intervals, and answers exactly: a rational witness when the answer is yes, an exact exclusion when it is no. The general problem is NP-complete (Proposition 5); our algorithm confines its exponential cost to β\beta, the length of the longest run of sampling intervals that touch an uncertain observation.

The revision makes the model and algorithm explicit while preserving the original main results and proofs (HYoR, vAoH). We have uploaded a revised PDF. A page at the start of the appendix ("Changes in this revision", p. 13) maps each concern to its location and gives the old-to-new numbering; numbers in these replies refer to the revision. The main results, their proofs and all previously reported numbers are unchanged; the former Theorem 2 is now Proposition 8.

  • §3 (pp. 3–5) is a formal model: a continuous-time definition, a lemma deriving the linear constraints that define compatibility, definitions of the support, of OPT\mathrm{OPT} (the minimum number of jumps), of the budget query and of the masked LP, a notation table and a worked example.
  • Algorithm 1 (p. 6) states the method in the main text, and Figure 3 (p. 6) shows how it works.
  • The relaxation section (§5, pp. 7–8) now follows the algorithm and defines every term it uses.
  • The introduction defines trajectories, events and compatibility in its first paragraph, names the relaxations and solvers it refers to, with citations, and gives an overview of the argument.
AuthorsOpenReview ↗

Summary of responses, new results and the revision (part 2)

What the new evidence shows (i89x, vAoH). The reviews asked whether the method reaches beyond small, structured inputs and whether it has a practical advantage over a certifying solver. The new evidence supports four claims. Each is computed with the submitted algorithm on input sets fixed before solving; §6.5 points to them, and the details are in Appendices S–W (the timing-window run in Appendix G.5 and Table 19). Below, nn is the number of labels (sampling intervals).

  1. The submitted algorithm runs exactly without any LP solver and reproduces every certified answer of the submission (Appendices S, V). For a fixed set of allowed labels, the reachable (position, velocity) states form a convex polygon, so Algorithm 1 can be evaluated by exact polygon operations in rational arithmetic. Re-solving all ten main panels of the submission reproduces all 3,406 certified facts and decides the 17 queries on which the submitted implementation returned UNKNOWN, in under 2 CPU seconds for all 254 inputs. It agrees with certified enumeration on 7,800 random instances; every minimum has a rational witness, and every lower bound reported here is replayed by an independently written checker.
  2. It is faster than the strongest certifying alternative and answers where that alternative runs out of time (Appendix W). We compared with exact SCIP in rational arithmetic, whose rejections carry VIPR certificates (machine-checkable proofs of infeasibility). On all 788 query records in which both certified an answer, the answers agree and our method used less CPU time; the median ratio of SCIP's time to ours ranges from about 3 on 12-label retail windows to over 400 at n=130n = 130. Within 600 seconds SCIP certifies none of the infeasible budgets of random inputs with n=512n = 512 or 1,0241{,}024, nor those of a panel built from budgets that cheap bounds leave open, at n=130n = 130 or, with blocks of four intervals, from n=50n = 50; our method answers each of these in under a second.
  3. It scales to inputs thousands of labels long, and its assumptions can be relaxed.
    • Random inputs with nn up to 16,384 and up to half of the samples uncertain: exact minimum in at most 36 CPU seconds, with time growing about linearly in nn. Retail log: 28-day windows with 4,032 labels (the submission used 6) in under 5 seconds.
    • With no exact sample at all: random inputs with nn up to 4,096 in at most 10 seconds, never storing more than 13 polygons; the retail log with every checkpoint quantized, all 32 inputs of 1 and 7 days in at most 40 seconds.
    • If samples are uncertain independently at random, β\beta grows only logarithmically in nn, so the cost is polynomial with high probability (Proposition 16). Timing windows with a positive lower end are now implemented; all 48 test decisions agree with enumeration. The reset also holds for jumps of either sign, with 3β3^\beta in place of 2β2^\beta (Proposition 18, Corollary 19).
  4. Exact minima are useful in practice. On all 12 contracts of our downstream pilot, a MILP solver finds a sparse model and our method proves that none with fewer slope changes exists. Repeating the audit of §6.4 on 188 inputs of 12 to 4,096 labels, the ℓ1\ell_1 relaxation (minimizing the total jump size) proposes more events than the certified minimum on every input (median factor 1.8), its reweighted variant on 179, and ℓ1\ell_1 trend filtering (fitting a piecewise-linear signal with a penalty on the total slope change) returns a signal that no compatible trajectory realizes on 166.

In short, the revision states the model and the algorithm explicitly in the main text, and the new evidence, all computed with the submitted algorithm, shows that exact, certified minimum-event inference works well beyond the settings of the submission and faster than the strongest certifying alternative. Each reply below answers its reviewer's points in order, with locations in the revision; we would be glad to answer further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.