Locally Private Online Quantile Regression: Estimation and Inference

Resumo Técnico: Regressão Quantílica Online com Privacidade Local

Definição do Problema
O artigo aborda o desafio de realizar regressão quantílica (RQ) online sob um protocolo de um único relatório por usuário, com privacidade diferencial local de nível de usuário $\varepsilon$-LDP. Na RQ online padrão, o servidor atualiza o estimador usando a contribuição da equação de estimação $g_\beta(X, Y) = X \{ \mathbb{1}(Y \le X^\top \beta) - \tau \}$. Este vetor acopla a covariável $X$ com uma comparação de resíduo (a função indicadora). Sob LDP de nível de usuário, o servidor recebe apenas um relatório privatizado de cada usuário. A dificuldade central é que uma privatização padrão deste vetor é impossível sem violar a restrição de privacidade ou destruir a estrutura de média condicional necessária para a aproximação estocástica. Especificamente, se o servidor não pode observar $X$ e o indicador diretamente, ele não consegue formar o vetor de atualização não viesado necessário para a convergência. Métodos existentes para quantis privados escalares ou RQ distribuída central/privada não abordam este problema específico de "equação de estimação decodificada", onde um único relatório LDP deve ser transformado em uma atualização não viesada e dependente de covariáveis.

Metodologia
Os autores propõem um framework onde o servidor não recebe o gradiente bruto, mas sim um dado decodificado que preserva a média condicional da equação de estimação.

1. Geometria Consciente do Suporte: A contribuição exata da equação de estimação da RQ $g_\beta(O)$ reside em uma geometria de suporte de duas faces específica $G_\tau$. A coordenada do intercepto identifica a face ativa ($\mathbb{1}(Y \le X^\top \beta) = 0$ ou $1$), e as coordenadas de inclinação (slopes) são restritas a intervalos simétricos determinados pela face e pelas covariáveis limitadas.
2. O Canal CQX(q, s): Os autores constroem um canal de alfabeto finito chamado CQX($q, s$), onde $q$ é o tamanho da grade para quantização de inclinação e $s$ é o tamanho de um bloco de coordenadas selecionado.
   • Processamento Local: Cada usuário computa $g_\beta(X, Y)$ localmente. Eles quantizam estocasticamente as coordenadas de inclinação selecionadas (usando uma grade pública) para uma categoria finita. Se o intercepto for selecionado, ele atua como um rótulo de face; caso contrário, as inclinações são quantizadas em uma grade incondicional.
   • Resposta Aleatória: O usuário aplica resposta aleatória à categoria resultante (a "categoria do bloco selecionado") para gerar um único relatório LDP.
   • Decodificação pelo Servidor: O servidor aplica um decodificador de resposta aleatória afim para corrigir a distorção e usa reconstrução de Horvitz-Thompson para recuperar o vetor completo.
   • Propriedade Chave: O dado decodificado $\tilde{g}_\beta$ satisfaz a não viesagem condicional: $E[\tilde{g}_\beta(X, Y) \mid X, Y, \beta] = g_\beta(X, Y)$. Isso permite que o servidor utilize o dado decodificado em um esquema de média de Polyak-Ruppert projetado ($\beta_i = \Pi_B \{ \beta_{i-1} - \eta_i \tilde{g}_i(\beta_{i-1}) \}$) sem enviesar o parâmetro alvo.
3. Inferência: O artigo desenvolve procedimentos de inferência livres de Hessiana que não exigem a estimativa da Hessiana da RQ (que é difícil sob LDP). Estes incluem:
   • Autonormalização (SN): Utiliza a variação temporal das médias de Polyak em uma única trajetória.
   • Dividir e Conquistar (DC): Particiona o fluxo em grupos disjuntos para computar médias de grupo e formar conjuntos de confiança do tipo Hotelling.
   • HiGrad: Utiliza uma estrutura de árvore pública para gerar centros de grupo correlacionados com templates de covariância conhecidos para studentização.

Principais Contribuições

1. Formulação: O artigo formula a RQ linear em streaming sob LDP de nível de usuário de um único relatório como um problema de equação de estimação decodificada, separando a garantia de privacidade do relatório do requisito de preservação de média da aproximação estocástica.
2. Construção do Mecanismo: Introduz o canal CQX($q, s$), que combina seleção de coordenada pública, quantização estocástica consciente do suporte, resposta aleatória e decodificação afim. Este mecanismo explora a geometria de suporte de duas faces da contribuição da RQ para garantir que o dado decodificado do servidor seja condicionalmente não viesado.
3. Garantias Teóricas: Para designs de canal finitos fixos, os autores provam:
   • Privacidade local ($\varepsilon$-LDP) para a contribuição de um único registro.
   • Não viesagem do decodificador condicional.
   • Consistência e normalidade assintótica do estimador de média de Polyak-Ruppert projetado.
   • Validade da inferência autonormalizada livre de Hessiana para contrastes escalares pré-especificados e elipsoides vetoriais.
4. Validação Empírica: Através de simulações e uma ilustração com dados de viagens de táxi de Nova York, o artigo demonstra que a trajetória privada se aproxima da referência não privada conforme o orçamento de privacidade ($\varepsilon$) aumenta. O canal proposto supera o lançamento de Laplace direto (que ignora o suporte) e o lançamento de exponencial de face (que desloca a média) em termos de erro de estimação e quantificação de incerteza.

Resultados

• Precisão de Estimação: Em simulações, o mecanismo CQX($q, s$) alcança um erro de estimação euclidiano médio menor comparado às bases geométricas (Laplace Direto e Exponencial de Face). O mecanismo Exponencial de Face frequentemente falha em quantis altos ($\tau=0.75$) devido ao descompasso de campo médio causando saturação de fronteira de projeção.
• Recuperação de Alto Orçamento: À medida que $\varepsilon \to \infty$ e a resolução da grade $q$ aumenta, a covariância do estimador privado converge para a do oráculo ASGD não privado.
• Calibração de Inferência: Os procedimentos de autonormalização (SN), dividir e conquistar (DC) e HiGrad fornecem intervalos de confiança com taxas de cobertura próximas ao nível nominal de 95%, particularmente para contrastes escalares e contrastes densos. Elipsoides de vetor completo são mais sensíveis à informação efetiva finita e condicionamento, mas permanecem válidos sob as condições de posto estabelecidas.
• Aplicação em Dados Reais: No conjunto de dados de táxi de NYC, as estimativas privadas preservam a calibração de holdout (taxas de acerto) e a perda de verificação preditiva do referente não privado, com desempenho melhorando conforme $\varepsilon$ aumenta.

Significância e Alegações
O artigo afirma apresentar o primeiro framework de LDP de um único relatório para estimativa e inferência de RQ online baseada em entradas de equação de estimação decodificadas que preservam a média. Argumenta-se que abordagens de SGD com ruído aditivo padrão são mal adequadas para RQ porque ignoram a geometria de suporte específica da equação de estimação. Ao desacoplar o mecanismo de privacidade da atualização de estimação via um passo de decodificação, os autores mostram que a privacidade local de um único relatório é compatível com a RQ online. A significância reside em permitir inferência estatística válida (consistência, normalidade, intervalos de confiança) em um ambiente de streaming com restrição de privacidade, sem exigir um curador confiável ou múltiplos relatórios por usuário. Os autores observam que a teoria é deliberadamente de dimensão fixa e depende de covariáveis limitadas; extensões para configurações de alta dimensão ou designs de canal adaptativos são deixadas para trabalhos futuros.