О задачах квазивыпуклой гладкой оптимизации с помощью оракула сравнения

Часто при работе со многими моделями машинного обучения задачи оптимизации оказываются сложными из-за ограниченного понимания конструкций и характеристик целевых функций. Поэтому серьёзные затруднения возникают при использовании алгоритмов первого порядка, в которых вычисление градиента сложно или даже невозможно в различных сценариях. По этой причине мы обращаемся к методам без производных (методам нулевого порядка). Эта работа посвящена подходу к минимизации квазивыпуклых функций с использованием только недавно предложенного оракула сравнения. Этот оракул сравнивает значения функции в двух точках и сообщает, какое из них больше; таким образом, при предложенном подходе сравнения — это всё, что нужно для решения рассматриваемой задачи оптимизации. Предлагаемый алгоритм решения рассматриваемой задачи основан на технике оценки направления градиента на основе сравнений и нормализованном градиентном спуске на основе сравнений. Алгоритм нормализованного градиентного спуска — это адаптация градиентного спуска, которая обновляется в направлении градиентов, а не по самим градиентам. Мы доказали скорость сходимости предложенного алгоритма, когда целевая функция гладкая и строго квазивыпуклая в $R^n$; этому алгоритму требуется $O(\frac{nD^2}{ε^2}*\log(\frac{nD}{ε}))$ запросов сравнения, чтобы найти $ε$-приближение оптимального решения, где $D$ — верхняя граница расстояния между всеми генерируемыми точками итераций и оптимальным решением.