Уведомления
Авторизуйтесь или зарегистрируйтесь, чтобы оценивать материалы, создавать записи и писать комментарии.
Авторизуясь, вы соглашаетесь с правилами пользования сайтом и даете согласие на обработку персональных данных.
Предложен новый метод решения вариационных неравенств в условиях, когда производные нельзя вычислить точно
Коллектив ученых из МФТИ, Университета искусственного интеллекта имени Мохаммеда бен Заида (Абу-Даби,ОАЭ), Иннополиса и Сколтеха исследовал задачу решения вариационных неравенств при неточной информации о производных. Им удалось предложить новый численный метод, а также теоретически и экспериментально показать его преимущества перед старыми методами.
Работа опубликована в материалах конференции NeurIPS 2024. В последние годы вариационные неравенства стали важным инструментом в области машинного обучения и оптимизации. Они охватывают широкий класс задач, включая минимизацию и мин-макс задачи. Однако существующие методы второго и более высоких порядков для их решения требуют точного вычисления производных, что часто приводит к чрезмерным затратам на итерации.
Исследования в области вариационных неравенств начались несколько десятилетий назад с заметным прорывом в 1970-х годах, когда был разработан метод экстрагредиента. С тех пор было предложено множество методов, однако большинство из них используют точную информацию о производных функции. В данной работе авторы стремятся ответить на вопросы о том, как можно построить оптимальные методы с учетом этой неточности.
В новой статье, представленной на конференции NeurIPS 2024, исследовано влияние неточности якобиана на методы второго порядка, а именно: доказана нижняя оценка сложности (граница быстрее которой методы с неточным якобианом не могут сходится), предложен оптимальный алгоритм и предложены варианты квази-ньютоновской аппроксимации якобиана.
Авторы предложили новый алгоритм, названный ими VIJI (второй порядок метода для вариационных неравенств с неточностью Якобиана), который достигает сублинейной скорости сходимости. При знании точного значения производных он сходится с той же скоростью, что и обычные оптимальные методы второго порядка.
Авторы предложили несколько квази-ньютоновских приближений, которые значительно снижают затраты на решение вспомогательной задачи, возникающей во всех методах высокого порядка с глобальной сходимостью. Эти приближения и обеспечивают глобальную сублинейную скорость сходимости, значительно ускоряя решение по сравнение с такими традиционными методами, как метод экстраградиента и другие методы первого порядка. В работе ими были представлены как теоретические результаты, подтверждающие оптимальность предложенного алгоритма в монотонном случае, так и экспериментальные данные, демонстрирующие его эффективность.
Исследователи сравнили между собой скорость сходимости нового метода с несколькими лучшими и методами в задаче минимакса. Это задачи поиска наилучшего решения при самом худшем возможном сценарии, и они часто встречаются на практике. Например, в задаче поиска такой экономической стратегии, при которой возможные убытки будут минимальными, или в задачах проектирования систем управления или сложных систем, в которых нужно ограничивать возможный ущерб при самом плохом стечении обстоятельств.
В качестве такой функции ущерба авторы использовали функцию в 50-мерном пространстве, которая представляет из себя сумму квадратичного и небольшого кубического слагаемого, которое обеспечивает наличие минимумов и максимумов.
«Наше исследование показывает, что даже при наличии неточностей в Якобиане можно достигнуть значительных успехов в решении вариационных неравенств. Мы надеемся, что наши результаты откроют новые горизонты для применения высокопорядковых методов в машинном обучении», — рассказал Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ.
Работа ученых полностью закрывает вопрос о том, как влияет неточность производных второго порядка и выше на качество решения задач. Отметим, что неточные производные появляются не только при использовании разных аппроксимаций, но и в машинном обучении (батчинг). Работа авторов показывает, что квази-ньютоновские методы применимы не только к задачам минимизации, где они уже стали классикой, но и к вариационным неравенствам, где исторически они практически не использовали.
Авторам удалось успешно предложить новые подходы, которые могут быть полезны для дальнейших исследований в области оптимизации и машинного обучения. В будущем они планируют исследовать возможность интеграции неточностей в сам оператор и разработать адаптивные схемы для динамической настройки уровня неточности.
Первый официальный документ, описывающий принцип действий в случае возможного контакта с внеземной цивилизацией, был принят Международной академией астронавтики (IAA) в 1989 году. С тех пор декларацию неоднократно пересматривали, а ее обновленную версию, адаптированную под реалии XXI века, ученые разработали совместно с участниками проекта по поиску инопланетян SETI.
Индийские психиатры описали необычное психическое расстройство у мужчины с алкогольной зависимостью. Так называемый синдром инкуба, сопровождаемый сексуальными галлюцинациями, развился у пациента при попытке сократить потребление спиртного.
Парадокс Циолковского — Ферми сформулировали почти век назад: во Вселенной много звезд, у них — планет. Почему же мы не видим следов других цивилизаций в небе? Автор новой гипотезы считает, что все дело в нейросетях.
В густой оранжевой дымке Титана, где температура опускается до минус 180 градусов Цельсия, происходят невозможные по земным меркам химические реакции: молекула циановодорода (HCN), рожденная в атмосфере из азота, метана и этана, могла сформировать кристаллы, объединяющие вещества противоположной природы.
Первый официальный документ, описывающий принцип действий в случае возможного контакта с внеземной цивилизацией, был принят Международной академией астронавтики (IAA) в 1989 году. С тех пор декларацию неоднократно пересматривали, а ее обновленную версию, адаптированную под реалии XXI века, ученые разработали совместно с участниками проекта по поиску инопланетян SETI.
Число несущих их клеток не просто увеличивается, механизм отбора связан с эволюционным преимуществом половых клеток. Узнать об этом помог улучшенный метод секвенирования ДНК.
Согласно новой гипотезе, сознание возникает не только из-за активности нейронов, но и благодаря физическим процессам — электромагнитным полям от движения жидкости в мозге. Эта модель, как и ее предшественники, пока носит теоретический характер, но предлагает нестандартный взгляд на проблему синхронизации работы разных отделов мозга.
Археологи Института истории материальной культуры РАН (ИИМК РАН), при поддержке фонда «История отечества» в ходе раскопок обнаружили на всемирно известной стоянке каменного века Костенки-17 в Воронежской области редчайшие украшения из зубов песца и окаменелой раковины, а также уникальный для этого времени нуклеус из бивня мамонта для снятия заготовок.
Экспедиционное судно «Эндьюранс» более века называли самым прочным деревянным судном, когда-либо построенным человеком. Но находка, сделанная на дне моря, и изучение старых писем раскрыли неприятную правду. Легендарный «Эндьюранс» Шеклтона вовсе не был непобедимым левиафаном. Напротив, он имел фатальные недостатки, а капитан знал об этом еще до того, как ушел в роковое плавание к берегам Антарктиды.
Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.
ПонятноИз-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.
ПонятноНаши фильтры обнаружили в ваших действиях признаки накрутки. Отдохните немного и вернитесь к нам позже.
ПонятноМы скоро изучим заявку и свяжемся с Вами по указанной почте в случае положительного исхода. Спасибо за интерес к проекту.
Понятно
Комментарии