Ventajas de abordar un problema formulando una función de costo que es globalmente optimizable

Esta es una pregunta bastante general (es decir, no necesariamente específica para las estadísticas), pero he notado una tendencia en el aprendizaje automático y la literatura estadística donde los autores prefieren seguir el siguiente enfoque:

Enfoque 1 : Obtenga una solución a un problema práctico formulando una función de costo para la cual es posible (por ejemplo, desde un punto de vista computacional) encontrar una solución globalmente óptima (por ejemplo, formulando una función de costo convexa).

más bien que:

Enfoque 2 : Obtenga una solución para el mismo problema formulando una función de costo para la cual no podamos obtener una solución óptima a nivel mundial (por ejemplo, solo podemos obtener una solución óptima localmente).

Tenga en cuenta que hablando rigurosamente los dos problemas son diferentes; La suposición es que podemos encontrar la solución globalmente óptima para la primera, pero no para la segunda.

Dejando a un lado otras consideraciones (es decir, velocidad, facilidad de implementación, etc.), estoy buscando:

1. Una explicación de esta tendencia (por ejemplo, argumentos matemáticos o históricos)
2. Beneficios (prácticos y / o teóricos) para seguir el Enfoque 1 en lugar de 2 al resolver un problema práctico.

Creo que el objetivo debe ser optimizar la función que le interesa. Si eso es el número de clasificaciones erróneas, y no una probabilidad binomial, digamos, entonces debe intentar minimizar el número de clasificaciones erróneas. Sin embargo, por la cantidad de razones prácticas mencionadas (velocidad, implementación, inestabilidad, etc.), esto puede no ser tan fácil e incluso puede ser imposible. En ese caso, elegimos aproximar la solución.

Sé básicamente de dos estrategias de aproximación; o presentamos algoritmos que intentan aproximar directamente la solución del problema original, o reformulamos el problema original como un problema que se puede resolver más directamente (por ejemplo, relajaciones convexas).

Un argumento matemático para preferir un enfoque sobre el otro es si podemos entender a) las propiedades de la solución realmente calculada yb) qué tan bien la solución se aproxima a la solución del problema que realmente nos interesa.

Sé de muchos resultados en estadísticas donde podemos probar las propiedades de una solución a un problema de optimización. Para mí, parece más difícil analizar la solución de un algoritmo, donde no tienes una formulación matemática de lo que calcula (por ejemplo, que resuelve un problema de optimización dado). Ciertamente no afirmaré que no puedes, pero parece ser un beneficio teórico , si puedes dar una formulación matemática clara de lo que calculas.

Para mí no está claro si tales argumentos matemáticos brindan algún beneficio práctico al Enfoque 1 sobre el Enfoque 2. Ciertamente hay alguien por ahí, que no teme a una función de pérdida no convexa .

@NRH proporcionó una respuesta a esta pregunta (hace más de 5 años), así que solo ofreceré un Enfoque 3, que combina los Enfoques 1 y 2.

Enfoque 3 :

1. Formule y resuelva a la optimización global un problema convexo, o en cualquier caso, globalmente optimizable (no necesariamente convexo), que está "cerca" del problema que realmente desea resolver.
2. Use la solución globalmente óptima del paso 1 como la solución inicial (inicial) para un problema de optimización no convexo que realmente desea resolver (o más desea resolver que el problema resuelto en el paso 1). Espero que su solución inicial esté en la "región de atracción" hacia el óptimo global relativo al método de solución empleado para resolver el problema de optimización no convexo que realmente desea resolver.