Мы рассматриваем задачу выбора модели, в которой задано множество кандидатных параметрических функций и требуется найти функцию с наименьшим минимумом и соответствующую точку минимума. Эта задача возникает при состязательном обучении нейронных сетей, где задан набор кандидатов, а ограниченный вычислительный бюджет не позволяет использовать полный перебор. Чтобы решить эту задачу, мы предлагаем обобщения классических постановок многорукого бандита (MAB) и идентификации лучшей руки (BAI), поскольку использование классических постановок MAB и BAI приводит к недопустимым вычислительным затратам. Мы называем предложенные постановки задачей функционального многорукого бандита (FMAB) и задачей идентификации наилучшей функции (BFI) соответственно. Для этих задач мы устанавливаем нижние оценки регрета для различных классов кандидатных функций. Для решения задач FMAB и BFI мы предлагаем новую схему сведения для построения алгоритма F-LCB — алгоритма типа UCB, основанного на базовых алгоритмах нелинейной оптимизации с известными скоростями сходимости. Алгоритм F-LCB объединяет шаг выбора руки и обновление текущего приближения оптимума. Мы приводим верхние оценки регрета для F-LCB на основе известных скоростей сходимости лежащих в основе базовых алгоритмов. Верхние оценки регрета совпадают с выведенными нижними оценками с точностью до логарифмического множителя. Численные эксперименты подтверждают, что предложенный подход корректно определяет оптимальную функцию и находит её точку минимума как в гладком, так и в негладком выпуклом случаях. Аналогично, F-LCB сходится быстрее алгоритмов SuccessiveHalving и Hyperband для задачи выбора модели, где кандидатные функции — это нейронные сети и доступна лишь стохастическая оценка градиента.
статья