| paper | d4-conf-aaai-2018-0710 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, already for \(\tau=d=T=1\) and \(k=2\), on instances satisfying all promises and conditional regret assumptions. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a finite support of customer cohorts with binary-rational masses \(\mu_\theta\), a shared feasible product space and feature map, a context stream for each cohort, and typewise choice fractions, can one compute cohort query sets and Choice Perceptron updates in polynomial time while attaining the mass-weighted expected average-regret guarantee?
A continuous population of customer cohorts, each with mass \(\mu_\theta\), a fixed but hidden linear utility vector, and its own Choice Perceptron state. Every member of a cohort receives that cohort's feasible query set; its choice fractions give the cohort-level expected update, and the objective is mass-weighted average regret.
The mirror assumes the recommender can identify cohorts whose members share the same hidden utility vectors; the proposed scenario requires those labels but does not explain how they are known.
fatal: False
The mirror covers Theorem 2's regret guarantee for homogeneous customer cohorts; it leaves the empirical comparisons and the computational complexity of query selection over hybrid product spaces unresolved.
The strongest positive case is a narrow one: this paper admits a continuous mirror for constructive preference elicitation across a large population of homogeneous customer cohorts. The society is the population of customers, not the product space. This stays close to the paper’s question—learning preferences by presenting feasible sets of products and observing choices—while making population shares, rather than headcounts, the natural quantities.
The lead anchor is Theorem 2, proved here. It states that for a user with fixed linear utility \(u^*(x,y)=\langle w^*,\phi(x,y)\rangle\), features bounded by \(\|\phi(x,y)\|\le R\), and a reasonable choice process, the Choice Perceptron has expected average regret at most
\[
\frac{\|w^*\|_2\sqrt{2\beta/\eta+4R^2}}{\alpha\sqrt{T}}
+\frac{2R\|w^*\|_2M}{T}.
\]
Here the query strategy must be \(\alpha\)-informative and \(\beta\)-affirmative, \(\eta\) is the update step size, and \(M\) is the number of expected uninformative iterations. This is a regret guarantee for the learning algorithm, not a runtime or complexity classification. The paper proves no named NP-hardness, polynomial-time, or parameterized-complexity result for the underlying query-selection problem.
A concrete mirror is Cohort Choice Perceptron. Its instance consists of a hybrid combinatorial product space \(Y\), a bounded feature map \(\phi\), a horizon \(T\), query size \(k\), and a finite support \(\Theta\) of customer types with binary-rational masses \(\mu_\theta\) summing to one. Each type has a fixed but hidden linear preference vector \(w^*_\theta\), a context stream, and a reasonable choice-response process. At each round, the elicitor presents a size-\(k\) feasible set \(Q_{\theta,t}\subseteq Y\) to each cohort and receives the exact fraction of that cohort choosing each item. The decision variables are the query sets and the estimates updated from those fractional responses. The objective is the mass-weighted average regret
\[
\mathrm{REG}^{\mu}_T
=\sum_{\theta\in\Theta}\mu_\theta\frac1T\sum_{t=1}^T
\min_{y\in Q_{\theta,t}}
\left(u^*_\theta(x_{\theta,t},y^*_{\theta,t})
-u^*_\theta(x_{\theta,t},y)\right),
\]
where \(y^*_{\theta,t}\) is the type’s optimal feasible product in that context.
The prover’s question is: given the succinct product constraints, masses, horizon, and cohort-level choice feedback, can one compute the query sets and updates with a running time polynomial in the feature dimension, support size \(\tau=|\Theta|\), input bit length, horizon, and product-space encoding size, while attaining the corresponding population regret guarantee? With type-specific \(\alpha_\theta,\beta_\theta,M_\theta\), Theorem 2 gives the direct-sum bound
\[
\mathbb E[\mathrm{REG}^{\mu}_T]\le
\sum_{\theta\in\Theta}\mu_\theta
\left(
\frac{\|w^*_\theta\|_2\sqrt{2\beta_\theta/\eta+4R^2}}
{\alpha_\theta\sqrt T}
+\frac{2R\|w^*_\theta\|_2M_\theta}{T}
\right).
\]
The continuum turns each cohort’s choices into fractional mass shares; averaging the Perceptron updates gives the expected update used in the theorem. The remaining computational question is whether the query-selection optimization over the hybrid product space can be solved efficiently. The paper casts that selection as a MILP, but does not settle its complexity. I would expect the regret analysis to extend cleanly, while exact query generation retains the combinatorial difficulty of the underlying product space; the paper supplies no hardness anchor to make that forecast a result.
A plausible regime is a large retailer’s configurable-product recommender with many customers but relatively few stable, well-defined cohorts: for example, recurring customers with the same product requirements and preference profile. Cohort labels and separate response shares must be available, while the preference vectors remain unknown to the elicitor. Millions of customers and hundreds or thousands of cohorts would make \(\tau\ll N\), with mass representing each cohort’s population share. The authors could recognize this as their constructive elicitation problem at population scale: the objects, menus, choice feedback, learning updates, and regret objective are all retained.
The weakness is the homogeneity and observability assumption. Real customer segments may contain different latent preferences, and aggregate feedback without cohort labels would not support the type-by-type updates in this formulation. This mirror therefore covers Theorem 2’s learning guarantee in a stratified population setting, not the paper’s full range of constructive tasks or a general population-choice model. It is a credible but deliberately limited positive case.
Theorem 2 is the only strong anchor, and its target is one user’s sequence of choices for one fixed hidden utility vector. Its horizon \(T\) counts interaction rounds; the theorem contains no population variable. More tellingly, it gives a regret bound for any query strategy, without bounding the cost of computing that strategy. The proposed mirror joins that bound to a new polynomial-time query-generation question. The paper’s MILP may motivate that question, but Theorem 2 does not supply a computational result about it.
The cohort construction has a serious input problem. A ChoCo-style society must be given by its types and masses. Here, a type includes the user’s hidden preference vector and response behavior. If the recommender knows which customers share those hidden properties, it has been given the very grouping the elicitation process is meant to discover; if it groups by observable traits instead, the members need not share a utility vector. Adding each person’s context stream to the type makes the support problem harder still.
Assume away that problem and give the system cohorts whose members really do share a utility vector and context stream. If each cohort gets its own query sets and learner, the construction runs one Choice Perceptron per cohort. The masses weight the final regret; they do not create a population-level query-selection problem. That is a straightforward parallelization of the original task. If instead every member’s response is collected and used as an exact cohort fraction, the update and feedback model change: the paper analyzes an individual choice, while the continuum supplies an exact choice distribution.
A shared query set for heterogeneous customers is a stronger alternative. It is plausible for a retailer, but the feedback is now a mixture of choices from different hidden utilities. There is no single \(w^*\) for that mixture, and the paper’s “reasonable user” assumption and regret bound do not cover it. Learning from aggregate group choices could be worthwhile, but it is a group-preference-learning problem that needs its own assumptions and objective; it does not mirror Theorem 2.
So the best case against is that the mirror either assumes access to latent cohorts and reduces to independent learners, or changes the paper’s single-user model into a new heterogeneous group problem. I cannot honestly make the universal negative airtight: a recommender researcher might regard common-menu elicitation from a large customer population as a natural extension of this work. That is where the case is weakest, and where a reader could still find a worthwhile 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.