Resumo Técnico: Otimização Convexa Online com Restrição de Capacidade e Feedback Atrasado

1. Definição do Problema

Este artigo aborda a Otimização Convexa Online (OCO) e a Otimização Convexa de Bandidos (BCO) sob duas restrições simultâneas: feedback atrasado e capacidade de rastreamento limitada.

Na aprendizagem online atrasada padrão, um aprendiz seleciona uma ação $x_t$ no arredondamento $t$, incorrendo em uma perda $f_t(x_t)$, mas recebe o feedback (gradiente ou escalar da perda) apenas no arredondamento $t + d_t$. A literatura tradicional assume que o aprendiz possui capacidade ilimitada para rastrear todos os arredondamentos pendentes até que seu feedback chegue. No entanto, em cenários práticos (por exemplo, ensaios clínicos com recursos de monitoramento limitados), o aprendiz pode rastrear apenas um número limitado de arredondamentos pendentes, denotado pela capacidade $C$. Se um arredondamento não for rastreado, seu feedback é permanentemente perdido.

O artigo formaliza isso como um jogo onde:

• O adversário fixa perdas convexas $f_t$ e atrasos $d_t$.
• O jogador mantém um conjunto de rastreamento $S$ de tamanho no máximo $C$.
• Em cada arredondamento, o jogador pode preempter (descartar) arredondamentos rastreados ou adicionar o arredondamento atual ao $S$.
• O feedback para o arredondamento $s$ é observado em $s + d_s$ se, e somente se, $s \in S$ nesse momento.
• O objetivo é minimizar o regret $R_T = \sum_{t=1}^T (f_t(x_t) - f_t(x^*))$ contra a melhor ação fixa $x^*$ no passado (in hindsight).

O artigo considera dois modelos de informação em relação aos atrasos:

1. Clairvoyant (Onisciente): Os atrasos $d_t$ são conhecidos no momento da predição.
2. Semi-Clairvoyant (Semi-onisciente): Os atrasos são revelados apenas na expiração (em $t+d_t$), consistente com as configurações padrão de aprendizagem atrasada.

2. Metodologia

Os autores propõem uma abordagem baseada em redução que decompõe o problema de capacidade restrita em dois componentes: um agendador (scheduler) e um aprendiz base (base learner).

2.1 A Estrutura de Redução

A ideia central é reduzir o problema de capacidade restrita para um novo problema de "OCO atrasado e ponderado".

• Agendador: Um algoritmo de embrulho (wrapper) gerencia o conjunto de rastreamento $S$. Ele utiliza um mecanismo de agendamento de atraso de proxy (proxy-delay scheduling). Para cada arredondamento $t$, o agendador amostra um "atraso de proxy" $d'_t$ de uma distribuição $D_t$. O arredamento $t$ é adicionado ao $S$ se $d'_t \ge 0$ e a capacidade permitir. Ele é removido de $S$ em $t + d'_t + 1$ se o feedback ainda não tiver chegado.
• Ponderação de Importância: Se o feedback para o arredondamento $s$ for observado (ou seja, $s \in S$ e $d'_s \ge d_s$), o embrulho encaminha o feedback para o aprendiz base com um peso de importância $w_s = 1 / P(d'_s \ge d_s)$. Se o feedback for perdido (devido à saturação de capacidade ou timeout precoce de proxy), o peso é definido como 0.
• Aprendiz Base: O aprendiz recebe um fluxo de feedback atrasado e ponderado. O artigo introduz algoritmos especificamente projetados para lidar com este fluxo de feedback ponderado e atrasado.

2.2 Algoritmos Base: DW-FTRL (Delayed-Weighted FTRL)

O artigo introduz e analisa dois algoritmos base para o cenário de feedback ponderado e atrasado:

1. DW-FTRL (Follow-the-Regularized-Leader Atrasado e Ponderado): Para feedback de primeira ordem (gradiente). Ele atualiza o iterado minimizando um objetivo regularizado que agrega gradientes ponderados de todos os arredondamentos observados.
2. DW-FTBL (Follow-the-Bandit-Leader Atrasado e Ponderado): Para feedback de bandido (perda escalar). Ele utiliza o estimador de gradiente de ponto único padrão (perturbando o ponto central), mas o aplica ao fluxo de feedback atrasado e ponderado.

A análise teórica desses algoritmos base estabelece limites de regret que consideram explicitamente a interação entre pesos variáveis no tempo e o acúmulo (backlog) de observações pendentes. Uma descoberta fundamental é que o regret depende das interações pareadas de pesos para arredondamentos com atrasos sobrepostos.

2.3 Agendadores de Atraso de Proxy

Para garantir que a redução funcione, o agendador deve equilibrar dois objetivos conflitantes: cobrir os atrasos reais (para observar o feedback) e evitar a saturação de capacidade. O artigo propõe dois agendadores específicos:

1. Agendador de Pareto: Adapta-se aos atrasos individuais $d_t$. Ele amostra atrasos de proxy de uma distribuição Pareto deslocada, tornando a probabilidade de rastreamento inversamente proporcional ao atraso. Isso é adequado para perdas convexas gerais.
2. Agendador de Bernoulli: Calibrado para o backlog máximo $\sigma_{max}$ (o número máximo de observações pendentes em qualquer momento). Ele amostra um atraso de proxy de $\infty$ com probabilidade $p \approx C / \sigma_{max}$ e $-1$ caso contrário. Isso gera pesos de importância uniformes, uma propriedade crucial para alcançar limites estreitos em configurações fortemente convexas e de bandido.

3. Principais Contribuições

1. Primeiros Garantias de Regret para OCO/BCO com Restrição de Capacidade: O artigo fornece os primeiros limites de regret sublineares para aprendizagem online com capacidade restrita e feedback atrasado, tanto em domínios convexos quanto fortemente convexos, para feedback de primeira ordem e de bandido.
2. Estrutura de OCO Atrasado e Ponderado: Introduz um novo cenário de problema (feedback atrasado e ponderado) e analisa variantes de FTRL para ele. Esta estrutura é de interesse independente para aprendizagem livre de escala sob atrasos.
3. Agendamento Unificado de Atraso de Proxy: Os autores unificam ideias de agendamento anteriores e introduzem um novo agendador (Bernoulli) que produz pesos uniformes, permitindo garantias mais fortes para configurações fortemente convexas e de bandido.
4. Tratamento de Parâmetros Desconhecidos: A estrutura acomoda o modelo semi-onisciente (atrasos desconhecidos no momento da predição) e utiliza o truque do dobramento (doubling trick) para lidar com $\sigma_{max}$ desconhecido sem conhecimento prévio.

4. Principais Resultados

Os limites de regret dependem do horizonte $T$, dimensão $k$, atraso total $d_{tot}$, backlog máximo $\sigma_{max}$ e capacidade $C$.

4.1 Feedback de Primeira Ordem (OCO)

• Perdas Convexas: Com $C = \Omega(\log T)$, o regret iguala a taxa atrasada não restrita ótima até fatores logarítmicos:
  $$\tilde{O}\left( G D \sqrt{d_{tot} + T} \right)$$
• Perdas Fortemente Convexas: O regret é:
  $$\tilde{O}\left( \frac{G^2}{\lambda} (\sigma_{max} + 1) \log T \right)$$
  Isso iguala a dependência ótima de $\sigma_{max}$ encontrada em configurações não restritas.

4.2 Feedback de Bandido (BCO)

Para feedback de bandido, a restrição de capacidade entra nos termos dependentes da dimensão via fatores de $(1 + \sigma_{max}/C)$.

• Perdas Convexas:
  $$\tilde{O}\left( GD \left( \sqrt{T \sigma_{max}} + T^{3/4} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/4} \sqrt{\nu k} \right) \right)$$
  onde $\nu$ é a razão de escala dos valores da função para os gradientes. O limite degrada graciosamente conforme $C$ diminui.
• Perdas Fortemente Convexas:
  $$\tilde{O}\left( \frac{G^2}{\lambda} \left( \sigma_{max} \log T + (T^2 \log T)^{1/3} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/3} (\nu k)^{2/3} \right) \right)$$

Observação Chave: Quando $C \ge \sigma_{max}$, os limites recuperam as taxas não restritas. Quando $C < \sigma_{max}$, o regret aumenta, mas permanece sublinear. A dependência de $\sigma_{max}$ (concorrência de pico) mostra-se mais natural do que a dependência de $d_{max}$ (atraso máximo) em sistemas do tipo fila (queueing-like).

5. Significância e Alegações

O artigo alega ser o primeiro a derivar garantias de regret para OCO e BCO com restrição de capacidade. Sua significância reside em:

• Unindo Teoria e Prática: Aborda a restrição realista de que os recursos de rastreamento são finitos, uma limitação ignorada pela maior parte da literatura anterior de aprendizagem atrasada, que assume capacidade infinita.
• Refinando o Modelo de Atraso: Ao adotar um modelo semi-onisciente (atrasos revelados apenas na expiração), o trabalho alinha-se mais de perto com a aprendizagem online padrão e a realidade do agendamento de tarefas do que as anteriores suposições "oniscientes".
• Degradação Graciosa: Os resultados demonstram que uma capacidade logarítmica ($C = \Omega(\log T)$) é suficiente para recuperar as taxas atrasadas padrão para feedback de primeira ordem, enquanto para feedback de bandido, o desempenho degrada graciosamente conforme a capacidade cai abaixo do backlog de pico.
• Novidade Teórica: A introdução do problema de OCO "atrasado e ponderado" e a análise específica da interação entre pesos e atrasos no FTRL fornecem novas ferramentas para analisar a aprendizagem online sob restrições de recursos.

Os autores observam que, embora seus limites para feedback de bandido convexo escalem com $\sqrt{T \sigma_{max}}$ em vez do $\sqrt{d_{tot}}$ ótimo da configuração não restrita, eles ainda melhoram os limites anteriores que dependiam de $\sqrt{T d_{max}}$. Eles identificam o fechamento desta lacuna como um problema em aberto. Além disso, sugerem que a similaridade estrutural entre seu modelo e sistemas de fila de buffer finito merece exploração adicional.