Locally Private Online Quantile Regression: Estimation and Inference

Sintesi Tecnica: Regressione Quantilica Online con Privacy Locale

Problematica
Il documento affronta la sfida di eseguire una regressione quantilica (QR) online sotto un protocollo di $\varepsilon$-privacy differenziale locale a livello utente ($\varepsilon$-LDP) con un singolo report. Nella QR online standard, il server aggiorna lo stimatore utilizzando il contributo dell'equazione di stima $g_\beta(X, Y) = X \{ \mathbb{1}(Y \le X^\top \beta) - \tau \}$. Questo vettore accoppia la covariata $X$ con un confronto dell'indicatore (la funzione indicatrice). Sotto la LDP a livello utente, un server riceve solo un report privatizzato da ogni utente. La difficoltà principale è che la privatizzazione standard di questo vettore è impossibile senza violare il vincolo di privacy o distruggere la struttura della media condizionale necessaria per l'approssimazione stocastica. Nello specifico, se il server non può osservare direttamente $X$ e l'indicatore, non può formare il vettore di aggiornamento non distorto necessario per la convergenza. I metodi esistenti per i quantili privati scalari o per la QR distribuita centrale/privata non affrontano questo specifico problema del "contributo dell'equazione di stima decodificato", dove un singolo report LDP deve essere trasformato in un aggiornamento dipendente dalle covariate e non distorto.

Metodologia
Gli autori propongono un framework in cui il server non riceve il gradiente grezzo, ma un input decodificato che preserva la media condizionale dell'equazione di stima.

1. Geometria Consapevole del Supporto (Support-Aware Geometry): Il contributo esatto dell'equazione di stima della QR $g_\beta(O)$ risiede su una specifica geometria di supporto a due facce $G_\tau$. La coordinata dell'intercetta identifica la faccia attiva ($\mathbb{1}(Y \le X^\top \beta) = 0$ o $1$), mentre le coordinate della pendenza sono vincolate a intervalli simmetrici determinati dalla faccia e dalle covariate limitate.
2. Il Canale CQX($q, s$): Gli autori costruiscono un canale a alfabeto finito chiamato CQX($q, s$), dove $q$ è la dimensione della griglia per la quantizzazione della pendenza e $s$ è la dimensione di un blocco di coordinate selezionato.
   • Elaborazione Locale: Ogni utente calcola localmente $g_\beta(X, Y)$. Essi quantizzano stocasticamente le coordinate di pendenza selezionate (usando una griglia pubblica) in una categoria finita. Se l'intercetta è selezionata, essa funge da etichetta della faccia; altrimenti, le pendenze sono quantizzate su una griglia incondizionata.
   • Risposta Randomizzata (Randomized Response): L'utente applica la risposta randomizzata alla categoria risultante (la "categoria del blocco selezionato") per generare un singolo report LDP.
   • Decodifica lato Server: Il server applica un decoder di risposta randomizzata affine per correggere la distorsione e utilizza la ricostruzione di Horvitz-Thompson per recuperare il vettore completo.
   • Proprietà Chiave: L'input decodificato $\tilde{g}_\beta$ soddisfa la non distorsione condizionale: $E[\tilde{g}_\beta(X, Y) \mid X, Y, \beta] = g_\beta(X, Y)$. Ciò consente al server di utilizzare l'input decodificato in uno schema di mediazione Polyak-Ruppert proiettata ($\beta_i = \Pi_B \{ \beta_{i-1} - \eta_i \tilde{g}_i(\beta_{i-1}) \}$) senza distorcere il parametro target.
3. Inferenza: Il documento sviluppa procedure di inferenza prive di Hessiana che non richiedono la stima dell'Hessiana della QR (che è difficile sotto LDP). Queste includono:
   • Auto-normalizzazione (SN): Utilizza la variazione temporale delle medie di Polyak in una singola traiettoria.
   • Divide-and-Conquer (DC): Partiziona lo stream in gruppi disgiunti per calcolare le medie di gruppo e formare set di confidenza di tipo Hotelling.
   • HiGrad: Utilizza una struttura ad albero pubblica per generare centri di gruppo correlati con template di covarianza noti per la studentizzazione.

Contributi Chiave

1. Formulazione: Il documento formula la QR lineare in streaming sotto la LDP sequenziale a un singolo report per utente come un problema di equazione di stima decodificata, separando la garanzia di privacy del report dal requisito di preservazione della media dell'approssimazione stocastica.
2. Costruzione del Meccanismo: Introduce il canale CQX($q, s$), che combina la selezione delle coordinate pubbliche, la quantizzazione stocastica consapevole del supporto, la risposta randomizzata e la decodifica affine. Questo meccanismo sfrutta la geometria di supporto a due facce del contributo della QR per garantire che l'input del server decodificato sia condizionalmente non distorto.
3. Garanzie Teoriche: Per design di canali finiti fissi, gli autori dimostrano:
   • Privacy locale ($\varepsilon$-LDP) per il contributo a un singolo record.
   • Non distorsione del decoder condizionale.
   • Consistenza e normalità asintotica dello stimatore con mediazione Polyak-Ruppert proiettata.
   • Validità dell'inferenza auto-normalizzata senza Hessiana per contrasti scalari prescritti ed ellissoidi vettoriali.
4. Validazione Empirica: Attraverso simulazioni e un'illustrazione con dati sui viaggi in taxi di New York City, il documento dimostra che la traiettoria privata si avvicina alla referenza online non privata all'aumentare del budget di privacy ($\varepsilon$). Il canale proposto supera il rilascio diretto di Laplace (che ignora il supporto) e il rilascio esponenziale-di-faccia (che sposta la media) in termini di errore di stima e quantificazione dell'incertezza.

Risultati

• Accuratezza della Stima: Nelle simulazioni, il meccanismo CQX($q, s$) raggiunge un errore euclideo medio inferiore rispetto ai baseline geometrici (Laplace Diretto e Esponenziale-di-Faccia). Il meccanismo Esponenziale-di-Faccia spesso fallisce ad alti quantili ($\tau=0.75$) a causa del mismatch del campo medio che causa la saturazione del confine di proiezione.
• Recupero ad Alto Budget: Man mano che $\varepsilon \to \infty$ e la risoluzione della griglia $q$ aumenta, la covarianza dello stimatore privato converge a quella dell'oracolo ASGD non privato.
• Calibrazione dell'Inferenza: Le procedure di auto-normalizzazione (SN), divide-and-conquer (DC) e HiGrad forniscono intervalli di confidenza con tassi di copertura vicini al livello nominale del 95%, particolarmente per contrasti scalari e contrasti densi. Gli ellissoidi a vettore completo sono più sensibili all'informazione effettiva finita e al condizionamento, ma rimangono validi sotto le condizioni di rango dichiarate.
• Applicazione su Dati Reali: Sul dataset dei taxi di NYC, le stime private preservano la calibrazione holdout (tassi di hit) e la perdita di controllo predittivo rispetto alla referenza non privata, con prestazioni che migliorano all'aumentare di $\varepsilon$.

Significatività e Rivendicazioni
Il documento afferma di presentare il primo framework LDP a un singolo report per la stima e l'inferenza della QR online basato su input di equazioni di stima decodificati che preservano la media. Sostiene che gli approcci SGD con rumore additivo standard siano inadatti per la QR perché ignorano la specifica geometria di supporto dell'equazione di stima. Decoupling (scollegando) il meccanismo di privacy dall'aggiornamento della stima tramite un passaggio di decodifica, gli autori mostrano che la privacy locale a un singolo report è compatibile con la QR online. La significatività risiede nel rendere possibile l'inferenza statistica valida (consistenza, normalità, intervalli di confidenza) in un ambiente in streaming e con vincoli di privacy, senza richiedere un curatore fidato o molteplici report per utente. Gli autori notano che la teoria è deliberatamente a dimensione fissa e si basa su covariate limitate; estensioni ad ambienti ad alta dimensione o design di canali adattivi sono lasciate al lavoro futuro.