| paper | d4-conf-ecai-2025-0386 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial time in \(T,\tau,L,E\). Exact prediction and posterior maintenance take \(O(L+\tau L^2+T\tau(E+L))\) bit operations using integer ratios whose numerators and denominators have \(O(L)\) bits. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3.1
statement extracted from the paper’s text layer
Given a finite support \(S\) of \(\tau\) evaluable binary prediction policies, a rational distribution \(\mu\) over \(S\), and a realizable sequence of \(T\) labeled cases, compute each online prediction by choosing the label with at least as much mass among policies consistent with prior cases, and update the posterior mass after each label. What exact running time and bit complexity suffice in \(T\), \(\tau\), the rational input length \(L\), and the policy evaluation cost?
The adviser pool is a fixed population of complete policy types \(t\in S\), with prevalence \(\mu_t\). That fixed distribution supplies the initial prior; the learner’s posterior after each round is a separate derived state, obtained by conditioning \(\mu\) on policies consistent with the observed cases. The decision each round is a binary prediction selected by comparing the two posterior masses, with mistakes bounded under realizability.
The mirror covers Proposition 3.1 through the Algorithm 3/Halving case, with Theorem 3.1 supporting the connection to LEA; it leaves the other algorithms, their cautious or agnostic regret bounds, and the belief-function combination complexity discussion aside.
My strongest positive case is a high-multiplicity version of Halving in which the population consists of advisers. It is a narrow mirror: the data still arrive over time, and predictions remain binary. The continuous object is the adviser pool itself.
Take a large deployment of binary prediction policies drawn from a small catalogue. A type is a complete policy: it gives the same prediction on every possible history and current input as every other adviser of that type. If there are \(N\) advisers but only \(\tau\) distinct policies, let \(\mu_t\) be the fraction using policy \(t\). This is a credible regime for replicated advisory systems or institutions drawing from a fixed bank of protocols, though it requires real agreement between copies, not just similar behavior on the cases observed so far.
The lead mirror is Continuous-prior Halving. An instance gives a finite support \(S\) of \(\tau\) policy types, rational masses \(\mu_t>0\) summing to one, and a sequential stream of binary-labeled cases. Assume realizability: some type predicts every label correctly. Before round \(j\), let \(V_j\) be the types consistent with all previous cases, and let
\[
W_{j,b}=\sum_{t\in V_j:\,h_t(x_j)=b}\mu_t.
\]
Predict \(1\) if \(W_{j,1}\ge W_{j,0}\), and \(0\) otherwise. After the label \(y_j\) arrives, retain only types predicting \(y_j\) and renormalize their masses. The computational problem is to produce these online predictions and posterior masses exactly, using the support and binary-rational input; a solution is the prediction and updated mass at each round.
This preserves the paper’s underlying task: aggregate expert advice to make predictions and control mistakes against the best expert. For \(N\) advisers with duplicate policies and uniform individual weights, the type masses are \(\mu_t=n_t/N\), so grouping advisers by type gives the same majority decision as ordinary Halving. The continuous version allows arbitrary rational proportions and asks for computation in \(\tau\) and their bit length, rather than in \(N\). With a realizable stream, each mistake at least halves the surviving mass, so the number of mistakes is at most \(\log_2(1/\mu_{t^\star})\) for any surviving correct type \(t^\star\). Exact simulation takes \(O(T\tau)\) arithmetic operations, with bit complexity polynomial in the input length.
My anchor is Proposition 3.1, proved in this paper: Algorithms 3, 4, and 5 can each be implemented in \(O(T|H|)\) time. The proposed mirror uses the Algorithm 3 case. The paper also establishes in Theorem 3.1 that Algorithm 3 makes the same predictions as Halving, and under realizability has \(O(\log_2 |H|)\) regret; that helps show this is still their LEA problem, rather than a simplified prediction task. The authors’ discussion of modifying Halving’s initial prior makes type-level masses especially plausible to them. I expect the continuous mirror to be tractable, a Class A result based on exact aggregation. The improvement is chiefly a smaller input representation, not a new algorithmic breakthrough.
The scope is just this Halving result. I would not claim the same mirror for Evidential Weighted Majority: its state is a mass function over expert subsets, and assigning ordinary population proportions to policy types does not by itself preserve that state or the update. The paper’s #P-completeness discussion concerns belief-function combination and is cited in prose; it is not a numbered hardness result I can use as an anchor under the stated rule.
The weak point is substantial: the paper already studies a finite set of experts, and merging duplicate policies into weighted types is a familiar extension of expert advice. Proposition 3.1 is already polynomial in the number of experts, so this does not show discrete hardness disappearing in a continuum. It is still a defensible population mirror because the population is the adviser pool, its masses encode prevalence, and the paper itself points toward nonuniform priors. A natural next question is whether a comparable exact type-mass representation can cover the paper’s cautious algorithms, especially outside the realizable setting.
The strongest anchor is Proposition 3.1, which gives an \(O(T|H|)\) implementation bound. Theorem 3.1 establishes that Algorithm 3 reproduces Halving’s predictions and gives a regret bound; it does not establish a separate computational complexity result. The proposed mirror is therefore mainly about Proposition 3.1.
The adviser-pool scenario is plausible: a large institution could have many copies of policies from a small catalogue. Given the catalogue and each type’s rational mass, weighted Halving predicts by summing the mass of currently consistent policies, then removes inconsistent types after each label. This is a well-posed mirror, and grouping exact duplicates preserves the predictions when their mass is used as the initial weight.
The problem for the negative case is that this mirror appears to be a routine weighted-expert version of an algorithm whose running time is already linear in the number of experts. With \(\tau\) supplied policy types, the update takes \(O(T\tau)\) expert evaluations and arithmetic operations. The continuous population changes the input representation from repeated policies to type masses; it does not give Proposition 3.1 a new computational task. Theorem 3.1 supports the connection to Halving, but its uniform initialization is not the proposed arbitrary-prior result. The paper itself points toward changing Halving’s initial prior, so the extension is natural and recognizable to the authors, while still looking like a small implementation variant rather than a new complexity question.
There is also a semantic gap to mind. The population mass would be an adviser’s prevalence, while the algorithm renormalizes mass over policies consistent with observed labels. That renormalized mass is the learner’s belief state, not the evolving composition of the adviser population. One can avoid conflating them by using prevalence only as the initial prior; then the model is especially clean, and especially close to weighted Halving. If instead the mirror uses a genuinely continuous space of policy types, the finite-\(|H|\) result no longer supplies a complexity bound: the policies and the integration or optimization over them need a tractable representation that this paper does not provide.
This makes the proposed mirror weak as a programme contribution, but it does not defeat it decisively. A fixed catalogue with many replicated advisers is a sensible high-multiplicity regime, and the mass-weighted problem is one the authors could recognize. The honest negative case is that the one surviving computational anchor offers little beyond compressing duplicate experts; I cannot rule out that an application where adviser prevalence has real meaning would make even that worthwhile.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.