Taxas Opcionais para DP-SCO com um Único Epoch e Lotes Grandes

Os algoritmos mais comuns para aprendizado de máquina (ML) diferencialmente privado (DP) são todos baseados em descida de gradiente estocástica, por exemplo, DP-SGD. Esses algoritmos alcançam DP tratando cada gradiente como uma consulta privada independente. No entanto, essa independência pode nos fazer pagar demais em perda de privacidade porque não analisamos toda a trajetória do gradiente. Neste trabalho, propomos um novo algoritmo DP, que chamamos de Acelerado-DP-SRGD (descida de gradiente recursiva estocástica DP), que nos permite quebrar essa independência e pagar apenas pela privacidade na diferença do gradiente, ou seja, na nova informação no passo atual. Nosso algoritmo alcança o erro ótimo de otimização convexa estocástica DP (DP-SCO) (até fatores polilogarítmicos) usando apenas um único epoch sobre o conjunto de dados e converge à taxa acelerada de Nesterov. Nosso algoritmo pode ser executado em no máximo n passos de gradiente em lote com tamanho de lote de pelo menos n, ao contrário de trabalhos anteriores que exigiam O(n) consultas com tamanhos de lote em sua maioria constantes. Para alcançar isso, nosso algoritmo combina três ingredientes chave: uma variante de gradientes recursivos estocásticos (SRG), descida de gradiente acelerada e geração de ruído correlacionado da contagem contínua DP. Finalmente, também mostramos que nosso algoritmo melhora os resultados existentes SoTA em regressão logística multiclasse no MNIST e CIFAR-10.