Active Ranking and Matchmaking, with Perfect Matchings
Authors: Hafedh El Ferchichi, Matthieu Lerasle, Vianney Perchet
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our algorithm achieves both objectives with high probability, and the total cost is optimal (up to logarithmic terms).Section 2 is dedicated to the first objective: recovering the exact ranking. The necessity of this step is illustrated in Section 2.1, highlighting its role in obtaining an optimal matching. Subsequently, we delve into the description of the ranking algorithm in Section 2.2, where we first outline the relevant properties of AKS-Paterson (Ajtai et al., 1983; Paterson, 1990) for this problem. We then explain how to employ AKS-Paterson (or any other sorting network with O(log N) time complexity) to obtain an (ε, δ)-PAC ranking, and then how to reach an exact ranking by refining ε further and further.More general comments, proofs and most pseudocodes are postponed to the Appendix, due to space limit. |
| Researcher Affiliation | Collaboration | 1CREST, ENSAE, IP Paris 2FAIRPLAY joint team 3Criteo AI Lab.Correspondence to: Hafedh El Ferchichi <hafedh.elferchichi@ensae.fr>. |
| Pseudocode | Yes | More general comments, proofs and most pseudocodes are postponed to the Appendix, due to space limit.F. Omitted Pseudo-codes |
| Open Source Code | No | No explicit statement or link providing access to open-source code for the described methodology was found. |
| Open Datasets | No | The paper is theoretical and does not describe experiments utilizing a dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments utilizing dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, including hyperparameters or training settings. |