| paper | d4-conf-aaai-2017-0107 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Every admissible run satisfies the stated distributional regret inequality. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given a finite support of user types \(h\), rational masses \(\mu_h\) summing to one, a common feasible option set \(X\), and a complete preference and feedback model for each type, run an independent Coactive Critiquing learner for each type. After \(T\) rounds, does the mass-weighted mean regret \(\sum_h \mu_h \mathrm{REG}_{T,h}\) satisfy the mass-weighted sum of the Proposition 2 bounds under per-type \(\alpha\)-informativity, bounded feature norms, and the corresponding improvement-error and missing-feature terms? The finite cohort with \(n_h\) identical users of each type is represented by \(\mu_h=n_h/n\).
A continuum of users represented by masses \(\mu_h\) over complete preference and feedback types; each type receives its own recommendations and critique-driven feature updates from an independent Coactive Critiquing learner; the objective is mass-weighted per-user regret.
The paper proves a guarantee for one learner, while a heterogeneous cohort requires separate learners and per-type informativeness assumptions; the shared-learner guarantee proposed by the proponent is not established.
fatal: False
The mirror covers Proposition 2’s growing-feature regret guarantee across user types; it leaves the empirical comparisons, critique-selection heuristic, and any runtime guarantee for inference over the option catalogue unaddressed.
There is no paper result that satisfies your anchor rule: this paper proves no named NP-hardness, polynomial-time, FPT, or other complexity classification. Theorem 1 is a regret bound cited from Shivaswamy and Joachims (2015); Proposition 2 is proved here, but it too is a regret bound. So I can offer a positive mirror only by treating Proposition 2 as a nearby learning-theoretic anchor, not as the required complexity result.
Proposition 2 says that for an \(\alpha\)-informative user with true preference vector \(w^*\), and feature vectors bounded by \(R\), Coactive Critiquing’s average regret after \(T\) rounds is at most \(2R\lVert w^*\rVert/(\alpha\sqrt{T}) + \sum_{t=1}^T(\xi_t+\eta_t)/(\alpha T)\). Here \(\xi_t\) is the improvement error, while \(\eta_t\) accounts for utility change from features the learner has not yet acquired. The paper proves this result. Theorem 1 gives the fixed-feature-space version, with the \(\eta_t\) term absent, but is attributed to earlier work.
The continuous mirror I would defend is Mass Coactive Critiquing Regret. Imagine a large recommendation service making constructive recommendations for a recurring cohort, such as travelers planning tours through the same region. There are \(n\) users but only \(\tau\) recurring user types, with \(n\gg\tau\). A type specifies everything relevant to elicitation: utility weights, improvement behavior, and which critiques its members would provide. Its mass \(\mu_h\) is the fraction of the cohort of type \(h\), with rational masses summing to one. The catalogue \(X\) remains the paper’s feasible set of constructed options; the population, rather than the options, is continuous.
An instance consists of \(X\), an initial feature map, a finite support of \(\tau\) types with masses \(\mu_h\), and access to type-level improvement and critique responses. All types use a shared feature vocabulary, though their utility weights may differ. The learner proposes one \(x_t\) per round, receives an improvement and any elicited critique from each type, and updates using their mass-weighted feedback. Its objective is to minimize average per-capita regret against \(U_\mu(x)=\sum_h\mu_h\langle w_h^*,\phi^*(x)\rangle\), the cohort’s aggregate utility. The question is whether a learner can return recommendations and feature updates with a bound of the Proposition 2 form, using aggregate improvement error \(\xi_t^\mu\) and aggregate missing-feature contribution \(\eta_t^\mu\). Assume the mass-weighted feedback is \(\alpha\)-informative for \(U_\mu\) and feature vectors have norm at most \(R\). A finite cohort with \(n_h\) identical users of each type maps to \(\mu_h=n_h/n\).
I expect this regret question to be tractable—Class A—if each round’s inference over \(X\) is efficient. The mass-weighted update remains bounded, so the Proposition 2 argument has a natural aggregate version. That expectation concerns the regret guarantee; it does not establish polynomial-time inference for arbitrary constructive domains. It also does not supply the paper’s missing complexity result.
This mirror covers Proposition 2’s growing-feature regret guarantee, not the paper’s empirical results or the full Coactive Critiquing setting. The authors could plausibly recognize it as a multi-user extension: it preserves constructive options, improvement feedback, critique-driven feature growth, and regret. The soft spot is that the paper models one user’s evolving preferences, whereas this mirror optimizes aggregate cohort utility. It also needs a shared feature vocabulary and aggregate informativeness, assumptions the paper does not establish. So this is a plausible extension, but a weak fit for a programme seeking computational complexity mirrors anchored in named complexity results.
The strongest objection is that this paper has no computational-complexity result for ChoCo to mirror. Its only new formal result, Proposition 2, is a regret bound. Theorem 1 is a regret bound imported from earlier work. The experiments report performance, but establish no complexity classification for inference, critique selection, or feature acquisition. The paper’s \(T\) counts interaction rounds, not people in a population.
The proposed cohort model is coherent, and a shared trip recommendation for recurring traveler types is a plausible setting. But it changes the problem: the paper studies one user’s evolving preferences, while the mirror studies a common recommendation optimized for aggregate utility, with type-level feedback and an aggregate informativeness assumption. That could support a useful multi-user learning paper, but it is not a continuous-population version of a computational result here.
The better variants do not fix the fit. With a common feature map and one shared recommendation, the cohort objective is determined by the mean preference weights. With type-specific features, the computational question becomes optimization over the particular catalogue and feature functions; the paper specifies no restricted domain from which to derive a meaningful complexity classification. If each type instead receives its own recommendation, the problem separates by type unless one adds shared constraints such as capacity or fairness. Those constraints would define a new problem, not mirror a result in this paper.
So I can defeat Proposition 2 as a ChoCo anchor, but I cannot honestly defend the literal claim that no worthwhile population version could be devised. The negative case is weaker at that broader level: a multi-user extension may be worth studying, just not as this paper’s continuous computational mirror.
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.