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

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

4.4

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

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

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

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

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

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

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

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

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

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

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

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

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

Известный американский отраслевой обозреватель Эрик Бергер взял интервью у экипажа космического корабля Boeing, из-за технических проблем которого два астронавта задержались на орбите на девять месяцев вместо одной недели. Детали, которые они озвучили, указывают на серьезные проблемы Starliner, о которых ранее умалчивали. Люди провели немало времени при глубоко нештатной температуре. При слегка другом сценарии миссии экипаж корабля мог погибнуть. Официальные заявления NASA и Boeing сразу после июньского полета к МКС, судя по интервью, были заведомо неправдивыми.

Вчера, 12:59
Unitsky String Technologies Inc.

Рынок электромобилей стремительно расширяется. На нем представлены не только пассажирские, но и грузовые модели, а также специализированный транспорт. Сегодня главные задачи по совершенствованию транспорта на электрической тяге — увеличение пробега на одной заправке (зарядке), повышение емкости и долговечности накопителей, применение экологически «чистых» аккумуляторов на всем его жизненном цикле. Все эти задачи связаны с одним важным конструктивным элементом — аккумуляторной батареей, которая все еще остается «головной болью» многих ученых и конструкторов мира. Над решением этих задач работают и специалисты компании UST Inc. Результаты их исследований показывают, что ставку в ближайшей перспективе нужно делать не на литий-ионные аккумуляторы.

Вчера, 15:13
ФизТех

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

27 марта
Сколтех

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

Вчера, 16:30
Березин Александр

Известный американский отраслевой обозреватель Эрик Бергер взял интервью у экипажа космического корабля Boeing, из-за технических проблем которого два астронавта задержались на орбите на девять месяцев вместо одной недели. Детали, которые они озвучили, указывают на серьезные проблемы Starliner, о которых ранее умалчивали. Люди провели немало времени при глубоко нештатной температуре. При слегка другом сценарии миссии экипаж корабля мог погибнуть. Официальные заявления NASA и Boeing сразу после июньского полета к МКС, судя по интервью, были заведомо неправдивыми.

31 марта
Татьяна

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

6 марта
Юлия Трепалина

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

15 марта
Юлия Трепалина

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

18 марта
Илья

Масштабный анализ геномов показал, что вид Homo sapiens возник в результате смешения двух древних популяций. Они разделились полтора миллиона лет назад, а затем воссоединились до расселения по миру.

[miniorange_social_login]

Комментарии

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

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

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

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

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

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

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

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

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

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

Понятно
Ваше сообщение получено

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

Понятно