Classement de manière optimale avec une protection différentielle de la vie privée à partir de comparaisons par paires

La confidentialité des données est une préoccupation centrale dans de nombreuses applications impliquant le classement à partir de comparaisons par paires incomplètes et bruyantes, telles que les systèmes de recommandation, les évaluations éducatives et les enquêtes d'opinion sur des sujets sensibles. Dans ce travail, nous proposons des algorithmes à protection différentielle de la vie privée pour le classement basé sur des comparaisons par paires. Plus précisément, nous développons et analysons des méthodes de classement sous deux notions de confidentialité : la confidentialité différentielle au niveau des bords, qui protège la confidentialité des résultats de comparaison individuels, et la confidentialité différentielle individuelle, qui sauvegarde potentiellement de nombreuses comparaisons contribuant par un seul individu. Nos algorithmes — y compris un estimateur du maximum de vraisemblance perturbé et une méthode basée sur le comptage bruyant — sont montrés pour atteindre des taux de convergence minimax optimaux sous les contraintes de confidentialité respectives. Nous démontrons en outre l'efficacité pratique de nos méthodes à travers des expériences sur des données simulées et du monde réel.