Hyperband

Hyperband é um algoritmo de otimização de hiperparâmetros (hyperparameter optimization) de multifidelidade (multi-fidelity) e baseado em bandits (bandit-based) projetado para encontrar boas configurações de hiperparâmetros gastando o mínimo possível de computação de treinamento. Em vez de treinar completamente cada configuração (como na clássica busca aleatória (random search) ou busca em grade (grid search)), o Hyperband avalia muitas configurações com um orçamento (budget) pequeno, descarta rapidamente as de pior desempenho usando Redução Sucessiva (Successive Halving, SH) e concentra recursos nas mais promissoras. Isso o torna especialmente eficaz quando o desempenho com treinamento parcial é preditivo do desempenho final e quando é possível usar parada antecipada (early stopping) ou pontos de verificação (checkpoint) em modelos.

O Hyperband se encaixa na área mais ampla de Otimização de Multifidelidade (Multi-Fidelity Optimization) e frequentemente é comparado com Otimização Bayesiana (Bayesian Optimization) e variantes assíncronas, como o Algoritmo de Redução Sucessiva Assíncrono (Asynchronous Successive Halving Algorithm, ASHA).

Motivação: por que o Hyperband existe

O ajuste de hiperparâmetros é um problema caro de otimização de caixa-preta: cada execução (trial) exige treinar e validar um modelo com alguns hiperparâmetros. Duas baselines comuns são:

Busca em grade: exaustiva, mas rapidamente se torna inviável.
Busca aleatória: muitas vezes surpreendentemente forte, mas ainda desperdiça computação se muitas execuções forem claramente ruins logo no início.

Em aprendizado profundo e em muitos cenários de treinamento iterativo, temos uma oportunidade adicional: podemos fazer treinamento parcial (partial training) (por exemplo, algumas épocas) e obter um sinal precoce de qualidade. Se a acurácia/perda de validação inicial correlaciona com o desempenho final, então podemos interromper execuções ruins cedo e realocar computação para as melhores.

O Hyperband formaliza esse problema de alocação de recursos como uma espécie de cenário de bandits (bandit) (múltiplos “braços (arms)” = configurações, recompensas incertas (rewards) = métrica de validação) e fornece uma forma fundamentada de equilibrar:

Exploração (exploration): testar muitas configurações de forma barata
Aproveitamento (exploitation): gastar mais orçamento nas configurações mais promissoras

Ideias centrais

1) Avaliação de multifidelidade (“orçamento”)

O Hyperband assume que você pode avaliar configurações em diferentes orçamentos (também chamados de recursos ou fidelidades), como:

épocas/iterações de treinamento
número de passos de gradiente
tamanho do subconjunto do conjunto de dados
resolução de entrada (comum em visão)
número de árvores (para árvores com boosting (boosted trees)), etc.

Uma configuração avaliada com um orçamento pequeno fornece uma estimativa barata e ruidosa de quão boa ela será no orçamento completo.

2) Redução sucessiva (parada antecipada + seleção)

O Hyperband se apoia na Redução Sucessiva:

Comece com muitas configurações treinadas/avaliadas com um orçamento pequeno.
Mantenha apenas a fração superior (por exemplo, o melhor 1/3).
Aumente o orçamento das sobreviventes.
Repita até restarem apenas algumas no orçamento máximo.

Isso é, essencialmente, uma parada antecipada estruturada: configurações ruins são eliminadas rapidamente.

3) “Grupos” para equilibrar exploração vs. aproveitamento

Uma única execução de redução sucessiva exige escolher com quantas configurações começar e qual deve ser o orçamento inicial. O Hyperband evita se comprometer com uma única escolha executando múltiplos grupos (brackets) de SH com diferentes compromissos:

Alguns grupos começam com muitas configurações com orçamento minúsculo (mais exploração).
Outros grupos começam com menos configurações com orçamento inicial maior (mais aproveitamento).

O Hyperband aloca a computação total entre esses grupos de modo que — aproximadamente — cada grupo consuma um orçamento total similar.

O algoritmo Hyperband

O Hyperband foi introduzido por Li et al. (2017). Ele é frequentemente parametrizado por:

(R): recursos máximos por configuração (por exemplo, máximo de épocas)
(\eta > 1): taxa de redução (comumente 3 ou 4). Cada etapa de redução mantém cerca de (1/\eta) das configurações e aumenta o orçamento por (\eta).

Defina:

(s_{\max} = \lfloor \log_{\eta}(R) \rfloor)
(B = (s_{\max} + 1)R) como um orçamento total canônico que o Hyperband usa para dimensionar os grupos

O Hyperband itera sobre grupos (s \in {s_{\max}, s_{\max}-1, \dots, 0}). Cada grupo corresponde a um orçamento inicial e a um número de configurações diferentes.

Fórmulas de escalonamento dos grupos (apresentação comum)

Para um determinado grupo (s):

Número inicial de configurações: [ n = \left\lceil \frac{B}{R} \cdot \frac{\eta^s}{s+1} \right\rceil ]
Orçamento inicial por configuração: [ r = R \cdot \eta^{-s} ]

Então execute redução sucessiva para (i = 0, 1, \dots, s):

número de configurações no degrau (rung) (i): [ n_i = \left\lfloor n \cdot \eta^{-i} \right\rfloor ]
orçamento no degrau (i): [ r_i = r \cdot \eta^i ]

Em cada degrau:

Treine/avalie cada configuração remanescente com orçamento (r_i).
Ordene pelo objetivo (por exemplo, perda de validação; menor é melhor).
Mantenha as (\approx n_i/\eta) melhores configurações e descarte o restante.

No degrau final, as sobreviventes terão atingido (aproximadamente) o orçamento (R).

Intuição

(s) grande ⇒ orçamento inicial (r) muito pequeno, mas muitas configurações iniciais (n). Esse grupo é agressivo na exploração.
(s) pequeno ⇒ orçamento inicial maior e menos configurações. Esse grupo é mais voltado ao aproveitamento e menos sensível a métricas muito iniciais e ruidosas.

Ao varrer todos os (s), o Hyperband se protege contra a possibilidade de que “o desempenho inicial seja enganoso” em orçamentos muito pequenos.

Degraus, orçamentos e o que “parada antecipada” significa na prática

Em sistemas práticos, você frequentemente ouvirá o Hyperband descrito em termos de degraus (rungs):

Um degrau é um nível discreto de orçamento (por exemplo, 1 época, 3 épocas, 9 épocas, …).
Quando uma execução atinge um degrau, ela reporta sua métrica.
O agendador (scheduler) decide se a execução deve ser promovida (promoted) para o próximo degrau ou interrompida.

Escolhendo um tipo de orçamento

O Hyperband é mais eficaz quando:

o orçamento é monotônico (mais orçamento geralmente melhora a estimativa), e
o progresso parcial é significativo (a métrica após 10% do treinamento correlaciona com a qualidade final).

Escolhas comuns:

Épocas/passos: padrão para aprendizado profundo.
Tamanho do subconjunto de dados: bom quando treinar com todos os dados é caro, mas tendências se transferem de subconjuntos menores.
Resolução: treine primeiro em baixa resolução; promova configurações promissoras para resoluções maiores.

Checkpointing e “continuar o treinamento”

Um detalhe prático importante: ao promover uma configuração para um orçamento maior, você normalmente quer retomar (resume) a partir do seu ponto de verificação em vez de treinar novamente do zero. Isso requer:

salvar o estado do modelo + otimizador
pipelines de dados determinísticos (ou aleatoriedade aceitável)
cuidado com cronogramas de taxa de aprendizado (learning rate schedules) (cronogramas muitas vezes dependem do total de passos)

Sem retomada, você pode perder grande parte da economia de computação.

Configurações práticas e regras gerais

Escolhendo \(\eta\)

(\eta = 3) é um padrão comum.
(\eta) maior (por exemplo, 4) poda de forma mais agressiva:
- Prós: eliminação mais rápida, menos “promoções” no total
- Contras: maior risco de descartar configurações que melhoram mais tarde (late bloomers) por causa do ruído

Se suas métricas iniciais forem muito ruidosas ou pouco informativas, prefira um (\eta) menor (poda menos agressiva).

Escolhendo \(R\) (orçamento máximo)

(R) deve ser o orçamento no qual você acredita que a avaliação é “final o suficiente” para selecionar um modelo (por exemplo, sua receita padrão de treinamento: 100 épocas, ou 50k passos). Definir (R) muito baixo pode levar a selecionar configurações que parecem boas cedo, mas seriam superadas mais tarde.

Orçamento mínimo (menor degrau)

O menor degrau é (R \cdot \eta^{-s_{\max}}), que fica próximo da menor potência de (\eta) acima de 1. Garanta que esse menor orçamento ainda seja significativo:

Se 1 época for puro ruído, considere definir o orçamento em unidades maiores (por exemplo, 5 épocas por degrau) ou reduzir (s_{\max}) diminuindo o intervalo de degraus que você usa.

Escolha da métrica e ruído

O Hyperband ranqueia execuções em cada degrau; ele não modela incerteza explicitamente. Para reduzir instabilidade:

Use uma métrica de validação estável (média ao longo de batches).
Considere múltiplas sementes apenas nos degraus mais altos (ou trate a semente como um hiperparâmetro).
Se as métricas forem extremamente ruidosas no início, use eliminação menos agressiva ((\eta) menor, menos degraus, ou orçamento mínimo mais alto).

Pseudocode (conceptual)

def hyperband(sample_config, evaluate, R, eta):
    s_max = int(log(R, eta))
    B = (s_max + 1) * R

    best = None
    for s in reversed(range(s_max + 1)):
        n = ceil((B / R) * (eta ** s) / (s + 1))
        r = R * (eta ** (-s))

        # Sample n configurations
        T = [sample_config() for _ in range(n)]

        for i in range(s + 1):
            n_i = floor(n * (eta ** (-i)))
            r_i = r * (eta ** i)

            # Evaluate each config at budget r_i
            results = [(t, evaluate(t, budget=r_i)) for t in T]

            # Keep top 1/eta fraction
            results.sort(key=lambda x: x[1])  # assume lower is better
            T = [t for (t, score) in results[: max(1, n_i // eta)]]

            # Track best seen at the largest budgets
            best = min((best, results[0]), key=lambda x: x[1]) if best else results[0]

    return best

Em implementações reais, evaluate() é incremental e pode retomar a partir de pontos de verificação; promoções acontecem ao retomar o treinamento até um orçamento maior.

Um exemplo prático: ajustando uma rede neural com épocas como orçamento

Suponha que você queira ajustar taxa de aprendizado e dropout para um classificador. O treinamento completo é de 81 épocas, e você define (\eta=3). Então os degraus podem ser:

1 época
3 épocas
9 épocas
27 épocas
81 épocas

Um grupo de “alta exploração” pode iniciar dezenas ou centenas de configurações em 1 época, manter o melhor terço e executá-las até 3 épocas, manter o melhor terço novamente, e assim por diante — terminando com apenas um pequeno conjunto treinado até 81 épocas.

Isso tende a superar a busca aleatória simples no orçamento completo porque:

Você ainda explora de forma ampla (muitas configurações iniciais),
mas não desperdiça 81 épocas em hiperparâmetros obviamente ruins.

Fundamentação teórica (alto nível)

O Hyperband se baseia em duas linhas de ideias:

Alocação de recursos no estilo bandit: você tem muitas opções (braços/configurações) e precisa decidir quanto recurso alocar para cada uma a fim de identificar as melhores sob uma restrição de orçamento.
Aproximação de multifidelidade: avaliações iniciais e baratas são imperfeitas, mas correlacionadas com o objetivo final.

A redução sucessiva tem garantias do tipo arrependimento (regret) sob suposições sobre como avaliações parciais se relacionam ao desempenho verdadeiro (e dependendo de modelos de ruído). A contribuição do Hyperband é em grande parte sobre robustez: em vez de exigir que o usuário escolha o cronograma “certo” de SH, ele executa um conjunto de cronogramas que cobre uma faixa de suposições sobre o quão informativas são as medições de baixa fidelidade.

Na prática, sua eficácia depende menos de suposições teóricas estritas e mais de correlação empírica entre desempenho cedo e tarde.

Hyperband vs Otimização Bayesiana

Otimização Bayesiana (BO) é outra abordagem popular para ajuste de hiperparâmetros. Ela constrói um modelo substituto (surrogate model) (por exemplo, processo gaussiano (Gaussian process), Estimador de Parzen Estruturado em Árvore (Tree-structured Parzen Estimator, TPE), floresta aleatória (random forest)) para prever desempenho e escolher as próximas configurações a avaliar.

Pontos fortes do Hyperband

Eficiente em computação via parada antecipada: não treina completamente a maioria das execuções.
Amigável ao paralelismo: muitas execuções podem rodar em paralelo (especialmente com variantes assíncronas).
Simples e robusto: menos suposições de modelagem; não requer modelo substituto.
Forte quando muitas configurações são ruins: descarta rapidamente essas configurações.

Pontos fortes da otimização bayesiana

Eficiente em amostras em cenários caros e de baixo ruído: quando cada avaliação é extremamente custosa e você só pode pagar por dezenas de execuções, BO frequentemente se destaca.
Aprende estrutura no espaço de busca: pode superar amostragem aleatória quando hiperparâmetros têm efeitos suaves ou correlações exploráveis.

Comparação prática

Se você pode pagar por muitas avaliações parciais baratas e quer aproveitar parada antecipada, o Hyperband frequentemente é um padrão forte.
Se as avaliações são tão caras que até o treinamento parcial é custoso, e você só consegue executar poucas execuções, BO pode ser melhor.
Muitos sistemas modernos combinam ambos: usam BO para propor configurações e promoção no estilo Hyperband/SH para alocar orçamentos. Um exemplo de destaque é o BOHB (Bayesian Optimization + HyperBand).

Hyperband vs ASHA (Redução Sucessiva Assíncrona)

O Hyperband clássico é comumente descrito como executando grupos sincronamente: ele avalia um conjunto de execuções em um degrau, espera por elas, ranqueia, e então promove.

ASHA (Algoritmo de Redução Sucessiva Assíncrono) é uma variante prática amplamente usada que remove barreiras de sincronização:

Execuções podem ser promovidas assim que terminam um degrau.
Não é necessário esperar por todas as execuções em um degrau (“problema do straggler (straggler problem)”).
Utilização muito melhor em clusters compartilhados.

Trade-offs

ASHA normalmente é mais rápido em tempo de relógio (wall-clock) para cargas paralelas.
A assincronia pode mudar levemente quais execuções são promovidas (porque o conjunto disponível para comparação depende do tempo), mas na prática frequentemente tem desempenho tão bom quanto ou melhor devido à maior vazão (throughput).

Uma forma comum de resumir:

Hyperband: especifica quantos grupos e cronogramas de degraus executar.
ASHA: especifica uma regra de promoção que funciona bem sob execução paralela e assíncrona. Muitas implementações essencialmente executam “Hyperband assíncrono” ao combinar a ideia de grupos do Hyperband com promoções no estilo ASHA.

Quando o Hyperband funciona bem (e quando não funciona)

Funciona bem quando

Sinais de validação iniciais correlacionam com o desempenho final.
O treinamento é iterativo e suporta ponto de verificação/retomada.
O espaço de busca é grande e muitas configurações são ruins.
Você tem recursos paralelos e quer alta vazão.

Casos de uso típicos:

redes neurais profundas (visão, NLP) com orçamentos baseados em épocas
ajuste de arquitetura neural ou parâmetros de aumento de dados (com proxies iniciais)
modelos com gradient boosting em que “número de árvores” pode ser um orçamento

Pode ter dificuldades quando

Existem “tardios”: alguns hiperparâmetros aprendem lentamente, mas acabam vencendo (o Hyperband pode podá-los cedo).
Curvas de aprendizado (learning curves) são não monotônicas (non-monotonic): comportamento inicial de overfitting/underfitting pode enganar os ranqueamentos.
Interações fortes com cronogramas de treinamento: por exemplo, aquecimento (warmup) da taxa de aprendizado ou decaimento cossenoidal (cosine decay) podem distorcer comparações iniciais, a menos que os orçamentos se alinhem às fases do cronograma.
Alto ruído em orçamentos pequenos: a estocasticidade domina as métricas iniciais.

Mitigações:

Aumente o orçamento mínimo / reduza o número de degraus.
Use (\eta) menor (poda menos agressiva).
Use métricas mais robustas ou suavização (smoothing).
Trate a semente aleatória como um hiperparâmetro (ou avalie as melhores configurações com múltiplas sementes no final).

Notas de implementação e boas práticas

Use pontos de verificação: promoções devem retomar o treinamento.
Reporte métricas intermediárias com frequência (por época/passo) para que agendadores possam decidir promoções.
Defina a direção do objetivo: muitos frameworks assumem “maximizar acurácia” ou “minimizar perda” — seja consistente.
Separe ajuste e treinamento final: use Hyperband para escolher hiperparâmetros e, em seguida, retreine a configuração escolhida do zero no orçamento completo para sua avaliação final do modelo (frequentemente com Validação Cruzada ou um conjunto de teste final separado).
Combine com boa amostragem: o Hyperband não dita como amostrar hiperparâmetros. Usar priors log-uniformes para taxas de aprendizado, limites sensatos e conhecimento do domínio ainda importa.

Métodos relacionados e contexto

Redução Sucessiva: o loop interno sobre o qual o Hyperband se baseia; um único cronograma fixo.
ASHA: SH assíncrono, frequentemente o padrão em sistemas distribuídos de ajuste.
BOHB: combina modelagem bayesiana com orçamentação no estilo Hyperband (fazendo a ponte entre Hyperband e BO).
Treinamento Baseado em População (Population Based Training, PBT): também realoca recursos, mas faz isso mutando e aproveitando execuções de treinamento em andamento, em vez de apenas selecionar configurações.

Dentro da taxonomia do wiki, o Hyperband é melhor entendido como um algoritmo prático e amplamente adotado em Otimização de Multifidelidade e como um contraponto/complemento orientado a computação à Otimização Bayesiana.

Resumo

Hyperband é um algoritmo de otimização de hiperparâmetros que economiza computação ao avaliar muitas configurações de forma barata, eliminar cedo as mais fracas via redução sucessiva e alocar mais orçamento para candidatos promissores. Sua principal força é transformar informações de treinamento parcial em uma estratégia sistemática de alocação de recursos por meio de múltiplos grupos que equilibram exploração e aproveitamento. Em cenários distribuídos modernos, variantes assíncronas como ASHA frequentemente são preferidas para melhor utilização do cluster, e métodos híbridos como BOHB combinam a orçamentação do Hyperband com a proposta bayesiana baseada em modelo de novas configurações.