Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the recovery of mixed multinomial logits using Frank-Wolfe algorithms. The authors proved that the proposed algorithm SSRFW converges to the true parameter of each individual mixture model. They also provided a sample complexity analysis of the proposed algorithm. 

strengths_and_weaknesses: The paper is generally well written and the results are interesting. Some clarification on the sample complexity of the subroutine should be added to the analysis. The comparison in the experiments could also be improved. See my specific questions in the next section. 
questions: Regarding the convergence of Algorithm 1 and Algorithm 2, I wonder whether the authors considered the computational complexity of Algorithm 2 in the analysis of the complexity of SSRFW. Specifically, how many iterations do step 4 of Algorithm 2 take to converge? And what is the order of $L$ in Algorithm 2 in order to get a good estimate of the input set $\mathcal{Q}$?

Can the authors elaborate more on the reason for obtaining the individual mixture? For constrained optimization with an aggregated objective, isn’t it enough to just know the aggregate prediction?

What is $\alpha$ in Line 4 of Algorithm 1? It does not appear in the objective function. How are you going to minimize $\mathcal{L}$ over it? Moreover, the footnote says $\alpha$ is a $k+1$ dimensional vector, while in Line 171 of the paper, the authors say $\alpha^{(k)}=\alpha$ is a $k$-dimensional vector (by Line 4 of Algorithm 1). This inconsistency makes it hard to understand the algorithm.

limitations: For the experiment results, I think it would be more reasonable to also compare the proposed method with those in recent related papers such as Chierichetti et al. [2018] and Jagabathula et al. [2020]. Though these baseline algorithms may work in a reduced setting or have different theoretical guarantees, their methods should still be applicable to the empirical studies in this paper. Therefore, it would be interesting to see how they compare with one another in the experiments. 

Lin 336: “reply” => “rely”
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors provide theoretical results on learning mixed multinomial logits. The main contribution is a new algorithm that learns both mixture weights and component-specific logit parameters with provable convergence guarantees for an arbitrary number
of mixtures.
strengths_and_weaknesses: [Strengths]
1. The paper is clearly written and the theoretical results look solid. 
2. Sample complexity is established for the proposed algorithm.

[Weaknesses]
1. The proposed algorithm performs EM-like updates. While sample complexity is provided, the algorithm could take many iterations to converge, and potentially converge to a local optima. How does the algorithm address these issues?
2. Both \alpha and \beta depend on the parameter \epsilon in Definition 1. Since the magnitude of z could be arbitrary, is the condition on \beta necessary?
3. I think the authors forgot to include the simulation studies as suggested in the abstract. 
questions: See the main comments.
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposed a new method for learning mixtures of multinomial logits based on historical choice data. The proposed method is based on Frank-Wolfe while restricting to a narrowed set of estimated choice probability vectors. The paper provided theoretical results on convergence and sample complexity. The paper provided numerical experiments to demonstrate the performance of the proposed method. 

strengths_and_weaknesses: 
Strengths. The proposed method seems effective for learning multinomial logit mixtures. The theoretical results are strong and solid. The paper is overall well-written. 

Weaknesses. The paper specifically considers historical choice data, which should be reflected in the title. It seems a narrow topic of learning multinomial logit mixtures using historical choice data, which may reduce the paper's significance. The Preliminaries subsection is a bit brief and it would be more helpful to formally define the historical choice data. 


- Line 35: typo of "Frank-Wolf (FW)"

- Line 330: typo of "Not only does it resolves ..."
questions: - Line 34 : "But it does not guarantee the estimators’ convergence." should better be "But it does not guarantee the estimators’ convergence to the true parameters", because EM algorithms do converge to something. 

- The authors could clarify why the problem considered in the paper is important and particularly relevant to the ML community. 

- The authors may provide more details on the underlying model for the historical choice data. Specifically, how were the parameters $z_j$'s (line 51) connected to the decision maker's choice probability q_k? Also, what's the usual relationship between N and T？ Do we consider a large N regime, large T regime, or large N large T regime?

- Theorem 1: what is the sample dependency on K (or L) and M? Also, is there a convergence guarantee for $\beta$'s in addition to q and \alpha?

- The method doesn't need to choose K but needs to choose an additional parameter L. How do you choose L in practice? 

- Algorithm 1 step 3 : $v$ was not defined. 

- Algorithm 1 : what's the stopping condition? 
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors provide theoretical analysis of a new "Stochastic Subregion Frank-Wolfe Algorithm" for learning mixed multinomial logits. The authors provide provable guarantees showing a polynomial number of samples is sufficient to achieve the performance guarantees. Simulations are provided in the supplementary material.
strengths_and_weaknesses: Overall, the topic and results are interesting. The smoothness of reading is affected by some typos that can be improved through further polishing.

**Originality.** The authors provide a novel algorithm that can be considered a variation of the Franke-Wolfe algorithm with a component that takes into account a "feasible region". This concept is quite interesting. Using this concept, the hyperparameter $K$ is not required in the algorithm which makes it appealing compared to algorithms that require knowledge of $K$.

**Quality.** The paper overall is interesting. The algorithms presented make sense. See below sections for a few questions (see below Questions section) and several notational confusions (see below clarity). 

**Clarity.** The clarity in the paper is mostly obstructed by typos and notational issues. Below are several points during my review:
* Clarity of notations and typos. For example:
    - defining "$\|\| \cdot \|\|$" before it appears in Theorem 1.
    - in the description of Theorem 1, the summation should be over $k'$ and not $k$. 
    - there are multiple typos throughout the submission but minimally affects the overall read. It would be beneficial to fix these typos in further revisions.

**Significance.** The MMNL model, Frank-Wolfe algorithm and related topics benefit a range of real world applications and therefore related research, including this paper, is important. 
questions: Below are several questions that may be worth a clarification:

* The results conveyed through Theorem 1 only depend on $\epsilon$ and $\delta$, and do not take into account other problem parameters such as $K$, $M$, etc. How do these parameters affect the sample complexity?
* Are there any information-theoretic impossibility results that can be used for comparison? For example, results that show a relation between feasible expected error compared to number of samples? Is the dependence on $\epsilon$ and $\delta$ already theoretically optimal, or is it possible that algorithms with better complexity exist?
* What is the computational complexity of the algorithms compared to previous algorithms such as MLE or previous algorithms that achieve sub-linear sample complexity for aggregate probabilities?
* In the supplementary material, several details are swept under the rug. For example, line 457 states that "enough sample"s are sufficient to give a performance guarantee by law of large numbers, but the whole discussion of that section relies on a precise characterization of the sample complexity --- can this be clarified? In other words, what is the precise sample complexity for the statement of line 457 to be true and does it affect the final sample complexity claims in the main text?
* Finally, in the simulations, although the authors claim that "EM achieves a marginally better performance" in certain scenarios in line 655, Figure 6-(b) does not suggest that and it appears the EM with suitably chosen $K$ has much better performance especially at larger epochs. While the authors clarify that EM "suffers from its instability", it does not appear to be a significant factor in this experiment. Can this be clarified?
limitations: Limitations are not thoroughly discussed in this submission. It would be beneficial to discuss limitations in more detail.
review_title: null

Meta-review: metareview: This paper proposes Frank-wolfe method for learning mixture of multinomial logit models. The algorithms is novel and the first of its kind to be applied to this problem. This is an important addition to the widely studied topic of preference learning, and this result extends the capability of what can be efficiently learned under realistic scenario with mixture models. Mixture models for ranking are notoriously hard problems and a novel approach such as the one introduced in this paper is critical in bridging the gap to making preference learning practical. All the reviewers' concerns have been addressed in the rebuttal adequately. 

Given the good quality of the paper, it will be quite beneficial for the readers if the paper spend some more time on explaining how the result compares to the extensive work that has been don on mixture of multinomial logit models. Such a nicely written related work section will only make the paper more interesting and broaden the impact of the results. Some important and closely related work that predate [Chierichetti et al. 2018] are missing. Some more recent related work are missing. Here is a sampling of such related work that should be compared with: 
- Learning Mixtures of Random Utility Models with Features from Incomplete Preferences Zhibing Zhao, Ao Liu, Lirong Xia, (IJCAI-22) 
- On the identifiability of mixtures of ranking models, Xiaomin Zhang, Xucheng Zhang, Po-Ling Loh, Yingyu Liang, https://arxiv.org/abs/2201.13132
- Learning Mixtures of Plackett-Luce Models from Structured Partial Orders, Zhibing Zhao, Lirong Xia, (NeurIPS 2019)
- Learning Plackett-Luce Mixtures from Partial Preferences, Ao Liu, Zhibing Zhao, Chao Liao, Pinyan Lu, Lirong Xia (AAAI-19)
- Learning Mixtures of Plackett-Luce Models, Zhibing Zhao, Peter Piech, Lirong Xia, (ICML-16)
- Collaboratively Learning Preferences from Ordinal Data, Sewoong Oh, Kiran K. Thekumparampil, Jiaming Xu, (NIPS 2015)
- A Topic Modeling Approach to Ranking, Weicong Ding, Prakash Ishwar, Venkatesh Saligrama, (AISTATS-15)
- Learning mixed multinomial logit model from ordinal data, S Oh, D Shah (NIPS-14)





confidence: Certain
Decision: Accept