Online Convex Optimization with Sublinear Noisy Probes

Resumo Técnico: Otimização Convexa Online com Sondas Ruidosas Sublineares

Formulação do Problema
Este artigo investiga a Otimização Convexa Online (OCO) sobre um conjunto convexo $K \subseteq \mathbb{R}^d$. No cenário padrão, um aprendiz seleciona uma decisão $x_t \in K$ em cada rodada $t$, incorre em uma perda convexa $f_t(x_t)$ escolhida adversarialmente e recebe feedback completo (a função $f_t$ ou seus subgradientes). O objetivo é minimizar o regret contra a melhor decisão fixa conhecida a posteriori (in hindsight).

Os autores introduzem um modelo de sonda (probing) unificado que generaliza duas linhas recentes de trabalho: consultas de melhor especialista sublineares no cenário de especialistas [Russo et al., 2024] e feedback de comparação por pares em OCO [Bhaskara et al., 2023b]. Neste framework, o aprendiz recebe um orçamento de $k \le T$ sondas por pares. Em uma rodada de sondagem, antes de selecionar $x_t$, o aprendiz pode consultar dois pontos $\{y_{t,1}, y_{t,2} \} \subseteq K$ e receber uma indicação de qual ponto incorre na menor perda. Crucialmente, essas sondas são ruidosas: com probabilidade $\delta$, o oráculo retorna o ponto com a maior perda (a resposta "errada"), e com probabilidade $1-\delta$, ele retorna o minimizador correto. O parâmetro de ruído $\delta \in [0, 1]$ é desconhecido para o aprendiz.

O protocolo assume um adversário oblíquo (oblivious adversary) que pré-compromete a sequência de funções de perda $\{f_t\}_{t=1}^T$ antes de o aprendiz decidir se realiza uma sondagem em qualquer rodada específica. Esta restrição é vital; se o adversário pudesse adaptar-se à decisão de sondagem, a sonda poderia ser tornada inútil (por exemplo, definindo perdas como 0 nas rodadas de sondagem), degradando o limite de regret para $\Theta(\sqrt{T-k})$.

Metodologia
O algoritmo proposto é uma versão adaptativa e aumentada por sondas do Pesos Exponenciais Contínuos (CEW). O núcleo da intuição técnica baseia-se em um efeito de redução de variância combinado com uma análise de segunda ordem (baseada em variância) do algoritmo CEW.

1. Redução de Variância via Sondagem:
   Em uma rodada de sondagem, o algoritmo amostra dois pontos independentemente da distribuição de densidade atual $p_t$. Ao jogar o ponto com a menor perda observada (ou aquele sugerido pela sonda), a perda esperada diminui em uma quantidade proporcional à variância da função de perda sob $p_t$, denotada $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$. Especificamente, para sondas sem ruído, a perda esperada é reduzida por $v_t$.

2. Lidando com Sondas Ruidosas (Meta-Aprendiz):
   Como $\delta$ é desconhecido, o algoritmo emprega um Meta-Aprendiz leve (especificamente o AdaHedge) para decidir se deve "seguir" a sugestão da sonda ou "inverter" a sugestão. O Meta-Aprendiz opera sobre duas ações: $F$ (seguir) e $I$ (inverter). Ele atualiza seus pesos com base nas perdas incorridas por essas duas ações hipotéticas nas rodadas de sondagem. Isso permite que o algoritmo adapte a confiança na sonda quando ela é informativa ($\delta$ longe de $1/2$) e a ignore quando ela não é informativa.

3. Decomposição de Regret:
   A análise de regret decompõe a perda total em dois componentes:

   • Rodadas sem sondagem: O algoritmo segue a atualização padrão do CEW. O regret é limitado usando uma análise de segunda ordem (seguindo de Rooij et al., 2014) que relaciona o regret base ao variância cumulativa $V_T = \sum v_t$.
   • Rodadas de sondagem: A perda é limitada pela perda da melhor das duas ações do Meta-Aprendiz ($F$ ou $I$), mais um termo de regret para o próprio Meta-Aprendiz. A análise mostra que a "melhor" ação alcança uma redução de perda proporcional a $|1-2\delta|v_t$.

Principais Resultados
O artigo estabelece que um orçamento sublinear de sondas por pares ruidosas pode comprovadamente melhorar o regret de pior caso no regime de feedback completo de OCO.

• Perdas Convexas Gerais: Para perdas convexas gerais limitadas em $[0, 1]$ sobre um conjunto convexo $K$, o regret esperado é:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  Este limite é apertado (até fatores logarítmicos em $T$) em relação ao horizonte $T$, ao orçamento de sondas $k$ e ao parâmetro de ruído $\delta$. O regret degrada suavemente conforme $\delta \to 1/2$ (lançamento de moeda).

• Predição com Especialistas: No caso especial do cenário de especialistas (perdas lineares sobre os vértices do simplex $\Delta^{d-1}$), o limite melhora para:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  Estas taxas são completamente apertadas em todos os parâmetros, incluindo a dimensão $d$.

Significância e Contribuições
Os autores alegam várias contribuições significativas:

1. Unificação: O trabalho unifica o modelo de sondagem discreta de "melhor especialista" e o modelo de "comparação por pares" contínuo, demonstrando que sondas por pares são tão informativas quanto sondas de melhor especialista para alcançar taxas de regret ótimas.
2. Robustez ao Ruído: Diferente de trabalhos anteriores que frequentemente assumem modelos de ruído sem ruído ou específicos, este framework lida com níveis de ruído desconhecidos $\delta$ e alcança a dependência ótima de $|1-2\delta|$.
3. Inovação Técnica: A análise evita o uso de maquinaria de privacidade diferencial e suposições sobre normas de gradiente ou curvatura (que eram exigidas em trabalhos anteriores como Bhaskara et al., 2023b). Em vez disso, ela utiliza um argumento de redução baseado em variância.
4. Otimalidade: O artigo fornece limites inferiores correspondentes (no Apêndice A) mostrando que as taxas derivadas são apertadas para o cenário de especialistas e apertadas em $T, k, \delta$ para conjuntos convexos gerais.

Os autores observam que, embora as garantias teóricas sejam fortes, o algoritmo principal requer o cálculo de integrais sobre conjuntos convexos, o que pode ser computacionalmente difícil em geral. Eles identificam o desenvolvimento de algoritmos eficientes que alcancem garantias comparáveis como uma direção aberta.