Вариационные неравенства (VI) появились как универсальная структура для решения широкого круга задач.Стохастические методы оказались мощными инструментами для решения таких задач, но они часто страдают от неустранимой дисперсии, что требует разработки методов снижения дисперсии. В этой работе мы предлагаем новый алгоритм со сниженной стохастической дисперсией для решения стохастических...
In [1], an information-theoretic model of massive uncoordinated multiple access was introduced and a random coding bound was obtained that can be applied in both asymptotic and non-asymptotic regimes. An improvement for the asymptotic regime was proposed in [2] using Gordon’s lemma on the minimum of a Gaussian process. In this work, we are going to prove a non-asymptotic analogue of the second...
Мы предлагаем новый стохастический алгоритм ExtraSAGA для решения вариационных неравенств, сочетающий преимущества ExtraGradient и SAGA с редукцией дисперсии. Теоретически доказана сходимость метода, а его эффективность подтверждена различными экспериментами. Работа расширяет возможности применения VI в оптимизации и машинном обучении.
В ходе рассмотрения топологических путей решения двойственной задачи линейного программирования возникло несколько проблем. Одна из них заключается в том, что отстутствует чёткий алгоритм для нахождения сбалансированного множества в Теореме Комии. В данном докладе будет рассмотрено алгоритмическое доказательство более слабой Теоремы KKMS, но важной для понимания, как можно было обобщить...
In Machine Learning, the non-smoothness of optimization problems, the high cost of communicating gradients between workers, and severely corrupted data during training necessitate further research of optimization methods under broader assumptions. This paper explores the efficacy of sign-based methods, which address slow transmission by communicating only the sign of each stochastic gradient....
В данной работе рассмотрены классические методы разделения операторов для решения ОДУ. Были получены общие локальные ошибки классических методов, а также оценки на норму коммутаторов, которые позволили оценить данные ошибки сверху. Также был построен обобщенный симметричный метод в случае разбиение исходного дифференциального уравнения на $N$ векторных полей, проведены оценки локальной ошибки...
Задача линейного программирования (ЛП)(1) является одной из самых распространенных задач, к которой можно свести очень большой класс проблем. Она имеет эффективный метод решения - Simplex-method, однако асимптотика его решения при некоторых условиях может вырождаться в экспоненциальную, что является неэффективно, однако в среднем она имеет линейную асимптотику, что приемлемо для этой задачи....
В работе предлагается обобщение метода кубической регуляризации Ньютона на случай $(L_0, L_1, L_2)$-гладкости третьего порядка. Показано, как адаптивный выбор параметра регуляризации позволяет обеспечить сходимости без предположения о глобальной ограниченности $\nabla^3 f(x)$. Представлены теоретические выкладки, оценка остаточного члена с помощью неравенства Гронуолла.
В работе исследуется асимптотическое поведение функции Беллмана ( V(t, x) ) в задачах оптимального управления с особыми режимами второго порядка. Основное внимание уделено построению оценок сингулярных составляющих решения уравнения Гамильтона-Якоби-Беллмана (HJB) вблизи особых траекторий, а также анализу устойчивости таких решений. Предложен метод регуляризации вырожденного гамильтониана и...
В настоящее время важной задачей математической оптимизации стало федеративное обучение, когда данные и/или части оптимизируемой функции распределены между множеством клиентских устройств и сервером, содержащим большую часть данных и обладающим наибольшими вычислительными мощностями. В такой ситуации ключевым становится не количество итераций алгоритма, а количество коммуникаций между клиентом...
В последние годы одной из ключевых задач математической оптимизации стало федеративное обучение — сценарий, в котором данные и/или компоненты оптимизируемой функции распределены между множеством клиентских устройств и центральным сервером, обладающим наибольшими вычислительными ресурсами и часто хранящим основную часть данных. В таких условиях важную роль играет не столько количество итераций...
