Предложен новый метод решения вариационных неравенств в условиях, когда производные нельзя вычислить точно
Коллектив ученых из МФТИ, Университета искусственного интеллекта имени Мохаммеда бен Заида (Абу-Даби,ОАЭ), Иннополиса и Сколтеха исследовал задачу решения вариационных неравенств при неточной информации о производных. Им удалось предложить новый численный метод, а также теоретически и экспериментально показать его преимущества перед старыми методами.
Работа опубликована в материалах конференции NeurIPS 2024. В последние годы вариационные неравенства стали важным инструментом в области машинного обучения и оптимизации. Они охватывают широкий класс задач, включая минимизацию и мин-макс задачи. Однако существующие методы второго и более высоких порядков для их решения требуют точного вычисления производных, что часто приводит к чрезмерным затратам на итерации.
Исследования в области вариационных неравенств начались несколько десятилетий назад с заметным прорывом в 1970-х годах, когда был разработан метод экстрагредиента. С тех пор было предложено множество методов, однако большинство из них используют точную информацию о производных функции. В данной работе авторы стремятся ответить на вопросы о том, как можно построить оптимальные методы с учетом этой неточности.
В новой статье, представленной на конференции NeurIPS 2024, исследовано влияние неточности якобиана на методы второго порядка, а именно: доказана нижняя оценка сложности (граница быстрее которой методы с неточным якобианом не могут сходится), предложен оптимальный алгоритм и предложены варианты квази-ньютоновской аппроксимации якобиана.
Авторы предложили новый алгоритм, названный ими VIJI (второй порядок метода для вариационных неравенств с неточностью Якобиана), который достигает сублинейной скорости сходимости. При знании точного значения производных он сходится с той же скоростью, что и обычные оптимальные методы второго порядка.
Авторы предложили несколько квази-ньютоновских приближений, которые значительно снижают затраты на решение вспомогательной задачи, возникающей во всех методах высокого порядка с глобальной сходимостью. Эти приближения и обеспечивают глобальную сублинейную скорость сходимости, значительно ускоряя решение по сравнение с такими традиционными методами, как метод экстраградиента и другие методы первого порядка. В работе ими были представлены как теоретические результаты, подтверждающие оптимальность предложенного алгоритма в монотонном случае, так и экспериментальные данные, демонстрирующие его эффективность.
Исследователи сравнили между собой скорость сходимости нового метода с несколькими лучшими и методами в задаче минимакса. Это задачи поиска наилучшего решения при самом худшем возможном сценарии, и они часто встречаются на практике. Например, в задаче поиска такой экономической стратегии, при которой возможные убытки будут минимальными, или в задачах проектирования систем управления или сложных систем, в которых нужно ограничивать возможный ущерб при самом плохом стечении обстоятельств.
В качестве такой функции ущерба авторы использовали функцию в 50-мерном пространстве, которая представляет из себя сумму квадратичного и небольшого кубического слагаемого, которое обеспечивает наличие минимумов и максимумов.
«Наше исследование показывает, что даже при наличии неточностей в Якобиане можно достигнуть значительных успехов в решении вариационных неравенств. Мы надеемся, что наши результаты откроют новые горизонты для применения высокопорядковых методов в машинном обучении», — рассказал Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ.
Работа ученых полностью закрывает вопрос о том, как влияет неточность производных второго порядка и выше на качество решения задач. Отметим, что неточные производные появляются не только при использовании разных аппроксимаций, но и в машинном обучении (батчинг). Работа авторов показывает, что квази-ньютоновские методы применимы не только к задачам минимизации, где они уже стали классикой, но и к вариационным неравенствам, где исторически они практически не использовали.
Авторам удалось успешно предложить новые подходы, которые могут быть полезны для дальнейших исследований в области оптимизации и машинного обучения. В будущем они планируют исследовать возможность интеграции неточностей в сам оператор и разработать адаптивные схемы для динамической настройки уровня неточности.
Telegram 
Дзен 
VK Физтехи разработали стохастический вариант метода Франк—Вульфа для моделирования равновесного распределения транспортных потоков. Особенность нового подхода — использование случайных фрагментов из большого массива данных — ускоряет вычисления, при этом в экспериментах метод показывает качество решения, сопоставимое с классическими алгоритмами.
Исследователи впервые подробно описали молекулярный «якорь», с помощью которого малярийный паразит проникает в клетки крови, и создали белок, блокирующий заражение. Оказалось, структура паразита сложнее и он активно перестраивает мембрану хозяина, чтобы проникнуть внутрь.
Наша планета имеет шансы уцелеть во время превращения Солнца в красного гиганта и избежать полного уничтожения в термоядерном пекле. Финальная судьба Земли определится хрупким балансом между гравитационным притяжением раздувающегося светила и потерей им своей массы, из-за которой хватка звезды ослабнет и позволит планете отодвинуться на более безопасную орбиту.
Американские ветеринары установили, что длина шага передних лап у пожилых собак отражает возрастные изменения в работе мозга. Когда у собак развивается деменция, шаги их передних лап становятся короче, причем эта связь не зависит от хронической боли в суставах.
Древнеримские инженеры проложили колоссальную сеть дорог через Европу, Северную Африку и Ближний Восток, многие участки которой до сих пор поражают безупречной прямолинейностью. Секрет строительства заключался в использовании трех особых геодезических инструментов, с помощью которых разбивали местность на ровные отрезки и размечали трассы.
Терраформировать Марс — то есть превратить в мир, где можно жить без защитных куполов — мечта человечества с того момента, как стало понятно, что это холодная планета с призрачной бескислородной атмосферой. Сейчас главный хедлайнер ее освоения — Илон Маск, компания SpaceX которого планирует первые полеты туда уже в 2028 году. Многие энтузиасты вспоминают слова Маска 14-летней давности: Красную планету надо лишь «подремонтировать», чтобы ходить без скафандра. Но между полетом и прогулками по городу-саду на Марсе лежит огромная пропасть. Пару лет назад Naked Science рассматривал положительный сценарий терраформирования. Пришло время подсчитать, сколько же лет и ресурсов потребуется.
Хотя длительность помех не превышала десяти секунд, это первый известный случай такого рода. Обычно спутникам не хватает мощности для создания радиосигналов той силы, что нужна для подобных помех.
Вселенная может оказаться «замкнутой» глобальной структурой, где свет от далеких галактик способен возвращаться к наблюдателю с разных направлений. Именно такой сценарий не удалось исключить авторам нового масштабного обзора. Проверить его предсказания астрономы смогут уже в ближайшие годы.
Ученые впервые на молекулярном уровне доказали, что обычная вода одновременно состоит из двух разных жидких состояний — более плотного и менее плотного, которые непрерывно сменяют друг друга. Раз молекулярная «двойственность» действительно существует, это подтверждает спорную 30-летнюю гипотезу. Новое открытие поможет, наконец, объяснить десятки «странных» физических аномалий воды, включая ее расширение при замерзании и парадоксальное изменение вязкости под давлением.
Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.
Понятно
Что-то в вашем комментарии показалось подозрительным, поэтому перед публикацией он пройдет модерацию.
Понятно
Из-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.
Понятно
Наши фильтры обнаружили в ваших действиях признаки накрутки. Отдохните немного и вернитесь к нам позже.
Понятно
Мы скоро изучим заявку и свяжемся с Вами по указанной почте в случае положительного исхода. Спасибо за интерес к проекту.
Понятно