Вычислительные ограничения в робастной классификации и беспроигрышные результаты04.02.2019 08:00

Аннотация

Мы продолжаем изучение статистических и вычислительных компромиссов при обучении робастных классификаторов, опираясь на недавнюю работу Бубека (Bubeck), Ли (Lee), Прайса (Price) и Разенштейна (Razenshteyn), которые продемонстрировали примеры задач классификации, где: (a) существует эффективный робастный классификатор в режиме малых возмущений; (b) неробастный классификатор может быть обучен эффективно;, но © обучение робастного классификатора вычислительно сложно, если предположить сложность факторизации больших чисел. Вопрос о том, существует ли робастный классификатор для их задачи в режиме больших возмущений, по-видимому, связан с важными открытыми проблемами в вычислительной теории чисел. В данной работе мы расширяем их исследование в трех направлениях.

Во-первых, мы демонстрируем задачи классификации, в которых вычислительно эффективная робастная классификация невозможна, даже когда существуют вычислительно неограниченные робастные классификаторы. Для этого мы опираемся на существование трудноразрешимых в среднем функций.

Во-вторых, мы показываем задачи классификации, для которых сложно обеспечить робастное обучение в режиме больших возмущений. А именно, мы показываем, что хотя эффективный классификатор, устойчивый к большим возмущениям, существует, вычислительно сложно обучить какой-либо нетривиальный робастный классификатор. Наше первое построение опирается на существование односторонних функций, а второе — на сложность задачи обучения паритету с шумом (learning parity with noise). В последнем случае не только существует неробастный классификатор, но также имеется эффективный алгоритм, который генерирует новые помеченные выборки при наличии доступа к полиномиальному числу примеров для обучения (называемый генерацией по Кернсу и др. (Kearns et al., 1994)).

В-третьих, мы показываем, что любой такой контрпример подразумевает существование криптографических примитивов, таких как односторонние функции. Это приводит нас к беспроигрышному сценарию: либо мы можем обучить эффективный робастный классификатор, либо мы можем построить новые экземпляры криптографических примитивов.