Нижняя граница ван Триса для полностью интерактивного дифференциально-приватного федеративного обучения

Исследователи вывели нижнюю границу ван Триса для оценки параметров в полностью интерактивных протоколах федеративного обучения с дифференциальной приватностью (DP). Эта работа обобщает существующие результаты, которые ранее были ограничены неинтерактивными протоколами или разложением на свежие батчи, и теперь охватывает произвольные публичные транскрипты с по-клиентским ограничением zCDP (zero-concentrated DP) на уровне сэмплов. Результат показывает, что для широкого класса задач интерактивность не даёт выигрыша в скорости сходимости по сравнению с более простыми протоколами.

Федеративное обучение с DP позволяет обучать модели на распределённых данных, сохраняя приватность. Однако до сих пор не было ясно, насколько интерактивность — множество раундов связи — и повторное использование локальных выборок могут улучшить точность оценки. Эта работа показывает фундаментальные ограничения, которые помогают разработчикам понять, когда стоит инвестировать в сложные интерактивные протоколы, а когда достаточно простых неинтерактивных подходов.

Основные результаты

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

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

Какие задачи охватывает новая нижняя граница?

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

Почему это важно для практики

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

Кроме того, работа помогает определить, какие задачи могут выиграть от интерактивности, если выйти за рамки рассмотренных предположений. Например, если транскрипты не являются публичными или используется другое определение DP, результаты могут отличаться.

Ограничения и открытые вопросы

Работа рассматривает только публичные транскрипты и zCDP; результаты для других определений DP, таких как (ε, δ)-DP, или для частных транскриптов не исследованы. Также остаётся открытым вопрос, могут ли интерактивные протоколы с дополнительными ограничениями, например на сложность связи или вычислительные ресурсы, превзойти полученные границы. Будущие исследования могут расширить эти результаты на более широкий класс задач и механизмов приватности.

Заключение

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