Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

Resumo Técnico: Limites de Regret de Alta Probabilidade Adaptativos ao Ruído para Otimização Convexa Online

Enunciado do Problema
Este trabalho aborda o problema da Otimização Convexa Online (OCO) sob três desafios distintos, porém interconectados: (1) alcançar limites de regret de alta probabilidade adaptativos ao ruído para perdas fortemente convexas no cenário de informação completa; (2) determinar o custo de confiança fundamental (dependência da probabilidade de falha $\delta$) ao transitar de feedback de informação completa para feedback de bandit; e (3) estabelecer garantias simultâneas de alta probabilidade tanto para o regret cumulativo quanto para a violação de restrições de longo prazo em OCO com restrições estocásticas.

Embora resultados clássicos estabeleçam que o Gradiente Descendente Online (OGD) alcança um regret esperado de $O(\frac{G^2}{\alpha} \log T)$ para perdas $\alpha$-fortemente convexas (onde $G$ limita as normas dos gradientes), as garantias de alta probabilidade são frequentemente insuficientes para aplicações críticas de segurança. Abordagens padrão dependem da desigualdade de Azuma-Hoeffding, que produz um termo de desvio de martingala escalonando com o limite de gradiente do pior caso $G$ e o diâmetro do domínio $D$ (especificamente $GD\sqrt{2T \log(1/\delta)}$). Esse limite é frouxo quando o nível de ruído estocástico real $\sigma$ é significativamente menor que $G$, um regime comum na minimização de risco empírico regularizado. Além disso, a literatura existente carece de um tratamento unificado de adaptatividade ao ruído, estrutura de feedback e satisfação de restrições de alta probabilidade.

Metodologia e Principais Contribuições

O artigo resolve três questões em aberto através de novos argumentos de concentração e construções de limites inferiores:

1. Limites de Alta Probabilidade Adaptativos ao Ruído (Informação Completa):
   Os autores provam que o OGD projetado com tamanho de passo $\eta_t = 1/(\alpha t)$ alcança um limite de regret de alta probabilidade onde o desvio de martingala escala com o nível de ruído $\sigma$ em vez do limite do gradiente $G$.

   • Metodologia: A análise introduz um argumento de supermartingala exponencial adaptado para sequências condicionalmente sub-gaussianas. Esta técnica contorna o requisito de diferença limitada inerente à desigualdade de Freedman, que tipicamente exige a truncagem de ruído sub-gaussiano ilimitado. Ao evitar a truncagem, os autores preservam a propriedade de martingala e derivam um limite onde o termo de desvio é $O(\sigma D \sqrt{T \log(1/\delta)})$.
   • Resultado: O limite de regret é $O(\frac{G^2}{\alpha} \log T + \sigma D \sqrt{T \log(1/\delta)})$. Isso resulta em uma melhoria multiplicativa de $G/\sigma$ sobre a linha de base clássica de Azuma-Hoeffding quando $\sigma \ll G$. A prova utiliza orçamentos de probabilidade independentes para separar a truncagem das normas dos gradientes da concentração de cauda de martingala.

2. Separação do Custo de Confiança (Bandit vs. Informação Completa):
   O artigo estabelece um limite inferior minimax demonstrando uma separação fundamental no custo de confiança entre os cenários de feedback de informação completa e de bandit para OCO fortemente convexo.

   • Metodologia: Usando uma construção baseada em épocas com ruído Gaussiano aditivo, os autores aplicam o lema de Bretagnolle-Huber e argumentos de acoplamento condicional para construir uma instância difícil.
   • Resultado: No cenário de informação completa, o regret de alta probabilidade escala como $\sqrt{\log(1/\delta)}$. Em contraste, sob feedback de bandit (onde apenas valores escalares de perda são observados), o regret escala linearmente como $\log(1/\delta)$. Isto constitui a primeira prova formal de que o custo informacional da confiança é estritamente maior no cenário de bandit para problemas fortemente convexos.

3. Garantias Simultâneas de Alta Probabilidade (OCO com Restrições):
   Os autores fornecem o primeiro algoritmo que alcança o controle simultâneo de alta probabilidade do regret cumulativo e da violação de restrições de longo prazo sob restrições estocásticas que satisfazem uma condição de Slater.

   • Metodologia: A análise emprega um framework de OGD primal-dual. O limite de regret utiliza a desigualdade de Freedman (aplicável devido à limitação quase certa do ruído da restrição). A análise de violação de restrição decompõe a violação cumulativa em um componente esperado e um componente de martingala estocástica. O componente esperado é limitado via um argumento de ponto de sela e desigualdade de Markov, enquanto o componente estocástico é controlado via desigualdade de Freedman.
   • Resultado: O algoritmo alcança $O(\sqrt{T \log(m/\delta)})$ de regret e $O(\frac{\sqrt{T}}{\zeta \delta_1} + m\sqrt{T \log(m/\delta_2)})$ de violação de restrição de longo prazo. Notavelmente, o limite de violação retém um fator $1/\delta$ para o componente esperado (via desigualdade de Markov), enquanto o desvio estocástico escala com $\sqrt{\log(1/\delta)}$.

Validação Experimental
Experimentos sintéticos corroboram as previsões teóricas:

• Adaptatividade ao Ruído: Estatísticas de cauda empíricas confirmam que os quantis de regret acompanham o limite adaptativo ao ruído ($\sigma$-dependente) e permanecem bem abaixo da linha de base de Azuma-Hoeffding ($G$-dependente) quando $\sigma \ll G$.
• Custo de Confiança: Experimentos em problemas fortemente convexos 1D demonstram que o regret de informação completa cresce como $\sqrt{\log(1/\delta)}$, enquanto o regret de bandit cresce linearmente com $\log(1/\delta)$, validando a separação informacional.
• OCO com Restrições: Distribuições conjuntas de regret e violação confirmam o orçamento de probabilidade independente e a escala inversamente linear da violação com o gap de Slater $\zeta$.

Significância e Alegações
O artigo afirma resolver três questões específicas na interseção de adaptatividade ao ruído, estrutura de feedback e satisfação de restrições em OCO fortemente convexo.

• Ele fornece um refinamento de adaptatividade ao ruído dos limites de alta probabilidade, mostrando que o "preço da confiança" pode ser desacoplado da magnitude do gradiente do pior caso e vinculado, em vez disso, ao nível de ruído real.
• Estabelece uma separação formal nos custos de confiança, provando que o feedback de bandit incorre em uma penalidade linear de $\log(1/\delta)$ comparado à penalidade de raiz quadrada $\sqrt{\log(1/\delta)}$ da informação completa.
• Oferece as primeiras garantias simultâneas de alta probabilidade tanto para regret quanto para violação de restrição no cenário estocástico com restrições, esclarecendo os mecanismos estatísticos (Markov vs. Freedman) que regem cada componente.

Os autores observam que, embora a dependência $1/\delta$ no limite de violação de restrição seja apertada para a técnica de prova atual (que depende da desigualdade de ponto de sela primal-dual via desigualdade de Markov), melhorar isso para $\log(1/\delta)$ permanece um problema em aberto que requer controle por caminho (pathwise) da desigualdade de ponto de sela primal-dual. Da mesma forma, estender a adaptatividade ao ruído para cenários de bandit com interações viés-supermartingala não triviais é identificado como uma direção para trabalhos futuros.