Российские ученые из МФТИ, Сколтеха и Иннополиса провели теоретическое исследование и компьютерное моделирование новых методов оптимизации, основанных на использовании сравнений значений функции между собой без знания самих значений этой функции и ее производных. Им удалось построить более эффективные алгоритмы, чем традиционные, и открыть обсуждение использования концепции порядковых оракулов в вычислении. Работа опубликована в материалах конференции NeurIPS 2024.
Проблема черного ящика (black-box problem) в задачах оптимизации относится к ситуации, когда целевая функция или система, которую нужно оптимизировать, является непрозрачной и недоступной для анализа. Одним из подходов в решении подобных проблем являются порядковые оракулы, которые позволяют сравнивать значения функции, не обращаясь к ее значениям непосредственно, что может облегчить решение задачи оптимизации.
С недавним появлением концепции порядковых оракулов исследователи начали изменять подходы к оптимизации, используя информацию о порядке значений функции для создания более совершенных алгоритмов. Эта концепция становится особенно важной в контексте многих современных приложений, таких как обучение с подкреплением, кросс-валидация и оптимизация гиперпараметров, где доступ к данным часто ограничен.
В свежей статье, представленная на конференции NeurIPS 2024, авторы предлагают новые подходы. Они создали оптимизационный алгоритм, который использует порядковый оракул, и предложили способ ускорения этого алгоритма. Исследователи подтвердили теоретическую состоятельность предложенных методов через численные эксперименты, которые продемонстрировали их высокую производительность.
Математики сравнили, как быстро работают два алгоритма с оракулом порядка: случайный спуск по координатам с оракулом порядка (OrderRCD) и ускоренный спуск по координатам с оракулом порядка (OrderACDM). Они также сравнили их с традиционными неускоренными алгоритмами, такими как случайный спуск по координатам RCD (алгоритм Нестерова) и градиентный спуск GD.
Неускоренные алгоритмы как RCD, так и OrderRCD показали более низкую скорость сходимости по сравнению с градиентным спуском, что подтверждило теоретические выводы российских ученых. Оказалось, что OrderRCD даже превосходит аналогичный метод первого порядка RCD, несмотря на ограничения в использовании оракула. Это связано с тем, что OrderRCD на каждой итерации использует точный шаг в направлении наискорейшего спуска, находя его с помощью метода золотого сечения GRM. Кроме того, оказалось, что ускоренный метод OrderACDM достигает большей скорости сходимости, чем все неускоренные алгоритмы, включая RCD и GD.
Математики отдельно рассмотрели три случая различных видов функций: невыпуклые, выпуклые и сильно выпуклые. Оказалось, что в случае сильно выпуклых функций алгоритм показал линейную сходимость, что позволяет значительно уменьшить количество итераций, необходимых для достижения точности. Кроме того, исследователи рассмотрели случай стохастической оптимизации и показали возможные перспективы для разработки новых стохастических алгоритмов.
«Работа по внедрению концепции порядкового оракула в практику оптимизации — это важный шаг к решению сложных задач, стоящих перед современной наукой о данных и машинным обучением, — рассказал Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ. — Научное сообщество благодаря этой концепции располагает мощным инструментом, способным обеспечить значительное улучшение в скорости и эффективности оптимизационных процессов».
Работа по внедрению концепции порядкового оракула в практику оптимизации — это важный шаг к решению сложных задач, стоящих перед современной наукой о данных и машинным обучением. Научное сообщество благодаря этой концепции располагают мощным инструментом, способным обеспечить значительное улучшение в скорости и эффективности оптимизационных процессов.
Авторы не только предложили новые эффективные алгоритмы, но и открыли обсуждения для будущих исследований, связывая их с реальными задачами, такими как ухудшение пользовательского опыта в реактивных системах или настройки в распределенных обучающих средах. Кроме того, в своей работе они предложили практические рекомендации по использованию разработанных ими алгоритмов.
Комментарии (0)
VAF34
18.09.2025 07:00Впечатление, что автор сознательно не хочет пояснить смысл основного алгоритма!
Maxpt1
18.09.2025 07:00Как я понял, оракул это некоторая функция О, которая возвращает информацию о значении исходной функции f в окрестности всех точек этой функции (например, x^3 хорошо показывает поведение функции x^333 на всей её области определения и её очевидно проще вычислять). Но честно говоря, неочень понятно в чём достижение статьи и в чём открытие учёных из МФТИ, если про этот такой подход есть и статья в Википедии достаточно старая и в книгах Нестерова и Немировского про это тоже писалось.
master_program Автор
18.09.2025 07:00Нет, оракул возвращает результат сравнения двух значений функции. Значения самой функции он не возвращает.
master_program Автор
18.09.2025 07:00У Нестерова есть похожий алгоритм, так в этой работе они его обогнали по скорости, написано же.
Maxpt1
18.09.2025 07:00Я почитал саму статью... зачем там что-то в конце писали про стартап с кофе-машиной? У меня это, скажем так, вызывает улыбку.
master_program Автор
18.09.2025 07:00Определение порядкового оракула из статьи
φ(x, y) = sign [f(x) − f(y) + δ(x,y)]f(x) и f(y) — это значения целевой функции в точках x и y, которые мы хотим сравнить. Сами эти значения нам неизвестны.
-
sign[...] — это математическая функция знака. Она возвращает:
+1, если выражение в скобках больше нуля (означает, что f(x) > f(y)).
-1, если выражение меньше нуля (означает, что f(x) < f(y)).
0, если выражение равно нулю (означает, что f(x) = f(y)).
δ(x,y) — это ограниченный шум. Шум означает, что сравнение может быть неточным, но ошибка этого сравнения (δ) не превышает некоторого известного предела.
Таким образом, порядковый оракул — это механизм (черный ящик), который на вход получает две точки x и y и сообщает, какая из них "лучше" (где значение функции меньше или больше), возможно, с небольшой погрешностью.
Maxpt1
18.09.2025 07:00Если значения f(x) и f(y) неизвстны, то как проводится операция "-"?
master_program Автор
18.09.2025 07:00Результат сравнения запрашивается у оракула. Операцию "-" никто не делает.
В этом смысл самого термина "оракул".
doctorw
18.09.2025 07:00Как оракул проводит эту операцию? Это же не магия, оракул тоже должен как-то производит вычисление.
master_program Автор
18.09.2025 07:00Авторы не описывают внутренний механизм оракула (например, как работает мозг дегустатора). Они описывают его внешнее поведение или интерфейс — что он принимает на вход и что выдает на выходе. Преимущество заключается не в оракуле, а в алгоритме, который может эффективно работать, имея доступ только к такому примитивному оракулу. Вот ключевые прорывы их метода:
А. Он вообще работает (и работает эффективно)
Проблема: Классические алгоритмы (вроде градиентного спуска) здесь бесполезны. Им нужен градиент, которого нет.
Решение авторов: Они придумали, как "обмануть" систему. Они интегрировали Порядковый Оракул в метод координатного спуска (coordinate descent) с помощью линейного поиска (line search).-
Как это работает (упрощенно):
Алгоритм выбирает одно направление для улучшения, например, "давай попробуем изменить только количество сахара" (это одна координата).
Далее ему нужно решить, насколько сильно изменить количество сахара. Для этого он использует линейный поиск.
Он "просит" Порядкового Оракула сравнить несколько вариантов: "Какой кофе лучше: с 1 ложкой сахара или с 1.5 ложками?", "А если сравнить 1.5 и 1.7?".
С помощью серии таких простых сравнений (статья упоминает метод золотого сечения) алгоритм находит оптимальный шаг в выбранном направлении, не зная ни точных значений "вкуса", ни градиента!
Б. Он обеспечивает УСКОРЕНИЕ (главный результат статьи)Это и есть ответ на вопрос, вынесенный в заголовок "Acceleration Exists!".
Контекст: Методы, использующие Порядковый Оракул, существовали и раньше. Но они были "медленными", не ускоренными.
Преимущество: Авторы статьи впервые в мире представили ускоренный алгоритм оптимизации (названный ими OrderACDM), который работает исключительно на сравнениях. "Ускоренный" — это технический термин, означающий, что он сходится к оптимальному решению значительно быстрее, чем его не ускоренные аналоги.
Наглядное доказательство: На Рисунке 2 (страница 9) это показано очень четко. Линия их ускоренного метода (OrderACDM, фиолетовая) уходит вниз (то есть находит лучшее решение) гораздо быстрее, чем все остальные методы, включая классические не ускоренные аналоги.
В. Он адаптивный
За счет использования линейного поиска на каждом шаге, их алгоритм (OrderRCD) автоматически подбирает оптимальный размер шага. Ему не нужно заранее сообщать параметры функции (например, константу гладкости), что делает его более простым в применении на практике.
-
master_program Автор
18.09.2025 07:00Один из авторов статьи работал над стартапом по созданию "умной" кофемашины. Клиент, пробуя два напитка с разным составом, выступает в роли оракула, говоря, какой из них ему нравится больше. Оценка клиента "какой из напитков лучше" - играет роль порядкового оракула. Умная кофемашина, используя оценки клиента, оптимизирует состав кофе.
Maxpt1
18.09.2025 07:00Ну так клиент когда пробует эти оба напитка, оценивает их (то есть вычисляет значение функции насколько ему это кофе нравится) и потом возвращает в кофемашину свой ответ, что ему больше понравилось. Да, сама кофемашина не знает значений функции насколько тот или иной кофе вкусный, но это просто потому, что клиент ей этого не передал, но само вычисление значений функции произошло – разве нет?
knagaev
18.09.2025 07:00Здесь можно так представить: функция f(X) - значение вкуса кофе по 10-балльной системе. Вычисление функции происходит, если клиент говорит "этот кофе 7,3 балла". А здесь получается, что эта чашка вкуснее, чем эта, а сколько в каждой баллов не вычисляется.
eigrad
18.09.2025 07:00Не очень понял, это ведь тот же RLHF только в профиль? Почему не сравнивались с методами из RL? С хорошей теорией по идее можно и RLHF ускорить, но сравнение пока у них только с принципиально более проигрышными методами?
master_program Автор
18.09.2025 07:00Потому что они оценивали скорость поиска минимума конкретных видов функций. RLHF всё-таки другая область науки, хотя тут и есть пересечение.
Но в целом это вопрос к авторам, почему они только это сравнение делали.
af7
18.09.2025 07:00Как интересно...
"С недавним появлением концепции порядковых оракулов исследователи начали изменять подходы к оптимизации"
То есть в математике концепция "порядковых оракулов" появилась недавно? А вот в программировании такая концепция существует уже много десятилетий. Все классические алгоритмы сортировки основаны на этой концепции, бинарный поиск, дерево поиска, а затем по цепочке притягиваются базы данных и вообще весь IT. Потому что эти алгоритмы определены для любых объектов, и необходимо только задать функцию оракула сравнения, которая попарно может сравнивать эти объекты и выдавать результат больше, меньше или равно. В точности как описано в этой статье.
Значит, раньше программирование брало всё из математики. Теперь пришло время математики заимствовать что-то обратно.
master_program Автор
18.09.2025 07:00Недавно появился активный интерес у специалистов в области оптимизации к алгоритмам, которые избегают вычисления значений функции, но могут сравнивать их между собой.
belch84
Можете на пальцах объяснить, что такое порядковый оракул и как он работает? Мне сложно представить, как можно минимизировать функцию, не вычисляя ее значений
master_program Автор
Всё объяснение тут заключено здесь "позволяют сравнивать значения функции, не обращаясь к ее значениям непосредственно".
Значения вычислять не можем, а сравнивать два значения можем между собой.
sbw
А можно подробнее, на примере, как это делается?
master_program Автор
Пусть, например, есть точки x = a и x = b. Мы не знаем и не можем узнать, чему равны f(a) и f(b), но порядковый оракул дает ответ на вопрос, верно ли, что f(a) > f(b) или f(a) < f(b).
В практических задачах редко бывает, когда значение совсем никак узнать нельзя, но часто бывает ситуация, когда вычисление значения функции гораздо дороже, чем вычисление сравнения двух значений. В таких случаях актуально использование алгоритмов, которые используют порядковые оракулы.
domix32
А как они получают результат сравнения без вычисления собственно сравниваемых?
master_program Автор
При моделировании абстрактного алгоритма они обычно этого не делают. А так много разных случаев есть, тут в комментариях описаны некоторые примеры. Например, можно приближенно вычислять значение с точностью, достаточной для сравнения, но не большей.
domix32
А как они приближенно вычисляют? Суть вопроса кажется не особо поменялась. Если она чёрная коробка, то каким-нибудь биномом ньютона пройтись не выйдет. Или речь идёт про момент, когда уже есть условно натренированная нейронка, которая умеет дешево считать примерные значения?
master_program Автор
А в этой работе оракул - это чёрный ящик. Там не важно, как он это делает, важна оценка количества таких операций сравнения.
master_program Автор
Так я уже ответил на этот вопрос. Никак они это не вычисляют. Смысл модели оракула в алгоритме в том, что они этого вообще не делают.
А если вы хотите применить алгоритм на практике, то возможны все эти описанные в комментариях варианты и многие другие.
domix32
ну то же определение
подразумевает, что происходит вычисление функций от параметров. Каким образом получить эти значения не вычисляя функцию - как раз тот самый вопрос. Как оракул формирует их? Единственный вариант который мне известен - иметь плохо натренированную нейронку, которая даст приблизительно верное значение, но быстрее чем вычислить функцию напрямую.
master_program Автор
Наоборот, определение оракула подразумевает, что не вычисляет.
Zalechi
Правильные вопросы задаете!
Я конечно понимаю, что содержание статьи больше смахивает на новость с обычного сайта, но нама тута эти хайповые заголовки без конкретики — просто не интересны.
Emulyator
Не знаю как делает оракул для сложных функций, но, например, для f(x) = x^99999, не обязательно возводить икс в такую большую степень, чтобы сравнить значения, можно сравнить аргументы.
belch84
Если заранее известно, что функция монотонна, то для оптимизации никакой оракул и не нужен
master_program Автор
Например, в сложных климатических или физических моделях полный расчет одного набора параметров может занимать недели. Иногда проще запустить два укороченных расчета и по промежуточным результатам определить, какой из них "более перспективный", не дожидаясь финального значения.
Или, к примеру, для AB-тестирования, мы сравниваем качество вариантов между собой, но обычно нет простого показателя качества.
Дегустация вкуса, как тут было отмечено - отличный пример.
mentin
Вы оптимизируете рецепт глинтвейна, по десятку параметров: количество ингредиентов, температура, продолжительность варки и тд. Никакого значения у функции нет, но оракл-дегустатор может сказать, какой из двух вариантов ему нравится больше.
belch84
Представил себе оракула, который в процессе оптимизации так напробовался глинтвейна, что потерял способность рационально мыслить и стал выдавать безумные рекомендации
sbw
Тяжёлая это работа – оптимизатор глинтвейна))