Resumo Técnico: Bandido Multi-Braços Funcional e Identificação da Melhor Função

1. Enunciado do Problema

O artigo aborda o problema de seleção de modelos em cenários com orçamentos computacionais limitados, como o treinamento competitivo de redes neurais. O desafio central é identificar a função ótima (por exemplo, a melhor arquitetura de rede neural ou configuração de hiperparâmetros) a partir de um conjunto de $K$ funções paramétricas candidatas $\{f_1, \dots, f_K\}$, onde cada função $f_i$ é definida sobre um conjunto de decisão convexo $X_i$.

Os autores formalizam dois novos setups de problemas que generalizam o clássico Bandido Multi-Braços (MAB) e a Identificação do Melhor Braço (BAI):

1. Bandido Multi-Braços Funcional (FMAB): O agente seleciona um índice $i_t$ e um vetor de decisão $x_{t, i_t} \in X_{i_t}$ em cada passo de tempo $t$. O objetivo é minimizar o regret cumulativo $R_O(T) = \sum_{t=1}^T [f_{i_t}(x_{t, i_t}) - f^*]$, onde $f^* = \min_{i} \min_{x \in X_i} f_i(x)$. Diferente do MAB padrão, onde os braços são variáveis aleatórias, aqui cada braço é uma função desconhecida otimizada via um oráculo de caixa-preta (ex: gradientes).
2. Identificação da Melhor Função (BFI): O agente visa identificar a única melhor função $J_T$ após $T$ rodadas, de modo que o regret final $R_B(T) = \min_{x \in X_{J_T}} f_{J_T}(x) - f^*$ seja minimizado.

O artigo argumenta que reduzir esses problemas ao MAB padrão (tratando cada ponto $x$ como um braço) leva a custos computacionais inviáveis devido à natureza contínua dos espaços de decisão. Em vez disso, o framework proposto aproveita a dinâmica interna dos algoritmos de otimização.

2. Metodologia: O Algoritmo F-LCB

Para resolver o FMAB e o BFI, os autores propõem o algoritmo F-LCB (Functional Lower Confidence Bound). Este é um algoritmo do tipo UCB que constrói intervalos de confiança baseados nas taxas de convergência de algoritmos de otimização base subjacentes, em vez da concentração estatística de variáveis aleatórias.

Mecanismo Central

• Otimizadores Base: Cada função candidata $f_i$ é associada a um algoritmo de otimização base $A_i$ (ex: Gradiente Descendente Projetado, Gradiente Descendente Acelerado) conhecido por ter uma taxa de convergência específica $g_i(k, \delta)$.
• Limite Inferior de Confiança (LCB): Em cada etapa, o algoritmo mantém um LCB para cada função $i$:
  $$LCB_i(k_i, \delta) = f_i(x_{i, k_i}) - g_i(k_i, \delta)$$
  Aqui, $k_i$ é o número de iterações alocadas para a função $i$, e $g_i(k_i, \delta)$ representa o limite superior teórico sobre o gap de subotimalidade após $k_i$ passos.
• Regra de Seleção: O algoritmo seleciona o braço $i_t$ com o valor mínimo de LCB.
• Atualização: Ele realiza uma iteração do otimizador base $A_{i_t}$, atualiza o valor da função e recalcula o LCB.
• Critério de Parada (para BFI): O processo para quando o gap entre a estimativa atual e o LCB cai abaixo de um limiar $\epsilon$, garantindo que a função identificada esteja dentro de $\epsilon$ do ótimo global.

O algoritmo equilibra efetivamente a exploração (alocando orçamento para funções com alta incerteza ou potencial promissor) e a explotação (refinando o melhor candidato) ao reagir imediatamente quando o LCB de um braço se torna subótimo.

3. Principais Contribuições

Contribuições Teóricas

• Formulação do Problema: O artigo introduz os frameworks FMAB e BFI, distinguindo-os formalmente do MAB clássico ao modelar os braços como tarefas de otimização com propriedades de convergência conhecidas.
• Limites Inferiores (Lower Bounds): Os autores estabelecem limites inferiores minimax para ambos, FMAB e BFI, em cenários determinísticos. Esses limites dependem da complexidade das classes de funções (ex: convexa $M$-Lipschitz, $L$-suave, $\mu$-fortemente convexa).
  • Por exemplo, para funções convexas $M$-Lipschitz, o limite inferior é $\Omega(MR\sqrt{T})$.
  • Para funções $\mu$-fortemente convexas e $L$-suaves, o limite é $\Omega(R^2)$.
• Limites Superiores de Regret (Regret Upper Bounds): O artigo prova que o algoritmo F-LCB alcança limites superiores de regret que correspondem aos limites inferiores derivados, exceto por fatores logarítmicos.
  • No caso determinístico, o regret depende da taxa de convergência $r$ do otimizador base (ex: $O(\sqrt{T})$ para $r=1/2$).
  • No caso estocástico (oráculos inexatos), os limites incorporam parâmetros de ruído e são válidos com alta probabilidade.

Contribuições Algorítmicas

• Algoritmo F-LCB: Um novo esquema de redução que integra taxas de convergência de otimização no processo de seleção de braços. Ele unifica o passo de seleção de braço com a atualização da aproximação do ótimo atual.
• Flexibilidade: O framework permite diferentes otimizadores base para diferentes braços, desde que suas taxas de convergência sejam conhecidas.

4. Resultados Experimentais

Os autores validam o F-LCB através de experimentos numéricos em conjuntos de dados sintéticos e do mundo real:

• Funções Convexas Sintéticas:
  • Convexa Suave (Smooth Convex): O F-LCB identificou com sucesso a função com o mínimo global entre três candidatas, cessando as atualizações para funções subótimas uma vez identificada.
  • Convexa Não Suave (Non-Smooth Convex): Usando funções lineares por partes e um método de subgradiente, o F-LCB demonstrou convergência para a função ótima com um regret cumulativo consistente com os limites teóricos.
  • Oráculos Inexatos: Na presença de ruído de gradiente, o F-LCB ainda identificou a melhor função, embora as curvas de convergência tenham sido menos distintas do que no caso determinístico.
• Seleção de Rede Neural (BFI):
  • Configuração: O algoritmo foi aplicado à tarefa de classificação de imagens CIFAR-100, selecionando a melhor arquitetura a partir de um conjunto de 10 modelos (incluindo variantes de MobileNet, ShuffleNet e ResNet) com menos de 5M de parâmetros.
  • Comparação: O F-LCB foi comparado contra Successive Halving (SH) e Hyperband.
  • Resultado: O F-LCB superou ambos os baselines em cenários de baixo orçamento (ex: $T=50, 100$), alcançando um ranking médio menor para o modelo selecionado. Ao contrário do Hyperband, que divide o orçamento entre múltiplas execuções de SH, o F-LCB não descarta modelos permanentemente, mas aloca recursos dinamicamente. Em orçamentos maiores ($T \ge 350$), o F-LCB teve desempenho comparável ao SH, identificando consistentemente o melhor modelo.

5. Significância e Alegações

O artigo afirma que o F-LCB fornece uma alternativa teoricamente fundamentada aos métodos heurísticos de AutoML (como Successive Halving e Hyperband) e às abordagens puramente de caixa-preta (como a Otimização Bayesiana).

• Garantias Teóricas: Ao contrário de métodos heurísticos, o F-LCB utiliza as taxas de convergência conhecidas das rotinas de otimização para derivar garantias formais de regret e limites de identificação.
• Eficiência: A abordagem é particularmente eficaz quando os orçamentos computacionais são apertados, pois evita os custos subexponenciais associados ao tratamento de problemas de otimização como MABs padrão com braços infinitos.
• Aplicabilidade: O framework é aplicável a qualquer cenário onde modelos candidatos sejam resolvidos via otimização iterativa com propriedades de convergência conhecidas (ex: relaxações convexas, seleção de métodos de otimização específicos).

Limitações Reconhecidas pelos Autores

O artigo observa explicitamente que a abordagem requer conhecimento prévio da classe funcional do objetivo e da taxa de convergência $g(k, \delta)$ do algoritmo base. Esta é uma restrição significativa para o aprendizado profundo (deep learning), onde as taxas de convergência para o treinamento de redes neurais não convexas não são bem definidas no sentido estrito exigido pela definição do algoritmo. Consequentemente, embora o método funcione para problemas convexos e tarefas de otimização específicas, sua aplicação ao treinamento geral de redes neurais depende de aproximações heurísticas de $g(k)$.