Le prix de la confidentialité dans les systèmes de recommandation non fiables

L'augmentation récente des préoccupations concernant la confidentialité en ligne soulève la question suivante : un système de recommandation peut-il être précis si les utilisateurs ne lui confient pas leurs données privées ? Pour répondre à cette question, nous étudions le problème de l'apprentissage de groupes d'éléments dans le cadre de la confidentialité différentielle locale, une notion puissante et formelle de la confidentialité des données. Nous développons des limites sur la complexité d'échantillonnage de l'apprentissage de groupes d'éléments à partir d'entrées utilisateur privatisées. De manière significative, nos résultats identifient une séparation de complexité d'échantillon entre l'apprentissage dans un régime riche en informations et un régime pauvre en informations, soulignant ainsi l'interaction entre la confidentialité et la quantité d'informations (évaluations) disponibles pour chaque utilisateur. Dans le régime riche en informations, où chaque utilisateur évalue au moins une fraction constante d'éléments, une approche de regroupement spectral permet d'atteindre une limite inférieure de complexité d'échantillon dérivée d'un argument simple de la théorie de l'information basé sur l'inégalité de Fano. Cependant, le régime de rareté de l'information, où chaque utilisateur n'évalue qu'une fraction négligeable d'éléments, nécessite une approche fondamentalement différente, tant pour les limites inférieures que pour les algorithmes. À cette fin, nous développons de nouvelles techniques pour limiter l'information mutuelle en fonction d'une notion d'inadéquation des canaux. Ces techniques peuvent présenter un intérêt plus large, et nous l'illustrons en les appliquant (i) à l'apprentissage basé sur des croquis à 1 bit, et (ii) à l'apprentissage adaptatif. Enfin, nous proposons un nouvel algorithme, MaxSense, et montrons qu'il atteint une complexité d'échantillonnage optimale dans le régime de rareté de l'information.