Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Дифференциально приватное обучение линейных классификаторов удалось сделать без роста порядка выборки по сравнению с неприватными алгоритмами. В препринте University of Copenhagen, который не прошёл рецензирование, все числа получены авторами: если параметр приватности ε не меньше допустимой добавочной ошибки α, приватные слагаемые не превышают обычную статистическую цену. Это снимает выбор между приватностью и количеством обучающих примеров, но только при заданных распределениях входов.
Полупространство делит данные линейной границей и относит точки к одному из двух классов. В агностическом режиме разметка может содержать произвольный шум, поэтому алгоритм должен приблизиться к ошибке лучшего полупространства, а не найти идеальное разделение. Дифференциальная приватность требует, чтобы замена одной записи лишь немного меняла распределение возможных результатов обучения.
Для классификатора произвольной формы авторы аппроксимируют границу полиномом, ограничивают влияние крупных признаков и приватно решают задачу выпуклой оптимизации. Чтобы вернуть именно полупространство, они находят подпространство малой размерности, строят конечный набор линейных границ и приватно выбирают лучшую. Третий алгоритм допускает ошибку в постоянное число раз выше оптимальной, зато сохраняет полиномиальную зависимость и от размерности, и от точности.
В гауссовском случае первому алгоритму требуется примерно DG/α² + DG/(εα) примеров, где DG растёт как d в степени порядка 1/α². При ε ≥ α второе слагаемое не больше первого. Для полиномиального полуагностического алгоритма получается d/α² + d/(εα) с тем же условием. Для логарифмически вогнутого распределения входов результат распространяется только на классификатор произвольной формы, а приватная цена поглощается при ε не меньше √α.
Доказательства охватывают три режима при стандартном гауссовском распределении входов: классификатор произвольной формы, полупространство и полуагностическое полупространство. Распределение предполагается известным; при фиксированной точности время работы полиномиально по числу примеров, однако точный алгоритм с выходом-полупространством дополнительно экспоненциально зависит от точности. Поэтому результат меняет расчёт выборки для задач с подходящей моделью данных, но не даёт общего приватного метода для произвольных признаков.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
