Преимущества подхода к проблеме путем формулирования функции стоимости, которая является глобально оптимизируемой

Это довольно общий вопрос (т.е. не обязательно специфический для статистики), но я заметил тенденцию в машинном обучении и статистической литературе, где авторы предпочитают придерживаться следующего подхода:

Подход 1 : Получить решение практической проблемы, сформулировав функцию стоимости, для которой можно (например, с вычислительной точки зрения) найти глобально оптимальное решение (например, путем формулировки выпуклой функции стоимости).

скорее, чем:

Подход 2 : Получить решение той же проблемы, сформулировав функцию стоимости, для которой мы, возможно, не сможем получить глобально оптимальное решение (например, мы можем получить только локально оптимальное решение для нее).

Обратите внимание, что строго говоря, две проблемы разные; Предполагается, что мы можем найти глобально оптимальное решение для первого, но не для второго.

Помимо других соображений (например, скорость, простота реализации и т. Д.), Я ищу:

1. Объяснение этой тенденции (например , математические или исторические аргументы)
2. Преимущества (практические и / или теоретические) для следования подходу 1 вместо 2 при решении практической задачи.

Я считаю, что цель должна состоять в том, чтобы оптимизировать интересующую вас функцию. Если это число ошибочных классификаций, а не, скажем, биномиальной вероятности, то вам следует попытаться минимизировать количество ошибочных классификаций. Однако по ряду упомянутых практических причин (скорость, реализация, нестабильность и т. Д.) Это может быть не так просто и даже невозможно. В этом случае мы выбираем приближенное решение.

Я знаю в основном две стратегии приближения; Либо мы придумываем алгоритмы, которые пытаются напрямую аппроксимировать решение исходной проблемы, либо мы переформулируем исходную проблему как более разрешимую проблему (например, выпуклые релаксации).

Математический аргумент в пользу предпочтения одного подхода над другим , можем ли мы понимаем , а) свойства раствора фактически вычислен и б) насколько хорошо решение приближает решение проблемы на самом деле мы заинтересованы.

Я знаю много результатов в статистике, где мы можем доказать свойства решения задачи оптимизации. Мне кажется более сложным анализировать решение алгоритма, когда у вас нет математической формулировки того, что он вычисляет (например, что он решает данную задачу оптимизации). Я, конечно, не буду утверждать, что вы не можете, но это кажется теоретическим преимуществом , если вы можете дать четкую математическую формулировку того, что вы вычисляете.

Мне неясно, дают ли такие математические аргументы практическую пользу подходу 1 по сравнению с подходом 2. Конечно, есть кто-то, кто не боится невыпуклой функции потерь .

@NRH дал ответ на этот вопрос (более 5 лет назад), поэтому я просто предложу подход 3, который объединяет подходы 1 и 2.

Подход 3 :

1. Сформулируйте и решите для глобальной оптимальности выпуклую или в любом случае глобально оптимизируемую (не обязательно выпуклую) проблему, которая «близка» к проблеме, которую вы действительно хотите решить.
2. Используйте глобально оптимальное решение из шага 1 в качестве начального (начального) решения невыпуклой задачи оптимизации, которую вы действительно хотите решить (или хотите решить больше, чем проблема, решенная в шаге 1). Надеюсь, что ваше исходное решение находится в «области притяжения» к глобальному оптимуму относительно метода решения, используемого для решения невыпуклой задачи оптимизации, которую вы действительно хотите решить.