Aprendizado Diferencialmente Privado Eficiente em Oracle com Dados Públicos

Devido a limites inferiores estatísticos sobre a aprendibilidade de muitas classes de funções sob restrições de privacidade, houve um interesse recente em aproveitar dados públicos para melhorar o desempenho de algoritmos de aprendizado privado. Neste modelo, os algoritmos devem sempre garantir privacidade diferencial em relação às amostras privadas, garantindo também garantias de aprendizado quando a distribuição dos dados privados está suficientemente próxima da dos dados públicos. Trabalhos anteriores demonstraram que quando há dados públicos, não rotulados, suficientes disponíveis, o aprendizado privado pode ser tornado estatisticamente tratável, mas os algoritmos resultantes têm sido todos computacionalmente ineficientes. Neste trabalho, apresentamos os primeiros algoritmos computacionalmente eficientes, que provavelmente aproveitam dados públicos para aprender de forma privada sempre que uma classe de funções é aprendível não privadamente, onde nossa noção de eficiência computacional é em relação ao número de chamadas a um oráculo de otimização para a classe de funções. Além deste resultado geral, fornecemos algoritmos especializados com complexidades de amostra aprimoradas nos casos especiais em que a classe de funções é convexa ou quando a tarefa é classificação binária.