• Добавить в закладки
  • 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
14 августа, 11:17
Денис Яковлев

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

14 августа, 08:00
Денис Яковлев

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

12 августа, 11:29
Юлия Трепалина

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

12 августа, 11:29
Юлия Трепалина

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

9 августа, 15:19
Любовь С.

Чтобы проверить законы физики в условиях, недоступных на Земле, астрофизик Козимо Бамби (Cosimo Bambi) из Фуданьского университета (Китай) предложил отправить к центру ближайшей черной дыры «нанокрафт» — крошечный зонд, способный добраться до цели примерно за 60-75 лет благодаря наземной лазерной установке.

13 августа, 10:56
Юлия Трепалина

Ученым известны случаи близких контактов усатых китов (Mysticeti) и их дальних родственников дельфинов (Delphinidae) в дикой природе, но подобные взаимодействия ранее считали редкостью. Австралийские специалисты, изучающие китообразных, собрали почти две сотни видео и фото со всего мира, опровергающих это мнение. Судя по свидетельствам, чаще всего подобное «общение» происходит между горбатыми китами и дельфинами-афалинами.

25 июля, 07:47
Адель Романова

Прибывшая из межзвездного пространства предполагаемая комета 3I/ATLAS движется по траектории, максимально удобной для гравитационных маневров управляемого корабля, при этом возможность ее отслеживания с Земли практически минимальна. По мнению некоторых ученых, такое «поведение» объекта наводит на определенные мысли.

6 августа, 20:59
Татьяна Пичугина

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

22 июля, 14:44
ФизТех

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

[miniorange_social_login]

Комментарии

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

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

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

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

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

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

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

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

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

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

Понятно