Locally Private Online Quantile Regression: Estimation and Inference

Résumé Technique : Régression Quantile en Ligne avec Confidentialité Locale

Énoncé du Problème
L'article traite du défi consistant à effectuer une régression quantile (QR) en ligne sous un protocole de confidentialité différentielle locale (LDP) de type $\varepsilon$-LDP au niveau de l'utilisateur avec un rapport unique. Dans une QR en ligne standard, le serveur met à jour l'estimateur en utilisant la contribution de l'équation d'estimation $g_\beta(X, Y) = X \{ \mathbb{1}(Y \le X^\top \beta) - \tau \}$. Ce vecteur couple la covariable $X$ avec une comparaison de résidu (la fonction indicatrice). Sous une LDP au niveau de l'utilisateur, le serveur ne reçoit qu'un rapport privatisé de chaque utilisateur. La difficulté centrale est qu'une privatisation standard de ce vecteur est impossible sans violer la contrainte de confidentialité ou détruire la structure de moyenne conditionnelle requise pour l'approximation stochastique. Plus précisément, si le serveur ne peut observer ni $X$ ni l'indicateur directement, il ne peut pas former le vecteur de mise à jour non biaisé nécessaire à la convergence. Les méthodes existantes pour les quantiles scalaires privés ou la QR distribuée centralisée/privée ne traitent pas ce problème spécifique de « l'équation d'estimation décodée », où un rapport LDP unique doit être transformé en une mise à jour dépendante des covariables et non biaisée.

Méthodologie
Les auteurs proposent un cadre dans lequel le serveur ne reçoit pas le gradient brut, mais plutôt une entrée décodée qui préserve la moyenne conditionnelle de l'équation d'estimation.

1. Géométrie Sensible au Support : La contribution exacte de l'équation d'estimation de la QR $g_\beta(O)$ repose sur une géométrie de support à deux faces $G_\tau$. La coordonnée d'ordonnée à l'origine identifie la face active ($\mathbb{1}(Y \le X^\top \beta) = 0$ ou $1$), et les coordonnées de pente sont contraintes par des intervalles symétriques déterminés par la face et les covariables bornées.
2. Le Canal CQX($q, s$) : Les auteurs construisent un canal à alphabet fini nommé CQX($q, s$), où $q$ est la taille de la grille pour la quantification des pentes et $s$ est la taille d'un bloc de coordonnées sélectionné.
   • Traitement Local : Chaque utilisateur calcule localement $g_\beta(X, Y)$. Ils quantifient de manière stochastique les coordonnées de pente sélectionnées (en utilisant une grille publique) vers une catégorie finie. Si l'ordonnée à l'origine est sélectionnée, elle agit comme une étiquette de face ; sinon, les pentes sont quantifiées sur une grille inconditionnelle.
   • Réponse Randomisée : L'utilisateur applique une réponse randomisée à la catégorie finie résultante (la « catégorie du bloc sélectionné ») pour générer un rapport LDP unique.
   • Décodage Côté Serveur : Le serveur applique un décodeur de réponse randomisée affine pour corriger la distorsion et utilise la reconstruction de Horvitz-Thompson pour récupérer le vecteur complet.
   • Propriété Clé : L'entrée décodée $\tilde{g}_\beta$ satisfait l'absence de biais conditionnel : $E[\tilde{g}_\beta(X, Y) \mid X, Y, \beta] = g_\beta(X, Y)$. Cela permet au serveur d'utiliser l'entrée décodée dans un schéma de moyennage de Polyak-Ruppert projeté ($\beta_i = \Pi_B \{ \beta_{i-1} - \eta_i \tilde{g}_i(\beta_{i-1}) \}$) sans biaiser le paramètre cible.
3. Inférence : L'article développe des procédures d'inférence sans calcul de Hessienne qui ne nécessitent pas d'estimer la Hessienne de la QR (ce qui est difficile sous LDP). Celles-ci incluent :
   • Auto-Normalisation (SN) : Utilise la variation temporelle des moyennes de Polyak dans une trajectoire unique.
   • Diviser pour Régner (DC) : Partitionne le flux en groupes disjoints pour calculer les moyennes de groupe et former des ensembles de confiance de type Hotelling.
   • HiGrad : Utilise une structure d'arbre publique pour générer des centres de groupes corrélés avec des modèles de covariance connus pour la studentisation.

Contributions Clés

1. Formulation : L'article formule la QR linéaire en streaming sous une LDP séquentielle d'un rapport par utilisateur comme un problème d'équation d'estimation décodée, séparant la garantie de confidentialité du rapport de l'exigence de préservation de la moyenne de l'approximation stochastique.
2. Construction du Mécanisme : Il introduit le canal CQX($q, s$), qui combine la sélection de coordonnées publiques, la quantification stochastique sensible au support, la réponse randomisée et le décodage affine. Ce mécanisme exploite la géométrie de support à deux faces de la contribution de la QR pour garantir que l'entrée décodée du serveur est conditionnellement non biaisée.
3. Garanties Théoriques : Pour des conceptions de canaux finis fixes, les auteurs prouvent :
   • La confidentialité locale ($\varepsilon$-LDP) pour la contribution d'un enregistrement.
     er l'absence de biais du décodeur conditionnel.
   • La cohérence et la normalité asymptotique de l'estimateur moyenné de Polyak-Ruppert projeté.
   • La validité de l'inférence auto-normalisée sans Hessienne pour des contrastes scalaires prescrits et des ellipsoïdes vectoriels.
4. Validation Empirique : À travers des simulations et une illustration basée sur les données de trajets de taxis de New York, l'article démontre que la trajectoire privée approche la référence non privée en ligne à mesure que le budget de confidentialité ($\varepsilon$) augmente. Le canal proposé surpasse la libération directe de Laplace (qui ignore le support) et la libération exponentielle de face (qui déplace la moyenne) en termes d'erreur d'estimation et de quantification de l'incertitude.

Résultats

• Précision de l'Estimation : Dans les simulations, le mécanisme CQX($q, s$) atteint une erreur euclidienne moyenne plus faible par rapport aux bases géométriques (Laplace Direct et Exponentielle de Face). Le mécanisme Exponentiel de Face échoue souvent aux quantiles élevés ($\tau=0.75$) en raison d'un décalage du champ moyen causant une saturation de la projection de la frontière.
• Récupération à Haut Budget : Lorsque $\varepsilon \to \infty$ et que la résolution de la grille $q$ augmente, la covariance de l'estimateur privé converge vers celle de l'oracle ASGD non privé.
• Calibration de l'Inférence : Les procédures d'auto-normalisation (SN), de division pour régner (DC) et HiGrad fournissent des intervalles de confiance avec des taux de couverture proches du niveau nominal de 95 %, particulièrement pour les contrastes scalaires et les contrastes denses. Les ellipsoïdes de vecteurs complets sont plus sensibles à l'information effective finie et au conditionnement, mais restent valides sous les conditions de rang énoncées.
• Application sur Données Réelles : Sur le jeu de données des taxis de NYC, les estimations privées préservent la calibration de maintien (taux de réussite) et la perte de contrôle prédictif de la référence non privée, avec des performances s'améliorant à mesure que $\varepsilon$ augmente.

Signification et Revendications
L'article affirme présenter le premier cadre LDP d'un rapport pour l'estimation et l'inférence de la QR en ligne basé sur des entrées d'équation d'estimation décodées préservant la moyenne. Il soutient que les approches SGD classiques à bruit additif sont mal adaptées à la QR car elles ignorent la géométrie de support spécifique de l'équation d'estimation. En découplant le mécanisme de confidentialité de la mise à jour de l'estimation via une étape de décodage, les auteurs montrent que la confidentialité locale d'un rapport est compatible avec la QR en ligne. La signification réside dans la capacité de réaliser une inférence statistique valide (cohérence, normalité, intervalles de confiance) dans un environnement de flux sous contrainte de confidentialité sans nécessiter de curateur de confiance ou de multiples rapports par utilisateur. Les auteurs notent que la théorie est délibérément fixée en dimension et repose sur des covariables bornées ; les extensions vers des contextes de haute dimension ou des conceptions de canaux adaptatives sont laissées aux travaux futurs.