• Добавить в закладки
  • Facebook
  • Twitter
  • Telegram
  • VK
  • Печать
  • Email
  • Скопировать ссылку
23.12.2024, 13:54
ФизТех
1 742

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

❋ 4.4

Коллектив ученых из МФТИ, Университета искусственного интеллекта имени Мохаммеда бен Заида (Абу-Даби,ОАЭ), Иннополиса и Сколтеха исследовал задачу решения вариационных неравенств при неточной информации о производных. Им удалось предложить новый численный метод, а также теоретически и экспериментально показать его преимущества перед старыми методами.

Сравнение различных методов по количеству итераций, необходимых для получения заранее заданной точности решения / © NeurIPS 2024

Работа опубликована в материалах конференции NeurIPS 2024. В последние годы вариационные неравенства стали важным инструментом в области машинного обучения и оптимизации. Они охватывают широкий класс задач, включая минимизацию и мин-макс задачи. Однако существующие методы второго и более высоких порядков для их решения требуют точного вычисления производных, что часто приводит к чрезмерным затратам на итерации.

Исследования в области вариационных неравенств начались несколько десятилетий назад с заметным прорывом в 1970-х годах, когда был разработан метод экстрагредиента. С тех пор было предложено множество методов, однако большинство из них используют точную информацию о производных функции. В данной работе авторы стремятся ответить на вопросы о том, как можно построить оптимальные методы с учетом этой неточности.

В новой статье, представленной на конференции NeurIPS 2024, исследовано влияние неточности якобиана на методы второго порядка, а именно: доказана нижняя оценка сложности (граница быстрее которой методы с неточным якобианом не могут сходится), предложен оптимальный алгоритм и предложены варианты квази-ньютоновской аппроксимации якобиана.

Авторы предложили новый алгоритм, названный ими VIJI (второй порядок метода для вариационных неравенств с неточностью Якобиана), который достигает сублинейной скорости сходимости. При знании точного значения производных он сходится с той же скоростью, что и обычные оптимальные методы второго порядка.

Авторы предложили несколько квази-ньютоновских приближений, которые значительно снижают затраты на решение вспомогательной задачи, возникающей во всех методах высокого порядка с глобальной сходимостью. Эти приближения и обеспечивают глобальную сублинейную скорость сходимости, значительно ускоряя решение по сравнение с такими традиционными методами, как метод экстраградиента и другие методы первого порядка. В работе ими были представлены как теоретические результаты, подтверждающие оптимальность предложенного алгоритма в монотонном случае, так и экспериментальные данные, демонстрирующие его эффективность.

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

В качестве такой функции ущерба авторы использовали функцию в 50-мерном пространстве, которая представляет из себя сумму квадратичного и небольшого кубического слагаемого, которое обеспечивает наличие минимумов и максимумов.

«Наше исследование показывает, что даже при наличии неточностей в Якобиане можно достигнуть значительных успехов в решении вариационных неравенств. Мы надеемся, что наши результаты откроют новые горизонты для применения высокопорядковых методов в машинном обучении», — рассказал Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ.

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

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

Нашли опечатку? Выделите фрагмент и нажмите Ctrl + Enter.
Московский физико-технический институт (национальный исследовательский университет), известен также как Физтех — ведущий российский вуз по подготовке специалистов в области теоретической, экспериментальной и прикладной физики, математики, информатики, химии, биологии и смежных дисциплин. Расположен в городе Долгопрудном Московской области, отдельные корпуса и факультеты находятся в Жуковском и в Москве.
Подписывайтесь на нас в Telegram, Яндекс.Новостях и VK
Предстоящие мероприятия
19 октября, 10:00
Любовь С.

Первый официальный документ, описывающий принцип действий в случае возможного контакта с внеземной цивилизацией, был принят Международной академией астронавтики (IAA) в 1989 году. С тех пор декларацию неоднократно пересматривали, а ее обновленную версию, адаптированную под реалии XXI века, ученые разработали совместно с участниками проекта по поиску инопланетян SETI.

20 октября, 10:40
Юлия Трепалина

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

20 октября, 12:07
Александр Березин

Парадокс Циолковского — Ферми сформулировали почти век назад: во Вселенной много звезд, у них — планет. Почему же мы не видим следов других цивилизаций в небе? Автор новой гипотезы считает, что все дело в нейросетях.

17 октября, 22:00
Любовь С.

В густой оранжевой дымке Титана, где температура опускается до минус 180 градусов Цельсия, происходят невозможные по земным меркам химические реакции: молекула циановодорода (HCN), рожденная в атмосфере из азота, метана и этана, могла сформировать кристаллы, объединяющие вещества противоположной природы.

19 октября, 10:00
Любовь С.

Первый официальный документ, описывающий принцип действий в случае возможного контакта с внеземной цивилизацией, был принят Международной академией астронавтики (IAA) в 1989 году. С тех пор декларацию неоднократно пересматривали, а ее обновленную версию, адаптированную под реалии XXI века, ученые разработали совместно с участниками проекта по поиску инопланетян SETI.

18 октября, 11:06
Evgenia Vavilova

Число несущих их клеток не просто увеличивается, механизм отбора связан с эволюционным преимуществом половых клеток. Узнать об этом помог улучшенный метод секвенирования ДНК.

13 октября, 11:10
Илья Гриднев

Согласно новой гипотезе, сознание возникает не только из-за активности нейронов, но и благодаря физическим процессам — электромагнитным полям от движения жидкости в мозге. Эта модель, как и ее предшественники, пока носит теоретический характер, но предлагает нестандартный взгляд на проблему синхронизации работы разных отделов мозга.

26 сентября, 11:41
ИИМК РАН

Археологи Института истории материальной культуры РАН (ИИМК РАН), при поддержке фонда «История отечества» в ходе раскопок обнаружили на всемирно известной стоянке каменного века Костенки-17 в Воронежской области редчайшие украшения из зубов песца и окаменелой раковины, а также уникальный для этого времени нуклеус из бивня мамонта для снятия заготовок.

7 октября, 11:46
Игорь Байдов

Экспедиционное судно «Эндьюранс» более века называли самым прочным деревянным судном, когда-либо построенным человеком. Но находка, сделанная на дне моря, и изучение старых писем раскрыли неприятную правду. Легендарный «Эндьюранс» Шеклтона вовсе не был непобедимым левиафаном. Напротив, он имел фатальные недостатки, а капитан знал об этом еще до того, как ушел в роковое плавание к берегам Антарктиды.

[miniorange_social_login]

Комментарии

Написать комментарий
Подтвердить?
Подтвердить?
Причина отклонения
Подтвердить?
Не получилось опубликовать!

Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.

Понятно
Жалоба отправлена

Мы обязательно проверим комментарий и
при необходимости примем меры.

Спасибо
Аккаунт заблокирован!

Из-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.

Понятно
Что-то пошло не так!

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

Понятно
Лучшие материалы
Закрыть
Войти
Регистрируясь, вы соглашаетесь с правилами использования сайта и даете согласие на обработку персональных данных.
Ваша заявка получена

Мы скоро изучим заявку и свяжемся с Вами по указанной почте в случае положительного исхода. Спасибо за интерес к проекту.

Понятно