d4-conf-aaai-2023-1160

The strongest mirror I see is the continuous weighted Plackett–Luce M-step, anchored on Theorem 3.2. The paper proves this theorem, adapting the proof of Maystre and Grossglauser (2015): for a ranking dataset \(\Pi=\{\pi_1,\ldots,\pi_m\}\) with nonnegative weights \(q_1,\ldots,q_m\), Weighted LSR outputs the maximum weighted log-likelihood estimate
\[ \theta^{\mathrm{MLE}}_q =\arg\max_{\theta}\sum_{l=1}^{m}q_l\log P_{\mathrm{PL}}(\pi_l\mid\theta). \]
The paper uses this as the exact M-step for each mixture component. It does not prove a polynomial bit-complexity bound, so the theorem is an algorithmic anchor, not a formal “in P” result.

Here is the continuous problem I would hand to a prover. There are \(n\) items and a finite support \(S\subseteq\mathfrak S_n\) of complete rankings. Each \(\pi\in S\) has rational population mass \(\mu_\pi>0\), with \(\sum_{\pi\in S}\mu_\pi=1\), and a nonnegative rational weight \(q_\pi\), with \(\sum_\pi\mu_\pi q_\pi>0\). The weights represent a component’s responsibility for that report type in the current EM iterate. Assume a finite maximum exists, and identify utility vectors that differ by a common additive constant. The task is to output a maximizing normalized utility vector \(\theta\) for
\[ \sum_{\pi\in S}\mu_\pi q_\pi\log P_{\mathrm{PL}}(\pi\mid\theta), \qquad P_{\mathrm{PL}}(\pi\mid\theta) =\prod_{i=1}^{n-1} \frac{e^{\theta_{\pi_i}}}{\sum_{j=i}^{n}e^{\theta_{\pi_j}}}. \]
For numerical complexity, the corresponding version asks for a vector whose objective is within \(\varepsilon\) of the maximum. The type is a reported ranking; its mass is the fraction of respondents giving that ranking. In this M-step, equal rankings have the same responsibility, since the paper’s posterior weight depends on the ranking and current component parameters. Thus repeated reports can be aggregated exactly into \((\mu_\pi,q_\pi)\).

A plausible regime is a large preference survey in which many residents rank the same small set of policy options. For example, with \(n=5\), there are only \(5!\) possible report types, so tens of thousands of respondents can readily have much greater multiplicity than support size \(\tau=|S|\). That is a concrete high-multiplicity version of the paper’s ranking-data problem. The people need not have identical underlying tastes in every respect: the type is complete for this M-step because the likelihood computation uses the reported ranking and its component weight. The latent mixture and shared component utilities remain part of the model.

I expect this mirror to be Class A: its negative objective is convex in the \(n\) utilities, modulo the translation symmetry, and the paper’s Weighted LSR computes the weighted MLE. The population input exposes the frequency-compressed problem directly, with \(\tau\) ranking types rather than \(m\) individual records. The authors should recognize it as their weighted M-step with the sample sum written in terms of population masses. Further questions include the precise running time in \(n,\tau,L,\log(1/\varepsilon)\), conditions for a finite unique optimum, and whether the full mixture problem admits stronger guarantees when its input is a population distribution.

The scope is deliberately narrow: this mirrors Theorem 3.2’s component update, not the paper’s full mixture-learning guarantees, initialization, or global optimization of the nonconvex mixture likelihood. The paper has no named hardness result to anchor a claim that discrete hardness might dissolve. My weakest point is that the paper is statistical ranking-model learning, not a collective-choice problem about selecting winners or allocating outcomes. This is a credible continuous-population mirror of its M-step, but only a modest bridge into computational social choice.