¿Es inútil proporcionar gradientes aproximados a un optimizador basado en gradiente?

¿No tiene sentido utilizar algoritmos de optimización basados ​​en gradiente si solo puede proporcionar un gradiente numérico? Si no, ¿por qué proporcionar un gradiente numérico en primer lugar si es trivial realizar una diferenciación finita para la biblioteca de optimización en sí?

[EDITAR]

• Solo para aclarar, mi pregunta es en un sentido más general que una aplicación específica. Aunque mi campo de aplicación es la optimización de probabilidad bajo varios marcos estadísticos.

• Mi problema con la diferenciación automática es que siempre parece haber una trampa. O bien, la biblioteca AD no puede propagarse a las llamadas de la biblioteca externa (como BLAS) o tiene que volver a trabajar su flujo de trabajo tan drásticamente que hace que sea difícil lidiar con él ... especialmente si está trabajando con lenguajes sensibles al tipo. Mis quejas con AD son un tema completamente diferente. ¡Pero quiero creer!

• Supongo que necesito formular mejor mi pregunta, pero estoy haciendo un mal trabajo al respecto. Si tengo la opción de usar un algoritmo de optimización sin derivadas o un algoritmo de optimización basado en derivadas con la advertencia de que solo puedo darle un gradiente numérico, ¿cuál será en promedio superior?

Para complementar la excelente respuesta de Brian, permítanme dar un poco de antecedentes (editoriales). Los métodos de optimización sin derivados se definen como métodos que solo hacen uso de evaluaciones de funciones, y son básicamente todas las variaciones de "muestrear el conjunto admisible de manera más o menos sistemática y guardar el mejor valor de función": eso es todo lo que puede hacer con la información. Estos métodos se pueden subdividir aproximadamente en

1. $1$ sobre su función, esto es todo lo que puede hacer, y puede que tenga suerte.

2. Métodos deterministas , donde la selección de muestras no es aleatoria, es decir, se basa únicamente en evaluaciones de funciones anteriores. El ejemplo más famoso es probablemente el método Nelder - Mead simplex; otros están generando métodos de búsqueda establecidos . Es importante darse cuenta de que esto solo puede funcionar si existe alguna relación (explotable) entre el valor de la función en diferentes puntos, es decir, cierta suavidad de la función. De hecho, la teoría de convergencia para, por ejemplo, el método Nelder - Mead se basa en la construcción de un método no uniformeaproximación de diferencia finita del gradiente en función de los valores de la función en los vértices del símplex y muestra que converge tanto al gradiente exacto como a cero cuando el símplex se contrae en un punto. (La variante basada en una aproximación estándar de diferencia finita se llama búsqueda por brújula ).

3. Métodos basados ​​en modelos , donde los valores de la función se utilizan para construir un modelo local de la función (por ejemplo, por interpolación), que luego se minimiza utilizando métodos estándar (basados ​​en gradiente / arpillera). Dado que una aproximación de diferencia finita es equivalente a la derivada exacta de un interpolante polinomial, el enfoque clásico de "gradiente numérico" también se incluye en esta clase.

Como puede ver, los límites entre estas clases son fluidos y, a menudo, solo una cuestión de interpretación. Pero la moraleja debe ser clara: asegúrese de utilizar toda la información disponible sobre la función que está minimizando. Para citar a Cornelius Lanczos:

La falta de información no puede remediarse con ningún truco matemático.

Después de todo, si no sabe nada acerca de su función, podría ser completamente aleatorio, y minimizar un valor aleatorio es una tarea tonta ...

Si su objetivo es fluido, usar aproximaciones de diferencias finitas a la derivada es a menudo más efectivo que usar un algoritmo de optimización libre de derivadas. Si tiene un código que calcula las derivadas exactamente, normalmente es mejor usar ese código en lugar de usar aproximaciones de diferencias finitas.

Aunque algunas bibliotecas de optimización calcularán aproximaciones de diferencias finitas para usted utilizando automáticamente la heurística para determinar los parámetros de tamaño de paso, puede ser mejor usar sus propias rutinas para calcular las aproximaciones de diferencias finitas, ya sea porque tiene un mejor conocimiento de los tamaños de paso apropiados o porque estructura especial en la función que su código puede explotar.

Otra opción que a menudo vale la pena es utilizar técnicas de diferenciación automática para producir una subrutina que calcule las derivadas analíticas del código fuente para calcular la función objetivo en sí.

Su pregunta se refiere a optimizadores basados ​​en gradiente, por lo que creo que Brian tenía razón. Solo compartiría, ya que actualmente estoy luchando con eso, algunos de los problemas.

Los problemas con la diferencia finita son 1) el rendimiento, porque debe volver a evaluar la función nuevamente para cada dimensión, y 2) puede ser difícil elegir un buen tamaño de paso. Si el paso es demasiado grande, la suposición de linealidad de la función puede no ser válida. Si el paso es demasiado pequeño, puede encontrarse con el ruido en la función en sí, porque las derivadas amplifican el ruido. Este último puede ser un problema real si la función implica resolver ecuaciones diferenciales. Si es posible calcular los gradientes analíticamente, o usando ecuaciones de sensibilidad, ciertamente será más preciso y quizás más rápido.

Hay otro enfoque que puede probar si aún no ha invertido demasiado tiempo en el software, y es ejecutarlo con aritmética compleja. Se llama diferenciación de pasos complejos . La idea básica es cuando evalúa la función, si desea su gradiente con respecto al parámetro X, establece la parte imaginaria de X en un número muy pequeño de eps . Después de hacer el cálculo, la parte imaginaria del valor de la función, dividida por eps , es el gradiente con respecto a X. Cuando desee el gradiente con respecto a Y, debe hacerlo todo de nuevo, por supuesto. Lo interesante de esto es que epsSe puede hacer muy pequeño. La razón por la que funciona es que las reglas normales del cálculo diferencial se reflejan exactamente en las reglas de la aritmética compleja.

Dicho esto, considero que no es una panacea, porque no siempre es fácil hacer una función complicada en aritmética compleja, no vale la pena si el gradiente se puede calcular analíticamente, y en el caso de ecuaciones diferenciales es exactamente equivalente a ecuaciones de sensibilidad , que estoy haciendo según sea necesario.