- Дифференциально частная стохастическая выпуклая оптимизация для приложений сетевой маршрутизации(arXiv)
Автор: Мэттью Цао, Картик Гопалакришнан, Кайди Ян, Марко Павоне.
Вывод: проблемы сетевой маршрутизации часто встречаются во многих инженерных приложениях. Вычисление оптимальных политик маршрутизации требует знания требований сети, т. е. источника и пункта назначения (OD) всех запросов в сети. Однако соображения конфиденциальности затрудняют обмен отдельными данными OD, которые потребуются для расчета оптимальных политик. Конфиденциальность может быть особенно сложной задачей в стандартных задачах сетевой маршрутизации, поскольку источники и приемники могут быть легко идентифицированы по ограничениям сохранения потока, что делает выполнимость и конфиденциальность взаимоисключающими. В этой статье мы представляем дифференциально частный алгоритм для задач сетевой маршрутизации. Основным компонентом является переформулировка сетевой маршрутизации, которая перемещает все параметры, зависящие от пользовательских данных, из набора ограничений в целевую функцию. Затем мы представляем алгоритм решения этой формулировки, основанный на дифференциально частном варианте стохастического градиентного спуска. В этом алгоритме дифференциальная конфиденциальность достигается путем введения шума, и можно задаться вопросом, не ухудшает ли это введение шума качество решения. Мы доказываем, что наш алгоритм является как дифференциально частным, так и асимптотически оптимальным, поскольку размер обучающей выборки стремится к бесконечности. Мы подтверждаем теоретические результаты численными экспериментами на сети дорожного движения, которые показывают, что наш алгоритм на практике обеспечивает дифференциально частные и близкие к оптимальным решения.
2.Однопроекционная процедура для бесконечномерных задач выпуклой оптимизации(arXiv)
Автор :Хоа Т. Буй, Регина С. Бурачик, Евгений А. Нурминский, Мэттью К. Там
Аннотация: в этой работе мы рассматриваем класс задач выпуклой оптимизации в реальном гильбертовом пространстве, которые можно решить, выполнив одну проекцию, т. е. проецируя недопустимую точку на допустимое множество. Наши результаты улучшают результаты, установленные для линейного программирования в Nurminski (2015), путем рассмотрения задач, которые: (i) могут иметь несколько решений, (ii) не удовлетворяют строгим дополнительным условиям и (iii) имеют нелинейные выпуклые ограничения. В качестве побочного продукта нашего анализа мы предоставляем количественную оценку необходимого расстояния между недопустимой точкой и допустимым множеством, чтобы ее проекция была решением проблемы. Наш анализ опирается на свойство «резкости» набора ограничений; новое свойство, которое мы вводим здесь.
