UnivMon accuracy rule: use the paper guarantee (1±ε, failure probability 0.3) #788

Problem, by example

ASAPPlanner certifies UnivMon outputs with bounds derived for the library's earlier estimators (crates/logical-asap-optimization/src/accuracy/estimators/univmon.rs):

• an L2 bound: a layer-0 Count Sketch Chebyshev bound plus a binomial row-failure bound (L2_ROW_FAILURE, l2_relative_error, l2_failure_probability, l2_shape);
• a distinct-count bound: DISTINCT_VARIANCE, DISTINCT_MIN_HEAP, distinct_chebyshev, distinct_guarantee;
• an incomplete-top-layer probability bound (incomplete_top_layer_bound, incomplete_top_layer_probability).

asap_sketchlib #221 makes UnivMon follow the SIGCOMM 2016 paper's Algorithm 2 for every query. It documents the guarantee only as the paper's source states it, Braverman–Ostrovsky (arXiv:1011.2571, Algorithm 4.1, Lemma 3.8, Theorem 4.2): the G-sum estimate is within (1 ± ε) with probability at least 0.7, i.e. failure probability at most 0.3, provided that

• the number of layers is at least about log₂ n + 1;
• the heap size is at least φ³/ε², where φ is the number of layers;
• the Count Sketch estimates are within (1 ± ε).

The library takes no median of copies. The Planner's derived bounds, which give smaller failure probabilities, no longer describe what the library guarantees.

Expected

• UnivMon's accuracy rule states exactly the paper's guarantee. It applies to L1, L2, cardinality and entropy (Stream-PolyLog g): relative error ε, failure probability 0.3, under the conditions above.
• The sizing rule follows those conditions:
  • layers from the distinct-count bound n;
  • heap ≥ φ³/ε²;
  • a Count Sketch shape giving (1 ± ε) at that heap.
• A target asking for failure probability below 0.3 is not met by UnivMon. The derived bounds are removed.
• Tests and examples that select UnivMon use accuracy targets with failure probability at least 0.3.

Acceptance

• A test plans an L2 or entropy query with ε = 0.1 and failure probability 0.3. The UnivMon candidate is valid, sized by the paper's conditions, and carries a guarantee of relative error 0.1 with failure probability 0.3.
• The same query with failure probability 0.05 rejects UnivMon with NoAccuracyGuarantee.

Depends on asap_sketchlib #221 for the library's documented guarantee.