Рандомизированный (блочный) координатный спуск — алгоритм оптимизации, популяризованный Нестеровым (2010) и усовершенствованный в работах Ричтарика и Такача (2012). Первый анализ метода, когда он применяется к задаче минимизации гладкой выпуклой функции, был осуществлён Нестеровым (2010). Нестеровым был предложен метод к квадратичным возмущениям исходной функции с неизвестным поправочным коэффициентом. Ричтарик и Такач (2011) дали границы сложности итераций без такого требования, то есть метод применяется к целевой функции напрямую. Более того, они обобщили алгоритм для задач минимизации, то есть суммы гладкой функции и (возможно негладкой) выпуклой блочно-сепарабельной функции:
где разложен на блоков переменных/координат: и являются (простыми) выпуклыми функциями.
Пример (декомпозиция блоков): Если и , можно выбрать и .
Пример (разделяемые блоки):
, где и является стандартной евклидовой нормой.
Алгоритм Рассмотрим задачу оптимизации
где является выпуклой и гладкой функцией.
Гладкость: Под гладкостью мы понимаем следующее: мы предполагаем, что градиент покоординатно липшицево-гладкая с константами . То есть, мы предполагаем, что
для любого и , где означает частную производную по переменной .
Нестеров, Ричтарик и Такач показали, что следующий алгоритм сходится к оптимальной точке:
// Рандомизированный координатный спуск Input: // стартовая точка Output:
set x := x_0
for k := 1, ... do // обновляем координату случайно
end for
Скорость сходимости Поскольку на итерациях алгоритма образуются случайные вектора, сложность следует отражать в числе итераций, необходимых для получения приближённого решения с высокой вероятностью. В статье Ричтарика и Такача было доказано, что если , где , является оптимальным решением (), является уровнем доверительной вероятности, а является желаемой точностью, то .
Пример для конкретной функции Рисунок ниже показывает как меняется по итерациям. Задача
Расширение для блоков координат
Можно естественным образом расширить алгоритм с просто координат на блоки координат. Предположим, что мы имеем пространство . Это пространство имеет 5 координатных направлений, а именно
в которых метод может двигаться. Однако можно сгруппировать некоторые координатные направления в блоки и мы можем иметь 3 блочных координатных направлений (см. рисунок) вместо 5 координат.
См. также Координатный спуск Градиентный спуск
Примечания
Литература
Категория:Градиентные методы