Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values

Resumen Técnico: Cerrando la brecha de complejidad de oráculo en la optimización convexa libre de derivadas

Planteamiento del problema
Este artículo investiga la complejidad de consulta determinista para minimizar una función convexa y 1-Lipschitz sobre una bola euclídea de $d$ dimensiones ($B_d$) utilizando únicamente valores exactos de la función (oráculo de orden cero). El estudio se centra en el número de evaluaciones en el peor de los casos necesarias para encontrar una solución $\varepsilon$-aproximada, específicamente a una precisión de $\varepsilon = \Theta(d^{-1/2})$.

Antes de este trabajo, existía una brecha polinómica significativa en la literatura para este escenario:

• Límite inferior: El mejor límite inferior conocido era $\Omega(d)$, heredado del modelo más fuerte de oráculo de primer orden (donde los subgradientes están disponibles).
• Límite superior: El método determinista de Protasov (1996) requería $O(d^2 \log^2 d)$ evaluaciones para lograr la misma precisión.

La cuestión central abordada es si la falta de información sobre la derivada aumenta fundamentalmente la complejidad de lineal a cuadrática en la dimensión $d$, o si el límite $\Omega(d)$ es ajustado.

Metodología
Los autores construyen una "familia de funciones difíciles" y un "oráculo resistente" para establecer un límite inferior casi cuadrático. La demostración procede a través de cuatro componentes principales:

1. Familia de funciones difíciles: Los autores definen una clase de funciones $f_W(x, z) = \max_{i \in [m]} \{ ax_i + \langle w_i, z \rangle \}$, donde $m = d/2$, $x, z \in \mathbb{R}^m$, y las filas $w_i$ son vectores en una pequeña bola de radio $\tau = \Theta(m^{-1/2})$. Estas funciones son convexas y 1-Lipschitz. Los minimizadores de estas funciones están determinados por la proyección euclídea del origen sobre el casco convexo de los vectores que definen las piezas lineales.

2. Oráculo resistente exacto: En lugar de proporcionar una única función, el adversario mantiene un conjunto de incertidumbre "rectangular" $P_1 \times \dots \times P_m$, donde cada $P_i$ es un conjunto convexo compacto de posibles vectores de fila $w_i$. La invariante es que cualquier selección de filas de estos conjuntos produce una función consistente con el historial completo de respuestas de consulta.

   • Cuando el algoritmo realiza una consulta, el adversario analiza los funcionales afines definidos por la consulta en cada conjunto de filas.
   • Si una fila no es constante, el adversario corta el conjunto mediante un hiperplano (reduciendo la dimensión en 1) pero asegura que el conjunto restante retenga una fracción significativa de su volumen intrínseco.
   • Si todas las filas relevantes son constantes, el adversario devuelve el valor constante sin reducir la dimensión.

3. Ancho agregado e indistinguibilidad: La demostración rastrea el codimensión total y la pérdida logarítmica de volumen intrínseco a través de todos los conjuntos de filas. Después de $T = O(m^2 / \log m)$ consultas, el análisis muestra que un número lineal de conjuntos de filas permanecen de alta dimensión con un gran volumen normalizado. Utilizando la desigualdad de Urysohn y argumentos de promedio, los autores identifican una única dirección $\theta$ en la cual el ancho agregado de estos conjuntos restantes es grande.

4. Separación de minimizadores: Al seleccionar los puntos extremos de los conjuntos de filas en la dirección $\theta$, el adversario construye dos funciones distintas, $f_{W^+}$ y $f_{W^-}$, que son indistinguibles para el algoritmo (producen transcripciones idénticas). Sin embargo, debido a la estructura baricéntrica "casi uniforme" de la proyección (Lema 8), el desplazamiento agregado de las filas obliga a que los minimizadores únicos de estas dos funciones estén separados por una distancia constante. Consecuentemente, cualquier salida única del algoritmo debe estar lejos del verdadero minimizador de al menos una de las funciones, resultando en un error de $\Omega(d^{-1/2})$.

Contribuciones clave y resultados

• Límite inferior casi cuadrático: El resultado principal (Teorema 1) establece que para una precisión $\varepsilon = \Theta(d^{-1/2})$, la complejidad de valor exacto determinista es $\tilde{\Omega}(d^2)$. Específicamente, existen constantes tales que:
  $$c \frac{d^2}{\log(d+1)} \leq Q_{\text{val}}^{\text{det}}\left(d, \frac{\varepsilon_0}{\sqrt{d}}\right) \leq C d^2 \log^2(d+1)$$
  Esto cierra la brecha entre los límites inferior y superior hasta factores polilogarítmicos, demostrando que los valores exactos por sí solos son significativamente menos informativos que los oráculos de primer orden completos (que son $\Theta(d)$).

• Extensión de enteros mixtos: Utilizando un teorema de transferencia de Basu et al., los autores elevan este resultado a la optimización convexa de enteros mixtos con $n$ variables binarias y $d$ variables continuas. Demuestran que la complejidad escala multiplicativamente con la dimensión entera:
  $$Q_{\text{MI,val}}^{\text{det}}(n, d, \varepsilon) = \tilde{\Theta}(2^n d^2)$$
  Esto se mantiene incluso cuando las consultas se permiten en puntos fraccionarios arbitrarios en el dominio producto.

• Verificación formal: Los autores reconocen el uso extensivo de herramientas de IA (GPT-5.6 Sol Pro) en el desarrollo de los argumentos matemáticos. Para asegurar el rigor, proporcionan una verificación formal del límite inferior $\tilde{\Omega}(d^2)$ utilizando el lenguaje de programación Lean.

Significado y afirmaciones
El artículo afirma resolver una brecha de complejidad que data de 1996. Su importancia radica en aislar el costo de carecer de información de subgradiente en el entorno de valores reales exactos y sin ruido. Los autores enfatizan que esta separación no es un artefacto de la precisión finita o de las restricciones de memoria, sino que es intrínseca a la información proporcionada por los valores exactos de la función frente a los oráculos de primer orden.

El trabajo demuestra que, para la optimización convexa no suave, el modelo de "solo valor" es fundamentalmente más difícil que el modelo de primer orden, requiriendo un número cuadrático de consultas en la dimensión en lugar de un número lineal. La técnica de demostración, que se basa en un invariante de producto cartesiano de incertidumbre y argumentos de ancho agregado, se presenta como un mecanismo novedoso para establecer límites inferiores en entornos de información parcial sin asignar un contenido de información finito a las respuestas reales exactas.

Los autores se mantienen modestos respecto a los factores logarítmicos restantes entre los límites inferior y superior y señalan que la familia difícil actual depende de una profundidad específica ($\Theta(d^{-1/2})$), lo que deja abierta la cuestión de los límites de precisión independientes de la dimensión y el comportamiento bajo supuestos de regularidad adicionales como la suavidad.