Otimização Convexa Estocástica Privada com Caudas Pesadas: Proximidade Ótima a partir de Reduções Simples

Estudamos o problema da otimização convexa estocástica diferentemente privada (DP-SCO) com gradientes de cauda pesada, onde assumimos um limite de k-ésimo momento nas constantes de Lipschitz das funções amostrais em vez de um limite uniforme. Propomos uma nova abordagem baseada em reduções que nos permite obter as primeiras taxas ótimas (até fatores logarítmicos) no cenário de caudas pesadas, alcançando erro G₂ 1 n + Gₖ (dn) ^1 - 1 k sob privacidade diferencial (, ) -aproximada, até um fator polilogar (1) leve, onde G₂² e Gₖᵏ são os limites de 2º e k-ésimo momento nas constantes de Lipschitz das amostras, quase correspondendo a um limite inferior de Lowy e Razaviyayn 2023. Além disso, apresentamos um conjunto de algoritmos privados no cenário de caudas pesadas que melhoram nosso resultado básico sob suposições adicionais, incluindo um algoritmo ótimo sob a suposição de constante de Lipschitz conhecida, um algoritmo de tempo próximo-linear para funções suaves, e um algoritmo ótimo de tempo linear para modelos lineares generalizados suaves.