Скалярная модель

Есть устройств. На устройстве хранится число , и серверу нужно . Это упрощённая модель одной нормированной координаты локальной поправки в распределённом обучении. Для реальных градиентов нужны знаки, масштабы, многие координаты и схема оптимизации; один бит не кодирует весь произвольный вектор.

Устройство независимо выбирает и отправляет один бит. Сервер считает . Все ожидания и дисперсии далее условны на фиксированных локальных числах . Независимыми должны быть ошибки квантования; сами данные устройств не обязаны быть независимы для этого условного расчёта.

Несмещённость

, поэтому по линейности . В отличие от обычного округления к 0 или 1, каждый исходный сигнал сохраняется в ожидании. Если все , обычное округление всегда даёт ноль; увеличение числа устройств такого смещения не лечит.

Точность

Так как , . Независимость даёт , значит . Для верхняя граница стандартного отклонения — 0,005. Это не гарантия двух десятичных знаков.

Для вероятностной гарантии используем Хёффдинга: . При , граница равна . Таким образом, гарантия имеет одновременно допуск и вероятность неудачи.

Когда среднее перестаёт спасать

В режиме «общая случайность» устройства сравнивают все свои числа с одним и тем же , то есть . Каждый бит всё ещё несмещён, но ошибки зависимы. Если все , сервер получает либо все нули, либо все единицы; разброс остаётся , независимо от . Это ярко отделяет линейность ожидания от сложения дисперсий.

ЦПТ для неодинаковых устройств

Биты с разными не одинаково распределены. Классическую i.i.d.-формулировку ЦПТ нельзя применить буквально. Для независимых ограниченных центрированных битов достаточно, например, : тогда условие Линдеберга выполняется и имеет нормальный предел. Если суммарная дисперсия не растёт, колокол не гарантируется, но граница дисперсии среднего остаётся верной.

Инженерные оговорки

32-кратное уменьшение по сравнению с 32-битным числом относится к полезной нагрузке одной координаты; адресация, масштабы и протокол тоже стоят биты. При фиксированном бюджете «все по одному биту» не всегда лучше более точной передачи от случайной подвыборки: результат зависит от неоднородности данных, схемы выборки и квантования. Сжатие само по себе не даёт приватности: при или 1 бит раскрывает значение точно, а повторные сообщения накапливают информацию.

Сюжет связан с указанной беседой А. В. Гасникова на ПостНауке и исследованиями несмещённого квантования. Он является самостоятельным учебным выводом, не транскриптом видеобеседы и не полным алгоритмом федеративной оптимизации.

От скалярного бита к шагу обучения

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

Задача с ответом

У 10 000 устройств все значения равны 0,3. Независимое однобитное округление даёт среднее 0,3 и стандартное отклонение . Детерминированное округление даёт ноль: абсолютная ошибка 0,3. Общая случайная пороговая величина даёт либо 0, либо 1: стандартное отклонение около 0,458. Три режима различаются не количеством сообщений, а устройством ошибки.

Почему общая случайность сохраняет положительные ковариации

При одном общем пороге U произведение двух битов равно 1 тогда и только тогда, когда . Поэтому

В дисперсии среднего теперь остаются все попарные слагаемые ковариаций. При одинаковых p каждое равно , а таких членов порядка ; деление на их не устраняет. Это математическое объяснение того, почему на третьей картинке колокол не сжимается при добавлении устройств.

Как связаны три главные идеи лекции

Линейность ожидания отвечает за правильный центр результата даже без независимости. Сложение дисперсий и закон больших чисел отвечают за уменьшение ошибки при независимом квантовании. ЦПТ при дополнительных условиях описывает форму увеличенной остаточной ошибки. Хёффдинг даёт конечновыборочную вероятностную гарантию, не ожидая предела. Это четыре разных утверждения, которые нельзя заменять одним словом «усреднение».

Для неодинаковых независимых битов условие действительно обеспечивает условие Линдеберга: , поэтому для любого фиксированного при больших m ни одно слагаемое не превосходит . Соответствующая сумма хвостовых вторых моментов тогда в точности равна нулю. Это обоснование применимости расширенной ЦПТ, а не предположение об одинаковости данных устройств.