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

Resumo Técnico: Fechando o Gap de Complexidade de Oráculo em Otimização Convexa Sem Derivadas

Enunciado do Problema
Este artigo investiga a complexidade de consulta determinística para minimizar uma função convexa e 1-Lipschitz sobre uma bola euclidiana de $d$ dimensões ($B_d$) utilizando apenas valores exatos da função (oráculo de ordem zero). O estudo foca no número de avaliações no pior caso necessárias para encontrar uma solução $\varepsilon$-aproximada, especificamente em uma precisão de $\varepsilon = \Theta(d^{-1/2})$.

Antes deste trabalho, existia um gap polinomial significativo na literatura para este cenário:

• Limite Inferior (Lower Bound): O melhor limite conhecido era $\Omega(d)$, herdado do modelo de oráculo de primeira ordem mais forte (onde subgradientes estão disponíveis).
• Limite Superior (Upper Bound): O método determinístico de Protasov (1996) exigia $O(d^2 \log^2 d)$ avaliações para alcançar a mesma precisão.

A questão central abordada é se a ausência de informação de derivada aumenta fundamentalmente a complexidade de linear para quadrática na dimensão $d$, ou se o limite $\Omega(d)$ é estrito.

Metodologia
Os autores constroem uma "família de funções difíceis" e um "oráculo resistente" para estabelecer um limite inferior quase quadrático. A prova procede através de quatro componentes principais:

1. Família de Funções Difíceis: Os autores definem uma classe de funções $f_W(x, z) = \max_{i \in [m]} \{ ax_i + \langle w_i, z \rangle \}$, onde $m = d/2$, $x, z \in \mathbb{R}^m$, e as linhas $w_i$ são vetores em uma pequena bola de raio $\tau = \Theta(m^{-1/2})$. Estas funções são convexas e 1-Lipschitz. Os minimizadores destas funções são determinados pela projeção euclidiana da origem sobre o invólucro convexo dos vetores que definem as partes lineares.

2. Oráculo Resistente Exato: Em vez de fornecer uma única função, o adversário mantém um conjunto de incerteza "retangular" $P_1 \times \dots \times P_m$, onde cada $P_i$ é um conjunto convexo compacto de possíveis vetores de linha $w_i$. O invariante é que qualquer seleção de linhas a partir destes conjuntos produz uma função consistente com todo o histórico de respostas às consultas.

   • Quando o algoritmo consulta um ponto, o adversário analisa os funcionais afins definidos pela consulta em cada conjunto de linhas.
   • Se uma linha não for constante, o adversário corta o conjunto por um hiperplano (reduzindo a dimensão em 1), mas garante que o conjunto restante retenha uma fração significativa de seu volume intrínseco.
   • Se todas as linhas relevantes forem constantes, o adversário retorna o valor constante sem reduzir a dimensão.

3. Largura Agregada e Indistinguibilidade: A prova rastreia a codimensão total e a perda logarítmica de volume intrínseco através de todos os conjuntos de linhas. Após $T = O(m^2 / \log m)$ consultas, a análise mostra que um número linear de conjuntos de linhas permanece de alta dimensão com grande volume normalizado. Usando a desigualdade de Urysohn e argumentos de média, os autores identificam uma única direção $\theta$ na qual a largura agregada destes conjuntos restantes é grande.

4. Separação de Minimizadores: Ao selecionar os pontos extremos dos conjuntos de linhas na direção $\theta$, o adversário constrói duas funções distintas, $f_{W^+}$ e $f_{W^-}$, que são indistinguíveis para o algoritmo (produzem transcrições idênticas). No entanto, devido à estrutura baricêntrica "quase uniforme" da projeção (Lema 8), o deslocamento agregado das linhas força os minimizadores únicos destas duas funções a serem separados por uma distância constante. Consequentemente, qualquer saída única do algoritmo deve estar longe do verdadeiro minimizador de pelo menos uma das funções, resultando em um erro de $\Omega(d^{-1/2})$.

Contribuições Principais e Resultados

• Limite Inferior Quase Quadrático: O resultado principal (Teorema 1) estabelece que, para precisão $\varepsilon = \Theta(d^{-1/2})$, a complexidade de valor exato determinística é $\tilde{\Omega}(d^2)$. Especificamente, existem constantes tais 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)$$
  Isso fecha o gap entre os limites inferior e superior até fatores polilogarítmicos, provando que valores exatos sozinhos são significativamente menos informativos do que oráculos de primeira ordem completos (que são $\Theta(d)$).

• Extensão de Inteiros Mistos: Usando um teorema de transferência de Basu et al., os autores elevam este resultado para otimização convexa de inteiros mistos com $n$ variáveis binárias e $d$ variáveis contínuas. Eles provam que a complexidade escala multiplicativamente com a dimensão inteira:
  $$Q_{\text{MI,val}}^{\text{det}}(n, d, \varepsilon) = \tilde{\Theta}(2^n d^2)$$
  Isso se mantém mesmo quando as consultas são permitidas em pontos fracionários arbitrários no domínio do produto.

• Verificação Formal: Os autores reconhecem o uso extensivo de ferramentas de IA (GPT-5.6 Sol Pro) no desenvolvimento dos argumentos matemáticos. Para garantir o rigor, eles fornecem uma verificação formal da prova do limite inferior $\tilde{\Omega}(d^2)$ usando a linguagem de programação Lean.

Significância e Alegações
O artigo afirma resolver um gap de complexidade que data de 1996. Sua significância reside em isolar o custo de carecer de informações de subgradiente no cenário de valores reais exatos e sem ruído. Os autores enfatizam que esta separação não é um artefato de restrições de precisão finita ou de memória, mas é intrínseca à informação fornecida por valores exatos de função versus oráculos de primeira ordem.

O trabalho demonstra que, para otimização convexa não suave, o modelo de "apenas valor" é fundamentalmente mais difícil que o modelo de primeira ordem, exigindo um número quadrático de consultas na dimensão, em vez de um número linear. A técnica de prova, baseada em um invariante de produto cartesiano de incerteza e argumentos de largura agregada, é apresentada como um mecanismo inovador para estabelecer limites inferiores em configurações de informação parcial sem atribuir conteúdo de informação finito a respostas reais exatas.

Os autores mantêm-se modestos quanto aos fatores logarítmicos restantes entre os limites inferior e superior e observam que a família de funções difíceis atual depende de uma profundidade específica ($\Theta(d^{-1/2})$), deixando aberta a questão de limites de precisão independentes da dimensão e o comportamento sob suposições de regularidade adicional, como suavidade.