Transcript

Use with ChatGPT / Claude Auto-scroll A

1. Федеративное обучение и базовая постановка

Обсуждается, почему федеративное обучение кажется приватным, и формулируется базовая схема обучения с частичной выборкой клиентов. Вводятся основные обозначения и описывается алгоритм FedAvg.

0:05 - 1:28
дифференциальная приватность в федеративном обучении.Да.Почему вообще интересно посмотреть на эту постановку?Ну, потому что в федеративном обучении мы уже не не имеем доступа к модели, как в обычном стастическом, да, у нас есть несколько моделей клиентов, которые каким-то образом агрегируются впоследствии обновляя модель сервера.Вот.И кажется, что федеративное обучение должно быть э-э приватно по самой своей парадигме.Она же не видит ни какие данные есть локальные у клиентов, ни как происходит агрегация.Ну, в общем, очень мало известных элементов в федеративке.И вот кажется, что всё должно быть хорошо, здорово и приватно.Да, давайте напомним про постановку вообще федеративки.Да, мы хотим минимизировать функцию потерь на сервере, а сервер, соответственно, представляется в виде агрегации по n-клиентов.И каждая функция ФТ, да, которая представляет отдельного клиента, является усреднением по нескольким локальным эпохам или нескольким локальным бочам на клиенте.Вот формально у нас все ифыты могут отличаться, но мы сейчас рассматриваем базовую постановку в федеративке, когда у нас на каждом из клиентов висит одна и та же моделька, да, и, соответственно, у сервера тоже будет эта копия модели.
Вот.А также вот тут, наверное, стоит, э, чуть поподробнее, э, момент, сейчас что-то написал.А, а, чуть поподробнее разобрать вот этот момент, да, потому что в федеративном сетапе, в отличие от распределённого, у нас усреднение, ну, или агрегация просто элементов с клиентов, она происходит не обязательно по всем клиентам.Более того, зачастую рассматриваются такие, ну, более реалистичные сценарии, когда некоторые клиенты у нас могут быть просто недоступны для агрегации в том или ином раунде, так называемые partial participation форматы.Вот.Поэтому мы сегодня будем рассматривать именно постановку с агрегации именно по какому-то подножству или когорте.Так, по обозначениям, которые я унифицировал по четырём статьям.Значит, у нас есть количество пользователей N большое, DТ - это их локальная подвыборка, - это количество раундов, которые у нас проходят в федеративном механизме.А WТТ - это, собственно, общая моделька на этом раунде, да.WТ ИТ, соответственно, - это модель клиента, итого клиента на этом раунде.
А значит, ST - это мощность выбираемых клиентов, по сути, да, точнее, множество выбираемых клиентов.М - это у нас, ну, мощность количества индексов, которые мы взяли.Уит - это локальные изменения модели, да?Потому что у нас иногда, что получается?Мы делаем несколько локальных эпох.И говорить, что, ну, мы передаём последний градиент - это как бы довольно странно.Поэтому мы передаём как бы такой релаксированный градиент, который является просто разностью весов модели.определённую на stepпсайizзe.В парадигме того, что у нас stepп-сайizз при локальном обучении он как бы не изменяется, да?А, соответственно, порог клипинга цит - это сигма как относительно масштаб гасового шума.И лямбда - это коэффициент регуляризации, про который, если мы успеем, мы поговорим в фтр подходах.Вот.А, собственно, как выглядит ФДВГ, да?Самый базовый алгоритм федеративного обучения Federative Averaging - это когда у нас на этом раунде есть расскидка, собственно, серверной модели по всем клиентам.
Каждый клиент делает несколько локальных эпох, да, и впоследствии отдаёт обновление в виде разности весов просто моделей.Вот сервер у нас всё это агрегирует, да, посредством усреднения по количеству участвующих клиентов, а делит это на шаг и обновляет серверные веса.Вот.А, да, тут я какую-то схемку придумал.Зачем, непонятно, потому что она начала плыть при демонстрации, за что, прошу прощения.Ну, в общем, у нас каждый пользователь с локальными, собственно, детасетами производит некоторые локальные операции, передаёт обновление, сервер их агрегирует, обновляется.

2. Угрозы приватности и атака DLG

Разбираются уровни уязвимости в федеративном обучении и показывается, что базовая постановка не является приватной. Затем вводится атака Deep Leakage from Gradients и объясняется, как по градиентам восстанавливать исходные данные.

А какие уровни уязвимости можно выделить в такой постановке?Ну, как бы я их разделил специально сильно, да.У нас есть пользовательская уязвимость.Когда мы начинаем проверять на ДП гарантии именно самого пользователя, есть уровень передачи самой информации.То есть злоумышленник имеет, например, доступ именно к переданному обновлению, но при этом не имеет доступа к локальной подвыборке пользователя.Он, в принципе, ещё должен иметь ээ доступ к модели, которая в таком формате учится.Но как бы очевидно, что если мы работаем не в personalized FL формате, да, когда у нас есть некоторое отличие между моделями пользователей и сервера, то в базовом Эффеле у нас все модельки одинаковые, являются некоторыми копиями одной архитектуры.Также есть уязвимость самого сервера, но уязвимость сервера она скорее как бы уже была нами разобрана, потому что, ну, можно учитывать все вот эти вот обновления от каждого из клиентов как некоторый бач градиентов.и, соответственно, атаковать сервер уже по формату ДП, который мы проходили.
Аа, собственно, давайте сразу пойдём, пропусть вопрос, что FL приватное или не приватное.Оно не приватно в базовой постановке.И вот, наверное, самой красивой и самой простой атакой является DLG Deep Leakage of Gradi, потому что она нацелена просто на восстановление градиентов и восстановление истинного изображения, которое было у пользователя.Собственно, модель атаки довольно проста, да?У нас есть известная сеть FW, есть параметры W, есть некоторая индивидуальная потеря на каждом из клиентов или в принципе серверная, да, и индивидуальный градиент одного примера.То есть по сути обновление, которое передаёт клиент к серверу.Что у нас получается?У нас получается, что вот это это истинный градиент, да, по некоторому локальному сэмплу X с меткой Y.И мы хотим восстановить такие X со звёздочкой, Y со звёздочкой, да?А, собственно, чтобы угадать истинный X и Y по доступу к этому истинному градиенту.Вот, соответственно, определение, которые дают в самой работе про идентифицируемость, что элементы выборки локальной клиента идентифицируемы по градиенту.
Если у нас про образ вот этого преобразования GW, да, то есть обратное преобразование к вот этому всему, у нас содержит только вот этот данный пример.А вроде с постановкой всё просто, как это решать?Ну, на самом деле, решение, ну, немножко тривиальное.Нам нужно каким-то образом приблизить градиент на по X со звёздочкой Y со звёздочкой к истинному значению, соответственно, градиента по XY, да?Вот давайте посмотрим на афином слое или просто линейном.А, собственно, у нас есть выход, да?А - это, собственно, линейное преобразование над входом X и B со смещением B.Тогда обозначим Q как градиент лоса по А, которая не равен нулю.Ну, иначе будет грустно, мы находимся в оптимуме.Вот если у нас известны градиент по А и градиент по B, то оказывается восстановление вот этого элемента X, оно довольно тривиальноя, да, оно выглядит вот в таком вот формате, просто из применения цепного правила, да, есть для такого простого
формата с линейным слоем мы можем типа изначально восстановить значение соответственно нашего примера а посредством знания градиента, который прокидывается через этот слой.Но это здорово.Насколько это работает в реальности?Ну, в реальности, наверное, работает плохо, потому что у нас помимо градиентов есть ещё какие-то функции активации.Если мы ещё посмотрим на модель клиента, то это вообще будет грустно, потому что она может быть там не то что нелинейной, а там с какими-то рандомными слоями, условно, там в силу или ещё чего-то.В общем, как пример ок.Но на практике, наверное, не работает.

3. Как работает восстановление градиентов

Поясняется оптимизационная постановка DLG и интуиция восстановления примеров через минимизацию расхождения градиентов. Обсуждаются практические ограничения атаки и показывается, что при одном локальном шаге восстановление работает особенно хорошо.

Собственно, что предлагает Depage of Gradi?Он предлагает взять и решить вот такую задачу оптимизации, да?То есть взять какие-то фиктивные X и Y.Каким образом они считаются, мы ещё поговорим.Взять от них функцию градиента и посмотреть на ошибку, соответственно, наших игреков с ошибкой
истинного градиента.Тфу.Со значением истинного градиента по L2 норме.Ну, задача оптимизации выглядит довольно простой.Аа как её решать?Ну вот пусть у нас есть,собственно, sampм.Да, обозначим его за Z.за,то есть ошибку обозначим разность градиента назад и истинного градиента.Аа
тогда тогда вот напомню, что у меня или просто матрица J, она вот в таком формате записана, да?Тогда может быть представлен у этого ЕКБИАНА.У нас получится вот она представляется в виде который, а, собственно, даме sampм, который мы пытаем, по которому мы хотим оптимизировать это всё.А, собственно, как работает алгоритм в общем формате?У нас есть известные Веса и Ж со звёздочкой, да?Есть некоторое число итерации для оптимизации вот этой матрицы.И есть некоторое правило оптимизации, по которому мы это всё будем отрешивать.Любой метод в оригинале автор использут просто из ГД.Вот, соответственно, мы каким-то образом синтетически симплируем x0, да, и просто какое-то непрерывное представление метки.Вот, соответственно, в процессе итераций, что мы делаем?мы получаем некоторую допустимую метку, прогоняя это, собственно, через трешхолдинг какой-то.Считаем градиент по, э, нашему даме смплутки, которая получилась.Вычисляем, соответственно, матрицу икоби и оптимайзим, соответственно, наш sampм и фиктивную метку.
Вот, соответственно, такой алгоритм.Довольно понятно, интуитивно понятно, почему нам возвращает что-то похожее на то, что есть в изначальной выборке.В чём его проблема?Что нам, в принципе, нужно понимать, какое у нас распределение есть.Но как это сделать, не имея доступа к, собственно, обучающей выборке модели?Ну, довольно просто.Мы можем просто запромтить, запромтить, ага, заинференсить ээ серверную модельку, посмотреть, что она нам выдаёт, сказать, что вот, в принципе, всё распределение, которое мы смогли увидеть, это вот наши лейблы.Ну давайте с этими лейблами по по трешхолдингу работать.Благо, что мы знаем, какая модель находится на сервере, точнее, её архитектуру,
11:47 - 11:48
да,
11:49 - 11:56
средне по тому, что есть у этого клиента.И вот такой адапта мы в среднем получим, да,
11:56 - 12:02
в среднем по тому, что есть у клиента, не очень понял.Поэтому,
12:02 - 12:37
ну, здесь подразумевается, что шаг один по клиенту вообще.То есть и да, спасибо за замечание.Подразумевается постановка вот самого-самого трушного эффеля, когда у нас один шаг оптимизации по каждому из клиентов, да, после этого агрегация всех этих градиентов и передача в сервер.Аа, но на самом деле это будет работать даже в постановке, что мы сделали несколько локальных шагов, сделали вообще всю эпоху.Но тогда что мы делаем?Мы делаем обновление формата разность весов модели делённо на степсай.
12:39 - 12:41
То есть оно тоже даст что-то похожее на мет.
12:41 - 12:44
Да, да, да.А вот
12:44 - 12:53
еслидем,соединяем по всему датасету, который на клиентеклиент,
12:53 - 12:56
мы же получим типа этой атака и что-то среднее, да?
12:56 - 13:34
Да, мы получим что-то среднее.И вот как раз, ну, есть смплы, которые более-менее хорошо восстанавливаются, которые, ээ, в направлении которых модель уже, скорее всего, не двигается.И вот эти сэмплы на самом деле довольно неплохо восстанавливаются э именно вот этой DLG атакой.Ну вот, э, здесь пример, конечно, я не очень хороший привёл.Надо было в апендикс лезть и доставать я что-то не паление смплов на что там, намнести и на цефаре из того, что есть.Ну, есть ещёсет с этот, господи, а, faces datasсеet и с
ха, который про что?Про какие-то просто рандомные фотки.Вот оказывается, что DLG в базовом формате, когда есть доступ к один, ровно один оптимизационный шаг, он довольно быстро умеет восстанавливать истинные, соответственно, элементы, которые были в обучающей выборке клиентов, что очевидно показывает, что, ну, как бы ээ обучение приФИДВГ с одним локальным шагом, оно ни фига не приватно.Вот простая интуитивная штука.

4. Защищённая агрегация и канареечные градиенты

Переходят к защищённой агрегации и обсуждают, как она должна скрывать индивидуальные обновления клиентов. Затем рассматривается идея канареечных градиентов и атака на защищённый сервер через выделение целевого вклада.

Наверное, надо придумать какую-нибудь защищённую агрегацию, потому что, ну, вот если мы взяли и просто у нас есть на сервередоступ к градиентам, то это истинные смплы приватных выборах клиентов, потому что по базе федеративное обучение у нас используется, когда когда невозможно передать данные с каждого из клиентов на сервер Или есть э-э проблема с тем, что там клиенты удаленыот сервера и на сервере стоит более мощный железо или ещё что-нибудь.А значит, про защищённую агрегацию.А это вводится, по-моему, в вот вы не видите, а, ну, как оно задаётся.У нас есть несколько клиентских векторов обновлений, да, У1 и так далее УМ.То есть мы уже выбираем некоторую когорту участвующих клиентов на данном шаге.И, соответственно, некоторая агрегу агрегация выдаёт нам вот в данном случае просто сумму этих обновлений, но нам хочется сделать эту агрегацию такой, чтобы при этом не выдавалась информация о входах сверх того, что вот следует из суммы.
Да,
15:31 - 15:39
если передавать клиента в посижение аре
теряет у нас федеративное обучение оно получает приватность или нет?
15:48 - 15:56
Да.Да.Федеративное обучение, да и любое обучение в LBIT пресижение теряет вообще любые гарантии ДП.Теряет получает.
15:56 - 15:59
Тьфу, получает.Кстати,
15:59 - 15:59
ну то есть
15:59 - 16:51
нет, не получает.Объяснение следующее, потому что ты не можешь вывести в Lowbit Pris DP гарантию вообще как такову.Ну этого пока никто не сделал.На практике, если мы рассматриваем ДП с точки зрения именно математической абстракции, то получается любой lowbit формат - это уже зашумление истинных данных, и формально они должны давать некоторые ДПрантии.Более того, из-за того, что low beit э-э оптимизация она более шумная и более неустойчивая, э, соответственно, это можно трактовать как наложение дополнительного шума.Однако, однако из-за того, что low beit может быть проинтерпретируем как некоторое детерминированное слшстахастическое преобразование над весами в каждый момент времени, то
через это можно
16:59 - 17:01
через тему сетинга,
17:02 - 17:15
но там сложная композиция просто не будет работать.Ну то есть прямо в лобовую не решается эта задача.Вот так.Э-э, что я хотел рассказать?Ну опять
17:15 - 17:17
что
целый и для компрессии есть, потому что компрессия она довольно понятна с точки зрения применяемых компрессоров.Она применяется там в компрессоре ранка, топк, там компрессоре квантования, так называемом, но оно довольно плохо по похоже на лоубито оптимизацию.Есть гранп, я не заказываю.Да,
а есть, по-моему, есть формате.
Но как бы они как и обычные ДП сходятся к некоторой окрестности глобального оптимума, что логично.При этомпри этом это скорее как бы математические гарантии в формате, что у нас Веса из РДЕП к нам приходят.На практике на практике они сохраняются, но в некоторых случаях может следовать за этим развал обучения.Ну, из того, что я сам тестил, да.Вот просто с компрессорами легко работать.Их можно всех запихнуть под одну гребёнку.Либо они равномерные, ну, то есть несмещённые компрессор, либо они контрактные.То есть у них нет несмещённого первого момента.А с битами так не получится сделать.Вот так.Про защищённую агрегацию, да?Как построить атаку на защищённый сервер?Давайте подумаем.Ну вот пусть у нас сервер выберет некоторую цель в виде катого клиента и, соответственно, параметры Wта для каждого клиента.Собственно, клиенты исполняют, блин, я не забыл поменять этот глагол, выполняют локальный алгоритм и не проверяют у нас равенство всех дубльвыитах на соответственно, которые они получили.
Некоторая защищённая агрегация у нас корректно раскрывает точную сумму по всем обновлениям.И для нецелевых клиентов у нас существует некоторая дубль ск ой с крышкой с тильдой, которая подавляет нужные координаты обновлений.То есть мы не хотим раскрывать полностью всю информацию о том, э какие клиенты были использованы в при обновлении на сервере, да?И нужно, чтобы злоумышленник их угадал, ну или, по крайней мере, восстановил это.А в дальнейшем можно уже делать ту атаку, которую мы проходили в ДЛГ.Вот
всех дубль выиги.Что это значит?Проверяю.Смотрите, в
постановке Secure Agregation мы разобрались, да, что условно по некоторым клиентам, а, ну или усреднённую сумму, там вообще без разницы.А, соответственно, часть обновлений, по которым не происходит обновление сервера, оно не должно быть раскрыто злоумышленнику, потому что они там в некоторый момент могут быть запривачены.Здесь неперерендеренный слайд почему-то.А, соответственно, не проверяет равенство всех WТХ означает, что есть проверка на то, насколько отличаются веса, которые получены в процессе локальных обновлений между другими, э, между всеми клиентами.Ну, потому что если у нас условно -э в вот эту выборку, которую мы агрегируем, попал условно попало обновление, которое в точности повторяет обновление какого-нибудь другого клиента, то это довольно плохо, потому что происходило на другом клиенте.Вот.Ну ладно, давайте вот сейчас вот этуштуку пропустим более понятно, как мне кажется.У нас есть некоторый сервер, как обычно, да, у нас есть моделька и её обновление у ката некоторое.Всё остальные модели, которые не участвуют при агрегации, да, они представляют некоторые модель W стильдей и, соответственно, их обновление, которое не используется при секре агрегейшене, оно должно быть равно нулю, да?
Соответственно, таким образом, защищённая сумма, она вот буквально в точности равна укатому, которая передаёт катая моделька.

5. Атака на secure aggregation

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

А, собственно, про то, что предлагают авторы в своей оригинальной статье про подавлейный слой с рело активацией.Да.А что здесь?Я же проверял, куда мы все переехали.А так, ладно, это скип просто потому что там, ну, немножко бред написан.
22:24 - 23:40
Давайте перейдём сразу к атаке.Это просто пример для одного слоя.Слой с активацией.Здесь не очень понятно будет постановка.А вот, наверное, стоит посмотреть на псевдокод одного раунда, что вот у нас есть некоторая цель в виде каждой модели.И мы создаём подавляющую модель W stild.Мы вот передаём модель клиенту, да?То есть модель V у нас дистрибьютится от сервера к клиенту, а W с крышкой, господи, стильдой, она передаётся всем остальным.Мы делаем, собственно, обновлениелокальное и передаю сервер, который производит протокол некоторого защищённого суммирования.Вот.А, соответственно, мы знаем, по какой клиентской модели мы делаем в данный момент обновление, да?Но при этом злоумышленник этого не знает.Вот, соответственно, мы извлекаем целевые координаты и производим восстановление или проверку свойств к вот этим вот координатам, которые мы восстановили из переданных даме моделек в стильдей.Вот, соответственно, что утверждают авторы.Вот это у нас вход, да?Вот сейчас я покажу.
У нас уита - это не S - это на наша сумма всех этих обновлений по всем клиентам.Так, вернёмся сюда.Соответственно, что сжитае это клиенты, которые участвуют в нашей выборке.Как оно происходит?Это просто вот обновление житое на катой, на катом клиенте, плюс обнулённые значения обновлений, да, по дами модулу, который передаёт сервер на всех клиентов, которые не являются таргетом.А как то есть сервер защищается от того, что был доступ к какому-то конкретному градиенту?Он делает для этого некоторую канареечное обновление на как на собственно вот этих вот всех модельках и таким образом пытается защититься от извлечения конкретного градиента по каждому из клиентов, который мывидели в ДЛГ.Вот предлагается сделать канареечный градиент.Канареечный градиент что делает?Вот у нас есть некоторые градиенты G1, G2 и ЖК.Мы можем вложить в это обновление ЖК-та некоторую, соответственно, точнее не так, в ЖКтом у нас есть некоторая чувствительная информация, которую мы не хотим раскрывать.
И, соответственно, мы хотим сделать агрегацию по сумме вот такого формата, да, что у нас некоторая функция пи, она будет возвращать нам значение этой при значении пи от суммы будет в точности равно значение пи от кто-то градиента, да?То есть, по сути, такая атака нам должна приблизить градиент К, про который мы не знаем, ну, типа, какого клиента мы из выбрали при данной агрегации.Вот.А, соответственно, детектор должен вот этот вот PC активироваться на нужном примере или на нужном свойстве, которое получено в градиен ЖКТ.Вот
что.А где
ту-туру-туру-ту-ту?Здесь должны были быть картинки, но картинки пропали.В общем, какой тейк?Вот в такой формации можно научить маленькую модельку, которая бы определяла вот это Pixси, некоторый аппроксиматор, который может извлекать даже при секре агрегейшене значение, соответственно, градиента, после которого применяется deep leaked gradient attack и восстанавливается sampмle с какого-то.При этом всё ещё есть доступ к модельной архитектуре, которая лежит на сервере.Вот.То есть даже в формате secure agгрейш можно поставить довольно простую ювристическую задачу по раскрытию локальной информации посредством э там обучения некоторой евристики в данном случае модельной апропсимации которая выделяет вот этот вот приватный градиент из secкure агрегеation потому чтов базе у нас как бы не хочется делать какие-то хитроумные финтифлюшки с градиентами нам хочется как бы усреднить и нормально куда-то сойтись на сервере, да?А таким образом, если мы начинаем там крутить и послесле этого ещё какое-то преобразование над ними сделал, так мы на сервере вообще никуда не обучимся.
И это очень плохо для Эффеля, как
алгоритмы вот от этого всего.Вот если у нас сервер видит индивидуальный градиент, то мы вот посмотрели, что можно восстановить исходный пример, да?Если сервер видит только агрегацию некоторую, ну вот, например, сумму этих градиентов, то можно таким образом подготовить входы через, что сервер может выделить этот вклад цели через аппроксиматор.Вот.То есть нам нужно каким-то образомв ДП на разных уровнях уметь ограничивать информацию.

6. Теория приватности в федеративке

Вводится клиентская смежность, фиксированное правило участия и переход к дифференциальной приватности в федеративном обучении. Объясняется связь чувствительности, гауссовского механизма и RDP, а также композиция приватности по раундам.

И давайте перейдём уже к теоретической постановке.Первое определение - это определение смежности.Если раньше мы работали со смежными выборками, которые отличались по одному элементу, то в данном случае в FL-парадигме у нас отличие идёт на уровне клиентов, да?То есть две выборки D1штрих до DNштрих.Это такие выборки клиентов, что существует такое к у нас дета - это смежная DIш штрих выборка.Вот.А сами наборы ДКТ и ДКштрих могут различаться произвольно.Вот, собственно, для последующих выводов у нас будут фиксировано, потому что иначе очень тяжело выводить какие-то базовые ДП гарантии.У нас фиксирован список пользователей, то есть мы работаем не в онлайн-постановке, когда у нас могут приходить рандомные новые пользователи и изменять трек и правила участия.То есть у нас есть детерминированное правило, которое отбирает нам к-лиентов на каждом раунде.Вот.И, собственно, правила участия у нас не раскрывает дополнительной приватной информации, а все условные сравнения выполняются при одной и той же опубликованной истории.
Это важно, что, ну, чтобы у нас не менялась траектория в процессе.То есть, например, мы опубликовали калитерации предыдущих обновлений для этого клиента, а потом резко решили, что всё, у нас интернет ул,мы не хотим больше передавать эту информацию, и на сервер это больше не приходит.Подход, который был предложен именно с точки зрения вообще ээ дп вле, это адаптивный клиппинг.Вот у нас есть локальный вклад, да, у ИТ.Мы навешиваем на него клиппинг, в данном случае базовый, да, и вот смотрим на зашумлённое значение градиента.То есть, по сути, что мы сделали?Мы взяли парадигму ДПСГД, да?Только теперь у нас обновление не по одному сэмплуит, а по агрегации зашумлёнклипированных самплов, которые всё прекрасно знаете.Здесь это клипинг.написан.А, соответственно, вот это устойчивость между двумя смежными выборками, да, между акатом и АКштрих, что у нас условия на отличие меньше, чем 2C, которые используется в доказательстве ДПСД.
Да, давайте чуть-чуть про теорию поговорим.Первое, что нужно вести - это чувствительность.Вы, наверное, уже прочитали в домашке.Я очень надеюсь, что вы его хотели, хотя бы открыли.А вводится L2 чувствительность.Ну, это по сути супремом по смежным выборкам вот такой вот величины.Ну, довольно понятная штука.Вот.И авторы доказывают очень простую лему, что у нас разность, то есть вот эта вот ээ чувствительность может быть ограничена через клипинг как 2 о'кей?Это, в принципе, база.Что они делают?Они переходят от гаусовского дифференциального механизма, да, к приватности по реньи.которая наиболее, наверное, применима в современных задачах, потому что, ну, даёт чуть более жёсткую оценку, чем GDP, и при этом имеет понятную с ним связь.Смотрите, приватность по ренги - это, по сути, некоторая альфа-дивергенция, да?Она задаётся вот таким вот страшным интегралом между распределениями P и Q, да, с плотностями P маленькая и Q маленькая, которая существуют вот по общей мажоритарной мере.
Вот, соответственно, механизм некоторого приватного обновление имеет стоимость от альфа распределением пуплением Q, то есть по сути тем, что выдаёт механизм.А, соответственно, какая связь с гаусовским механизмом?Вот если у нас чувствительность, то есть отличие по, господи, распределениям смежных выборок не больше, чем дельта, и мы смплируем из нормального распределения с сигмой, ну, сего дисперсия равна S, да, то у нас связка между бюджетом RE и бюджетомGDP, она вот такая вот.То есть бюджет рении дифференциальной приватности, он более жёсткий, нежели чем то, что нам даёт соофт механизм.Но вот у них довольно простая оценка, ну, связка между ними, да.Ну и очевидно, что если мы хотим получить какую-то нормальную ДП гарантию, то мы обычно работаем именно в постановке RDP, то есть RFial Privacy.Так, а про позицию и переход к ДП.Вот тут, наверное, я сейчас надолго залипну, потому что это краеугольный какой-то момент.Смотрите, если у нас в некотором раунде Т на стоимость RDP R отт, да?
То есть, ещё раз, вот у нас
был, э, механизм некоторый там, условно итоговый потраченный бюджет на он меньше или равен.
чем сумма всех бюджетов, которые мы по потратили отдельно на каждой итерации.Вот это важно, потому что у нас сейчас, когда есть несколько нить, да, через там РДП, как оценивать потерю бюджета на сервере, вообще непонятно.И вот эта вот штуковина, вот эта штука, она нам даёт, соответственно, понимание того, что потраченный бюджет при обновлении сервера не превышает сумму потраченных бюджетов на каждом из клиентов.Вот это со собственно теорема, и она, ну, не очень оригинальная статьте, там есть доказательства.Вот, соответственно, какой вывод из этого всего делаем?Нам же нужна си дельта приватность, да?Вот оказывается, что тогда для любого дельта у нас весь протокол нашего обновления, если с RDP стоимостью на каждой тта итерации, он будет удовлетворять вот такой оценке наси.

7. Проблемы клиппинга и адаптивный порог

Обсуждается, почему фиксированный клиппинг плохо работает при сильной гетерогенности клиентов. Затем вводится квантильный подход к выбору порога клиппинга и приватный счётчик для оценки числа клиентов под порогом.

Вот.То есть как бы получается,
которая не видел никаких, собственно, данных.ээ и не видел, собственно, моделей в общем случае,
потому что ДП постановка, переворовку может
аа Да, собственно, в чём проблема?В чём проблема?Что у нас нормы с клиентов, они вообще, ну, неадекватно себя ведут.нормы градиентов с клиентов, они могут меняться очень сильно, ещё даже до применения какого-нибудь шума, да?Вот здесь показана картинка из оригинальной статьи.Они прогнали на нескольких клиентов э довольно слабо гитрогенными выборками.То есть распределение данных на каждом из клиентов отличались слабо, как по иксу, так и по игреку.Обычно они смплируются с помощью дирехле распределения.В реальности же, если мы смотрим на какие-то там, ну, реалистичные, ну, порядка там
с параметром там единичка или полтора.Ну, то есть довольно сильная гитрогенность.Вот.И, соответственно, у нас приходят различные градиенты.И если мы начнём клипировать их с одним уровнем, да, потому что мы жёстко урезаем.И если мы будем собирать какую-то гарантию, но при этом ещё с весами из РД мы должны куда-то сойтись, на практике такое, ну, к сожалению, не работает.Поэтому авторы ставят следующий вопрос: как нам сделать порог клиппинга адаптивным, чтобы мы не загубили своим ДП вообще качество обучной модели?Потому что есть большая проблема с этим.Если вы порешаете практическое задание, вы увидите, что пороги клиппинга могут не сильно влиять на бюджет приватности, но очень сильно влиять на финальное качество модели.Вот.А, собственно, что предлагают авторы?Они предлагают определить квантиль для нормы и, соответственно, будем доказывать, соответственно, дифференциальную приватность нашего алгоритма.Собственно, давайте в обозначим через R собственно норму обновления, да?А, соответственно, f от r - это наша функция распределения вероятности для эрок меньше или равных, чем некоторое заданное значение c.
А, соответственно, гамма квантиль, напоминаю из статов у нас
выглядит вот таким вот.Что здесь написано?Здесь написано, что функция распределения у нас у, точнее, значение функции распределения зажато сверху и снизу, соответственно, элементами.
есть какие-тоционные
методы аля там zero ордера, вот то множество квантилей у нас совпадает с минимум функцией, то есть Вот если мы записываем вот таким вот образом, то мы можем через квантили хорошо приблизиться к формату использования базового трешхолда, который наперёд задаётсяна весь процесс обуче, что вот, ну, мы можем рассмотреть отрицательные и положительное, соответственно, значение функции распределения, да, оно вот таким вот образом записывается.Значит, по условию минимуму выкуплой функции, а мы всё ещё для выведения какой-то
нтии работаем с выпуклыми функциями, то вот если у насоптимум негладкой выпуклой функции, да, то тогда у нас нолик должен лежать вот в этом отрезочке.Если нолик лежит в этом отрезочке, то что можно сказать?Можно сказать вот такую штуковину.Вот.Соответственно, для эмпирического распределения субградиент выбирается вот таким вот образом.То есть мы взяли, посчитали ограничения, посмотрели индикаторы для всех клиентов, которые имеют ограниче, господи, норму обновления меньше или равную, чем C, и просто взяли и усреднили, ну, там, с учётом квантили, да?То есть нашему ограничению,да.Собственно, про на чём мы остановились?На агрегировании вот этого всего.У нас есть сравнение, собственно, индикаторные сравнение по тому, какие клиенты удовлетворяют ограниченность норме нормы градиента.И приватный счётчик, что у нас делает?Он у нас суммирует все эти бритые, да?То есть, по сути, считает количество клиентов, которые у нас участвуют на этом раунде, добавляет некоторую случайную величину к ситом усредняет.
Что у нас делает некоторая случайная величина к си?Она нам не позволяет, точнее, злоумышнику не позволяет нормально узнать, сколько клиентов участвовало на этом раунде.Потому что, ну, как мы уже видели, если мы знаем по с каким клиентам делается агрегация, то мы можем понять, ээ, соответственно, обновление каждого из этих клиентов через атаку от Secure agгation.
А и мы по этому признаку бираем в участке.
41:29 - 41:39
Сейчас бта у наснет.Это да, это индикатор того, ну
удовлетворяют условия на трешхолд по клиппингу.Изначально свои же градиенты.Вот приватный счётчик нам даёт количество клиентов, которые вернули градиент, довольно маленький.Вот.Аа,соответственно, сейчас клиппинг выбирается как экспоненциальное распределение, потому что там удобно для него это всё считать ээ ограничения по квантилям.Это просто ивристика, которую предложили авторы.На самом деле можно просто какой-нибудь скедлер поставить на клиппинг.

8. Алгоритм адаптивного клиппинга

Поясняется, как сервер и клиенты используют адаптивный клиппинг в процессе локального обучения и агрегации. Разбирается, как шум, индикаторы клиппинга и RDP-оценка дают более жёсткую гарантию приватности.

Давайте сейчас перейдём к колгосу.Мне казалось, что это именно для secк агрегейшна делалось.А нет, ну когорта выбирается самостоятельно.Ну ладно, хорошо.Что-то я, видимо, не разобрался чуть-чуть.Так, значит, что происходит на клиенте, да?Как в процессе, когда нам передал сервер обновление модели ВТ, новую её версию, что у нас происходит?И происходит локальное обучение.Де считается, собственно, почему сырой вклад?А, ну потому что это дословный перевод.Сорри.А, а обновление с этого клиента считается меньше норм этого обновления, чем заданный порог клиппинга.Если а нет, еслизачем я если говорю, в общем, клипируются обновление и передаётся пара вида клипированное обновление и, соответственно, меньше порога клиппинга или нет.Вот.А всё это считается на заранее раскиданном значении цитета, которое считает сервер.Ну, он считает его вот в таком формате.А-э, он может читать по какому-то заданному скедлингу до этого.Вот что у нас делает сервер?Сервер делает вообще, ну, нетривиальную штуку, как по мне.
Он, собственно, генерит наши случайные величины.А, соответственно, значение Z дельта ввадра оно у нас задаётся из DP и потом будет посчитано.АТ у нас, как обычно, клипинг на этом раунде и случайная нормальная величина шума Кситта.Вот.Он получает приватные, средние, да, делает усреднея по всем аитам, которые входили в когорту, и делает обновление по БТАм.А, соответственно, БТы узна О, господи, агрегируют в себе знания про то, какие элементы входили с градиентами большими, чем заданный порог или меньше, чем заданный порог.Обновление на сервере происходит вот в таком вот формате.Так, вопрос следующий.Внимательные слушатели могли заметить, что как бы, ну, взяли, усреднили снова всех градиента, ой, всех клиентов, клиентские градиенты, закинули шум и сделали обновление.Вроде БТ нигде не участвуют, но вот оказывается, что БТ участвуют у нас в Z дельта в квадра.Вот.То есть что происходит?У нас происходит следующее.Вот у нас обновление уитая, оно по нему считается две величины.
Аита с клипингом, да, добавляется сумма Z.Получается, соответственно, дисперсия шума, который мы докидываем - это S от Z рав Z дельта некоторая, умноженное на константу клипинга.Вот на этом раунде.А, соответственно, индикатор клиппинга, а он даёт нам некоторую сумму, соответственно, элементов, которые были меньше по норме градиента, чем константа клиппинга.Плюс добавленный шум.Дисперсия добавленного шума равно тау.Это тоже и гиперпараметр, который можно подбирать.Вот.Соответственно, что у нас такое куито.Куито это же распределение, да?Туру-туру-ту.Что?Да, было, было.Вот оно было.Это плотности были.Сейчас, подождите, я переобозначил все определения и статей, чтобы они были условно одинаковыми по лекции, и забыл, что я переобозначил, что логично.Вот
что.Ноито - это просто модель, да, которая у нас работает со всем этим, да, это просто механизм для, ну, это query, то есть, ээ, выдача моделью по результатам там обновления по выборке или ещё чему-то.Вот это обозначение Q.Соответственно, что они здесь показывают?Они показывают, что Итая выдача может быть представлена в формате вот такой вот штуковины, где её квадрат нормы будет ограничен вот такой вот величиной.Совместная нормировка двух приватных каналов.Это очень хороший вопрос,
46:59 - 47:19
да?Нет, вот это это двумерный случайный вектор.Да.Ну, как, ну, э, немножко, мм, не двумерный, а D + одимерный.А так, да, да.Вот.А-э,собственно,
да, это, собственно, а, агрегация по всем клиентам по двум, ээ, соответственно, элементам.Первая по градиенту, который есть у клиента.Вторая - это по вот этому битику, соответственно, меньше, чем норма клиппинга или не меньше, чем норма клиппинга.Вот.И оценивается, что норма вот этого вот, господи, передачи куита, оно сверху ограничено вот таком вот такой штукой.И это вроде правда даже сейчас ээ отсюда 1 на Z дельта в²вадра должно бытьшка ещё должно быть
48:09 - 48:13
нет.Нуцета у нас обязательно должна быть.
Аита по уровне больше, чем C.Да, всё отлично.Да, тогда неравенство выполнить.Хорошо.
Так, какое утверждение было доказано авторами?Разобрались с куитами, не поняли, где они здесь используются.Мне кажется, что я вот тут вот неправильно переписал сейчас.Ну это же очень легко проверяется.Мы делаем вот так.
А вы ничего не увидите.Правильно.
Какие вы глаза стоит.
Ой, ну и замечательно.А так это же оно.Это не адаптив, да?Adдаптив клипоing.Сейчас момент, момент.Ну момент тут тоже есть.
Нет, сейчас вот вот локальное обновление, да, с заданным порогом клиппинга.После этого шумовка изначальных градиентов, как было в, ну, в базе ДПСД.После этого обновление с моментумом э шага, да, ну просто градиента.Вот.А и обновление элементат, которое влияет на выбор сигмы дельта в квадрате.Вот
что
50:05 - 50:50
где понять?Ну вот вот тут, да, ну она это за дельта нацет.Цтт обновляется через знание априорное про то, сколько элементов было больше или меньше.То есть по сути клиппинг подстраивается таким образом, чтобы выровнять условия ээ для всех клиентов.То есть, если, например, у нас приходит какой-то огромный градиент, да, который перекрывает ээ все градиенты низких пользователей, то, очевидно, его нужно клипировать сильнее к пользовательским градиентам, чтобы у нас он не выбился в сумму и по нему уже нельзябыло ничего провести.Вот, собственно, идея вроде такая должна быть.Я только не понял, почему у меня это не перенеслось
сейчас.Что?Нет, это дерево под оттресков.Мы до него ещё не дошли.
Нет, сейчас.А значит, какое утверждение?Да, Аит, как обновление ограничено.BТ от нуля до единички участвует не участ О, господи.Да меньше или не меньше, чем нормаклипинга.Шумы независимы с отклонениями.Условно А точно, я вспомнил, зачем это сделано.Потому что иначе мы никак не можем посчитать бюджет, трату бюджета на одно и то же обновление.Во, что довольно логично.Смотрите, мы же должны посчитать бюджет для участия с точки зрения именно уже клипированной величины, которую мы отдаём серверу.Да, агрегация это никак не влияет на бюджет, который мы используем.А вот все махинации с векторочками, они влияют на это.И чтобы получить хорошую ДПо оценку, авторы прибегают вот этому ухищрению, которое ещё и на практике работает, просто потому что, э, соответственно, есть ну, усреднениенормы градиентов по квантильному клипингу, чтобы градиенты не сильно друг от друга отличались, не зависимости от того, что у нас там пришло, от одной модели или от другой модели.
Вот.Ну, очевидно, что у нас может быть раунд, в котором, например, ну, трешхолд клиппинга, который мы выбрали для него, будет не очень удачен.То есть, например, у нас получился огромный градиент по одной модельке и очень маленькие градиенты по всем остальным.В таком случае всё-таки итоговый градиент будет больше направлен в сторону того, который был большим.Однако всё ещё должна будет сохраниться, э, соответственно РДП приватность, ну, точнее механизм будет выполнен, и отсюда будет следовать ДП приватность с дельта гарантии.

9. Гарантии и эксперименты адаптивного клиппинга

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

Вот тяжело все эти евристики для того, чтобы получить статистические границы, они, конечно, классные.Вот, значит, какое утверждение доказали авторы?Вот первое и важное - это вот эта штука, что у нас ээ стоимость с точки зрения RDP аккаунтента, она вот вот такая вот на обновление.Причём Z дельта в минус второй и TAO в минус второй, ну, на самом деле, можно посчитать довольно просто.Вот.Ну вот Z дельта - это вот вот такая вот штука.Поверьте мне.Если не верите, можно сделать вот таким образом.Где у теорема один заказано.А это нет, это укороченная версия.Блин, мне опять не повезло выбрать укороченную версию Снипса.Будь прокляты люди, которые саплимент не докидывают.
Но они, по-моему, через ренормировку это делают.Сейчас я Ну это скетч.
54:02 - 54:06
А, ну, ну да.
Это доказательство того, блин, чего это доказательство того, что он сходится так же, как неадаптивный ДП ФДВГ.Но ДП ФДВГ мы как бы разобрали, на самом деле, вот тут, когда вот это обсуждали.
А где
у вот тут?
Ну что у нас DPФДВГ выглядит в формате DPSGD?Просто аккаунтент по каждому из пользователей происходит э
ну вот через господи, где эта сумма-то?А вот вот вот эту вот штуку.То есть сумма участия каждого пользователя может быть оценена вот таким вот образом.А авторы предлагают квантильную штуку для того, чтобы получить более жёсткое ограничение на потраченный бюджет приватности.При этом сойтись точно так же, как ДПФДВГ.Чёрт, что-то поплыл под вечер.Вроде вчера с этим разбирался.Да, сорян.Собственно, адаптивный клипинг им нужен только для того, чтобы урезать ээ оценку на потраченный бюджет, да, потому что в ДП мы обычно гонимся за тем, чтобы более приватным алгоритм сделать с точки зрения э потраченного бюджета приватности.И, соответственно, они оценили через ГДП.Ой, куда?оценили через ГДП, ДП ФДВГ.Авторы вот этой статьи, а кто они там?Каружи же.А, Макмахан.А Макмахн что сделал?Он, соответственно, сказал, что ограничение не лучшее.Давайте сделаем адаптивный клиппинг.Он будет сходиться точно так же, как ДПДВГ, но при этом иметь более жёсткую гарантию с точки зрения дифференциальной приватности.
Вот вот такой тейк нужно было сказать в самом начале.Спасибо, что вы мне помогли разобраться и разобрались, надеюсь, вместе со мной.Так, это доказательство, оно не очень интересное.А про результаты экспериментов.Результаты экспериментов.Adдаaptive cliлипинг позволяет ээ чуть хуже, ну, в среднем в медиане сходиться приблизительно точно так же, как ФДВГ.То есть вот они показывают там с усами вот эти платы, что, ну, например, на цефри сотом там адаптив чуть-чуть получше по Экорисе на Емнисте там условно одинаково, потому что слишком простая задача.А, соответственно, Шекспир одинаково почти, да, там в сотой доли процента.А это STхаic Oracle задачи тоже там более-менее одно и то же.То есть по сути получается, что адаптивный подход, он точно такой же, как базовый зафиксированный клиппинг, но при этом даёт более хорошую гарантию, которая видна на экспериментах.

10. Переход к FTRL в федеративке

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

Плюс на него довольно долго, по-моему, искали атаку, которая бы прошла.Вот.То есть это не не с потолка сделанная какая-то
не с потолка взятый механизм, потому что он там выдерживал базовую эту мемership infренс атаку по клиентским выборкам.То есть ДЛГ, по-моему, на нём не проходил, если я правильно помню.Так.М.Да, про более сильное ограничивание м приватности, точнее, наоборот, улучшение приватности через правила отбора клиентов.Вот нам бы хотелось, наверное, ещё и агрегацию каким-то образом изменить с базовой какой-то детерминированной, условно, ну, там, усреднение по когорте или усреднение по количеству смплов, которые были видны.на этих всех градиентах, которые к нам пришли с каждого клиента, то вот можно ли получить некоторые сходящееся приватное обучение, не опираясь на равномерный отбор клиентов?То есть, например, в формате, что у нас есть какая-то функция, которая бы говорила нам: ну вот клиент доступен на данном раунде коммуникационном, да?То есть для обновления, для пересылки обновления на сервер или нет.При этом эта функция, ну, может быть вообще, в принципе, произвольной, может быть, стахастической, может быть детерминированной, может быть А всё, а я всё перебрал.
Либо стахастический, либо детерминированный, да?А так, значит, втр метод разберём.А, не знаю, кто-нибудь занимался федеративным обучением?Нет.Всех минуло.Чаша сия.А федеративном обучении довольно такой широкоизвестный метод, потому что FTRL переводится как following the regularized leader.Вот.То есть он довольно широко был распространён, однако имеет очень большой баунт по дополнительному дополнитель дополнительной памяти, которую он использует в процессе обновления.Но сейчас, ладно, давайте не об этом.Когда будет псевдокод, посмотрим на это всё.Значит, поток Угу.Куда?Поток здесь обозначает то, что нам пришло над деттой,
не на ДТтой, на ТТЙ, на итерации Т, агрегации на сервере D ит обозначает количество агрегированных элементов, точнее, как бы это по-русски-то сказать?
Собственно, что используется для агрегации на сервере и для с последующим обновлением.Вот.Вот так.Причём в D у нас могут входить, ну, типа различные обновления от различных пользователей.Ну, вот в данном формате на каждом проходе, а, у нас пользователь может встретиться только один раз, а не несколько.То есть мы не перевзвешиваем с точки зрения того, что там условно несколько раз взяли одного пользователя, потому что это, ну, нереалистично.Но если взяли одного пользователя, ну, и хватит с него.Вот можем его брать или не брать, вот это уже другой разговор.Вот, соответственно, на этом раунде это просто клипированный градиент по весам модели серверной и выбранному количеству а клиентов, но обновлений клиентов, в которые ещё могут идти по времени.То есть, например, мы, например, берём а несколько обновлений, которые пришли на этом раунде, и несколько обновлений, которые у нас сохранились минус первого, минус второго и минус третьего раундов.
Вот.И оказывается то, что это, в принципе, тоже работает.А, да, про приватную префиксную сумму.Ну, здесь вроде норм, да?Мы взяли, усреднили по всем градиентам, которые приходили к нам до момента периода Т.И, соответственно, ЖТ с тильдой - это просто некоторая зашумлённая штуковина, да?У нас истинная агрегация плюс шум, который зависит ещё и от времени зачастую.А, да, как выглядит Автоl, да?Follow the regularized leader.Ну, вообще тут following должно быть.Ну, ладно, английский - это не моя сте.А как делается обновление?Обновление - это, по сути, просто отрешивание задачи на нечастном градиенте, зашумлённом, да, жестильдой на ТТ итерации.Вот в случае, если веса в РД, то у нас обновление вот таким вот образом выглядит.Вот.То есть нам нужно научиться пересчитывать все эти жииты с тильдой таким образом, чтобы у нас бюджет приватности не тратился.Почему нам это важно научиться делать?Ну, точнее, он тратился бы, безусловно, но тратился только по добавочным обновлениям, которые приходят на этом моменте времени.
А почему нам это важно?Потому что, ну, собственно, апдейт мы всё равно сервер делаем какой-то.Нам нужно его делать в какую-то нормальную сторону, а не просто от балды куда-то сходиться.Аа при этом мы используем очень мало знаний про то, какие штуки нам передали сами клиенты, да?То есть мы каким-то образом выбираем их, а из суммы по всем временам до этого момента времени.

11. Дерево отрезков для приватных сумм

Разбирается, как FTRL использует дерево отрезков для накопления и шумления префиксных сумм без повторной траты приватного бюджета на старые обновления. Поясняется построение дерева, обновление узлов и более сильная RDP-оценка.

Вот, собственно, для этого граждане решили упороться и использовать дерево отрезков, там двоичное дерево отрезков.А, соответственно, что они делают?Что они делают?у нас считается сумма по, соответственно, в этому интервалу, если G принадлежит к области, э клиентов, которые изначально были пронумерованы.В данном случае там от одного до восьми у меня есть клиенты, да, всего восемь клиентов.Вот мы выбираем, соответственно, некоторый интервал, а шумим его и считаем, соответственно, уже на этом случае вот.А так,ну, это какой-то пример с диаграммкой, он не очень релевантен.Давайте посмотрим на пример того, как это в реальности, наверное, считается.Где оно?Вот про дерево, да?Вот у нас есть H - это просто глубина дерева по числу эпох, эпох обновлений сервера.Вот.А, собственно, имеет два ваш листьев, что логично.Вот.А для каждого двоичного интервала у нас независимо генерится вот некоторая такая величина.Здесь у нас C и сигма фиксированы.
Вот также мы говорим, что YV, да, вот эта вот случайная величина, она вот будет равна ZV именно в начале итерации.После этого, что мы делаем?Мы получаем жетый.ЖТ - это, собственно, апдейт клиента же, ну, на тта итерации, то есть разность его весов, по сути.Вот.И прибавляем его ко всем узлам на пути от листа Т к корню.От листа ТГ к корню.Вот.Ну, а это, соответственно, под суммы у нас получаются те, которые используются.А так дальше мы раскладываем вот эти вот временные промежутки от одного до Т в не пересекающиеся двоичные интервалы.По этим двоичным интервалам, этим вот всем двоичным интервалам, а мы что делаем?Мы делаем агрегацию как раз нашего G стильдей.Когда мы сделали такую агрегацию, то что у нас получилось?Что у нас лежит в ЖТ там?Давайте подумаем.
Да, градиенты и некоторая сумма шумов.Вот из такого распределения.Что можно сказать про ЖТты?Он представлен вот в таком вот виде, да?Он представим.Хорошо.А так еттый, который мы накладываем, он вот такой вот, да, что довольно очевидно.И, соответственно, оценка на ковариацию ЕТ этого на дисперсию, она вот вот такая, что довольно логично.
1:06:46 - 1:08:02
Вот где используется вот это вот непонятный алго с предпочётом различных сумм и непересекающихся отрезков, но он используется в дп в Трле вот в таком вот формате.То есть пусть у нас есть замкнутое выпуклое множество, на котором оптимизируем нужно для гарантии ДП.Просто ДПСD, на самом деле.Вот есть регуляризатор лямбда, есть C, есть сигма и есть некоторые публичные параметры дерева.Ну, условно, как мы его строим.Вот.Аэ, а строим мы его понятно, что вот сколько эпох мы сделали на данный момент на сервере, да, всё это, ну, в принципе, может быть видно атакующему, но при этом ДПС-гарантия будет сохранена.А что делается?Считается новый градиент.Он добавляется в дерево, да?Получаем по нему префикс ЖТТ вот таким вот алгосом.И уже пожет этотому делаем апдейт.Ну, вроде ничего сложного.Как?Да.Да.Внутри дерева.То есть вот у нас добавление жет этотого в дерево, да, оно активирует у нас процесс построения дерева, потому что оно, ну, как бы на каждой тта итерации обновления сервера
1:08:02 - 1:08:03
за
1:08:03 - 1:08:07
заново строится, потому что добавляется новая эпоха.
1:08:07 - 1:08:09
Да,
1:08:09 - 1:08:12
конкретно какие там нужны.
1:08:12 - 1:08:12
А в плане
1:08:12 - 1:08:27
в плане мы всегда возвращаем ТТ для Т фиксированного уже, да, последний.То есть мы всегда знаем, что мы возьмём вот такие такие такие-то шумы, потому что мы вощаем же от этой, ну, сумму суму по конкретному отреда.
1:08:28 - 1:08:29
То есть на самом деле,
1:08:29 - 1:08:32
ну, то значит нужно зашемить только новые листья, которые мы добавили.
1:08:33 - 1:08:49
Да, дада, дада, дада, да, это правда.А, ну я дурак.Вот оно тут написано, да?При получении же от этого прибавить его ко всем узлам на пути от листа к Т к корню.И, соответственно, шум у нас.Ну вот.
1:08:49 - 1:08:52
Да, да, да,
1:08:54 - 1:10:05
спасибо.Авторы были умнее, чем докладчик, поэтому сорри.Аа, да, но они снова ПРВ и тьфу ПРВ РДП использовали, получили более жёсткую оценку, причём зависящую от глубины дерева.Вот в таком формате, да.Ну вот log 2Т - это глубина дерева с точки зрения количества эпох.Вот.И соответственно, ну давайте сравним вот эту оценку и оценку с адаптивным клиппингом, который мы получали.Где она?Вот такая оценка.Но она, конечно, не очень как бы представима в нормальном формате.У меня здесь есть где-нибудь выписанная она?Нет.Ладно, нету.Но можете поверить мне, что Z дельта и тао в мину второй - это, ну, не очень маленькие величины.То есть, по сути, что мы здесь сделали?Вот тут вот у нас получилась оценка вида 2 альфа делить на какую-то на там усреднённую э сигма ввадра, да?Что у нас получилось здесь?Здесь у нас получилось наоборот альфа делить на 2.
Вот эта вот штуковина, если количество итерации не очень большое, оно довольно маленько, а сигму мы можем заранее сами выбрать.То есть формально вот эта оценка сильно лучше, чем то, что получили вот тут в адаптивном клиппинге.Но и для этого мы как бы не пересчитывали, как меня правильно поправили, а-а значение шумов и не тратили как бы бюджет приватности на то, чтобы делать вот эти вот сложные обновления.не тратили дополнительный бюджет приватности, потому что этот это в любом случае нам нужно было шумить.

12. Итоги лекции и выводы

Подводятся итоги по DLG, защищённой агрегации, адаптивному клиппингу и FTRL. В конце отдельно отмечается, что FTRL также рассматривается в онлайн-постановке, но с более слабыми гарантиями.

А так, собственно, есть ещё адаптивный случай, который работает с условными механизмами при общеопубликованной истории.Но так у меня здесь протокольчик, который, наверное, не стоит смотреть, но тут очень плохой скетч доказательства.Мне он не нравится, поэтому мы его скипнем.А это для онлайн-постановки, да?Вот про результаты.Про результаты.А есть СГД с одним моментом, довольно странное название, но это ДПС СГД с моментумом, который доказан в ДП постановке с РДП аккаунтентом.Вот, если смотреть на то, как он работает, да, мы видим, что он довольно сильно проигрывает автоллелму, а, в формате, что, ну, сильно, ну, лучше, что ли, процесс обучения.То есть, э, на низком значении бюджета приватности, а-а, мы получаем лучшее значение по финальной точности, которое мы, собственно, пытались достичь из-за того, что ДП убивает нам сходимость к глобальному минимуму.Вот.А так что у меня здесь есть?А, ну, повторную часть, наверное, сейчас нет смысла разбирать.
Так, это это уже РДП оценки.Угу, угу.Да, это уже это уже аппендикс у меня пошёл.Значит, какой момент, наверное, из лекции хочется достать?Первый момент - это то, что у нас где эта штука есть Длг.Вообще довольно полезная штука для восстановления по градиенту, а, истинных смплов обучающей выборке.применяется не только для FL-постановки, можно применять для какой-нибудь реальной постановки, так называемый reconstruction атак.А есть, собственно, проблемы с защищённой агрегацией, которую мы посмотрели через канореечные атаки, да, через канореечные градиенты.А попытались защититься.Первое, что мы сделали, ну, посмотрели на формат ДП ФидВГ, который я что-то проглотил, за что прошу прощение, который выглядит буквально так же, как ДПСД, ну, точнее, получает ту же самую оценку в формате с одним локальным апдейтом с каждогоклиента, да.Вот.а-а, дальше усилили эту оценку через РДП, э, дифференциальную прива РДП механизм дифференциальной приватности и адаптивный клиппинг.Усиление оценки получилось довольно значимое.
После этого разобрали FTRL.FTRL в формате, что, ну, нам не нужно делать апдейт и на каждой на каждом шаге.тратя, соответственно, шум на каждого из обновлений, мы можем использовать обновления, которые к нам пришли до этого в виде деревоотрезков, и использовать это для агрегации и последующего обновления на сервере.Вот такие пироги.Какая-то такая лекция получилась.Значит, Frail, наверное, ещё ремарку сделаю.Он доказан не только вот в таком формате, да, оффлайн обучения, он ещё для онлайнообучения доказан.А там оценка более плохая, как все оценки в онлайн оббучении, потому что мы уже не знаем распределение, из которого приходят.Но при этом я не знаю, наверное, какого-то более аккуратно доказанного, что ли, алгоритма ДП с онлайнпостановками.Да, возможно, у меня просто знания очень плохие.Так.А,угу.
Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

Конфиденциальные вычисления 9. Дифференциальная приватность в федеративном обучении